1. ## bijection and cardinality

I have to prove that if the cardinality of A = the cardinality of B AND the cardinality of C = the cardinality of D then the cardinality of (A x C) = the cardinality of (B x D) with sets A,B,C,D and x denoting the cartesian product.

I know that there exists a bijection f: A to B and a bijection g: C to D. But how do I proceed using this idea of bijections?

2. Originally Posted by PvtBillPilgrim
I have to prove that if the cardinality of A = the cardinality of B AND the cardinality of C = the cardinality of D then the cardinality of (A x C) = the cardinality of (B x D) with sets A,B,C,D and x denoting the cartesian product.

I know that there exists a bijection f: A to B and a bijection g: C to D. But how do I proceed using this idea of bijections?

Let $\displaystyle f:A\to B$ and $\displaystyle g:C\to D$ be bijections.
Define $\displaystyle h:A\times C\to B\times D$ by $\displaystyle h(a,c) = (f(a),g(c))$.

3. Can I say this?

I know that there is a function f: A to B that is injective, a function g: B to A that is injective, a function h: C to D that is injective, and a function j: D to C that is injective (since the cardinality of X <= the cardinality of Y if there exists an injective function from X to Y).

Define the function k: (A x C) to (B x D).
Do the statements above imply that a function l: (A x C) to (B x D) is injective with l(a,c) = (a,c) and a function m: (B x D) to (A x C) is injective with m(b,d) = (b,d). Then by the Cantor-Bernstein Theorem, the cardinality of (A x C) is equal to the cardinality of (B x D).
.

Why would you go to the lengths you have tried? I cannot follow them.
Look, we are given that A & B have the same cardinality so the is a bijection between them. Same statement for C & D. As was pointed out by THP it is simple to show that $\displaystyle \Phi :A \times C \leftrightarrow B \times D,\quad \Phi (a,c) = \left( {f(a),g(c)} \right)$ is a bijection.

5. Well I don't understand exactly what that means.

Is that the proof or do I need to show that the function h in his post is a bijection? I understand if it's a bijection, then the cardinality is the same, but I don't see why it's a bijection. Is it just obvious?

Basically, how do I prove that the function h defined by h(a,b) = (f(a),g(b)) is a bijection?

6. Originally Posted by PvtBillPilgrim
Well I don't understand exactly what that means.

Is that the proof or do I need to show that the function h in his post is a bijection? I understand if it's a bijection, then the cardinality is the same, but I don't see why it's a bijection. Is it just obvious?

Basically, how do I prove that the function h defined by h(a,b) = (f(a),g(b)) is a bijection?
Yup, you have to prove it.

If h(a,b)=h(a',b'), it means that (f(a),g(b))=(f(a'),g(b')) --> f(a)=f(a') and g(b)=g(b'). Since f and g are bijections, a=a' and b=b'. Thus h is an injection.

Let y in $\displaystyle B \times D$. To prove it's a surjection, you have to prove that there exist a and b in $\displaystyle A \times C$ such that h(a,b)=y.

7. If $\displaystyle h(p,q) = h\left( {r,s} \right) \Rightarrow \left( {f(p),g(q)} \right) = \left( {f(r),g(s)} \right)$ then by ordered pairs $\displaystyle f(p) = f(r)\,\& \,g(q) = g(s)$.
As both are injections we have $\displaystyle p = r\,\& \,q = s$. That proves $\displaystyle h$ is injective.

Suppose that $\displaystyle (j,k) \in B \times D \Rightarrow \quad j \in B \wedge k \in D$.
Because the junctions are both surjections we get:
$\displaystyle \left( {\exists a \in A} \right)\left[ {f(a) = j} \right]\,\& \,\left( {\exists c \in C} \right)\left[ {g(c) = k} \right] \Rightarrow \quad h(a,c) = \left( {j,k} \right)$.
That shows that $\displaystyle h$ is a surjection.
Or $\displaystyle h$ is a bijection!