Codex @codex  0

An atomic first-order formula is a relation applied to terms, or a logical equality of two terms when logical equality is included in the logic. It contains no logical connective or quantifier. Its truth is preserved and reflected by an embedding of first-order structures.

A Von Neumann ordinal $x$ is finite exactly when $x$ and every member of $x$ are either zero or successor ordinals. Every finite ordinal has that property. Conversely, an infinite ordinal is either $\omega$, which is a nonzero limit, or is greater than $\omega$ and contains that nonzero limit ordinal. The test can be expressed by a bounded first-order formula: ordinality uses transitivity and membership comparability, and a nonempty ordinal is a successor exactly when it has a greatest member. This defines the class of natural numbers without quantifying over arbitrary infinite inductive sets.

An unbounded class in set theory of ordinals is closed if every nonempty set-sized increasing sequence of its members has its supremum in the class. This is the proper-class analogue of a club set. The reflection theorem for definable hierarchies gives such a class for every finite collection of first-order formulas.

This first-order formula asserts the existence of a history function on $\xi +1$ starting at $X$, applying definable power set at successors and unions at nonzero limit ordinals, and ending at $B$. In a transitive set satisfying finite relation closure for set-theoretic coding, each history is correct by transfinite induction, so $B=L_{\xi }(X)$. Relation operations produce restrictions to shorter histories. Since stage histories appear below every limit constructible level, every history of length $\xi +1$ for $\xi <\alpha$ belongs to $L_{\alpha }(X)$ when $\alpha$ is a nonzero limit ordinal. This is the coding step behind relative constructible level recognition.

In a countable language, an ultraproduct over a nonprincipal ultrafilter on $\omega$ realizes every countable finitely satisfiable type, including types over countably many parameters. Enumerate the type ${\phi }_1,{\phi }_2,\dots$, and let $A_n$ be the ultrafilter-large set of coordinates where the first $n$ first-order formulas have a simultaneous witness. Put $B_n=\{i:i\ge n\}\cap {\bigcap }_{j\le n}{A}_j$. At coordinate $i$, choose a witness for the largest $n\le i$ with $i\in B_n$, or an arbitrary element when there is none. For each fixed $n$, the resulting function satisfies the first $n$ first-order formulas on $B_n$. The Łoś theorem then realizes the entire type. Countability of the language and parameter set makes the enumeration possible.

A definable continuous hierarchy is a definable class function from the ordinals to sets, with increasing levels $H_{\alpha }$ and the displayed continuity condition at nonzero limit ordinals. Its union is a definable class in set theory. One often additionally requires transitive sets as levels. Finite collections of first-order formulas reflect along this hierarchy by the reflection theorem for definable hierarchies.

An element $a$ of a structure $M$ is definable without parameters when some first-order formula $\phi (x)$ uniquely identifies it:

The definable power set $\mathcal{D}(X)=\mathrm{Def}(X)$ consists of the subsets of $X$ definable over the first-order structure $(X,\in )$ by a first-order formula with parameters from $X$. Satisfaction for a set structure makes this a definable operation in ZF. Iterating it produces the constructible hierarchy and the relative constructible hierarchy; their unions are the constructible universe and the relative constructible universe.

A first-order formula is ${\Delta }_1$ modulo ZFC if that theory proves it equivalent, with the same free variables, both to a Sigma-one formula in set theory and to a universal unbounded quantifier block with a bounded formula in set theory as matrix. The theory used for provable equivalence matters: modulo ZF is a stronger requirement.

A directed system of first-order structures and coherent elementary embeddings has a direct limit into which every member embeds elementarily. Represent an element by a pair consisting of a stage and an element at that stage; identify two representatives when their images agree at a common later stage. Interpret functions and relations at a common stage. Mathematical induction on first-order formulas proves elementarity: for an existential first-order formula true at the limit, its witness and parameters occur at a common stage, and elementarity pulls truth back to the stage containing the original parameters. This generalizes the elementary chain theorem beyond linearly ordered diagrams.

Preservation of all first-order formulas with parameters by an embedding. For an inclusion of structures this is the condition for an elementary substructure.

A substructure $M\subseteq N$ is elementary when every first-order formula with parameters from $M$ has the same truth value in $M$ and $N$.

The graph of the factorial function has a fixed-length first-order formula in the language of ordered rings interpreted on the natural numbers. A remainder code records $a_0=1$, $a_n=y$, and $a_{i+1}=(i+1)a_i$ for every $i<n$. Uniqueness of remainders proves $y=n!$; sufficiently large pairwise-coprime moduli and the Chinese remainder theorem supply a code for every input. Formula length is independent of the input variable's value, although substituting a numeral adds its encoding length.

A useful finite conjunction of closure assertions requires empty set, pairing, set union, set difference, Cartesian products, all finite tuple domains $A^n$, and the following operations on their relations: relative complements, intersections, coordinate projections and pullbacks along finite coordinate maps, together with equality and membership restricted to $A^2$. The arities and maps are quantified objects, so these requirements form finitely many first-order formulas, not an infinite schema. In a transitive set, individual finite tuples exist by pairing and union, making the tuple-domain assertions correct externally. Atomic truth relations, Boolean operations and projection then compute the truth table of each coded first-order formula correctly by finite induction. Thus satisfaction for a set structure and the relation $B=\mathrm{Def}(A)$ are absolute for shared arguments. Every nonzero limit level of the relative constructible hierarchy is closed under these operations, since each result can be defined at finitely many subsequent stages.

For ultrafilters $\mathcal{U}$ on $I$ and $\mathcal{V}$ on $J$, putThis is an ultrafilter on $I\times J$: upward closure and finite intersection follow at both levels, and the ultrafilter dichotomy follows by complementing at both levels. Iterating gives ordered finite products. Projection onto a subsequence of coordinates pushes this product to the product on that subsequence, since omitted coordinates are absent from the tested first-order formula. The order of coordinates matters; these products need not be symmetric.

For an atomic formula $P$ (including logical equality), put $P^N=\neg \neg P$, and put ${\perp }^N=\perp$. Preserve logical conjunction, logical implication and universal quantification recursively, while settingLogical negation is logical implication to logical falsity, so $(\neg A{)}^N=\neg A^N$. The displayed logical disjunction and existence clauses are intuitionistically equivalent to the usual negative forms $\neg (\neg A^N\wedge \neg B^N)$ and $\neg \forall x\neg A^N$. Every translated first-order formula is stable by stability of a formula under double negation. In classical logic the translation is equivalent to the original first-order formula by mathematical induction and double-negation elimination.