1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Bijection between AxB and BxA

  1. Dec 27, 2008 #1
    1. The problem statement, all variables and given/known data

    Show that there is a bijective correspondence of AxB with BxA.


    2. Relevant equations



    3. The attempt at a solution

    I am lacking the general understanding of this. Can I create a function g such that,

    g: (a in A, b in B) --> (b in B, a in A).

    If A and B are sets, then are AxB and BxA the same?
     
  2. jcsd
  3. Dec 27, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You just did create such a function. If (a,b) is in AxB, then let g((a,b))=(b,a), which is what you said, if not what you meant. (b,a) is in BxA. Now you just have to prove it's a bijection
     
  4. Dec 27, 2008 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Yes, you can do that. Now you have to prove that is a "bijection": its both "one-to-one" (an injection) and "onto", (a surjection).

    No, absolutely not! But there exist an injection between them so they have the same "cardinality". For example, if A= {x} and B= {y} then A x B= {(a, b)} and B x A= {(b, a)}. Those two sets have the same cardinality (1) but are different sets because they contain different pairs: as an ordered pair, (a, b) is NOT the same as (b, a).
     
  5. Dec 28, 2008 #4
    But only if WLOG A is not an empty set, because the Zermelo–Fraenkel set theory (the standard set theory) defines in the "axiom of empty set" that there isn't an a in A.

    [tex]\exists X\, \forall y\, \lnot (y \in X)[/tex]

    And do not forget to make your answer save to sets with infinite cardinality.
     
  6. Dec 28, 2008 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It's not clear exactly what you're saying. But it doesn't seem to be relevant to anything anyone else said.
     
  7. Dec 28, 2008 #6
    Sorry, my english is not very good, but i will try to explain it.

    You can not prove a bijective correspondence of AxB with BxA for any set A, B by an function that says nothing for empty sets.

    The function says:
    g: (a in A, b in B) --> (b in B, a in A)

    The "axiom of empty set" says:
    [tex]\exists X\, \forall y\, \lnot (y \in X)[/tex]
    It means that there is an set A with no a in A. We call it emtpy set.

    If you look again at the function g you will see that it is not defined for empty sets. Because if WLOG (Without loss of generality) A is the empty set, there is no a in A and so you dont know what (a in A, b in B) --> (b in B, a in A) means, or do you know what (,) -> (,) means?

    So if you prove that g: (a in A, b in B) --> (b in B, a in A) is bijective, than you only know that there is a bijective correspondence of AxB with BxA when neither A nor B is an empty set.
    Sure it is trivial that there is a bijective correspondence of {} and {}, but if you have to answer an basic question it should be an complete anwser without the "trivial"-option.

    If i have to correct such an answer i would mark this point red, so i wanted to show this point before anyone will really mark this answer red.
     
    Last edited: Dec 28, 2008
  8. Dec 28, 2008 #7
    Actually, the function definition [itex]f:A \times B \rightarrow B \times A: (a,\ b) \mapsto (b,\ a)[/itex] is perfectly valid even in the case where at least one of A or B are empty. Why? Because in that case, [itex]A \times B = \emptyset[/itex], so it is vacuously true that every element in [itex]A \times B[/itex] is of the form (a, b) for some [itex]a \in A[/itex] and some [itex]b \in B[/itex]. Thus, there is no need to handle the case where one of A or B are empty separately, since the general argument applies to it as well (and in that case, the bijection constructed is simply the empty function).
     
  9. Dec 29, 2008 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You're use of 'WLOG' here is incorrect; assuming A to be empty is a loss of generality.
     
  10. Dec 29, 2008 #9

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    "Your use of 'WLOG'":devil:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Bijection between AxB and BxA
Loading...