Cardinality of Cartesian Product

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

 

[Hurkyl]

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

 

[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"?

 

[sujoykroy]

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]

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.

 

[sujoykroy]

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]

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! )

 

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

 

[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).

 

[Hurkyl]

I think you misread the problem.

 

[xplo99]

Yes, that I did