Cardinality of Cartesian Product

  • Thread starter sujoykroy
  • Start date
  • #1
18
0

Main Question or Discussion Point

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

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

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
17
What have you tried? What methods can you use? What ways of restating the problem have you considered?
 
  • #3
tiny-tim
Science Advisor
Homework Helper
25,832
249
Hi sujoykroy! :smile:

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"? :smile:

oh … and … what is the definition of "non empty set"? :biggrin:
 
  • #4
18
0
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 [itex]f[/itex] in such way that [itex]f\left(\:a\:\right)\:=\:\left(\:a\:,\:b\:)[/itex] for some [itex]b\:\in\:B[/itex] for all [itex]a\:\in\:A[/itex], then [itex]f[/itex] will be a one-to-one function with [itex]dom\:f\:=\:A[/itex] and [itex]ran\:f\:\subset\:A\:\times\:B[/itex], hence proving that [itex]\left|\:A\:\right|\:\leq\:\left|\:A\:\times\:B\:\right|\: if\: B\neq\phi[/itex], but i am not sure if the approach is right or not.

Hi sujoykroy! :smile:

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"? :smile:

oh … and … what is the definition of "non empty set"? :biggrin:
Below is the definition of cardinality that i am using,
The cardinality of a set [itex]A[/itex] is less than or equal to the cardinality of a set [itex]B[/itex] if there is a one-to-one function [itex]f[/itex] on [itex]A[/itex] into [itex]B[/itex]
 
  • #5
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
17
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. :smile:
 
  • #6
18
0
Well, try formalizing it. If you wind up with a valid proof, then your approach is right. :smile:
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 [itex]\left|X\right|\:\leq\:\left|Y\right|[/itex] and [itex]\left|Y\right|\:\leq\:\left|X\right|[/itex] then [itex]\left|X\right|\:=\:\left|Y\right|[/itex] 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
tiny-tim
Science Advisor
Homework Helper
25,832
249
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! :smile:

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! :smile:)
 
  • #8
1
0
I also have a quick query regarding something related to cardinality of a cartesian product.

What does [tex]\left|A\right|[/tex] = [tex]\left|A \times \aleph\right|[/tex]for any set A, tell you about A?

I hope to use this to find an injective function from [tex]\aleph^{A}[/tex]to [tex]\left\{0,1\right\}^{A}[/tex]
 
  • #9
CRGreathouse
Science Advisor
Homework Helper
2,820
0
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
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
17
I think you misread the problem.
 
  • #11
1
0
Yes, that I did
 

Related Threads for: Cardinality of Cartesian Product

Replies
4
Views
10K
  • Last Post
Replies
11
Views
4K
  • Last Post
Replies
9
Views
10K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
4
Views
633
  • Last Post
Replies
8
Views
4K
Replies
3
Views
2K
Top