5 min read

On Basic Set Theory (Cheat Sheet)

January 22, 2019

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