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