9 ms·

Here's a nice video that digs into the general structure of diagonalization arguments: https://www.youtube.com/watch?v=dwNxVpbEVcc https://www.youtube.com/watch

Here's a nice video that digs into the general structure of diagonalization arguments: https://www.youtube.com/watch?v=dwNxVpbEVcc https://www.youtube.com/watch?v=dwNxVpbEVcc It's a really neat way to see a shared core between seemingly-separate topics: - Gödel's Incompleteness Theorems, - Cantor's Theorem, - Russell's Paradox, - The Halting Problem, - The Y Combinator!, - etc.

3abiton 3y ago
Great video, thanks for sharing
ballenf 3y ago
I have a problem with the diagonalization, but I'm more of a math fan so please forgive my ignorance. The proof of uncountability of real numbers starts with a process of enumerating this infinite list of infinitely long binary numbers. Then says that we construct a number that can't be on them by flipping bits the down the diagonal. But hasn't this concept already kind of mixed domains? The enumeration was describing a process, but the diagonal flipping move seems to assume or require that the enumeration is complete or at least paused. How could the diagonal construction ever finish to allow a "check" of whether the result of that process is actually on the list. Obviously at any point in time it won't be, but aren't we just kind of proving that we can construct a number that isn't on the list yet? And the first process would certainly eventually get to our constructed number? The diagonal just seems like a shortcut to a number that we know the first process hasn't gotten to yet? I just don't get how we conclude that Integers are countable and Reals are Uncountable from this proof, even though its obvious in an intuitive sense that Reals have to be much "larger".
- vgatherps 3y ago
  > The proof of uncountability of real numbers starts with a process of enumerating this infinite list of infinitely long binary numbers. > How could the diagonal construction ever finish to allow a "check" of whether the result of that process is actually on the list. > The diagonal just seems like a shortcut to a number that we know the first process hasn't gotten to yet? I think you are mixing up the enumeration of the (hypothetically countable) reals with the existance of said set of reals, and viewing the construction of the counterexample as an actual process that involves programmatically iterating over the list instead of a description of how the digits of said new real number is created. There is no pause or setp-by-step of this iteration that's required, since it's only telling you that the i'th digit of the counterexample will be distinct from the i'th digit of the i'th number (thereby creating a real not in your countable set, since you have created a number outside of your 1-1 mapping onto the natural numbers).
- kccqzy 3y ago
  You are confused about the concept of countability and finiteness. The enumeration that you mention requires that a set be countable, not that it is finite. So it's wrong to somehow require the enumeration to finish. Countable sets can be finite or infinite. Most interesting countable sets are infinite. The enumeration then means a bijection with the natural numbers. Your definition of enumeration seems to require it to "complete" which is incorrect. (I put "complete" in quotes because that's the word you used, but I don't want you to further confuse that with the completeness of real numbers which is a whole another thing.)
  - k__ 3y ago
    It's a bit like saying 0,1... isn't a real number because you couldn't type all the 1s.
- owalt 3y ago
  I don't quite understand your main concern, but it seems others did and have answered. To elaborate on why Cantor's argument doesn't go through for the integers: Assume you had a list of every integer. To begin with, you couldn't start flipping bits from the left since integers don't start from the left. You could however imagine them having a sequence of 0s extending infinitely to the left, e.g. 101 = ...00000101. If you did that, the diagonal argument is possible to perform only starting from the rightmost digit, and you do end up with some string of numbers. The problem is this: If you do walk right-to-left flipping bits in such a list, the integer case has an "out". You do end up with a string of 0s and 1s, but by assumption it can't have 0s extending infinitely to the left because then it would have been on the list. In other words, the thing you end up with never has its "final" 1, and so what you end up with isn't an integer. This is really the crux of the argument: Not every string of 0s and 1s actually represents an integer. However, put any string of 0s and 1s after the radix point ("decimal point") and that does represent a real number. So what you construct in the real version of the argument really is a real number not on the list (i.e. a contradiction). It's instructive to do the same thought experiment with an imaginary list of rational numbers written out as decimals and see why the diagonal argument fails in that case too. Now I described the above as a kind of procedure ("walk right-to-left") but that's really just for convenience. There isn't any actual iteration going on.
  - danielheath 3y ago
    > Not every string of 0s and 1s actually represents an integer. Is that to say that only the finite ones are? Since an infinitely long string that starts with 1 is infinite in size? Otherwise I can’t make sense of this statement.
    - owalt 3y ago
      Yes, for instance ...101010 (the pattern 10 repeated infinitely) isn't an integer. It's maybe easier to think of the argument as working on sequences: From a sequence (x_0, x_1, x_2, ...) with each x_n a binary digit (i.e. 0 or 1) you can always construct a real number x = Sum(x_n / 2^n, n = 0, 1, 2, ...). The integer you'd want to construct from such a sequence would be Sum(x_n * 2^n, n = 0, 1, 2, ...), but this only works if there's some N such that x_n = 0 for all n > N. Otherwise you would have an "infinite integer" (whatever that means). Valid positive integers are all on the form Sum(x_n * 2^n, n = 0, 1, 2, ..., N), i.e. the binary expansion is finite. The subtlety of the diagonal argument (why it works for reals but not for integers/rationals) is that while it always produces _some_ string of digits, only the real numbers are defined such that the string of digits is itself always a real number. In the integer/rational case, you can construct a number "outside" the set you started from. (In fact you always do if the original list really was of all integers/rationals. Given any enumeration of the rationals, the diagonal argument can actually be used constructively to produce an irrational number.)
- Scarblac 3y ago
  Thinking like that no infinite set can be countable, because "at any one point in time" you haven't completely enumerated it yet. That's not how thinking about infinite sets works.
- systoll 3y ago
  A set is countable if, and only if, there is a bijection between it and the natural numbers — ie if there can be an enumeration. Cantor is doing a proof by contradiction. He’s assuming that the complete enumeration exists precisely because it is wrong. If you object to making that assumption, you’re just agreeing with Cantor’s conclusion before he’s made the argument.
- lordnacho 3y ago
  It's not a process. You think of it as a process because you can only read one line at a time, but the proof is looking at the whole. It's like saying "There are infinitely many primes because if not we could multiply them all together and add one to generate another one". You don't actually have to find all the prime numbers and work out a product. You are saying that's actually not possible because the idea contradicts itself.
- xelxebar 3y ago
  Actually, I think you bring up some really good points. If you believe the reals are countable, then your task is to come up with one, just one, scheme for enumerating them (i.e. putting in 1-to-1 correspondence with the naturals). If, on the other hand, you believe the reals are uncountable, then your task is decidedly harder: You need to come up with some scheme that, given any proposed enumeration, you can produce a number definitively not on that list. Cantor's argument does the latter. Given any scheme---say a computer program---that claims to enumerate the reals, Cantor's argument shows us how to build a corresponding computer program to generate the digits of a number that are never produced by your original program. I.e. if you let the original program list out N reals, Cantor's program can give you an N-digit number that it has definitely not listed. The original program certainly might list it later, but by that point it's listed N+M digits and Cantor's program can give an N+M-digit number that's missing. The point being that Cantor's program always works, no matter how big N gets. On the other hand, as another poster has pointed out, the Cantor scheme fails to work for an actually countable set, like the even numbers or primes. Cantor's argument will still work in a sense. It will give you something, but the thing it gives you will always violate some property that the original set of things must satisfy, like having only finite digits or whatnot.
- Tainnor 3y ago
  Well, we can't really "count to infinity" in real life, and most of mathematics (unless you're a finitist or something, which is rather rare) assumes that we can somehow do it and establishes some base rules about how that would have to work without leading to contradictions. With that said, assume that you have some list of real numbers. In a sense, what we're asking for is a function f, such that f(i, j) returns the j-th digit of the i-th number on that list. [0, 1] Then you construct a function g as follows: def g(j) f(j, j) + 1 % 10 end Now you convince yourself of the fact that there is no number i, such that f(i, j) = g(j) for all j - or in other words, g encodes a different number than f(i, .) for any i. So, for every list of real numbers, there must be a number not on that list. [0]: I'm brushing over the fact that some different sequences of integers encode the same real number, e.g. 0.999... and 1.000... - it doesn't affect the argument substantially. [1]: This function doesn't necessarily have to implementable in a programming language - mathematicians are fine with talking about "uncomputable functions" and claiming that they exist. The argument shows that such a function can't exist even non-constructively. You can avoid all that talk about uncomputable functions and numbers by getting into constructive mathematics, but that's another can of worms and as far as I know it comes with its own unintuitive results. For example, exactly the same diagonalisation argument shows that there is no computable function encoding a list of all computable numbers.
- agd 3y ago
  This is something I’ve pondered, and for what it’s worth, I don’t think any of the responses so far clearly explain the flaw in your rationale. That’s not to say Cantor was wrong - much more likely we’re missing something, however I think the issue is more subtle than people realise.
  - btilly 3y ago
    That is absolutely true. See https://news.ycombinator.com/item?id=37421201 https://news.ycombinator.com/item?id=37421201 for what that subtlety is.
- cvoss 3y ago
  You've gotten a lot of thoughtful answers here already. Here's mine. I'll come at it from a constructivist perspective. There is a way to completely define a countable list. I do not say that you can completely write the list out in finite time. But you can specify it fully. Write a function f : Nat -> X, where X is the type of the things in the list, such that f is total, i.e., provably halts on every input. Your favorite typed lambda calculus or other theorem proving language will give you this property basically for free. The entire list is encoded as f. It doesn't matter that you can only extract elements one at a time by processing this function. They're all there, well-defined. Now, we use this technique twice in Cantor's argument. First, we suppose the existence of f : Nat -> Real with the property that f covers all the reals. What we mean by that is you cannot define a real, x, such that f i != x for all i. (But we will do so.) Second, each real number is itself encoded as a countable list of digits. So, Real := Nat -> Digit. In some sense, every real number is itself "a process" of digit generation, but you don't need to carry it out. Simply holding the function will suffice. Now, it's kind of tricky to compare reals to see which are equal and unequal, but ignoring the 0.99999... = 1 issue, which can be resolved, a proof that x != y involves identifying just one place i : Nat where the digits disagree: x i != y i. Here we go: define x as x i := (f i i) + 1 mod 10. We claim x witnesses that f doesn't cover the reals. We agreed this means we must show x != f i for all i. We agreed that means finding j such that x j != f i j. The proof we seek: Let j := i. We're just pushing functions around in a suitably typed language. Everything halts, nothing is running forever, no infinite storage space is required to hold the supposed list of reals nor the digits of each real. You can whip this up pretty fast in Lean or Coq etc.
  - btilly 3y ago
    Ironically, Cantor's argument falls apart in constructivism.
    - Tainnor 3y ago
      Cantor's argument shows that there exists no surjective map from the natural numbers to the reals and that proof is valid constructively. So the proof still works, it just has a different interpretation.
- btilly 3y ago
  Your ignorance hides wisdom and an unexamined assumption in classical mathematics. The problem is what does existence mean? Classical math includes "procedures" with processes based on absolute truth. They avoid paradox only because you cannot reason about the reasoning process itself. The result of this is simpler arguments, but we must accept the existence of things that we can never, even in principle, write down. Now let's change existence to mean that mathematical things only exist when we can write them down. (Classical mathematics calls this the constructible universe.) So procedures must be computer programs. Real numbers are represented computer programs that produce a sequence of rational numbers converging at a known rate. An enumeration of real numbers is a program that produces a list of programs that themselves represent real numbers. And so on. Now try Cantor's argument. We start with an enumeration of the real numbers. A program that creates a list of programs. We then construct a new real number as per Cantor. So far so good. And, as Cantor said, the new real number cannot be on the enumeration. Cantor now concludes that there are more real numbers. BUT his conclusion is now false! I can easily write down a program that lists every possible program. Ones that crash. Ones that run forever and never stop. And, yes, ones that represent real numbers. It is a countable list. And our new real is on the list! The problem isn't that there are too many real numbers. It is that you can't decide whether or not a given program represents a real number without solving the halting problem. So every enumeration has a choice - it either includes things that aren't real numbers, or it misses some real numbers. But all the things that can be real numbers are on a countable list! The only sense in which there can be "more" real numbers in classical mathematics is that we accept the "existence" of numbers whose claim to exist is extremely tentative. And we do so with decision "procedures" that depend on decisions made based on unverifiable absolute truths. If you want a sense of how different mathematics looks if you don't do that, look up Constructivism.
  - ballenf 3y ago
    Thank you and all the very thoughtful and helpful replies! Definitely going to check out Construvism, which is a new term to me, and was mentioned by several replies.
  - Tainnor 3y ago
    > They avoid paradox only because you cannot reason about the reasoning process itself. All of ZFC can be formulated with an effectively computable set of first-order axioms and every valid theorem has a proof which is nothing more than a finite string of symbols which can be checked in finite time. It's really odd to claim that "you cannot reason about the reasoning process of classical mathematics".
- dannymi 3y ago
  >The proof of uncountability of real numbers starts with a process of enumerating this infinite list of infinitely long binary numbers. Then says that we construct a number that can't be on them by flipping bits the down the diagonal. I don't know what you mean by "process". Any list of numerals like this will be missing (at least) a numerals is what he says. Maybe let's take a step back. It needs a proof by contraposition. The "normal" position is "S -> T" (so if S then T), which also fixes the contraposition "(not T) -> (not S)". Cantor's idea is to have a list of (possibly infinite length) binary literals representing real numbers between 0 and 1 (and if those are uncountable, so are ALL the real numbers :P). The important part is that first consider the set of all such literals, whether countable or not. Let's call those T (for "total"). But then consider the subset of those that can be enumerated. Let's call those S (for "subset"). The countability means that you have a function that literally enumerates those (i.e. a function "natural number -> literal", 1:1) Enumerate the literal and enumerate the digit at some position in the literal. Let a_n be the nth literal. The a_n need to be unique (in order for those to be an enumeration). Let d(n, m) be the nth literal's digit at position n. Now construct a new literal q that differs from the first string in the first position, from the second string in the second position and so on. This q is NOT IN S. (it differs from any of the elements of S in at least one position each) Thereby, we proved that if S is countable, then it's not all of T. (because we found some literal that's not on the list; the list of all needs to be bigger!) So the "position" proof is: "Assume S is countable. Then show it's not all of T." But that, by contraposition, means, if it's all of T then it's not countable. Which is what we wanted.
- calebh 3y ago
  I recently learned that the computable numbers are subcountable but not enumerable. Proof sketch: Turing Machines are enumerable by lexiographically sorting them. The Turing Machines that compute computable numbers are a subset of them. Therefore the set of computable numbers is subcountable. Now assume that the set of computable numbers is enumerable by some Turing Machine M. Then I can construct a new computable number who's ith digit is a swap from the ith number's ith digit given by M (ie a diagonialization). This contradiction shows that the set of computable numbers is not enumerable. Another way of looking at this is that determining if some Turing Machine computes a computable number requires deciding the halting problem, which cannot be done. TMs computing computable numbers are required to terminate given an input precision.
arrowsmith 3y ago
TIL that "Y Combinator" is a mathematical concept and not just a VC firm.
- acjohnson55 3y ago
  Yep. If you ever take a course on theory of programming languages that's based on the lambda calculus, you'll find it's one of the ways to model recursion in a programming language that would otherwise be Turing-incomplete. You get recursion at the cost of being subject to the Halting Problem.

3abiton 3y ago

Great video, thanks for sharing

ballenf 3y ago

I have a problem with the diagonalization, but I'm more of a math fan so please forgive my ignorance. The proof of uncountability of real numbers starts with a process of enumerating this infinite list of infinitely long binary numbers. Then says that we construct a number that can't be on them by flipping bits the down the diagonal. But hasn't this concept already kind of mixed domains? The enumeration was describing a process, but the diagonal flipping move seems to assume or require that the enumeration is complete or at least paused. How could the diagonal construction ever finish to allow a "check" of whether the result of that process is actually on the list. Obviously at any point in time it won't be, but aren't we just kind of proving that we can construct a number that isn't on the list yet? And the first process would certainly eventually get to our constructed number? The diagonal just seems like a shortcut to a number that we know the first process hasn't gotten to yet? I just don't get how we conclude that Integers are countable and Reals are Uncountable from this proof, even though its obvious in an intuitive sense that Reals have to be much "larger".

vgatherps 3y ago
> The proof of uncountability of real numbers starts with a process of enumerating this infinite list of infinitely long binary numbers. > How could the diagonal construction ever finish to allow a "check" of whether the result of that process is actually on the list. > The diagonal just seems like a shortcut to a number that we know the first process hasn't gotten to yet? I think you are mixing up the enumeration of the (hypothetically countable) reals with the existance of said set of reals, and viewing the construction of the counterexample as an actual process that involves programmatically iterating over the list instead of a description of how the digits of said new real number is created. There is no pause or setp-by-step of this iteration that's required, since it's only telling you that the i'th digit of the counterexample will be distinct from the i'th digit of the i'th number (thereby creating a real not in your countable set, since you have created a number outside of your 1-1 mapping onto the natural numbers).
kccqzy 3y ago
You are confused about the concept of countability and finiteness. The enumeration that you mention requires that a set be countable, not that it is finite. So it's wrong to somehow require the enumeration to finish. Countable sets can be finite or infinite. Most interesting countable sets are infinite. The enumeration then means a bijection with the natural numbers. Your definition of enumeration seems to require it to "complete" which is incorrect. (I put "complete" in quotes because that's the word you used, but I don't want you to further confuse that with the completeness of real numbers which is a whole another thing.)
- k__ 3y ago
  It's a bit like saying 0,1... isn't a real number because you couldn't type all the 1s.
owalt 3y ago
I don't quite understand your main concern, but it seems others did and have answered. To elaborate on why Cantor's argument doesn't go through for the integers: Assume you had a list of every integer. To begin with, you couldn't start flipping bits from the left since integers don't start from the left. You could however imagine them having a sequence of 0s extending infinitely to the left, e.g. 101 = ...00000101. If you did that, the diagonal argument is possible to perform only starting from the rightmost digit, and you do end up with some string of numbers. The problem is this: If you do walk right-to-left flipping bits in such a list, the integer case has an "out". You do end up with a string of 0s and 1s, but by assumption it can't have 0s extending infinitely to the left because then it would have been on the list. In other words, the thing you end up with never has its "final" 1, and so what you end up with isn't an integer. This is really the crux of the argument: Not every string of 0s and 1s actually represents an integer. However, put any string of 0s and 1s after the radix point ("decimal point") and that does represent a real number. So what you construct in the real version of the argument really is a real number not on the list (i.e. a contradiction). It's instructive to do the same thought experiment with an imaginary list of rational numbers written out as decimals and see why the diagonal argument fails in that case too. Now I described the above as a kind of procedure ("walk right-to-left") but that's really just for convenience. There isn't any actual iteration going on.
- danielheath 3y ago
  > Not every string of 0s and 1s actually represents an integer. Is that to say that only the finite ones are? Since an infinitely long string that starts with 1 is infinite in size? Otherwise I can’t make sense of this statement.
  - owalt 3y ago
    Yes, for instance ...101010 (the pattern 10 repeated infinitely) isn't an integer. It's maybe easier to think of the argument as working on sequences: From a sequence (x_0, x_1, x_2, ...) with each x_n a binary digit (i.e. 0 or 1) you can always construct a real number x = Sum(x_n / 2^n, n = 0, 1, 2, ...). The integer you'd want to construct from such a sequence would be Sum(x_n * 2^n, n = 0, 1, 2, ...), but this only works if there's some N such that x_n = 0 for all n > N. Otherwise you would have an "infinite integer" (whatever that means). Valid positive integers are all on the form Sum(x_n * 2^n, n = 0, 1, 2, ..., N), i.e. the binary expansion is finite. The subtlety of the diagonal argument (why it works for reals but not for integers/rationals) is that while it always produces _some_ string of digits, only the real numbers are defined such that the string of digits is itself always a real number. In the integer/rational case, you can construct a number "outside" the set you started from. (In fact you always do if the original list really was of all integers/rationals. Given any enumeration of the rationals, the diagonal argument can actually be used constructively to produce an irrational number.)
Scarblac 3y ago
Thinking like that no infinite set can be countable, because "at any one point in time" you haven't completely enumerated it yet. That's not how thinking about infinite sets works.
systoll 3y ago
A set is countable if, and only if, there is a bijection between it and the natural numbers — ie if there can be an enumeration. Cantor is doing a proof by contradiction. He’s assuming that the complete enumeration exists precisely because it is wrong. If you object to making that assumption, you’re just agreeing with Cantor’s conclusion before he’s made the argument.
lordnacho 3y ago
It's not a process. You think of it as a process because you can only read one line at a time, but the proof is looking at the whole. It's like saying "There are infinitely many primes because if not we could multiply them all together and add one to generate another one". You don't actually have to find all the prime numbers and work out a product. You are saying that's actually not possible because the idea contradicts itself.
xelxebar 3y ago
Actually, I think you bring up some really good points. If you believe the reals are countable, then your task is to come up with one, just one, scheme for enumerating them (i.e. putting in 1-to-1 correspondence with the naturals). If, on the other hand, you believe the reals are uncountable, then your task is decidedly harder: You need to come up with some scheme that, given any proposed enumeration, you can produce a number definitively not on that list. Cantor's argument does the latter. Given any scheme---say a computer program---that claims to enumerate the reals, Cantor's argument shows us how to build a corresponding computer program to generate the digits of a number that are never produced by your original program. I.e. if you let the original program list out N reals, Cantor's program can give you an N-digit number that it has definitely not listed. The original program certainly might list it later, but by that point it's listed N+M digits and Cantor's program can give an N+M-digit number that's missing. The point being that Cantor's program always works, no matter how big N gets. On the other hand, as another poster has pointed out, the Cantor scheme fails to work for an actually countable set, like the even numbers or primes. Cantor's argument will still work in a sense. It will give you something, but the thing it gives you will always violate some property that the original set of things must satisfy, like having only finite digits or whatnot.
Tainnor 3y ago
Well, we can't really "count to infinity" in real life, and most of mathematics (unless you're a finitist or something, which is rather rare) assumes that we can somehow do it and establishes some base rules about how that would have to work without leading to contradictions. With that said, assume that you have some list of real numbers. In a sense, what we're asking for is a function f, such that f(i, j) returns the j-th digit of the i-th number on that list. [0, 1] Then you construct a function g as follows: def g(j) f(j, j) + 1 % 10 end Now you convince yourself of the fact that there is no number i, such that f(i, j) = g(j) for all j - or in other words, g encodes a different number than f(i, .) for any i. So, for every list of real numbers, there must be a number not on that list. [0]: I'm brushing over the fact that some different sequences of integers encode the same real number, e.g. 0.999... and 1.000... - it doesn't affect the argument substantially. [1]: This function doesn't necessarily have to implementable in a programming language - mathematicians are fine with talking about "uncomputable functions" and claiming that they exist. The argument shows that such a function can't exist even non-constructively. You can avoid all that talk about uncomputable functions and numbers by getting into constructive mathematics, but that's another can of worms and as far as I know it comes with its own unintuitive results. For example, exactly the same diagonalisation argument shows that there is no computable function encoding a list of all computable numbers.
agd 3y ago
This is something I’ve pondered, and for what it’s worth, I don’t think any of the responses so far clearly explain the flaw in your rationale. That’s not to say Cantor was wrong - much more likely we’re missing something, however I think the issue is more subtle than people realise.
- btilly 3y ago
  That is absolutely true. See https://news.ycombinator.com/item?id=37421201 https://news.ycombinator.com/item?id=37421201 for what that subtlety is.
cvoss 3y ago
You've gotten a lot of thoughtful answers here already. Here's mine. I'll come at it from a constructivist perspective. There is a way to completely define a countable list. I do not say that you can completely write the list out in finite time. But you can specify it fully. Write a function f : Nat -> X, where X is the type of the things in the list, such that f is total, i.e., provably halts on every input. Your favorite typed lambda calculus or other theorem proving language will give you this property basically for free. The entire list is encoded as f. It doesn't matter that you can only extract elements one at a time by processing this function. They're all there, well-defined. Now, we use this technique twice in Cantor's argument. First, we suppose the existence of f : Nat -> Real with the property that f covers all the reals. What we mean by that is you cannot define a real, x, such that f i != x for all i. (But we will do so.) Second, each real number is itself encoded as a countable list of digits. So, Real := Nat -> Digit. In some sense, every real number is itself "a process" of digit generation, but you don't need to carry it out. Simply holding the function will suffice. Now, it's kind of tricky to compare reals to see which are equal and unequal, but ignoring the 0.99999... = 1 issue, which can be resolved, a proof that x != y involves identifying just one place i : Nat where the digits disagree: x i != y i. Here we go: define x as x i := (f i i) + 1 mod 10. We claim x witnesses that f doesn't cover the reals. We agreed this means we must show x != f i for all i. We agreed that means finding j such that x j != f i j. The proof we seek: Let j := i. We're just pushing functions around in a suitably typed language. Everything halts, nothing is running forever, no infinite storage space is required to hold the supposed list of reals nor the digits of each real. You can whip this up pretty fast in Lean or Coq etc.
- btilly 3y ago
  Ironically, Cantor's argument falls apart in constructivism.
  - Tainnor 3y ago
    Cantor's argument shows that there exists no surjective map from the natural numbers to the reals and that proof is valid constructively. So the proof still works, it just has a different interpretation.
btilly 3y ago
Your ignorance hides wisdom and an unexamined assumption in classical mathematics. The problem is what does existence mean? Classical math includes "procedures" with processes based on absolute truth. They avoid paradox only because you cannot reason about the reasoning process itself. The result of this is simpler arguments, but we must accept the existence of things that we can never, even in principle, write down. Now let's change existence to mean that mathematical things only exist when we can write them down. (Classical mathematics calls this the constructible universe.) So procedures must be computer programs. Real numbers are represented computer programs that produce a sequence of rational numbers converging at a known rate. An enumeration of real numbers is a program that produces a list of programs that themselves represent real numbers. And so on. Now try Cantor's argument. We start with an enumeration of the real numbers. A program that creates a list of programs. We then construct a new real number as per Cantor. So far so good. And, as Cantor said, the new real number cannot be on the enumeration. Cantor now concludes that there are more real numbers. BUT his conclusion is now false! I can easily write down a program that lists every possible program. Ones that crash. Ones that run forever and never stop. And, yes, ones that represent real numbers. It is a countable list. And our new real is on the list! The problem isn't that there are too many real numbers. It is that you can't decide whether or not a given program represents a real number without solving the halting problem. So every enumeration has a choice - it either includes things that aren't real numbers, or it misses some real numbers. But all the things that can be real numbers are on a countable list! The only sense in which there can be "more" real numbers in classical mathematics is that we accept the "existence" of numbers whose claim to exist is extremely tentative. And we do so with decision "procedures" that depend on decisions made based on unverifiable absolute truths. If you want a sense of how different mathematics looks if you don't do that, look up Constructivism.
- ballenf 3y ago
  Thank you and all the very thoughtful and helpful replies! Definitely going to check out Construvism, which is a new term to me, and was mentioned by several replies.
- Tainnor 3y ago
  > They avoid paradox only because you cannot reason about the reasoning process itself. All of ZFC can be formulated with an effectively computable set of first-order axioms and every valid theorem has a proof which is nothing more than a finite string of symbols which can be checked in finite time. It's really odd to claim that "you cannot reason about the reasoning process of classical mathematics".
dannymi 3y ago
>The proof of uncountability of real numbers starts with a process of enumerating this infinite list of infinitely long binary numbers. Then says that we construct a number that can't be on them by flipping bits the down the diagonal. I don't know what you mean by "process". Any list of numerals like this will be missing (at least) a numerals is what he says. Maybe let's take a step back. It needs a proof by contraposition. The "normal" position is "S -> T" (so if S then T), which also fixes the contraposition "(not T) -> (not S)". Cantor's idea is to have a list of (possibly infinite length) binary literals representing real numbers between 0 and 1 (and if those are uncountable, so are ALL the real numbers :P). The important part is that first consider the set of all such literals, whether countable or not. Let's call those T (for "total"). But then consider the subset of those that can be enumerated. Let's call those S (for "subset"). The countability means that you have a function that literally enumerates those (i.e. a function "natural number -> literal", 1:1) Enumerate the literal and enumerate the digit at some position in the literal. Let a_n be the nth literal. The a_n need to be unique (in order for those to be an enumeration). Let d(n, m) be the nth literal's digit at position n. Now construct a new literal q that differs from the first string in the first position, from the second string in the second position and so on. This q is NOT IN S. (it differs from any of the elements of S in at least one position each) Thereby, we proved that if S is countable, then it's not all of T. (because we found some literal that's not on the list; the list of all needs to be bigger!) So the "position" proof is: "Assume S is countable. Then show it's not all of T." But that, by contraposition, means, if it's all of T then it's not countable. Which is what we wanted.
calebh 3y ago
I recently learned that the computable numbers are subcountable but not enumerable. Proof sketch: Turing Machines are enumerable by lexiographically sorting them. The Turing Machines that compute computable numbers are a subset of them. Therefore the set of computable numbers is subcountable. Now assume that the set of computable numbers is enumerable by some Turing Machine M. Then I can construct a new computable number who's ith digit is a swap from the ith number's ith digit given by M (ie a diagonialization). This contradiction shows that the set of computable numbers is not enumerable. Another way of looking at this is that determining if some Turing Machine computes a computable number requires deciding the halting problem, which cannot be done. TMs computing computable numbers are required to terminate given an input precision.

arrowsmith 3y ago

TIL that "Y Combinator" is a mathematical concept and not just a VC firm.

acjohnson55 3y ago
Yep. If you ever take a course on theory of programming languages that's based on the lambda calculus, you'll find it's one of the ways to model recursion in a programming language that would otherwise be Turing-incomplete. You get recursion at the cost of being subject to the Halting Problem.