Thread: Exists Bijection to a Disjoint Set

1. Exists Bijection to a Disjoint Set

In "Modern Algebra" by Seth Warner (1965), section 8 (page 54 in my copy) there exists this:

"If $\displaystyle E$ and $\displaystyle F$ are sets, then there is a bijection from $\displaystyle F$ onto a set $\displaystyle F'$ disjoint from $\displaystyle E$."

It also says: "[This] may be proved in any formal development of the theory of sets."

But I haven't found this proof anywhere, so I'm trying to craft my own proof.

My approach is as follows.

Let $\displaystyle f: F \to F$ be a bijection, any bijection (the identity mapping will do).

If $\displaystyle E \cap F = \varnothing$ then job done, $\displaystyle F = F'$ and $\displaystyle f$. is our bijection.

Otherwise we have to construct it, or prove that there is a process for doing so.

Take $\displaystyle S = E \cap F$, and put all elements of $\displaystyle F - E$ into $\displaystyle F'$.

Let $\displaystyle P(S)$ be the power set of $\displaystyle S$.

Take some element $\displaystyle s \in S$.

Then (as is easily proved) $\displaystyle \exists t \in P(S): t \notin S$. So put $\displaystyle t \in F'$.

Then you create the mapping $\displaystyle f'$ defined as:
$\displaystyle f'(x) = \begin{cases} f(x) & : x \ne s \\ t & : x = s \end{cases}$

Then you've got $\displaystyle S' = S - \{s\}$ and you can repeat the process with $\displaystyle S'$.

However, this gets messy when $\displaystyle S$ is infinite (and worse when it's uncountable) and requires the Axiom of Choice in order to construct such a set.

Also, I haven't proved that the $\displaystyle t$ I picked is not already in $\displaystyle F - E$ which would render my mapping $\displaystyle f'$ not a bijection.

Does anyone know of an easier way of doing this? Apologies for any howlers in this, I'm practically self-taught when it comes to set theory.

Please be aware that any proof produced will appear (in some form) on the page:
Exists Bijection to a Disjoint Set - ProofWiki
... so unless you're happy for this to happen, best not answer.

2. Originally Posted by Matt Westwood
In "Modern Algebra" by Seth Warner (1965), section 8 (page 54 in my copy) there exists this:

"If $\displaystyle E$ and $\displaystyle F$ are sets, then there is a bijection from $\displaystyle F$ onto a set $\displaystyle F'$ disjoint from $\displaystyle E$."

It also says: "[This] may be proved in any formal development of the theory of sets."

But I haven't found this proof anywhere, so I'm trying to craft my own proof.

My approach is as follows.

Let $\displaystyle f: F \to F$ be a bijection, any bijection (the identity mapping will do).

If $\displaystyle E \cap F = \varnothing$ then job done, $\displaystyle F = F'$ and $\displaystyle f$. is our bijection.

Otherwise we have to construct it, or prove that there is a process for doing so.

Take $\displaystyle S = E \cap F$, and put all elements of $\displaystyle F - E$ into $\displaystyle F'$.

Let $\displaystyle P(S)$ be the power set of $\displaystyle S$.

Take some element $\displaystyle s \in S$.

Then (as is easily proved) $\displaystyle \exists t \in P(S): t \notin S$. So put $\displaystyle t \in F'$.

Then you create the mapping $\displaystyle f'$ defined as:
$\displaystyle f'(x) = \begin{cases} f(x) & : x \ne s \\ t & : x = s \end{cases}$

Then you've got $\displaystyle S' = S - \{s\}$ and you can repeat the process with $\displaystyle S'$.

However, this gets messy when $\displaystyle S$ is infinite (and worse when it's uncountable) and requires the Axiom of Choice in order to construct such a set.

Also, I haven't proved that the $\displaystyle t$ I picked is not already in $\displaystyle F - E$ which would render my mapping $\displaystyle f'$ not a bijection.

Does anyone know of an easier way of doing this? Apologies for any howlers in this, I'm practically self-taught when it comes to set theory.

Please be aware that any proof produced will appear (in some form) on the page:
Exists Bijection to a Disjoint Set - ProofWiki
... so unless you're happy for this to happen, best not answer.
Have you looked at Ex. 8.12 in the book?

3. This is in Z set theory, right?

Def: range(E) = {y | there exists an x such that <x y> in E}.

Previously proven theorem: For any S, there exists a z not in S.

Let z not in range(E).

So F X {z} is disjoint from E.

F is 1-1 with F X {z}.

4. Originally Posted by Swlabr
Have you looked at Ex. 8.12 in the book?
Yes, doesn't help.

5. Originally Posted by MoeBlee
This is in Z set theory, right?

Def: range(E) = {y | there exists an x such that <x y> in E}.

Previously proven theorem: For any S, there exists a z not in S.

Let z not in range(E).

So F X {z} is disjoint from E.

F is 1-1 with F X {z}.
How do you know that $\displaystyle F \times \{z\} \cap E = \varnothing$?

What if:

$\displaystyle F = \{z, a, b\}$

$\displaystyle E = \{a, (b, z)\}$

If $\displaystyle f (a) = b, f((b, z)) = a$ we have $\displaystyle z \notin Rng(E)$ but $\displaystyle (b,z) \in (F \times \{z\}) \cap E$.

Am I missing something?

6. If z not in range(E) then F X {z} /\ E = 0

Proof:

Suppose p in F X {z}.

So there exists a c such that p = <c z>.

Toward a contradiction, suppose <c z> in E.

But then z in range(E).

F = {z a b}
E = {a <b z>}

But then z in range(E).

8. Originally Posted by MoeBlee

F = {z a b}
E = {a <b z>}

But then z in range(E).
Aha! I think I understand.

Range(E) is the set of all elements of E which happen to be the first element of an ordered pair which also happens to be in E.

I assume there is bound to be one such. I will think about that one a bit more in a minute, it sounds plausible.

$\displaystyle E = \{x, (x, y), ((x, y), y), (((x, y), y), y), ...\}$
?
Then every element of E is the first element of an ordered pair that happens also to be in E.

9. Originally Posted by Matt Westwood
Aha! I think I understand.

Range(E) is the set of all elements of E which happen to be the first element of an ordered pair which also happens to be in E.

I assume there is bound to be one such. I will think about that one a bit more in a minute, it sounds plausible.

$\displaystyle E = \{x, (x, y), ((x, y), y), (((x, y), y), y), ...\}$
?
Then every element of E is the first element of an ordered pair that happens also to be in E.
No sorry, I got it wrong, my understanding of Range(E). Sorry, you use unconventional notation and I have to read it twice to understand it. Apologies, I will go away and see if I can work this out by myself.

10. You had the right idea but reversed it.

range(E) is the set of all second components of ordered pairs in E.

Just as I wrote originally:

range(E) = {y | there exists an x such that <x y> in E}.

11. No unconventional notation:

range(E) = {y | there exists an x such that <x y> in E}

the range of E is the set of those y such that there exists an x such that <x y> in E.

12. Originally Posted by MoeBlee
No unconventional notation:

range(E) = {y | there exists an x such that <x y> in E}

the range of E is the set of those y such that there exists an x such that <x y> in E.
Yes I guessed that <x y> is an ordered pair, which I am used to writing (x, y), accessing your profile I understand what you mean now. Apologies but the notation <x y> is unconventional in mainstream mathematics. What branch is your specialty?

13. "< >" is not unconventional notation for ordered pairing in set theory.

There are many textbooks and journal articles in set theory that use "< >" for ordered pairs, including Enderton and Suppes, which are among the mostly widely referenced set theory textbooks.

And I wouldn't be too shy even to wager that "< >" is vastly more used than is "( )" for ordered pairs in, e.g., 'The Journal Of Symbolic Logic', which is probably the most widely read journal for matters in set theory.

14. Originally Posted by MoeBlee
"< >" is not unconventional notation for ordered pairing in set theory.

There are many textbooks and journal articles in set theory that use "< >" for ordered pairs, including Enderton and Suppes, which are among the mostly widely referenced set theory textbooks.

And I wouldn't be too shy even to wager that "< >" is vastly more used than is "( )" for ordered pairs in, e.g., 'The Journal Of Symbolic Logic', which is probably the most widely read journal for matters in set theory.
Hmm ... perhaps in symbolic logic and modern set theory, but I believe the rest of the mediaeval benighted community of mere mathematics is still using ( , ) ... it doesn't matter what notation you use IMO as long as you explain it as you go. I understand that, in the field in which you work, < > is more common than ( , ) but feel free to take on board the fact that < > is understood by few at university level or below. To refuse to do so can cause a barrier to free and open communication, which IMO is a less than perfectly good thing.

Just my 2 cents worth. I will update the page on ProofWiki to include this notation. Many thanks for your solution. I got there in the end.

15. Note that we could just as well have used domain rather than range.

dom(E) = {x | exists a y such that <x y> in E}.

Let z not in dom(E).

So E is disjoint from {z} X F.

And F is 1-1 with {z} X F.

Page 1 of 2 12 Last