[lisper]

> Sorry if I wasn't making myself clear

You still aren't.

> diagonalization is not self-contained/provided-up-front/fully-written-down or any of the other phrases I've tried to use to get my point across

But it is. The fact that one of its inputs happens to be a function doesn't make it any less self-contined.

> The point is that Cantor's proof isn't actually about the real numbers!

It isn't just about the reals, but it is definitely about the reals. The claim is: there exist well-defined mathematical structures that cannot be put into a one-to-one correspondence with the naturals. The proof is constructive, with the reals as the canonical example. Cantor's proof is about the real numbers in the exact same sense that Turing's proof of the non-computability of the halting problem is about Turing machines.

[chriswarbo]

> diagonalization is not self-contained/provided-up-front/fully-written-down or any of the other phrases I've tried to use to get my point across

> But it is.

No it's not. It's a function. That is exactly the opposite of what I mean by "self-contained" (and all of the various rephrasings of how I defined it).

> The fact that one of its inputs happens to be a function doesn't make it any less self-contined.

True, it doesn't become less self-contained, because it's already not self-contained because it has an input. A function whose input is a function is just as self-contained as one whose input is a natural; or whose input is a teapot: they're all, precisely, not "self-contained" as per my definition.

I can't think of any clearer way of stating it. Maybe you're getting derailed by this phrase because you're interpreting it in some way other than the various equivalent, precise definitions I have given over and over?

[lisper]

> it's already not self-contained because it has an input

On this view there is no such thing as a "self-contained function". All functions have inputs.

[chriswarbo]

Exactly. One way to define the same notion of "self-contained" is "not a function" , so it makes perfect sense that there are no self-contained functions.

Free variables are also not allowed, e.g. defining diagonalization in terms of some free variable "x" to stand for our list. That's effectively the same as being a function of "x", so again it doesn't count as self-contained.

Hence, a program for diagnonalization is not self-contained, since it would be a function, e.g.

    function (List<Real> x) { return ... }

Some examples of programs which are self-contained are:

    42

    sqrt(2)

    // Difficult to compute, but still a well-defined number
    if (riemannHypothesis) then 1 else 2

    // Doesn't halt, evaluates to 1.1111111...
    let f = function(n) { return (1 / n) + f(n * 10); }
     in f(1)

If we want to allow classical logic, then hypercomputation can be included too, e.g.

    if (haltingProblem) then 1 else 2

So by "program" or "description" we just mean a finite representation of a (potentially infinite) object, e.g. like the `1.11111...` example, which we could never write down in 'fully expanded' form.

We need this idea of "programs" to give meaning to statements like "we must write down our entire list before Cantor chooses his counter-example", or "if we force Cantor to write down his supposed counter-example before we write down our list".

Since we're talking about infinite objects (real numbers with a never-ending list of digits, or lists of real numbers), we can't write them down in a 'fully expanded' form, since we'll never finish writing, and hence statements about what happens "after" are vacuous (for the same reason that proof assistants don't allow (non-productive) non-termination).

If we write down a program instead, then 'the entire thing' can be written down in finite time, and hence it makes sense to talk about what happens "after".

Consider the case where a real number is written down first and then a list is written down (i.e. the opposite of Cantor's proof):

- The number cannot be written down in 'fully expanded' form, since its digits never end, so we'd never get to write down the list.

- The number can be written down as a self-contained program. For example, `pi`.

- That program cannot be/use diagonalization, since diagonalization is not self-contained. We can't write down the diagonalization program as our number, since diagonalization itself is not a number (it's a function) so that's a type error. We can't apply diagonalization to anything, since we don't have access to any list of numbers (assuming that we don't have a time machine); we could make up a list of numbers to diagonalize, but in that case we might as well skip the diagonalization altogether and just make up our number.

The theorem we can prove about this scenario is that it's always possible for us to write down a list containing that number. This is trivial, since we're writing our list after the number has been written down (as a program), so we can just put that at the head of our list.

This "opposite situation" gives a result which is the "opposite" of that in Cantor's proof (in Cantor's proof the number is never in the list). Hence "the second player always wins", and the reason the second player wins is that they get to look at the first player's choice before making their own.

We could make a winning strategy for rock/paper/scissors in a similar way: no matter how complex the strategy of the first player is (even if it requires solving the Riemann Hypothesis!), we can always beat them because we get to look at their choice.

[lisper]

All of that is a red herring. The basic structure of Cantor's proof applies equally to finite (what you call "self-contained") lists. Consider:

Theorem: there are an infinite number of the integers.

Proof: Assume to the contrary that there are a finite number of integers. Then it is possible to construct a finite list L that contains all of the integers. Find the largest integer in L and add one. The result will be larger (by one) than the largest integer in L, and hence larger than all of the integers in L, and hence not in L, contradicting our assumption that L contains all of the integers. Hence no finite list can contain all of the integers. QED.

You are saying, "But if you give me any integer, I can produce a finite list containing that integer." That's true. But if you don't see at this point why that is irrelevant then you are beyond my ability to help.

[chriswarbo]

> finite (what you call "self-contained") lists.

Wow, I thought it was pretty clear when I said that self-contained == not a function. I don't know how you've interpreted that to mean 'is finite'...

The thing that must be finite isn't our list, it's the representation/program/description of our list. Here's a finite representation/program/description of an infinite list:

    The list beginning with zero, where each successive element is one more than its predecessor

That represents/computes/describes an infinite list (containing all of the naturals in ascending order), but it itself is not infinite (it only contains 92 characters) and is not a list (it is a program/description/whatever).

That has nothing to do with being "self-contained". All I meant by "self-contained" is, as I've said, "not a function".

The program above is not a function; it has no inputs; it has no free variables; etc. hence it is a finite, self-contained program.

The list it describes/computes/represents is also not a function (it's a list); it has no inputs; it has no free variables; etc. hence it is an infinite, self-contained list.

If you like, we could flesh out examples elsewhere on these axes:

- An example of an infinite, self-contained program is: "the list containing the number zero, followed by the number one, followed by ..." and so on ad infinitum. That's self-contained, since it's not a function (it has no inputs), but it's infinite (of course, to represent it in a Hacker News comment I've had to use a finite description at a meta-level (the '...'), but such is the nature of these things!)

- An example of an infinite, not-self-contained program is: "given a number N, return the list containing N, followed by N+1, followed by N+2, followed ...". It's not self-contained because it is a function: it has an input (N). Again, we have to use a meta-level (the '...') to 'represent the infinite representation' ;)

- An example of a finite, not-self-contained program is diagonalization: "given a list L, return the number whose Nth digit is equal to the Nth digit of the Nth element of L, plus one mod 10." That's finite (it's only 117 characters long), and it's not-self-contained since it's a function (it takes the input 'L'). Note that in this case, we're computing a real number rather than a list, but that's irrelevant to the concepts of "self-contained" (i.e. not a function) and the distinction between representations and objects.

Just for fun, here's another not-self-contained program: "Given a binary tree, return its left-most leaf". That's got nothing to do with numbers, lists, diagonalization, etc. but we can immediately see that it's not self-contained, since it's a function.

The program/object distinction is needed because Cantors proof talks about "after" we've given/written-down/etc. an infinite list. We cannot write down such a list in 'unexpanded' form (e.g. [0, 1, 2, 3, ...and so on), since we would keep going forever; and hence any statement about what happens "after" (like Cantor finding a number that's not in our list) is meaningless, since there's no "after".

On the other hand, it's trivial to write down a finite representation/program/description of this list; that's exactly what I've written above as "The list beginning with zero...".

> The basic structure of Cantor's proof applies equally to finite lists... Theorem: there are an infinite number of the integers. Proof: ...

Yes. It also applies to Euclid's proof that there are infinitely many primes ("given a list of primes, I can write down a prime that's not in that list"). We can use it to prove that there's no "best" choice in rock/paper/scissors: given a choice, I can beat it". It's a very useful technique (as is diagonalization).

> All of that is a red herring

From what? Paying the bills? In that sense, all pure maths (including Cantor's proof) is a 'red herring'. I was pointing out (what I find to be) some interesting aspects of Cantor's proof:

- If we do the choices in the opposite order, we get the opposite result.

- If we interleave the choices (e.g. pick one more list element, pick one more digit, pick one more list element, etc.) then it's a "stalemate".

- If we make the choices concurrently, in a perfect information setting (i.e. each "player" knows their own "program" and their competitor's) then it's a win for whoever has more computing power: since they can simulate their opponent and perform the 'extra step' of add-one-mod-10, or append-number-with-diagonalized-prefix (depending on which "player" they are).

Isn't 'noticing and discussing interesting things about an abstract/formal system' basically the process of mathematics? So why is it a "red herring"? What were you hoping to achieve, other than (hopefully) understanding these aspects of the proof that I've tried to point out (which you can then ignore, or take in another direction, or whatever you like)?

> if you don't see at this point why that is irrelevant then you are beyond my ability to help.

Again, irrelevant to what and help with what? I don't plan on taking these observations any further (e.g. writing a paper), since I would imagine they're pretty clear to those with a mathematical mindset. I was pointing them out here because:

- The HN audience seems to like mathematical ideas (for example, this article!)

- The HN audience isn't all highly trained mathematicians, for whom this might be too trivial to discuss

- The HN audience seems to like computational ideas, which these aspects of the proof are related to (although classical mathematics isn't limited to turing computability; hence why I said a "program"/"description" could use hypercomputation, if we like)

[lisper]

> Wow, I thought it was pretty clear when I said that self-contained == not a function. I don't know how you've interpreted that to mean 'is finite'...

Because your definition doesn't make sense. Everything in mathematics is a function. I was trying to do you the courtesy of interpreting what you said in a way that made sense rather than just pointing out that you don't seem to understand what a function is.

> The program above is not a function; it has no inputs; it has no free variables; etc. hence it is a finite, self-contained program.

Now it sounds like what you're trying to get at is the concept of a "constant function" (https://en.wikipedia.org/wiki/Constant_function). Constant functions are functions, and they can have inputs.

So now it seems that you've just spent all this time and effort to point out that diagonalization is not a constant function. That's true, but I don't think it's a particularly interesting observation.