FORMULA LIBRARY : SETS

1. Basic Definitions & Representation

• Set-builder form: { x : P(x) } — the set of all x such that property P(x) holds.
• Roster form: A = { 1, 2, 3, 4 }
• Empty set: ∅ or { } — contains no element.
• Singleton set: { a } — exactly one element.
• Cardinal number: n(A) — number of distinct elements in finite set A.
• Equivalent sets: n(A) = n(B)
• Equal sets: A = B ⇔ (A ⊆ B) and (B ⊆ A)

2. Types of Sets

• Finite set: finite number of elements.
• Infinite set: infinite number of elements (e.g., N, Z, Q, R).
• Subset: A ⊆ B ⇔ (x ∈ A ⇒ x ∈ B)
• Proper subset: A ⊂ B ⇔ (A ⊆ B and A ≠ B)
• Superset: A ⊇ B ⇔ B ⊆ A
• Power set: P(A) = { X : X ⊆ A }, and n(P(A)) = 2^n(A)
• Universal set: U — the superset of all sets under consideration.

3. Operations on Sets

• Union: A ∪ B = { x : x ∈ A or x ∈ B }
• Intersection: A ∩ B = { x : x ∈ A and x ∈ B }
• Difference: A − B = { x : x ∈ A and x ∉ B }
• Symmetric difference: A Δ B = (A − B) ∪ (B − A) = (A ∪ B) − (A ∩ B)
• Complement: A’ = A^c = U − A = { x ∈ U : x ∉ A }
• Disjoint sets: A ∩ B = ∅

4. Laws of Algebra of Sets

Idempotent Laws:
• A ∪ A = A
• A ∩ A = A

Commutative Laws:
• A ∪ B = B ∪ A
• A ∩ B = B ∩ A

Associative Laws:
• (A ∪ B) ∪ C = A ∪ (B ∪ C)
• (A ∩ B) ∩ C = A ∩ (B ∩ C)

Distributive Laws:
• A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
• A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

De Morgan’s Laws:
• (A ∪ B)’ = A’ ∩ B’
• (A ∩ B)’ = A’ ∪ B’
• A − (B ∪ C) = (A − B) ∩ (A − C)
• A − (B ∩ C) = (A − B) ∪ (A − C)

5. Identity Laws & Special Properties

• A ∪ ∅ = A  |  A ∩ ∅ = ∅
• A ∪ U = U  |  A ∩ U = A
• A ∪ A’ = U  |  A ∩ A’ = ∅
• (A’)’ = A (Involution)
• U’ = ∅ and ∅’ = U
• A − B = A ∩ B’
• A − B = A ⇔ A ∩ B = ∅
• A ∪ (A ∩ B) = A (Absorption)
• A ∩ (A ∪ B) = A (Absorption)

6. Cardinal Number / Counting Principle

• n(A ∪ B) = n(A) + n(B) − n(A ∩ B)
• n(A ∪ B) = n(A) + n(B)  (if A and B are disjoint)
• n(A − B) = n(A) − n(A ∩ B)
• n(B − A) = n(B) − n(A ∩ B)
• n(A Δ B) = n(A) + n(B) − 2n(A ∩ B)
• n(A’) = n(U) − n(A)

Three Sets (Inclusion-Exclusion Principle):
• n(A ∪ B ∪ C) = n(A) + n(B) + n(C) − n(A ∩ B) − n(B ∩ C) − n(C ∩ A) + n(A ∩ B ∩ C)
• n(Exactly one of A,B,C) = n(A) + n(B) + n(C) − 2[n(A∩B) + n(B∩C) + n(C∩A)] + 3n(A∩B∩C)
• n(Exactly two of A,B,C) = n(A∩B) + n(B∩C) + n(C∩A) − 3n(A∩B∩C)
• n(At least two of A,B,C) = n(A∩B) + n(B∩C) + n(C∩A) − 2n(A∩B∩C)

7. Power Set & Number of Subsets

• Total number of subsets of a set A with n elements: 2ⁿ
• Number of proper subsets: 2ⁿ − 1
• Number of non-empty subsets: 2ⁿ − 1
• Number of subsets with exactly r elements: ⁿC_r
• Sum of binomial coefficients: ⁿC₀ + ⁿC₁ + … + ⁿC_n = 2ⁿ
• Number of elements in power set: n(P(A)) = 2^n(A)

8. Intervals on Real Line (Subsets of R)

• Closed interval: [a, b] = { x ∈ R : a ≤ x ≤ b }
• Open interval: (a, b) = { x ∈ R : a < x < b }
• Semi-open / semi-closed: [a, b) = { x ∈ R : a ≤ x < b }
• Semi-open: (a, b] = { x ∈ R : a < x ≤ b }
• Rays: (−∞, a], (−∞, a), [a, ∞), (a, ∞)
• Entire real line: (−∞, ∞) = R

9. Important Set Relations & Venn Formulas

• A − (B ∪ C) = (A − B) ∩ (A − C)
• A − (B ∩ C) = (A − B) ∪ (A − C)
• A ∩ (B − C) = (A ∩ B) − (A ∩ C)
• (A ∪ B) ∩ (A ∪ B’) = A
• (A ∩ B) ∪ (A ∩ B’) = A
• A × (B ∪ C) = (A × B) ∪ (A × C)
• A × (B ∩ C) = (A × B) ∩ (A × C)
• n(A × B) = n(A) · n(B)

10. Multiset & Advanced Counting (Extra)

• Number of elements in exactly k sets (for n sets): inclusion-exclusion generalized.
• For two sets: n(A’ ∩ B’) = n((A ∪ B)’) = n(U) − n(A ∪ B)
• For two sets: n(A’ ∪ B’) = n((A ∩ B)’) = n(U) − n(A ∩ B)
• If A ⊆ B, then n(A) ≤ n(B), A ∪ B = B, A ∩ B = A
• If A ⊆ B, then B’ ⊆ A’
• Cardinality of Cartesian product: n(A₁ × A₂ × … × Aₖ) = n(A₁) · n(A₂) · … · n(Aₖ)