Set Operations

Set Operations

1. SUBSET

   • Basic Subset
     • A is a subset of B if all elements of A are elements of B.
     • ⊆
   • Proper Subset
     • A is a proper subset of B if A is a subset of B and A is not equal to B
     • ⊂

2. UNION

   • ∪
   • A + B

3. INTERSECTION

   • ∩
   • everything the same in A + B

4. DISJOINT

   • A ∩ B = ∅

5. LESS

   • A - B (A\B) = A - (A ∩ B)

6. COMPLEMENT

   • A complement is everything in U outside of A (U\A)

7. Commutative

8. Associative

9. Distributive

10. De Morgan Laws

    • (A ∩ B) complement = A complement ∪ B complement
    • (A ∪ B)^c = A^c ∩ B^c

11. Involutivity of the Complement

    • (A^c)^c) = A
    • "An involution is a map such that applying it twice gives the (original) identity. Familiar examples: reflecting across the x-axis, the y-axis, or the origin in the plane.

12. Transitivity of Inclusion

    • A ⊆ B ∧ B ⊆ C → A ⊆ C

13. Equality of Sets

    • from (P ↔ Q) ↔ [(P → Q) ∧ (Q → P)]
    • A = B ↔ (A ⊆ B) ∧ (B ⊆ A)
    • Non-Equality of Sets
      • A != B ↔ [(A\B) ∪ (B\A)] != 0

14. POWER SET

    • P(A)
      • Recall ∅ ⊆ A. Also, A ⊆ A.
      • If A = {0, 1},
        • then P(A) = {∅, {0}, {1}, {0,1}}
        • If A = {a, b, c},
          • then P(A) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.
          • If A = ∅,
            • P(A) = {∅}
            • P(P(A)) = {∅, {∅}}
      • ∅ and {∅} are different objects. ∅ has no elements, whereas {∅} has one element.
      • P(A) and A are viewed as living in separate world to avoid phenomena like Russell's paradox.
      • If A has n elements, then P(A) has 2^n elements.
      • In the ZFC (Zermelo Fraenkel set theory) standard system, it is an axion of set theory that every set has a power set, which implies no set consisting of all possible sets could exist, else what would it power set be?

Images and files in the map