Reflection, Absoluteness, and Elementary Submodels: Examples and Counterexamples

Absolute basic set operations and relations: The graphs of empty set, subset, unordered pair, singleton, union, intersection (with $\bigcap \mathrm{\varnothing }=\mathrm{\varnothing }$), difference, Kuratowski ordered pair, Cartesian product, relation domain/range, functionhood, evaluation and injection have ${\mathrm{\Delta }}_0$ definitions. Thus their values agree between transitive membership structures whenever the input and output sets are in the smaller domain. This is graph agreement, not an assertion that an arbitrary transitive domain is closed under these operations.

Bounded formulas are absolute for transitive sets: If $M\subseteq N$ are nonempty transitive sets, every ${\mathrm{\Delta }}_0$ formula is absolute between them on parameter tuples from $M$. No internal set-theory axioms are required. The analogous assertion for definable transitive classes is a formula-by-formula scheme.

Sigma-one truth goes upward: For nonempty transitive $M\subseteq N$, a literal existential block over a ${\mathrm{\Delta }}_0$ matrix transfers truth upward, and its universal dual transfers truth downward. For formulas classified only by ZF-provable equivalence, assume both structures satisfy ZF (or all axioms used in the equivalence proof).

Ordinals and omega in transitive models: In ambient ZF, ordinalhood is absolute between transitive membership domains containing the parameter. A transitive set model of ZF contains precisely the real finite ordinals as its natural numbers and has ${\omega }^M=\omega$. Its ordinals form an initial segment of the actual ordinals.

Absolute basic set operations and relations: The graphs of empty set, subset, unordered pair, singleton, union, intersection (with $\bigcap \mathrm{\varnothing }=\mathrm{\varnothing }$), difference, Kuratowski ordered pair, Cartesian product, relation domain/range, functionhood, evaluation and injection have ${\mathrm{\Delta }}_0$ definitions. Thus their values agree between transitive membership structures whenever the input and output sets are in the smaller domain. This is graph agreement, not an assertion that an arbitrary transitive domain is closed under these operations.

Ranks agree and hierarchy membership is absolute: If $M\subseteq N$ are transitive models of ZF and $x\in M$, then ${\mathrm{rank}}^M(x)={\mathrm{rank}}^N(x)$. For every $\alpha \in M\cap \mathrm{Ord}$, $(V_{\alpha }{)}^M=M\cap (V_{\alpha }{)}^N$. Equality of the two internal power sets or stage sets is not asserted.

Montague–Lévy reflection for a finite formula family: In ZF, for each fixed finite family $\mathrm{\Phi }$ and every ordinal $\alpha$, some $\beta >\alpha$ makes $\mathrm{\Phi }$ absolute between $V_{\beta }$ and $V$, for all tuples in $V_{\beta }$. More generally the same holds between $W_{\beta }$ and $W$ for a definable increasing continuous hierarchy of sets exhausting a definable nonempty class $W$. For an empty class, the relativization statement is interpreted as a scheme rather than satisfaction in an empty structure.

Transitive models of fixed finite axiom fragments: For each fixed external finite $\mathrm{\Gamma }\subseteq \mathrm{Z}\mathrm{F}$, ZF proves that some transitive $V_{\beta }$ satisfies $\mathrm{\Gamma }$, with $\beta$ above any prescribed ordinal bound. In ZFC the analogous scheme holds for fixed finite $\mathrm{\Gamma }\subseteq \mathrm{Z}\mathrm{F}\mathrm{C}$. These are schemes indexed by external fragments, not a single internal assertion of models for all coded fragments.

Hartogs: an ordinal that does not inject into a given set: For every set $A$ there is an ordinal (def-ordinal) that does not inject into $A$, that is, admits no injective function into $A$. The least such ordinal is the Hartogs number $\mathrm{\aleph }(A)$, and it is exactly

$\mathrm{\aleph }(A)=\{\mathrm{o}\mathrm{t}(S,R):S\subseteq A\text{ and }R\text{ well-orders }S\},$

the set of order types (thm-mostowski-collapse) of the well-ordered subsets of $A$.

The proof is choice free. That is the whole point of the theorem: in ZF alone, with no assumption that $A$ can be well ordered, one still gets an ordinal too long to be laid inside $A$.

Countable elementary submodels and their collapses: In ZFC, if an infinite set membership structure $M$ satisfies Extensionality, then for every at most countable $A\subseteq M$ there is a countably infinite $X\prec M$ containing $A$, and $X$ has a countable transitive collapse. To retain a set $a\in M$ as one parameter, use $A=\{a\}$.

What the collapse fixes: Let $\pi :X\to \bar{X}$ be a collapse of actual membership as above. It fixes every transitive subset $A\subseteq X$ pointwise. If $\alpha \in X$ is an actual ordinal, $\pi (\alpha )$ is the order type of $X\cap \alpha$. In particular, if $X\cap \alpha$ is transitive, $\pi (\alpha )=X\cap \alpha$.

The Axiom of Choice: Every family of nonempty sets has a choice function

Elementary chains and compatible collapses: A nonempty set-ordinal elementary chain of actual membership structures satisfying Extensionality has a union elementary over every stage, and the union has a transitive collapse. Conjugating the inclusions by stage and union collapses gives coherent elementary embeddings; these are not asserted to be inclusions of the transitive images.

What the collapse fixes: Let $\pi :X\to \bar{X}$ be a collapse of actual membership as above. It fixes every transitive subset $A\subseteq X$ pointwise. If $\alpha \in X$ is an actual ordinal, $\pi (\alpha )$ is the order type of $X\cap \alpha$. In particular, if $X\cap \alpha$ is transitive, $\pi (\alpha )=X\cap \alpha$.

Countable elementary submodels and their collapses: In ZFC, if an infinite set membership structure $M$ satisfies Extensionality, then for every at most countable $A\subseteq M$ there is a countably infinite $X\prec M$ containing $A$, and $X$ has a countable transitive collapse. To retain a set $a\in M$ as one parameter, use $A=\{a\}$.

Hartogs: an ordinal that does not inject into a given set: For every set $A$ there is an ordinal (def-ordinal) that does not inject into $A$, that is, admits no injective function into $A$. The least such ordinal is the Hartogs number $\mathrm{\aleph }(A)$, and it is exactly

$\mathrm{\aleph }(A)=\{\mathrm{o}\mathrm{t}(S,R):S\subseteq A\text{ and }R\text{ well-orders }S\},$

the set of order types (thm-mostowski-collapse) of the well-ordered subsets of $A$.

The proof is choice free. That is the whole point of the theorem: in ZF alone, with no assumption that $A$ can be well ordered, one still gets an ordinal too long to be laid inside $A$.

The Axiom of Choice: The Axiom of Choice (AC) is the following statement.

Every family of nonempty sets has a choice function (def-choice-function).

Written out: for every set $\mathcal{F}$ all of whose members are nonempty, there exists a function $g$ with domain $\mathcal{F}$ satisfying $g(S)\in S$ for all $S\in \mathcal{F}$.

An equivalent formulation is that a product of nonempty sets is nonempty: if $X_i\mathrm{\ne }\mathrm{\varnothing }$ for every $i\in I$, then ${\prod }_{i\in I}{X}_i\mathrm{\ne }\mathrm{\varnothing }$. Here ${\prod }_{i\in I}{X}_i$ is the set of functions $f$ with domain $I$ such that $f(i)\in X_i$ for every $i\in I$; when a family of nonempty sets is indexed by itself, such an $f$ is precisely a choice function for it.