# Can any subset of $x$ be moved out of $x$?

Let $x$ be a set and let $y\subset x$. Does there exist a set $z$ such that:

(1) $z\cap x=\emptyset$ and

(2) there exists a bijection $y \to z$ ?

It is quite intuitive that the answer should be yes. My first attempt was to take a set $x'\notin x$ and to consider $z=y\times \{ x'\}$. But I am unable to show $z\cap x=\emptyset$. I could imagine a proof with the axiom of choice, but I'd prefer to avoid it if possible.

• Try $z = y\times \{x\}$. Then $z\cap x = \varnothing$ by the axiom of foundation. Commented Nov 2, 2013 at 22:53
• Dear @DanielFischer: could you elaborate ? Commented Nov 2, 2013 at 22:55
• $z = y\times \{x\} = \{ \{a, \{a,x\}\} : a \in y\}$. Supposing we had $z\cap x \neq\varnothing$, we'd have $x \in \{a,x\} \in \{a,\{a,x\}\} \in x$ for some $a \in y$, which is forbidden by foundation (that's NBG, I don't know how the equivalent is called and formulated in ZF). Commented Nov 2, 2013 at 23:07
• Yes, I see, thanks ! If you put this comment into an answer I will be glad to accept it. Commented Nov 2, 2013 at 23:10
• @DanielFischer You should feel free to post your comment as an answer; I didn't intend to deprive you of that opportunity. Commented Nov 2, 2013 at 23:11

Edit: simplified version

The Axiom of Foundation is not needed.

Theorem. Given a set $X$ we can find a set $Y$, disjoint from $X$, and a bijection from $X$ to $Y$.

Proof. Let $$T=\{(S,x):(S,x)\in X\wedge(S,x)\notin S\}$$and let$$Y=\{(T,x):x\in X\}.$$Of course $x\mapsto (T,x)$ is a bijection from $X$ to $Y$. Assume for a contradiction that $X\cap Y\ne\emptyset$. This means that there is an element $x\in X$ such that $(T,x)\in X$. Now, according to the definition of $T$,$$(T,x)\in T\Leftrightarrow(T,x)\in X\wedge(T,x)\notin T.$$Since $(T,x)\in X$ by assumption, we arrive at the contradiction$$(T,x)\in T\Leftrightarrow(T,x)\notin T.$$

• Could you elaborate on the contradiction? It seems like we would need $T \subset X$ in order to get the Russell-like contradiction $(T,x) \in T \iff (T,x) \notin T$, because of the condition $S \subset X$ in the definition of $T$. Commented Nov 2, 2013 at 23:44
• It still seems like you only get $(T,x) \in T \iff T \subset X \wedge (T,x) \notin T$. So if $T \not\subset X$ then there is no contradiction. Commented Nov 2, 2013 at 23:48
• @TrevorWilson $T\subseteq X$. I was still parsing the set consrtructor, which one might rewrite matching the axiom of comprehension: $T=\{\,t\in X\mid \exists S, x\colon t=(S,x), S\subseteq X, t\notin S\,\}$. Commented Nov 2, 2013 at 23:51
• So axioms used are just Extensionality, Pairing (hidden in $(,)$), Comprehension (for $T$), Replacement (for $Y$), I guess? Nice. Commented Nov 3, 2013 at 0:00
• @TrevorWilson Come to think of it, I wonder why I put that condition $S\subseteq X$ in the definition of $T$. I don't see a reason for it, so I've taken it out. If there was a reason for it, which I'm not seeing, I hope someone will tell me about it. I think it looks a lot more natural now.
– bof
Commented Nov 3, 2013 at 11:13

Choosing $z = y\times \{x\} = \bigl\{ \{\{a\},\{a,x\}\} : a \in y\bigr\}$ works, since the axiom of foundation guarantees that $z \cap x = \varnothing$ then. For otherwise, there'd be an $a\in y$ with

$$x \in \{a,x\} \in \{\{a\},\{a,x\}\} \in x.$$

• Should there be brackets around your $a$'s? Or are you using a definition other than Kuratowski's? Commented Nov 2, 2013 at 23:24
• Frankly, I don't remember Kuratowski's definition of ordered pairs. Could be that that includes more $\{\}$s. But I think this one works too. Commented Nov 2, 2013 at 23:27
• It's not clear to me that it has the desired property that $(a,b) = (c,d) \implies a = c \wedge b = d$. If $a$ itself is a pair, then it seems like it might be hard to figure out the first and second coordinates of $\{a,\{a,x\}\}$. Commented Nov 2, 2013 at 23:29
• Since $a \in \{a,x\}$, figuring out the first component shouldn't be a problem. But if I'm overlooking something, just replacing with a working definition of ordered pairs would do it. I'm just hunting for my set theory book to look up Kuratowski's. Commented Nov 2, 2013 at 23:36
• @HagenvonEitzen I do think it is useful (in general, rather than in the context of this question) to have a definition of ordered pair that can be proved to have the desired property without using foundation. Also, according to bof we don't need foundation for this question anyway. Commented Nov 2, 2013 at 23:46

To elaborate on Daniel Fischer's comment, we can prove this using the axiom of foundation, or more easily (in my opinion) using the consequence that every set has an ordinal rank.

Take your set $x'$ to be any set with rank at least that of $x$, say $x' = x$ itself. Then every element of $y \times \{x'\}$ will have rank greater than that of $x$ because the rank of an ordered pair is greater than the ranks of its components. On the other hand, every element of $x$ has rank less than that of $x$. Therefore $x \cap (y \times \{x'\}) = \emptyset$.