Question

Show that if A,B,C and D are sets |A| = |B| and |C| = |D| then$|\mathrm{A}\times \mathrm{C}|=|\mathrm{B}\times \mathrm{D}|$

Short answer

If h is one-to-one and onto, h is one-to-one correspondence from $A\times C$to$B\times D$ , then$\left|A\times C\right|=\left|B\times D\right|$

Step-by-step solution

Step 1

Definition:

The power set of S is the set of all subsets of S .

Notation: P (s)

The function is onto if and only if for every element $b\in B$there exist an element $a\in A$such that $f\left(a\right)=b$

The function f is one-to-one if and only if f (a) = f (b) implies that a = b for all a and b in the domain.

f is a one-to-one correspondence if and only if f is one-to-one and onto.

Definition (1): $\left|A\right|=\left|B\right|$if and only if there is a one-to-one correspondence from A to B .

Step 2

Given: A,B,C and D are sets with |A| = |B| and |C| = |D|

To proof: $\left|A\times C\right|=\left|B\times D\right|$

By definition : There exists a one-to-one correspondence f from A to B (since $\left|A\right|=\left|B\right|$).

By definition : There exists a one-to-one correspondence g from C to D ( since $\left|C\right|=\left|D\right|$).

We can then define the function h as:

$h:A\times C\to B\times D,h(a,c)=\left(f\right(a),g(c\left)\right)$

h is one-to-one: Let $g(a,c)=g(x,y)$, by definition of $g:\left(f\right(a),g(c\left)\right)=\left(f\right(x),g(y\left)\right)$which implies since is a one-to-one correspondence and c = y since g is a one-to-one correspondence. Thus we have then shown that is one-to-one. h is onto: Let (b,d) $\in B\times D$.

Since f is a one-to-one correspondence, there exists an element $a\in A$such that $f\left(a\right)=b$.

Since g is a one-to-one correspondence, there exists an element $c\in C$such that g (c) = d Combining, we then obtain: and thus is onto.

Since h is one-to-one and onto, is one-to-one correspondence from $A\times C\text{to}B\times D$.

By definition : $|A\times C|=|B\times D|$