18
$\begingroup$

It's well known and quite trivial that $\sf{ZF}$ with global choice is mutually interpretable with $\sf{ZF}$ plus a global wellordering. However, a much less obvious question is whether the two theories are bi-interpretable. The non-obvious nature of this question is revealed when investigating how exactly the mutual interpretation is conventionally performed.

When interpreting a global wellorder, assuming global choice, typically we apply the wellordering theorem. To be careful, each layer of the cumulative hierarchy is wellordered individually, and then all those wellorders can be concatenated into a global wellorder with the help of a global choice operator. The reverse interpretation is much simpler: given a global wellordering relation, the corresponding "$\min$" operation is immediately a global choice operation. These strategies are well known.

When considering the question of bi-interpretability however, an issue arises: the above mechanisms are not inverses! Composing the two interpretations does not necessarily lead to isomorphism. Indeed, a great many choice functions could lead to the exact same wellorder. Worse still, intuitively the vast majority of global choice functions will fail to agree with the $\min$ function of a wellorder. Similarly, the decision to construct the wellorder by stratifying $V$ via the cumulative hierarchy restricts our strategy to only construct setlike wellorders. In fact, all the wellorders we produce are rank-respecting.

To obtain bi-interpretability between Global Choice and a Global Wellordering, we would require something akin to a definable bijection between global choice functions and global wellorderings. My question is essentially whether this is possible.

If we augment $\sf{ZF}$ with a function symbol implementing Global Choice, is that bi-interpretable with the augmentation of $\sf{ZF}$ by a Global Wellorder relation?

To address the technicalities: the choice function is just a new symbol we add to the signature, and we assert axiomatically that it produces as output a member of the input set, provided the input is nonempty. Similarly the order relation is introduced as a new symbol, asserted to be a total order, and it's asserted to be a wellorder as a schema ranging over definable collections. In each case, the Replacement and Specification schemata are extended as expected, to include formulae with the new symbol.

EDIT: As pointed out in comments, the wellfoundedness schema ranging over classes is equivalent to the single statement ranging over sets. Each class can be partitioned into sets via rank, a minimum can be found in each rank, and the resulting transfinite sequence cannot descend infinitely (the image of an $\omega$-sequence without minimum is a set without minimum), so it converges discretely to a true minimum.


A slightly easier question is whether we get bi-interpretability by restricting the wellorder to be setlike. I suspect we can get an affirmative answer in that case, but I'm not sure yet. If we further require our wellorder to be rank-respecting, however, then I think I have a proof of bi-interpretation. To be precise, a wellordering relation $<$ is said to be rank-respecting precisely when the following holds, where $\operatorname{rank}(x)$ denotes the ordinal rank of the wellfounded set $x$. $$\operatorname{rank}(x)\subsetneq \operatorname{rank}(y) \implies x<y$$

The modified version of my question, where the wellorder is restricted to be rank-respecting, is stated below.

If we augment $\sf{ZF}$ with a Global Choice operator, is that bi-interpretable with $\sf{ZF}$ augmented by a rank-respecting Global Wellorder relation?

I've posted a proof of this modified question as a partial answer. However, my main question is what I'm really interested in, so my answer will remain unaccepted.

$\endgroup$
22
  • 2
    $\begingroup$ This is a great question. $\endgroup$ Commented yesterday
  • 1
    $\begingroup$ Choose a well-order of $V_{\alpha+1}\setminus V_\alpha$, then use those to well-order the universe lexicographically. $\endgroup$
    – Asaf Karagila
    Commented yesterday
  • 1
    $\begingroup$ @AsafKaragila That is how one usually makes a global well order from a global choice function, but the OP has already explained why this falls short of bi-interpretation. You need to define a global well-order which is equidefinable with the choice function and conversely, in a such a way that every global well-order arises. $\endgroup$ Commented yesterday
  • 2
    $\begingroup$ In particular, for a bi-interpretation, the definition of the well-order $\leq$ from the choice function $F$ must depend on every single value $F(x)\in x$, since otherwise there will be more than one $F$ giving rise to the same $\leq$, which prevents bi-interpretation. $\endgroup$ Commented yesterday
  • 2
    $\begingroup$ Global well-ordering can be expressed as a sentence rather than a schema. If every subset of a class order has a minimum, so does every subclass. $\endgroup$ Commented yesterday

2 Answers 2

15
$\begingroup$

The answer to the first question is yes: Global Choice is bi-interpretable with Global Well-Ordering.

First, I will prove that a class linear order $(C, <)$ is a well-ordering iff every subset (rather than every subclass) has a minimum. In particular, "Global Well-Ordering" can be expressed in a single sentence. Let $X \subset C$ be a proper class. Let $\kappa$ be such that $V_{\kappa} \prec_{\Sigma_2^{(C, X, <)}} V.$ Then $X \restriction V_{\kappa}$ has a minimum $x,$ which by elementarity, is minimal in $X.$

Now to construct the bi-interpretation. Our task is to construct, in a ZF-definable manner, a bijection between the hyperclass $\mathcal{F}$ of global choice functions and the hyperclass $\mathcal{W}$ of global well-orderings. We begin by constructing injections $i: \mathcal{F} \rightarrow \mathcal{W}$ and $j: \mathcal{W} \rightarrow \mathcal{F}.$ For $j,$ send a global well-ordering $<$ to the choice function which maps nonempty $X \rightarrow \min_{<}(X).$ For $i,$ let $F$ be a global choice function, and construct a rank-respecting global well-ordering $\prec$ by choosing well-orderings of each $V_{\alpha+1}\setminus V_{\alpha}.$ This is set-like, and thus defines a bijection $G: V \rightarrow \mathrm{Ord}.$ Code $(V, F)$ into a class of ordinals $C,$ in a manner which is absolute below every $\Sigma_2$-correct $\kappa.$ Defne $i(F)$ to be the well-ordering created by swapping $\omega \cdot \alpha$ with $\omega \cdot \alpha+1$ in $\prec$ for each $\alpha \in C.$ This is a set-like well-ordering which intersects every $V_{\alpha}$ for limit $\alpha$ in an initial segment.

We use a Cantor–Bernstein construction to extract a bijection $k$ between $\mathcal{F}$ and $\mathcal{W}.$ Let $F=F_0$ be a global choice function. We will construct a sequence of "candidate preimages," namely a sequence $<_{-1}, F_{-1}, <_{-2}, \ldots$ such that for every $n,$ if $F_{-n}$ is the image of some global well-ordering $\prec,$ then ${\prec} = {<}_{-n-1},$ and if $<_{-n}$ is the image of some global choice function $G,$ then $G=F_{-n}.$

Define $F_{-n}(X)=x$ if there are $\Sigma_2$-correct $\kappa> \mathrm{rk}(X),$ choice functions $G_{-n}, \ldots, G_0=F_0 \restriction V_{\kappa}$ on $V_{\kappa},$ and well-orderings $\prec_{-n}, \ldots, \prec_{-1}$ on $V_{\kappa}$ such that for each $m \le n:$

  1. $i^{V_{\kappa}}(G_{-m})={\prec}_{-m}$
  2. $j^{V_{\kappa}}(\prec_{-m})=G_{-m+1}$
  3. $G_{-n}(X)=x.$

Then $<_{-n}$ can be defined similarly.

Finally, we have $k$ send $F$ to $<_{-1}$ if there is there is $n$ such that $i(F_{-n}) \neq {<}_{-n}$ (or $F_{-n} \not \in \mathcal{F}$) and for each $m<n,$ $i(F_{-m})={<}_{-m}$ and $j(<_{-m-1})=F_{-m}.$ Otherwise, set $k(F)=i(F).$

$\endgroup$
5
  • $\begingroup$ Would I be correct in saying you'd get a CSB-like result for bijecting any two hyperclasses, where the hyperclasses and relevant meta-injections are defined without any higher-order quantifiers? By appealing to $\Sigma_n$-correct $\kappa$ as you do, where $n$ depends only on the hyperclasses and the injections between them. $\endgroup$ Commented 16 hours ago
  • $\begingroup$ There's probably some sort of meta-theorem you can get out of this but it would be pretty limited. The problem with what you have in mind is that we can only demand $\kappa$ be $\Sigma_n$-correct with respect to $(V, \in),$ not the hypothetical classes in question. So the meta-injections have to be such that they are absolute to each $\Sigma_n$-correct cardinal. $\endgroup$ Commented 16 hours ago
  • $\begingroup$ I was hoping you'd say that, although it means I don't really understand the role of $\Sigma_2$-correctness in your proof. Can you elaborate on the how (and why) $C$ is constructed from $(V,F)$? I think I understand the rest of the proof. $\endgroup$ Commented 15 hours ago
  • $\begingroup$ We have the rank-respecting bijection $G: V \rightarrow \mathrm{Ord}.$ Now $\in$ and $F$ are subclasses of $\mathrm{Ord}^2,$ which can together be encoded by a single subclass of Ord by say Gödel pairing. This is absolute below $\Sigma_2$-correct cardinals. $\endgroup$ Commented 15 hours ago
  • $\begingroup$ Very nice, Elliot. I see now that because the injections both ways are completely local, it solves the complexity blow-up I was concerned about. This method seems very general for other kinds of bi-interpretability, since in general such transformations of class objects will be local in that way relative to $\Sigma_n$-correct cardinals for some fixed $n$. $\endgroup$ Commented 9 hours ago
6
$\begingroup$

This is an answer to the second question, proving Global Choice is bi-interpretable with a rank-respecting Global Wellorder. This is intuitively the same as finding a definable bijection between the two relevant hyperclasses.

Our strategy is inspired by the fact each global wellorder can be expressed as a concatenation of its restrictions to each rank of the cumulative heirarchy, the sets $V_{\alpha+1}\setminus V_\alpha$. Similarly, each global choice function can be expressed as a union of its restrictions to each rank domain. This decomposition allow us to represent our hyperclasses as products of sets, indexed by the ordinals. This works since the behavior of a choice function/wellorder within one rank is completely independent to its behavior in some other rank.

Ideally we can find, for each rank $\alpha$, a specific bijection between the corresponding factors of the above product representations. If this can be done by a single formula (parameterized by $\alpha$), then we can produce a bijection of the relevant hyperclasses using their product representation, leading to an explicit bi-interpretation. As-is, this strategy runs into numerous difficulties. Instead, we use a slightly modified strategy where the decomposition is broken up only at limit ranks.


Bijecting the factors

Our technique relies on the fact that the Schroder-Bernstein theorem is roughly constructive. That is, the following fact should be a corollary of the typical Schroder-Bernstein proof.

There's a set-theoretic formula $\phi(f,g,h)$ such that $\sf{ZF}$ proves: if $f,g$ are injections where both $\operatorname{ran}(g)\subseteq \operatorname{dom}(f)$ and $\operatorname{ran}(f)\subseteq \operatorname{dom}(g)$, then there's a unique $h$ such that $\phi(f,g,h)$, and this unique $h$ bijects $\operatorname{dom}(f)\to \operatorname{dom}(g)$.

Let $\mathcal{S}(f,g)=h$ denote the Schroder-Bernstein function just described, so now we just need to construct some injections.

For any ordinal $\alpha$, let $\mathcal{W}_\alpha$ denote the set of rank-respecting non-strict wellorders of $V_\alpha$, and let $\mathcal{C}_\alpha$ denote the set of choice functions with domain $V_\alpha\setminus\{\emptyset\}$. Notice that each $C\in\mathcal{C}_{\alpha+\omega}$ can be restricted to some $c=C\restriction_{V_\alpha}$, where $c\in \mathcal{C}_\alpha$. This method induces a partition of $\mathcal{C}_{\alpha+\omega}$ based on which functions have the same restrictions. A similar phenomenon happens with $\mathcal{W}$, so we consider the following definitions of those equivalence classes. $$\begin{align} [c]&:=\{C\in\mathcal{C}_{\alpha+\omega} : C\restriction_{V_\alpha}=c\} \\ [w]&:=\{W\in\mathcal{W}_{\alpha+\omega} : W\restriction_{V_\alpha}=w\} \end{align}$$

We first construct $F_{\alpha,w,c}$ injecting $[w]\to [c]$. To do this, for each $W\in [w]$ we define $F_{\alpha,w,c}(W)$ by first taking the $\min$ function of $W$, restricting its domain to $V_{\alpha+\omega}\setminus V_\alpha$, and then extending that by $c$ to get a choice function with domain $V_{\alpha+\omega}\setminus\{0\}$. Where $C=F_{\alpha,w,c}(W)$, we get $C\in \mathcal{C}_{\alpha+\omega}$ simply because $C$ extends $c$. This $F_{\alpha,w,c}$ function is injective, demonstrable by recovering $W$ from $C$. Since $W$ extends $w$, we need only consider $a,b\in V_{\alpha+\omega}\setminus V_\alpha$. We recover the $W$-order of $a,b$ by consequence of $W$ being rank-respecting, proven by letting $\beta=\max(\operatorname{rank}(a),\operatorname{rank}(b))$ and observing the following. $$\begin{align} (a,b)\in W &\iff a=\min{}_W(a,b) \\ &\iff a=\min{}_W(\{a,b\}\cup V_{\beta+2}\setminus V_{\beta+1}) \\ &\iff a=C(\{a,b\}\cup V_{\beta+2}\setminus V_{\beta+1}) \end{align}$$

With more difficulty, we now construct $G_{\alpha,w,c}$ injecting $[c]\to[w]$. Fix any $C\in [c]$, so that $C$ is a choice function on $V_{\alpha+\omega}\setminus\{0\}$ extending $c$. Since $\alpha+\omega$ is a limit ordinal, an easy corollary of the wellordering theorem will construct an explicit parameter-definable function $g_{\alpha,w,c}$ sending $[c]\to [w]$. That function isn't injective, but it can be used to construct $G$. We'll assume we're using Kuratowski's ordered pair, which obeys $\operatorname{rank}((x,y))=\max(\operatorname{rank}(x),\operatorname{rank}(y))+2$ in full generality, hence any pair $(S,x)$ having $x\in S$ will obey $\operatorname{rank}((S,x))=\operatorname{rank}(S)+2$.

For each $S\in\operatorname{dom}(C\setminus c)$, we can let $q_S=(S,C(x))$, and find $p_S=\min_g\{(S,x) : x\in S\}$. Finally, define the wellorder $G_{\alpha,w,c}(C)$ as a modification of $g_{\alpha,w,c}(C)$ formed by permuting $p_S$ with $q_S$, for every $S\in\operatorname{dom}(C\setminus c)$. These permutations don't conflict, so we can apply all of them simultaneously to obtain a well-defined wellorder. We only permute terms of equivalent rank, so the resulting wellorder is still rank-respecting. Finally, we only permute terms with rank at least $\alpha$, so the resulting wellorder is still an extension of $w$. In other words, $G_{\alpha,w,c}(C)$ is a member of $[w]$ as required. This $G_{\alpha,w,c}$ is injective since, for any $S\in\operatorname{dom}(C\setminus c)$, the following holds by consequence of our permuting $p_S$ with $q_S$. $$(S,C(S))=\min{}_G\{(S,x) : x\in S\}$$

Note that everything we've done so far works even if $\alpha=0$. To complete this segment of the proof, let $H_{\alpha,w,c}=\mathcal{S}(F_{\alpha,w,c},G_{\alpha,w,c})$, so that $H_{\alpha,w,c}$ is a bijection $[w]\to[c]$. Notice that $[w]$ is trivially in bijection with the set of rank-respecting wellorders on the domain $V_{\alpha+\omega}\setminus V_\alpha$, where the bijection just takes each $W\in[w]$ and deletes the initial segment $w$. A similar phenomenon holds for $[c]$, so the set of wellorders with domain $V_{\alpha+\omega}\setminus V_\alpha$ are in bijection with the set of choice functions on the same domain. This gives a bijection between the factors, as we needed, but now we've got these extra $w,c$ parameters to worry about. Fortunately, this won't affect the strategy too much.


The bijection between hyperclasses

Define, for each non-successor $\lambda$, a bijection $B_\lambda:\mathcal{W}_\lambda \to \mathcal{C}_\lambda$. This is done via transfinite recursion on $\lambda$, using the following rules. $$\begin{align} B_0(\emptyset) &:= \emptyset &\\ B_{\lambda+\omega} &:= \bigcup\{H_{\lambda,w,B_\lambda(w)} : w\in\mathcal{W}_\lambda\} \\ B_{\mu}(W) &:= \bigcup\{B_\lambda(W\restriction_{V_\lambda}) : \lambda<\mu\} \text{ whenever $\mu$ is a limit of limits.} \end{align}$$

We can verify that each $B_\lambda$ is a bijection on the required domain, and moreover they're compatible with restrictions in the sense that $B_\lambda(W)\restriction_{V_\mu} = B_\mu(W\restriction_\mu)$ for $\lambda<\mu$. This works trivially in the base case $\lambda=0$, since $V_0=\emptyset$ and thus $\mathcal{W}_0=\mathcal{C}_0=\{\emptyset\}$.

Assuming $B_\lambda$ is a bijection, we have $B_{\lambda+\omega}$ being the union of all the $H_{\lambda,w,B_\lambda(w)}$ bijections. These all have disjoint domains, so $B_{\lambda+\omega}$ is at least an injective function. That $B_{\lambda+\omega}$ is bijective onto $\mathcal{C}_{\lambda+\omega}$ holds since the codomain is the union of the $[B_\lambda(w)]$ equivalence classes, and bijectivity of $B_\lambda$ onto $\mathcal{C}_\lambda$ guarantees that the aforementioned union is exactly $\mathcal{C}_{\lambda+\omega}$. The restriction-compatability condition is preserved during the successor stage, since we just have $B_{\lambda+\omega}(W) = H_{\lambda,w,c}(W)$ where $w=W\restriction_{V_\lambda}$ and $c=B_\lambda(c)$, and therefore $B_{\lambda+\omega}(W)\restriction_{V_\lambda} = c = B_\lambda(W\restriction_{V_\lambda})$.

Finally, the restriction-compatibility condition guarantees that $B_\mu$ is a well-defined bijection during the limit stages of the recursion, and compatibility is also clearly preserved at the limit step. That $B_\mu$ is bijective follows since we can construct an explicit inverse, having almost identical structure, as below. $$B_\mu^{-1}(C) = \bigcup\{B_\lambda^{-1}(C\restriction_{V_\lambda}) : \lambda<\mu\}$$

The logic behind limit stages extends directly to proper classes. Given any global wellordering relation $<$, we can define a global choice function $\mathfrak{c}$ as follows. $$\mathfrak{c}(S)=B_\lambda(\{(x,y)\in V_\lambda : x<y\})(S) \hspace{12mm}\text{where $\lambda>\operatorname{rank}(S)$ is a limit}$$

This gives an interpretation of Global Choice. Conversely, Global Choice interprets a Global Wellorder by defining the relation $<$ as follows. $$x<y \iff (x,y)\in B_\lambda^{-1}(\mathfrak{c}\restriction_{V_\lambda}) \hspace{12mm} \text{where $\lambda>\operatorname{rank}(x,y)$ is a limit.}$$

It's seen that these two interpretations invert each other, and so we have a bi-interpretation.

$\endgroup$
3
  • 1
    $\begingroup$ Can you just use a flat pairing function and avoid all the $+\omega$ and $+2$ stuff? There is a definable pairing function for which $V_\alpha=V_\alpha\times V_\alpha$ for all infinite $\alpha$. $\endgroup$ Commented 22 hours ago
  • 1
    $\begingroup$ @JoelDavidHamkins The +2 is needed for the finite ranks, but otherwise it's unnecessary; could be avoided by handwaving the finite ranks and using type-level pairing. The $+\omega$ is necessary to handle a seemingly unavoidable off-by-one discrepancy. Conventionally, you need a choice function with domain $V_{\alpha+1}^*$ to generate a wellorder of $V_\alpha$. For limit $\lambda$, this leaves the choice functions with domain $V_{\lambda+1}\setminus V_\lambda$ left out. $\endgroup$ Commented 22 hours ago
  • 1
    $\begingroup$ The usual argument shows that every choice function on $V_\lambda$ for a limit $\lambda$ gives a well order on $V_\lambda$. Namely, the next element in the well order is chosen from the set of minimal-rank elements not yet placed on the order. I think your argument can be greatly simplified. You don't need the equivalence classes $[c]$, $[w]$, etc. Just work along a club of limit ordinals. We can even take $\lambda$ to be beth fixed points, etc., if that would be convenient, or even $\Sigma_2$-correct, as in the idea suggested by Elliot. $\endgroup$ Commented 21 hours ago

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .