# 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 = { 1, 2, 3, … }

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

Z = integers

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

R = real 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.
• 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 }
```