7
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Also "size one less" may be too small a step in the infinite case ... $\endgroup$ Feb 10, 2013 at 8:21
  • $\begingroup$ What other axioms do you have at your disposal? $\endgroup$
    – user642796
    Feb 10, 2013 at 8:23
  • $\begingroup$ extensionality, existence of unions, intersections, differences $\endgroup$
    – TJIF
    Feb 10, 2013 at 8:25
  • $\begingroup$ @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? $\endgroup$ Feb 10, 2013 at 8:31
  • $\begingroup$ oh, no, I think u can use Pairing and replacement too, sorry :D $\endgroup$
    – TJIF
    Feb 10, 2013 at 8:34

3 Answers 3

9
$\begingroup$

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

$\endgroup$
0
6
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ With a slightly more involved argument, you can avoid the use of Foundation. $\endgroup$
    – bof
    Apr 18, 2015 at 11:17
6
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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