Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cardinality of Cartesian Product

  1. May 11, 2008 #1
    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].
     
  2. jcsd
  3. May 11, 2008 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What have you tried? What methods can you use? What ways of restating the problem have you considered?
     
  4. May 11, 2008 #3

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    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:
     
  5. May 11, 2008 #4
    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.

    Below is the definition of cardinality that i am using,
     
  6. May 11, 2008 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, try formalizing it. If you wind up with a valid proof, then your approach is right. :smile:
     
  7. May 11, 2008 #6
    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.
     
  8. May 11, 2008 #7

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    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:)
     
  9. Sep 9, 2008 #8
    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]
     
  10. Sep 9, 2008 #9

    CRGreathouse

    User Avatar
    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).
     
  11. Sep 3, 2010 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I think you misread the problem.
     
  12. Sep 3, 2010 #11
    Yes, that I did
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Cardinality of Cartesian Product
  1. Cartesian product (Replies: 7)

  2. The Cartesian Product (Replies: 9)

  3. Cartesian Products (Replies: 7)

Loading...