Wikipedia:Reference desk/Archives/Mathematics/2020 December 3

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 3

A contradiction from assuming R is not countable.

Suppose the set of all numbers in R cannot be counted. Consider Cantor's set T of infinite sequences of binary bits. Cantor assumes that T is complete, thus lets presort, without lost of generality, T into mutually exclusive sets T0 and T1. First, initialize T0 with the sequence {0,0,0,...} and T1 with the sequence {1,1,1,...}, and when done the strings of T need to be organized like this (the character x is a placeholder for either 1 or 0):

T0
s1 =	(0,	0,	0,	...)
s2 =	(x,	0,	x,	...)
s3 =	(x,	x,	0,	...)
...
T1
s1 =	(1,	1,	1,	...)
s2 =	(x,	1,	x,	...)
s3 =	(x,	x,	1,	...)
...

Now apply the diagonal procedure to the set T0, it completes its count of T0, without contradiction, because the compliment of the diagonal (0,0,0,...) of T0 is not in T0, it's in T1, but still in T. Likewise, apply the diagonal procedure to the set T1, it completes its count of T1, without contradiction, because the compliment of the diagonal (1,1,1...) of T1 is not in T1, it's in T0, but still in T. T0 and T1 are both countable therefore their union T is countable. The supposition that T is uncountable is false and since there is a bijection between T and R the supposition that R is uncountable is false.

-Modocc (talk) 01:31, 3 December 2020 (UTC)

If I follow your argument, your error is that one particular attempt to show T0 and T1 are uncountable didn't work, and you therefore conclude they're countable. That doesn't follow. And in fact they are uncountable. --Trovatore (talk) 04:06, 3 December 2020 (UTC)

The only common ground then is that the count is infinite. I'll leave at that. Thanks. --Modocc (talk) 05:25, 3 December 2020 (UTC)

I'm sorry, my comment was nonsense, as I realized lying in bed last night, but I really didn't want to get up just for that. The actual problem is that you just haven't said what T0 and T1 are at all. I tried to respond as though they were well-specified things, but they aren't, so saying they're uncountable makes no sense. --Trovatore (talk) 18:18, 3 December 2020 (UTC)

There's also the issue that you assume towards a contradiction that R is uncountable, but then you wish to partition it into two clearly countable sets with no justification for why this is possible. You're assuming that which you wish to show.--2406:E003:E0A:7A01:30D8:6043:EFF5:B08F (talk) 08:44, 3 December 2020 (UTC)

Apart from the beginner's fallacy of assuming that finding an error in a proof of some proposition means that you have proved the falsehood of the proposition, and the fallacy of assuming in the construction that which you seek to prove, which also plagued the Real Number Pyramid scheme and is a hallmark of crankhood, there is also the (in comparison minor, but actually major) issue that whereas each s₀ is a single sequence, the other s_i are each by themselves an infinitude of sequences, so where is the diagonal? Furthermore, sequences of the form (✶, 0, 1, ✶, ✶, ...) belong both to T₀ via its s₂ and to T₁ via its s₃, so this does not even look like a partition of T. There was the person who proved the Moon landings were fake because the Moon looked so white whereas the real Moon is yellow. There was the other person who proved the Earth was flat because otherwise they could not have made all these flat maps in their atlas. These disproofs are at a similarly pitiable level of amateurishness.  --Lambiam 09:22, 3 December 2020 (UTC)

The Real Number Pyramid post was a list in the form of an argument but it was not a proof. Every statement has to be justified for it to be a proof. I do suspect that past rulers had pretty much the same conception of the infinity that they buried themselves in. Here, I stipulated a partition, I did not show any when there are many. I figured that if a segregated S is permitted whilst counting T then a partition of T is too and we could see if the argument still holds, for I maintain the view that a complete count of T has S and if it's shown to be without S the count simply breaks with the assumption of one-one correspondence between infinity and T. To remove the apparent contradiction, simply add S to the count so that it is complete and the simplest way to do that is to partition T. -Modocc (talk) 16:46, 3 December 2020 (UTC)

@Modocc: I have no idea what you mean by T is complete but Cantor certainly does not assume anything like that. By imputing that you make a false assumption in the very first step of your wanna-be reasoning, thus making it all unjustified. --CiaPan (talk) 19:30, 3 December 2020 (UTC)

@Modocc: BTW, you repeated the Cantor's proof: you construct two sets, and you show none of them contains all binary strings. Alas, you claim but you do not prove their union contains all of them. --CiaPan (talk) 23:10, 3 December 2020 (UTC)

• I believe this may be relevant to the current discussion... --Jayron32 19:40, 3 December 2020 (UTC)

• This is actually a Reference Desk, not a place where people present their favourite theories for comment. -- Jack of Oz ^{[pleasantries]} 20:00, 3 December 2020 (UTC)

• The evolution of this discussion is making me feel better and better about my initial contribution. --JBL (talk) 16:31, 5 December 2020 (UTC)

• To the extent that I can make sense of it, the argument goes as follows (with some renaming, using S and T instead of T0 and T1 and counting from 0):

The set R of all infinite bit sequences can (through some ill-specified procedure) be separated into two lists:

S = (s₀, s₁, s₂, ...);

T = (t₀, t₁, t₂, ...).

Because of the construction, the complement of the diagonal of S occurs in R and conversely, so the union of S and T covers R.

The main problems with the argument are:

1. The ill-specified procedure of the construction of S and T.
2. The absence of a cogent and coherent argument why all elements of R occur in the union of S and T.

There is no hope that these defects can be cured, for the simple reason that Cantor's argument also applies to this situation. Because of the obfuscation of a separation into two lists, it needs some simple adjustments. To be precise, we construct an infinite bit sequence u and show it does not occur in S, and also not in T. Each sequence s_i in S can be written as (s_i,0, s_i,1, s_i,2, ...), and likewise for each sequence t_i in T. We denote the operation of flipping a bit by ~: {0, 1} → {0, 1}, where ~0 = 1 and ~1 = 0. Then u is defined by

u_2i+0 = ~s_i,2i+0;

u_2i+1 = ~t_i,2i+1.

Now suppose u occurs in S. So, for some index i, u = s_i. If these sequences are the same, they also agree at position 2i+0. So we have

u_2i+0 = s_i,2i+0.

This contradicts the definition of u, so u does not occur in S. Likewise, assuming u occurs in T, u = t_i for some index i. Then we have

u_2i+1 = t_i,2i+1.

This also contradicts the definition of u, so u does not occur in T either.  --Lambiam 20:44, 5 December 2020 (UTC)