Problems with Cantor's proofs

[A Bogart]

PROBLEM 1:

While examining some old almost-universally-accepted proofs, I noticed they all implicitly used the Principle of Mathematical Induction. However, something in the way this was used didn't sit right with me. Looking at these proofs inspired the following example:

Let f be a function on the positive integers such that f(n) = n {where n is a positive integer, of course}.

Let P be a proposition {dependent on the positive integers} which says:

P(n) is finite

By The Principle Of Mathematical Induction, P(n) is True for all positive integers n, that is

The proposition “P(n) is finite” is True for all {positive integer} n.

Let n = ꝏ. Then we have

“P(ꝏ) is finite” must be true.

But f(n) is f(ꝏ) is ꝏ. So P(ꝏ) should be infinite.

Can anyone explain what is wrong with this example? (I believe I know an answer, but I cannot reconcile my answer with the logic which was used in the old proofs which I was examining). Maybe someone else has a more satisfactory answer.

Full disclosure: If the answer to this problem is what I believe it to be, those old proofs all have one and the same logical error. It is my hope that if I am wrong, someone will respond with a clear explanation which will show me the error in my own logic. If I am right, hopefully readers will open their minds to rethinking their acceptance of these old proofs. What is correct is important, because some of the most highly lauded accomplishments of mathematicians such as Voltera, Baire, Riemann, Lebesgue, Russell, and Goedel rely in part on these old proofs or on the logic method used in them.

=================

PROBLEM 2:

Consider the list on the Real positive interval [0,1) defined as (d₁ | d_i1= 0 to d₁ = 9), (d₁d₂ | (d_i2= 1 to d₂ = 9)(d₁ = 0 to d₁ = 9)), (d₁d₂d₃ | (d₃= 1 to d₃ = 9)(d₂= 0 to d₂ = 9)(d₁ = 0 to d₁ = 9)), … (d₁d₂...d_n | (d_n= 1 to d_n = 9)(d_n-1= 0 to d_n-1 = 9)...(d₂= 0 to d₂ = 9)(d₁ = 0 to d₁ = 9)), …

The first few terms of the list are as follows. Note that lined-out numbers (duplicate representations) are not included in the count (list); they are presented to remind us that duplicate representations are possible if one does not take care.:

0.0 0.00 0.01 … 0.09 0.000 0.001 … 0.009 … 0.090 0.091 … 0.099 ...

0.1 0.10 0.11 … 0.19 0.110 0.111 … 0.119 … 0.190 0.191 … 0.199 ...

0.2 . . . . . .

. . . . . .

. . . . . .

0.7 . . . . . .

0.8 0.80 0.81 … 0.89 0.810 0.811 … 0.819 … 0.890 0.891 … 0.899 ...

0.9 0.90 0.91 … 0.99 0.910 0.911 … 0.919 … 0.990 0.991 … 0.999 ...

If one were to describe the list as a sequence of {a_k, k = 1 to …}, a₁ = 0.0, a₂ = 0.1, …, a₁₀ = 0.0, a₁₁ = 0.01, a₁₂ = 0.02, …

If you like to work with closed intervals, simply append “1” to the end of the list to get the closed interval [0,1].

2.A Can you identify a Real number in the interval [0,1) which is not represented in the list?

2.B Can you apply Cantor's nested interval proof that the Reals are uncountable to this list?

2.B.i The original form of Cantor's proof used the indexes k of the list to arrive at the conclusion that there must be a number N such that a_N would be the only list element remaining after applying his nested intervals sufficiently many times, and that N >= 2N + 1, therefore he had arrived at a number which must be in the list if the list is complete, but arithmetically could not be in the list. Apply his method to the sample list above. What number N do you arrive at, and does that number cause you to rethink Cantor's conclusion using N >= 2N + 1?

2.B.ii A later version (supplied by someone after Cantor?) uses limits at a_N. Using that method, what limit(s) do you arrive at using this example list? Are these limit(s) inside the nested intervals?

2.C Apply Cantor's Diagonalization method to the example list. Describe what you see happening.

In particular, at each step N of the construction, focus on the possible choices of the next Diagonal digit. I.e., in the decimal base, for example, the next possible digit to choose must be one of the set [0,...,9], but all 10 possible partially constructed Diagonal numbers are already present in the list (just haven't all been examined by the construction process as yet).

==========

PROBLEM 3

Consider any "countably" infinite list, such as the Natural numbers. Represent it by {a_i}: a₁ a₂ a₃ …

The powerset of that list is defined as the set of all possible sets which contain 0 elements through all of the elements a_i.

Consider the list {} {a₁ a₂ a₃ …} {a₁} {a₂} {a₁ a₂} {a₃} {a₁ a₃} {a₂ a₃} {a₁ a₂ a₃} {a₄} {a₁ a₄}

{a₂ a₄} {a₃ a₄} {a₁ a₂ a₄} {a₁ a₃ a₄} {a₂ a₃ a₄} {a₁ a₂ a₃ a₄} …

I.e., after the empty set and the entire set, start with the first element and create all possible permutations of that element (exactly one, at the start). Then add the next element, and create all possible new subsets of the first two elements. Continue adding one element at a time, creating all possible new subsets of the current list of elements being processed. Continue infinitely.

Does this list exhaust the powerset of {a_i}? If not, what subset of the powerset is missing?

[A Bogart]

Correct a typo in the second sentence in problem 1:

Change "Let P be a proposition {dependent on the positive integers} which says:

P(n) is finite"

to "Let P be a proposition {dependent on the positive integers} which says:

f(n) is finite"

[A Bogart]

Add subproblem 2D:

      For some finite sets, Cantor's diagonalization method fails:

xx xy yx yy The list contains all possible 2-symbol permutations of the symbols x y; Diagonalization can only construct an element already in the list.

This is true for any finite list in which each element of the list has the same number of digits (n) and the list contains all possible n-digit permutations of the base used to describe each element (binary, octal, decimal, etc.).

    For some infinite sets, Cantor's diagonalization method fails:

x y xx xy yx yy xxx xxy xyx xyy yxx yxy yyx yyy … The list contains all possible 1 to … permutations of the symbols x, y; Diagonalization can only construct an element already in the list.

So if the proposed infinite list of all possible symbols (numbers, if you prefer) contains all possible permutations of those symbols (numbers), than the diagonalization process cannot construct an object which is not already in the list. 

[A Bogart]

Ok, the typo in problem 1 carried through in several sentences.  Here's a complete correction:

Let f be a function on the positive integers such that f(n) = n {where n is a positive integer, of course}.

Let P be a proposition {dependent on the positive integers} which says:

f(n) is finite

By The Principle Of Mathematical Induction, P(n) is True for all positive integers n, that is

The proposition “f(n) is finite” is True for all {positive integer} n.

Let n = ꝏ. Then we have

“f(ꝏ) is finite” must be true.

But f(n) is f(ꝏ) is ꝏ. So P(ꝏ) should be false.

[Hippasos Metapont]

abgr...@gmail.com schrieb am Freitag, 10. November 2023 um 22:10:16 UTC+1:

PROBLEM 1:

While examining some old almost-universally-accepted proofs, I noticed they all implicitly used the Principle of Mathematical Induction. However, something in the way this was used didn't sit right with me. Looking at these proofs inspired the following example:

Let f be a function on the positive integers such that f(n) = n {where n is a positive integer, of course}.

Let P be a proposition {dependent on the positive integers} which says:

P(n) is finite

By The Principle Of Mathematical Induction, P(n) is True for all positive integers n, that is

The proposition “P(n) is finite” is True for all {positive integer} n.

Let n = ꝏ. Then we have

“P(ꝏ) is finite” must be true.

But f(n) is f(ꝏ) is ꝏ. So P(ꝏ) should be infinite.

Induction holds only for finite numbers n.

Regards, WM 

[Hippasos Metapont]

Test

[Heinrich]

Test3

[A Bogart]

Got all test messges, but the link to this group which was sent in the messages went to someplace which McAfee labelled as suspicious.   Note that going directly to the group via GoogleGroups was NOT labelled suspicious.  Here is the GOOD link:

https://groups.google.com/g/scivszfc/c/4EnVszlvkQA

Here's the BAD link:

https://groups.google.com/d/msgid/scivszfc/edf65049-4538-4c85-9c47-3df784c87784n%40googlegroups.com