Ehrenfeucht principles in set theory

This is a talk at the British Logic Colloquium in Cambridge, UK, September 2-4, 2015.
Slides

Ehrenfeucht's lemma: If $a\neq b$ are elements of a model $M\models{\rm PA}$, and $b$ is definable from $a$ in $M$, then $a$ and $b$ must have different types.

Ehrenfeucht's lemma can be used to show, for example, that if a model $M\models{\rm PA}$ is the Skolem closure of a single element $a$, $M={\rm Scl(\{a\})}$, then it has no non-trivial automorphisms. Since every element of $M$ is definable from $a$, $a$ is the unique element of its type and therefore any automorphism must map $a$ to $a$, thereby fixing everything. It is not difficult to see why Ehrenfeucht's lemma holds for models of ${\rm PA}$. Suppose $b$ is definable from $a$ in $M\models {\rm PA}$. By tweaking the definition slightly, we can assume that there is a definable function $f(x)$ such that $f(a)=b$. First, suppose that $a<b$. Consider the definable (undirected) graph $G$ consisting of all pairs $\{x,y\}$ such that $f(x)=y$ and $x<y$. The pair $\{a,b\}\in G$. Because ${\rm PA}$ proves that $<$ is a well-order, $G$ is loop-free. Let $c$ be the $<$-least element connected to $a$. Then $c$ is also the $<$-least element connected to $b$. But the shortest distance from $a$ to $c$ differs by $1$ from the shortest distance from $b$ to $c$, and so one is even if and only if the other is odd. The case $b<a$ uses the same idea.

Historically, there has been a very fruitful exchange of concepts, methods, and techniques between model theory of models of arithmetic and model theory of models of set theory. So it was natural to ask about Ehrenfeucht's lemma for models of set theory. An identical argument to the one given above shows that if $V\models{\rm ZF}$ has a definable global well-ordering ($V={\rm HOD}$), then Ehrenfeucht's lemma holds. More generally, it shows that in any $V\models{\rm ZF}$, Ehrenfeucht's lemma holds for ordinal definable sets. In [2], we showed that in general Ehrenfeucht's lemma can fail for a model of set theory. Indeed it fails in a very strong way in any Cohen forcing extension.

Theorem: Every Cohen forcing extension $V[c]$ has $a\neq b$ that are inter-definable and have the same type, even with parameters from $V$.

It is easy to see that the Cohen poset is isomorphic to the $\omega$-fold finite-support product of Cohen forcing. Let $G$ be $V$-generic for the $\omega$-fold finite-support product of Cohen forcing and let $\langle c_i\mid i<\omega\rangle\in V[G]$ be the Cohen reals on the coordinates of $G$. In $V[G]$, let $C=\{c_i\mid i<\omega\}$, let $E=\{c_{2i}\mid i<\omega\}$ be Cohen reals on even coordinates, and let $O=\{c_{2i+1}\mid i<\omega\}$ be Cohen reals on odd coordinates. The pairs $\langle C,E\rangle$ and $\langle C,O\rangle$ are obviously inter-definable in $V[G]$, and an automorphism argument shows that they have the same type (even with parameters from $V$) in $V[G]$. From what is known so far, it is possible that Ehrenfeucht's lemma holds precisely when $V={\rm HOD}$. This question is completely open.

Question: Does Ehrenfeucht's lemma imply $V={\rm HOD}$ in models of ${\rm ZF(C)}$?

By considering parametric versions of Ehrenfeucht's lemma, we arrived at a collection of principles, which we call Ehrenfeucht principles, a scheme that captures several interesting properties of models of set theory. We say that the Ehrenfeucht principle ${\rm EL}(A,P,Q)$ holds for a model $V\models{\rm ZF}$ and $A,P,Q\subseteq V$ if for every $a\in A$, if $b\neq a$ is definable from $a$ using parameters in $P$, then $a$ and $b$ have different types with parameters in $Q$. In short, $P$-definability implies $Q$-discernibility. In this new scheme, the original Ehrenfeucht's lemma is ${\rm EL}(V,\emptyset,\emptyset)$ and we know that ${\rm EL}({\rm OD},\emptyset,\emptyset)$ holds in every $V\models{\rm ZF}$. We also know that ${\rm EL}(V[c],\emptyset,V)$ fails in any Cohen extension $V[c]$. Let's consider some other notable Ehrenfeucht principles. The principle ${\rm EL}(V,{\rm ORD},{\rm ORD})$ states that if $a\neq b$ and $b$ is definable from $a$ with ordinal parameters, then $a$ and $b$ have differen types with ordinal parameters. We can think of ${\rm EL}(V,{\rm ORD},{\rm ORD})$ as a first-order expressible version of Ehrenfeucht's lemma. The principle ${\rm EL}(V,V,\emptyset)$ states that any $a\neq b$ have different types, e.g. there are no indiscernibles. Ali Enayat calls such models Leibnizian in honor of Leibniz who posited in his Identity of Indiscernibles principle that any two objects must differ on some property. The property of being Leibnizian is not first-order (Ehrenfeucht and Mostowski showed that every first-order theory $T$ with an infinite model, has a model with indiscernibles), but it is closely related to a first-order property that Enayat has called the Leibniz-Mycielski axiom.

Leibniz-Mycielski axiom: (${\rm LM}$) Any two $a\neq b$ have different types in some $V_\alpha$.

Mycielski showed in [3] that a theory $T$ extending ${\rm ZF}$ has a Leibnizian model if and only if it proves ${\rm LM}$. It is not difficult to see that ${\rm LM}$ is itself equivalent to the principle ${\rm EL}(V,V,{\rm ORD})$ which states that any $a\neq b$ have different types with ordinal parameters. Thus, a theory $T$ has a model in which distinct elements have different types if and only if in every model of $T$ distinct elements have different types with ordinal parameters.

The Leibniz-Mycielski axiom is equivalent over ${\rm ZF}$ to the existence of a definable injection from $V$ into subsets of ordinals [4]. In particular, it implies that there is a definable global linear-ordering of $V$, and so we can think of it as a weak global choice principle. Easton first showed in his dissertation that there are models of ${\rm ZFC}$ without a definable global linear-ordering (see this MO post for Hamkins' argument). It is not known whether ${\rm LM}$ implies the existence of a definable global well-ordering of $V$ over ${\rm ZFC}$ and this is a major open question.

Question: Does ${\rm LM}$ imply over ${\rm ZFC}$ that $V$ has a definable global well-ordering?

A very related open question is whether there is a model of ${\rm ZFC}$ with a definable global linear-ordering, but not a definable global well-ordering (see this MO post).

Question: Is there a model $V\models{\rm ZFC}$ with a definable global linear-ordering, but no definable global well-ordering?

Solovay showed that over ${\rm ZF}$, ${\rm LM}$ doesn't even imply countable choice [4]. The argument proceeds by forcing to add $\omega$-many Jensen reals (with finite-support) over $L$ and then showing that $L(S)$, where $S$ is the collection of the $\omega$-many Jensen reals from the generic filter, is a model of ${\rm LM}$, but not of countable choice. This uses a key property of Jensen reals that $S$ is definable. Jensen's forcing adds a unique generic real over $L$ and a (modern) way to see that $S$ is definable is to use a recent theorem of Kanovei showing that the Jensen reals added by an $\omega$-fold finite-support product over $L$ are precisely the reals on the coordinates of the generic filter [5].

References

1. A. Ehrenfeucht, “Discernible elements in models for Peano arithmetic,” J. Symbolic Logic, vol. 38, pp. 291–292, 1973.
2. 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.
3. J. Mycielski, “New set-theoretic axioms derived from a lean metamathematics,” J. Symbolic Logic, vol. 60, no. 1, pp. 191–198, 1995.
4. A. Enayat, “On the Leibniz-Mycielski axiom in set theory,” Fund. Math., vol. 181, no. 3, pp. 215–231, 2004.
5. V. G. Kanovei and V. A. Lyubetski, “A definable countable set containing no definable elements,” Mat. Zametki, vol. 102, no. 3, pp. 369–382, 2017. Available at: https://doi.org/10.4213/mzm10842