4 ms·

Has anyone done work on finding undecidable math beyond self-referential statements? Meaning: beyond variations of "who shaves the barber," do we have a sense t

Has anyone done work on finding undecidable math beyond self-referential statements? Meaning: beyond variations of "who shaves the barber," do we have a sense that the undecidable statements are all pathologically long, or are there (we think) undecidable statements a human can comprehend that are undecidable that don't rely on self-reference?

wardedVibe 3y ago
So the most physically grounded example I know of is the undecidability of some spectral gaps[0] (is there a discrete jump between the ground state and the excited states), which as far as I can tell doesn't rely on self-reference. [0]: https://arxiv.org/pdf/1502.04573.pdf https://arxiv.org/pdf/1502.04573.pdf
- calf 3y ago
  Apparently it does? Check this old comment from Scott Aaronson: > Rahul #97: No, because the other point is that whether a spectral gap goes to zero as the lattice size goes to infinity is the kind of thing that real condensed-matter physicists and quantum field theorists ask all the time. It’s something they accept every day as a good mathematical idealization for what they care about. So it’s worthwhile to know that their problem secretly contains the halting problem—that for large enough constant d, there can never be a clean algorithmic criterion to tell you which nearest-neighbor qudit Hamiltonians are gapped and which are gapless. https://scottaaronson.blog/?p=2586#comment-975416 https://scottaaronson.blog/?p=2586#comment-975416 If I read this he's clearly implying the spectral gaps problem is done by reduction to the halting problem. (Edit, in the blog entry he explains: "Cubitt et al.’s theorem now says the following: for some fixed, constant local dimension d, there is no algorithm that takes as input the local Hamiltonian h (say, as a d2×d2 matrix of algebraic numbers), and that decides whether the material is gapped or gapless. Indeed, you can reduce the halting problem to that problem, in such a way that the material will be gapped if your Turing machine halts, or gapless if it runs forever.")
gsinclair 3y ago
I believe the continuum hypothesis is an example of an undecidable statement. That is, we know that the integers have cardinality of “aleph null”, the smallest infinity. And we know how to construct the “next” level of infinity using something analogous to power sets. Call this “aleph one”. Now the hypothesis: the cardinality of the real numbers is equal to aleph one. It is known that we can never prove that hypothesis one way or the other. The US mathematician Paul Cohen established this in the 1960s. There are probably egregious errors in my telling of this, but it could be a prompt for further reading.
Tainnor 3y ago
Gödel's first incompleteness theorem just guarantees that for every system of axioms that is computable and "strong enough", an undecidable sentence exists. For systems we actually use, such as ZFC or PA, we know a number of actually "meaningful" examples such as the Continuum Hypothesis, which is independent of ZFC. But of course, you can always just add this hypothesis (or its negation) as an axiom. Gödel's theorem has to rely on self-reference because we can't really give a "natural" example when we're not actually looking at a specific system, but trying to say something about all possible systems.
janejeon 3y ago
I think for mathematics a good suspect is probably the Riemann hypothesis, which many other results rely on. We don't know that it's "undecidable", but from what I've read it's probably true and (even more interestingly), we can derive meaningful results from it being "probably"/"mostly" true (e.g. "for 99>% of cases it is true"), even without knowing that it is 100% decideably true. Super fun stuff, though I'm not going to pretend I understand all of this (I mostly just gleam this stuff from what mathematicians say on Numberphile channel).
empath-nirvana 3y ago
In a sense _all_ of the axioms of a given system are undecidable. They're just given, and they're relatively arbitrarily chosen. You can create, for example a version of set theory where the starting axioms are different from ZFC (the "standard" set theory) and you can derive some of the axioms of ZFC from them. What Godel proved is that no matter what set of axioms you choose, as long as it's sufficient for expressing basic arithmetic, you can produce still produce new undecidable statements, or there will be true statements that you can't prove with it.
lanstin 3y ago
As the article mentions, the generalized continuum hypothesis has been proven to be undecidable in ZFC, and I believe specific Diophantine equations have been proven to be undecidable. Axiom of Choice of course is undecidable from the other ZF axioms/axiom schemas. Answering questions about a presentation of a group is provably undecidable in general but since it is a kind of halting problem that makes sense.
cyborgx7 3y ago
Here is the thing with that. Technically every individual instance of a problem is decidable. It's only in the universal case that they become undecidable. Take the halting problem for example. Imagine two algorithms for determining if a program halts. One always returns true, the other always returns false. For every single program, one of them will be the correct solver, but clearly neither of them is the correct solver for every single program. Therefore the counter-example necessarily has to depend on the specific details of the algorithm that claims to be the universal halting decider. Strictly speaking, there isn't an universal counter-example, since it changes depending on what the algorithm is. There are just instructions on how you can always make one, no matter what the algorithm is.
cubefox 3y ago
Here is an overview: https://plato.stanford.edu/entries/goedel-incompleteness/#ConCasUnpSta https://plato.stanford.edu/entries/goedel-incompleteness/#Co... It ends with an interesting point about the continuum hypothesis: > Sometimes Paul Cohen’s celebrated result that the Continuum Hypothesis (CH) is independent of ZFC (Cohen 1963, 1964; see the entry on independence and large cardinals). However, this case is very different. In all the above independence results the relevant statements are still theorems of mathematics, taken as shown to be true (the last case, which requires large cardinal axioms that go beyond ZFC, is more controversial; still, at least many set-theoreticians find such axioms plausible). And with the first incompleteness theorem itself, the truth of the unprovable statement easily follows, given that the assumption of the consistency of the system is indeed correct. However, in the case of Cohen’s result, there is absolutely no indication whether CH should be considered true, false, or perhaps lacking a truth-value.

wardedVibe 3y ago

So the most physically grounded example I know of is the undecidability of some spectral gaps[0] (is there a discrete jump between the ground state and the excited states), which as far as I can tell doesn't rely on self-reference. [0]: https://arxiv.org/pdf/1502.04573.pdf https://arxiv.org/pdf/1502.04573.pdf

calf 3y ago
Apparently it does? Check this old comment from Scott Aaronson: > Rahul #97: No, because the other point is that whether a spectral gap goes to zero as the lattice size goes to infinity is the kind of thing that real condensed-matter physicists and quantum field theorists ask all the time. It’s something they accept every day as a good mathematical idealization for what they care about. So it’s worthwhile to know that their problem secretly contains the halting problem—that for large enough constant d, there can never be a clean algorithmic criterion to tell you which nearest-neighbor qudit Hamiltonians are gapped and which are gapless. https://scottaaronson.blog/?p=2586#comment-975416 https://scottaaronson.blog/?p=2586#comment-975416 If I read this he's clearly implying the spectral gaps problem is done by reduction to the halting problem. (Edit, in the blog entry he explains: "Cubitt et al.’s theorem now says the following: for some fixed, constant local dimension d, there is no algorithm that takes as input the local Hamiltonian h (say, as a d2×d2 matrix of algebraic numbers), and that decides whether the material is gapped or gapless. Indeed, you can reduce the halting problem to that problem, in such a way that the material will be gapped if your Turing machine halts, or gapless if it runs forever.")

gsinclair 3y ago

I believe the continuum hypothesis is an example of an undecidable statement. That is, we know that the integers have cardinality of “aleph null”, the smallest infinity. And we know how to construct the “next” level of infinity using something analogous to power sets. Call this “aleph one”. Now the hypothesis: the cardinality of the real numbers is equal to aleph one. It is known that we can never prove that hypothesis one way or the other. The US mathematician Paul Cohen established this in the 1960s. There are probably egregious errors in my telling of this, but it could be a prompt for further reading.

Tainnor 3y ago

Gödel's first incompleteness theorem just guarantees that for every system of axioms that is computable and "strong enough", an undecidable sentence exists. For systems we actually use, such as ZFC or PA, we know a number of actually "meaningful" examples such as the Continuum Hypothesis, which is independent of ZFC. But of course, you can always just add this hypothesis (or its negation) as an axiom. Gödel's theorem has to rely on self-reference because we can't really give a "natural" example when we're not actually looking at a specific system, but trying to say something about all possible systems.

janejeon 3y ago

I think for mathematics a good suspect is probably the Riemann hypothesis, which many other results rely on. We don't know that it's "undecidable", but from what I've read it's probably true and (even more interestingly), we can derive meaningful results from it being "probably"/"mostly" true (e.g. "for 99>% of cases it is true"), even without knowing that it is 100% decideably true. Super fun stuff, though I'm not going to pretend I understand all of this (I mostly just gleam this stuff from what mathematicians say on Numberphile channel).

empath-nirvana 3y ago

In a sense _all_ of the axioms of a given system are undecidable. They're just given, and they're relatively arbitrarily chosen. You can create, for example a version of set theory where the starting axioms are different from ZFC (the "standard" set theory) and you can derive some of the axioms of ZFC from them. What Godel proved is that no matter what set of axioms you choose, as long as it's sufficient for expressing basic arithmetic, you can produce still produce new undecidable statements, or there will be true statements that you can't prove with it.

lanstin 3y ago

As the article mentions, the generalized continuum hypothesis has been proven to be undecidable in ZFC, and I believe specific Diophantine equations have been proven to be undecidable. Axiom of Choice of course is undecidable from the other ZF axioms/axiom schemas. Answering questions about a presentation of a group is provably undecidable in general but since it is a kind of halting problem that makes sense.

cyborgx7 3y ago

Here is the thing with that. Technically every individual instance of a problem is decidable. It's only in the universal case that they become undecidable. Take the halting problem for example. Imagine two algorithms for determining if a program halts. One always returns true, the other always returns false. For every single program, one of them will be the correct solver, but clearly neither of them is the correct solver for every single program. Therefore the counter-example necessarily has to depend on the specific details of the algorithm that claims to be the universal halting decider. Strictly speaking, there isn't an universal counter-example, since it changes depending on what the algorithm is. There are just instructions on how you can always make one, no matter what the algorithm is.

cubefox 3y ago

Here is an overview: https://plato.stanford.edu/entries/goedel-incompleteness/#ConCasUnpSta https://plato.stanford.edu/entries/goedel-incompleteness/#Co... It ends with an interesting point about the continuum hypothesis: > Sometimes Paul Cohen’s celebrated result that the Continuum Hypothesis (CH) is independent of ZFC (Cohen 1963, 1964; see the entry on independence and large cardinals). However, this case is very different. In all the above independence results the relevant statements are still theorems of mathematics, taken as shown to be true (the last case, which requires large cardinal axioms that go beyond ZFC, is more controversial; still, at least many set-theoreticians find such axioms plausible). And with the first incompleteness theorem itself, the truth of the unprovable statement easily follows, given that the assumption of the consistency of the system is indeed correct. However, in the case of Cohen’s result, there is absolutely no indication whether CH should be considered true, false, or perhaps lacking a truth-value.