Proof of exchange principle in set theory

Solution 1:

Actually, you don't need the Axiom of Foundation for that.

Lemma. Given a set $X$, we can find a set $Y$ such that $|X|=|Y|$ and $X\cap Y=\emptyset.$

Proof. Let $$T=\{(S,x):S\subseteq X,\ x\in X,\ (S,x)\in X,\ (S,x)\notin S\}\subseteq X$$ and let $$Y=\{(T,x):x\in X\}.$$ Clearly $|X|=|Y|.$ Assume for a contradiction that $X\cap Y\ne\emptyset,$ i.e., there is an element $x\in X$ such that $(T,x)\in X.$ Then we get the Russell paradox in the form $$(T,x)\in T\iff(T,x)\notin T.$$ Theorem. Given sets $x$ and $y,$ we can find a set $x'$ such that $|x|=|x'|$ and $x'\cap y=\emptyset.$

Proof. Let $X=x\cup y.$ By the lemma, we can find a set $Y$ such that $X\cap Y=\emptyset$ and $|Y|=|X|=|x\cup y|\ge|x|.$ Choose $x'\subseteq Y$ with $|x'|=|x|.$

Solution 2:

Using Pairing and Replacement, let $$x'=\bigl\{ \{y,z\}\mid z\in x\bigr\}.$$ Then $x\to x'$, $z\mapsto \{y,z\}$ is a bijection (even if $z=y$ may occur). For $z\in x$ consider the set $u=\{\{z,y\},y\}$ (again using Pairing). As $\{z,y\}\cap u$ is nonempty, Foundation says that $y\cap u$ is empty, especially $\{y,z\}\notin y$, hence $x'\cap y=\emptyset$

Solution 3:

Allow me to offer a different approach, which may be more interesting but more advanced.$\newcommand{\rank}{\operatorname{rank}}$

From the axioms of foundation and replacement we can deduce the existence of an ordinal rank function, e.g.: $$\rank(x)=\sup\{\rank(y)+1\mid y\in x\}.^{[1]}$$

Fact: If $\alpha$ is an ordinal then $\rank(\alpha)=\alpha$.

Proof. We prove by induction, suppose it is true for all $\beta<\alpha$ then, $$\rank(\alpha)=\sup\{\rank(\beta)+1\mid\beta<\alpha\}=\sup\{\beta+1\mid\beta<\alpha\}=\alpha.$$

The first equality sign is the definition of the rank; the second follows from the induction hypothesis; and the last equality is vacuous in the case of zero, if $\alpha$ is a successor then $\alpha=\beta+1$ and the equality follows, and if $\alpha$ is a limit ordinal then the equality follows from the definition of a limit ordinal. $\square$

So suppose $\alpha=\rank(x)$ and $\beta=\rank(y)$ and $\gamma=\alpha+\beta+1$, we define $x'=x$ and $y'=\{\{\gamma,z\}\mid z\in y\}$. Then $y'$ is a set because of pairing and replacement (similar to Hagen von Eitzen's answer). Clearly $x$ and $x'$ have a bijection between them, and $y$ has a bijection with $y'$.

Let us see that $y'\cap x'=\varnothing$. All the elements of $x'$ have rank smaller than $\alpha$ by the definition of the rank function, while every element of $y'$ is of the form $\{\gamma,z\}$, where $\rank(z)<\beta<\gamma$. Therefore, $$\rank(\{\gamma,z\})=\max\{\gamma+1,\rank(z)+1\}=\gamma+1.$$

From this we have that if $z'\in y'$ then $\rank(z')>\rank(x')$ and therefore $z'\notin x'$, and if $z'\in x'$ then it is impossible that $z'\in y'$ as well. So we have $x'\cap y'=\varnothing$ as wanted.

Footnotes:

1. The $+1$ can be placed outside the $\sup$ itself, and I find it a philosophical question whether or not new data should be added at limit stages; I find myself sitting on the fence and leaning to either side depending on my mood.