| 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. |
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.