2 ms·

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

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

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