The complete study guide — set theory, logic and proofs, number theory, combinatorics, graph theory, recurrence relations, Boolean algebra, relations, and the mathematics of infinite sets.
A set is an unordered collection of distinct objects called elements. Sets are the foundation of all modern mathematics. We write a ∈ A to mean “a is an element of A” and a ∉ A to mean “a is not an element of A.”
| Operation | Notation | Definition | Example (A=(1,2,3), B=(2,3,4)) |
|---|---|---|---|
| Union | A ∪ B | Elements in A or B or both | (1,2,3,4) |
| Intersection | A ∩ B | Elements in both A and B | (2,3) |
| Difference | A − B | Elements in A but not B | (1) |
| Complement | A′ or A̅ | Elements in U but not A | U − A |
| Symmetric Diff. | A ⊕ B | In A or B, but not both | (1,4) |
The power set P(A) is the set of all subsets of A, including ∅ and A itself. If |A| = n, then |P(A)| = 2^n.
// Example: A = (a, b, c), |A| = 3, |P(A)| = 8
P(A) = (
∅,
(a), (b), (c),
(a,b), (a,c), (b,c),
(a,b,c)
)
The Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B. If |A| = m and |B| = n, then |A × B| = mn.
// A = (1, 2), B = (x, y)
A × B = ( (1,x), (1,y), (2,x), (2,y) )
Venn diagrams visualize set relationships with overlapping circles inside a rectangle (the universal set). Key algebraic laws:
Commutative Laws
A ∪ B = B ∪ A
A ∩ B = B ∩ A
Associative Laws
(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)
Distributive Laws
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
De Morgan's Laws
(A ∪ B)′ = A′ ∩ B′
(A ∩ B)′ = A′ ∪ B′
A proposition is a declarative statement that is either true (T) or false (F). Propositions are combined using logical connectives.
| Connective | Symbol | Read as | True when |
|---|---|---|---|
| Negation | ¬p | not p | p is false |
| Conjunction | p ∧ q | p and q | both p and q are true |
| Disjunction | p ∨ q | p or q | at least one of p, q is true |
| Implication | p → q | if p then q | p is false, or q is true |
| Biconditional | p ↔ q | p if and only if q | p and q have the same truth value |
A predicate P(x) is a statement containing a variable x that becomes a proposition when x is assigned a specific value.
Assume the hypothesis P is true and derive the conclusion Q using definitions, axioms, and previously proven theorems.
Example: Prove that if n is even, then n² is even. Let n = 2k for some integer k. Then n² = (2k)² = 4k² = 2(2k²), which is even. ■
To prove P → Q, instead prove ¬Q → ¬P (the contrapositive). Both are logically equivalent.
Example: Prove that if n² is even, then n is even. Contrapositive: if n is odd, then n² is odd. Let n = 2k + 1. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. ■
Assume the negation ¬P is true and derive a logical contradiction. This proves P must be true.
Example: Prove √2 is irrational. Assume √2 = p/q in lowest terms. Then 2q² = p², so p is even; write p = 2m. Then 2q² = 4m², so q² = 2m², making q even too — contradicting that p/q is in lowest terms. ■
Three steps:
Example: Prove 1 + 2 + … + n = n(n+1)/2. Base: 1 = 1(2)/2 ✓. Inductive step: assume sum = k(k+1)/2; adding (k+1) gives k(k+1)/2 + (k+1) = (k+1)(k+2)/2. ■
In the inductive step, assume P(1), P(2), …, P(k) are all true (not just P(k)), then prove P(k+1). Useful for problems where the k+1 case depends on earlier cases other than just k. Example: proving every integer ≥ 2 has a prime factorization.
We say a divides b (written a | b) if there exists an integer k such that b = ak. Equivalently, b mod a = 0.
Division Algorithm
For any integers a and d with d > 0, there exist unique integers q (quotient) and r (remainder) such that a = dq + r where 0 ≤ r < d.
The greatest common divisor GCD(a, b) is the largest integer that divides both a and b. The least common multiple LCM(a, b) is the smallest positive integer divisible by both. Key identity: GCD(a,b) × LCM(a,b) = a × b.
// Euclidean Algorithm (iterative)
function gcd(a, b):
while b != 0:
r = a mod b
a = b
b = r
return a
// Example: gcd(252, 105)
252 = 2*105 + 42
105 = 2*42 + 21
42 = 2*21 + 0 → GCD = 21
The Extended Euclidean Algorithm also finds integers x and y such that ax + by = GCD(a, b) (Bezout's identity), which is essential for computing modular inverses.
We write a ≡ b (mod n) if n | (a − b). This is a congruence relation. Modular arithmetic supports addition, subtraction, and multiplication. Division requires a modular inverse: a¹ mod n exists if and only if GCD(a, n) = 1.
| Property | Rule |
|---|---|
| Addition | (a + b) mod n = ((a mod n) + (b mod n)) mod n |
| Multiplication | (a * b) mod n = ((a mod n) * (b mod n)) mod n |
| Fermat's Little Theorem | a^p ≡ a (mod p) for prime p |
The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be written uniquely as a product of primes (up to ordering). Example: 360 = 2³ × 3² × 5.
To find GCD and LCM from prime factorizations: take the minimum exponent for each prime to get GCD, and the maximum exponent for each prime to get LCM.
If n₁, n₂, …, nₖ are pairwise coprime, the system x ≡ a₁ (mod n₁), …, x ≡ aₖ (mod nₖ) has a unique solution modulo N = n₁ × n₂ × … × nₖ.
// CRT Construction
N = n1 * n2 * ... * nk
For each i: Ni = N / ni
Find yi such that Ni * yi ≡ 1 (mod ni)
Solution: x = (a1*N1*y1 + a2*N2*y2 + ...) mod N
Permutations P(n, r)
P(n,r) = n! / (n-r)!
Ordered selection of r items from n distinct items.
P(5,3) = 5!/2! = 60
Combinations C(n, r)
C(n,r) = n! / (r!(n-r)!)
Unordered selection of r items from n distinct items.
C(5,3) = 120/12 = 10
Pascal's triangle encodes all binomial coefficients. Row n, position k gives C(n, k). Each entry equals the sum of the two entries above it: C(n, k) = C(n-1, k-1) + C(n-1, k).
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Binomial Theorem: (x + y)^n = ∑ₖ₌₀ⁿ C(n,k) x^k y^(n-k). The sum of all entries in row n is 2^n.
For counting elements in the union of sets, avoid double-counting with:
|A ∪ B| = |A| + |B| - |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C|
- |A ∩ B| - |A ∩ C| - |B ∩ C|
+ |A ∩ B ∩ C|
Example: How many integers from 1 to 100 are divisible by 2 or 3? |A| = 50, |B| = 33, |A ∩ B| = 16. Answer: 50 + 33 - 16 = 67.
If more than n objects are placed into n categories, at least one category contains two or more objects.
Classic Applications
Generalized form: if kn + 1 objects fill n boxes, some box holds k + 1 or more objects.
A graph G = (V, E) consists of a set of vertices V and a set of edges E connecting pairs of vertices.
| Term | Definition |
|---|---|
| Degree deg(v) | Number of edges incident to vertex v |
| Path | Sequence of vertices connected by edges, no repeated vertices |
| Cycle | A path that starts and ends at the same vertex |
| Connected graph | A path exists between every pair of vertices |
| Complete graph Kₙ | Every pair of vertices is connected; has n(n-1)/2 edges |
| Bipartite graph | Vertices split into two sets; edges only between sets |
Handshaking Lemma: For any graph, ∑ deg(v) = 2|E|. Every graph has an even number of odd-degree vertices.
Eulerian Path / Circuit
Traverses every edge exactly once.
Hamiltonian Path / Cycle
Visits every vertex exactly once.
A proper coloring assigns a color to each vertex so no two adjacent vertices share a color. The minimum number of colors needed is the chromatic number χ(G).
A graph is planar if it can be drawn in the plane without edge crossings.
Euler's Formula for Planar Graphs
V - E + F = 2
V = vertices, E = edges, F = faces (including the unbounded outer face)
Consequence: for simple connected planar graphs with V ≥ 3: E ≤ 3V - 6.
K₅ and K₃,₃ are the minimal non-planar graphs (Kuratowski's theorem).
A tree is a connected acyclic graph. Key facts: a tree on n vertices has exactly n - 1 edges; there is a unique path between any two vertices.
A spanning tree of a connected graph G is a subgraph that is a tree containing all vertices of G. Every connected graph has at least one spanning tree.
Kruskal's Algorithm (Min Spanning Tree)
Time: O(E log E)
Prim's Algorithm (Min Spanning Tree)
Time: O(E log V) with priority queue
// Dijkstra's Algorithm (non-negative weights)
Initialize dist[source] = 0, all others = infinity
Priority queue Q with all vertices
while Q not empty:
u = vertex in Q with minimum dist
for each neighbor v of u:
alt = dist[u] + weight(u, v)
if alt < dist[v]: dist[v] = alt
// Time: O((V + E) log V) with a min-heap
Bellman-Ford handles negative edge weights in O(VE). Floyd-Warshall finds all-pairs shortest paths in O(V³).
A recurrence relation defines each term of a sequence in terms of earlier terms. Paired with initial conditions, it uniquely determines the sequence.
Form: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + … + cₖaₙ₋ₖ. The characteristic equation is:
r^k - c1*r^(k-1) - c2*r^(k-2) - ... - ck = 0
If this has k distinct roots r₁, r₂, …, rₖ, the general solution is aₙ = α₁r₁^n + α₂r₂^n + … + αₖrₖ^n. Use initial conditions to determine the constants αᵢ.
F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1
Characteristic equation: r² - r - 1 = 0
Roots: r = (1 + √5)/2 = φ (golden ratio) and r = (1 - √5)/2
F(n) = (1/√5) * (φ^n - ψ^n) (Binet's formula)
Solves divide-and-conquer recurrences T(n) = aT(n/b) + f(n) where a ≥ 1, b > 1. Let p = logₕ(a).
| Case | Condition | Solution | Example |
|---|---|---|---|
| 1 | f(n) = O(n^(p-e)) | T(n) = Θ(n^p) | T(n) = 8T(n/2) + n |
| 2 | f(n) = Θ(n^p) | T(n) = Θ(n^p log n) | T(n) = 2T(n/2) + n (merge sort) |
| 3 | f(n) = Ω(n^(p+e)) | T(n) = Θ(f(n)) | T(n) = 2T(n/2) + n² |
The ordinary generating function (OGF) for a sequence a₀, a₁, a₂, … is the formal power series:
G(x) = a0 + a1*x + a2*x^2 + ... = ∑ a_n * x^n
Generating functions turn sequence problems into algebraic ones. Operations on sequences correspond to operations on functions:
| Sequence | Generating Function |
|---|---|
| 1, 1, 1, 1, ... | 1 / (1 - x) |
| 1, r, r^2, r^3, ... | 1 / (1 - rx) |
| C(n,0), C(n,1), ..., C(n,n) | (1 + x)^n |
| Fibonacci: 0,1,1,2,3,5,... | x / (1 - x - x^2) |
Exponential generating functions (EGF) use the form ∑ aₙ x^n / n! and are especially useful for counting labeled structures (permutations, labeled trees). The EGF for e^x is 1, 1, 1, 1, … because n!/n! = 1.
Boolean algebra operates on values in (0, 1) with operations AND (·), OR (+), and NOT (overbar). It provides the mathematical foundation for digital circuits.
| Gate | Symbol | Output | Note |
|---|---|---|---|
| AND | A · B | 1 only when both inputs are 1 | Multiplication in Boolean algebra |
| OR | A + B | 1 when at least one input is 1 | Addition in Boolean algebra |
| NOT | A̅ | Inverts the input | Complement |
| NAND | (A · B)̅ | 0 only when both inputs are 1 | Functionally complete alone |
| NOR | (A + B)̅ | 1 only when both inputs are 0 | Functionally complete alone |
| XOR | A ⊕ B | 1 when inputs differ | Used in adders, parity checks |
Identity and Null Laws
A + 0 = A, A · 1 = A
A + 1 = 1, A · 0 = 0
Idempotent and Complement
A + A = A, A · A = A
A + A̅ = 1, A · A̅ = 0
De Morgan's Laws
(A + B)̅ = A̅ · B̅
(A · B)̅ = A̅ + B̅
Absorption
A + (A · B) = A
A · (A + B) = A
A Karnaugh map (K-map) is a grid-based method for simplifying Boolean expressions by visually grouping 1s in powers of 2.
// 3-variable K-map layout (AB \\ C)
C=0 C=1
AB=00 | m0 | m1 |
AB=01 | m2 | m3 |
AB=11 | m6 | m7 |
AB=10 | m4 | m5 |
// Group adjacent 1s and read off the simplified expression
A binary relation R on a set A is a subset of A × A. We write aRb to mean (a, b) ∈ R.
| Property | Definition | Example |
|---|---|---|
| Reflexive | aRa for all a ∈ A | ≤ on integers |
| Symmetric | aRb implies bRa | Equality, friendship |
| Antisymmetric | aRb and bRa imply a = b | ≤ on integers, subset ⊆ |
| Transitive | aRb and bRc imply aRc | < on integers, ancestor |
| Total | aRb or bRa for all a, b | ≤ on integers |
A relation is an equivalence relation if it is reflexive, symmetric, and transitive. Equivalence relations partition the set A into disjoint equivalence classes [a] = (x ∈ A | xRa).
Example: Congruence mod n
a ≡ b (mod 4) partitions Z into 4 classes:
[0] = (..., -8, -4, 0, 4, 8, ...)
[1] = (..., -7, -3, 1, 5, 9, ...)
[2] = (..., -6, -2, 2, 6, 10, ...)
[3] = (..., -5, -1, 3, 7, 11, ...)
A partial order is a relation that is reflexive, antisymmetric, and transitive. A set with a partial order is a partially ordered set (poset).
A Hasse diagram represents a poset by drawing elements as points and edges only for covering relations (a covers b if a > b and no element c satisfies a > c > b). Edges point upward.
Dilworth's theorem: in any finite poset, the minimum number of chains needed to cover all elements equals the maximum size of an antichain.
A function f : A → B assigns to each element of A exactly one element of B. A is the domain and B is the codomain.
Injective (One-to-One)
Different inputs produce different outputs: f(a) = f(b) implies a = b.
|A| ≤ |B| is necessary.
Surjective (Onto)
Every element of B is the output of some element of A: range = codomain.
|A| ≥ |B| is necessary.
Bijective
Both injective and surjective. A bijection establishes a one-to-one correspondence between A and B.
|A| = |B|.
Two sets have the same cardinality if there exists a bijection between them — even if both are infinite.
The Hierarchy of Infinities
Countably infinite (ℵ₀): a set that can be put in bijection with the natural numbers N. Examples: integers Z, rationals Q, algebraic numbers, finite strings. Countable unions of countable sets are countable.
Uncountably infinite (c = 2^ℵ₀): a set that is infinite but has no bijection with N. Examples: real numbers R, complex numbers, continuous functions, power set of N.
Cantor proved [0, 1] is uncountable by contradiction: suppose we list all real numbers in [0, 1] as r₁, r₂, … in decimal. Construct a new number d by letting the n-th decimal digit of d differ from the n-th digit of rₙ. Then d is in [0, 1] but differs from every rₙ in the list — contradiction.
For any set A, the cardinality of P(A) (its power set) is strictly greater than that of A: |P(A)| > |A|. This holds for both finite and infinite sets.
Proof sketch: Suppose a surjection f : A → P(A) exists. Define D = (a ∈ A | a ∉ f(a)). Then D ∈ P(A), so D = f(x) for some x ∈ A. Is x ∈ D? If yes, then x ∉ f(x) = D — contradiction. If no, then x ∈ f(x) = D — contradiction. So no such surjection exists.
This gives an infinite tower: |N| < |P(N)| < |P(P(N))| < …, proving there are infinitely many distinct sizes of infinity.
If there exist injections f : A → B and g : B → A, then there exists a bijection h : A → B (so |A| = |B|). This theorem lets us prove two sets have the same cardinality without explicitly constructing a bijection — just find injections in both directions.
A permutation is an ordered arrangement — order matters. A combination is an unordered selection — order doesn't matter. Use P(n,r) = n! / (n-r)! when arrangement matters (ranking, PIN codes), and C(n,r) = n! / (r!(n-r)!) when it doesn't (committees, subsets). C(5,3) = 10, while P(5,3) = 60 — the same elements but six times as many ordered arrangements.
Mathematical induction proves a statement P(n) holds for all natural numbers n ≥ n₀. Step 1 (base case): verify P(n₀) directly. Step 2 (inductive step): assume P(k) is true, then prove P(k+1). It's the standard tool for sum formulas, divisibility claims, recursive algorithms, and inequalities involving n. Strong induction allows you to assume P(1), …, P(k) all hold when proving P(k+1).
An Eulerian path traverses every edge exactly once. An Eulerian circuit exists iff every vertex has even degree; an Eulerian path (non-circuit) exists iff exactly two vertices have odd degree. A Hamiltonian path visits every vertex exactly once — no clean characterization exists and determining Hamiltonian paths is NP-complete in general.
If more than n objects are distributed into n categories, at least one category gets two or more objects. Generalized: if kn + 1 objects fill n boxes, some box has at least k + 1 objects. Classic use cases: in a group of 13 people, two share a birth month; among any 5 integers, two share the same remainder mod 4.
An equivalence relation is reflexive, symmetric, and transitive — it partitions a set into equivalence classes (example: congruence mod n). A partial order is reflexive, antisymmetric, and transitive — it ranks elements, though not every pair need be comparable (example: divisibility on positive integers). A total order adds the requirement that every pair is comparable.
Cantor's theorem says the power set P(A) always has strictly greater cardinality than A, even for infinite A. This means there is no largest infinity — there are infinitely many sizes of infinite sets. The natural numbers are countably infinite; the reals are uncountably infinite; P(R) is a still-larger infinity, and so on without end.
The Master Theorem solves T(n) = aT(n/b) + f(n). Compute p = logₕ(a) and compare f(n) to n^p. Case 1: f(n) grows slower — T(n) = Θ(n^p). Case 2: f(n) grows at the same rate — T(n) = Θ(n^p log n). Case 3: f(n) grows faster — T(n) = Θ(f(n)). Merge sort gives T(n) = 2T(n/2) + n; here p = 1 and f(n) = n, so Case 2 applies: T(n) = Θ(n log n).
Combinatorics
Counting, arrangements, and probability foundations
Graph Theory
Networks, paths, coloring, and algorithms
Number Theory
Primes, divisibility, and modular arithmetic
Mathematical Logic
Formal systems, propositions, and quantifiers
Proof Techniques
Direct, contradiction, contrapositive, induction
Combinations and Permutations
Counting strategies with worked examples
Cryptography Mathematics
RSA, modular arithmetic, and prime applications
Reinforce every concept — from set proofs to graph algorithms — with adaptive practice problems and step-by-step explanations.
Start Practicing Free