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