10
$\begingroup$

It is known that locally one can ``code'' any set in the von Neumann universe $V$ by a set of ordinals. But can one do this globally? In other words, is there a first-order definable bijection $P(On) \longrightarrow V$, where $P(On)$ is the class of all subsets of the class $On$ of all ordinals?

Note that $P(On)$ is in natural bijection with the ordered field $No$ of surreal numbers. Thus, the question is equivalent to: Is there a first-order definable bijection $No \longrightarrow V$?

If we assume $V = HOD$, then indeed there a first-order definable bijection $No \longrightarrow V$ (since $V = HOD$ is equivalent to the existence of a first-order definable bijection $On \longrightarrow No$ (or $On \longrightarrow V$); see Definable map from all the ordinals to the surreal numbers with a dense image?) However, I would be surprised if the converse were also true. It seems like the existence of a first-order definable bijection $No \longrightarrow V$ (or $P(On) \longrightarrow V$) should be weaker than $V = HOD$ but still perhaps not provable in ZFC.

EDIT: Given Andreas Blass' answer that the statement is indeed independent of ZFC, I'm still wondering whether or not any of the implications $(1) \Rightarrow (2) \Rightarrow (3)$ are reversible, where the respective statements are (1) $V = HOD$, (2) there is a definable bijection $P(On) \longrightarrow V$, and (3) there is a definable linear ordering of $V$.

$\endgroup$
  • $\begingroup$ Essentially a duplicate, maybe, mathoverflow.net/questions/110799/… $\endgroup$ – Asaf Karagila Dec 8 '14 at 7:04
  • $\begingroup$ I'm wondering its strength relative to $V = HOD$, so it's not a complete duplicate I think. $\endgroup$ – Jesse Elliott Dec 8 '14 at 7:55
  • $\begingroup$ Yeah, given the edit it's less duplicate. :-) $\endgroup$ – Asaf Karagila Dec 8 '14 at 8:38
13
$\begingroup$

I will use $(1)$, $(2)$, and $(3)$ as defined in the EDIT to the question.

It is known that $(1)\Rightarrow (2)$ does not reverse over ZF, indeed, by a result due to Solovay (appearing as Theorem 3.3 of my paper below) if ZF is consistent, then there is a model of ZF + $(2)$ + $\lnot$ AC, which shows that over ZF the implication $(1) \Rightarrow (2)$ does not reverse.

The status of the above failure of reversibility over ZFC (as opposed to ZF), as well as the reversibility-status of $(2) \Rightarrow(3)$ over ZF or ZFC, were posed in a 2004-paper of mine (see Conjecture 4.3.2 of the paper below), and remain open.

More detail: my paper The Leibniz-Myscielski Axiom in Set Theory (Fund. Math. 181, 2004, pp.215-231) shows that the existence of an injection (equivalently: a bijection) of V into P(Ord) is equivalent to a "logical" principal dubbed LM (for Leibniz-Mycieslki), where:

LM:$\ \ \ \forall x\forall y$ $[x\neq y\rightarrow\exists\alpha>\max \{\rho(x),\rho(y)\}$ $Th(V_{\alpha},\in,x)\neq Th(V_{\alpha},\in,y)].$

In the above, $\rho(x)$ is the ordinal-valued set theoretic rank of $x$, and $Th(V_{\alpha},\in,x)$ is the first order theory of the structure $(V_{\alpha},\in,x)$.

LM captures the spirit of Leibniz's principle on the identity of indiscernibles because, by a theorem of Mycielski, a consistent T completion of ZF includes LM iff T has a $\cal{M}$ model with no indisceribles , i.e., if $a$ and $b$ are a pair of distinct elements of $\cal{M}$, then there is a formula $\phi(x)$ in the language of set theory such that $\cal{M}\models\phi(a)\land\lnot\phi(b)$.

As shown in the aforementioned paper, the existence of an injection from V into P(Ord) is also equivalent with the global version of the Kinna-Wagner Selection Principle, in other words, models of ZF + LM are precisely models of ZF in which there is a definable class function $\mathbf{F}$ that "chooses" a proper nonempty subset from each set with at least two elements, i.e., $\forall x(\left| x\right| \geq2\rightarrow \emptyset\neq\mathbf{F}(x)$ $\subsetneq x);$

$\endgroup$
7
$\begingroup$

$\mathcal P(\text{On})$ has a definable linear ordering, namely the lexicographical one: One set $x$ of ordinals precedes another set $y$ of ordinals iff the first element of their symmetric difference is in $y$. But $V$ need not have a definable linear ordering; indeed, even a very small part of $V$, the power set of the real line, need not have a definable linear ordering. So there need not be a definable bijection between $\mathcal P(\text{On})$ and $V$ (nor even a definable injection from $V$ into $\mathcal P(\text{On})$).

$\endgroup$
  • $\begingroup$ This shows that (1) implies (2) implies (3), where the respective statements are (1) $V = HOD$, (2) there is a definable bijection between $V$ and $P(On)$, and (3) there is a definable linear ordering of $V$. But are any of these implications reversible? $\endgroup$ – Jesse Elliott Dec 8 '14 at 7:06
6
$\begingroup$

$\newcommand\Ord{\text{Ord}}\newcommand\HOD{\text{HOD}}$Let me point out that the existence of a definable bijection of $V$ with $P(\Ord)$ is equivalent to the assertion that the universe is Leibnizian over the ordinals, that is, that any two distinct sets $a\neq b$ satisfy different formulas with ordinal parameters.

This is proved in Ali Enayat's fine paper, On the Leibniz-Mycielski axiom in set theory, where he discusses a variety of issues surrounding this axiom.

For the forward implication, suppose that we have a definable bijection of $V$ with $P(\Ord)$, given by a specific definition. Thus, to every object $a$ we have definably associated a distinct set $F(a)\subset\Ord$. In particular, if $a\neq b$, then there is some ordinal $\alpha$ such that $\alpha\in F(a)$ and $\alpha\in F(b)$ get different truth values, which establishes that the types of $a$ and $b$ over the ordinals are different. We could have even allowed that the bijection was definable with ordinal parameters.

Conversely, suppose that the universe is Leibnizian over the ordinals. This means that whenever $a\neq b$, then there is some formula $\varphi$ and ordinal parameters $\vec\alpha$ such that $\varphi(a,\vec\alpha)$ is true and $\varphi(b,\vec\alpha)$ is false. By reflection, there is some ordinal $\theta$ such that $a,b,\vec\alpha\in V_\theta$ and $\varphi$ is absolute to $V_\theta$. Thus, we have $V_\theta\models\varphi(a,\vec\alpha)$ and $V_\theta\models\neg\varphi(b,\vec\alpha)$. Since $V_\theta$ is $\Pi_1$ definable, this shows that $a$ and $b$ have different $\Sigma_2$ formulas with the parameters $\varphi,\vec\alpha$ and $\theta$. (In particular, because we have bounded the complexity of the formula this way, this shows that being Leibnizian over the ordinals is first-order expressible in ZFC.) For each object $a$, let $\theta_a$ be the next $\Sigma_3$-correct ordinal beyond the rank of $a$, and let $T_a$ be the type of $a$ in $V_\theta$ over ordinal parameters less than $\theta$. Thus, $T_a$ is the set of tuples $\langle\varphi,\vec\alpha\rangle$ such that $V_{\theta_a}\models\varphi(a,\vec\alpha)$. Since any $\Sigma_2$ assertion about $a$ will reflect below $\theta_a$, it follows from the Leibnizian assumption that $a\neq b$ implies $T_a\neq T_b$. Further, since $T_a$ is a set of tuples of formulas and ordinals, we may by Gödel coding view $T_a$ as a set of ordinals. Thus, we have defined an injective map $a\mapsto T_a$ of $V$ into $P(\Ord)$, as desired.

In the Leibnizian property, we may fold the ordinal parameters $\vec\alpha$ into the ordinal $\theta$, by making $\vec\alpha$ definable in $V_\theta$, and say it equivalently like this: for any $a\neq b$, there is some ordinal $\theta$ and formula $\varphi$ for which $V_\theta\models\varphi(a)\wedge\neg\varphi(b)$. This is what Enayat calls the Leibniz-Mycielski axiom LM.

At that the conclusion of that paper, he conjectures that the implication $V=\HOD$ to LM is not reversible.

$\endgroup$
  • $\begingroup$ Joel, I noticed your answer after composing mine. Thanks for providing a synopsis of my work. $\endgroup$ – Ali Enayat Dec 8 '14 at 18:24
  • $\begingroup$ Sure, it is very nice paper! And a nice question about the ZFC case. I spent the whole morning thinking about it... $\endgroup$ – Joel David Hamkins Dec 8 '14 at 18:25
  • $\begingroup$ Does the proof of this equivalence go through over ZF? $\endgroup$ – Jesse Elliott Dec 8 '14 at 23:12
  • $\begingroup$ @Jesse: yes, the equivalence mentioned by Joel, as well as the one mentioned in my answer, go through over ZF. $\endgroup$ – Ali Enayat Dec 8 '14 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.