# Cardinality of Cartesian Product

1. May 11, 2008

### sujoykroy

Can you prove the following theory of cardinality for a Cartesian product, -
$\left|\:A\:\right|\:\leq\:\left|\:A\:\times\:B\:\right|\: if\: B\neq\phi$

In English,
The cardinality of a set $A$ is less than or equal to the cardinality of Cartesian product of A and a non empty set $B$.

2. May 11, 2008

### Hurkyl

Staff Emeritus
What have you tried? What methods can you use? What ways of restating the problem have you considered?

3. May 11, 2008

### tiny-tim

Hi sujoykroy!

In problems like this, just write out the definition, and then plug the problem into it.

So … what is the definition of "cardinality of P ≤ cardinality of Q"?

oh … and … what is the definition of "non empty set"?

4. May 11, 2008

### sujoykroy

I think, if you pick up a binary relation $f$ in such way that $f\left(\:a\:\right)\:=\:\left(\:a\:,\:b\:)$ for some $b\:\in\:B$ for all $a\:\in\:A$, then $f$ will be a one-to-one function with $dom\:f\:=\:A$ and $ran\:f\:\subset\:A\:\times\:B$, hence proving that $\left|\:A\:\right|\:\leq\:\left|\:A\:\times\:B\:\right|\: if\: B\neq\phi$, but i am not sure if the approach is right or not.

Below is the definition of cardinality that i am using,

5. May 11, 2008

### Hurkyl

Staff Emeritus
Well, try formalizing it. If you wind up with a valid proof, then your approach is right.

6. May 11, 2008

### sujoykroy

Thanks. Actually i was trying to understand/prove the use/existence of Infinite Sequence used in various proof of Cantor-Schroder-Bernstein i.e. if $\left|X\right|\:\leq\:\left|Y\right|$ and $\left|Y\right|\:\leq\:\left|X\right|$ then $\left|X\right|\:=\:\left|Y\right|$ and current problem was a doorway to open up the logical window towards it. So, formalization was not really my problem, i just needed to get confirmation if the logic is correct.

7. May 11, 2008

### tiny-tim

Hi sujoykroy!

Yes, that's the one … so, in this case, you need to define a one-to-one f on A into A x B.

And to do that, answer the question: what is the definition of "non empty set"?

(it may sound a daft question … but sometimes maths is like that! )

8. Sep 9, 2008

### rich292

I also have a quick query regarding something related to cardinality of a cartesian product.

What does $$\left|A\right|$$ = $$\left|A \times \aleph\right|$$for any set A, tell you about A?

I hope to use this to find an injective function from $$\aleph^{A}$$to $$\left\{0,1\right\}^{A}$$

9. Sep 9, 2008

### CRGreathouse

You need the Axiom of Choice, as far as I can tell. But once you apply the Axiom, it's pretty simple, assuming your definition of A <= B is that there is an injection from A to B (a bijection from A to a subset of B).

10. Sep 3, 2010

### Hurkyl

Staff Emeritus
I think you misread the problem.

11. Sep 3, 2010

### xplo99

Yes, that I did