[sharpener]

The mileage of others may vary, but it has been my experience that there is no cogent solid proof of uncountability that can withstand concerted critique.[0]

Being charitable one might argue that the meanings of terminology had been lost in translation over time and that perhaps Cantor was trying to create non-standard analysis, but then the diagonal argument seems to represent nothing more than the truism that finite numbers are smaller than transfinite ones.

Hence I worry about people who are still worrying about this issue, and I worry for the future of science and AI in particular if folks can't get clear of it.

[0] https://www.researchgate.net/publication/328568169_The_Case_...

Yes, I'm that guy who wrote that.

[myWindoonn]

Hi, Lawvere pummelled your position into the ground a while ago: http://tac.mta.ca/tac/reprints/articles/15/tr15.pdf Your critique involves repeatedly crossing the boundary between the inside and outside of the system in question; Lawvere works entirely inside the system, and shows that the paradoxes of self-reference arise from our interpretations. https://arxiv.org/abs/math/0305282v1 explains with many examples.

Hi downvoters: Use your words when somebody is wrong. Your downvotes aren't helpful here for finding the truth.

[ProfHewitt]

Lawvere's work is elegant! However, Lawvere missed the

crucial importance of Russell's orders on propositions in

blocking the construction of monster propositions using

recursive definitions. Orders on propositions block

construction of I'mFalse, I'mNotSelfapplicable,

I'mUnprovable, and MyTheoremsAreEnumerable.

See the following video for more information:

https://www.youtube.com/watch?v=AJP1VL7shiI

for the following article:

https://papers.ssrn.com/abstract=3603021

[sharpener]

Lawvere's paper appears to suggest that if I refute one diagonal argument then I refute them all. Would you consider that to be an accurate description?

[sharpener]

I'm not seeing this yet. Perhaps you could explain it to me in plain terms.

[myWindoonn]

Pick any Cartesian closed category. Says Lawvere:

If there exists t : Y -> Y such that t;y != y for all y : 1 -> Y then for no A does there exist a surjection A -> (A -> Y).

(He actually says something much stronger.) Note that the first half of this is saying "if there exists t such that t has no fixed points..."

Let our category be Set, the category of sets and functions; it is well-known to be Cartesian closed. Let A be the set of natural numbers and let Y be the Booleans. Then Lawvere is saying that there is no surjection N -> (N -> 2), and thus definitely no bijection, because there is a function 2 -> 2 with no fixed points: the negation function which swaps true and false has no fixed point.

It does not get much plainer without actually reading Lawvere and/or Yanofsky directly, sorry. I hope that this helps explain how inescapable this sort of theorem is.

[candybar]

> Stage 4 of the CDA outline can be critiqued on several grounds. The first is that if we have all the numbers in [0,1] in our table a priori, then using the diagonal process to create a number that is not in the original set does precisely that: It creates a number that is not in [0,1]. So why does the constructed anti-diagonal number seem to have a form that puts it within [0,1]? Could it be that ignoring the zero ahead of the decimal point is a bit sneaky?

You wrote all this and you don't seem to understand how proof by contradiction works?

> If, instead, we construct the anti-diagonal number by counting down the table by positions before each digit selection we find that any anti-diagonal number constructed (from the rectangle) is now within the set we have counted through, and therefore not outside the counted set. This Stretched Diagonal counterargument remains true as d→ ∞, irrespective of any ordering of number representations in the table.

This is not how anything works. You can't take a proof where they create an example that leads to contradictions and say, well, if you choose a different example, it doesn't lead to contradictions, so the proof doesn't work.

Your "proof" in Appendix B is also just gibberish from a mathematical perspective. The infinity and cardinalities aren't numbers - this isn't a mathematically rigorous statement: lim(n -> inf) log(n) = inf = aleph_0 - it's nonsense. What you're saying here is that as n increases without bound, 2^n also increases without bound. That doesn't prove anything about the cardinality of infinite sets.

Also, since you seem to accept that |R| is equivalent 2^|N|, it's also not hard to prove that 2^|S| > |S| for any S. 2^|S| < |S| is trivially untrue and if |S| = 2^|S], there must be at least one bijection F such that F: S => P(S) and inverse F^-1: P(S) => S

Now define S' to be a subset of S such that s is in S if & only if it's in S, but not in F(s). Now, consider F^-1(S') - it must be in S, due to how it's defined. Let's consider whether it's also in S':

1. If F^-1(S') is not in S' (= F(F^-1(S')), by definition, it must be in S'

2. If F^-1(S') is in S', by definition it must not be in S'

Since both these lead to contradictions, the assumption that there must be a bijection between P(S) and S mut be false.

On the whole, you seem to be generally confused - R is not a real thing - it's a mathematical abstraction.

[curtisf]

This presents a confused understanding of Cantor's diagonalization argument.

You are shrouding in complexity something that is straightforward. The complete proof of distinct infinite cardinalities can be stated succinctly and clearly in only a few lines, without referencing the reals at all. You don't need to vaguely refer to "four steps", you should precisely elaborate the steps of the proof you view as problematic.

First, forget the reals. Let's establish that there are sets that are infinite yet uncountable.

----

"Uncountable" means that there is no bijection with (a subset of) the natural numbers.

An "infinite sequence of A's" means a function ℕ → A. For convenience, I'll denote the set of infinite sequences of A's with `A**` -- this is not standard notation.

Theorem: There is no bijection between ℕ and {0, 1}**.

Proof: Suppose for contradiction that there is a bijection f: ℕ → {0,1}**.

Define a function z(n) = 1 - f(n)(n).

z is clearly well defined and is clearly a member of {0,1}**.

Since f is a bijection and z is in the codomain of f, there is an element k of ℕ such that f(k) = z.

However, z(k) = 1 - f(k)(k). Yet f(k) = z, so z(k) = 1 - z(k).

This is a contradiction. So, the assumption (that there exists a bijection f: ℕ ↔ {0,1}**) must be false.

Q.E.D.: There does not exist a bijection between ℕ and {0, 1}**.

----

The linked paper claims that the above proof would work on a bijection of the form ℕ ↔ [ℕ] or ℕ ↔ [ℚ] (where the [] indicate some suitable representation of the set as sequences of bits; again, not standard notation), but that is mistaken: crucially, the constructed function `z` must be a member of the codomain of `f`. The construction 1 - f(n)(n) does not necessarily lie in that set when the set only permits _certain_ bit-sequences!

For example, consider an encoding [ℕ] which is "one-hot"; the natural n is encoded as a function y(n) = 1 and otherwise y(k) = 0. Then there is an obvious bijection `f`: f(a, b) = 1 when a=b and otherwise 0. What is `z` for such an `f`? z(k) = 1 - f(k, k) = 1. So, `z` is not a member of [ℕ].

For a more involved example, consider an encoding of [ℕℕ] that is a unary-encoding of the first natural, followed by a single zero, followed by a unary encoding of the second natural, and followed by only 0s. (The rationals correspond to a subset of these). A standard bijection has the pairs appear in the order of their sum: (0, 0), (0, 1), (1, 0), (2, 0), (1, 1), (0, 2), ... It's an exercise left for the reader that z constructed on this set does not encode to a unary number, followed by a single zero, followed by a unary number, followed by only zeros.

----

If you have an issue with cardinalities, I expect it can be found in the above proof and does not actually lie with the reals. But, for completion, to tie in the real numbers, it's necessary to show that {0,1}** is bijective with ℝ, or with (0, 1). This falls out from the Cauchy-sequence definition of ℝ. For a sequence y : {0,1}** the sequence z(k) = y(0) + 1/2·y(1) + 1/4·y(2) + 1/8·y(3) + ... + 1/2^k·y(k) is clearly a Cauchy sequence with a limit in the interval [0, 1]. It's also straightforward to check that every real number in the interval [0, 1] is the limit of one such Cauchy sequence.

[sharpener]

> Define a function z(n) = 1 - f(n)(n).

I don't understand the notation f(n)(n). Is it related to f_{nn} in LaTeX notation? Your later text suggests maybe it was aiming at f(n,n) so I will assume that.

I recognise a form of this argument and I might have tackled it in the supplementary materials I created that are referenced in the article. Let me know.

> However, z(k) = 1 - f(k)(k). Yet f(k) = z, so z(k) = 1 - z(k).

I'm assuming this was intended to be: z(k) = 1 - f(k). Yet f(k) = z, so z(k) = 1 - z(k).

For some k, z(k) = 0.5. f(k) = 0.5. Seems Ok.

[myWindoonn]

For future readers: z cannot return 0.5. z can only return 0 or 1. This is because z is closed over a function which returns 0 or 1, and inverts it to return 1 or 0.

This should remind folks of both Turing's Halting problem and Russell's paradox. z takes some f which claims to be a bijection (claims to Halt, claims to be a set of all sets) and finds a way to call f against a witness constructed from f.

[drdeca]

For each natural number k, f(k) is itself a function, and f(k)(k) means the value of that function at k.

Yes, you could basically think of it as f_{k,k} if you wanted to.

No, this is __not__ meant to be 1 - f(k) . f(k) is a function (or a sequence, if you prefer), not a particular value in {0,1}, f(k)(k) is a particular value in {0,1}.

0.5 is not in the set {0,1}, and therefore if z(k)=0.5 then z is not in {0,1}* .

[sharpener]

> Theorem: There is no bijection between ℕ and {0, 1}*.

So no bijection between \bb{N} in an unspecified number base and some binary strings that could represent integers? That's a nonstarter for me.

Please read my article. Thanks.

[myWindoonn]

You misread their type. There is no bijection N -> (N -> 2); {0,1}* = 2* = N -> 2.

Note that the given proof is a version of Lawvere's fixed-point theorem. The trick is noticing that for some x : N, f : N -> (N -> 2) can be applied onto it twice, giving f(x) : N -> 2 and f(x)(x) : 2.

Note further that infinite binary strings don't just represent natural numbers. Indeed, every natural number has a finite binary string, and that is the bijection that you're imagining. The question is, which natural number is represented by 111...? This leads to the difference between the natural numbers, their one-point compactification, and Cantor space in terms of searchability. Escardó has an article on this: http://math.andrej.com/2007/09/28/seemingly-impossible-funct...

Please read Lawvere's article. Thanks.

[sharpener]

For the sake of HN archival history...

The executive summary of my paper is that provably there are fatal inconsistencies in Cantor's Diagonal Argument (CDA).

They take a few forms:

(1) Application of basic classical analysis tools reveals that the contradiction sought by CDA does not hold if those tools are used.

E.g. Assume we have the table of all unique infinite length binary strings {0,1}* (where * represents the supremum of the natural numbers, e.g. the first ordinal infinity in set theoretic language).

Assume that those strings represent the fractional part of binary represetations of real numbers in the continuum interval [0,1].

Assume they start big endian, so for some string s, the value v(k) of some bit at the k-th position of s is v(k) = s(k)/2^k, for k = 1,2,3....

Let f: \N x \N -> {0,1}, be a function that accesses bits in the binary strings viewed as a matrix M(i,j).

Create the binary number z as z(k) = 1 - f(k,k).

Now deploy basic analysis.

Note that k -> \infty implies v(k) -> 0.

So no matter what the value of z(k) is, k -> \infty implies |z - f(k)| -> 0, for some suitable k.

Let f be the limit of f(k) as k -> \infty.

Then in the limit k -> \infty the number z = f, and (for all practical purposes) the diagonal z coincides with a binary number in the table f within a countable limit.

This is independent of any ordering of the table rows of M(i,j).

So the contradiction of CDA does not hold convincingly when these basic tools of analysis are used.

(2) Corollary: Platonists would need to prove that infinite digit existence somehow invalidates basic analysis in order to cling to CDA. Moreover, they would have to prove that "higher" infinite digit existence does not invalidate useful concepts of numbers and limits at all.

As far as I know, no one has done that yet.

(3) Using the same basic tools of analysis, key arguments about powersets having cardinalities that are "higher" infinities do not go through, and moreover aspects of "higher" cardinal arithmetic, as presently defined, can be shown to be self-inconsistent.

Therefore: A) When the tools of basic classical analysis are so useful, why would any pragmatic user of mathematics throw them out at some key point within CDA (and CDA only) to endorse a notion of "uncountability" that creates manifold inconsistencies further on?

B) Why should any pragmatic mathematician allow the extra unconvincing machinery of higher infinities into maths?

In the absence of decent answers to those questions I am compelled towards the recommendation is that mathematicians should throw CDA out.

Edit: formatting.

[myWindoonn]

You're presupposing the topology of the Cantor space; how do you know that Cantor space {0,1}* corresponds to real numbers? You're also supposing that an infinite matrix is actually some sort of infinite-plus-one matrix in a handwaved fashion. Limits don't work in the discrete setting; you must invent and justify them.

Pick a k. Note that z(k) is not in rows 0 through k of M, by finite diagonalization. Now, suppose that you try taking k to "infinity" again. z(k) keeps up at every step, by primitive recursion, and M is always missing at least one entry. By what justification do you suppose that M somehow outruns v at "infinity"?

I need you to remember how to be a human for just a moment. Reread your words, "the recommendation is that mathematicians should ..." and consider the precise moral justification by which you make this recommendation. Note that your attempt at the passive voice failed to shift the moral burden, because the given proof is unconvincing (and quite unrigorous). Please consider a dram of humility and give Yanofsky's paper a serious read. It's good.

Also, if you want a better idea of such an infinite Boolean matrix, consider reading about Chu spaces: http://chu.stanford.edu/

[civilized]

Your argument has some gaps. Here are the two basic problems:

1. f(k) is not defined in your notation, only f(k,k) is. My guess is that f(k) is supposed to represent the real number defined by the k^th row of the table.

2. Whatever f(k) is supposed to be in your notation, you have not shown that it has a limit as k approaches infinity, let alone that z = f.

In fact, f(k) cannot possibly have a limit f. If it did, then by the definition of limit, all but finitely many numbers in [0,1] would have to be within epsilon of f, for any epsilon > 0. We could then show that all but finitely many numbers in [0,1] have the exact same first trillion digits of their decimal expansion. Obviously this is absurd.

This is what always happens with Cantor diagonal argument critiques. The critique invariably ignores the logically rigorous argument of the CDA itself, sets up its own new version or extension of the diagonalization construction, and then makes whatever false assumptions are needed for the new construction reach a conclusion contrary to the CDA.

It's like walking into a sturdy bridge with a few pebbles in your pocket, arranging the pebbles into a flimsy tower, knocking the tower over and declaring that you've destroyed the bridge.