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

Equal Cardinality

  1. Mar 31, 2005 #1

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    O.K this has been bugging me all night since I first thought of it.

    How would I show the sets,

    [tex]\left\{ 0 < x < 1 \left| x \in \mathbb{R}\left\}[/tex]

    [tex]\left\{ 0 < x \leq 1 \left| x \in \mathbb{R}\left\}[/tex]

    Have equal cardinality?
     
  2. jcsd
  3. Mar 31, 2005 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Do you know the Schröder-Bernstein theorem? If you have a 1-1 map from A to B and a 1-1 map from B to A then A and B have the same cardinality.
     
  4. Mar 31, 2005 #3

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    I do in fact know that. Could you create a 1-1 map for this?
     
  5. Mar 31, 2005 #4

    Curious3141

    User Avatar
    Homework Helper

    In any set of uncountable cardinality, adding a countable number of elements to it will not alter the cardinality. In this case, you're adding a countable number (in fact, finite, just one element) to an uncountable set, and this axiom applies.
     
  6. Mar 31, 2005 #5

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Map each element that is not of the form 1/n (for natural n) to itself. Map the element 1/n from the second set to 1/(n+1) of the first set. This is clearly 1-1 and onto, so the two sets are bijective, and hence of equal cardinality.
     
  7. Mar 31, 2005 #6

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    A is your first set (without 1). A->B, take the identity mapping. B->A take x->x/2.
     
  8. Apr 1, 2005 #7

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    I'm quite aware of that but I have not seen a proof.

    Where does that map the element 2/3 to an element in the other set?

    I don't get that at all :frown:
     
  9. Apr 1, 2005 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    In AKG's post the function maps the element 2/3 to 2/3 just like it states here:

    "Map each element that is not of the form 1/n (for natural n) to itself."

    And secondly,

    A=(0,1) B=(0,1]

    the map f(x)=x is an injection from A to B, shmoe's identity mapping. Which part of that is causing confusion.

    The map g(x)= x/2 is an injection from B to A.

    Hence, by the Cantor, bernstein, schreoder theorem there exists some bijection between A and B.

    go through it step by step; which part is the problem.


    In general, there is bijection map from S to S' where S is any uncountable set and S' is S less a countably infinite set of points.

    Let S' = S\{x_1,x_2,..}

    since S' is infinite (otherwise S would be the union of {x_1,...,} and a finite set, there is a sequence y_1,y_2,.... indexed by the natural numbers.

    Define a map from S to S' via x_r is sent to y_{2r}, y_t is sent to y_{2t-1}, and every other element is sent to itself. This is a bijection between S and S'

    The proof when S' is S less any finite number of points is left as an exercise.
     
  10. Apr 1, 2005 #9

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    O.K thanks, I kind of get that, well still not shmoe's post but I think I get the general idea of AKG's.
     
  11. Apr 1, 2005 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Well, do you actually know what the Cantor Bernstien Shroeder theorem states?

    If X any Y are two sets and f is an injection from X to Y and g is an injection from Y to X then there exists a bijection between X and Y. The proof is elegant, fi you look it up. Anyway, shmoe wrote down two obvious injections. So, is it the injectivity part you don't follow, or was it that you didn't properly know what C-B-S states?
     
  12. Apr 1, 2005 #11

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    Yes I was aware of what it states it's just I doubt I fully understood what it meant as the course I took that covered this was childish so most the mathematics I've taught myself. I guess I do actually get it now, just seemed rather odd to start off with.

    Thanks for helping my understand.
     
  13. Apr 1, 2005 #12

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    What it does is allow us to make a relation on cardinal numbers.

    Given two sets, we'll say |X| <=|Y| iff there is an injection between them. C-B-S allows us to state that

    if |X|<=|Y| and |Y|<=|X|, then in fact |X|=|Y|.

    This isn't a trivial theorem, adn if we were to instead use surjections, then the proof that this is an ordering would require the axiom of choice. The injection version doesn't. For me that is neither here nor there, but some people like to avoid the axiom of choice. and you need to admit it is a little odd that this is true.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Equal Cardinality
  1. Cardinality of R^N (Replies: 1)

  2. Are these equal? (Replies: 2)

Loading...