5 ms·

For any concrete definition of definable reals and any well-order of the reals, I can refer to the first real that’s undefinable in that system.

skissane 2y ago
If we don’t limit ourselves to formal systems, we can speak about definable in natural language. In which case you just uttered a paradox. Now, you can object to “natural language definability” as lacking “concreteness” since maybe it can’t be formalised, but then the claim in your comment can’t be formalised either… Actually, are we sure natural language can’t be formalised? Obviously any formalisation of natural language has to be paraconsistent (maybe even dialetheic) rather than consistent, but granted that…
- dullcrisp 2y ago
  I think you’re right, which I guess might prove that it’s impossible to refer to a well-ordering of the real numbers. I guess that’s what they mean when they say non-constructible, huh? But still my intuition is that for any consistent formal system I should be able to find a more powerful system that can express strictly more things, even if my argument above was silly. But I don’t think we can talk about the set of things that can be defined in natural language in any meaningful way.
  - chriswarbo 2y ago
    > But still my intuition is that for any consistent formal system I should be able to find a more powerful system that can express strictly more things The problem with defining more and more powerful systems is that we have an arbitrary selection of axioms to choose from. For example, if we start with the Peano axioms and define a Goedel sentence (i.e. a specific instance of "this sentence cannot be proven"), then we can choose to extend that system either by adding that sentence as an axiom, or adding its negation as an axiom. Both would result in a consistent system. Then we can define a Goedel sentence in that system, and make a more powerful system by making that or its negation an axiom. And so on. This process of choosing new axioms does make our formal system strictly more powerful (it can prove/refute sentences which were unprovable in the weaker systems, and their consequences); but it's not very useful or interesting, since we're just arbitrarily choosing whether those extra sentences should be provable or not. This is related to the fact that any particular formal system can only compute a few digits of Chaitin's constant (since we can only ever solve the halting problem for a subset of all possible programs). We can consistently extend our chosen system by specifying subsequent digits as axioms, but that doesn't really tell us anything; we're just asserting it, for no particular reason one way or another.
    - dullcrisp 2y ago
      But doesn’t that still call into question the notion of “definability” as a property of a number? If I invent an axiomatic system called “ZFC + Chaitin's constant is c” does that make Chaitin’s constant any more definable than it was before?
      - chriswarbo 2y ago
        Hmm, that's a good question. My first thought is that, if a number has some representation, then we can always define a Turing machine which outputs that number; by doing the equivalent of a hard-coded 'print "..."' statement. However, such machines may require an infinite transition table; so the computable numbers are those which are finitely representable; which limits us to those whose digits follow some sort of algorithm. Relating that to "definable" numbers, it seems I've probably missed some subtlety with Chaitin's constant: since (a) defining extra digits via axioms seems to be adding (algorithmic) information to our system, so defining all of its digits seems to give infinite information; yet (b) it's trivial to do this in a finite way, like "all subsequent digits are zero". Maybe I'll think about this more, but it seems like my intuition is a bit off (this area of mathematics is notoriously nuanced).
EGreg 2y ago
Have you heard of https://en.wikipedia.org/wiki/Berry_paradox https://en.wikipedia.org/wiki/Berry_paradox ? It seems to run into the same sort of thing that led to ZF axioms, namely that you can have a language that is a bit too "loose" and therefore leads to contradictions. I think Kurt Godel showed that any non-trivial language is going to have something like that.
- dullcrisp 2y ago
  Thanks, I have now!
Dylan16807 2y ago
Can you coherently refer to the "first" real outside some set, just in general? Like, what is the first positive real? If you have to involve infinitesimals or something, I think it's perfectly fine for you to be able to take the definable reals and then extend them in that way. it doesn't invalidate the idea of a "definable" real.
- deleted 2y ago
  [deleted]
- zeroonetwothree 2y ago
  See the “well ordering theorem”.
  - Dylan16807 2y ago
    Okay, I hadn't really picked up on the implications of well-ordering there. Though the (im)possibility of well-ordering all reals doesn't really matter here. Computable reals can by sorted by their programs, and definable reals can be sorted by their definitions. So if you have a "concrete definition of definable reals", then the system you use gives you ways to well-order them. And if you want to "refer to the first real that’s undefinable in that system", you can make a new system2 that encapsulates the old system1. That might prove we can't have a universal system for defining things, which would be disappointing but workable. Or maybe it's just that "the first real that's undefinable in system1" is not concrete, so we can reject it as a description of a number, and then the consequences are much smaller.
  - skissane 2y ago
    Which is equivalent to the axiom of choice. If one chooses not to accept that axiom, then the well-ordering theorem is not a theorem. One can even (consistently) append the negation of the axiom of choice to ZF, in which case this theorem is false. Mere negation of the axiom of choice is not a very interesting addition, but there are some interesting alternative axioms, such as the axiom of determinacy, which have negation of the axiom of choice as a consequence People who are fixated on definable/computable reals generally have constructivist sympathies, and many (but not all) constructivist mathematicians reject the axiom of choice. So relying on it in arguments in this context is questionable. https://mathoverflow.net/questions/119561/mathematics-with-the-negation-of-ac https://mathoverflow.net/questions/119561/mathematics-with-t...
Someone 2y ago
Can you? There’s no “first real larger than 2”, for example, so if I define the definable reals as {0, 1, 2}, what is that first real? In general, you also can’t use Cantor’s diagonal argument on the list of definable reals because there are numbers in there that aren’t computable.
- zeroonetwothree 2y ago
  See the “well ordering theorem”.

skissane 2y ago

If we don’t limit ourselves to formal systems, we can speak about definable in natural language. In which case you just uttered a paradox. Now, you can object to “natural language definability” as lacking “concreteness” since maybe it can’t be formalised, but then the claim in your comment can’t be formalised either… Actually, are we sure natural language can’t be formalised? Obviously any formalisation of natural language has to be paraconsistent (maybe even dialetheic) rather than consistent, but granted that…

dullcrisp 2y ago
I think you’re right, which I guess might prove that it’s impossible to refer to a well-ordering of the real numbers. I guess that’s what they mean when they say non-constructible, huh? But still my intuition is that for any consistent formal system I should be able to find a more powerful system that can express strictly more things, even if my argument above was silly. But I don’t think we can talk about the set of things that can be defined in natural language in any meaningful way.
- chriswarbo 2y ago
  > But still my intuition is that for any consistent formal system I should be able to find a more powerful system that can express strictly more things The problem with defining more and more powerful systems is that we have an arbitrary selection of axioms to choose from. For example, if we start with the Peano axioms and define a Goedel sentence (i.e. a specific instance of "this sentence cannot be proven"), then we can choose to extend that system either by adding that sentence as an axiom, or adding its negation as an axiom. Both would result in a consistent system. Then we can define a Goedel sentence in that system, and make a more powerful system by making that or its negation an axiom. And so on. This process of choosing new axioms does make our formal system strictly more powerful (it can prove/refute sentences which were unprovable in the weaker systems, and their consequences); but it's not very useful or interesting, since we're just arbitrarily choosing whether those extra sentences should be provable or not. This is related to the fact that any particular formal system can only compute a few digits of Chaitin's constant (since we can only ever solve the halting problem for a subset of all possible programs). We can consistently extend our chosen system by specifying subsequent digits as axioms, but that doesn't really tell us anything; we're just asserting it, for no particular reason one way or another.
  - dullcrisp 2y ago
    But doesn’t that still call into question the notion of “definability” as a property of a number? If I invent an axiomatic system called “ZFC + Chaitin's constant is c” does that make Chaitin’s constant any more definable than it was before?
    - chriswarbo 2y ago
      Hmm, that's a good question. My first thought is that, if a number has some representation, then we can always define a Turing machine which outputs that number; by doing the equivalent of a hard-coded 'print "..."' statement. However, such machines may require an infinite transition table; so the computable numbers are those which are finitely representable; which limits us to those whose digits follow some sort of algorithm. Relating that to "definable" numbers, it seems I've probably missed some subtlety with Chaitin's constant: since (a) defining extra digits via axioms seems to be adding (algorithmic) information to our system, so defining all of its digits seems to give infinite information; yet (b) it's trivial to do this in a finite way, like "all subsequent digits are zero". Maybe I'll think about this more, but it seems like my intuition is a bit off (this area of mathematics is notoriously nuanced).

EGreg 2y ago

Have you heard of https://en.wikipedia.org/wiki/Berry_paradox https://en.wikipedia.org/wiki/Berry_paradox ? It seems to run into the same sort of thing that led to ZF axioms, namely that you can have a language that is a bit too "loose" and therefore leads to contradictions. I think Kurt Godel showed that any non-trivial language is going to have something like that.

dullcrisp 2y ago
Thanks, I have now!

Dylan16807 2y ago

Can you coherently refer to the "first" real outside some set, just in general? Like, what is the first positive real? If you have to involve infinitesimals or something, I think it's perfectly fine for you to be able to take the definable reals and then extend them in that way. it doesn't invalidate the idea of a "definable" real.

deleted 2y ago
[deleted]
zeroonetwothree 2y ago
See the “well ordering theorem”.
- Dylan16807 2y ago
  Okay, I hadn't really picked up on the implications of well-ordering there. Though the (im)possibility of well-ordering all reals doesn't really matter here. Computable reals can by sorted by their programs, and definable reals can be sorted by their definitions. So if you have a "concrete definition of definable reals", then the system you use gives you ways to well-order them. And if you want to "refer to the first real that’s undefinable in that system", you can make a new system2 that encapsulates the old system1. That might prove we can't have a universal system for defining things, which would be disappointing but workable. Or maybe it's just that "the first real that's undefinable in system1" is not concrete, so we can reject it as a description of a number, and then the consequences are much smaller.
- skissane 2y ago
  Which is equivalent to the axiom of choice. If one chooses not to accept that axiom, then the well-ordering theorem is not a theorem. One can even (consistently) append the negation of the axiom of choice to ZF, in which case this theorem is false. Mere negation of the axiom of choice is not a very interesting addition, but there are some interesting alternative axioms, such as the axiom of determinacy, which have negation of the axiom of choice as a consequence People who are fixated on definable/computable reals generally have constructivist sympathies, and many (but not all) constructivist mathematicians reject the axiom of choice. So relying on it in arguments in this context is questionable. https://mathoverflow.net/questions/119561/mathematics-with-the-negation-of-ac https://mathoverflow.net/questions/119561/mathematics-with-t...

Someone 2y ago

Can you? There’s no “first real larger than 2”, for example, so if I define the definable reals as {0, 1, 2}, what is that first real? In general, you also can’t use Cantor’s diagonal argument on the list of definable reals because there are numbers in there that aren’t computable.

zeroonetwothree 2y ago
See the “well ordering theorem”.