# 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!