Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 6 down vote accepted

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$

share|cite|improve this answer
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.


  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.
share|cite|improve this answer
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|.$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.