Discrete Math Definitions

Set: A set is a well-defined collection of distinct objects, called elements or members, typically denoted by uppercase letters. If x is an element of set A, we write x ∈ A.
Subset: A set A is a subset of a set B (denoted A ⊆ B) if every element of A is also an element of B.
Proper Subset: A is a proper subset of B (denoted A ⊂ B) if A ⊆ B and A ≠ B.
Empty Set: The empty set, denoted ∅, is the unique set that contains no elements.
Power Set: The power set of A, denoted 𝒫(A), is the set of all subsets of A, including ∅ and A itself.
Universal Set: The universal set U is the set that contains all objects under consideration in a particular context.
Union: The union of sets A and B, denoted A ∪ B, is defined as { x ∣ x ∈ A or x ∈ B }.
Intersection: The intersection of sets A and B, denoted A ∩ B, is defined as { x ∣ x ∈ A and x ∈ B }.
Set Difference: The difference of sets A and B, denoted A − B, is the set { x ∣ x ∈ A and x ∉ B }.
Complement: The complement of a set A, relative to universal set U, is A′ = U − A.
Cartesian Product: Given sets A and B, the Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.
Relation: A relation R from set A to set B is a subset of the Cartesian product A × B.
Function: A function f from a set A to a set B, denoted f: A → B, is a relation in which every element a ∈ A is associated with exactly one element b ∈ B.
Domain: The domain of a function f is the set of all inputs for which f is defined.
Codomain: The codomain of f is the set B that contains all possible outputs, regardless of whether they are achieved by f.
Range: The range of f is the set { f(a) ∣ a ∈ A }.
Injective Function (One-to-One): A function f: A → B is injective if for all a₁, a₂ ∈ A, f(a₁) = f(a₂) implies a₁ = a₂.
Surjective Function (Onto): A function f: A → B is surjective if for every b ∈ B, there exists a ∈ A such that f(a) = b.
Bijective Function: A function is bijective if it is both injective and surjective.
Proposition: A proposition is a declarative statement that is either true or false, but not both.
Predicate: A predicate is a function P(x) that returns a proposition when a specific value is substituted for the variable x.
Logical Connectives: Operations on propositions:
- Negation: ¬P (“not P”)
- Conjunction: P ∧ Q (“P and Q”)
- Disjunction: P ∨ Q (“P or Q”)
- Implication: P → Q (“If P then Q”)
- Biconditional: P ↔ Q (“P if and only if Q”)
Tautology: A proposition that is true under all possible truth assignments.
Contradiction: A proposition that is false under all possible truth assignments.
Contingency: A proposition that is neither a tautology nor a contradiction.
Logical Equivalence: Propositions P and Q are logically equivalent, denoted P ≡ Q, if they have identical truth values under all interpretations.
Contrapositive: The contrapositive of P → Q is ¬Q → ¬P. A statement and its contrapositive are logically equivalent.
Quantifiers:
- Universal Quantifier (∀): ∀x ∈ A, P(x) asserts that P(x) holds for all elements x in A.
- Existential Quantifier (∃): ∃x ∈ A, P(x) asserts that there exists at least one x in A such that P(x) holds.
Proof: A finite sequence of logically justified statements that establish the truth of a mathematical proposition.
Direct Proof: Proves P → Q by assuming P is true and showing that Q must follow.
Proof by Contrapositive: Proves P → Q by proving ¬Q → ¬P.
Proof by Contradiction: Assumes the negation of the conclusion and derives a logical contradiction.
Mathematical Induction: A method of proof for propositions indexed by natural numbers:
- Prove the base case (e.g., P(0)).
- Prove the inductive step: P(k) → P(k+1).
Strong Induction: Similar to induction but assumes P(0), P(1), …, P(k) to prove P(k+1).
Well-Ordering Principle: Every non-empty set of non-negative integers has a least element.
Divisibility: An integer a divides b, written a ∣ b, if there exists an integer k such that ak = b.
Prime Number: A positive integer greater than 1 with exactly two positive divisors: 1 and itself.
Greatest Common Divisor (gcd): The largest integer that divides two given integers without remainder.
Least Common Multiple (lcm): The smallest positive integer divisible by both given integers.
Modular Arithmetic: A system of arithmetic for integers where numbers “wrap around” after reaching a modulus n.
Congruence Modulo n: a ≡ b (mod n) if n divides (a − b).
Equivalence Relation: A relation R on a set A is an equivalence relation if it is:
- Reflexive: aRa for all a ∈ A.
- Symmetric: aRb implies bRa.
- Transitive: aRb and bRc imply aRc.
Equivalence Class: Given an equivalence relation R on A, the equivalence class of a ∈ A is the set { x ∈ A ∣ xRa }.
Partition: A collection of disjoint non-empty subsets of A whose union is A.
Graph: An ordered pair G = (V, E) where V is a non-empty set of vertices and E is a set of unordered or ordered pairs of vertices called edges.
Degree: The degree of a vertex in an undirected graph is the number of edges incident to it.
Path: A sequence of vertices such that each consecutive pair is connected by an edge.
Cycle: A path in which the first and last vertices are the same and no edge is repeated.
Connected Graph: A graph in which there exists a path between every pair of vertices.
Tree: A connected acyclic graph.
Spanning Tree: A subgraph of G that includes all the vertices of G and is a tree.
Adjacency Matrix: A matrix used to represent a graph where entry (i, j) is 1 if there is an edge from vertex i to j, and 0 otherwise.
Graph Isomorphism: Two graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) are isomorphic if there exists a bijection f: V₁ → V₂ such that (u, v) ∈ E₁ if and only if (f(u), f(v)) ∈ E₂.
Planar Graph: A graph that can be embedded in the plane without edge crossings.
Eulerian Path: A path in a graph that visits every edge exactly once.
Hamiltonian Path: A path in a graph that visits every vertex exactly once.
Recursion: A method of defining a function or sequence in terms of itself.
Recurrence Relation: An equation that recursively defines a sequence by expressing each term as a function of preceding terms.
Generating Function: A formal power series in which the coefficients correspond to the terms of a sequence.
Big O Notation: f(n) ∈ O(g(n)) means that for sufficiently large n, f(n) grows no faster than a constant multiple of g(n).
Big Ω Notation: f(n) ∈ Ω(g(n)) means that for sufficiently large n, f(n) grows at least as fast as a constant multiple of g(n).
Big Θ Notation: f(n) ∈ Θ(g(n)) means that f(n) grows at the same rate as g(n) up to constant factors.
Pigeonhole Principle: If n objects are distributed among m containers and n > m, then at least one container holds more than one object.
Combinatorics: The branch of mathematics dealing with combinations, permutations, and enumeration of elements in sets.
Permutation: An ordered arrangement of r elements selected from a set of n distinct elements.
Combination: An unordered selection of r elements from a set of n elements.
Binomial Theorem: Describes the expansion of (x + y)ⁿ as the sum ∑ₖ₌₀ⁿ (n choose k) xⁿ⁻ᵏ yᵏ.
Lattice: A partially ordered set (L, ≤) in which every pair of elements a, b ∈ L has a unique least upper bound (join a ∨ b) and greatest lower bound (meet a ∧ b).
Boolean Algebra: A complemented distributive lattice (B, ∨, ∧, ¬) satisfying:
- Commutativity: a ∨ b = b ∨ a, a ∧ b = b ∧ a
- Associativity: (a ∨ b) ∨ c = a ∨ (b ∨ c), and similarly for ∧
- Distributivity: a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c), and vice versa
- Identity: a ∨ 0 = a, a ∧ 1 = a
- Complement: a ∨ ¬a = 1, a ∧ ¬a = 0
Hasse Diagram: A graphical representation of a finite partially ordered set, where edges indicate cover relations (minimal ordering steps).
Poset (Partially Ordered Set): A set P with a binary relation ≤ that is reflexive, antisymmetric, and transitive.
Total Order: A partial order in which every pair of elements is comparable: for all a, b ∈ P, either a ≤ b or b ≤ a.
Well-Founded Order: A partial order with no infinite descending chains.
Dilworth’s Theorem: In any finite poset, the size of the largest antichain equals the minimum number of chains needed to cover the set.
Zorn’s Lemma: If every chain in a non-empty partially ordered set has an upper bound, then the set contains at least one maximal element.
Hall’s Marriage Theorem: A bipartite graph has a matching that covers one part if and only if every subset of that part is matched to at least as many nodes on the other side.
Ramsey Theory: A branch of mathematics studying the conditions under which order must appear, such as the minimal conditions to guarantee a complete subgraph.
Turing Machine: A theoretical model of computation consisting of an infinite tape, a tape head, and a finite set of states used to recognize formal languages.
Decidability: A language or problem is decidable if there exists an algorithm (Turing machine) that halts with a correct yes/no answer for every input.
Undecidable Problem: A problem for which no algorithm exists that can always produce a correct yes/no answer in finite time (e.g., the Halting Problem).
P vs NP Problem: The question of whether every problem for which a solution can be verified in polynomial time (NP) can also be solved in polynomial time (P).
NP-Complete: A problem is NP-complete if it is in NP and as hard as any problem in NP; that is, every problem in NP reduces to it in polynomial time.
Reduction: A method of solving one problem using a solution to another, often used to prove NP-completeness.
Graph Coloring: The assignment of colors to vertices of a graph such that adjacent vertices receive different colors. The chromatic number is the minimum number of colors needed.
Chromatic Polynomial: A function P(G, k) that counts the number of valid k-colorings of a graph G.
Euler’s Formula: For a connected planar graph with v vertices, e edges, and f faces, v − e + f = 2.
Kuratowski’s Theorem: A graph is non-planar if and only if it contains a subdivision of K₅ or K₃,₃.
Spectral Graph Theory: Studies properties of a graph using the eigenvalues and eigenvectors of matrices such as the adjacency matrix or Laplacian matrix.
Matrix-Tree Theorem: The number of spanning trees in a graph equals any cofactor of its Laplacian matrix.
Stable Matching: A matching where no two elements prefer each other over their current matches. Central to the Gale-Shapley algorithm.
Mobius Function (Posets): In incidence algebra, used for inversion formulas over posets; defined recursively in terms of zeta functions.
Generating Functions (Advanced): Used in solving recurrence relations; formal power series where operations encode combinatorial properties.
Recursion Trees: A visualization of recursive function calls used to analyze time complexity.
Master Theorem: Provides a solution for recurrence relations of the form T(n) = aT(n/b) + f(n) for divide-and-conquer algorithms.
Propositional Logic: A logic with variables and connectives, used to build compound statements.
First-Order Logic (FOL): Extends propositional logic by including quantifiers and predicates with variables ranging over a domain.
Gödel’s Incompleteness Theorems:
- Any consistent formal system expressive enough to describe arithmetic is incomplete.
- Such a system cannot prove its own consistency.
Peano Arithmetic: A formal system for natural numbers with axioms governing 0, successor, addition, and multiplication.
Lambda Calculus: A formal system for function definition, application, and recursion; the foundation for functional programming.
Combinatorial Design: A study of arrangements of elements with specific properties, including:
- Block Designs: Structures like balanced incomplete block designs (BIBDs).
- Latin Squares: An n × n array where each symbol occurs exactly once in each row and column.
Inclusion-Exclusion Principle: For finite sets A₁, …, Aₙ,
|⋃ Aᵢ| = Σ |Aᵢ| − Σ |Aᵢ ∩ Aⱼ| + Σ |Aᵢ ∩ Aⱼ ∩ Aₖ| − …
Stirling Numbers: Count ways to partition a set of n objects into k non-empty subsets (second kind), or permutations with k cycles (first kind).
Bell Numbers: Count the number of partitions of a set of n elements.
Burnside’s Lemma: A tool in group theory for counting distinct configurations under group actions.
Polya Enumeration Theorem: Generalizes Burnside’s Lemma to count patterns under group symmetries.

Discrete Math Definitions

Share this:

Discover more from SodakAI: Bespoke AI Solutions