cardinality of subset of irrationals?

[zaphod]

lets say i've got this subset T of irrational numbers that i want to prove is non-denumerable... how should i go about this?

 

i'm not seeing any way of diagonalizing without guaranteeing that the new number will still be in T.

 

any pointers?

[matt grime]

Depends on what the set of irrational numbers is. Why don't you say?

[zaphod]

hehe, yeah, i was kind of in a rush to leave work when i posted that last night. i realized after that i should have been more specific.

 

its quite a long story from another messageboard concerning whether or not your phone number could ever be found in pi. there was a website where you can search the first 2 million decimal places of pi to see if a certain string of numbers is in there.

 

anyway, debate started about whether or not it was absolutely guaranteed that anybody's phone number was going to be in pi eventually since the decimal expansion is infinite and non-repeating.

 

i got sick of the debate, so i kinda sketched out a little mathematical argument against it. here's the copy/paste of the post i made:

 

ok' date=' here it is, once and for all.

 

Is it possible that someone's phone number is not in pi? This question can be generalized by asking the following:

 

[b']Is it possible that a 10 digit string might not be found in the decimal expansion of a number that is infinite and non-repeating?[/b]

 

To answer the question, we will take the set of numbers which are infinite and non-repeating, which is commonly known as the set of irrational numbers, and call it J (which can be found by subtracting the elements of set of rational numbers Q from the elements of the real numbers R.)

 

We will show that there exists at least one element of J, say j, where a given 10 digit string of numbers x is not found. For the purposes of this demonstration, we will choose x to be the following phone number: 416-555-2372, or 4165552372.

 

How do we find this element j of J? We can actually use our imagination and "create" one. For example, if we choose the following irrational number:

 

j = 0.12120120012000120000120000012000000120000000...

 

Would you be able to find x in this string of numbers? The way j is constructed, it would be impossible to find x. We have therefore shown that is is indeed possible that a 10 digit string might not be found in the decimal expansion of a number that is infinite and non-repeating.

 

We can imagine now a subset of J, say S, which consists of all the elements of J that do not contain the string x = 4165552372. This new set S is known to contain at least one element, j.

 

Using the link earlier, we can do a quick search and find that the string x, "4165552372" does not occur in the first 200000000 digits of pi.

 

Now, does this prove that pi is an element of our set S? No, it does not. As far as we know, pi may or may not be an element of S since there is no real way to prove whether or not pi will eventually contain that string x.

 

However, what we have shown is that simply because pi's decimal expansion is infinitely long and non-repeating, this does not absolutely guarantee that everybody's phone number will be found somewhere.

 

-------------------------------

 

In other words, we take a 10 digit string called r. We can create a subset of J, called T, whose elements t are irrational numbers that do not contain the string r. It is not known if pi is an element of T for any given r. It may or may not be. However, what we do know that for any given r, that there exists a non-empty set T.

 

The very existence of this non-empty set T disproves the assertion that any string of numbers must eventually be found in the decimal expansion of an irrational number.

 

now, this set T is the set in question.

[matt grime]

Of course the assertion: any string of numbers can be found in the decimal expansion of any irrational number is false. I don't see why anyone would think otherwise.

 

What is true is that pi is thought to be normal, and thus any finite string of digits should appear at some point in the decimal expansion almost surely (i.e. with probability 1, which is *not at all* the same thing as saying it must happen).

 

 

And in answer to the final question, fix an r and let T be the irrational numbers in which r does not appear in the decimal expansion, then T is definitely uncountable, as is the complement of T in the set of irrational numbers.

 

 

To show the former here's a messy way of doing it. Take you string r, and let x be a digit that is not the first nor last digit of r, and let y be a string of that digit repeated 10 times. Construct the following set:

 

S:={ s in R: s = 0.s(1)ys(2)ys(3)y....}

 

where s(i) is any string of 10 digits except r, and such that s is irrational.

 

1. S is a subset of T: any substring of ten digits is one of the s(i) or starts or ends with x, and is then not equal to r.

 

2. For s in S consider the set X:= { x : x= 0.s(1)s(2)s(3)...} ie now delete the y strings. S and X are in bijection. But X is just the set of irrationals written in base 10^10 with one string of 10 digits omitted from the expansion, and now it doesn't matter what the string is so we may as well assume it is 9999999999, and X is now clearly in bijection with the set of irrational numbers written in base 9999999999 hence we have a bijection from a subset of T onto the irrationals in the interval (0,1) which is uncountable.

 

3. note these shenanigans were purely to avoid the possibility that r might occur as a string overlapping any splitting of a number into substrings.

[zaphod]

brilliant. thanks.

[zaphod]

hmmm.. however, i'm thinking about this part:

 

"where s(i) is any string of 10 digits except r"

 

this would be a finite number of strings, right?

[matt grime]

And? There are 10^10 - 1 such, but what does that have to do with anything?

[zaphod]

i'm just not clear on how you can guarantee that s is irrational given that the number of strings s(i) is finite.

[matt grime]

Here's a far far better explanation of the same thing.

 

Get your string of ten digits r. Pick some digit that is not the first or last digit of r, well, what the heck, we can suppose it is zero.

 

Consider this injection from the irrationals to T.

 

take an irrational, insert 11 zeroes between each digit in the decimal expansion. The result is irrational and in T (because any string of ten digits must start or end with a zero and we're assuming that r neither starts nor ends with a zero) and it is an injection.

[matt grime]

i'm just not clear on how you can guarantee that s is irrational given that the number of strings s(i) is finite.

 

You don't see how to get irrational numbers from gluing together strings of finite length? Every irrational is gotten by gluing together strings of length 1 and there are only 10 of those.

[zaphod]

You don't see how to get irrational numbers from gluing together strings of finite length? Every irrational is gotten by gluing together strings of length 1 and there are only 10 of those.

 

its not that i'm not clear on how you get a number that is infinitely long, but since the actual number of strings you're gluing together is finite, then i'm just not clear on how you can guarantee the "non-repeating" condition.

 

but i'm still reading over your "far far better explanation" right now, so i'll get back to you.

 

(and hey, by the way, i'm on your side. dont see this as a debate between me and you. its just math )

[zaphod]

You don't see how to get irrational numbers from gluing together strings of finite length? Every irrational is gotten by gluing together strings of length 1 and there are only 10 of those.

 

to clarify my unease, lets pretend there were only 10 strings s(i).

 

s would look something like this: s = 0.s(0)ys(1)ys(2)ys(3)ys(4)ys(5)ys(6)ys(7)ys(8)ys(9)ys(1)ys(2)ys(3)ys(4)y....

 

which would not be very irrational, right?

[matt grime]

But why are you only allowing yourself to glue them together in that obviously repeating fashion? I didn't say anything about cycling through them like that. You have to allow all possible ways of gluing the 10^10 - 1 strings together, just like you have to allow for all possible ways of gluing the digits 0,1,..,9 together to get all decimal expansions of all numbers.

 

 

You don't think that the only decimal number is

 

0.123456789012345678901234567890...

 

do you? But that is equivalent to what you've written.

[zaphod]

ok, so is there a way to re-define your set S that clearly defines how to cycle through the finite number of strings so as to make sure the cycles never repeat?

 

is there not only a finite number of combinations possible?

 

(be back in an hour, lunch time)

[matt grime]

What I defined does that already: start with all possible strings if you must then take those that define irrational numbers. These are in bijection with all irrational numbers so there must be an infinite number of them: there is no need to count them at the beginning.

 

There is clearly an uncountable number of possible gluings and only countably many of them are rational, this in itself is enough of a proof now I come to think of it. There that is three proofs for you: all of the stuff I did after this point in the original is just proving that there are indeed uncountably many possible gluings in painstaking detail.

 

I'm just making irrational numbers in base 10^10, and it is exactly the same as making irrational numbers in base 10. I'm not going to go through the details anymore if you don't see them because

 

1. they're clear, if you don't see it replace strings of '10 digits' with strings of '1 digit' and think about *all* parts of the replies I've given you pointing out what your line of reasoning implies.

 

 

2. I've given you two better proofs.

[zaphod]

after thinking about it over lunch, i understand. thank you for the (somewhat patronizing) explanations, matt

[matt grime]

thank you for the (somewhat patronizing) explanations, matt

 

I think exasperated is a better word. Patronizing would seem to imply that I was explaining something to you that you understood in an overly elaborate manner. Still, if you want to insult me after the help I voluntarily gave then feel free; I shan't bother to help again, then, if you find it patronizing.

[zaphod]

i just feel that you got "exasperated" very quickly if your first response to one of my fairly basic questions was:

 

"And? There are 10^10 - 1 such, but what does that have to do with anything?" (implied emphasis denoted)

 

i apologize if your initial response was perhaps not as clear to everyone as it is to you, and that questions about it came up.

 

perhaps next time, you should add a disclaimer to your explanations stating that your line of reasoning has been double checked by god himself and that no questions about the integrity of your answers shall be tolerated.

 

i've never had any beef with you in any of my posts, and i didnt mean to "insult" you. i just think that as an official "math expert" of the board, it shouldnt be too much to ask to explain something that you wrote without giving off the very distinct tone of talking down to the person in question.

 

in closing, thank you for your help. good day.

[matt grime]

i just feel that you got "exasperated" very quickly if your first response to one of my fairly basic questions was:

 

And i feel you didn't take very long to think about it, that you kept ignoring important points that I repeatedly had to make to attempt to get you to notice them, which would certainly seem like patronization.

 

"And? There are 10^10 - 1 such, but what does that have to do with anything?" (implied emphasis denoted)

 

That would be ' inferred emphasis denoted'. I did not put that emphasis there, you did. I did not imply it, you inferred it. As I pointed out every irrational (or rational) number is gotten by stringing together only ten different strings that are 1 digit long. You kept ignoring that and apparently not thinking about it.

 

 

 

 

perhaps next time, you should add a disclaimer to your explanations stating that your line of reasoning has been double checked by god himself and that no questions about the integrity of your answers shall be tolerated.

 

My reasoning is frequently wrong. As can be demonstrated by the fact that the original explanation is now third in quality in the list of ones presented here.

 

i've never had any beef with you in any of my posts, and i didnt mean to "insult" you. i just think that as an official "math expert" of the board,

 

I hate the bloody tag. It doesn't mean I am anything official here, indeed I am not anything official here. Surely the fact that I kept responding should at least count for something.

 

As you have now found sometimes 11 minutes (time between first post of thanks and next post of 'oh hang on..') is not sufficient to understand an explanation. You came back after lunch and it all seemed a whole lot easier. That is how I would expect it to work. And it might be worthwhile remembering that lack of patience rather than what you percieve as mine.

[zaphod]

anyway, long story short: i respect you. thank you for everything.