# Proof of exchange principle in set theory

How would one use the Axiom of Foundation (that every non-empty set has an $\in$-minimal element) to prove that for any two sets $x,y$ we can find a set $x'$ so that $x'$ and $y$ are disjoint and $x'$ and $x$ are in bijection?

I myself tried to construct $x$ recursively by doing the following: if $x$ and $y$ are disjoint, we are done; if not, take $z$ in $x \cap y$ and let $x_{1} = (x - \left\{z_{1}\right\} ) \cup \left\{y\right\}$. Now, the new intersection $x_{1} \cap y$ has size with $1$ less than the size of $x \cap y$ because $y \not \in y$ (by Axiom of Foundation) and so on (i.e. if $x_{1}$ and $y$ are not disjoint take $z_{2}$ in the intersection and let $x_{3} = (x_{1} - \left\{z_{2}\right\}) \cup \left\{\left\{y\right\}\right\}$. However, I don't think this works since we might have $y \in x$ and this messes up our bijection.

A detailed answer would be appreciated... (for me to get confortable with the basics) thanks

-
Also "size one less" may be too small a step in the infinite case ... – Hagen von Eitzen Feb 10 '13 at 8:21
What other axioms do you have at your disposal? – arjafi Feb 10 '13 at 8:23
extensionality, existence of unions, intersections, differences – TJIF Feb 10 '13 at 8:25
@TJIF Oops, really so little? I guess that would not necessarily give you more than just the empty set (admittedly, in such a small model disjointness is not hard to achieve). Then how do you justify $\{y\}$ and $\{\{y\}\}$ in your own argument? – Hagen von Eitzen Feb 10 '13 at 8:31
oh, no, I think u can use Pairing and replacement too, sorry :D – TJIF Feb 10 '13 at 8:34

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$

-
Perfect! Thank you! – TJIF Feb 12 '13 at 5:48
With a slightly more involved argument, you can avoid the use of Foundation. – bof Apr 18 '15 at 11:17

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.
-
What do you mean by saying you can place the $+1$ outside the $\sup$? Wouldn't that give $\text{rank}(\omega) = \omega+1$ instead of $\omega$? – Trevor Wilson Feb 12 '13 at 2:28
@Trevor: Yes, of course. But it will not change the essence of the proof. Now ask yourself whether the rank of a set should denote the point where it became a class or an actual set, and do you want to think of limit stages as stages where data is not added. These will ultimately decide whether or not $+1$ appears inside or outside the braces. – Asaf Karagila Feb 12 '13 at 2:31
I see. I'd never seen it defined with the $+1$ outside. I think it is much better inside, because then the rank function can also be characterized as the pointwise least function into the ordinals that preserves $\in$. – Trevor Wilson Feb 12 '13 at 2:38
Very interesting answer as well. Thanks a lot! – TJIF Feb 24 '13 at 6:06
@TJIF: My pleasure! – Asaf Karagila Feb 24 '13 at 6:09

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|.$

-