Discrete Math 1: Set Theory
Cheat Sheet

1. Definitions
// Set A contains elements 1,2 and 3
A = {1,2,3}// 2 is an element of A
2∈A// 4 is not an element of A
4∉A
2. Number Sets
Naturals N = {1,2,3,4,...}
Integers Z = {...,-2,-1,0,1,2,...}
Rationals Q = Ratio of 2 integers. example: 1/2
Irrationals Q′= Can't be represented as ratios of integers
Real R = Q and Q′
Imaginary I = Everything not in the reals. Ex: (√x = -1)
Complex C = Reals and imaginaries
3. Set Equality
The order and repetition of elements does not matter
A = {1,2,3}
B = {2,3,2,2,3,1,2,3,2,1,1,2,3,2,2,3,1,1,3,2,1}A = B
4. Set Builder Notation
A = {1,2,3,4,5,6,7,8,9}// B is equal to all elements of A (x∈A), such that (|),
// the elements are less than 5 (x<5)
B = { x∈A | x<5 }B = {1,2,3,4}
5. Types of Sets
Universal U
Empty {} or ϕ
Finite
Infinite
Subset
6. Cardinality
The number of distinct elements in a set.
n(A) or |A|
7. Equivalence
Sets are equivalent when their cardinality is the same. NOT to be mistaken with equality.
A = {1,2,3,4}
B = {5,6,7,8}// A and B are equivalent
A~B
8. Subsets
Subsets: ⊆
Proper subsets: ⊂
A = {1,2,3,4}
B = {2,3}// A is a subset of A, but not a PROPER subset of A
// ⊆
A⊆A// B is a proper subset of AB⊂A
9. Power Sets
A power set P(A) is the set of all of the subsets of A.
A = {1,2,3}
P(A) = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
10. Ordered n_tuples / Ordered Pairs
Denoted by round brackets ( ). Unlike sets, the order matters
(a,b,c) != (c,b,a)
// but
{a,b,c} = {c,b,a}
11. Cartesian Products
The cross product between two sets.
AxB = {(a,b} | a∈A and b∈B}// So if...A = {1,2,3} and B = {x,y,z}AxB = {(1,x),(1,y),(1,z),(2,x),(2,y),(2,z),(3,x),(3,y),(3,z)}
11.a. Cardinality of Cartesian Products
The cardinality of A multiplied by the cardinality of B
n(AxB) = n(A) * n(B)// In our case...n(AxB) = 9
11.b. Cartesian Plane
Think of it as a 2D graph. (2,1)
is not the same position as (1,2)
.
| x y z
--------------------
1| (1,x) (1,y) (1,z)
2| (2,x) (2,y) (2,z)
3| (3,x) (3,y) (3,z)
RxR is the cartesian product of all the real numbers. In other words, every single real number point on an (x,y) graph.
12. Operations
How sets interact with each other.
12.a. Union (∪)
A∪B = {x | x∈A or x∈B}// So if...A = {1,2,3} and B = {4,5,6}
A∪B = {1,2,3,4,5,6}
12.b. Intersection (∩)
A∩B = {x | x∈A and x∈B}// So if...A = {1,2,3} and B = {3,4,5}
A∩B = {3}// Another example. If...A = {x∈R | -2<x≤0}
B = {x∈R | 0<x<6}A∪B = {x∈R | -2<x<6}
A∩B = ϕ
13. Identities 1
Rules that are always true and can help shortcut.
1. Commutative
A∪B = B∪A2. Associative
(A∪B)∪C = A∪(B∪C)3. Distributive
A∪(B∩C) = (A∪B)∩(A∪C)4. Empty
A∪ϕ = A
A∩ϕ = ϕ5. Universal
A∪U = U
A∩U = A6. Subset
A∪A = A
A∩A = A
14. Operations 2
14.a. Compliment (c)
Everything in the universe that isn’t in A
A = {x∈R | -2<x<0}
Ac = {x∈R | x≤-2 and 0≤x}
14.b. Difference (-)
A-B is everything in A that is NOT in B
A-B = {x | x∈A and x∉B}// So if...A = {1,2,3,4} and B = {3,4,5}
A-B = {1,2}
15. Identities 2
1. A∪Ac = U
2. (Ac)c = A
3. Uc = ϕ
4. ϕc = U
5. A-B = A∩Bc
16. De Morgans Law
(A∪B)c = Ac ∩ Bc// And the opposite is true...(A∩B)c = Ac ∪ Bc
17. Partitions
17.a. Disjoint
Sets are disjoint when neither have any of the same elements.
// Disjoint
A∩B = ϕ
Mutually Disjoint is where many sets all have no elements in common with each other.
17.b. Partition Definition
A collection of non-empty sets is a partition if and only if:
- A is the union of all the sets
- The sets are mutually disjoint

// Example 1
A = {1,2,3,4,5,6}
A₁ = {1,2}
A₂ = {3,4,5}
A₃ = {6}{A₁,A₂,A₃} is a partition of A because
{{1,2},{3,4,5},{6}}
Rule 1 and 2 are satisfied// Example 2
i = {1,2,3} and Aᵢ = {i,i²} and A= {1,2,3,4,9}Is Aᵢ a partition of A?
Aᵢ = {{1},{2,4},{3,9}}
YES!