Ehrenfeucht's lemma in set theory

PDF   Bibtex   Arχiv

G. Fuchs, V. Gitman, and J. D. Hamkins, “Ehrenfeucht’s lemma in set theory,” Notre Dame J. Form. Log., vol. 59, no. 3, pp. 355–370, 2018.

Ehrenfeucht's lemma asserts that if an element $b$ in a model $M$ of Peano arithmetic (${\rm PA}$) is definable from another distinct element $a$, then the types of $a$ and $b$ in $M$ must be different. This lemma first appeared in a short paper of Ehrenfeucht's [1], who used it to argue that if a model of ${\rm PA}$ is the Skolem closure of a single element $a$, then $a$ is the only element of its type; consequently, such models have no non-trivial automorphisms. Since that time, Ehrenfeucht's lemma has become ubiquitous in the study of models of ${\rm PA}$. In light of the extensive transfer of model-theoretic techniques from models of ${\rm PA}$ to models of set theory, we find it extremely natural to inquire whether Ehrenfeucht's lemma holds for models of set theory.

The initial answer is that Ehrenfeucht's original argument succeeds directly in models of $V={\rm HOD}$, and more generally, it applies to the ordinal-definable elements of any model of set theory. Nevertheless, we prove that the lemma does not hold in all models of ${\rm ZFC}$, and it definitely fails in the forcing extension obtained by adding a generic Cohen real.

Theorem:

  1. If $a$ is ordinal-definable in a model of set theory $M\models{\rm ZF}$ and $b$ is definable from $a$, with $b\neq a$, then $a$ and $b$ satisfy different types in $M$. Consequently, Ehrenfeucht's lemma holds fully in models of $V={\rm HOD}$.
  2. Meanwhile, Ehrenfeucht's lemma does not hold in all models of set theory. Specifically, if $M$ is any model of ${\rm ZFC}$, then in the forcing extension $M[c]$ to add a Cohen real $c$, there are inter-definable elements $a\neq b$ with exactly the same type in $M[c]$. Indeed, there are such elements $a$ and $b$ with ${\rm tp}^{M[c]}(a/M)={\rm tp}^{M[c]}(b/M)$, meaning that $a$ and $b$ satisfy all the same formulas even with parameters from the ground model $M$.

Generalizing these observations, we shall introduce the parametric family of principles ${\rm EL}(A,P,Q)$, which holds for a model of set theory $M$ if whenever $a\in A$ and $b$ is definable in $M$ from $a$ using parameters in $P$, with $b\neq a$, then the types of $a$ and $b$ over $Q$ in $M$ are different. So in short, ${\rm EL}(A,P,Q)$ can be expressed by the slogan that $P$-definability from $A$ implies $Q$-discernibility. It might be of interest in general to also specify a set $B$ that $b$ has to belong to, but for our present purposes, this is not needed. Usually, the crucial case is that $a$ and $b$ come from the same collection, because if they don't, then they can be distinguished for that very reason, at least for the classes $A$ that will be of interest to us.

These principles unify several natural variations of Ehrenfeucht's lemma that one finds in set theory. The principle ${\rm EL}(M,\emptyset,\emptyset)$, for instance, expresses the original Ehrenfeucht's lemma itself, and we have just mentioned in the theorem above that the principle ${\rm EL}({\rm OD}^M,\emptyset,\emptyset)$ holds in every model of set theory, while the principle ${\rm EL}(M,\emptyset,{\rm On}^M)$ fails in any model $M$ obtained by forcing to add a Cohen real. The principle ${\rm EL}(M,M,{\rm On}^M)$ expresses in a model $M$ of set theory that any two distinct elements of $M$ can be distinguished by some formula with an ordinal parameter, which is the Leibniz-Mycielski axiom (see [bibcite key=Enayat2004:LM]). The principle ${\rm EL}(M,M,\emptyset)$ holds for a model $M$ if any two distinct elements of $M$ have distinct types, which is precisely the property of $M$ being Leibnizian (see [2]).

Lastly, we shall explore the relationship between definability and algebraicity, and variations of Ehrenfeucht's lemma which arise by using algebraicity in place of definability. Specifically, as in [bibcite key=HamkinsLeahy:AlgAndImp], a set is algebraic in a parameter if it belongs to a finite set definable from that parameter. We show that Ehrenfeucht's lemma holds on all ordinal-algebraic sets if and only if the ordinal-algebraic sets and the ordinal-definable sets coincide, and we also settle several open questions that were asked in [3] by pointing out that there are models of set theory in which there are algebraic sets that are not ordinal definable and there are models of set theory in which there are objects that are internally but not externally algebraic. Finally, we shall also investigate the algebraic versions of Ehrenfeucht's lemma, the principles ${\rm AEL}_{\text{ext}}(A,P,Q)$ and ${\rm AEL}_{\text{int}}(A,P,Q)$, which state that if $b$ is (externally/internally) algebraic in $a$ using parameters from $P$, with $b\neq a$, then the types of $a$ and $b$ in $M$ over $Q$ are different -- in short, $P$-algebraicity from $A$ implies $Q$-discernibility.

References

  1. A. Ehrenfeucht, “Discernible elements in models for Peano arithmetic,” J. Symbolic Logic, vol. 38, pp. 291–292, 1973.
  2. A. Enayat, “Leibnizian models of set theory,” J. Symbolic Logic, vol. 69, no. 3, pp. 775–789, 2004.
  3. J. D. Hamkins and C. Leahy, “Algebraicity and implicit definability in set theory,” Notre Dame J. Form. Log., vol. 57, no. 3, pp. 431–439, 2016.