# Equivalents of Replacement under removal of Extensionality?

1. Is the following schema equivalent to the axiom schema of Replacement over the rest of axioms of $ZF$ [equality axioms, full versions of Pairing, Union and Power; Infinity, Foundation, Extensionality].

Scheme: If $\phi$ is a formula in which only symbols $x",z"$ occur free, then the following sentence is an axiom: $\forall A \ \exists B \ \forall y \ (y \in B \iff \exists x \in A \ (\forall z \ (\phi \iff z=y)))$

Other questions:

1. IF we remove $\text{Extensionality} ,Ext.",$ from $ZF$ (with this version of replacement) would the resultant theory still interpret full $ZF$? or it would be as weak as $Z$?

2. IF we replace $z=y$ in the above schema by $\forall m (m \in z \iff m \in y)$, would that save the resultant theory - $Ext.$ from being equivalent to $Z$?

3. IF we replace $z = y$ in the above schema by $z \in y$, would that save the resultant theory - $Ext.$ from being equivalent to $Z$?

• The model in mathoverflow.net/a/54328 satisfies ZFC without extensionality, and satisfies all versions of the replacement schema that you listed. Since it is basically embellished $V_{\omega+\omega}$, it is fair to say that the theory is essentially as weak as Z. If you want to interpret ZF in something without extensionality, you need to strengthen Replacement to Collection. – Emil Jeřábek Jan 5 '18 at 14:21
• @EmilJeřábek, I thought that it is the uniqueness quantifier in Replacement that caused that drastic weakening of ZF-Extensionality, here we have the same uniqueness in the first version but the next two versions do not have that, especially the last version. I thought that if I interpret sets as hereditarily unions of equivalence classes under co-extensionality, and membership as the epsilon membership relation restricted to them, then we can interpret the whole hierarchy of ZF without extensionality but with replacement formalized after one of the last two versions presented in my question. – Zuhair Al-Johar Jan 5 '18 at 15:37
• I think one can make non-uniqueness work arbitrarily many levels deep, in the last version there is no clear check to the kinds of sets $z$ that are related to $x$ as far as we have a set of all $z$'s per each $x \in A$, and this can go deeper and deeper as well. – Zuhair Al-Johar Jan 5 '18 at 18:10
• Yes, take the union of these $y$'s, and you'll get the $z$'s for each $x$, you can make the $y$'s iterated singletons of a set that contains the many $z$'s, etc... Anyhow, I'm not objecting to your position, I'll try to fathom it since to me it is not clearly written in the referred link. Thanks – Zuhair Al-Johar Jan 5 '18 at 18:42
• I thought that the usual proof of collection from replacement and foundation would also be applicable here, since we have foundation, and minimal stages $V_a$'s of cumulative hierarchies can be defined that can have a set $y$ such that $\phi(x,y)$ in them, so we can send each $x \in A$ to those minimal stages and take the union of them and separate on that union with $\phi(x,y)$ to get collection. I'm not seeing why that cannot happen here? – Zuhair Al-Johar Jan 6 '18 at 14:25

I think I have the solution to this in my head, It is to interpret in $\text{ZF-Ext.}$ (with the last version of replacement) the theory $\text{ZFA}$ which in turn interpret $\text{ZF}$.

The crux of the proof is to use Marcel Crabbe approach to interpreting equality and membership used in the equalization of $\text{SF}$ to $\text{NFU}$. So equality will be interpreted as co-extensionaity, and membership as membership in SETs, where SETs are defined as unions of equivalence classes under coextensionality, denote those as $=^*"$ , $\in^*"$, now we can see that the "atomic" formulas of that language (i.e. whose formulas only use $=^*"$ , $\in^*"$ as predicate symbols), are preserved under co-extensionality, i.e. if truth value of $x \in^*\alpha$ is K (for whatever $x$ and $\alpha$), then if we replace $x$ by a co-extensional object to $x$ and if we replace $\alpha$ by a coextensional object to $\alpha$ still the resulting formula would have truth value K, and of course the same applies to atomic formula $x=^* \alpha$, no doubt, this to be called as "truth preservation under co-extensional replacements".This means that for any formula in the language that only uses $=^*"$ , $`\in^*"$ as predicates, then its truth is preserved under co-extensional replacements, because the truth of any formula is a function of the truth of its atomic subformulas, so if the truth of latter ones is not affected by such replacements then the truth of the total formula shall not be affected. Call this LEMMA.

Now important theorems is that this theory proves that for any $A$ we can have a set of all objects coextensional with elements of $A$, simply let $\phi(x,z)$ in the replacement scheme to be $z \in x$, and $B$ would be a set of all $y's$ that are coextensional with the $x's$ in $A$, Call this PRPOSITION.

Also $\in$-Separation (using any kind of formulas in the language of set theory) is provable in an easy manner, simply let $\phi(x,z)$ in the replacement scheme to be $z=x \wedge \pi(x)$, and take the union of the resulting set from Replacement, and we get the set of all $x \in A$ satisfying $\pi$.

By the above LEMMA if the separating formula $\pi$ in $\in$-Separation only uses $=^*, \in^*$, then clearly the asserted object is a SET (i.e. a union of equivalence classes under coextensionality).

So $\in^*$-Separation is PROVED for ($=^*, \in^*$ formulas).

The proof of Weak Extensionality, Pairing, Union and Power-{0}, is rather straightforward (all written using predicates $=^*$,$\in^*$, over the whole domain of $\text{ZF-Ext.}$).

Now the proof of replacement is pretty much straightforward also since if the replacement formula satisfies the condition $\exists k \forall y (\phi(x,y) \iff y=^*k)$, then matters are really easy, i.e. we are replacing each $x \in A$ by every $y$ that satifies $\phi(x,y)$ and all of these $y$'s are coextensional! now to do that we take $\phi(x,z)$ , then apply replacement and each $y$ will be the set of all coextensional objects to a $z$ that fulfills $\phi(x,z)$, since there must exist such a $z$ by the preconditioning on replacement, then by pairing there must exist a set $\{z\}$ where $z$ fulfills $\phi(x,z)$, and by PROPOSITION we'll have the set of all coextensionals of $z$, and so the union of all such sets would be the needed replacement set, which is simply the union of the resulting replacement set. This would be a SET because of LEMMA.

Of course we can easily define transitive closures in this method, and we can actually define PURE SET as a set that is hereditarily set! and we can take the domain of our model to be the class of all hereditarily sets, and the equality and membership relation defined as above over that domain. This will save us headache about the many Ur-elements and easily interpret all the hierarchy of ZF(with full Extensionality).

The axiom of collection is easily provable in the usual manner by sending elements $x$ of $A$ to all minimal stages of the hierarchy that contains a $y$ as an element such that $\phi(x,y)$, this can be easily done by using the above replacement, and thus proving even collection.

The proof of Infinity goes as follows:

What is needed is to prove that:

$\exists N [\exists o \in^* N (\not\exists z (z \in^* o) )\wedge \\ \forall x \in^*N (\forall y (\forall z (z \in^* y \iff z \in^* x \lor z =^* x) \implies y \in^*N)]$

The idea is to define the usual Von Neuman ordinals (i.e. transitive classes of transitive classes such that no two distinct elements are co-extensional) as $\in$-ordinals, and to define $\in^*$-ordinals as transitive SETs of transitive SETs (Assuming Regularity), then to define a “copying relation” between them such that for each $\in$-ordinal there is a copying relation $F$ that sends it to an $\in^*$-ordinal, and the latter shall be denoted as an $\in^*$-ordinal copy of it. We’ll denote a usual finite $\in$-ordinal by $n$ and an $\in^*$-ordinal copy of it by $n^*$. Now we define the predicate "ordinal copying relation" in the following manner:

For all $F$, $F$ is an ordinal copying relation from $n$ to $m$ if and only if $F$ is a set of Kuratowski ordered pairs such that:

$[\forall a,b (\langle a,b \rangle \in F \implies a \in n \wedge b \in m)] \wedge \\ [\forall a,b,c,d (\langle a,b \rangle \in F \wedge\langle c,d\rangle \in F \implies (a=c \iff b=^*d))]$

also $F$ must satisfy the “quasi-bijectivity” condition which is:

$[\forall a \in n \exists b \in m*(\exists p \in F (p=\langle a,b \rangle))] \wedge \\ [\forall b \in m \exists a\in n(\exists p \in F (p=\langle a,b \rangle))]$

Now we can also require "quasi-isomorphism" condition, i.e. that of:

$\forall a,b,c,d (\langle a,b \rangle \in F \wedge \langle c,d\rangle \in F \implies (a\in c \iff b\in^*d))$.

Now all $\in^*$-empty ordinals are $\in$-empty sets, so a quasi-bijectivity ordinal copying relation trivially exists between them. So any first Von-Neumann ordinal will have an $\in^*$-ordinal copy, which is simply itself! And actually any other empty set. Now we can prove by induction that for any “finite” Von-Neuman ordinal $n$, there is an $n^*$ copy of it, and also there is a set of all $n^*$ copies of it. This is easy since this is the case for every empty set $n$, and if $n$ has an $n^*$ and a set $F$ that is an ordinal copying relation between it and that $n^*$, then clearly $n+1$ will have an $(n+1)^*$ and a set $G$ that is an ordinal copying relation between them, since $G$ will be a union of $F$ with a Cartesian product of an $\{n\}$ and an $\{n’| n’ =^* n^*\}$; and so an $(n+1)^*$ will be a range of $G$.

So in nutshell for every $\in$-ordinal $n$ that has an $\in^*$-ordinal copy $n^*$, then each successor $n+1$ of $n$ will be easily shown to be sent by some ordinal copying relation to each successor $(n+1)^*$ of $n^*$, where $(n+1)^*$ is a union set of $n^*$ and a set $\{n’| n’ =^* n^*\}$. Now any set $\{n’| n’ =^* n^*\}$ would be a set that contains ALL co-extensionals of any set $n^*$ because simply ALL $n^*$ sets are co-extensional! so this proves that for every finite von Neuman ordinal $n$, there is a set of all sets coextensional to each $\in^*$-ordinal copy of it.

Now by Replacement we can send each element $n$ of the set of all finite Von Neumann ordinals to all sets $y$ of all of $n^*$ copies. Now a union of this replacement set would be a set that corresponds to an $\in^*$-$\omega$. Or another way is to use Replacement (last version above) to replace each element $n$ of the set of all finite Von Neumann ordinals by each set $y$ of all $\in^*$-ordinal copies of elements of $n$, in other words each $n$ would by replaced by all $n^*$ sets, and so the resulting set from Replacement would be an $\in^*$-$\omega$ SET. QED

So I think this is a sketch of a proof of ZF being interpretable in ZF-Ext. with the above axiom of replacement.

• How do you prove infinity? – Emil Jeřábek Jan 13 '18 at 8:28
• Ok, I've presented the proof above. – Zuhair Al-Johar Jan 14 '18 at 13:14
• I don’t understand the proof. Without extensionality, even standard ordinals, like $0,1,2,\dots$ may have many different Von Neumann representations. So how could $F$ be a bijection? Second, $F$ seems to be constructed by some kind of primitive recursion. It’s a priori not clear that usual proofs of recursion in ZF can be carried out without extensionality. – Emil Jeřábek Jan 14 '18 at 18:39
• Ok, I admit that what I called as "bijectivity" condition is not the usual bijection (that's why it has been put in scare quotes), it is of course not a bijection in the usual sense at all, I perhaps must call it as quasi-bijection then, and F is not constructed by any kind of recursion, F is not a primitive at all, I only put it there for clarity purposes, you can dispence with it altogether, F is just a set of ordered pairs that fulfill the above-mentioned conditions, that's all. – Zuhair Al-Johar Jan 14 '18 at 19:34
• Hmm. I’m still not quite convinced as there are many details missing, but it seems it could actually work. – Emil Jeřábek Jan 15 '18 at 16:36

I chose to put this as a separate answer because it directly depends on an important prior result due to Dana Scott that is mentioned by Azriel Levy in the below-mentioned link, and so it constitutes a shorter answer than the elaborate above-mentioned personal answer of mine.

https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/gandy-r-o-on-the-axiom-of-extensionality-the-journal-of-symbolic-logic-vol-21-1956-pp-3648-and-vol-24-no-4-for-1959-pub-1961-pp-287300-scott-dana-more-on-the-axiom-of-extensionality-essays-on-the-foundations-of-mathematics-dedicated-to-a-a-fraenkel-on-his-seventieth-anniversary-edited-by-barhillel-y-poznanski-e-i-j-rabin-m-o-and-robinson-a-for-the-hebrew-university-of-jerusalem-magnes-press-jerusalem-1961-and-northholland-publishing-company-amsterdam1962-pp-115131/B668C4F6F2A5D674B3719D6B71E183AB

In this article, it speaks of a proof due to Dana Scott of the following:

If ZF* means ZF but with replacement written as follows, then ZF*-Ext. interprets ZF.

Replacement*: $$\forall A[\forall x,y,z (\phi(x,y) \wedge \phi(x,z) \implies y=^*z) \implies \exists B \forall y (y \in B \iff \exists x \in A \phi(x,y))]$$

where $$y=^*z$$ is defined as [$$\forall m (m \in y \iff m \in z)$$]

Now it is clear that the second formulation presented in this question implies the above scheme, also the third formulation clearly implies the second formulation, just let $$\phi(x,z)$$ to be $$\exists k (\phi(x,k) \wedge z \in k)$$, then separate on the resulting set with the formula $$\exists x \in A (\phi(x,y))$$. So the answer is to the POSITIVE, i.e. both of the second and third formulations can interpret ZF.

• Have you considered writing a blog for things like this? I understand that MO offers a utility for asking and answering ones own questions, but I can think of maybe one instance outside your posts and no instances where someone posted multiple answers to their own question with no other answers present. It seems like you’re doing it here for the specific audience (understandable), but it’s disingenuous to essentially blog in a space that isn’t made for blogging. Many famous posters on here (Terry Tao, Joel Hamkins) maintain blogs they sometimes reference in posts, but they avoid blogging here. – Alec Rhea Sep 13 '20 at 7:20