Show Menu
Cheatography

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)
                       
 

Metadata

  • Languages:
  • Published: 27th March, 2024

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

          Discrete Math Cheat Sheet
          EECS 203 Exam 1 Cheat Sheet
          EECS 203 Exam 2 Cheat Sheet