Results 1 to 9 of 9

Math Help - Discrete Math - Cardinals

  1. #1
    Member
    Joined
    Jul 2009
    Posts
    168

    Discrete Math - Cardinals

    Let 'A' be a set of open lines on the real axis, so that every two lines in this group are disjoint. Prove that |A| is lower or equal to 'Alef 0' (the cardinal number of the Natural numbers - |N|='Alef 0' )

    Clue: Think of a finite line - how many lines that belong to A can be have the length equal or bigger than (1/n) in this line? (the length of the line (a,b) is a-b * )

    *I believe this is a mistake, and they should have written b-a (considering that b>a)

    *In case my way of explaining it in English was not quite clear - an open line can be, for instance (0,3) meaning that 0<x<3 for every x in the line. Every two lines in this group are disjoint, means that they have no common elements.

    Thank you very much!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    This is really hard to answer not knowing what you have to work with.
    This is a really simple proof it you know two facts about the real numbers: the rational numbers for a countable set and the rational numbers are dense in the reals.

    Here is the proof. In each open interval there is a rational number.
    Because these open intervals are pairwise disjoint, the collection is at most countable.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2009
    Posts
    168
    Thank you very much Plato, but I'm afraid I'll have to find a full proof for that. We also haven't learned 'density', so I surely can't use it.

    There's something else I didn't understand - you said that there is a rational number in each interval, and that makes it most countable, but what if I find an irrational number in one of the intervals?

    Oh, I think I understand you - it doesn't matter ^ if there is an irrational number - you meant that IF we can find a rational number K in each interval, then we'll name the interval '1' or '2' , . . ., and since these K1, and K2 are located in different intervals, so K1 is surely not equal to K2. That means, that if K1, K2, . . . are rational numbers, then this is most countable.

    Aha! very nice proof! I really like it... but it's a little weird for me, because in the class we always proved such things with functions...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jul 2009
    Posts
    168
    Okay, now I completely understood it !

    I am also able to show this with a function (the more common and 'formal' way where I study) - I say that ri is the smallest rational number between ai and bi,.

    Then, I create a function from the group A={(ai,bi) | iEI} (and another phrase to show that every two sets in this group are different)

    I create a function from A to Q, like this:

    g((ai,bi))=ri .

    Then, all I need to show that if

    g(k)=g(j) then k=j, which is easy, because there can't be two different ri, rj that are equal while i and j aren't.

    THANK YOU SO MUCH!!!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    Quote Originally Posted by adam63 View Post
    I am also able to show this with a function (the more common and 'formal' way where I study) - I say that ri is the smallest rational number between ai and bi,.
    That is a big mistake.
    The is no smallest rational in (a,b).
    But you can use a choice function to pick exactly one.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Aug 2009
    Posts
    25
    Hi Adam and Plato, I am new here, just wanted to say Hi and I hope we can avoid axiom of choice if we define our function for example like this: "for every (a,b) from A, decimal expansion of number r is the shortest initial segment of the decimal expansion of number (a+b)/2, such that a<r".
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jul 2009
    Posts
    168
    Thanks !!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    Quote Originally Posted by Liwuinan View Post
    Hi Adam and Plato, I am new here, just wanted to say Hi and I hope we can avoid axiom of choice if we define our function for example like this: "for every (a,b) from A, decimal expansion of number r is the shortest initial segment of the decimal expansion of number (a+b)/2, such that a<r".
    I hope you don't think that \frac{a+b}{2} has to be rational.
    Anyway, we can avoid choice (what is wrong with choice?).
    If the collection \{(a,b)\in A\} is not countable then the set of rationals is not countable as first said. You don't need a function.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Aug 2009
    Posts
    25
    Quote Originally Posted by Plato View Post
    You don't need a function.
    Yes, I too think that your argument (without function) is clear enough.

    Quote Originally Posted by Plato View Post
    I hope you don't think that has to be rational.
    I never said so.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Discrete Math - Cardinals
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 13th 2009, 01:02 PM
  2. Discrete Math!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 9th 2008, 12:11 PM
  3. Discrete math
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 22nd 2008, 01:56 AM
  4. Discrete Math
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 26th 2007, 06:30 PM
  5. Discrete Math
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 26th 2007, 06:26 PM

Search Tags


/mathhelpforum @mathhelpforum