5 min read

On Basic Set Theory (Cheat Sheet)

This is a work in progress. Its intended to be used as a quick reference.

Set Notation

∅ = empty set

  • ∅ = {}

N = natural numbers

  • N = { 1, 2, 3, … }

  • N0 = { 0, 1, 2, 3, … }

Z = integers

  • Z = { …, -1, 0, 1, … }

Q = rational numbers

R = real numbers

C = complex numbers

Set Operators

∪ = union

  • A ∪ B = { p : p ∈ A or p ∈ B }

    • The definition of A union B equals the set containing elements p such that p is an element of A or p is an element of B.

∩ = intersection

  • A ∩ B = { p : p ∈ A and p ∈ B }

    • The definition of A intersection B equals the set containing elements p such that p is an element of A and p is an element of B.

\ = complement

  • A \ B = { p : p ∈ A or p ∉ B }

    • The definition of A difference of B equals the set containing elements p such that p is an element of A or p is not an element of B.

⊕ = symmetric difference

  • xor
  • A ⊕ B = ( A \ B ) ∪ ( B \ A )

R \ Q = I

(Some) Laws of Set Theory

U = the universe

Idempotence

  • Applying a binary operator to a proposition over and over will never change the value of the original proposition.

    • A ∪ A = A
    • A ∩ A = A

Identity

  • An equality relation, A and B produce the same value as each other.

    • A ∪ ∅ = A
    • U ∪ A = U
    • A ∩ U = A
    • ∅ ∩ A = ∅

Complement

  • Ac = { x : x ∉ A }

    • A ∪ Ac = U
    • c = U
    • A ∩ Ac = ∅
    • Uc = ∅

Involution

  • If we have a proposition and apply it to the same function twice it will yield the original value.

  • A function that is its own inverse.

    • (Ac)c = A
    • f(f(x)) = x

Associativity

  • Sets can be regrouped.

    • A ∩ ( B ∩ C ) = ( A ∩ B) ∩ C
    • A ∪ ( B ∪ C ) = ( A ∪ B) ∪ C

Commutativity

  • The sets can be switched relative to the operator.

    • A ∩ B = B ∩ A
    • A ∪ B = B ∪ A

Distributive

  • A ∩ ( B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C )

    • To show equality, you must prove that each side of an equation are subsets of each other:

      • A ∩ ( B ∪ C ) ⊆ ( A ∩ B ) ∪ ( A ∩ C )
      • ( A ∩ B ) ∪ ( A ∩ C ) ⊆ A ∩ ( B ∪ C )
      Example
    
      A = { 1, x, 3 }
      B = { 3, k, z }
      C = { 1, 3 }
    
      A ∩ B = { 3 }	  <----- A set with only one element is referred
      A ∩ C = { 1, 3 }         to as a singleton or a singleton set.
      B ∪ C = { 1, 3, k, z }
      A ∩ ( B ∪ C ) = { 1, 3 }
    
      A ∩ ( B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C )
    
      { 1, 3 } = { 3 } ∪ { 1, 3}
      { 1, 3 } = { 1, 3 }
      
  • A ∪ ( B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C )

      Example
    
      A = { 1, x, 3 }
      B = { 3, k, z }
      C = { 1, 3 }
    
      A ∪ ( B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C )
    
      A ∪ B = { 1, x, 3, k, z }
      A ∪ C = { 1, x, x }
      B ∩ C = { 3 }
      A ∪ ( B ∩ C ) = { 1, x, 3 }
    
      A ∪ ( B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C )
    
      { 1, x, 3 } = { 1, x, 3, k, z } ∩ { 1, x, 3 }
      { 1, x, 3 } = { 1, x, 3 }
      

De Morgan’s Law

The complement of the union is the intersection of the complements.

  • ( A ∪ B )c ⊆ Ac ∩ Bc

    • x ∈ ( A ∪ B )c
    • x ∉ ( A ∪ B )
    • x ∉ A and x ∉ B
    • x ∈ Ac and x ∈ Bc
    • x ∈ Ac ∩ Bc
      Example:
      ( A ∪ B )c ⊆ Ac ∩ Bc
    
      A = { 1, x, 3 }
      B = { 3, k, z }
      C = { 1, 3 }
    
      U = { x ∈ Z : 0 ≤ x ≤ 5 }
    
      A ∪ B = { 1, x, 3, k, z }
      ( A ∪ B )c  = { 0, 2, 4, 5 }
      Ac ∩ Bc = { 0, 2, 4, 5 }
      

The complement of the intersection is the union of the complements.

  • ( A ∩ B )c ⊆ Ac ∪ Bc

    • x ∈ ( A ∩ B )c
    • x ∉ ( A ∩ B )
    • x ∉ A or x ∉ B
    • x ∈ Ac or x ∈ Bc
    • x ∈ Ac ∪ Bc
      Example:
      ( A ∩ B )c ⊆ Ac ∪ Bc
    
      A = { 1, x, 3 }
      B = { 3, k, z }
      C = { 1, 3 }
    
      U = { x ∈ Z : 0 ≤ x ≤ 5 }
    
      A ∩ B = { 3 }
      ( A ∩ B )c = { 0, 1, 2, 4, 5 }
      Ac ∪ Bc = { 0, 1, 2, 4, 5 }
      

References