Exists Bijection to a Disjoint Set

**Matt Westwood** · July 13th 2010, 10:39 PM

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

"If $E$ and $F$ are sets, then there is a bijection from $F$ onto a set $F'$ disjoint from $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 $f: F \to F$ be a bijection, any bijection (the identity mapping will do).

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

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

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

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

Take some element $s \in S$ .

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

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

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

However, this gets messy when $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 $t$ I picked is not already in $F - E$ which would render my mapping $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.

**Swlabr** · July 14th 2010, 01:00 AM

Originally Posted by Matt Westwood

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

"If $E$ and $F$ are sets, then there is a bijection from $F$ onto a set $F'$ disjoint from $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 $f: F \to F$ be a bijection, any bijection (the identity mapping will do).

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

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

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

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

Take some element $s \in S$ .

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

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

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

However, this gets messy when $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 $t$ I picked is not already in $F - E$ which would render my mapping $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?

**MoeBlee** · July 14th 2010, 08:23 AM

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

**Matt Westwood** · July 14th 2010, 09:51 AM

Originally Posted by Swlabr

Have you looked at Ex. 8.12 in the book?

Yes, doesn't help.

**Matt Westwood** · July 14th 2010, 10:14 AM

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 $F \times \{z\} \cap E = \varnothing$ ?

What if:

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

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

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

Am I missing something?

**MoeBlee** · July 14th 2010, 10:21 AM

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

**MoeBlee** · July 14th 2010, 10:22 AM

You ask about the case:

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

But then z in range(E).

**Matt Westwood** · July 14th 2010, 10:33 AM

Originally Posted by MoeBlee

You ask about the case:

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

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.

But what about:
$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.

**Matt Westwood** · July 14th 2010, 10:40 AM

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.

But what about:
$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.

**MoeBlee** · July 14th 2010, 10:52 AM

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

**MoeBlee** · July 14th 2010, 10:53 AM

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.

**Matt Westwood** · July 14th 2010, 12:02 PM

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?

**MoeBlee** · July 14th 2010, 12:15 PM

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

**Matt Westwood** · July 14th 2010, 12:52 PM

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.

**MoeBlee** · July 14th 2010, 02:21 PM

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.

Thread: Exists Bijection to a Disjoint Set

LinkBack

Thread Tools

Display

Exists Bijection to a Disjoint Set

Similar Math Help Forum Discussions

[SOLVED] Set related question ... find out if disjoint of not disjoint ...

Subsets that have a disjoint

Disjoint cycles

disjoint intervals

Disjoint cycles...