Here is what I am confused about with regards to diagonalisation:
Start with binary non-negative integers:
000
001
010
011
100
101
... (goes to infinity)
This set now includes all possible bit strings of infinite length since the way these are iteratively generated includes all possibilities.
This is also an enumerable set by definition.
Let's now reverse the bits and put them after a decimal. These are just real numbers now going from zero to one. (This step is actually unnecessary I think.)
.000
.100
.010
.110
.001
.101
.011
...
This must be enumerable set too.
Using diagonalisation argument, .111111 is never to be found in this set. This is exactly where I am stuck. This number comes into the set from flipping of infinity in the original set, which includes all possible stings of infinite length.
I immediately read into your message on treating these as bit strings instead of real numbers. I still am stuck though. (Do you also see a connection to 0.99999... by the way?)
> Start with binary non-negative integers:
> 000 001 010 011 100 101 ... (goes to infinity)
> This set now includes all possible bit strings of
> infinite length
No, it only contains the strings of finite length. There are infinitely many of them, but each one stops after a while. In particular, then n^th one only has log2(n) places before it then becomes all 0s.
> This is also an enumerable set by definition.
Yes.
> Let's now reverse the bits and put them after a decimal.
> These are just real numbers now going from zero to one.
> ... .000 .100 .010 .110 .001 .101 .011 ...
But not all of them, since these are only those numbers that have a finite number of 1's in them.
> This must be enumerable set too.
Yes it is.
> Using diagonalisation argument, .111111 is never to be
> found in this set.
Irrelevant.
> This is exactly where I am stuck. This number comes
> into the set from flipping of infinity in the original set,
"Infinity" was never in your original set. And if it was, it wouldn't be produced by the diagonalisation argument.
> which includes all possible strings of infinite length.
The set is still enumerable since this is just binary encoding mapping to the set {0, 1, 2, 3, ...}
The question still is if it covers all possible bit strings of infinite length.
For units place, we covered both zero and one. For (n+1)th place, we cover both zero and one together with all combinations for the first (n) bits. As n -> infinite, all possibilities get covered.
The question is if 111111111... is also there in this set. But isn't it there too?
> For the first set, I meant to write:
> [Prepend each string with infinite zeroes]
> ...000
> ...001
> ...010
...
If there are infinitely many zeros on the front, you can't actually append anything. That doesn't end up being well-defined.
(Well, actually, there are transfinite ordinals, but that would confuse the issue. It's not what you mean, and it doesn't help)
> Now all bit strings here have infinite length.
If you want to talk about an infinite "decimal" string, you need to talk about the things that come after the decimal point, in order. As such, they come in order, and you can't have infinitely many zeros and then a finite string on the end.
> The string is still enumerable since this is just binary
> encoding mapping to the set {0, 1, 2, 3, ...}
You need to be more careful about how you actually define the strings. Strings have a start, then they go on one place by one place.
> The question still is if it covers all possible bit strings of
> infinite length.
Well, you haven't actually properly defined strings, but even so, no. Everything you have starts with a zero.
> For units place, we covered both zero and one.
No, you don't seem to have.
> For (n+1)th place, we cover both zero and one
> together with all combinations for the first (n) bits.
> As n -> infinite, all possibilities get covered.
No, because as soon as you have a one in your expansion the string is finite, so not all possibilities are covered.
> The question is if 111111111... is also there in this set.
> But isn't it there too?
You defined the set - tell me where it is. Even leaving alone the fact that these aren't proper strings, it doesn't appear to be there.
>>> [Prepend each string with infinite zeroes]
> ...000
> ...001
> ...010
>> If there are infinitely many zeros on the front, you can't actually append anything.
I am lost. In this first set, I do not have a decimal point anywhere. Why cannot I have an infinitely many zeros to the left of 1. It will still be just one when looked at as a number.
>> Strings have a start, then they go on one place by one place
As far as representing it as a string, I may still start from the right and work towards the left.
I understand your point for the decimal case, infinitely many zeroes on the right of decimal cannot be followed a finite string. My argument does not require this however. (I change ...00000011010 from the first set to .0101100000000... in the second set.)
>> > For units place, we covered both zero and one.
>> No, you don't seem to have.
The units place is the rightmost below. Both zero and one are covered.
...000
...001
Stating the above for the decimal case, let n=1 be the place right after the decimal, n=2 to the right of it, and so on. Now for place n=1, the both zero and one are covered (first two cases below). For n=2 place, again both zero and one are covered for all possible combinations above for n=1 place (first four cases below).
Using the mathematical induction argument, all combinations are covered. This must include 0.1111111111... It sits exactly where (simple) infinity sits in the enumerable set {0, 1, 2, 3, ... }
OK, so you're not talking about the usual diagonalisation. I'll try to follow what you've said and respond as I go.
> In this first set, I do not have a decimal point anywhere.
OK, fine. But then you talked about flipping them around to come after the decimal point. When you do that you have only those strings that only have a finite number of 1s in them.
> As far as representing it as a string, I may still start
> from the right and work towards the left.
Yes you can, but that's not what people do when talking about Cantor and diagonalisation, so it's now completely unclear what you're talking about.
However, you start with finite strings of 0s and 1s, basically the non-negative whole numbers, represented as binary strings. Note that these are all finite, and the non-zero parts are still finite, even if you prepend an infinite number of 0s.
> Stating the above for the decimal case, let n=1 be the
> place right after the decimal, n=2 to the right of it, and
> so on.
See, now you're talking about stuff after the decimal point. I'll continue ...
> Now for place n=1, the both zero and one are covered
> (first two cases below).
But for diagonalisation that's irrelevant. We only ask what is the first digit of the first number.
> For n=2 place, again both zero and one are covered for
> all possible combinations above for n=1 place
Again, irrelevant. We only ask what is the 2nd digit of the 2nd number.
So here if we construct the diagonal of this sequence as you've listed it we have 0.00000... Let me highlight the diagonal for you from this quoted section:
Edit: This comment should be read after my comment below this. It shows up first on HN.
If infinity was in the original set, what would diagonalisation produce? [Genuinely asking, I am unclear on this.] I am flipping all the bits along a diagonal and they are all zeros before flipping.
If 0.99999... = 1, then using my argument of flipping the bits around the decimal, wouldn't infinity be in the set?
What does this mean? Your complete imprecision is making it impossible to answer the questions, despite wanting to help, because they don't make sense.
What set? Define it clearly. Don't talk about infinite strings of zeros followed by stuff, because in the context of decimal or binary expansions that doesn't make sense. Strings have a start, then they go on one place at a time.,
> I am flipping all the bits along a diagonal and they
> are all zeros before flipping.
If they are all zero before flipping then 0.11111... isn't there. You've stated that the n^th number has 0 in the n^th place. That means 0.11111... is not the n^th number for any n.
If 0.99999... = 1, then using my argument of flipping the bits around the decimal, wouldn't infinity be in the set?
>> If they are all zero before flipping then 0.11111... isn't there.
This helps. Since the first set has infinitely many zeros on the left, flipping around the decimal means there would have to be infinitely many zeros somewhere on the right. 0.1111.... however has infinitely many ones before these supposed infinitely many zeroes, which cannot be for the same reason that a finite string with one cannot be after infinitely many zeroes at the right of a decimal.
This means that the first set does not have 111111...
So if I keep incrementing binary numbers, I'll never reach 11111... within the limits of enumerability.
I need to think and read more. The above seems to imply that the simple infinity is not in the enumerable set. But I may be confused again.
>> You've stated that the n^th number has 0 in the n^th place. That means 0.11111... is not the n^th number for any n.
I have been confused about this. Somehow 0.11111... is not in the set, in spite of the mathematical induction proof I supply. I need to think more. The proof must be incomplete (or imprecise as you say).
> This set now includes all possible bit strings of infinite length since the way these are iteratively generated includes all possibilities.
That's not correct -- in fact, it contains no infinite bit strings at all (to prove this to yourself, ask at what position the first infinite string appears).
Start with binary non-negative integers: 000 001 010 011 100 101 ... (goes to infinity)
This set now includes all possible bit strings of infinite length since the way these are iteratively generated includes all possibilities.
This is also an enumerable set by definition.
Let's now reverse the bits and put them after a decimal. These are just real numbers now going from zero to one. (This step is actually unnecessary I think.) .000 .100 .010 .110 .001 .101 .011 ...
This must be enumerable set too.
Using diagonalisation argument, .111111 is never to be found in this set. This is exactly where I am stuck. This number comes into the set from flipping of infinity in the original set, which includes all possible stings of infinite length.
I immediately read into your message on treating these as bit strings instead of real numbers. I still am stuck though. (Do you also see a connection to 0.99999... by the way?)