# Discrete Math - Cardinals

• Aug 23rd 2009, 09:36 AM
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! :)
• Aug 23rd 2009, 09:57 AM
Plato
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.
• Aug 23rd 2009, 10:14 AM
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...
• Aug 23rd 2009, 10:44 AM
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!!! :)
• Aug 23rd 2009, 11:21 AM
Plato
Quote:

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.
• Aug 23rd 2009, 11:34 AM
Liwuinan
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".
• Aug 23rd 2009, 11:39 AM
Thanks (Yes) !!
• Aug 23rd 2009, 12:51 PM
Plato
Quote:

Originally Posted by Liwuinan
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.
• Aug 23rd 2009, 01:14 PM
Liwuinan
Quote:

Originally Posted by Plato
You don't need a function.

Yes, I too think that your argument (without function) is clear enough.

Quote:

Originally Posted by Plato
I hope you don't think that http://www.mathhelpforum.com/math-he...7ce70ea9-1.gif has to be rational.

I never said so. (Lipssealed)