Cheatography

# Discrete Math Cheat Sheet by AviMathPerson

Notes from a course I took in discrete math coving a variety of topics including set theory, relations, cardinality, etc.

### Important relations

 Reflexive: Shorthand: Ia ⊆ R Meaning: Every element is related to itself. for all a ∈ A, aRa holds ( R ⊆ {(a, a) | a ∈ A} ) Transi­tive: Shorthand: ( R ∘ R = R2 ⊆ R ) Meaning: If ( (a, b) ∈ R ) and ( (b, c) ∈ R ), then ( (a, c) ∈ R ). (aRb and bRc) -> aRc Symmetric: Shorthand: ( R = R⁻¹ ) Meaning: If ( (a, b) ∈ R ), then ( (b, a) ∈ R ). When aRb <=> bRa Antisy­mme­tric: Shorthand: ( R ∩ R⁻¹ ⊆ {(a, a) | a ∈ A} ) Meaning: If ( (a, b) ∈ R ) and ( (b, a) ∈ R ), then ( a = b ). (aRb and bRa) -> (a = b) - This does not mean not-sy­mmetric
Equiva­lence relation is one where Reflex­ivity, Transi­tivity, and Symmetry all hold

### Cardin­ality

 Cardin­ality Classi­fic­ation Examples Aleph 0 Countably infinite ℕ ℕ x ℕ ℕ x ℕ x ℕ ℤ ℚ ℚ x ℚ Aleph Uncoun­tably infinite (0,1) {0,1}^ℕ P(ℕ) ℝ ℝ x ℝ ℂ Finite Countably finite if A = {1}, |A| = 1 {3,4,5} {1,2,....1­000}

### Combin­atorics

 Case: Order matters Order doesn't matter With repetition n^k (case 1) nCk (case 3) Without repetition nPk (case 2) (k+n-1­)C(k) (case 4)

### Functions

 Let f,g be two functions, (f:A -> B) , (g:B -> A) Function f Horizontal line test Classi­fic­ation Invert­ibility G is - inverse of f Definition English Onto Hits at least 1 point Surjective Right invertible f ∘ g = Ib {f(a) | a ∈ A} = B every element in range (B) has a source function that maps one or more elements of A to the same element of B One to One Hits at most 1 point Injective Left Invertible g ∘ f = Ia if a1 != a2 then f(a1) != f(a2) or contra­pos­itive if f(a1) = f(a2) then a1 = a2 function that always maps the distinct element of its domain to the distinct element of its codomain Onto and One to One Hits exactly at 1 point Bijective Invertible g ∘ f = Ia, f ∘ g = Ib f⁻¹ = g function that is both injective and surjective Identity Ia Hits exactly at 1 point Bijective Invertible f ∘ Ia = f = Ib ∘ f f(a) = a function that always returns the value that was used as its argument, unchanged
(g ∘ f)(a) = g(f(a)) means g composed with f

### Set Theory

 A ∪ B = {x ∈ A or x ∈ B or both} A ∩ B = {x ∈ A and x ∈ B} A ⊕ B = (A - B) ∪ (B - A) = (A ∪ B) - (A ∩ B) A - B = A ∩ Bᶜ = {x ∈ A and x ∉ B} Demorgan’s laws: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ Associ­ati­vity: A ∪ (B ∪ C) = (A ∪ B) ∪ C = A ∪ B ∪ C Distri­but­ivity; A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

### Subsets

 A ⊆ A ∪ B = B ∪ A B ⊆ A ∪ B If A ⊆ B, then A ∪ B = B A ∩ B ⊆ A ⊆ A ∪ B B ∩ A ⊆ B ⊆ A ∪ B

### Cartesian product:

 A × B = { (a, b) | a ∈ A and b ∈ B } an unordered set of sets of ordered pairs where a is in A, b is in B if A = {1,2}, B = {2,3}, then A × B = {(1,2), (1,3), (2,2), (2,3)} A × B ≠ B × A (unless A = B) A ∩ (A × B) = ∅ |A × B| = |A| × |B| Distri­bution: A × (B ∪ C) = (A × B) ∪ (A × C) A × (B ∩ C) = (A × B) ∩ (A × C)

### Order relation

 Partial order If and only if all (Refle­xivity, Transi­tivity, and Anti-s­ymm­etry) hold clear hasse diagram can be drawn items for which the relation doesn’t hold will be drawn but not connected to the others in the diagram
Total/­Linear order:
Partial order holds
Totality: For any ( a, b ∈ A ), either ( (a, b) ∈ R ) or ( (b, a) ∈ R ).
In other words: For any two distinct elements a and b, either a is related to b (a ≤ b), or b is related to a (b ≤ a).
hasse diagram would be a straight line (all elements relate to one another in this set)

### Universal Set

 Universal Set = U: for any finite set A U = { x ∈ U | x ∉ A } Aᶜ = U - A (Aᶜ)ᶜ = A Uᶜ = ∅ ∅ᶜ = U

### Relations

 ARB = (a,b) ∈ R Identity: Ia = (a,a) Ex: {(1,1)­,(2­,2)­,(3,3), … } Relation on set itself: R ⊆ A × A ARA is another way to write it too. Empty relation when R = ∅ implies that the relation R is empty, meaning it does not hold between any two pairs. It’s essent­ially a relation with no elements. Complete relation when R = A × B implies that the relation R contains all possible pairs that can be formed by taking one element from set A and one element from set B. It’s a relation where every element of A is related to every element of B. Inverse relation is R⁻¹ = { (b, a) | (a, b) ∈ R } R consists of all pairs in R but with their elements reversed. If (a,b) is in R, then (b,a) is in R⁻¹ Compos­ition of relations: R ∘ S = { (a, c) | ∃ b : (a, b) ∈ R and (b, c) ∈ S } Set of pairs (a,c) such that exists an element b for which both (a,b) is in R and (b,c) is in S R ∘ R = R2 is a relation composed with itself (R ∘ S) ∘ T = R ∘ (S ∘ T) i.e it is associ­ative (but not commun­itive) Ia ∘ R = R

### Order relation terms

 Minimal An element a is minimal if there is no b such that b precedes a. Elements with nothing less than them (no predec­essors) Minimum An element a is a minimum if for all b, a precedes b Element that is less than everything else (either a set has 1 minimum or no minimum element) Maximal An element a is maximal if there is no b such that a precedes b follows from minimal (with greater than) Maximum An element a is a maximum if for all b, b precedes a follows from minimum (with greater than)

### Power sets

 The power set of A is denoted as P(A) or 2A A ∈ P(A), ∅ ∈ P(A) If |A| = n, then |P(A)| = 2n |P(A)| = 2|A| If A = ∅, then P(A) = {∅} If A = {1,2}, then P(A) = {∅, {1}, {2}, {1, 2}} |A| < |P(A)|

### Power set proofs

 P(A) ∩ P(B) = P(A ∩ B) Forward Inclusion: Let 𝑋 be an arbitrary element in 𝑃(𝐴) ∩ 𝑃(𝐵). By definition of inters­ection, 𝑋 belongs to both 𝑃(𝐴) and 𝑃(𝐵). This implies 𝑋 is a subset of both 𝐴 and 𝐵. Conseq­uently, 𝑋 is also a subset of their inters­ection, 𝐴 ∩ 𝐵. Thus, 𝑋 is an element of 𝑃(𝐴 ∩ 𝐵). Therefore, 𝑃(𝐴) ∩ 𝑃(𝐵) ⊆ 𝑃(𝐴 ∩ 𝐵). Reverse Inclusion: Let 𝑌 be an arbitrary element in 𝑃(𝐴 ∩ 𝐵). By defini­tion, 𝑌 is a subset of 𝐴 ∩ 𝐵, hence a subset of both 𝐴 and 𝐵. Conseq­uently, 𝑌 belongs to both 𝑃(𝐴) and 𝑃(𝐵). Thus, 𝑌 is an element of 𝑃(𝐴) ∩ 𝑃(𝐵). Therefore, 𝑃(𝐴 ∩ 𝐵) ⊆ 𝑃(𝐴) ∩ 𝑃(𝐵). Conclu­sion: Combining both directions of inclusion, we’ve demons­trated that 𝑃(𝐴) ∩ 𝑃(𝐵) ⊆ 𝑃(𝐴 ∩ 𝐵) and 𝑃(𝐴 ∩ 𝐵) ⊆ 𝑃(𝐴) ∩ 𝑃(𝐵), implying 𝑃(𝐴) ∩ 𝑃(𝐵) = 𝑃(𝐴 ∩ 𝐵). Thus, the equality holds.
P(A) ∪ P(B) ≠ P(A ∪ B)

Example of why these aren’t equal:
A = {1}, B = {2}, A ∪ B = {1,2} => P(A ∪ B) = {∅, {1}, {2}, {1,2}}

P(A) = {∅, {1}}, P(B) = {∅, {2}} => P(A) ∪ P(B) = {∅, {1}, {2}}

### More combin­atorics

 number of ways to place k balls in n boxes. P = permut­ation C = combin­ation Order matters = sequence of choices Order doesn’t matter = if we picked ball 1 then ball 2… it would be equivalent to picking ball 2 then ball 1 With replac­ement = same item can be picked several times Without replac­ement= each item is chosen at most, 1 time Case 1 K times out of n objects Number of functions from A to B |A| = K, |B| = n if A has 3 elements, and B has 5… we would get 5^3 total functions that can be defined Case 2 K unique balls in n small boxes (can only fit 1 item in each box) number of one to one functions from A to B Case 3 K identical balls in n small boxes Binomial coeffi­cients Case 4 Bars and stars K identical balls in n numbered boxes (but each box can hold >= 0 balls)