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

*

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

