Bijection between AxB and BxA

1. Dec 27, 2008

Unassuming

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. Dec 27, 2008

Dick

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

3. Dec 27, 2008

HallsofIvy

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

4. Dec 28, 2008

knollen baum

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.

$$\exists X\, \forall y\, \lnot (y \in X)$$

And do not forget to make your answer save to sets with infinite cardinality.

5. Dec 28, 2008

Hurkyl

Staff Emeritus
It's not clear exactly what you're saying. But it doesn't seem to be relevant to anything anyone else said.

6. Dec 28, 2008

knollen baum

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:
$$\exists X\, \forall y\, \lnot (y \in X)$$
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
7. Dec 28, 2008

Citan Uzuki

Actually, the function definition $f:A \times B \rightarrow B \times A: (a,\ b) \mapsto (b,\ a)$ is perfectly valid even in the case where at least one of A or B are empty. Why? Because in that case, $A \times B = \emptyset$, so it is vacuously true that every element in $A \times B$ is of the form (a, b) for some $a \in A$ and some $b \in B$. 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).

8. Dec 29, 2008

Hurkyl

Staff Emeritus
You're use of 'WLOG' here is incorrect; assuming A to be empty is a loss of generality.

9. Dec 29, 2008

HallsofIvy

Staff Emeritus