Demonstrating the Naturals are not Countable

It's all in how you present the solution. The listing of naturals isn't limited to any particular format. It turns out that if the naturals are listed so that one digit of each number lies on the diagonal then Cantor's diagonal method works just fine. There's no need to reformat the numbers themselves.

Consider the following two demonstrations:

Pattern 1 – Highest digit of each natural number on the diagonal (absolute). The number Y differs from every number in the list by at least one digit, just as in Cantor's diagonal method on the (0, 1) real number interval.

1   7   3                                                                   
    2   1   1   1   1   1   1                                               
        3   2                                                               
            4   6   5                                                       
                5   0                                                       
                    6   7   3   2                                           
                        7   8   8   8                                       
                            3   1   4   8   7   1   5                       
…

Y =
3     1       4      8     7      1     5       6 …

Pattern 2 – Any digit of the natural number on the diagonal (clustering). In this case, 1, 2, 3, 4, 5, 6, 7 and 3 all lie along the diagonal. Again, Y differs from every number in the list by at least one digit, just as in Cantor's diagonal method on the (0, 1) real number interval.

1   7   3                                                                   
    2   1   1   1   1   1   1                                               
    2   3                                                                   
    5   6   4   1   3   7                                                   
                5                                                           
            1   7   6   7   3   2                                           
                3   2   7   8   8   8                                       
                            3   1   4   8   7   1   5                       
…

Y =
3     1       4      8     7      1     5       6 …

As with Cantor’s treatment of the reals on (0, 1), Y differs from every entry in the list by at least one digit. Both patterns result in a natural number that will never appear in a list of natural numbers no matter how long the list grows.

I have purposely chosen to present the list of naturals in random order, but the method works if the list is presented well ordered as well.

The above demonstration has some interesting implications regarding the Continuum Hypothesis. I have demonstrated the Natural Numbers are not countable and the fact that the Real Numbers on the (0, 1) interval are equally not countable means that both sets possess the same cardinal number. As a consequence of this fact that there can be no infinite set with a cardinal number between them. The Continuum Hypothesis is true because the naturals and reals have the same cardinal number.

A Different Approach

I am going to approach this from a non-numeric perspective. In 1969 G. Spencer Brown authored a book titled Laws of Form. In the book Spencer Brown lays out ideas behind the calculus of indications, a primary non-numerical arithmetic and algebra. I’m not going to go into a detailed explanation of the calculus he discovered (invented?). You may already be aware of his work but in the event you’re not, his book is still in publication and there’s lots of commentary available on the internet.

I have noted with footnotes where I am quoting LOF verbatim. Unquoted definitions, theorems, instructions etc. are my own extensions to the calculus, introduced in order to facilitate the discussion.

“Definition

Distinction is the perfect continence.

That is to say, a distinction is drawn by arranging a boundary with separate sides so that a point on one side cannot reach the other side without crossing the boundary.”[1]

“Construction

Draw a distinction.”[2]

“Knowledge

Let a state distinguished by the distinction be marked with a mark

┐

of distinction.”[3]

Assignment

Call the mark a cross.

“Arrangement

Call the form of a number of crosses [tokens] considered with regard to one another (that is to say, considered in the same form) an arrangement.”[4]

“Expression

Call any arrangement intended as an indicator an expression.”[5]

“Axiom 1: The Law of Calling

The value of a call made again is the value of the call.”[6]

Length

Length is a state of an expression and is given by the number of crosses that comprise the expression, denoted by L(e).

“Value

Call a state indicated by an expression the value of the expression.”[7]

Expressions of unequal lengths are unequal in value. That is to say,

If L(e_i) ≠ L(e_j) then e_i ≠ e_j

 “Equivalence

Call expressions of the same value equivalent.
Let a sign

=

of equivalence be written between equivalent expressions.”[8]

Initial 1: Number

┐= ┐┐(expansion)

and

┐┐= ┐(contraction)

Repeated applications of Initial 1 (expansion) will create forms of increasing length indefinitely.

┐	=	┐┐
┐┐	=	┐┐┐
┐┐┐	=	┐┐┐┐
	…

                         I1

                         I1

                         I1

Call the set  created by indefinitely invoking Initial 1 on each form in the list the set of Natural Expressions [N_e].

Question: Is it possible to list the elements of [N_e] such that no element will be missing from the list?

Given: The first distinction           ┐

“Theorem 1: Form

The form of any finite cardinal number of crosses can be taken as the form of an expression.

That is to say, any conceivable arrangement of any integral number of crosses can be constructed from a simple expression by the initial steps of the calculus.”[9]

The proof of Theorem 1 is given in the text of LOF so I won’t repeat it here. What’s important to note is that using Initial 1 in conjunction with Theorem 1 it is possible to construct an expression the form of which is a member of [N_e] but will never appear in the listing of [N_e].

Theorem 2: Incompleteness

An attempt to list the elements of [N_e] must be incomplete.

That is to say, it is possible to construct an element ω of [N_e] such that ω will never appear in the list of [N_e] no matter how long the list grows.

Proof: The element ω of [N_e] is constructed as follows:

List the elements of [N_e] one above the other. After each element is listed apply Initial 1 to it to expand its length and append it to ω. Since ω is a single expression the length of which grows over time as the listing of [N_e] proceeds, the length of ω will grow at a rate such that it will always exceed the length of any expression in the listing of [N_e].

e	ω
┐	┐┐
┐┐	┐┐┐┐┐
┐┐┐	┐┐┐┐┐┐┐┐┐
┐┐┐┐	┐┐┐┐┐┐┐┐┐┐┐┐┐┐
…	…

ω = ┐┐┐┐┐┐┐┐┐┐┐┐┐┐after 4 elements of [N_e] have been listed.

It’s clear that no matter how long the listing process goes on that ω, an element of [N_e] will never be an expression that appears in the listing of the elements of [N_e]. Since ω will never appear in the list, the list will always be incomplete which proves Theorem 2.

“Third canon. Convention of substitution

In any expression, let any arrangement be changed for an equivalent arrangement.

Step

Call any such change a step.

Let a sign

   

Stand for the words

is changed to.”[10]

Using the convention of substitution we can now substitute the arrangement of symbols representing the natural numbers for crosses in expressions of the form according the following rule.

Rule of substitution

Let an expression of the form be substituted by a natural number such that the value of the natural number is equal to the length of the expression, so that:

┐		1
┐┐		2
┐┐┐		3
	…

We can now expand the substitution of number for expression to include ω

e	ω
┐	┐┐
┐┐	┐┐┐┐┐
┐┐┐	┐┐┐┐┐┐┐┐┐
┐┐┐┐	┐┐┐┐┐┐┐┐┐┐┐┐┐┐
…	…

n	ω
1	2
2	23
3	234
4	2345
…	…

ω = ┐┐┐┐┐┐┐┐┐┐┐┐┐┐

                                                     

ω = 2345

In both cases as the listing of each set continues ω will never appear in the list. Consequently both the non-numeric and numeric lists will always be incomplete.

---

[1] Laws of Form, G. Spencer Brown page 1

[2] Laws of Form, G. Spencer Brown page 3

[3] Laws of Form, G. Spencer Brown page 4

[4] Laws of Form, G. Spencer Brown page 4

[5] Laws of Form, G. Spencer Brown page 4

[6] Laws of Form, G. Spencer Brown page 1

[7] Laws of Form, G. Spencer Brown page 5

[8] Laws of Form, G. Spencer Brown page 5

[9] Laws of Form, G. Spencer Brown page 12

[10] Laws of Form, G. Spencer Brown page 8