4 ms·

I consider uncountability an artefact of a flawed approach to mathematics. I'd recommend looking into constructive mathematics based on intuitionistic logic. Al

by madez 11y ago

I consider uncountability an artefact of a flawed approach to mathematics. I'd recommend looking into constructive mathematics based on intuitionistic logic. All fruitful insights based on other mathematics can be proven by it, from all of it's results we can easily extract methods and it is much less mystic. I think it is much more fun, too.

baddox 11y ago
I'm aware of constructivism, but what is "intuitionistic logic?" I am under the impression that the real numbers (and their uncountability) are generally accepted by constructivists.
- madez 11y ago
  Intuitionistic logic is nearly classical logic. That is, we start by assigning statements one of the two values ‘True‘ and ’False’. While truth in the classical sense is abstract, it is concretized in intuitionistic logic with the meaning of ’we can prove it’. We know that there are statements that can neither be proved nor disproved, so we cannot make use of the law of excluded middle "a statement is true or it is not". Add that we are consistent, that is "not (a and not a)" for all a, and then negation must not be the inverse of itself, because we'd be able to proof the law excluded middle otherwise. You see, it is basically classical logic with some minor adaptions to take into account what we’ve learned. I understand under "constructive reals" the computable reals, and there are only countably many of them.
  - baddox 11y ago
    So is your intuitionist discipline a subset of constructivism? I thought that constructivists generally accept the existence and uncountability of the real numbers.
    - madez 11y ago
      I don’t feel safe enough with the vocabulary, so please let me use my own words to describe it. Construcive mathematics implies for me to construct all objects you talk about on the things you already declared (for example, recursion becomes a notational shortcut). So, we need to start with something. One simple approach would be finite bit arrays. The most general approach I see, and the one I take, is to start with computable sequences of bits. Consequently, everything based on that is countable.
  - thetwiceler 11y ago
    It seems misleading to say that intuitionistic logic assigns statements to one of the two values, True or False. There's no symmetry between the notions of truth and falsity as there is in boolean logic. You need to be very, very careful when talking about the size of the constructive reals. If you are working within constructive mathematics, if you describe the real numbers as setoids of Cauchy sequences with Cauchy-equivalence as the equivalence relation, then there are uncountably many real numbers. From a meta-theoretic perspective, it is obvious (as we are working in constructive mathematics) that every real number is in some sense "computable". Your notion that there are countably many constructive reals probably comes from definitions of the constructive reals from within classical set theory, wherein you must internalize some notion of what it means for a real number to be constructible, and so you are, in a sense, working meta-theoretically. Then it is no surprise that the computable real numbers are countable. After all, Skolem's paradox says that, meta-theoretically, we could have countable models of the classical real numbers as well. Additionally, meta-theoretically, we see that our definition of real numbers in constructive mathematics will also have a countable model when seen from the outside.
    - madez 11y ago
      if you describe the real numbers as setoids of Cauchy sequences with Cauchy-equivalence as the equivalence relation, then there are uncountably many real numbers. I start with computable sequences (or — if want — with turing machines), define natural numbers based on them, go to the rational numbers, define real numbers as a setoid of cauchy-sequences (note: all these sequences will be computable by the way we constructed them) of rational numbers, and end up with countably many. So, it depends on what you start your constructive world with. I see no way to start with something uncountable. You talk about meta-theory and models. I never saw the reason to complicate things with that. Care to elaborate?
      - ihm 11y ago
        The reals one defines thee reals constructively in essentially the same way as one does classically. When the parent commenter says the reals in constructive mathematics are uncountable, he means that inside of a constructive system one can prove the statement There does not exist a bijection between the natural numbers and the real numbers. which is true. You are free to interpret constructive logic in various ways. If you interpret it as the logic of computable things, in which case this statement becomes interpreted as something like There is no computable bijection between the natural numbers and the computable reals. If you interpret it into classical logic, it becomes (now in the classical sense) There is no bijection between the natural numbers and the reals.
  - vilhelm_s 11y ago
    I think there is no difference between constructive and classical logic here? The proof of "the powerset of the natural is uncountable" (or equivalently, expanding out the definition of uncountability, "there does not exist a bijection between N and P(N)") is constructive, and will hold just as well in intuinistic logic. You can't get away from uncountable sets. On the other hand, you could prove a metatheoretic result, constructing a model which only contains sets which are forced to exist by some finite formula (and therefore the model is countable). But that you can do in ordinary classical set theory also (the Löwenheim-Skolem theorem, Gödel's constructible universe). I guess this is analogous to how, in constructive logic every function is computable, but it is not possible to internalize this fact as an axiom in the logic. (https://existentialtype.wordpress.com/2012/08/09/churchs-law/ https://existentialtype.wordpress.com/2012/08/09/churchs-law...)
- thetwiceler 11y ago
  They're usually used synonymously. Yes, Cantor's diagonal argument can still be used to show the uncountability of real numbers in a constructive setting.
- ihm 11y ago
  I would take a look at Andrej Bauer's excellent talk "Stages of Accepting Constructive Mathematics"[0]. Essentially, constructive mathematics is mathematics done without the law of excluded middle ("for all propositions P, either P or not P"). Importantly, it does not necessitate that you deny the law of excluded middle. Intuitionism (or intuitionistic mathematics) is sometimes used to mean the same thing as constructivism and sometimes refers to Brouwer's[1] practice of denying excluded middle by introducing an axiom along the lines of "all functions are computable" or "all functions are continuous" (which from some perspectives is almost the same thing). [0]: https://www.youtube.com/watch?v=zmhd8clDd_Y https://www.youtube.com/watch?v=zmhd8clDd_Y [1]: https://en.wikipedia.org/wiki/L._E._J._Brouwer https://en.wikipedia.org/wiki/L._E._J._Brouwer

by madez 11y ago

baddox 11y ago

I'm aware of constructivism, but what is "intuitionistic logic?" I am under the impression that the real numbers (and their uncountability) are generally accepted by constructivists.

madez 11y ago
Intuitionistic logic is nearly classical logic. That is, we start by assigning statements one of the two values ‘True‘ and ’False’. While truth in the classical sense is abstract, it is concretized in intuitionistic logic with the meaning of ’we can prove it’. We know that there are statements that can neither be proved nor disproved, so we cannot make use of the law of excluded middle "a statement is true or it is not". Add that we are consistent, that is "not (a and not a)" for all a, and then negation must not be the inverse of itself, because we'd be able to proof the law excluded middle otherwise. You see, it is basically classical logic with some minor adaptions to take into account what we’ve learned. I understand under "constructive reals" the computable reals, and there are only countably many of them.
- baddox 11y ago
  So is your intuitionist discipline a subset of constructivism? I thought that constructivists generally accept the existence and uncountability of the real numbers.
  - madez 11y ago
    I don’t feel safe enough with the vocabulary, so please let me use my own words to describe it. Construcive mathematics implies for me to construct all objects you talk about on the things you already declared (for example, recursion becomes a notational shortcut). So, we need to start with something. One simple approach would be finite bit arrays. The most general approach I see, and the one I take, is to start with computable sequences of bits. Consequently, everything based on that is countable.
- thetwiceler 11y ago
  It seems misleading to say that intuitionistic logic assigns statements to one of the two values, True or False. There's no symmetry between the notions of truth and falsity as there is in boolean logic. You need to be very, very careful when talking about the size of the constructive reals. If you are working within constructive mathematics, if you describe the real numbers as setoids of Cauchy sequences with Cauchy-equivalence as the equivalence relation, then there are uncountably many real numbers. From a meta-theoretic perspective, it is obvious (as we are working in constructive mathematics) that every real number is in some sense "computable". Your notion that there are countably many constructive reals probably comes from definitions of the constructive reals from within classical set theory, wherein you must internalize some notion of what it means for a real number to be constructible, and so you are, in a sense, working meta-theoretically. Then it is no surprise that the computable real numbers are countable. After all, Skolem's paradox says that, meta-theoretically, we could have countable models of the classical real numbers as well. Additionally, meta-theoretically, we see that our definition of real numbers in constructive mathematics will also have a countable model when seen from the outside.
  - madez 11y ago
    if you describe the real numbers as setoids of Cauchy sequences with Cauchy-equivalence as the equivalence relation, then there are uncountably many real numbers. I start with computable sequences (or — if want — with turing machines), define natural numbers based on them, go to the rational numbers, define real numbers as a setoid of cauchy-sequences (note: all these sequences will be computable by the way we constructed them) of rational numbers, and end up with countably many. So, it depends on what you start your constructive world with. I see no way to start with something uncountable. You talk about meta-theory and models. I never saw the reason to complicate things with that. Care to elaborate?
    - ihm 11y ago
      The reals one defines thee reals constructively in essentially the same way as one does classically. When the parent commenter says the reals in constructive mathematics are uncountable, he means that inside of a constructive system one can prove the statement There does not exist a bijection between the natural numbers and the real numbers. which is true. You are free to interpret constructive logic in various ways. If you interpret it as the logic of computable things, in which case this statement becomes interpreted as something like There is no computable bijection between the natural numbers and the computable reals. If you interpret it into classical logic, it becomes (now in the classical sense) There is no bijection between the natural numbers and the reals.
- vilhelm_s 11y ago
  I think there is no difference between constructive and classical logic here? The proof of "the powerset of the natural is uncountable" (or equivalently, expanding out the definition of uncountability, "there does not exist a bijection between N and P(N)") is constructive, and will hold just as well in intuinistic logic. You can't get away from uncountable sets. On the other hand, you could prove a metatheoretic result, constructing a model which only contains sets which are forced to exist by some finite formula (and therefore the model is countable). But that you can do in ordinary classical set theory also (the Löwenheim-Skolem theorem, Gödel's constructible universe). I guess this is analogous to how, in constructive logic every function is computable, but it is not possible to internalize this fact as an axiom in the logic. (https://existentialtype.wordpress.com/2012/08/09/churchs-law/ https://existentialtype.wordpress.com/2012/08/09/churchs-law...)
thetwiceler 11y ago
They're usually used synonymously. Yes, Cantor's diagonal argument can still be used to show the uncountability of real numbers in a constructive setting.
ihm 11y ago
I would take a look at Andrej Bauer's excellent talk "Stages of Accepting Constructive Mathematics"[0]. Essentially, constructive mathematics is mathematics done without the law of excluded middle ("for all propositions P, either P or not P"). Importantly, it does not necessitate that you deny the law of excluded middle. Intuitionism (or intuitionistic mathematics) is sometimes used to mean the same thing as constructivism and sometimes refers to Brouwer's[1] practice of denying excluded middle by introducing an axiom along the lines of "all functions are computable" or "all functions are continuous" (which from some perspectives is almost the same thing). [0]: https://www.youtube.com/watch?v=zmhd8clDd_Y https://www.youtube.com/watch?v=zmhd8clDd_Y [1]: https://en.wikipedia.org/wiki/L._E._J._Brouwer https://en.wikipedia.org/wiki/L._E._J._Brouwer