Set Theory

Set: unordered collection of distinct elements

Notation:
  A = {1, 2, 3}              Roster/enumeration
  B = {x | x > 0, x in Z}    Set-builder notation
  ∅ or {}                     Empty set

Membership:
  3 ∈ A       "3 is an element of A"
  5 ∉ A       "5 is not an element of A"

Important sets:
  N = {0, 1, 2, 3, ...}      Natural numbers
  Z = {..., -2, -1, 0, 1, 2, ...}   Integers
  Q = {p/q | p, q in Z, q != 0}     Rationals
  R                           Real numbers
  C                           Complex numbers
  N ⊂ Z ⊂ Q ⊂ R ⊂ C        Containment chain

A ⊆ B      "A is a subset of B" (every element of A is in B)
A ⊂ B      "A is a proper subset of B" (A ⊆ B and A ≠ B)
A = B      iff A ⊆ B and B ⊆ A

For any set A:
  ∅ ⊆ A               Empty set is subset of everything
  A ⊆ A               Every set is a subset of itself
  |P(A)| = 2^|A|      Power set has 2^n elements

Power set P(A) = set of all subsets:
  P({1,2}) = {∅, {1}, {2}, {1,2}}

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}    (also A - B)
Complement:      A' = U \ A = {x ∈ U | x ∉ A}     (relative to universe U)
Symmetric diff:  A △ B = (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B)
Cartesian prod:  A × B = {(a,b) | a ∈ A, b ∈ B}

Example:
  A = {1, 2, 3},  B = {2, 3, 4}
  A ∪ B = {1, 2, 3, 4}
  A ∩ B = {2, 3}
  A \ B = {1}
  A △ B = {1, 4}
  A × B = {(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}

Commutative:   A ∪ B = B ∪ A           A ∩ B = B ∩ A
Associative:   (A∪B)∪C = A∪(B∪C)       (A∩B)∩C = A∩(B∩C)
Distributive:  A∩(B∪C) = (A∩B)∪(A∩C)   A∪(B∩C) = (A∪B)∩(A∪C)
De Morgan's:   (A∪B)' = A'∩B'           (A∩B)' = A'∪B'
Identity:      A ∪ ∅ = A               A ∩ U = A
Complement:    A ∪ A' = U              A ∩ A' = ∅

|A|               Number of elements in A

Inclusion-exclusion:
  |A ∪ B| = |A| + |B| - |A ∩ B|

  Three sets:
  |A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

Cartesian product:
  |A × B| = |A| * |B|

Power set:
  |P(A)| = 2^|A|

Countably infinite:    can be put in 1-1 correspondence with N
  N, Z, Q are all countably infinite (same "size")

Uncountably infinite:  strictly larger than N
  R is uncountable (Cantor's diagonal argument)
  |R| = |P(N)| = 2^|N|
  No bijection N → R exists

Relation R from A to B: a subset of A × B
  R ⊆ A × B
  (a, b) ∈ R means "a is related to b", written aRb

Function: a relation where each a ∈ A maps to exactly one b ∈ B
  (special case of relation)

Reflexive:     aRa for all a ∈ A         (every element relates to itself)
Symmetric:     aRb implies bRa           (if a~b then b~a)
Antisymmetric: aRb and bRa implies a=b   (no mutual pairs except self)
Transitive:    aRb and bRc implies aRc   (chains work)

Equivalence relation: reflexive + symmetric + transitive
  Partitions the set into equivalence classes
  Example: congruence mod n

Partial order: reflexive + antisymmetric + transitive
  Example: ⊆ on sets, ≤ on numbers, divisibility on integers

# Unix tools operate on sets of lines

# Union (sorted)
sort -u file1 file2

# Intersection
comm -12 <(sort file1) <(sort file2)

# Difference (in file1 but not file2)
comm -23 <(sort file1) <(sort file2)

# Symmetric difference
comm -3 <(sort file1) <(sort file2) | tr -d '\t'

# Cartesian product (all pairs)
awk 'NR==FNR{a[NR]=$0;n=NR;next} {for(i=1;i<=n;i++) print a[i],$0}' f1 f2