Page 1 of 2 12 LastLast
Results 1 to 15 of 18

Math Help - Exists Bijection to a Disjoint Set

  1. #1
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    824
    Thanks
    33

    Exists Bijection to a Disjoint Set

    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}<br />
f(x) & : x \ne s \\<br />
t & : x = s<br />
\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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Matt Westwood View Post
    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}<br />
f(x) & : x \ne s \\<br />
t & : x = s<br />
\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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    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}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    824
    Thanks
    33
    Quote Originally Posted by Swlabr View Post
    Have you looked at Ex. 8.12 in the book?
    Yes, doesn't help.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    824
    Thanks
    33
    Quote Originally Posted by MoeBlee View Post
    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?
    Last edited by Matt Westwood; July 14th 2010 at 10:15 AM. Reason: Inaccuracy
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    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).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    You ask about the case:

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

    But then z in range(E).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    824
    Thanks
    33
    Quote Originally Posted by MoeBlee View Post
    You ask about the case:

    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.

    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    824
    Thanks
    33
    Quote Originally Posted by Matt Westwood View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    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}.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    824
    Thanks
    33
    Quote Originally Posted by MoeBlee View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    "< >" 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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    824
    Thanks
    33
    Quote Originally Posted by MoeBlee View Post
    "< >" 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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    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.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. [SOLVED] Set related question ... find out if disjoint of not disjoint ...
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: July 9th 2011, 02:26 AM
  2. Subsets that have a disjoint
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 8th 2010, 10:02 AM
  3. Disjoint cycles
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 3rd 2009, 01:00 PM
  4. disjoint intervals
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: September 10th 2009, 08:43 AM
  5. Disjoint cycles...
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: July 1st 2008, 07:41 PM

/mathhelpforum @mathhelpforum