## Cantor diagonalization, exponentials and speed table

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Xwerxes
Posts: 7
Joined: Sat Jun 22, 2013 12:01 pm UTC

### Cantor diagonalization, exponentials and speed table

I have been struggeling with a nagging feeling that there is a link between these subjects that I cannot quite get a grasp on.

if we construct our infinite squence of infinite sequences as simple counting with zero padding.

s(0) = 0...
s(1) = 10...
s(2) = 010...
...
and so on. Then all natural numbers will be enumerated. The diagonal would then be sd = 11...
A number in sd that at any sub index (i.e. from 1 to x) is going to be larger than any infinite series with the same index, i.e. s(x) = x but sd(x) = 2x - 1.

Now any number is going to be within the set s(x) as such 2x can be found at index s(2x) for any x.
So any subset of sd is going to be within s.

So is the impossibility of finding sd within the set of s(x) related to the faster growth of 2x?
and is the requirement of not just any faster growth (i.e. x2) related to the property of power sets?
i.e. that the cardinality of N is less than that of 2N but not so with N2?

If this is the case how about even faster growing functions (xx, busy beaver)?
Or are these functions less well defined in set theory and combinatorics perhaps?

gmalivuk
GNU Terry Pratchett
Posts: 26453
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Cantor diagonalization, exponentials and speed table

I don't understand what's motivating that choice of sequences, or how you get 2x from the diagonal.

Do you mean counting in binary (but with numerals reversed)? Because that's not clear from your post.

If that's the case, then sd isn't 11111..., it's 11000...
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Xwerxes
Posts: 7
Joined: Sat Jun 22, 2013 12:01 pm UTC

### Re: Cantor diagonalization, exponentials and speed table

As far as I understand one can pick any set of sequences for s. Wikipedia has
s(0) = 00000...
s(1) = 11111...
s(2) = 01010...
s(3) = 10101...

however I find that sequence harder to generalize and to be shure that it covers all natural numbers.

the counting in binary (in reverse yes so that you can have infinite sequences by zero padding) seems more straight forward to assure that all natural numbers are guaranteed to be covered by some simple algorithm.

sd would be the diagonal with 0->1 and 1->0 to make shure that it is not similar to any other number in the set. So should it not be 11111?
s(0) = 00000000
s(1) = 10000000
s(2) = 01000000
s(3) = 11000000
s(4) = 00100000

Eebster the Great
Posts: 3090
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

### Re: Cantor diagonalization, exponentials and speed table

I'm not sure you understand the diagonal argument. There is no need to "cover" the natural numbers. The natural numbers are the domain, and for every s(n), you pick some sequence. No matter which function s you pick (that is, no matter which list of sequences, whether binary counting or not), you can always construct an sd that is not in that list. Therefore, there is no function from the natural numbers onto the reals.

gmalivuk
GNU Terry Pratchett
Posts: 26453
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Cantor diagonalization, exponentials and speed table

Yeah, starting with one specific list of sequences isn't particularly helpful, because the proof depends on the fact that you could do the same thing for *any* such list.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Xwerxes
Posts: 7
Joined: Sat Jun 22, 2013 12:01 pm UTC

### Re: Cantor diagonalization, exponentials and speed table

Alright so the "off by one" argument is sufficient. Thanks for the clarification.

Although I would argue that any other list is the same one but sorted differently is it not?

 Indeed that is the justification of covering all numbers. The wikipedia set of numbers is also in there as is any otherm however perhaps in another order but that should not matter too much I belive

ucim
Posts: 6489
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

### Re: Cantor diagonalization, exponentials and speed table

Xwerxes wrote:Although I would argue that any other list is the same one but sorted differently is it not?
No. That's the supposition; that the list is complete (contains all the reals) and differs only in the order. But no matter how you do it, at least one number (the one you construct) will be missing. As it turns out, an infinite number of numbers is missing; an uncountably infinite number to boot.

There are an uncountably inifinite number of ways this can happen.

So no, no list you can actually construct is guaranteed to have a one-to-one correspondence (eta: where the selected elements from each set are equal) with any other arbitrary list you can also actually construct. They are not necessarily "the same but in a different order", even though it is possible to create such a list pair.

Jose
Last edited by ucim on Fri Jun 02, 2017 2:07 pm UTC, edited 1 time in total.
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

Eebster the Great
Posts: 3090
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

### Re: Cantor diagonalization, exponentials and speed table

It's easy to make functions s that are not bijections. For instance, I could have s(n) consist of n 0s followed by all 1s, so s(0)=111..., s(1)=0111..., s(2)=00111..., etc. Obviously that misses lots of sequences, like 10111..... The question is if it is possible to find a bijection, or if all possible functions s will leave out some sequence. The diagonal argument shows that no matter what s you choose, it is always possible to construct a sequence that never shows up in s, and therefore s is never a bijection. By definition, an infinite set is "countable" if and only if there exists some bijection between it and the natural numbers. There does not exist one for the set of real numbers, so the set of real numbers is not countable.

Xwerxes
Posts: 7
Joined: Sat Jun 22, 2013 12:01 pm UTC

### Re: Cantor diagonalization, exponentials and speed table

ucim wrote:
Xwerxes wrote:Although I would argue that any other list is the same one but sorted differently is it not?
No. That's the supposition; that the list is complete (contains all the reals) and differs only in the order. But no matter how you do it, at least one number (the one you construct) will be missing. As it turns out, an infinite number of numbers is missing; an uncountably infinite number to boot.

There are an uncountably inifinite number of ways this can happen.

So no, no list you can actually construct is guaranteed to have a one-to-one correspondence with any other arbitrary list you can also actually construct. They are not necessarily "the same but in a different order", even though it is possible to create such a list pair.

Jose

Ah, that is a clear point onto my missunderstanding. I thought it was construction of a new number from a full set not that we could prove that the full set was not full to begin with.

Thanks for the clarification

Eebster the Great
Posts: 3090
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

### Re: Cantor diagonalization, exponentials and speed table

ucim wrote:So no, no list you can actually construct is guaranteed to have a one-to-one correspondence with any other arbitrary list you can also actually construct.

I guess by "one-to-one correspondence" you mean actually having the same elements? Because all sequences are countable, so there will certainly be a bijection between any two sequences.

ucim
Posts: 6489
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

### Re: Cantor diagonalization, exponentials and speed table

Eebster the Great wrote:I guess by "one-to-one correspondence" you mean actually having the same elements?
Yes, that is what I mean. Perhaps I should have said "one-to-one identity"; an element by element statement that the sets are (or are not) equal to each other. Equality cannot be guaranteed; the sets can have different "missing" elements.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

Eebster the Great
Posts: 3090
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

### Re: Cantor diagonalization, exponentials and speed table

Yeah that makes sense. Also, one list (function's range) can be a proper subset of another('s). You can even have a countably infinite set of sets of sequences with each member of the set a proper subset of another (i.e. A⊃B⊃C⊃..., where each A,B,C,... is the range of some function sA, sB, sC, etc., each a function from N to R).

The set of real numbers is much larger than the set of natural numbers.