Are the two versions of the axiom of replacement equivalent?

Question

1. $$ \forall A(\forall u\forall v\forall w(u\in A\wedge\varphi(u,v)\wedge\varphi(u,w)\rightarrow v=w)\rightarrow\exists B\forall x(x\in B\leftrightarrow\exists y(y\in A\wedge\varphi(y,x)))) $$
2. $$ \forall u\forall v\forall w(\varphi(u,v)\wedge\varphi(u,w)\rightarrow v=w)\rightarrow\forall A\exists B\forall x(x\in B\leftrightarrow\exists y(y\in A\wedge\varphi(y,x))) $$ The first version appears in Tao's analysis; The second version appears in Jech's set theory.In Fraenkel's Foundations of Set Theory, he points out that the two versions are equivalent. Yet I didn't come up with a reason, can someone prove that it is equivalent or not? Any help would be appreciated.

Answer 1

Please note that these axioms are really axiom schemas because you can fill in for $\varphi$ any formula with two free variables. So, every time you use a new formula, you get a new axiom. These axiom schemas thus represent a whole (infinite) set of axioms.

Now, if you fill in the same formula for $\varphi$ for both formulas, and then compare the result of that, then they are not equivalent. For example, suppose $P$ is a two-place predicate, and suppose we use that to instantiate both axiom schemas, resulting in the following two axioms:

$\forall A(\forall u\forall v\forall w(u\in A\wedge P(u,v)\wedge P(u,w)\rightarrow v=w)\rightarrow\exists B\forall x(x\in B\leftrightarrow\exists y(y\in A\wedge P(y,x)))) $

$\forall u\forall v\forall w(P(u,v)\wedge\ P(u,w)\rightarrow v=w)\rightarrow\forall A\exists B\forall x(x\in B\leftrightarrow\exists y(y\in A\wedge P(y,x))) $

Well, these two axioms are not logically equivalent.

However, following @mihaild's comment, if you use $P(u,v)$ to instantiate $\varphi(u,v)$ for the first axiom, then you can use $u \in A \land P(u,v)$ to instantiate $\varphi(u,v)$ for the second axiom, and now the resulting axioms are equivalent.

Moreover, it should be pretty clear that this 'trick' works for any formula: whatever formula you use for $\varphi(u,v)$ to instantiate the first axiom with, you simply pick $u \in A \land P(u,v)$ for $\varphi(u,v)$ to instantiate the second axiom with. As such, the set of all axioms that the first axiom schema represents can be derived from the set of all axioms that the second axiom schema represents.

The other way around is even easier, as you already realized: whatever you plug in for $\varphi(u,v)$ in the second axiom schema, we can simply use that very same $\varphi(u,v)$ for the first, and the latter will logically imply the former, meaning that the set of all axioms that the second axiom schema represents can be derived from the set of all axioms that the first axiom schema represents.

Those two results together allows us to say that the two axioms schemas are logically equivalent.

Here is an example that you may be more familiar with but that demonstrates the same principle. As you probably know, weak induction is said to be equivalent to strong induction, and indeed, whatever you can prove using strong induction you can prove using weak induction.

Now, that this is so is not at all obvious. Indeed, let's look at the formalizations of weak induction and strong induction. Where $\varphi(x)$ is any formula with one free variable $x$, we have:

Weak induction: $(\varphi(0) \land \forall x (\varphi(x) \to \varphi(x+1))) \to \forall x \ \varphi(x)$

Strong induction: $\forall x ((\forall y (y < x \to \varphi(y)) \to \varphi(x)) \to \forall x \ \varphi(x)$

OK, so these sentences do not at all look like they are equivalent: The one sentence refers to $0$, $1$, and $+$, while the other refers to $<$, so how could they possibly be (actually, many formalizations of weak induction use $s(x)$ instead of $x+1$ ... but you get a discrepancy in terms of their non-logical predicate, constants, and function symbols either way).

So, the first thing to realize in this case is that you'll need to assume certain axioms that define and relate these terms of $0$, $s$, $<$, etc. For this, you could for example use standard Peano Arithmetic, without the axiom of induction, but together with some suitable definition for $<$.

Even so, if we pick some specific 1-place predicate $P(x)$ for each of the axioms, we get the following two axioms:

$(P(0) \land \forall x (P(x) \to P(x+1))) \to \forall x \ P(x)$

$\forall x ((\forall y (y < x \to P(y)) \to P(x)) \to \forall x \ P(x)$

And you can still not derive the one from the other, even in the context of those axioms for Peano Arithmetic.

However, at this point the same story holds as above. Again, these axioms of induction are axiom schemas. So, when you fill in something like $P(x)$ in the strong induction schema, you can fill in $\forall y (y < x \to P(x))$ for the weak induction schema to get:

$(\forall y (y < 0 \to P(0)) \land \forall x (\forall y (y < x \to P(x)) \to \forall y (y < x + 1 \to P(x+1)))) \to \forall x \ \forall y (y < x \to P(x))$

And this sentence, together with the axioms of Peano Arithmetic, allows you to derive the strong induction 'counterpart':

$\forall x ((\forall y (y < x \to P(y)) \to P(x)) \to \forall x \ P(x)$

And so it is in that sense that we can say that weak induction and strong induction are equivalent: they are equivalent assuming some background assumptions, but most importantly, they are equivalent because they are equivalent as axiom schemas.

OK, one final comment. Instead of an axiom schema, you could present these as second-order logic formulas. In your case, for example, you could consider the following two SOL sentences:

$\forall \varphi \ \forall A(\forall u\forall v\forall w(u\in A\wedge\varphi(u,v)\wedge\varphi(u,w)\rightarrow v=w)\rightarrow\exists B\forall x(x\in B\leftrightarrow\exists y(y\in A\wedge\varphi(y,x)))) $

$ \forall \varphi \ \forall u\forall v\forall w(\varphi(u,v)\wedge\varphi(u,w)\rightarrow v=w)\rightarrow\forall A\exists B\forall x(x\in B\leftrightarrow\exists y(y\in A\wedge\varphi(y,x))) $

And, you will find that these are second-order logic equivalent.

Answer 2

1. You need to be careful about which free variables in the formula you quantify over.
2. The axiom schemas permit parameters.
3. The two forms are not equivalent per $\varphi$. The entire schema (over all $\varphi$) is equivalent to the entire other schema.

The first form: Let $\varphi=\varphi(u,v,p_1,\dots,p_n)$ be a formula whose free variables are among $u,v,p_1\dots,p_n$. Then $$\forall p_1\dots\forall p_n\forall A((\forall u\forall v\forall w((u\in A\land \varphi\land\varphi[w/v]) \rightarrow v=w))\rightarrow \exists B\forall x(x\in B\leftrightarrow\exists y(y\in A\land \varphi[y/u,x/v])))$$

The second form: Let $\varphi=\varphi(u,v,p_1,\dots,p_n)$ be a formula whose free variables are among $u,v,p_1\dots,p_n$. Then $$\forall p_1\dots\forall p_n((\forall u\forall v\forall w((\varphi\land\varphi[w/v]) \rightarrow v=w))\rightarrow\forall A\exists B\forall x(x\in B\leftrightarrow\exists y(y\in A\land \varphi[y/u,x/v])))$$

The first form implies the second form by using the same $\varphi$.

The second form implies the first form by taking $\varphi' = \varphi\land (u\in p_{n+1})$ (for $\varphi$ from the first form), then using the second form on $\varphi'$ with one extra parameter $p_{n+1}$ and letting $p_{n+1}$ take the same value as $A$.