foundations-of-mathematics.bigb

= Foundations of mathematics
{wiki}

= Set theory
{parent=Foundations of mathematics}
{wiki}

= Von Neumann hierarchy
{title2=$V_\alpha$}
{c}
{parent=Set theory}
{wiki}

The von Neumann hierarchy is
$$
V_0=\varnothing,
\qquad
V_{\alpha+1}=\mathcal P(V_\alpha),
\qquad
V_\lambda=\bigcup_{\beta<\lambda}V_\beta.
$$
Every level is transitive, the levels are increasing, and every set belongs to some level.

= Rank of a set
{parent=Von Neumann hierarchy}
{wiki=Rank_(set_theory)}

The rank is defined by
$$
\operatorname{rank}(x)
=\sup_{y\in x}(\operatorname{rank}(y)+1).
$$
It is the least ordinal $\alpha$ for which $x\subseteq V_\alpha$.

= Transitive set
{parent=Set theory}
{wiki}

A set $X$ is transitive when every element of an element of $X$ is itself an element of $X$.

= Well-founded relation
{parent=Set theory}
{wiki=Well-founded_relation}

A relation $r$ on $X$ is well-founded when every nonempty subset of $X$ contains an element with no $r$-predecessor in that subset.

= Extensional relation
{parent=Set theory}
{wiki=Extensionality}

A relation is extensional when distinct elements have distinct sets of predecessors.

= Set
{parent=Set theory}
{wiki=Set_(mathematics)}

A set is a collection of distinct objects regarded as its elements.

= Empty set
{title2=$\varnothing$}
{parent=Set}
{wiki}

The empty set has no elements.

= Singleton set
{parent=Set}
{wiki=Singleton_(mathematics)}

A singleton set has exactly one element.

= Distinct elements
{parent=Set}

Elements are distinct when they are unequal.

= Generating set
{parent=Set}
{wiki}

A generating set is a subset from which every element of a structure can be obtained using the structure's operations.

= Subset
{parent=Set}
{wiki}

A set $A$ is a subset of $B$ when every element of $A$ belongs to $B$.

= Set union
{title2=$\bigcup$}
{parent=Set}
{wiki=Union_(set_theory)}

The union $\bigcup_{i\in I}A_i$ contains exactly the elements that belong to at least one set $A_i$.

= Union
{synonym}

= Set intersection
{title2=$\bigcap$}
{parent=Set}
{wiki=Intersection_(set_theory)}

The intersection $\bigcap_{i\in I}A_i$ contains exactly the elements that belong to every set $A_i$.

= Intersection
{synonym}

= Pair
{parent=Set}
{wiki=Pair_(mathematics)}

A pair is a collection of two objects. An ordered pair records which object is first, whereas an unordered pair does not.

= Ordered pair
{parent=Pair}
{wiki}

= Ordered pairs
{synonym}

= Unordered pair
{parent=Pair}
{wiki=Pair_(mathematics)}

= Partially ordered set
{parent=Set}
{wiki=Partially_ordered_set}

A partially ordered set, or poset, is a set equipped with a reflexive, antisymmetric and transitive binary relation.

= Poset
{synonym}

= Maximal element of a partially ordered set
{parent=Partially ordered set}
{wiki=Maximal_and_minimal_elements}

An element $m$ of a partially ordered set is maximal when $m\leq x$ implies $x=m$. A poset can have several maximal elements and need not have a greatest element.

= Maximal element
{synonym}

= Minimal element of a partially ordered set
{parent=Partially ordered set}
{wiki=Maximal_and_minimal_elements}

An element $m$ of a partially ordered set is minimal when $x\leq m$ implies $x=m$.

= Minimal element
{synonym}

= Total order
{parent=Set}
{wiki}

A total order is a reflexive, antisymmetric, transitive relation in which every two elements are comparable.

= Empty order
{parent=Total order}

The empty order is the unique total order on the <empty set>.

= Greatest element
{parent=Total order}
{wiki=Greatest_element_and_least_element}

An element is greatest when every element of the ordered set is less than or equal to it.

= Initial segment
{parent=Total order}
{wiki}

An initial segment contains every element below each of its elements.

= Initial segments
{synonym}

= Binary relation
{parent=Set theory}
{wiki}

A binary relation on a set $X$ is a subset of $X\times X$.

= Reflexive relation
{parent=Binary relation}
{wiki=Reflexive_relation}

A relation $\mathrel R$ on $X$ is reflexive when $x\mathrel R x$ for every $x\in X$.

= Symmetric relation
{parent=Binary relation}
{wiki=Symmetric_relation}

A relation $\mathrel R$ is symmetric when $x\mathrel R y$ implies $y\mathrel R x$.

= Transitive relation
{parent=Binary relation}
{wiki=Transitive_relation}

A relation $\mathrel R$ is transitive when $x\mathrel R y$ and $y\mathrel R z$ imply $x\mathrel R z$.

= Equivalence relation
{parent=Binary relation}
{wiki}

An equivalence relation is a reflexive, symmetric, and transitive binary relation. It partitions a set into disjoint equivalence classes.

= Function
{parent=Set theory}
{wiki=Function_(mathematics)}

A function assigns exactly one output to each input in its domain.

= Map
{synonym}

= Identity function
{title2=$\operatorname{id}$}
{parent=Function}
{wiki=Identity_function}

The identity function on a set $X$ maps every $x\in X$ to itself.

= Identity map
{synonym}

= Piecewise-linear function
{parent=Function}
{wiki=Piecewise_linear_function}

A piecewise-linear function is linear on each member of a finite or locally finite partition of its domain into intervals or polyhedral pieces.

= Bounded function
{parent=Function}
{wiki}

A real- or complex-valued function is bounded when the <moduli> of all its values have one finite upper bound.

= Unbounded function
{parent=Bounded function}
{wiki=Bounded_function}

An unbounded function has no finite bound on the <moduli> of its values.

= Constant function
{parent=Function}
{wiki}

A constant function has the same output for every input.

= Real-valued function
{parent=Function}
{wiki=Real-valued_function}

A real-valued function has codomain contained in the real numbers.

= Global maximum
{parent=Real-valued function}
{wiki=Maximum_and_minimum}

A global maximum of a real-valued function is a value $f(x_0)$ satisfying $f(x)\leq f(x_0)$ throughout its domain.

= Bijection
{parent=Function}
{wiki}

A bijection is a function that is both injective and surjective, so every target element has exactly one preimage.

= Periodic function
{parent=Function}
{wiki=Periodic_function}

A function is periodic when $f(x+T)=f(x)$ for some nonzero period $T$ and every $x$ in its domain.

= Zorn lemma
{parent=Set theory}
{c}
{wiki=Zorn%27s_lemma}

If every chain in a nonempty partially ordered set has an upper bound, then the set has a maximal element.

= Class in set theory
{parent=Set theory}
{wiki=Class_(set_theory)}

A class is a collection of sets specified by a formula, possibly with set parameters. A class is a set when one set has exactly those members.

= Proper class
{parent=Class in set theory}
{wiki}

A proper class is a <class in set theory> that is not a set in the ambient universe.

= Transitive class
{parent=Class in set theory}
{wiki=Transitive_set}

A class $M$ is transitive when $x\in y\in M$ implies $x\in M$. Consequently, every member of a member of $M$ is available as an element of the structure $(M,\in)$.

= Basic set-theoretic axioms inherited by a transitive class
{parent=Transitive class}

If a transitive class $M$ contains the empty set and is closed under pairing and union, then $(M,\in)$ satisfies extensionality, empty set, pairing, and union. Transitivity makes all members of each $x\in M$ visible inside $M$, so the ambient witnesses have the same required membership relations internally.

= Formula relativization to a class
{parent=Transitive class}

The relativization $\varphi^M$ of a formula $\varphi$ is obtained recursively by restricting every quantifier to $M$:
$$
(\exists x\,\psi)^M=\exists x\,(x\in M\land\psi^M),
\qquad
(\forall x\,\psi)^M=\forall x\,(x\in M\mathbin\Rightarrow\psi^M).
$$
For parameters in $M$, the ambient statement $\varphi^M$ holds exactly when the structure $(M,\in)$ satisfies $\varphi$.

= Axiom schema of replacement
{parent=Set theory}
{c}
{wiki=Axiom_schema_of_replacement}

Every definable function-class maps a set-sized domain to a set-sized range. Functionality means that the defining formula assigns exactly one output to each input in the domain.

= Axiom of foundation
{parent=Set theory}
{c}
{wiki=Axiom_of_regularity}

Every nonempty set $A$ has an element $x\in A$ such that $x\cap A=\varnothing$.

= Epsilon induction
{title2=$\in$-induction}
{parent=Axiom of foundation}

The principle of epsilon induction says that every progressive class is universal: if
$$
\forall x\left[
(\forall y\in x,\ \varphi(y))\Longrightarrow\varphi(x)
\right],
$$
then $\varphi(x)$ holds for every set $x$. Over the other axioms of ZF, it is equivalent to the <axiom of foundation>.

= Axiom of power set
{parent=Set theory}
{c}
{wiki=Axiom_of_power_set}

For every set $x$ there is a set $\mathcal P(x)$ whose members are exactly the subsets of $x$.

= Cumulative hierarchy
{title2=$V_\alpha$}
{parent=Set theory}
{wiki}

The cumulative hierarchy is defined by $V_0=\varnothing$, $V_{\alpha+1}=\mathcal P(V_\alpha)$, and $V_\lambda=\bigcup_{\alpha<\lambda}V_\alpha$ at limit ordinals.

= Transitive closure
{title2=$\operatorname{TC}(x)$}
{parent=Cumulative hierarchy}
{wiki}

The transitive closure $\operatorname{TC}(x)$ is the least transitive set containing every member of $x$. It is obtained by taking the union of all finite iterates of the union operation starting from $x$.

= Hereditarily countable set
{title2=$H_{\omega_1}$}
{parent=Transitive closure}
{wiki=Hereditarily_countable_set}

A set is hereditarily countable when its <transitive closure> is <countable set>[countable]. These sets form the transitive set $H_{\omega_1}$ and all have rank below $\omega_1$.

= Reasonable set
{parent=Hereditarily countable set}

A set $x$ is reasonable when every member of $\operatorname{TC}(\{x\})$ is countable. In ZFC this is equivalent to $x$ being <hereditarily countable set>[hereditarily countable].

= Hereditarily finite set
{parent=Cumulative hierarchy}
{wiki}

The class of hereditarily finite sets is the set
$$
V_\omega=\bigcup_{n<\omega}V_n.
$$
Equivalently, these are the sets with finite transitive closure, or the sets contained in a finite transitive set.

= Axiom schema of specification
{parent=Set theory}
{wiki}

For each formula $\varphi$, the axiom schema of specification forms the subset
$$
\{z\in x:\varphi(z)\}
$$
of any set $x$. When interpreting the schema inside a class model, the formula must be evaluated internally.

= Axiom schema of separation
{synonym}

= Relativized closure criterion for separation
{parent=Axiom schema of specification}

Let $M$ be a transitive class. If $M$ is closed under the ambient subsets defined by $\varphi^M$, then $M$ satisfies the $\varphi$-instance of separation, because
$$
\{z\in x:V\models\varphi^M(z)\}
=\{z\in x:M\models\varphi(z)\}.
$$

= Axiom of choice
{parent=Set theory}
{wiki}

Every family of nonempty sets has a choice function. In ZF this is equivalent to the well-ordering theorem.

= Choice function
{parent=Axiom of choice}
{wiki}

A choice function on a family $\mathcal A$ of nonempty sets is a function $f$ with $f(A)\in A$ for every $A\in\mathcal A$.

= Well-ordering theorem
{parent=Axiom of choice}
{wiki}

Every set admits a well-order. In ZF this statement is equivalent to the <axiom of choice>.

= Choice-function well-ordering construction
{parent=Well-ordering theorem}

Given a choice function on all nonempty subsets of $X$, recursively choose the next point from the complement of all earlier choices. <Hartogs theorem> forces the recursion to exhaust $X$ before it defines an injection from $h(X)$ into $X$, producing a bijection from an ordinal to $X$.

= Cardinal comparability principle
{parent=Axiom of choice}

For any sets $X,Y$, either $X$ injects into $Y$ or $Y$ injects into $X$. Applying this to $X$ and its Hartogs ordinal proves the <well-ordering theorem>, so over ZF cardinal comparability is equivalent to choice.

= Hartogs theorem
{c}
{parent=Set theory}
{wiki=Hartogs_number}

For every set $X$ there is a least ordinal $h(X)$ that does not inject into $X$.

= Tarski cardinal-square theorem
{c}
{parent=Set theory}

In ZF, if $X\times X\cong X$ for every infinite $X$, apply this to $X\sqcup h(X)$. The <product-sum comparison lemma> applied to $X$ and its Hartogs ordinal gives either an impossible injection $h(X)\to X$ or a surjection $h(X)\to X$. In the latter case, ordering each $x\in X$ by its least ordinal preimage well-orders $X$. The converse is the well-orderable-cardinal identity $\kappa^2=\kappa$.

= Image and preimage of a function
{parent=Set theory}
{wiki}

Images send subsets of a domain forward through a function, while preimages pull subsets of the codomain back.

= Cartesian product
{title2=$X\times Y$}
{parent=Set theory}
{wiki}

The Cartesian product $X\times Y$ is the set of ordered pairs $(x,y)$ with $x\in X$ and $y\in Y$.

= Disjoint union
{title2=$X\sqcup Y$}
{parent=Set theory}
{wiki}

The disjoint union tags the elements of its summands, for example $X\sqcup Y=(X\times\{0\})\cup(Y\times\{1\})$.

= Fiber product of sets
{parent=Set theory}
{wiki}

The fiber product of maps f:A to B and g:A-prime to B consists of pairs with equal images in B.

= Cantor diagonal argument
{parent=Set theory}
{c}
{wiki}

Cantor’s diagonal argument constructs an object differing from the nth listed object in its nth coordinate, proving no proposed enumeration is complete.

= Cardinal number
{parent=Set theory}
{wiki}

In the presence of choice, a cardinal number may be represented by the least ordinal in its bijection class.

= Uncountable set
{parent=Cardinal number}
{wiki=Uncountable_set}

An uncountable set is a set for which no <bijection> with a subset of the natural numbers exists.

= Initial ordinal
{parent=Cardinal number}
{wiki}

An initial ordinal is an ordinal not equinumerous with any smaller ordinal. It is therefore the canonical ordinal representative of a cardinal.

= Aleph number
{parent=Initial ordinal}
{wiki}

The alephs enumerate the infinite initial ordinals: $\aleph_0=\omega$, successor indices select the next initial ordinal, and limit indices select the least initial ordinal above all earlier values.

= Cardinal arithmetic
{parent=Cardinal number}
{wiki}

Cardinal sums are cardinalities of disjoint unions, products are cardinalities of Cartesian products, and exponentials $\kappa^\lambda$ count functions from a set of size $\lambda$ to one of size $\kappa$.

= Product-sum comparison lemma
{title2=$\kappa\lambda\leq\kappa+\lambda$}
{parent=Cardinal arithmetic}

In ZF, let $K,L$ be nonempty. If $K\times L$ injects into $K\sqcup L$, then there is either an injection or a surjection from $K$ to $L$.

Indeed, extend the inverse of the given injection to a surjection $p:K\sqcup L\to K\times L$ by sending points outside its range to one fixed pair $(k_*,l_*)$. If the second coordinate of $p$ restricted to the $K$-summand covers $L$, it is the required surjection. Otherwise choose $l_0$ that it misses. Every $(k,l_0)$ then has its preimage in the $L$-summand. Except possibly for the default pair, that preimage is unique, so these preimages inject $K$ into $L$. In the exceptional case they inject $K\setminus\{k_*\}$ into $L$; either their image is all of $L$, yielding a surjection from $K$, or an omitted point extends the map to an injection from $K$.

= Infinite cardinal arithmetic
{parent=Cardinal arithmetic}

For infinite cardinals, choice gives $\kappa+\kappa=\kappa\cdot\kappa=\kappa$. Exponentiation satisfies $(\kappa^\lambda)^\mu=\kappa^{\lambda\mu}$, while a countable sum of cardinals has size the maximum of $\aleph_0$ and their supremum.

= König theorem for cardinal numbers
{parent=Cardinal arithmetic}
{c}
{wiki=König's_theorem_(set_theory)}

If $\kappa_i<\lambda_i$ for every $i\in I$, then
$$
\sum_{i\in I}\kappa_i<\prod_{i\in I}\lambda_i.
$$
The injection uses functions supported at one coordinate. For non-surjectivity, given any map from the disjoint union to the product, choose at coordinate $i$ a value omitted by the $i$th row; the resulting diagonal element is outside its image.

= Cantor-Schröder-Bernstein theorem
{parent=Cardinal number}
{c}
{wiki}

If there are injections $X\to Y$ and $Y\to X$, then there is a bijection $X\cong Y$.

= Ordinal
{parent=Set theory}
{wiki}

An ordinal is a transitive set well-ordered by membership and represents the order type of a well-order.

= Ordinal number
{synonym}

= Successor ordinal
{parent=Ordinal}
{wiki=Successor_ordinal}

The successor of an ordinal $\alpha$ is $\alpha+1=\alpha\cup\{\alpha\}$.

= Countable ordinal
{parent=Ordinal}
{wiki=Countable_ordinal}

A countable ordinal has a <countable set> as its underlying set.

= Order type
{parent=Ordinal}
{wiki}

The order type of a well-order is the unique ordinal isomorphic to it.

= Mostowski collapse theorem
{parent=Order type}
{c}
{wiki}

Every well-founded extensional relation is uniquely isomorphic to membership on a transitive set.

= Limit ordinal
{parent=Ordinal}
{wiki}

A nonzero ordinal is a limit ordinal when it is not a successor ordinal. Equivalently, it is the supremum of all smaller ordinals.

= Transfinite recursion
{parent=Ordinal}
{wiki}

Transfinite recursion defines a value at each ordinal from the function of all earlier values.

= Transfinite induction
{parent=Ordinal}
{wiki}

If a property of an ordinal follows whenever it holds for every smaller ordinal, then it holds for every ordinal.

= Ordinal addition
{title2=$\alpha+\beta$}
{parent=Ordinal}
{wiki}

Ordinal addition is ordered concatenation and is associative but generally not commutative.

= Associativity of ordinal addition
{parent=Ordinal addition}

For all ordinals $\alpha,\beta,\gamma$,
$$
(\alpha+\beta)+\gamma=\alpha+(\beta+\gamma).
$$
This follows by <transfinite induction> on $\gamma$ from the recursive definition of <ordinal addition>.

= Commuting ordinal addition
{parent=Ordinal addition}

Nonzero ordinals commute under addition precisely when they are positive finite right multiples of a common ordinal. This follows by comparing their <Cantor normal form>[Cantor normal forms] at the first exponent where they differ.

= Ordinal multiplication
{title2=$\alpha\beta$}
{parent=Ordinal}
{wiki}

Ordinal multiplication is defined recursively by
$$
\alpha0=0,
\qquad
\alpha(\beta+1)=\alpha\beta+\alpha,
\qquad
\alpha\lambda=\sup_{\xi<\lambda}\alpha\xi
$$
for nonzero <limit ordinal> $\lambda$. It is associative and left-distributive over <ordinal addition>, but generally neither commutative nor right-distributive.

= Ordinal exponentiation
{title2=$\alpha^\beta$}
{parent=Ordinal}
{wiki}

Ordinal exponentiation is defined recursively by
$$
\alpha^0=1,\qquad
\alpha^{\beta+1}=\alpha^\beta\alpha,\qquad
\alpha^\lambda=\sup_{\xi<\lambda}\alpha^\xi
$$
for nonzero limit $\lambda$. Transfinite induction gives
$$
\alpha^{\beta+\gamma}=\alpha^\beta\alpha^\gamma.
$$

= Derived-set iteration of a well-order
{parent=Ordinal}

For a well-ordered set $X$, let $X'$ contain the points whose strict initial segments are nonempty and have no greatest element, and iterate this operation transfinitely, taking intersections at limit stages. Every nonempty derivative loses at least its least element. If no derivative became empty, choosing one point from each successive difference would inject the ordinal supplied by <Hartogs theorem> for $X$ into $X$, a contradiction.

= Derived sets of an ordinal
{parent=Derived-set iteration of a well-order}

For an ordinal $\xi$,
$$
\xi'=\{\omega\beta<\xi:\beta>0\},
\qquad
\xi''=\{\omega^2\beta<\xi:\beta>0\}.
$$
Thus the derivative index of $\omega$ is one and that of $\omega^2$ is two.

= Ordinal interval
{parent=Ordinal}

For $\alpha<\beta$, the ordinal interval $\beta\setminus\alpha$ is the ordered tail from $\alpha$ inclusive to $\beta$ exclusive.

= First uncountable ordinal
{parent=Ordinal}
{wiki}

The first uncountable ordinal $\omega_1$ is the set of all countable ordinals.

= Tail of the first uncountable ordinal
{parent=First uncountable ordinal}

Deleting any countable initial segment from $\omega_1$ leaves a well-order of type $\omega_1$.

= Cantor normal form
{parent=Ordinal}
{c}
{wiki}

Every nonzero ordinal has a unique finite expression $\omega^{\delta_1}n_1+\cdots+\omega^{\delta_r}n_r$ with decreasing exponents and positive finite coefficients.

= Leading term of an ordinal
{parent=Cantor normal form}

The leading term $\omega^\delta n$ is the highest-exponent term in Cantor normal form; the remaining tail is strictly below $\omega^\delta$.

= Greatest power of omega below an ordinal
{parent=Leading term of an ordinal}

Every nonzero ordinal $\alpha$ has a greatest exponent $\beta$ such that $\omega^\beta\leq\alpha$. It is the leading exponent in the <Cantor normal form> of $\alpha$, and
$$
\alpha=\omega^\beta n+\gamma
$$
for a positive finite integer $n$ and $\gamma<\omega^\beta$.

= Leading exponent of an ordinal product
{parent=Leading term of an ordinal}

Let nonzero ordinals $\xi,\eta$ have leading exponents $\rho,\sigma$. If $\eta$ is finite, then $\xi\eta$ has leading exponent $\rho$. If $\eta$ is infinite, so that $\sigma>0$, then $\xi\eta$ has leading exponent $\rho+\sigma$. This follows by multiplying the leading terms in <Cantor normal form> and using continuity of <ordinal multiplication> at limit ordinals.

= Indecomposable ordinal
{parent=Ordinal}
{wiki=Indecomposable_ordinal}

The additively indecomposable ordinals are exactly the powers $\omega^\delta$.

= Additively closed ordinal
{parent=Indecomposable ordinal}

A nonzero ordinal $\delta$ is additively closed when $\beta+\gamma<\delta$ for all $\beta,\gamma<\delta$. These are exactly the ordinals $\omega^\alpha$: sufficiency follows from <Cantor normal form>, while necessity follows by splitting any leading coefficient or nonzero tail below $\delta$ into two smaller summands.

= Additively closed ordinals
{synonym}

= Additively indecomposable ordinal
{synonym}

= Division by an additively indecomposable ordinal
{parent=Indecomposable ordinal}

For every ordinal $\gamma$ and $\lambda=\omega^\alpha$, there are unique ordinals $\beta,\delta$ such that
$$
\gamma=\lambda\beta+\delta,
\qquad \delta<\lambda.
$$
Choose the greatest initial multiple $\lambda\beta\leq\gamma$; if its remainder were at least $\lambda$, the next multiple would still fit. Uniqueness follows because every remainder below $\lambda$ lies before $\lambda(\beta+1)$.

= Multiplicatively closed ordinal
{parent=Indecomposable ordinal}

An ordinal $\delta>2$ is multiplicatively closed when $\beta\gamma<\delta$ for all $\beta,\gamma<\delta$. These are exactly
$$
\delta=\omega^{\omega^\alpha}.
$$

= Multiplicatively closed ordinals
{synonym}

= Multiplicatively indecomposable ordinal
{synonym}

= Multiplicative closure criterion for a power of omega
{parent=Multiplicatively closed ordinal}

For nonzero $\lambda$, the ordinal $\omega^\lambda$ is <multiplicatively closed ordinal>[multiplicatively closed] exactly when $\lambda$ is <additively closed ordinal>[additively closed]. One direction follows from
$$
\omega^\rho\omega^\sigma=\omega^{\rho+\sigma}.
$$
For the other, the <leading exponent of an ordinal product> shows that products of ordinals below $\omega^\lambda$ still have leading exponent below $\lambda$.

= Hessenberg natural sum
{parent=Ordinal}
{c}
{wiki=Natural_operations}

The Hessenberg natural sum aligns equal exponents in two Cantor normal forms and adds their finite coefficients; unlike ordinal addition it is commutative.

= Shuffle bound for ordinal partitions
{parent=Hessenberg natural sum}

If a well-order is the union of suborders of types $\xi$ and $\eta$, its type is at most $\xi\mathbin\#\eta$.

= Ordinal partition bound
{parent=Shuffle bound for ordinal partitions}

If an ordinal is partitioned into two copies of type $\beta$, its type is below $\beta+\beta+\beta$; two copies do not always give a strict bound.

= Mathematical logic
{parent=Foundations of mathematics}
{wiki}

Mathematical logic studies formal languages, proofs, models, computability, and the foundations of mathematics.

= Propositional logic
{parent=Mathematical logic}
{wiki}

= Soundness theorem for propositional logic
{parent=Propositional logic}
{wiki=Soundness}

If $\Gamma\vdash t$, every valuation that satisfies all formulae in $\Gamma$ also satisfies $t$.

= Deductively closed set of formulae
{title2=$S=\operatorname{Cn}(S)$}
{parent=Propositional logic}

A set $S$ of formulae is deductively closed when
$$
S\vdash\varphi\quad\Longrightarrow\quad\varphi\in S.
$$
Equivalently, $S$ equals its deductive closure $\operatorname{Cn}(S)$.

= Consistent set of formulae
{parent=Propositional logic}

A set $S$ is syntactically consistent when $S\not\vdash\bot$. Equivalently in classical logic, there is no formula $\varphi$ for which both $S\vdash\varphi$ and $S\vdash\neg\varphi$.

= Finitary set of formulae
{parent=Propositional logic}

A set $S$ is finitary when it is deductively equivalent to some finite set $F$: both $S\vdash F$ and $F\vdash S$.

= Increasing union of deductively closed sets
{parent=Propositional logic}

If
$$
T_0\subsetneq T_1\subsetneq T_2\subsetneq\cdots
$$
are deductively closed, then each $T_i$ is consistent and their union is consistent and deductively closed. The union is not finitary. Each conclusion follows from the <finite character of formal proofs>.

= Maximal consistent set in propositional logic
{parent=Propositional logic}

A consistent set $T$ is maximal consistent when no proper extension is consistent. It is deductively closed and decides every formula: exactly one of $t$ and $\neg t$ belongs to $T$. Therefore $v(t)=1$ exactly when $t\in T$ defines a model of $T$.

= Propositional compactness theorem
{parent=Propositional logic}
{wiki=Compactness_theorem}

A set of propositions has a model exactly when every finite subset has a model. Syntactically, a contradiction uses only finitely many assumptions, and every consistent set extends by <Zorn lemma> to a <maximal consistent set in propositional logic>.

= Compactness obstruction to expressing totality over an infinite codomain
{parent=Propositional compactness theorem}

With atoms $p_{x,y}$, finitary propositions can enforce that the true pairs form an injective partial function. If the codomain is infinite, they cannot enforce that every $x$ has a value: adjoining every $\neg p_{x_0,y}$ remains finitely satisfiable, so compactness produces a model omitting $x_0$.

= First-order logic
{parent=Mathematical logic}
{wiki}

First-order logic permits quantification over elements of a structure while its nonlogical symbols describe operations, constants, and relations.

= First-order language
{parent=First-order logic}
{wiki=Signature_(logic)}

A first-order language specifies its constant, operation, and relation symbols, together with the arity of each nonconstant symbol.

= Finite language support
{parent=First-order language}

A finite set of formulas mentions only finitely many nonlogical symbols. This observation lets compactness reduce arguments in a language indexed by a large set to a finite sublanguage.

= Free variable
{parent=First-order logic}
{wiki=Free_variables_and_bound_variables}

An occurrence of a variable is free when it is outside the scope of a quantifier binding that variable.

= First-order sentence
{parent=First-order logic}
{wiki=Sentence_(mathematical_logic)}

A first-order sentence is a formula with no free variables, so its truth in a structure is independent of a variable assignment.

= First-order theory
{parent=First-order logic}
{wiki=Theory_(mathematical_logic)}

A first-order theory is a set of sentences in one first-order language. Depending on convention, the term may instead mean its deductive closure.

= First-order axiomatizable class
{parent=First-order theory}

A class of structures is first-order axiomatizable when it is exactly the class of models of some first-order theory. If extra constants are allowed, the corresponding class of reducts consists of structures that admit interpretations of those constants satisfying the theory.

= Axiomatisable
{synonym}

= Consistent first-order theory
{parent=First-order theory}
{wiki=Consistency}

A theory is consistent when it does not derive a contradiction. By first-order completeness, this is equivalent to having a model.

= Monotonicity of inconsistency
{parent=Consistent first-order theory}

Every theory containing an inconsistent subtheory is inconsistent, because the same finite derivation of contradiction remains available.

= Finite character of formal proofs
{parent=First-order theory}

Every formal proof is a finite string and therefore uses only finitely many of the available assumptions.

= Universal first-order theory
{parent=First-order theory}
{wiki=Universal_theory}

A universal theory can be axiomatized by sentences whose quantifiers are all universal. Such sentences often forbid specified finite configurations.

= Finite forbidden-pattern axiomatization
{parent=Universal first-order theory}

If failure of a property has a finite witness, one can often axiomatize the property by a universal sentence forbidding each possible finite witness. Compactness supplies finite witnesses when failure is expressed by inconsistency of an associated theory.

= First-order structure
{parent=First-order logic}
{wiki=Structure_(mathematical_logic)}

A structure supplies a nonempty domain and an interpretation of every constant, operation, and relation symbol in its language.

= Model of a first-order theory
{parent=First-order structure}
{wiki=Model_theory}

A structure $M$ is a model of $T$ when $M\models\sigma$ for every sentence $\sigma\in T$.

= Automorphism of a first-order structure
{parent=First-order structure}
{wiki=Automorphism}

An automorphism is a bijection from a structure to itself that preserves every operation and relation in its language.

= First-order axiomatization of an automorphism
{parent=Automorphism of a first-order structure}

After adjoining a unary function symbol $f$, injectivity, surjectivity, preservation of each operation, and preservation in both directions of each relation form an axiom scheme whose models interpret $f$ as an automorphism.

= Faithful automorphism action
{parent=Automorphism of a first-order structure}

A family $(f_g)_{g\in G}$ of automorphisms satisfying $f_gf_h=f_{gh}$ defines a group action. It is faithful exactly when distinct indices define distinct automorphisms, equivalently when $G$ embeds in the automorphism group.

= Rigid first-order structure
{parent=Automorphism of a first-order structure}
{wiki=Rigid_structure}

A first-order structure is rigid when its identity map is its only automorphism. Every finite linear order is rigid, whereas $(\mathbb Z,<)$ is nonrigid because every translation is an order automorphism.

= Compactness transfer of finite nonrigidity
{parent=Rigid first-order structure}

If a theory has arbitrarily large finite nonrigid models, expand its language by a unary function $f$, axiomatize that $f$ is an automorphism, require $f$ to move some element, and add sentences demanding at least $n$ elements for every $n$. Every finite fragment has a sufficiently large finite nonrigid model, so compactness supplies an infinite nonrigid model.

= Soundness theorem for first-order logic
{parent=First-order logic}
{wiki=Soundness}

Every sentence derivable from a first-order theory is true in every model of that theory.

= Godel completeness theorem
{parent=First-order logic}
{c}
{wiki=G%C3%B6del%27s_completeness_theorem}

For first-order logic, every sentence true in every model of a theory is derivable from that theory. Equivalently, every consistent theory has a model.

= Compactness theorem
{parent=First-order logic}
{wiki=Compactness_theorem}

A set of first-order sentences has a model if and only if every finite subset has a model.

= Syntactic proof of first-order compactness
{parent=Compactness theorem}

If a theory were inconsistent, a proof of contradiction would use a finite inconsistent subset. Therefore consistency of every finite subset implies consistency of the whole theory, and completeness supplies a model.

= Compactness obstruction to axiomatizing finitely many maximal elements
{parent=Compactness theorem}

If a theory claimed that a poset has only finitely many maximal elements, adjoining countably many constants required to be distinct and maximal would remain finitely satisfiable. Compactness would produce a model with infinitely many maximal elements, contradicting the claimed axiomatization.

= Compactness obstruction to an exclusive disjunction of infinitude
{parent=Compactness theorem}

Suppose a class requires exactly one of two definable sets to be infinite. Add constants witnessing arbitrarily many distinct members of both sets. Every finite fragment can keep one set infinite and make the other large but finite, whereas compactness makes both sets infinite. Therefore such an exclusive disjunction is not first-order axiomatizable.

= Lowenheim-Skolem theorem
{parent=First-order logic}
{c}
{wiki=L%C3%B6wenheim%E2%80%93Skolem_theorem}

The Löwenheim--Skolem theorems control the cardinalities of models of a first-order theory without changing its first-order truths.

= Upward Lowenheim-Skolem theorem
{parent=Lowenheim-Skolem theorem}
{c}

If an $L$-theory has an infinite model, then it has models of arbitrarily large cardinality. For a cardinal $\kappa$, add constants $c_\alpha$ for $\alpha<\kappa$ and all inequalities $c_\alpha\ne c_\beta$. Every finite fragment is satisfiable in the given infinite model, so compactness gives a model with at least $\kappa$ elements. Applying the downward theorem produces a model of exactly $\kappa$ when $\kappa\geq|L|+\aleph_0$.

= Downward Lowenheim-Skolem theorem
{parent=Lowenheim-Skolem theorem}
{c}

If $A$ is an infinite $L$-structure and $|L|+\aleph_0\leq\kappa\leq|A|$, then $A$ has an elementary substructure of cardinality $\kappa$. One proof adds Skolem functions for existential formulas and closes a chosen $\kappa$-element subset under them; the closure still has size $\kappa$, and the Tarski--Vaught test makes it elementary.

= Computability theory
{parent=Foundations of mathematics}
{wiki}

= Register machine
{parent=Computability theory}
{wiki}

A register machine has finitely many states and finitely many addressed registers, together with instructions that inspect and modify register contents and change state. A computed partial function is defined by the contents at the halt state.

= String register machine
{parent=Register machine}

In a string register machine, $+_a(k,q)$ appends $a$ to register $k$; $?_a(k,p,q)$ branches according to whether its final letter is $a$; $?_\varepsilon(k,p,q)$ tests emptiness; and $-(k,p,q)$ branches to $p$ when empty, or deletes the final letter and branches to $q$ otherwise.

= Characteristic-function register machine
{parent=String register machine}

A machine computes the characteristic function of a language $X$ when it halts on every input with the one-letter output $1$ for inputs in $X$ and $0$ for inputs outside $X$.

= One-register separation for equal block lengths
{parent=Characteristic-function register machine}

Two string registers can recognize $\{a^nb^n:n>0\}$ by storing one marker per $a$ and removing one per $b$. A machine with only its input register cannot: two different terminal $b$-block lengths eventually reach the same state and remaining prefix, forcing equal outputs for one member and one nonmember.

= String register-machine suffix test
{parent=Characteristic-function register machine}

To recognize words ending in a fixed symbol $a$, test the final input letter, choose one of two erasing loops, and append $1$ after the accepting loop or $0$ after the rejecting loop. The empty word follows the rejecting branch.

= Complementing a characteristic-function register machine
{parent=Characteristic-function register machine}

Replace the original halt state by a continuation state that tests whether its one-letter output is $0$ or $1$, removes it, appends the other symbol, and enters a new halt state. This computes the complement language without changing termination behavior.

= Primitive recursive function
{parent=Computability theory}
{wiki}

Primitive recursive functions are generated by zero, successor, and projections under composition and primitive recursion.

= Initial function of recursion theory
{parent=Primitive recursive function}

The initial functions are the zero function, the successor function, and all coordinate projections.

= Zero function
{title2=$Z$}
{parent=Initial function of recursion theory}

The zero function has the constant value
$$
Z(x)=0.
$$
Dummy variables give a zero function of any finite arity.

= Successor function
{title2=$S$}
{parent=Initial function of recursion theory}

The successor function is
$$
S(n)=n+1.
$$

= Projection function
{title2=$\pi_i^k$}
{parent=Initial function of recursion theory}

The $i$th $k$-ary projection returns its $i$th input:
$$
\pi_i^k(x_1,\ldots,x_k)=x_i.
$$

= Function composition in recursion theory
{parent=Primitive recursive function}

Given a $m$-ary function $g$ and $k$-ary functions $h_1,\ldots,h_m$, composition forms
$$
f(\mathbf x)=g(h_1(\mathbf x),\ldots,h_m(\mathbf x)).
$$

= Primitive recursion
{parent=Primitive recursive function}
{wiki}

From $g:\mathbb N^k\to\mathbb N$ and $h:\mathbb N^{k+2}\to\mathbb N$, primitive recursion defines
$$
f(\mathbf x,0)=g(\mathbf x),
\qquad
f(\mathbf x,n+1)=h(\mathbf x,n,f(\mathbf x,n)).
$$

= Composition-only recursive function
{parent=Primitive recursive function}

The functions generated from the initial functions using composition alone are exactly
$$
f(\mathbf x)=c
\quad\hbox{or}\quad
f(\mathbf x)=x_i+c
$$
for a constant $c\in\mathbb N$. Structural induction proves necessity, and iterating the successor function on zero or a projection proves sufficiency.

= Diagonal argument
{parent=Computability theory}
{wiki}

A list $f(n,k)$ of all functions in a class closed under diagonal substitution and successor misses $d(k)=f(k,k)+1$.

= Recursively enumerable set
{parent=Computability theory}
{wiki=Computably_enumerable_set}

A set is computably enumerable when a program halts precisely on its members. Equivalently, it is the domain of a <partial computable function> or some algorithm lists its elements.

= Computably enumerable set
{synonym}

= Domain and range characterizations of a nonempty computably enumerable set
{parent=Recursively enumerable set}

For a nonempty set $A$ of words, the following are equivalent: $A$ is <computably enumerable set>[computably enumerable], $A$ is the domain of a <partial computable function>, $A$ is the range of a partial computable function, and $A$ is the range of a <total computable function>. The nonempty hypothesis is needed only for the last formulation, since the range of a total function cannot be empty.

= Recursion theorem
{parent=Computability theory}
{wiki=Kleene%27s_recursion_theorem}

Kleene recursion gives programs access to their own effective descriptions: every computable transformation of program indices has a semantic fixed point.

= Many-one reduction
{parent=Computability theory}
{wiki=Many-one_reduction}

A many-one reduction $A\leq_mB$ is a total computable $f$ satisfying $x\in A$ exactly when $f(x)\in B$.

= Many-one degree
{parent=Many-one reduction}
{wiki=Many-one_reduction\#Many-one_equivalence}

Two sets have the same many-one degree when each many-one reduces to the other.

= Computable reduction by staged enumeration
{parent=Many-one reduction}

A staged-enumeration reduction controls an output language by enumerating more elements at each simulation stage and changing behavior when a source computation halts.

= Many-one complete set
{parent=Many-one reduction}

A set $A$ is complete for a class $\mathcal C$ under many-one reductions when $A\in\mathcal C$ and every $B\in\mathcal C$ satisfies $B\leq_mA$.

= Index set
{parent=Computability theory}
{wiki=Index_set_(recursion_theory)}

An index set is a set of program codes whose membership depends only on the partial function or enumerable language computed, rather than the code's syntax.

= Extensional property of programs
{parent=Index set}

An extensional program property gives identical answers to all codes computing the same object.

= Rice theorem
{parent=Index set}
{c}
{wiki=Rice%27s_theorem}

Every nontrivial extensional property of partial computable functions or computably enumerable languages is undecidable.

= Infinite-domain index set
{parent=Index set}

For an effective enumeration $f_{w,1}$ of unary partial computable functions,
$$
\mathbf{Inf}=\{w:\operatorname{dom}(f_{w,1})\text{ is infinite}\}
$$
is an index set.

= Infinite-domain range-restriction index set
{parent=Infinite-domain index set}

For a nonempty set $X$ of words, the property
$$
w\in\mathbf{Inf}
\quad\hbox{and}\quad
\operatorname{ran}(f_{w,1})\subseteq X
$$
is a nontrivial extensional property of unary partial computable functions: the nowhere-defined function fails it, while any total constant function with value in $X$ satisfies it. The <Rice theorem> therefore makes its index set undecidable.

= Cofinite index set
{parent=Index set}

The cofinite index set contains codes whose enumerable language has finite complement.

= Padding lemma
{parent=Computability theory}
{wiki=Padding_lemma_(computability_theory)}

The padding lemma produces infinitely many syntactically distinct program indices for the same computed function or language.

= Dovetailing
{parent=Computability theory}
{wiki=Dovetailing_(computer_science)}

Dovetailing interleaves finite stages of multiple computations so that every computation that halts is eventually observed.

= S-m-n theorem
{parent=Computability theory}
{c}
{wiki=Smn_theorem}

The S-m-n theorem says that fixed inputs can be compiled into program codes by a total computable transformation. For every $m,n\geq1$, there is a total computable $s_n^m$ such that
$$
f_{s_n^m(e,x_1,\ldots,x_m),n}(y_1,\ldots,y_n)
=f_{e,m+n}(x_1,\ldots,x_m,y_1,\ldots,y_n)
$$
whenever either side is defined.

= Partial computable function
{parent=Computability theory}
{wiki=Partial_recursive_function}

A partial function is computable when a program returns its value on every input in its domain and runs forever on inputs outside its domain.

= Partial recursive function
{synonym}

= Unbounded minimization
{title2=$\mu$}
{parent=Partial computable function}
{wiki=Mu_operator}

For a partial function $g(\mathbf x,y)$, unbounded minimization defines
$$
f(\mathbf x)=\mu y\,[g(\mathbf x,y)=0]
$$
as the least $y$ at which $g$ is zero, provided the preceding required computations are defined. If no such $y$ is found, $f(\mathbf x)$ is undefined. Closing the <primitive recursive function>[primitive recursive functions] under this operation gives the partial recursive functions.

= Total computable function
{parent=Partial computable function}
{wiki=Computable_function}

A total computable function is a computable function whose domain contains every allowed input.

= Truncated computation function
{parent=Partial computable function}

For a program code $e$, input $x$, and time bound $t$, the truncated computation simulates program $e$ on $x$ for at most $t$ steps and reports either its output or that no halt occurred within the bound. This is a total computable function of $(e,x,t)$.

= Arithmetical hierarchy
{parent=Computability theory}
{wiki}

The arithmetical hierarchy classifies sets by alternating blocks of number quantifiers over computable predicates.

= Sigma-1 set
{parent=Arithmetical hierarchy}
{c}
{wiki=Arithmetical_hierarchy}

A set $A$ is in $\Sigma_1$ exactly when it is the domain of a partial computable function. Equivalently, there is a computable predicate $R$ such that
$$
x\in A\quad\Longleftrightarrow\quad\exists t\,R(x,t).
$$

= Pi-2 set
{parent=Arithmetical hierarchy}
{c}
{wiki=Arithmetical_hierarchy}

A set is in $\Pi_2$ when membership can be written with one universal block followed by one existential block over a computable predicate. Equivalently, in the word-function formulation, there is a partial computable $f$ such that
$$
w\in P\quad\Longleftrightarrow\quad
\forall v\;f(w,v)\mathbin\downarrow.
$$

= Totality problem
{parent=Pi-2 set}

For an effective enumeration of computably enumerable languages $W_v$, the totality problem is
$$
\mathbf{Tot}=\{v:W_v=\mathbb W\}.
$$
It is $\Pi_2$-complete: a $\Pi_2$ condition $w\in P\iff\forall x\,f(w,x)\downarrow$ maps effectively to a program whose domain is $\{x:f(w,x)\downarrow\}$.

= Formal language theory
{parent=Foundations of mathematics}
{wiki=Formal_language}

= Regular expression
{parent=Formal language theory}
{wiki}

A regular expression is built from alphabet symbols, the empty language and the empty word using finite union, concatenation and Kleene star.

= Kleene theorem
{c}
{parent=Regular expression}
{wiki=Kleene%27s_theorem}

Kleene's theorem states that a language is denoted by a regular expression exactly when it is accepted by a finite automaton.

= Formal grammar
{parent=Formal language theory}
{wiki}

A grammar $(N,\Sigma,P,S)$ generates the terminal words reachable from $S$ by finitely many productions.

= Variable-based grammar
{parent=Formal grammar}

A variable-based grammar has disjoint finite terminal and variable alphabets $\Sigma,V$, a start variable $S\in V$, and productions $\alpha\to\beta$ in which $\alpha,\beta\in(\Sigma\cup V)^*$ and $\alpha$ contains at least one variable.

= Unreachable nonterminal
{parent=Variable-based grammar}

A nonterminal is unreachable when no word derivable from the start symbol contains it. Productions whose left sides are unreachable do not affect the generated <formal language theory>[language].

= Nonproductive nonterminal
{parent=Variable-based grammar}

A nonterminal is nonproductive when no word derived from it consists entirely of terminal symbols. Every derivation containing such a symbol therefore fails to produce a word in the generated <formal language theory>[language].

= Regular grammar
{parent=Variable-based grammar}
{wiki}

A right-linear regular grammar has productions of the forms $A\to wB$ and $A\to w$, where $A,B$ are variables and $w$ is a terminal word.

= Sentential form of a right-linear regular grammar
{parent=Regular grammar}

Every sentential form reachable from the start variable of a right-linear grammar is either a terminal word $w$ or $wA$, where $A$ is the unique variable and occurs at the right end.

= Accessible variable of a regular grammar
{parent=Regular grammar}

A variable $A$ is accessible when $S\Rightarrow^*wA$ for some terminal word $w$.

= Looping variable of a regular grammar
{parent=Regular grammar}

A variable $A$ is looping when $A\Rightarrow^*wA$ for some terminal word $w$ through a nonempty derivation.

= Terminable variable of a regular grammar
{parent=Regular grammar}

A variable $A$ is terminable when $A\Rightarrow^*w$ for some terminal word $w$.

= Accessible looping terminable variable criterion
{parent=Regular grammar}

If a finite right-linear grammar generates an infinite language, some variable is accessible, looping, and terminable. It is the repeated variable on a sufficiently long accepting derivation.

= Concatenation grammar
{parent=Variable-based grammar}

For grammars $G=(\Sigma,V,P,S)$ and $G'=(\Sigma,V',P',S')$ with disjoint variable sets, introduce a new variable $S_0$ and set
$$
H=(\Sigma,V\cup V'\cup\{S_0\},
P\cup P'\cup\{S_0\to SS'\},S_0).
$$
If both input grammars are variable based, then $L(H)=L(G)L(G')$.

= Regular concatenation grammar
{parent=Concatenation grammar}

Retain every production $\alpha\to\beta$ of $P$ whose right-hand side contains a variable, replace every production $\alpha\to w$ with $w\in\Sigma^*$ by $\alpha\to wS'$, include $P'$, and use $S$ as start variable. If $G$ and $G'$ are right-linear, the resulting grammar is right-linear and generates $L(G)L(G')$.

= Failure of the regular concatenation construction for a nonregular grammar
{parent=Regular concatenation grammar}

The regular construction relies on a regular derivation having exactly one terminal rule, at its end. In a general variable-based grammar several variables may each use terminal productions, so replacing every such production can introduce several copies of the second start variable.

= Concatenation grammar need not be regular
{parent=Concatenation grammar}

Even if both input grammars are regular, the added production $S_0\to SS'$ has two variables on its right-hand side and therefore need not be a regular production.

= Context-free language
{parent=Formal language theory}
{wiki}

A grammar is context-free when each production has one nonterminal on its left.

= Context-free grammar
{parent=Context-free language}
{wiki}

A context-free grammar consists of terminal and nonterminal alphabets, a start symbol, and productions whose left side is one nonterminal. A derivation records the order of substitutions, while a parse tree records their hierarchical structure, so several derivations can represent one parse tree.

= Grammar derivation
{parent=Context-free grammar}

A grammar derivation is a finite sequence of words in which each step replaces one occurrence of a production's left side by its right side. A leftmost derivation always replaces the leftmost available nonterminal.

= Parse tree
{parent=Context-free grammar}
{wiki}

A parse tree places the start symbol at its root, the symbols on the right side of a production at the children of its left-side nonterminal, and terminal symbols at its leaves. Reading the leaves from left to right gives the tree's yield.

= Equivalent grammar
{parent=Context-free grammar}

Two grammars are equivalent when they generate the same formal language.

= Isomorphic grammar
{parent=Equivalent grammar}

Two grammars over a common terminal alphabet are isomorphic when a bijection between their nonterminal alphabets maps one start symbol to the other and maps their productions bijectively after being extended to fix every terminal symbol. Isomorphic grammars are <equivalent grammar>[equivalent].

= Chomsky normal form
{parent=Context-free grammar}
{c}
{wiki}

A context-free grammar is in Chomsky normal form when every production has the form $A\to BC$ or $A\to a$, with $A,B,C$ nonterminals and $a$ a terminal. If the empty word belongs to the language, one commonly also permits the exceptional rule $S\to\epsilon$ under the usual restriction on the start symbol.

= Epsilon production
{title2=$A\to\epsilon$}
{parent=Chomsky normal form}
{wiki=Context-free_grammar#Production_rule_types}

An epsilon production is a grammar production whose right-hand side is the empty word.

= Unit production
{title2=$A\to B$}
{parent=Chomsky normal form}
{wiki=Unit_production}

A unit production replaces one nonterminal by one nonterminal and emits no terminal symbols.

= Chomsky-normal-form derivation length
{parent=Chomsky normal form}
{c}

A Chomsky-normal-form parse tree for a word of length $n\geq1$ has $n$ terminal productions and $n-1$ binary productions. Every derivation represented by the tree therefore has exactly $2n-1$ steps.

= Weak Chomsky normal form
{parent=Chomsky normal form}
{c}

Weak Chomsky normal form additionally permits ternary productions $A\to BCD$. Compressing a two-step pattern $A\to BE$, $E\to CD$ into $A\to BCD$ preserves its generated yields whenever the intermediate variable has no other role, and saves one derivation step each time the pattern is used.

= Context-free grammar for even palindromes
{parent=Context-free language}

The productions $S\to0S0\mid1S1\mid00\mid11$ generate exactly the nonempty binary palindromes of even length.

= Closure of context-free languages under regular intersection
{parent=Context-free language}
{wiki=Context-free_language\#Closure_properties}

The intersection of a context-free language with a regular language is context-free, because a pushdown automaton and a finite automaton can be run in product.

= Nested-count context-free grammar
{parent=Context-free language}

A context-free grammar can enforce sums such as $0^n1^m0^{n+m}$ by nesting one matched terminal pair for each independent count.

= Pumping lemma for context-free languages
{parent=Formal language theory}
{wiki}

For some $p$, every sufficiently long $w$ in a context-free language has $w=uvxyz$ with $|vxy|\le p$, $|vy|>0$, and $uv^ixy^iz$ in the language for all $i\ge0$.

= Three-block context-free pumping obstruction
{parent=Pumping lemma for context-free languages}

For a word consisting of three long constrained blocks, a pumpable window shorter than each block cannot alter both outer blocks; pumping then breaks a required three-way count relation.

= Deterministic finite automaton
{parent=Formal language theory}
{wiki}

A deterministic finite automaton has finitely many states and one transition for each state-symbol pair.

= Extended transition function of a deterministic finite automaton
{title2=$\widehat\delta$}
{parent=Deterministic finite automaton}

For a transition function $\delta:Q\times\Sigma\to Q$, define
$$
\widehat\delta(q,\varepsilon)=q,
\qquad
\widehat\delta(q,wa)=\delta(\widehat\delta(q,w),a).
$$
The accepted language is $\{w:\widehat\delta(q_0,w)\in F\}$.

= Accessible state of a deterministic finite automaton
{parent=Deterministic finite automaton}

A state is accessible when some input word takes the initial state to it. Removing inaccessible states preserves the accepted language.

= Indistinguishable states of a deterministic finite automaton
{parent=Deterministic finite automaton}

Two states are indistinguishable when every continuation is accepted from both or rejected from both. Distinguishable states admit at least one suffix with different acceptance outcomes.

= Quotient deterministic finite automaton by indistinguishable states
{parent=Indistinguishable states of a deterministic finite automaton}

Indistinguishability is a right-invariant equivalence relation. The quotient has states $[q]$, transition $[q]\mapsto[\delta(q,a)]$, initial state $[q_0]$, and accepting classes represented by accepting states. It accepts the original language and has no two distinct indistinguishable states.

= Irreducible deterministic finite automaton
{parent=Deterministic finite automaton}

A deterministic automaton is irreducible when every state is accessible and every pair of distinct states is distinguishable.

= Minimal deterministic finite automaton
{parent=Irreducible deterministic finite automaton}
{wiki=DFA_minimization}

An irreducible deterministic automaton has the fewest states among deterministic automata for its language and is unique up to isomorphism. Its states are the Myhill--Nerode classes.

= Accessible unary deterministic finite automaton
{parent=Minimal deterministic finite automaton}

An accessible automaton over one letter consists of a directed tail entering one directed cycle. Its minimal quotient is obtained by merging positions having the same future binary acceptance sequence.

= Nondeterministic finite automaton
{parent=Formal language theory}
{wiki=Nondeterministic_finite_automaton}

A nondeterministic finite automaton assigns a set of possible successor states to each state-symbol pair and accepts when at least one run ends in a final state.

= Extended transition of a nondeterministic finite automaton
{parent=Nondeterministic finite automaton}

Without epsilon transitions, define
$$
\widehat\Delta(q,\varepsilon)=\{q\},\qquad
\widehat\Delta(q,wa)=
\bigcup_{p\in\widehat\Delta(q,w)}\Delta(p,a).
$$
A word is accepted when the set reached from the initial state meets the final set.

= Witnessing sequence for a nondeterministic automaton
{parent=Extended transition of a nondeterministic finite automaton}

For $w=a_0\cdots a_{n-1}$, a witnessing sequence from $p_0$ to $p_n$ satisfies $p_{i+1}\in\Delta(p_i,a_i)$. Induction on word length shows that $q'\in\widehat\Delta(q,w)$ exactly when such a sequence runs from $q$ to $q'$.

= Powerset construction
{parent=Nondeterministic finite automaton}
{wiki=Powerset_construction}

The powerset construction turns an NFA with state set $Q$ into a DFA with state set $\mathcal P(Q)$, transition
$$\delta_D(S,a)=\bigcup_{q\in S}\Delta(q,a),$$
and accepting subsets that meet the NFA final set.

= Brzozowski automaton
{parent=Nondeterministic finite automaton}
{c}

In the convention used here, a Brzozowski NFA has one final state, every state can reach it, and each word labels a path to it from exactly one starting state.

= Irreducibility of the accessible subset automaton
{parent=Brzozowski automaton}

For distinct accessible subset states, choose a state in their symmetric difference. A word taking it to the unique final state accepts from one subset; uniqueness of the starting state prevents acceptance from the other. Thus the accessible part of the subset automaton is irreducible.

= Regular language
{parent=Formal language theory}
{wiki}

A language is regular exactly when it is accepted by a finite automaton, or equivalently has finitely many Myhill-Nerode classes.

= Pumping lemma for regular languages
{parent=Formal language theory}
{wiki}

For a <deterministic finite automaton> with $N$ states, every accepted word $w$ with $|w|\geq N$ has a decomposition $w=xyz$ such that $|xy|\leq N$, $|y|\geq1$, and $xy^iz$ is accepted for every integer $i\geq0$.

= Myhill-Nerode theorem
{c}
{parent=Formal language theory}
{wiki=Myhill–Nerode_theorem}

A language is regular exactly when indistinguishability by all suffixes has finitely many equivalence classes; these classes form its minimal DFA.

= Myhill-Nerode equivalence
{parent=Myhill-Nerode theorem}
{c}

For a language $A\subseteq\Sigma^*$, define
$$
v\sim_Aw
\quad\Longleftrightarrow\quad
\forall u\in\Sigma^*,\
vu\in A\Longleftrightarrow wu\in A.
$$
This is a right congruence, and its equivalence classes are the states of the minimal <deterministic finite automaton> for $A$.

= Closure properties of formal languages
{parent=Formal language theory}
{wiki=Abstract_family_of_languages}

A language class is closed under an operation when applying that operation to members always produces another member of the class.

= Computably enumerable language
{parent=Formal language theory}
{wiki=Recursively_enumerable_language}

A language is computably enumerable when a machine recognizes its members, possibly running forever on nonmembers.

= Halting problem
{parent=Computably enumerable language}
{wiki}

The halting set is computably enumerable but undecidable, and its complement is not computably enumerable.

= Diagonal halting set
{title2=$K$}
{parent=Halting problem}

For an effective enumeration of unary partial computable functions, the diagonal halting set is
$$
K=\{e:f_{e,1}(e)\text{ is defined}\}.
$$
Equivalently, for an enumeration $W_e$ of computably enumerable sets, $K=\{e:e\in W_e\}$.

= Many-one completeness of the halting problem
{parent=Diagonal halting set}

Every <recursively enumerable set> many-one reduces to the <diagonal halting set>. If a program halts exactly on $X$, the <S-m-n theorem> produces from $x$ an index $g(x)$ for a unary program that ignores its input and performs that computation on $x$. Then
$$
x\in X\Longleftrightarrow g(x)\in K.
$$
Conversely, a computable preimage of a recursively enumerable set is recursively enumerable.

= Distinct representative of the halting many-one degree
{parent=Many-one completeness of the halting problem}

If $0\notin K$, then
$$
S=\{0\}\cup\{2n+1:n\in K\}
$$
differs from $K$, while the computable map $n\mapsto2n+1$ proves $K\leq_mS$.

= Graph theory
{parent=Foundations of mathematics}
{wiki}

= Binomial random graph
{title2=$G(n,p)$}
{parent=Graph theory}
{wiki=Erdős–Rényi_model}

The binomial random graph $G(n,p)$ has vertex set $\{1,\ldots,n\}$ and includes each of the $\binom n2$ possible edges independently with probability $p$.

= Clique count in a binomial random graph
{parent=Binomial random graph}

If $X_t$ counts copies of the <complete graph> $K_t$ in $G(n,p)$, then
$$
\mathbb EX_t=\binom ntp^{\binom t2}.
$$
Consequently $p n^{2/(t-1)}\to0$ implies $\mathbb P(X_t>0)\to0$ by the <first moment method>.

= Triangle count in a binomial random graph
{parent=Binomial random graph}

If $X$ counts triangles in $G(n,p)$, then
$$
\mathbb EX=\binom n3p^3
$$
and
$$
\operatorname{var}X
\leq\binom n3p^3
+2\binom n2\binom{n-2}2p^5.
$$
Thus $np\to\infty$ implies $\operatorname{var}X/(\mathbb EX)^2\to0$, and the <second moment method> gives $\mathbb P(X>0)\to1$.

= Triangle with an attached leaf in a binomial random graph
{parent=Binomial random graph}

Partition the vertices into two sets of comparable size. If $np\to\infty$, the first set contains a triangle with probability tending to one. Conditional on any triangle chosen using only internal edges, the probability that none of its vertices has a neighbour in the second set is at most
$$
(1-p)^{3\lfloor n/2\rfloor}
\leq e^{-3p\lfloor n/2\rfloor}\longrightarrow0.
$$
Hence $G(n,p)$ contains a triangle with an attached leaf with probability tending to one.

= Graph
{parent=Graph theory}
{wiki=Graph_(discrete_mathematics)}

A graph consists of <vertices of a graph>[vertices] joined by <edges>.

= Vertex of a graph
{parent=Graph}
{wiki=Vertex_(graph_theory)}

A vertex is one of the objects joined by the <edges> of a graph.

= Vertices of a graph
{synonym}

= Vertices
{synonym}

= Isomorphic graphs
{parent=Graph}
{wiki=Graph_isomorphism}

Two graphs are isomorphic when a <bijection> between their vertex sets preserves adjacency.

= Triangle in a graph
{parent=Graph}
{wiki=Cycle_graph}

A triangle is a set of three vertices joined by all three possible edges, equivalently a copy of $K_3$.

= Triangles in a graph
{synonym}

= Triangle-free graph
{parent=Triangle in a graph}
{wiki}

A triangle-free graph contains no <triangles in a graph>[triangle].

= Graph colouring
{parent=Graph theory}
{wiki=Graph_coloring}

A graph colouring assigns labels called colours to graph elements subject to specified constraints. A proper vertex colouring gives adjacent vertices different colours.

= Graph colourings
{synonym}

= Chromatic number
{parent=Graph colouring}
{wiki}

The chromatic number $\chi(G)$ is the least number of colours in a proper vertex colouring of $G$.

= Brooks' theorem
{c}
{parent=Chromatic number}
{wiki}

A connected graph of maximum degree $\Delta$ has chromatic number at most $\Delta$ unless it is a complete graph or an odd cycle.

= Edge chromatic number
{title2=$\chi'(G)$}
{parent=Graph colouring}
{wiki=Edge_coloring}

The edge chromatic number is the least number of colours required to colour edges so that incident edges receive different colours.

= Chromatic polynomial
{title2=$P_G(t)$}
{parent=Graph colouring}
{wiki}

For each positive integer $t$, the chromatic polynomial $P_G(t)$ counts the proper vertex colourings of a finite graph $G$ using a fixed palette of $t$ colours.

= Deletion-contraction recurrence for the chromatic polynomial
{parent=Chromatic polynomial}

For a non-loop edge $e$,
$$
P_G(t)=P_{G-e}(t)-P_{G/e}(t).
$$
The first term counts colourings after deleting $e$; the second subtracts those giving its endpoints the same colour, which correspond to colourings of the contraction. Together with $P_G(t)=t^{|V(G)|}$ for an edgeless graph, induction proves that $P_G$ is a polynomial.

= Chromatic polynomial after attaching a leaf
{parent=Chromatic polynomial}

Attaching a new <leaf of a graph>[leaf] to a graph multiplies its <chromatic polynomial> by $t-1$, because after colouring the old graph the leaf may receive any colour except its neighbour's.

= Independent set
{parent=Graph theory}
{wiki=Independent_set_(graph_theory)}

An independent set is a set of vertices no two of which are adjacent. In every proper colouring, each colour class is an independent set.

= Leaf of a graph
{parent=Graph theory}
{wiki=Vertex_(graph_theory)}

A leaf is a vertex of degree one.

= Edge of a graph
{parent=Graph theory}
{wiki=Glossary_of_graph_theory_terms#edge}

An edge joins two vertices of a graph; in a simple graph it is an unordered pair of distinct vertices.

= Edge
{synonym}

= Edges
{synonym}

= Path in a graph
{parent=Graph theory}
{wiki=Path_(graph_theory)}

A path of length $t$ is a sequence of $t+1$ distinct vertices in which consecutive vertices are adjacent.

= Long path from minimum degree
{parent=Path in a graph}

Every connected $n$-vertex graph of minimum degree $\delta$ contains a path of length at least $\min(2\delta,n-1)$.

= Erdos-Gallai path edge bound
{parent=Path in a graph}
{c}
{wiki=Erdős–Gallai_theorem}

An $n$-vertex graph containing no path of length $t$ has at most $(t-1)n/2$ edges.

= Subgraph
{parent=Graph theory}
{wiki}

A subgraph is obtained from a graph by selecting some of its vertices and edges while retaining every selected edge's endpoints.

= Induced subgraph
{parent=Subgraph}
{wiki}

The subgraph induced by a vertex set $W$ contains every edge of the original graph whose two endpoints lie in $W$.

= Three-colourable two-thirds subgraph lemma
{parent=Subgraph}

Every finite graph $G$ has a three-colourable subgraph with at least $2e(G)/3$ edges. Give vertices three independent uniform colours and retain edges whose endpoints have different colours. Each edge survives with probability $2/3$, so the expected number surviving is $2e(G)/3$.

= Complete graph
{parent=Graph theory}
{wiki}

The complete graph $K_r$ has $r$ vertices and every possible edge between distinct vertices.

= Clique
{parent=Complete graph}
{wiki=Clique_(graph_theory)}

A clique in a graph is a vertex set whose induced subgraph is complete. A copy of $K_r$ is therefore an $r$-vertex clique.

= Adjacency-matrix quadratic relation for a complete graph
{parent=Complete graph}

For the adjacency matrix $A$ of $K_n$,
$$
A=J-I,
\qquad
A^2=(n-2)A+(n-1)I.
$$
Hence $I,A,A^2$ are linearly dependent for every $n\geq2$.

= Graph Laplacian
{title2=$L$}
{parent=Graph theory}
{wiki=Laplacian_matrix}

For a finite graph with adjacency matrix $A$ and degree matrix $D$, its graph Laplacian is
$$
L=D-A.
$$
Its quadratic form is $x^TLx=\sum_{\{i,j\}\in E}(x_i-x_j)^2$.

= Laplacian spectrum of a complete graph
{parent=Graph Laplacian}

The <graph Laplacian> of the <complete graph> $K_n$ has eigenvalue zero on the constant vector and eigenvalue $n$ on the $(n-1)$-dimensional subspace whose coordinates sum to zero.

= Minimum-cost flow
{parent=Graph theory}
{wiki=Minimum-cost_flow_problem}

A minimum-cost flow minimizes a linear edge cost subject to vertex flow balances and edge capacity intervals. Subtracting every lower capacity from its edge flow converts all lower bounds to zero while shifting the balance vector and objective by constants.

= Extremal graph theory
{parent=Graph theory}
{wiki=Extremal_graph_theory}

= Extremal number
{title2=$\operatorname{ex}(n,H)$}
{parent=Extremal graph theory}
{wiki=Extremal_graph_theory}

The extremal number $\operatorname{ex}(n,H)$ is the largest number of edges in an $n$-vertex graph containing no subgraph isomorphic to $H$.

= Mantel theorem
{c}
{parent=Extremal number}
{wiki=Mantel%27s_theorem}

Every triangle-free graph on $n$ vertices has at most $\lfloor n^2/4\rfloor$ edges.

= Turan theorem
{c}
{parent=Extremal graph theory}
{wiki=Turán%27s_theorem}

Among $n$-vertex graphs containing no $K_{r+1}$, the maximum number of edges is attained by the complete $r$-partite graph whose part sizes differ by at most one, denoted $T_r(n)$.

= Quadratic Turan edge bound
{parent=Turan theorem}
{c}

Every $n$-vertex graph containing no $K_{r+1}$ satisfies
$$
e(G)\leq\left(1-\frac1r\right)\frac{n^2}{2}.
$$

= Rhombus-free edge bound
{parent=Turan theorem}

A graph-theoretic rhombus is two triangles sharing an edge. Every rhombus-free graph on $n\geq4$ vertices has at most
$$
e(T_2(n))=\left\lfloor\frac{n^2}{4}\right\rfloor
$$
edges. If the graph is triangle-free this is Turán's theorem. Otherwise remove a triangle: every remaining vertex has at most one neighbor in it, and induction bounds the edge count by
$\lfloor(n-3)^2/4\rfloor+n\leq\lfloor n^2/4\rfloor$.

= Triangular prism graph
{parent=Rhombus-free edge bound}
{wiki=Triangular_prism_graph}

The triangular prism has six vertices and nine edges. Each edge lies in at most one triangle, so it has no rhombus; its two triangles show that it is not $K_{3,3}=T_2(6)$.

= Flow network
{parent=Graph theory}
{wiki=Flow_network}

A flow network is a directed capacitated graph with a source and sink. A feasible flow respects edge capacities and conserves flow at every other vertex.

= Max-flow min-cut theorem
{parent=Flow network}
{wiki=Max-flow_min-cut_theorem}

The greatest value of a feasible source-to-sink flow equals the least capacity of a source-to-sink cut. For a maximum flow, the vertices reachable from the source in the residual graph define a cut whose forward edges are saturated and whose backward edges carry zero flow.

= Parametric maximum flow with one source capacity
{parent=Max-flow min-cut theorem}

If one edge leaving the source has capacity $x$, every cut capacity is affine in $x$ with coefficient zero or one. In the 2024 Cambridge Part IB example, cuts of capacities $x+5$ and $14$ are both sharp, giving
$$
\delta^*(x)=\min\{x+5,14\}.
$$

= Eulerian graph
{parent=Graph theory}
{wiki}

An Eulerian graph has a closed trail that traverses every edge exactly once.

= Euler circuit criterion
{parent=Eulerian graph}
{c}

A finite graph with at least three vertices is Eulerian exactly when it is connected and every vertex has even degree. A maximal trail closes by parity; closed trails based at vertices with unused incident edges can then be spliced together.

= Line graph
{parent=Graph theory}
{wiki}

The line graph $L(G)$ has one vertex for each edge of $G$, with adjacency when two original edges share an endpoint.

= Line graph of a regular graph is Eulerian
{parent=Line graph}

If $G$ is connected and $r$-regular, then $L(G)$ is connected and every one of its vertices has degree $2r-2$. The <Euler circuit criterion> therefore applies.

= Planar graph
{parent=Graph theory}
{wiki}

A planar graph admits a drawing in the plane whose edges meet only at common endpoints.

= Euler formula for a connected planar graph
{parent=Planar graph}
{c}
{wiki=Euler's_formula}

For a connected planar graph with $n$ vertices, $e$ edges, and $f$ faces,
$$
n-e+f=2.
$$
Deleting a cycle edge preserves connectedness and decreases both $e$ and $f$ by one, reducing the formula to its immediate tree case.

= Planar graph edge bound
{parent=Euler formula for a connected planar graph}

A simple planar graph with $n\geq3$ vertices has at most $3n-6$ edges.

= Planar girth edge bound
{parent=Euler formula for a connected planar graph}

If every face of a connected planar graph has size at least $g>2$, double-counting edge-face incidences and using Euler's formula gives
$$
e\leq\frac{g(n-2)}{g-2}.
$$

= Crossing number
{parent=Graph theory}
{wiki}

The crossing number of a graph is the minimum number of edge-crossing pairs among its plane drawings. For a fixed drawing, deleting at most one edge per crossing pair leaves a planar graph.

= Crossing lemma
{parent=Crossing number}
{wiki}

If a simple graph has $n$ vertices and $e\geq4n$ edges, every plane drawing has at least
$$
\frac{e^3}{64n^2}
$$
crossings. Apply the linear planar bound to the random induced subgraph obtained by retaining vertices independently with probability $4n/e$.

= Graph neighbourhood
{title2=$N(S)$}
{parent=Graph theory}
{wiki=Neighbourhood_(graph_theory)}

The neighbourhood $N(S)$ of a vertex set $S$ consists of all vertices adjacent to at least one vertex of $S$.

= Neighbourhoods of a vertex
{synonym}

= Common neighbour
{parent=Graph neighbourhood}

A common neighbour of vertices $u$ and $v$ is adjacent to both of them.

= Common neighbours
{synonym}

= Degree of a vertex
{title2=$\deg(v)$}
{parent=Graph theory}
{wiki=Degree_(graph_theory)}

The degree of a vertex is the number of edges incident with it, equivalently the cardinality of its neighbourhood in a simple graph.

= Locally finite graph
{parent=Degree of a vertex}
{wiki}

A graph is locally finite when every vertex has finite degree.

= Cut of a graph
{parent=Graph theory}
{wiki=Cut_(graph_theory)}

A cut is a partition $V=A\sqcup B$ of the vertex set. Its size is the number of edges with one endpoint in each part.

= Maximum cut
{parent=Cut of a graph}
{wiki=Maximum_cut}

A maximum cut has greatest size among all cuts of a finite graph.

= Unfriendly partition of a graph
{parent=Cut of a graph}
{wiki=Unfriendly_partition}

An unfriendly partition $V=A\sqcup B$ puts at least as many neighbours of every vertex in the opposite part as in its own part.

= Unfriendly partition theorem for a finite graph
{parent=Unfriendly partition of a graph}

Every finite graph has an unfriendly partition. In a maximum cut, moving any vertex to the other side cannot increase the number of crossing edges, which is exactly the required neighbour inequality.

= Unfriendly partition theorem for a countable locally finite graph
{parent=Unfriendly partition of a graph}

Take unfriendly partitions of an exhaustion by finite induced subgraphs and use a diagonal subsequence to stabilize the colour of each vertex. Local finiteness makes every neighbourhood stabilize after finitely many steps, so each unfriendly inequality passes to the limit.

= Random unfriendly partition of a countable infinite-degree graph
{parent=Unfriendly partition of a graph}

Independently colour the vertices of a countable graph red or blue with equal probabilities. If every vertex has infinite degree, then each fixed vertex has infinitely many neighbours of each colour almost surely. A countable union of the exceptional null events is null, so such a colouring exists.

= Bipartite graph
{parent=Graph theory}
{wiki}

A graph is bipartite when its vertices split into two classes and every edge joins the two different classes.

= Complete bipartite graph
{parent=Bipartite graph}
{wiki}

The complete bipartite graph $K_{r,s}$ has vertex classes of sizes $r$ and $s$ and contains all $rs$ edges between the classes.

= Two-colourability criterion for bipartite graphs
{parent=Bipartite graph}

A finite graph is <bipartite graph>[bipartite] exactly when it has a proper colouring with two colours. Equivalently,
$$
P_G(2)>0
$$
for its <chromatic polynomial>.

= Directed graph
{parent=Graph theory}
{wiki}

A directed graph consists of <vertices of a graph>[vertices] joined by oriented edges.

= Directed edge
{parent=Directed graph}

A directed edge $u\to v$ has an initial vertex $u$ and a terminal vertex $v$.

= Directed edges
{synonym}

= Directed walk
{parent=Directed graph}

A directed walk is a sequence of vertices in which each consecutive pair is joined by a <directed edge> in the direction traversed.

= Closed directed walk
{parent=Directed walk}

A directed walk is closed when its first and last vertices agree.

= Closed directed walks
{synonym}

= Adjacency matrix of a directed graph
{title2=$A$}
{parent=Directed graph}

The adjacency matrix of a finite directed graph has entry $A_{ij}$ equal to the number of directed edges from vertex $i$ to vertex $j$. The entry $(A^n)_{ij}$ counts length-$n$ directed walks from $i$ to $j$, so $\operatorname{tr}(A^n)$ counts pointed closed directed walks of length $n$.

= Adjacency matrix of a graph
{title2=$A(G)$}
{parent=Graph theory}
{wiki=Adjacency_matrix}

The adjacency matrix of a finite simple graph has entry $A_{uv}=1$ when vertices $u,v$ are adjacent and zero otherwise.

= Walk count from powers of an adjacency matrix
{parent=Adjacency matrix of a graph}

For every nonnegative integer $k$, the entry $(A^k)_{uv}$ equals the number of length-$k$ walks from $u$ to $v$. This follows by induction, since matrix multiplication appends one adjacent vertex to each walk.

= Graph distance
{title2=$d(u,v)$}
{parent=Graph theory}
{wiki=Distance_(graph_theory)}

The distance $d(u,v)$ between connected vertices is the least length of a path joining them.

= Graph diameter
{title2=$d(G)$}
{parent=Graph distance}
{wiki=Distance_(graph_theory)}

The diameter of a connected finite graph is the maximum distance between two vertices.

= Linear independence of adjacency powers up to the diameter
{parent=Graph diameter}

If a connected graph has adjacency matrix $A$ and diameter $d$, then
$$
I,A,\ldots,A^d
$$
are linearly independent. For the largest index $k$ with a nonzero coefficient, choose vertices at distance $k$; the corresponding entries of all lower powers vanish, while $(A^k)_{uv}>0$ by the <walk count from powers of an adjacency matrix>.

= Graph eigenvalue
{parent=Graph theory}
{wiki=Spectral_graph_theory}

The eigenvalues of a finite graph are the eigenvalues of its adjacency matrix.

= Bipartite adjacency matrix
{parent=Graph theory}

With the two vertex classes listed consecutively, a bipartite graph has adjacency matrix $\left(\begin{smallmatrix}0&B\\B^T&0\end{smallmatrix}\right)$.

= Perfect matching from a nonzero determinant
{parent=Bipartite adjacency matrix}

If a square bipartite adjacency matrix $B$ has nonzero determinant, some product in its Leibniz expansion is nonzero. Its permutation selects one edge at each vertex and therefore gives a perfect matching.

= Matching in a graph
{parent=Graph theory}
{wiki=Matching_(graph_theory)}

A matching is a set of edges with no shared endpoints. It saturates a vertex set when every vertex in that set is incident to one of its edges.

= Perfect matching
{parent=Matching in a graph}
{wiki}

A perfect matching saturates every vertex of the graph.

= Maximal matching
{parent=Matching in a graph}
{wiki=Maximal_matching}

A matching is maximal when no edge can be added to it, and maximum when no matching has more edges. Every maximum matching is maximal, and the unmatched vertices of a maximal matching form an independent set.

= Matching number
{parent=Matching in a graph}
{wiki=Matching_(graph_theory)\#Matching_number}

The matching number $\nu(G)$ is the largest number of edges in a matching of $G$.

= Hall marriage theorem
{parent=Matching in a graph}
{c}
{wiki=Hall%27s_marriage_theorem}

A bipartite graph has a matching saturating $X$ exactly when $|N(S)|\ge|S|$ for every $S\subseteq X$.

= Hall induction through a tight set
{parent=Hall marriage theorem}
{c}

For Hall's theorem, either every proper nonempty set has one excess neighbour and one deletes an arbitrary edge's endpoints, or a tight set $S$ with $|N(S)|=|S|$ splits the problem into the induced graph on $S\cup N(S)$ and its complement.

= Regular bipartite graph has a perfect matching
{parent=Hall marriage theorem}

In a $k$-regular bipartite graph, edge counting gives equal vertex-class sizes and $k|S|\leq k|N(S)|$. Hall's theorem therefore supplies a perfect matching.

= Regular-graph matching bound from unmatched vertices
{parent=Matching in a graph}

If a $k$-regular graph on $n$ vertices has a maximum matching of size $m$, its unmatched vertices are independent. Counting their incident edges gives $k(n-2m)\leq2(k-1)m$, and hence $m\geq kn/(4k-2)$.

= Disjoint union of triangles as a sharp matching example
{parent=Regular-graph matching bound from unmatched vertices}

The disjoint union of $r$ triangles is $2$-regular on $3r$ vertices and has matching number $r$, attaining the regular-graph lower bound $n/3$.

= Antichain
{parent=Graph theory}
{wiki}

An antichain is a family of sets no one of which contains another.

= Ramsey theorem
{c}
{parent=Graph theory}
{wiki=Ramsey%27s_theorem}

Every sufficiently large graph contains either a prescribed clique or a prescribed independent set.

= Diagonal Ramsey number
{parent=Ramsey theorem}

The diagonal Ramsey number $R(t)$ is the least $n$ such that every red-blue edge-colouring of $K_n$ contains a monochromatic $K_t$.

= Binomial upper bound for a Ramsey number
{parent=Diagonal Ramsey number}

The off-diagonal recursion
$$
R(s,t)\leq R(s-1,t)+R(s,t-1)
$$
with $R(1,t)=R(s,1)=1$ gives
$$
R(s,t)\leq\binom{s+t-2}{s-1}.
$$
In particular, $R(t)\leq\binom{2t-2}{t-1}<2^{2t}$.

= Graph Ramsey number
{parent=Ramsey theorem}

For a finite graph $G$, its two-colour Ramsey number $R(G)$ is the least $n$ such that every red-blue colouring of $K_n$ contains a monochromatic copy of $G$. It exists because a monochromatic clique on $|V(G)|$ vertices contains a copy of $G$.

= Off-diagonal graph Ramsey number
{title2=$r(G,H)$}
{parent=Graph Ramsey number}

The Ramsey number $r(G,H)$ is the least $n$ such that every red-blue colouring of $K_n$ contains a red copy of $G$ or a blue copy of $H$.

= Clique-path Ramsey number
{title2=$r(K_s,P_t)$}
{parent=Off-diagonal graph Ramsey number}

If $P_t$ denotes a path of length $t$, then
$$
r(K_s,P_t)=(s-1)t+1
$$
for $s\geq2$ and $t\geq1$.

= Ramsey number of a star
{parent=Graph Ramsey number}
{c}

For the star $K_{1,t}$,
$$
R(K_{1,t})=
\begin{cases}
2t,&t\text{ odd},\\
2t-1,&t\text{ even}.
\end{cases}
$$
The parity distinction follows from the handshake lemma applied to a hypothetical $(t-1)$-regular colour class on $2t-1$ vertices.

= Paw graph
{parent=Graph Ramsey number}
{wiki}

The paw graph is a triangle with one pendant edge.

= Ramsey number of the paw graph
{parent=Paw graph}
{c}

The paw graph $H$ has $R(H)=7$. A colouring of $K_6$ with two disjoint red triangles and all cross-edges blue avoids a monochromatic paw. In $K_7$, a monochromatic triangle exists; avoiding a paw forces all its edges to the other four vertices into the opposite colour, which then forces those four internal edges into the triangle's colour and creates a paw.

= Dirac theorem
{c}
{parent=Graph theory}
{wiki=Dirac%27s_theorem}

Every graph on $n\ge3$ vertices with minimum degree at least $n/2$ has a Hamilton cycle.

= Longest-path rotation
{parent=Graph theory}
{wiki=P%C3%B3sa%27s_theorem}

If an endpoint of a longest path is adjacent to an internal vertex, replacing the incident path edge by that chord produces another longest path with the same vertex set and a new endpoint. Every neighbour of every endpoint obtained this way must remain on the original path.

= Neighbourhood bound for a square-free bipartite graph
{parent=Longest-path rotation}

Let $A$ be $k$ vertices of a bipartite graph, each of degree at least $k$. If the graph has no $4$-cycle, then $|N(A)|\geq2k-1$. Indeed, any pair in $A$ has at most one common neighbour, so
$$
\sum_{y\in N(A)}\binom{d_A(y)}2\leq\binom k2.
$$
If $|N(A)|\leq2k-2$, Cauchy--Schwarz and $\sum_y d_A(y)\geq k^2$ make the left side strictly larger than $\binom k2$, a contradiction.

= Strongly regular graph
{parent=Graph theory}
{wiki}

A strongly regular graph has constant degree and fixed common-neighbour counts for adjacent and nonadjacent vertex pairs.

= Moser spindle
{c}
{parent=Graph theory}
{wiki}

The Moser spindle is a seven-vertex unit-distance graph with chromatic number four.

= Random graph
{parent=Graph theory}
{wiki}

A random graph is a graph sampled from a probability distribution on graphs.

= Isolated vertex
{parent=Random graph}
{wiki}

An isolated vertex has degree zero.

= Erdős-Rényi model
{parent=Random graph}
{c}
{wiki=Erdős–Rényi_model}

In the $G(n,p)$ model, each of the $\binom n2$ possible edges is included independently with probability $p$.

= Isolated vertices in the Erdős-Rényi model
{parent=Erdős-Rényi model}

Let $N$ be the number of isolated vertices in $G(n,p)$. Indicator variables give
$$
\mathbb EN=n(1-p)^{n-1}
$$
and, because a specified pair is simultaneously isolated precisely when the $2n-3$ incident edges are absent,
$$
\mathbb E(N^2)=n(1-p)^{n-1}
+n(n-1)(1-p)^{2n-3}.
$$

= Isolated-vertex threshold in the Erdős-Rényi model
{parent=Isolated vertices in the Erdős-Rényi model}

For $p=c\log n/n$, the number $N$ of isolated vertices satisfies
$$
\mathbb P(N=0)\longrightarrow
\begin{cases}
1,&c>1,\\
0,&c<1.
\end{cases}
$$
The upper side follows from the first-moment bound. On the lower side, $\mathbb EN\to\infty$ and $\operatorname{var}(N)/(\mathbb EN)^2\to0$, so the second-moment method applies.

= Connectivity threshold in the Erdős-Rényi model
{parent=Erdős-Rényi model}

For every fixed $\varepsilon>0$,
$$
p\geq(1+\varepsilon)\frac{\log n}{n}
\Longrightarrow\mathbb P(G(n,p)\text{ is connected})\to1,
$$
whereas the probability tends to zero when $p\leq(1-\varepsilon)\log n/n$. Above the threshold a union bound excludes every component of size at most $n/2$; below it isolated vertices remain with high probability.

= Expected subgraph count in the Erdős-Rényi model
{parent=Erdős-Rényi model}

If a fixed graph $H$ has $v$ vertices, $e$ edges, and $N_H(n)$ unlabelled copies in $K_n$, then the number $X_H$ of its copies in $G(n,p)$ satisfies
$$
\mathbb E X_H=N_H(n)p^e.
$$
This follows by writing $X_H$ as a sum of <indicator random variables>.

= Sparse clique-count concentration
{parent=Expected subgraph count in the Erdős-Rényi model}

For $p=n^{-2/3}\log n$, the number $X$ of copies of $K_4$ satisfies
$$
\mathbb EX=\binom n4p^6\sim\frac{(\log n)^6}{24}
$$
and $\operatorname{var}(X)=o((\mathbb EX)^2)$. Two distinct copies have dependent indicators only when they share at least two vertices; pairs sharing two or three vertices contribute respectively $O(n^6p^{11})$ and $O(n^5p^9)$ to the variance.

= Vertex-disjoint sparse clique copies
{parent=Expected subgraph count in the Erdős-Rényi model}

For $p=n^{-2/3}\log n$, the expected number of pairs of $K_4$ copies sharing a vertex is
$$
O(n^7p^{12}+n^6p^{11}+n^5p^9)=o(1).
$$
Thus, with probability tending to one, all the $K_4$ copies are vertex-disjoint. Together with <sparse clique-count concentration>, this gives arbitrarily many vertex-disjoint copies with probability tending to one.

= Complement graph
{parent=Graph theory}
{wiki}

The complement of a simple graph has exactly the edges absent from the original graph; a vertex of degree $d$ acquires degree $n-1-d$.

= Menger theorem
{parent=Graph theory}
{c}
{wiki=Menger%27s_theorem}

The maximum number of disjoint paths joining two vertex sets equals the minimum size of a separating set, with vertex and edge versions according to the chosen notion of disjointness.

= Vertex separator
{parent=Menger theorem}
{wiki=Vertex_separator}

An $x$-$y$ vertex separator is a set of vertices, excluding $x$ and $y$, whose deletion leaves no path from $x$ to $y$.

= Internally vertex-disjoint paths
{parent=Menger theorem}
{wiki=Menger%27s_theorem}

Paths with common endpoints are internally vertex-disjoint when they share no other vertex.

= Set version of Menger theorem
{c}
{parent=Menger theorem}

For vertex sets $A,B$, the maximum number of pairwise vertex-disjoint $A$-$B$ paths equals the minimum size of a vertex set meeting every $A$-$B$ path.

= Linked graph
{parent=Menger theorem}
{wiki=K-linked_graph}

A graph is $k$-linked when any $2k$ distinct vertices paired as $(x_i,y_i)$ can be joined by $k$ mutually vertex-disjoint paths from $x_i$ to $y_i$.

= Vertex connectivity
{parent=Menger theorem}
{wiki=K-vertex-connected_graph}

Vertex connectivity $\kappa(G)$ is the smallest number of vertices whose deletion disconnects a nontrivial graph or reduces it to one vertex.

= Dirac circumference theorem
{parent=Vertex connectivity}
{c}
{wiki=K-vertex-connected_graph\#Properties}

A $k$-connected graph has a cycle of length at least $\min\{|G|,2k\}$.

= Longest-cycle attachment argument
{parent=Dirac circumference theorem}

A component outside a longest cycle has at least $k$ attachment vertices in a $k$-connected graph, and no two attachments are consecutive, forcing cycle length at least $2k$.

= Edge connectivity
{parent=Menger theorem}
{wiki=K-edge-connected_graph}

Edge connectivity $\lambda(G)$ is the smallest number of edges whose deletion disconnects the graph.

= Whitney inequalities for graph connectivity
{parent=Menger theorem}
{c}
{wiki=Connectivity_(graph_theory)}

For every nontrivial graph, $\kappa(G)\leq\lambda(G)\leq\delta(G)$.

= Connectivity realization construction
{parent=Whitney inequalities for graph connectivity}

Two large cliques joined by a bipartite cross graph with edge count $\ell$ and vertex-cover number $k$ realize edge connectivity $\ell$ and vertex connectivity $k$ while preserving a chosen minimum degree.

= Bipartite vertex cover
{parent=Graph theory}
{wiki=Vertex_cover\#Bipartite_graphs}

König's theorem equates the minimum vertex-cover size of a bipartite graph with its maximum matching size.

= Statistical learning theory
{parent=Foundations of mathematics}
{wiki}

= Bounded differences inequality
{c}
{parent=Statistical learning theory}
{wiki=McDiarmid%27s_inequality}

If independent inputs $Z_1,\ldots,Z_n$ enter a function whose value changes by at most $L_i$ when only coordinate $i$ changes, then
$$
\mathbb P(F-\mathbb EF\geq t)
\leq\exp\left(-\frac{2t^2}{\sum_iL_i^2}\right).
$$

= Uniform stability of a learning algorithm
{parent=Statistical learning theory}
{wiki=Stability_(learning_theory)}

A learning algorithm has uniform stability $\beta$ for a loss when replacing one training example changes the loss at every test example by at most $\beta$.

= Hypothesis class
{parent=Statistical learning theory}
{wiki=Concept_class}

A binary hypothesis class is a family of functions from an input space to a two-element label set, commonly $\{-1,1\}$.

= Sign function
{title2=$\operatorname{sgn}$}
{parent=Hypothesis class}
{wiki}

The sign function records whether a real number is positive or negative, with a convention chosen separately at zero.

= Empirical risk minimization
{parent=Statistical learning theory}
{wiki}

Empirical risk minimization chooses a hypothesis that minimizes the average loss on the observed data.

= Squared-loss empirical risk for linear prediction
{parent=Empirical risk minimization}

For data $(X_i,Y_i)$ and predictions $h_\beta(X)=\beta^TX$, it is convenient to write
$$
R_n(\beta)=\frac1{2n}\sum_{i=1}^n(\beta^TX_i-Y_i)^2.
$$
Its <gradient> is
$$
\nabla R_n(\beta)=\frac1n\sum_{i=1}^n(\beta^TX_i-Y_i)X_i.
$$

= Regression tree
{parent=Statistical learning theory}
{wiki=Decision_tree_learning}

A regression tree recursively partitions predictor space by axis-aligned splits. At each leaf, candidate coordinates and thresholds are compared by the residual sum of squares after replacing that leaf by its two children; the selected split minimizes the total criterion. The fitted value in each terminal region is the sample mean there.

= Conditional variance of a fixed regression-tree partition
{parent=Regression tree}

For a deterministic partition $R_1,\ldots,R_J$ and
$$
\widetilde\gamma_j=\frac1{N_j+1}
\sum_{i=1}^nY_i\mathbf1_{R_j}(X_i),
$$
conditional independence gives
$$
\operatorname{Var}(\widetilde\gamma_j\mid X_{1:n})
=\frac{\sum_i\operatorname{Var}(Y_i\mid X_i)\mathbf1_{R_j}(X_i)}
{(N_j+1)^2}.
$$
If the conditional response variance is at most $\sigma^2$, the prediction variance at an independent test point is at most $\sigma^2J/n$.

= Shattering coefficient
{title2=$s(\mathcal H,n)$}
{parent=Statistical learning theory}

The shattering coefficient is
$$
s(\mathcal H,n)=\sup_{x_1,\ldots,x_n}
\left|\{(h(x_1),\ldots,h(x_n)):h\in\mathcal H\}\right|.
$$

= Shattering coefficient of a union
{parent=Shattering coefficient}

For binary hypothesis classes,
$$
s(\mathcal H_1\cup\mathcal H_2,n)
\leq s(\mathcal H_1,n)+s(\mathcal H_2,n),
$$
because the label vectors realized by the union form the union of the two sets of realized label vectors.

= VC dimension
{title2=$\operatorname{VC}(\mathcal H)$}
{parent=Shattering coefficient}
{c}
{wiki}

The VC dimension is the largest number of points on which a binary hypothesis class realizes every possible labeling.

= Sauer-Shelah lemma
{parent=VC dimension}
{c}
{wiki=Sauer%E2%80%93Shelah_lemma}

If $VC(H)=D<\infty$, then $s(H,n)\leq\sum_{j=0}^D\binom nj$.

= Sauer-Shelah growth bound
{parent=Sauer-Shelah lemma}
{c}

The elementary estimate $\sum_{j=0}^D\binom nj\leq(n+1)^D$ converts finite VC dimension into a polynomial bound on the number of sample labelings.

= VC dimension bound for lower orthants
{parent=VC dimension}
{c}

The class of lower orthants $\prod_{j=1}^p(-\infty,a_j]$ in $\mathbb R^p$ has VC dimension at most $p$. Among any $p+1$ points, choose a coordinate maximizer for each of the $p$ coordinates. A remaining point cannot be excluded while all those maximizers are included.

= VC dimension of interval indicators
{parent=VC dimension}
{c}

Indicators of real intervals have VC dimension two: two ordered points can be labeled arbitrarily, while an interval containing the two outer points of a triple must contain the middle point.

= VC dimension of intervals and their complements
{parent=VC dimension}
{c}

Intervals together with their label complements shatter three ordered points, but cannot realize an alternating labeling on four, so their VC dimension is three.

= VC dimension of a vector space
{c}
{parent=Statistical learning theory}
{wiki=VC_dimension}

The sign class of a $d$-dimensional real <vector space> of functions has VC dimension at most $d$. If $n>d$ points were shattered, the <linear map>[evaluation map] from the function space to $\mathbb R^n$ would have a nonzero vector orthogonal to its image. Choosing labels according to the signs of that vector contradicts orthogonality.

= VC dimension upper bound for Euclidean balls
{c}
{parent=VC dimension of a vector space}

The indicators of closed <Euclidean ball>[Euclidean balls] in $\mathbb R^d$ have VC dimension at most $d+2$. Indeed,
$$
\mathbf1_{\{\lVert x-c\rVert_2^2\leq r^2\}}
=\mathbf1_{\{f_{c,r}(x)\leq0\}},
$$
where
$$
f_{c,r}(x)=\lVert x\rVert_2^2-2c^Tx+\lVert c\rVert_2^2-r^2
$$
belongs to the span of $\lVert x\rVert_2^2,x_1,\ldots,x_d,1$.

= Quadratic feature map
{parent=VC dimension of a vector space}

The map $x\mapsto(x_ix_j)_{i\leq j}$ embeds homogeneous quadratic forms in a linear function space of dimension $d(d+1)/2$.

= Growth bound for homogeneous linear classifiers
{parent=VC dimension of a vector space}

The signs of homogeneous linear forms $x\mapsto x^T\beta$ on $\mathbb R^p$ have VC dimension at most $p$. The <Sauer-Shelah growth bound> therefore gives
$$
s(\mathcal H,n)\leq(n+1)^p.
$$

= Growth bound for signs of m-term linear combinations
{parent=Statistical learning theory}

For $f=\sum_{j=1}^m\alpha_jg_j$ with $g_j$ drawn from a binary class $\mathcal G$, fixing $(g_1,\ldots,g_m)$ leaves an $m$-dimensional linear sign class. Consequently
$$
s(\operatorname{sgn}\mathcal F,n)
\leq(n+1)^m|\mathcal G|^m
$$
when $\mathcal G$ is finite, and in general
$$
s(\operatorname{sgn}\mathcal F,n)
\leq(n+1)^m s(\mathcal G,n)^m.
$$

= Growth bound for a single-hidden-layer sign network
{parent=Growth bound for signs of m-term linear combinations}

A bias-free network with $p$ inputs, $m$ sign-activated hidden nodes, and a thresholded linear output satisfies
$$
s(\mathcal H,n)\leq(n+1)^{(p+1)m}.
$$
The hidden units contribute $s(\mathcal G,n)^m\leq(n+1)^{pm}$ sample patterns, and the output weights contribute $(n+1)^m$.

= AdaBoost
{c}
{parent=Statistical learning theory}
{wiki}

AdaBoost constructs an additive classifier by repeatedly fitting a base classifier to exponentially reweighted observations. Misclassified observations receive greater weight at the next iteration, and the final score is a nonnegative weighted sum of the base classifiers.

= Exponential classification risk
{parent=AdaBoost}

For labels $Y\in\{-1,1\}$ and a real-valued score $f$, the exponential loss is $\phi(Yf(X))=e^{-Yf(X)}$. Its population and empirical risks are
$$
R_\phi(f)=\mathbb E[e^{-Yf(X)}],
\qquad
\widehat R_\phi(f)=\frac1n\sum_{i=1}^ne^{-Y_if(X_i)}.
$$

= Rademacher complexity
{c}
{parent=Statistical learning theory}
{wiki}

Rademacher complexity measures how strongly a hypothesis class can correlate with independent random signs on a sample.

= Massart finite-class lemma
{parent=Rademacher complexity}
{c}
{wiki=Rademacher_complexity\#Massart%27s_lemma}

For a finite $A\subseteq\mathbb R^n$ with $\max_{a\in A}\lVert a\rVert_2\leq R$, its empirical Rademacher complexity is at most $R\sqrt{2\log|A|}/n$.

= Rademacher bound for bounded weighted indicators
{parent=Rademacher complexity}
{c}

For $|D_i|\leq M$ and a binary class $H$ of VC dimension at most $p$, the vectors $(D_i h(X_i))_{i=1}^n$ have norm at most $M\sqrt n$ and at most $(n+1)^p$ distinct values. The Massart finite-class lemma gives
$$
\widehat R\leq M\sqrt{\frac{2p\log(n+1)}n}.
$$

= Rademacher complexity of a convex hull
{parent=Rademacher complexity}
{c}

A linear functional has the same supremum over a class and its convex hull. Thus taking convex combinations does not increase empirical Rademacher complexity.

= Rademacher contraction lemma
{parent=Rademacher complexity}
{c}
{wiki=Rademacher_complexity\#Properties}

Composition with an $L$-Lipschitz scalar map increases Rademacher complexity by at most the factor $L$ after centering at zero.

= Frobenius norm Rademacher calculation
{parent=Rademacher complexity}
{c}

Independent signs cancel cross terms in $\mathbb E\lVert\sum_i\sigma_iA_i\rVert_F^2$, leaving $\sum_i\lVert A_i\rVert_F^2$.

= Rademacher complexity of quadratic forms
{parent=Rademacher complexity}
{c}

For $h_M(x)=x^TMx$, $M\succeq0$, $\operatorname{tr}M\leq s$, and $\lVert x\rVert\leq C$, the complexity is at most $C^2s/\sqrt n$.

= Expected excess-risk bound for empirical risk minimization
{parent=Rademacher complexity}

With the $1/n$ Rademacher convention, an empirical risk minimizer has expected excess risk at most twice the Rademacher complexity of its loss class.

= Hinge loss
{parent=Statistical learning theory}
{wiki}

The hinge loss is $\max(0,1-yh(x))$ and is one-Lipschitz in the signed margin.

= Mathematical proof
{parent=Foundations of mathematics}
{wiki=Mathematical_proof}

A mathematical proof is a finite deductive argument from stated assumptions to a conclusion.

= Counterexample
{parent=Mathematical proof}
{wiki}

A counterexample is one instance satisfying a claim’s hypotheses but not its conclusion, and therefore disproves the universal claim.

= Structural induction
{parent=Mathematical proof}
{wiki}

Structural induction proves a property of every recursively generated object by checking the initial objects and showing that every construction rule preserves the property.

= Probability-preserving bijection
{parent=Mathematical proof}

A probability-preserving bijection pairs outcomes of two events without changing their masses, proving the events have equal probability.