4
$\begingroup$

$\textbf{Logic:}$ Mono-sorted first order logic with equality.

$\textbf{Extralogical Primitives: } <, \in$

Define: $x > y \iff y < x \\ x \leq y \iff x < y \lor x=y \\ x \not > y \iff \neg \, x > y $

$ \textbf{Axioms:}$

  • $ \begin{align} \textbf{Order: } & x \not < x \\ & x < y < z \to x < z \\ & y \in x \to \exists l \in x \forall m \in x : l \leq m \end{align} $

  • $\textbf{Sets: } \forall n \exists! x \forall m \, (m \in x \leftrightarrow m \not > n \land \phi)$, if $x$ is not free in formula $\phi$

  • $\textbf{Respective: } x \in y \to x < y$

  • $\textbf{Hyper-respective: } \forall m \in x (m < z) \land z \in y \to x < y$

  • $ \textbf{Infinity:} \exists l \neq 0 \forall x < l \exists y < l: x < y $

  • $ \begin {align} \textbf{Boundedness: } & \pi: \phi \to \psi \ \land \\ & \pi \text { is 1-1 } \ \land \\ & \forall m: \phi(m) \to m < x \\ & \to \\ & \exists y \forall n: \psi(n) \to n < y \end{align} $

Where $\pi,\phi,\psi$ are predicates definable by formulae not using "$y$".

Is this theory synonymous with $\sf ZF + GC$?

Where $\sf GC$ is Global Choice, formalized by adding a total unary function $c$ to the signature of $\sf ZF$, and add the axiom that $c(\varnothing)=\varnothing$ and the axiom that for each nonempty set $x$ we have $c(x) \in x$.

$\endgroup$
5
  • $\begingroup$ I think this question is much deeper than it was intended to be. The theory $\sf{ZF}+\text{"global choice"}$ doesn't have an obvious synonymity with the theory $\sf{ZF}+\text{"global wellordering"}$. The usual method for constructing a wellorder using a Choice function is not invertible, as many different choice functions lead to the same wellorder, so proving synonymity seems unusually difficult. Would I be correct in saying that the intended question is: can we find a mutual interpretation where the membership relation is standard in both cases? $\endgroup$ Commented 2 days ago
  • $\begingroup$ what about if we ask about ZF+ global well ordering and this theory. Both theories are in the same language, so perhaps the question about their synonymy is easier? $\endgroup$ Commented yesterday
  • $\begingroup$ I think that might make it harder. To prove synonymity of two theories, you basically need (among other things) to find a bijection between the class of all models of one theory to the class of all models of the other. Your theory has fewer ($\subseteq$) models than $\sf{ZF}+\text{"global wellorder"}$, so finding a synonymity is nontrivial. I think you can prove synonymity to the theory $\sf{ZF}+\text{"global wellorder"}$ plus the axiom $\sup\{x+1 : x\in S\}<\sup\{x+1 : x\in Z\}\implies S<Z$, where $x+1$ denotes the order-theoretic successor defined in terms of $<$ $\endgroup$ Commented yesterday
  • $\begingroup$ That said, I've started to think you can actually find the desired synonymity, but it's much more complicated than what you probably had in mind for your question. Basically, you can show synonymity of your theory with that modified theory I mentioned, and that theory (I think) can then be proven synonymous with $\sf{ZF}+\text{"Global Choice"}$ using a separate mechanism. I'm working on writing a proof of that secondary synonymity, and will post it as a separate question when done, and then link to that as part of an answer to yours. $\endgroup$ Commented yesterday
  • 1
    $\begingroup$ @JadeVanadium, hmmm... from Eliot's proof of bi-interpretability of global choice and global well order presented to your other thread, it appears that a positive answer to this question is possible? $\endgroup$ Commented 13 hours ago

1 Answer 1

3
$\begingroup$

Yes, this theory is synonymous with $\sf{ZF}$ plus global choice. Explicitly, we'll prove direct equivalence to the theory: $\sf{ZF}$ plus a global wellorder $<$, plus the following two axioms. $$\operatorname{rank}(x)\subsetneq \operatorname{rank}(y) \implies x<y \tag{Ax1}$$ $$\sup\{\operatorname{S}(x) : x\in A\}<\sup\{\operatorname{S}(x) : x\in B\} \implies A<B \tag {Ax2}$$ $$\operatorname{S}(x) := \min\{y : x<y\}$$

Basically, axiom 1 just says $<$ is rank-respecting. For any such wellorder, we can also consider the function $A\mapsto \sup\{\operatorname{S}(x) : x\in A\}$, and the universe can be partitioned into a wellordered hierarchy based on the output of that function. Axiom 2 simply says that $<$ respects the aforementioned stratification in the same way that it respects rank.

Once we've proven direct equivalence between your theory and mine, the desired synonymity can be proven using the same basic techniques outlined in this answer by Elliot. Basically, it's not terribly difficult to show that a global choice function can induce a global wellorder obeying my axioms 1 and 2, and there's enough freedom in how each stratum is constructed to produce a bi-interpretation using the same kind of Cantor-Bernstein tactic used by Elliot.


To prove equivalence, we notice that my axiom 1 proves Respective, and moreover that Hyper-respective is logically equivalent to axiom 2, as follows.

$$\begin{align} &\forall z, (((\forall(m\in x), m<z)\land z\in y) \implies x<y) \\ &(\exists z,(\forall(m\in x), m<z)\land z\in y) \implies x<y \\ &(\exists(z\in y), \forall(m\in x), m<z)\implies x<y \\ &(\exists(z\in y), \sup\{\operatorname{S}(m) : m\in x\}\leq z)\implies x<y \\ &\sup\{\operatorname{S}(m) : m\in x\}<\sup\{\operatorname{S}(m) : m\in y\}\implies x<y \end{align}$$

The rest of your axioms are trivial consequences of my theory, so mine proves yours. To show that your theory proves mine, we'll show that yours proves all the axioms of $\sf{ZF}$ with a setlike global wellorder. After that, we recover my axiom 2 using the same equivalence just described. Finally, it turns out that my axiom 2 just implies axiom 1 outright, so your theory proves mine. The proof of axiom 1 using axiom 2 is described below, and after that we'll show how your theory proves the axioms of $\sf{ZF}$ with a setlike global wellorder.

Assuming $\sf{ZF}$ with a global setlike wellorder and axiom 2, we prove $\forall x,\forall y, \operatorname{rank}(x)\subseteq \alpha\subsetneq\operatorname{rank}(y) \implies x<y$ for all ordinals $\alpha$, where $\subsetneq$ is (equivalent to) the standard order relation on the ordinals. By contradiction suppose not, then let $\alpha$ be an inclusion-minimal counter example. Since $\operatorname{rank}(y)\supsetneq\alpha$, we can find $t\in y$ with $\operatorname{rank}(t)\supseteq \alpha$. By contrast, all $m\in x$ must have $\operatorname{rank}(m)\subsetneq \operatorname{rank}(x)\subseteq \alpha$. If we label $\beta=\operatorname{rank}(m)$ then $\beta\subsetneq \alpha$, and by minimality of $\alpha$ we infer $\operatorname{rank}(m)\subseteq\beta\subsetneq\operatorname{rank}(t) \implies m<t$, hence we actually have $m<t$ for all $m\in x$. It follows that $\sup\{\operatorname{S}(m) : m\in x\}\leq t < \sup\{\operatorname{S}(t) : t\in y\}$, which guarantees $x<y$ via axiom 2. This contradicts the premise of having a counter example, so no counter examples exist and axiom 1 is proven.


Extensionality and Specification are easy consequences of the Sets and Respective axioms. For any set $y$, there's a unique set $x$ where generally $m\in x \iff (m\not>y \land (m\in y\land \phi))$. Notice that $m\in y \implies m<y \implies m\not>y$, where the first implication follows from Respective, and the second follows from Ordering. This makes the term $m\not>y$ redundant in the earlier formula, so it simplifies to $\exists!x, \forall m, m\in x \iff (m\in y \land \phi)$. The existence of such $x$ implies Specification directly. In the special case where $\phi$ is a tautology, the uniqueness of $x$ implies Extensionality.

To prove $<$ is a global wellorder, we just prove it's trichotomous. Given any $a,b$ such that $\neg(a\leq b)$, use Sets to construct $x=\{m\not>a : m=a\lor m=b\}$. We have $b\not >a$ by premise, and $a\not>a$ by Ordering, so then $x=\{a,b\}$. Now apply Ordering to find $m\in\{a,b\}$ obeying $m\leq a$ and $m\leq b$, and since $\neg(a\leq b)$ then $m=b$ and so $b\leq a$. It follows deductively that $\neg(a\leq b) \implies b\leq a$ for all $a,b$, which is equivalent to Trichotomy. Along with Ordering, this proves $<$ is a global wellorder.

Moreover we see $<$ is setlike, by consequence of Sets. Indeed, for any $n$ we find a set $x=\{m\leq n : \phi\}$, and taking $\phi$ to be a tautology implies $\{m : m\leq n\}$ is a set, so $<$ is setlike.

Pairing is now trivial, $\{x,y\}=\{m\not>z : m=x\lor m=y\}$ where $z=\max(x,y)$.

Regularity is not much harder, as any nonempty $x$ admits $l\in x$ where $\forall(m\in x), l\leq m$, due to Ordering. Since having $m\in l$ would imply $m<l$ via Respective, it follows that $x\cap l = \emptyset$, proving Regularity.

The axiom of Union follows since, for any set $x$, we simply have $u=\{m : m\leq x\}$ being a superset of the union of $x$. Indeed, given $k\in m\in x$ we have $k<m<x$, therefore $k\in u$ implying $m\subseteq u$. All $m\in x$ have $m\subseteq u$, so the union of the members of $x$ is just a subset of $u$.

The axiom of Powerset is a consequence of Hyper-Respective. Take any set $z$, let $y=\{z\}$ which exists via Pairing, then let $p=\{m\leq y : m\subseteq z\}$. Notice that every subset $x\subseteq z$ obeys $\forall(m\in x), m\in z$ and thus $\forall(m\in x), m<z$ via Respective, and since $z\in y$ then $x<y$ via Hyper-respective. It follows that $x\in p$, and so $p$ contains every subset of $z$, proving Powerset.

The schema of Replacement is almost identical to Boundedness. Let $F$ be any function symbol, let $x$ be any set, and let $\psi$ be the predicate coding the class image of $F$ over the set $x$. Using $<$, we can find a subset of $x$ on which $F$ bijects to $\psi$, explicitly $x'=\{m\in x : m=\min\{k\in x : F(k)=F(m)\}\}$. Now $F$ bijects $x'$ with $\psi$, so Boundedness finds $y$ bounding $\psi$. It follows that every $m\in x$ admits $k\in x'$ with $F(m)=F(k)$, and any $k\in x'$ has $F(k)<y$, hence $F(m)<y$. Letting $y'=\{j : y\leq y\}$, we have Replacement since all $m\in x$ have $F(m)\in y'$.

Finally, the Infinity axiom of $\sf{ZF}$ is now a direct consequence of your Infinity axiom. This works because the class $\mathbb{N}$ of finite ordinals can be defined without ever assuming Infinity, and we can also prove the Recursion theorem without ever assuming Infinity, and we have all other axioms of $\sf{ZF}$. Simply let Let $\ell$ denote the minimal $l$ witnessing your Infinity axiom, let $\mathbb{N}$ denote the class of all finite ordinals, then apply Recursion to define a bijection between $\{x : x<\ell\}$ and $\mathbb{N}$ in the expected way. The former is a set, and so the latter is a set via Replacement.

$\endgroup$

You must log in to answer this question.

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