Foundations of mathematics

The von Neumann hierarchy isEvery level is transitive, the levels are increasing, and every set belongs to some level.

The rank is defined byIt is the least ordinal $\alpha$ for which $x\subseteq V_{\alpha }$.

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

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

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

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

The empty set has no elements.

A singleton set has exactly one element.

Elements are distinct when they are unequal.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A relation $R$ is symmetric when $xRy$ implies $yRx$.

A relation $R$ is transitive when $xRy$ and $yRz$ imply $xRz$.

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

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

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

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

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

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

A constant function has the same output for every input.

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

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

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

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

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

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.

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

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 )$.

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.

The relativization ${\phi }^M$ of a formula $\phi$ is obtained recursively by restricting every quantifier to $M$:For parameters in $M$, the ambient statement ${\phi }^M$ holds exactly when the structure $(M,\in )$ satisfies $\phi$.

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.

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

The principle of epsilon induction says that every progressive class is universal: ifthen $\phi (x)$ holds for every set $x$. Over the other axioms of ZF, it is equivalent to the Axiom of foundation.

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

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.

The transitive closure $\mathrm{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$.

A set is hereditarily countable when its transitive closure is countable. These sets form the transitive set $H_{{\omega }_1}$ and all have rank below ${\omega }_1$.

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

The class of hereditarily finite sets is the setEquivalently, these are the sets with finite transitive closure, or the sets contained in a finite transitive set.

For each formula $\phi$, the axiom schema of specification forms the subsetof any set $x$. When interpreting the schema inside a class model, the formula must be evaluated internally.

Let $M$ be a transitive class. If $M$ is closed under the ambient subsets defined by ${\phi }^M$, then $M$ satisfies the $\phi$-instance of separation, because

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

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}$.

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

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$.

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.

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

In ZF, if $X\times X\cong X$ for every infinite $X$, apply this to $X\bigsqcup 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$.

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

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

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

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

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

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

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

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

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 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$.

In ZF, let $K,L$ be nonempty. If $K\times L$ injects into $K\bigsqcup 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\bigsqcup L\to K\times L$ by sending points outside its range to one fixed pair $(k_{\ast },l_{\ast })$. 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_{\ast }\}$ 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$.

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.

If ${\kappa }_i<{\lambda }_i$ for every $i\in I$, thenThe 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.

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

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

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

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

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

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

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 defines a value at each ordinal from the function of all earlier values.

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

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

For all ordinals $\alpha ,\beta ,\gamma$,This follows by transfinite induction on $\gamma$ from the recursive definition of 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 forms at the first exponent where they differ.

Ordinal multiplication is defined recursively byfor nonzero limit ordinal $\lambda$. It is associative and left-distributive over ordinal addition, but generally neither commutative nor right-distributive.

Ordinal exponentiation is defined recursively byfor nonzero limit $\lambda$. Transfinite induction gives

For a well-ordered set $X$, let $X^{\prime }$ 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.

For an ordinal $\xi$,Thus the derivative index of $\omega$ is one and that of ${\omega }^2$ is two.

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

The first uncountable ordinal ${\omega }_1$ is the set of all countable ordinals.

Deleting any countable initial segment from ${\omega }_1$ leaves a well-order of type ${\omega }_1$.

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.

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

Every nonzero ordinal $\alpha$ has a greatest exponent $\beta$ such that ${\omega }^{\beta }\le \alpha$. It is the leading exponent in the Cantor normal form of $\alpha$, andfor a positive finite integer $n$ and $\gamma <{\omega }^{\beta }$.

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.

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

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.

For every ordinal $\gamma$ and $\lambda ={\omega }^{\alpha }$, there are unique ordinals $\beta ,\delta$ such thatChoose the greatest initial multiple $\lambda \beta \le \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)$.

An ordinal $\delta >2$ is multiplicatively closed when $\beta \gamma <\delta$ for all $\beta ,\gamma <\delta$. These are exactly

For nonzero $\lambda$, the ordinal ${\omega }^{\lambda }$ is multiplicatively closed exactly when $\lambda$ is additively closed. One direction follows fromFor the other, the leading exponent of an ordinal product shows that products of ordinals below ${\omega }^{\lambda }$ still have leading exponent below $\lambda$.

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

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

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 studies formal languages, proofs, models, computability, and the foundations of mathematics.

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

A set $S$ of formulae is deductively closed whenEquivalently, $S$ equals its deductive closure $\mathrm{Cn}(S)$.

A set $S$ is syntactically consistent when $S/⊢\perp$. Equivalently in classical logic, there is no formula $\phi$ for which both $S⊢\phi$ and $S⊢\neg \phi$.

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

Ifare 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.

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$.

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.

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 permits quantification over elements of a structure while its nonlogical symbols describe operations, constants, and relations.

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

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.

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

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

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.

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.

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

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

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

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

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.

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

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

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

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.

A family $(f_g{)}_{g\in G}$ of automorphisms satisfying $f_g{f}_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.

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.

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.

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

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.

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

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.

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.

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.

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

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 \ge |L|+{\aleph }_0$.

If $A$ is an infinite $L$-structure and $|L|+{\aleph }_0\le \kappa \le |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.

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.

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$; ${?}_{\epsilon }(k,p,q)$ tests emptiness; and $-(k,p,q)$ branches to $p$ when empty, or deletes the final letter and branches to $q$ otherwise.

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$.

Two string registers can recognize $\{a^n{b}^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.

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.

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 functions are generated by zero, successor, and projections under composition and primitive recursion.

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

The zero function has the constant valueDummy variables give a zero function of any finite arity.

The successor function is

The $i$th $k$-ary projection returns its $i$th input:

Given a $m$-ary function $g$ and $k$-ary functions $h_1,\dots ,h_m$, composition forms

From $g:{\mathbb{N}}^k\to \mathbb{N}$ and $h:{\mathbb{N}}^{k+2}\to \mathbb{N}$, primitive recursion defines