Concepts Checklist

Discrete Mathematics Concepts Checklist

Sets

Set definition: Sets are collections of objects where repetition and order don’t matter
Set notation: Elements written in curly braces {1, 2, 3}
Special number sets: ℕ (naturals), ℤ (integers), ℚ (rationals), ℝ (reals)
Element membership: a ∈ A means “a is an element of A” [read: “a in A”]
Non-membership: a ∉ A means “a is not an element of A” [read: “a not in A”]
Empty set: ∅ or {} - the set containing no elements [read: “empty set” or “null set”]
Set-builder notation: {x | P(x)} - all x satisfying property P [read: “the set of x such that P of x”]
Subset: A ⊆ B means every element of A is also in B [read: “A is a subset of B”]
Proper subset: A ⊂ B means A ⊆ B and A ≠ B [read: “A is a proper subset of B”]
Set equality: A = B when A ⊆ B and B ⊆ A
Universal set: U contains all elements under consideration
Cardinality: |A| denotes the number of elements in set A [read: “cardinality of A” or “size of A”]
Finite vs infinite sets: Finite sets have countable elements (e.g., {1,2,3}); infinite sets like ℕ, ℤ don’t
Union: A ∪ B = {x | x ∈ A or x ∈ B} [read: “A union B”]
Intersection: A ∩ B = {x | x ∈ A and x ∈ B} [read: “A intersect B” or “A cap B”]
Set difference: A - B or A \ B = {x | x ∈ A and x ∉ B} [read: “A minus B” or “A setminus B”]
Complement: A’ or Ā = {x | x ∈ U and x ∉ A} [read: “A complement” or “A bar”]
Disjoint sets: A and B are disjoint if A ∩ B = ∅
Partition: Collection of non-empty disjoint sets whose union equals the original set
Power set: P(A) or 2^A - set of all subsets of A [read: “power set of A”]
Power set cardinality: |P(A)| = 2^|A|
Power set contains ∅: Empty set is always in power set, even P(∅) = {∅}
Cartesian product: A × B = {(a,b) | a ∈ A, b ∈ B} [read: “A cross B” or “A times B”]
Cartesian product cardinality: |A × B| = |A| × |B|
Identity laws: A ∪ ∅ = A and A ∩ U = A
Domination laws: A ∪ U = U and A ∩ ∅ = ∅
Idempotent laws: A ∪ A = A and A ∩ A = A
Complement laws: A ∪ A’ = U and A ∩ A’ = ∅
Double complement: (A’)’ = A
Commutative laws: A ∪ B = B ∪ A and A ∩ B = B ∩ A
Associative laws: (A ∪ B) ∪ C = A ∪ (B ∪ C) and (A ∩ B) ∩ C = A ∩ (B ∩ C)
Distributive laws: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
De Morgan’s laws: (A ∪ B)’ = A’ ∩ B’ and (A ∩ B)’ = A’ ∪ B'
Absorption laws: A ∪ (A ∩ B) = A and A ∩ (A ∪ B) = A
Inclusion-Exclusion (2 sets): |A ∪ B| = |A| + |B| - |A ∩ B|
Venn diagrams: Visual representation of set relationships using overlapping circles

Relations

Relation definition: Subset of Cartesian product A × B
Binary relation: Relation between elements of two sets
Endorelation: Relation from a set to itself (subset of A × A)
Relation notation: aRb or (a,b) ∈ R [read: “a is related to b”]
Domain: Set of all first elements in ordered pairs
Range/Codomain: Set of all second elements in ordered pairs
Inverse relation: R⁻¹ = {(b,a) | (a,b) ∈ R} [read: “R inverse”]
Reflexive property: aRa for all a ∈ A (every element relates to itself)
Symmetric property: If aRb then bRa
Antisymmetric property: If aRb and bRa then a = b
Transitive property: If aRb and bRc then aRc
Equivalence relation: Reflexive, symmetric, and transitive

Functions

Function definition: Relation where each input has exactly one output
Function notation: f: A → B [read: “f from A to B” or “f maps A to B”]
Domain: Set A (all possible inputs)
Codomain: Set B (all possible outputs)
Range/Image: f(A) = {f(a) | a ∈ A} ⊆ B (actual outputs used)
Function equality: f = g when f(x) = g(x) for all x in domain
Injective (one-to-one): Different inputs give different outputs; f(a) = f(b) implies a = b
Surjective (onto): Every codomain element is hit; for every b ∈ B, exists a ∈ A with f(a) = b
Bijective: Both injective and surjective (one-to-one correspondence)
Inverse function: f⁻¹ exists if and only if f is bijective [read: “f inverse”]
Composition: (g ∘ f)(x) = g(f(x)) [read: “g composed with f” or “g circle f”]
Identity function: id(x) = x
Constant function: f(x) = c for all x
Floor function: ⌊x⌋ = greatest integer ≤ x [read: “floor of x”]
Ceiling function: ⌈x⌉ = smallest integer ≥ x [read: “ceiling of x”]
Pigeonhole principle: n+1 objects in n boxes → at least one box has >1 object
Generalized pigeonhole: ⌈n/k⌉ objects in at least one box when n objects in k boxes

Counting

Sum rule: If A ∩ B = ∅, then |A ∪ B| = |A| + |B| (disjoint sets add)
Product rule: |A × B| = |A| × |B| (multiply for sequential choices)
Bijection principle: Sets have same size if bijection exists between them
Factorial: n! = n × (n-1) × … × 2 × 1 [read: “n factorial”]
0! = 1: By definition (important for formulas)
Permutations P(n,r): Ordered arrangements of r items from n items (no repetition)
- Formula: n!/(n-r)! = n × (n-1) × … × (n-r+1)
- Example: Arranging r people in a line from n people
Combinations C(n,r): Unordered selections of r items from n items (no repetition)
- Formula: n!/(r!(n-r)!)
- Example: Choosing r items from n items (like choosing a committee)
Combination notation: C(n,r) = (n choose r) = ⁿCᵣ [read: “n choose r”]
Arrangements with repetition: nʳ ways (each of r positions has n choices)
Circular permutations: (n-1)! ways to arrange n distinct objects in circle
Permutations of multisets: n!/(n₁!n₂!…nₖ!) when nᵢ copies of type i
Pascal’s identity: C(n,r) = C(n-1,r-1) + C(n-1,r)
Symmetry property: C(n,r) = C(n,n-r)
Sum of combinations: ∑C(n,k) = 2ⁿ for k=0 to n
Inclusion-Exclusion (general): |A₁ ∪ … ∪ Aₙ| alternating sum formula
Derangements D(n): Permutations where no element in original position

Advanced Counting (Problem Types)

Committee selection: Choosing groups with/without constraints
Team formation: Dividing people into teams (ordered vs unordered)
Shelf arrangement: Books/objects with grouping constraints
Letter arrangements: Words with repeated letters (like MISSISSIPPI)
Seating problems: People around tables with restrictions
Distribution problems: Objects into bins (distinct vs identical)
Path counting: Ways to travel on grids with constraints
Birthday problem: Probability at least 2 share birthday in group of n
Tie/group together technique: Treating grouped items as single unit
Gap method: Placing items between others (boys/girls not adjacent)
Complementary counting: Count what you don’t want, subtract from total
Case analysis: Break into disjoint cases, add results

Stars and Bars

Basic concept: Distributing n identical items into k distinct bins
Visual representation: n stars (★) and k-1 bars (|) to separate bins
- Example: ★★★|★|★★ represents 3 in bin 1, 1 in bin 2, 2 in bin 3
Formula: C(n+k-1, k-1) or equivalently C(n+k-1, n)
Non-negative integer solutions: Count solutions to x₁ + x₂ + … + xₖ = n where xᵢ ≥ 0
Positive integer solutions: x₁ + x₂ + … + xₖ = n with each xᵢ ≥ 1
- Give 1 to each first, then distribute n-k: C(n-1, k-1)
Lower bounds: For xᵢ ≥ aᵢ, distribute aᵢ first, then apply formula
Upper bounds: Use inclusion-exclusion when xᵢ ≤ bᵢ
Multiset size-r combinations: Choose r items from n types with repetition = C(n+r-1, r)

Probability

Sample space Ω: Set of all possible outcomes [read: “omega”]
Event: Any subset of sample space
Probability axioms: P(Ω)=1, P(A)≥0, P(A∪B)=P(A)+P(B) if A∩B=∅
Uniform distribution: All outcomes equally likely; P(E) = |E|/|Ω|
Complement rule: P(A’) = 1 - P(A) [read: “P of A complement”]
Addition rule: P(A∪B) = P(A) + P(B) - P(A∩B)
Conditional probability: P(A|B) = P(A∩B)/P(B) [read: “P of A given B”]
Multiplication rule: P(A∩B) = P(A|B) × P(B)
Independence: Events A, B independent if P(A∩B) = P(A) × P(B)
Mutual independence: All subsets of events satisfy independence
Bayes’ theorem: P(A|B) = [P(B|A) × P(A)]/P(B)
Law of total probability: P(B) = ∑P(B|Aᵢ) × P(Aᵢ) where Aᵢ partition Ω
Random variable: Function X: Ω → ℝ mapping outcomes to numbers
Expected value: E[X] = ∑x × P(X=x) [read: “expected value of X” or “E of X”]
Linearity of expectation: E[X+Y] = E[X] + E[Y] (always true)
Variance: Var(X) = E[(X-μ)²] = E[X²] - (E[X])²
Standard deviation: σ = √Var(X) [read: “sigma”]
Bernoulli trial: Single experiment with success probability p
Binomial distribution: B(n,p) - exactly k successes in n trials
Binomial formula: P(X=k) = C(n,k) × p^k × (1-p)^(n-k)
Geometric distribution: Number of trials until first success

Logic

Proposition: Statement that is either true or false (not both)
Truth values: True (T or 1) or False (F or 0)
Negation: ¬p is true when p is false [read: “not p”]
Conjunction: p ∧ q is true when both are true [read: “p and q”]
Disjunction: p ∨ q is true when at least one is true [read: “p or q”]
Exclusive or: p ⊕ q is true when exactly one is true [read: “p XOR q”]
Implication: p → q is false only when p true and q false [read: “p implies q” or “if p then q”]
Biconditional: p ↔ q is true when both have same truth value [read: “p if and only if q” or “p iff q”]
Truth tables: Systematic evaluation of compound propositions
Tautology: Always true regardless of variable values
Contradiction: Always false regardless of variable values
Contingency: Sometimes true, sometimes false
Logical equivalence: p ≡ q when same truth values always [read: “p is equivalent to q”]
De Morgan’s laws (logic): ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q
Contrapositive: p → q ≡ ¬q → ¬p (always equivalent)
Converse: q → p (not necessarily equivalent to p → q)
Inverse: ¬p → ¬q (not necessarily equivalent to p → q)
Distributive laws: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Absorption laws: p ∨ (p ∧ q) ≡ p and p ∧ (p ∨ q) ≡ p
Predicate: Statement with variables P(x)
Universal quantifier: ∀x P(x) - true for all x in domain [read: “for all x, P of x”]
Existential quantifier: ∃x P(x) - true for at least one x [read: “there exists x such that P of x”]
Uniqueness quantifier: ∃!x P(x) - true for exactly one x [read: “there exists unique x such that P of x”]
Nested quantifiers: Order matters; ∀x∃y ≠ ∃y∀x in general
Quantifier negation: ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x)
Bound vs free variables: Variables inside/outside quantifier scope
Valid argument: Conclusion logically follows from premises
Modus ponens: From p and p→q, conclude q
Modus tollens: From ¬q and p→q, conclude ¬p
Hypothetical syllogism: From p→q and q→r, conclude p→r
Disjunctive syllogism: From p∨q and ¬p, conclude q

Introduction to Proofs

Direct proof (Template 1): State hypothesis, work forward to conclusion, link the steps
Proof by contradiction (Template 12): Assume opposite, derive contradiction ⇒⇐
Proof by contrapositive (Template 11): To prove p→q, instead prove ¬q→¬p
Proof by cases: Break into exhaustive cases, prove each separately
Existence proof (Template 7): Constructive (build example) vs non-constructive
Uniqueness proof (Template 14): Show exists, then assume two solutions and prove equal
Counterexample (Template 3): Find instance where hypothesis true but conclusion false
If and only if proofs (Template 2): Prove both directions (⇒) and (⇐)
Proof symbols: ∴ [read: “therefore”], ∵ [read: “because”], □ or QED [read: “end of proof”]
Common mistakes: Circular reasoning (using what you’re proving), assuming conclusion
Vacuous truth: p→q is true when p is false (empty case)
Trivial proof: p→q is true when q is always true

Elementary Proof Techniques

Truth table proof (Template 4): Show logical equivalence by checking all cases
Set equality proof (Template 5): Show A ⊆ B and B ⊆ A
Subset proof (Template 6): Let x ∈ A, show x ∈ B through logical steps
Universal statement proof (Template 8): Let x be arbitrary element, prove property
Combinatorial proof (Template 9): Count same thing two ways, equate results
Inclusion-exclusion proof (Template 10): Classify as good/bad, use overlaps
Empty set proof (Template 13): Assume nonempty, derive contradiction
Smallest counterexample (Template 15): Consider smallest failure case, derive contradiction
Well-ordering principle (Template 16): Use existence of smallest element in ℕ
Without loss of generality (WLOG): Reduce symmetric cases
Pigeonhole principle proofs: Identify pigeons (objects) and holes (containers)
Parity arguments: Use even/odd properties (sum of evens is even, etc.)
Divisibility proofs: Use definition a|b means b = ka for some integer k
Modular arithmetic proofs: Work with remainders and congruences
Rational/irrational proofs: Classic √2 irrational proof by contradiction
Clear proof writing: State goal, justify each step, conclude clearly

Induction Proof Techniques

Mathematical induction principle (Template 17): Base case + inductive step
Induction structure: [P(n₀) ∧ (P(k) → P(k+1))] → ∀n≥n₀ P(n)
Choosing base case: Start at smallest value where claim should hold
Inductive hypothesis (IH): “Assume P(k) is true for some k ≥ n₀”
Inductive step: Using P(k), prove P(k+1) follows
Common error: Cannot use P(k+1) to prove P(k+1) (circular)
Multiple base cases: Sometimes need P(0) and P(1) for P(k+2) step

Weak Induction

Standard form: Assume P(k), prove P(k+1)
Base case verification: Explicitly check P(n₀) (often n₀ = 0 or 1)
Classic examples: Sum formulas like 1+2+…+n = n(n+1)/2
Inequality proofs by induction: Like 2ⁿ > n² for n ≥ 5
Divisibility by induction: Like proving n³-n divisible by 3
Set size proofs: Like |P(S)| = 2^|S| by induction on |S|
Algorithm correctness: Proving loops work via loop invariants
Tiling problems: Like 2ⁿ × 2ⁿ board minus one square

Strong Induction

Strong induction principle (Template 18): Assume P(n₀) through P(k) all true
When to use: Need multiple previous cases (like Fibonacci proofs)
Strong vs weak: Strong assumes all P(i) for n₀ ≤ i ≤ k; weak just P(k)
Prime factorization theorem: Every integer > 1 has unique prime factorization
Fibonacci inequality proofs: Like Fₙ < 2ⁿ
Postage stamp problems: Making amounts with certain denominations

Graphs

Graph definition: G = (V,E) where V is vertices, E is edges
Directed vs undirected: Edges have direction (arrows) or not
Adjacent vertices: Connected by an edge; neighbors
Degree of vertex: Number of edges incident to it; deg(v)
In-degree/out-degree: For directed graphs; edges coming in/going out
Handshaking lemma: ∑deg(v) = 2|E| (each edge contributes 2 to sum)
Path: Sequence of vertices v₁, v₂, …, vₖ where consecutive vertices adjacent
Simple path: Path with no repeated vertices
Cycle: Path that starts and ends at same vertex
Simple cycle: Cycle with no repeated vertices except first=last
Connected graph: Path exists between any two vertices
Connected components: Maximal connected subgraphs
Complete graph Kₙ: All possible edges present; n(n-1)/2 edges
Bipartite graph: Vertices split into two sets, edges only between sets
Complete bipartite Kₘ,ₙ: All possible edges between two parts
Tree: Connected acyclic graph
Forest: Disjoint union of trees (acyclic, possibly disconnected)
Tree properties: n vertices implies exactly n-1 edges
Spanning tree: Subgraph that includes all vertices and is a tree
Rooted tree: Tree with one vertex designated as root
Binary tree: Rooted tree where each vertex has at most 2 children
Tree traversal: Preorder, inorder, postorder ways to visit nodes
Graph isomorphism: Same structure but vertices labeled differently
Planar graph: Can be drawn in plane without edge crossings
Euler path: Path using every edge exactly once
Euler circuit: Euler path that starts and ends at same vertex
Euler’s theorem: Euler circuit exists iff all vertices have even degree
Hamilton path: Path visiting every vertex exactly once
Hamilton circuit: Hamilton path that returns to start
Adjacency matrix: n×n matrix where entry (i,j) = 1 if edge exists
Adjacency list: For each vertex, list of its neighbors
Weighted graphs: Edges have numerical weights/costs
Shortest path problem: Find minimum total weight path
Dijkstra’s algorithm: Finds shortest paths from source vertex
Minimum spanning tree (MST): Lightest tree connecting all vertices
Kruskal’s algorithm: Build MST by adding lightest edges
Prim’s algorithm: Build MST by growing from starting vertex
Breadth-first search (BFS): Explore level by level from start
Depth-first search (DFS): Explore as far as possible, then backtrack
Directed acyclic graph (DAG): Directed graph with no cycles
Topological sort: Order vertices so all edges go forward