Thread: 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!

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.

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...

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!!!

Originally Posted by adam63

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 .
But you can use a choice function to pick exactly one.

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".

Thanks !!

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 has to be rational.
Anyway, we can avoid choice (what is wrong with choice?).
If the collection is not countable then the set of rationals is not countable as first said. You don't need a function.

Originally Posted by Plato

You don't need a function.

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

Originally Posted by Plato

I hope you don't think that has to be rational.

I never said so.