# Cardinality of Cartesian Product

## Main Question or Discussion Point

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$.

## Answers and Replies

Related Set Theory, Logic, Probability, Statistics News on Phys.org
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
What have you tried? What methods can you use? What ways of restating the problem have you considered?

tiny-tim
Science Advisor
Homework Helper
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"?

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

considered?
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.

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"?
Below is the definition of cardinality that i am using,
The cardinality of a set $A$ is less than or equal to the cardinality of a set $B$ if there is a one-to-one function $f$ on $A$ into $B$

Hurkyl
Staff Emeritus
Science Advisor
Gold Member
but i am not sure if the approach is right or not.
Well, try formalizing it. If you wind up with a valid proof, then your approach is right.

Well, try formalizing it. If you wind up with a valid proof, then your approach is right.
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.

tiny-tim
Science Advisor
Homework Helper
Below is the definition of cardinality that i am using,

"The cardinality of a set A is less than or equal to the cardinality of a set B if there is a one-to-one function f on A into B"
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! )

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}$$

CRGreathouse
Science Advisor
Homework Helper
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).

Hurkyl
Staff Emeritus
Science Advisor
Gold Member
I think you misread the problem.

Yes, that I did