7 ms·

As a constructivist I'll be over in the corner that says that there are only a countable number of real numbers, and the unimaginable number of unimaginable inf

by btilly 5y ago

As a constructivist I'll be over in the corner that says that there are only a countable number of real numbers, and the unimaginable number of unimaginable infinities that classical mathematics insiste exists is all made up nonsense. That, in fact, things that can't ever be named, even in principle, don't actually exist. What is interesting is that as shocking as constructivism may be, there is no logical flaw in it. If classical mathematics is consistent, then so is constructivism. And "there exists" is a whole lot more meaningful in constructivism.

scapp 5y ago
You sound like you need to read this [0] answer to the question "Are real numbers countable in constructive mathematics?". > You are using the word "constructive" in an unusual way. It is true that, in ZFC, the set of computable real numbers is countable, but that is not directly a statement about constructive mathematics. > Not every school of constructive mathematics identifies real numbers with algorithms; that's a characteristic of the "Russian" school as I understand it. In other schools of constructivism that I am more familiar with, real numbers are coded by elements of 2^ω, or by a certain type of Dedekind cut on the rationals. In such schools it is not universally assumed that every real number is associated with a finite algorithm. > Even in the Russian school, they would not say that the set of real numbers is countable. Because, if you identify real numbers with algorithms, there is no computable enumeration of computable reals that lists all computable reals, and so the translation of "the real numbers are countable" into this setting is false. > That phenomenon also occurs in classical computable analysis. The subsystem RCA0 of second-order arithmetic has a model in which every real number is computable. But this subsystem still proves that there is no surjection N -> R. --- It's worth noting that another answer to that question (Andrej Bauer's) gives a constructive proof that the real numbers are uncountable using with the axiom of countable choice. The question of whether it's provable without the axiom of countable choice is open (though see this [1] fairly recent paper on a proof for MacNeille reals). [0] https://mathoverflow.net/questions/30643/are-real-numbers-countable-in-constructive-mathematics/30657#30657 https://mathoverflow.net/questions/30643/are-real-numbers-co... [1] https://arxiv.org/abs/1902.07366 https://arxiv.org/abs/1902.07366
- btilly 5y ago
  Yes, there are multiple constructivist approaches possible. However since my objection to classical approaches is that I want "X exists" to be meaningful, I like mathematical objects that can be written down with a finite number of symbols in a finite space. Which means that I'm only interested in a countable universe of possible mathematical things. If you say "exists" about anything else, I'll understand you - I do have advanced degrees in math. But I'll think that you're using the word "exists" in a deeply artificial way.
  - LudwigNagasena 5y ago
    What’s the problem with it being “artificial”? Is your problem purely linguistic? You just dislike the word “exists” being used in this context?
    - btilly 5y ago
      The problem is that exists comes to mean something technical that doesn't match common usage. Let's take my favorite example. In graph theory, a minor of a graph is a graph you can get by removing vertices, removing edges, or by replacing an edge-vertex-edge triple with a single edge. Many categories of graphs are closed under the act of taking minors. For example planar graphs, graphs you can draw on the plane with no crossings, are. The category of planar graphs is entirely described by the fact that any graph that isn't planar must have either K5 or K3,3 as minors. That is, a graph with 5 vertices, all connected. Or a graph with 2 groups of 3 vertices, that all connect to each other. Therefore we call those two graphs the "forbidden minors" for planar graphs. The Robertson–Seymour theorem says that any category of graphs which is closed under graph minors has a similar description. There is a finite list of forbidden minors which, if none are minors of a given graph, then that graph is in the category. Since there is a polynomial time algorithm to detect whether a given graph is a minor of another, this immediately means any category of graphs closed under taking minors must have a polynomial time algorithm to test for membership. Just test each forbidden minor. So far this is straightforward, but here is where things get weird. The first catch is that the Robertson–Seymour theorem is non-constructive. That is, it says that the list exists and is finite. But it does not bound the number. It does not give us a way to find those minors. It does not give us any way to determine whether we have a complete list. For example we know of thousands of minimal forbidden minors for graphs that can be drawn on a torus, and do not know if our list is complete. The second catch is that we know that none of those things are possible to do. That is, there are collections of categories of such graphs such that we can prove that no algorithm can bound the number, no algorithm can search for those examples, and no algorithm can verify that a list of forbidden minors is complete. In what sense does a finite thing that is unfindable, unverifiable, and of unknowable size actually exist? And, if you think that it exists, in what sense is something of unboundable size actually finite?
klysm 5y ago
Does constructivism rule out uncountability because induction is always indexable?
- btilly 5y ago
  There are different schools of constructivism. But if you insist on only dealing with mathematical objects that admit of finite descriptions with finite symbols, there is a surjection from a countable set onto the entire universe of possible mathematical objects. That said, an enumeration of all mathematical objects is not possible. That's because we may not be able to resolve the question of whether 2 descriptions of a mathematical object actually refer to the same object or not.
chmod775 5y ago
> there are only a countable number of real numbers Then you should be able to come up with a function that assigns a natural number uniquely to each real number. Of course if you tried that I could immediately name you a real number, or a pair of them, for which your rule doesn't work.
- skoodge 5y ago
  That depends on what you mean by "assigns uniquely", "rule" and "doesn't work", which is why this question is deeply entangled with philosophical issues that cannot be settled purely mathematically. It is obvious that all expressions in the English language can be ordered from smallest to largest and lexicographically, which makes these expressions trivially countable. We can thus assign natural numbers to real numbers by assigning numbers to their expressions in a natural or formal language, which will of course include infinitely many expressions that are just nonsense descriptions and infinitely many expressions that map to the same real number. These expressions will also include any possible expressions of Cantor's or other diagonalized numbers. In such a sense then, we can trivially "count" the real numbers unless we hold the philosophical view that there are real numbers that are not expressible. This is where it becomes a question of philosophy of mathematics, not mathematics proper. You can of course object that what you meant by "assigns uniquely" is an unambiguous 1:1 mapping and that including any number of nonsense descriptions misses the point. In that case giving a "rule doesn't work" because the diagonalized number always escapes the proposed system of counting the numbers, but only because the diagonalized number is allowed to 'parasitically' depend on the totality of the system, but is excluded from the system (or else it would diagonalize itself and become ambiguous at that particular decimal place). This particular viewpoint is tied to a particular philosophical position, however, and not all positions in the philosophy of mathematics will agree with it. This all might seem trivial or even nonsensical (as philosophy of mathematics so often appears), but I merely want to point out that the 'uncountability' of the real numbers is not a consequence of the set of the natural numbers being 'too small' to hold all the real numbers, because they are 'large enough' to assign numbers to all possible descriptions all real numbers that will ever be expressed in language. Uncountability is a consequence of a view that restricts Cantor's diagonalized number from the set of the countable number but still considers this diagonalized number to be a real number (which again is only unambiguously defined if it is not allowed to diagonalize itself). There are however other possible philosophical viewpoints which either include the diagonalized number in the set of countable numbers (at the cost of including ambiguous or paradoxical numbers) or reject the view that Cantor's diagonalized number should be considered to be a real number in the first place. tl;dr: Yeah, you can always name a real number for which a particular counting rule does not work, but only as long as there is agreement regarding the philosophical underpinnings. Most mathematicians can probably be considered platonists and from their standpoint the real numbers are obviously uncountable, but that is by no means true for all positions in the philosophy of mathematics.
papandada 5y ago
I have found my people. Thank you.
reggieband 5y ago
I'd like to subscribe to this newsletter. Mathematicians using sets to argue about the size of uncountably infinite Reals feels like the old joke of philosophers arguing over how many angels can fit on the head of a pin. I often wonder if we've used set theory (and formalisms of math based on logic) to substitute one metaphysical theory for another equivalent one. I can understand the frustration of mathematicians of the past being told they have to ensure their theories align with some spiritual mythology. But it sort of feels like I'm being forced to accept some kind of metaphysical truth in the name of ensuring the calculus of infinitesimals is grounded in logic.
ummonk 5y ago
Constructivism (including the kind that precludes uncountable infinities) is not inherently more shocking than classical mathematics. It only seems surprising because classical mathematics has become the default formalism.

by btilly 5y ago

scapp 5y ago

You sound like you need to read this [0] answer to the question "Are real numbers countable in constructive mathematics?". > You are using the word "constructive" in an unusual way. It is true that, in ZFC, the set of computable real numbers is countable, but that is not directly a statement about constructive mathematics. > Not every school of constructive mathematics identifies real numbers with algorithms; that's a characteristic of the "Russian" school as I understand it. In other schools of constructivism that I am more familiar with, real numbers are coded by elements of 2^ω, or by a certain type of Dedekind cut on the rationals. In such schools it is not universally assumed that every real number is associated with a finite algorithm. > Even in the Russian school, they would not say that the set of real numbers is countable. Because, if you identify real numbers with algorithms, there is no computable enumeration of computable reals that lists all computable reals, and so the translation of "the real numbers are countable" into this setting is false. > That phenomenon also occurs in classical computable analysis. The subsystem RCA0 of second-order arithmetic has a model in which every real number is computable. But this subsystem still proves that there is no surjection N -> R. --- It's worth noting that another answer to that question (Andrej Bauer's) gives a constructive proof that the real numbers are uncountable using with the axiom of countable choice. The question of whether it's provable without the axiom of countable choice is open (though see this [1] fairly recent paper on a proof for MacNeille reals). [0] https://mathoverflow.net/questions/30643/are-real-numbers-countable-in-constructive-mathematics/30657#30657 https://mathoverflow.net/questions/30643/are-real-numbers-co... [1] https://arxiv.org/abs/1902.07366 https://arxiv.org/abs/1902.07366

btilly 5y ago
Yes, there are multiple constructivist approaches possible. However since my objection to classical approaches is that I want "X exists" to be meaningful, I like mathematical objects that can be written down with a finite number of symbols in a finite space. Which means that I'm only interested in a countable universe of possible mathematical things. If you say "exists" about anything else, I'll understand you - I do have advanced degrees in math. But I'll think that you're using the word "exists" in a deeply artificial way.
- LudwigNagasena 5y ago
  What’s the problem with it being “artificial”? Is your problem purely linguistic? You just dislike the word “exists” being used in this context?
  - btilly 5y ago
    The problem is that exists comes to mean something technical that doesn't match common usage. Let's take my favorite example. In graph theory, a minor of a graph is a graph you can get by removing vertices, removing edges, or by replacing an edge-vertex-edge triple with a single edge. Many categories of graphs are closed under the act of taking minors. For example planar graphs, graphs you can draw on the plane with no crossings, are. The category of planar graphs is entirely described by the fact that any graph that isn't planar must have either K5 or K3,3 as minors. That is, a graph with 5 vertices, all connected. Or a graph with 2 groups of 3 vertices, that all connect to each other. Therefore we call those two graphs the "forbidden minors" for planar graphs. The Robertson–Seymour theorem says that any category of graphs which is closed under graph minors has a similar description. There is a finite list of forbidden minors which, if none are minors of a given graph, then that graph is in the category. Since there is a polynomial time algorithm to detect whether a given graph is a minor of another, this immediately means any category of graphs closed under taking minors must have a polynomial time algorithm to test for membership. Just test each forbidden minor. So far this is straightforward, but here is where things get weird. The first catch is that the Robertson–Seymour theorem is non-constructive. That is, it says that the list exists and is finite. But it does not bound the number. It does not give us a way to find those minors. It does not give us any way to determine whether we have a complete list. For example we know of thousands of minimal forbidden minors for graphs that can be drawn on a torus, and do not know if our list is complete. The second catch is that we know that none of those things are possible to do. That is, there are collections of categories of such graphs such that we can prove that no algorithm can bound the number, no algorithm can search for those examples, and no algorithm can verify that a list of forbidden minors is complete. In what sense does a finite thing that is unfindable, unverifiable, and of unknowable size actually exist? And, if you think that it exists, in what sense is something of unboundable size actually finite?

klysm 5y ago

Does constructivism rule out uncountability because induction is always indexable?

btilly 5y ago
There are different schools of constructivism. But if you insist on only dealing with mathematical objects that admit of finite descriptions with finite symbols, there is a surjection from a countable set onto the entire universe of possible mathematical objects. That said, an enumeration of all mathematical objects is not possible. That's because we may not be able to resolve the question of whether 2 descriptions of a mathematical object actually refer to the same object or not.

chmod775 5y ago

> there are only a countable number of real numbers Then you should be able to come up with a function that assigns a natural number uniquely to each real number. Of course if you tried that I could immediately name you a real number, or a pair of them, for which your rule doesn't work.

skoodge 5y ago
That depends on what you mean by "assigns uniquely", "rule" and "doesn't work", which is why this question is deeply entangled with philosophical issues that cannot be settled purely mathematically. It is obvious that all expressions in the English language can be ordered from smallest to largest and lexicographically, which makes these expressions trivially countable. We can thus assign natural numbers to real numbers by assigning numbers to their expressions in a natural or formal language, which will of course include infinitely many expressions that are just nonsense descriptions and infinitely many expressions that map to the same real number. These expressions will also include any possible expressions of Cantor's or other diagonalized numbers. In such a sense then, we can trivially "count" the real numbers unless we hold the philosophical view that there are real numbers that are not expressible. This is where it becomes a question of philosophy of mathematics, not mathematics proper. You can of course object that what you meant by "assigns uniquely" is an unambiguous 1:1 mapping and that including any number of nonsense descriptions misses the point. In that case giving a "rule doesn't work" because the diagonalized number always escapes the proposed system of counting the numbers, but only because the diagonalized number is allowed to 'parasitically' depend on the totality of the system, but is excluded from the system (or else it would diagonalize itself and become ambiguous at that particular decimal place). This particular viewpoint is tied to a particular philosophical position, however, and not all positions in the philosophy of mathematics will agree with it. This all might seem trivial or even nonsensical (as philosophy of mathematics so often appears), but I merely want to point out that the 'uncountability' of the real numbers is not a consequence of the set of the natural numbers being 'too small' to hold all the real numbers, because they are 'large enough' to assign numbers to all possible descriptions all real numbers that will ever be expressed in language. Uncountability is a consequence of a view that restricts Cantor's diagonalized number from the set of the countable number but still considers this diagonalized number to be a real number (which again is only unambiguously defined if it is not allowed to diagonalize itself). There are however other possible philosophical viewpoints which either include the diagonalized number in the set of countable numbers (at the cost of including ambiguous or paradoxical numbers) or reject the view that Cantor's diagonalized number should be considered to be a real number in the first place. tl;dr: Yeah, you can always name a real number for which a particular counting rule does not work, but only as long as there is agreement regarding the philosophical underpinnings. Most mathematicians can probably be considered platonists and from their standpoint the real numbers are obviously uncountable, but that is by no means true for all positions in the philosophy of mathematics.

papandada 5y ago

I have found my people. Thank you.

reggieband 5y ago

I'd like to subscribe to this newsletter. Mathematicians using sets to argue about the size of uncountably infinite Reals feels like the old joke of philosophers arguing over how many angels can fit on the head of a pin. I often wonder if we've used set theory (and formalisms of math based on logic) to substitute one metaphysical theory for another equivalent one. I can understand the frustration of mathematicians of the past being told they have to ensure their theories align with some spiritual mythology. But it sort of feels like I'm being forced to accept some kind of metaphysical truth in the name of ensuring the calculus of infinitesimals is grounded in logic.

ummonk 5y ago

Constructivism (including the kind that precludes uncountable infinities) is not inherently more shocking than classical mathematics. It only seems surprising because classical mathematics has become the default formalism.