# 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 ... Feb 10, 2013 at 8:21
• What other axioms do you have at your disposal? Feb 10, 2013 at 8:23
• extensionality, existence of unions, intersections, differences
– TJIF
Feb 10, 2013 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? Feb 10, 2013 at 8:31
• oh, no, I think u can use Pairing and replacement too, sorry :D
– TJIF
Feb 10, 2013 at 8:34

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

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$

• With a slightly more involved argument, you can avoid the use of Foundation.
– bof
Apr 18, 2015 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\}.^{}$$

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$? Feb 12, 2013 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. Feb 12, 2013 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$. Feb 12, 2013 at 2:38
• Very interesting answer as well. Thanks a lot!
– TJIF
Feb 24, 2013 at 6:06
• @TJIF: My pleasure! Feb 24, 2013 at 6:09