Discrete Math 1: Set Theory

Cheat Sheet

Photo by Gabby K from Pexels (not actually discrete math)

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 A
B⊂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