It's Like Infinity, But Bigger!

[BonJoviJones]

So in the "basic question" thread below, the conversation veered to when P(X)=1 and P(X)=0 aren't certainties given infinite sets to work with. I'm intrigued and curious.

Here's my informal proof, anybody want to comment?

(I should note that this started as a "I don't get this post", but half-way through I think I figured it out. I'm quite proud [img]/forums/images/icons/wink.gif[/img])

A guy has a box of colored balls. There is one red ball, and the rest are yellow. If N is the number of balls in the bag, and R is picking a red ball:

P(R) = (lim n->inf) 1/N

This means that P(R)=0 _but_ there is still a red ball in there somewhere, and it can still be drawn.

Am I on track so far?

So let's expand to BruceZ's number example, which I'll rephrase as:

Given an infinite precision random number 0 to 1 inclusive, what is P(Rational Number)?

Using the above ball problem as a template, we get:

P(R) = (rational numbers)/(irrational numbers)

(My calc skills are breaking down, but we want the limit as rational numbers approach infinity, and as irrationtals approach infinity _faster_.)

Given that irrationals are uncountably infinite, while rationals are merely countably infinite it should boil down to P(R) = 0, but like the ball problem it's still possible to get a rational number.

How's that?

[Mano]

Your thinking along the right lines, but it isn't that simple. There are uncountably infinite subsets of the of the unit segment such as the Cantor set, which nonetheless have a measure of zero (and hence a probability of zero of choosing if you randomly pick a number between zero and 1). It comes down to a branch of mathematics called measure theory. A space is "measurable" if you can define a function from certain subsets of the space to the real numbers that satisfies certiain axioms, like the measure of the union of two disjoint subsets is the sum of their measures. Probability is the study of measurable spaces with a measure of 1. I'd have to dig out my old college math stuff to go much deeper than this ( I haven't really looked at any of it in over 10 years). Clear as mud, huh. [img]/forums/images/icons/wink.gif[/img] Anyway, that's my 2 cents on the subject.

[brad]

'Given that irrationals are uncountably infinite, while rationals are merely countably infinite '

so youre saying that say between 0 and 1 exclusive there are more irrationals than rationals? i know some infinite sets can be bigger than other infinite sets so i guess.

but how do u know?

[BonJoviJones]

"but how do u know?"

Hehe, I know because professors have shown and explained the proof [img]/forums/images/icons/smile.gif[/img]

[BruceZ]

The proof goes like this. Suppose the irrationals could be put in one-to-one correspondence with the integers. Think of this as a list of irrationals. Then we could form a new irrational number by making its nth decimal digit different from the nth decimal digit of the nth element on the list for all n. This number is not on the list because it differs from each element of the list in at least one digit. So the list does not contain all the irrationals, thus no such list can exist; no such one-to-one correspondence between integers and irrationals can exist, and irrationals are uncountably infinite. Rationals are countably infinte because we can form a one-to-one correspondence with the integers by simply enumerating all fractions p/q.

[PseudoPserious]

Very succinctly stated, BruceZ. Nice.

PP

[BruceZ]

I just thought of an aspect of this I haven't seen before. Suppose we try to make this same argument for the rationals. Rationals either terminate after a finite number of decimal places or else they repeat. For simplicity let's just consider the ones that terminate. Since the rationals are countably infinite, the ones that terminate must also be countably infinte. As before, assume a list of all the terminating rationals. The numbers on this list get as long as you like, but they all terminate. Again form a new number by changing the nth place of every nth element on the list for all n. Again this number isn't on the list, but in this case it doesn't need to be because this number either repeats or is irrational! The reason is that it has an nth decimal digit for all n, meaning it does not terminate. It's kind of interesting that we formed a non-terminating number by changing the decimal places of rational numbers which all terminate.