4 ms·

> One annoying thing about both the Collatz and Goldbach conjectures is that if they are unprovable, it's also impossible to prove they're unprovable (unless ma

> One annoying thing about both the Collatz and Goldbach conjectures is that if they are unprovable, it's also impossible to prove they're unprovable (unless math is inconsistent). This has been proved! So is there a countable order of metaprovability? i.e. are there problems that if they're impossible to prove, it's impossible to prove whether it's possible to prove whether they're unprovable, but _that_ can be proven? Or does that mean the same thing? What does it mean if that goes infinitely deep? That we'll never know anything about a problem in that set unless we prove it? I guess it's not possible to prove that a problem is in that set, right? Is it possible to prove that problems do exist in that set at all? edit: (non-vacuously. Provable problems are obviously vacuously in all the sets). edit2: oh I see now (I think). Above I'd need an "AND if you can't prove it undecideable ... then you can't prove its undecidability's decideability either, and that can be proved" So basically each level needs to be conditioned on all 0..n-2 levels not holding, then you can prove level n-1 is undecideable. level 0: provable level 1: provably undecideable level 2: if not provable (can't prove level 0) then can't prove undecideable. (Goldbach, Collatz) level 3: if it's not in level 0 or 1, then can't prove level 2. level 4: if it's not in levels 0, 1, or 2, then can't prove level 3. ... Which means there's no level infinity, since there's no level infinity minus 1 to talk about so it's meaningless. Correct?

deleted 3y ago
[deleted]
hansvm 3y ago
A couple of things: > level 2: if not provable (can't prove level 0) then can't prove undecideable. (Goldbach, Collatz) If you're operating in the ordinary naturals, neither Goldbach nor Collatz are undecidable. The statements are either true or false. The question at hand is whether we can generate a finite proof of that fact in a given axiomatic system. The quote at hand simply said that if no such proof exists (obviously implying the statements are true because otherwise a simple finite proof would be a counter-example) then similarly no finite proof of that lack of existence exists either. They might be undecidable in other arithmetic systems (implying that some models of those systems would have the statements be true and some would have them be false), but not for the naturals. > Which means there's no level infinity, since there's no level infinity minus 1 to talk about so it's meaningless. Correct? When you're making up a new definition, you care about (1) is it coherent (don't want to be like the proverbial Ph.D. who made up an exciting mathematical object and studied it for years before finding out no such objects could exist), (2) what can you deduce about that object, and (3) is it "useful" (for some broad definition thereof). The question of "meaningfulness" can lead you down incorrect paths because it merges (2) and (3). The definition you picked for the broad concept you have in your mind has no level "infinity" because you snuck the naturals into the definition as the indexing set (defined using the successor function). If we strictly look at point (2), yes, there's no "infinity". The general concept you're looking at though might more naturally fit in a world where there are infinities (i.e., let's look at point (3) a bit more). As a rule of thumb, if you're looking at a set of things indexed by the naturals, especially if they have a successor function, especially if they're defined inductively, especially if their interesting properties are defined in terms of all previous items, it's natural to take a look at indexing via the ordinals and trying to define them via transfinite induction. For this particular set of things, that may or may not be straightforward. The notions of unprovability, undecidability, ... are a bit intricate, and you need to define them with respect to the system being studied and the system being used to study them. Right now, your inductive definition _seems_ to also require a predecessor function (which, if intrinsic to the property being analyzed would preclude many attempts to wrangle in some infinities), but I wouldn't be surprised if a careful re-writing found that to be an extraneous detail, in which case you could add in a limiting case (defining f(w) in terms of f(n) for all n<w for all limit ordinals w).
- daxfohl 3y ago
  Fwiw I'm going back to my original hypothesis and saying there's no limit at infinity, but there is a class of questions that are in none of the levels, essentially meaning you can't prove anything about their solvability. It's impossible to prove that any particular question is in that class, by definition, but it may be possible to prove that there exist questions that are. Which opens the philosophical question of why so many questions aren't.

deleted 3y ago

[deleted]

hansvm 3y ago

A couple of things: > level 2: if not provable (can't prove level 0) then can't prove undecideable. (Goldbach, Collatz) If you're operating in the ordinary naturals, neither Goldbach nor Collatz are undecidable. The statements are either true or false. The question at hand is whether we can generate a finite proof of that fact in a given axiomatic system. The quote at hand simply said that if no such proof exists (obviously implying the statements are true because otherwise a simple finite proof would be a counter-example) then similarly no finite proof of that lack of existence exists either. They might be undecidable in other arithmetic systems (implying that some models of those systems would have the statements be true and some would have them be false), but not for the naturals. > Which means there's no level infinity, since there's no level infinity minus 1 to talk about so it's meaningless. Correct? When you're making up a new definition, you care about (1) is it coherent (don't want to be like the proverbial Ph.D. who made up an exciting mathematical object and studied it for years before finding out no such objects could exist), (2) what can you deduce about that object, and (3) is it "useful" (for some broad definition thereof). The question of "meaningfulness" can lead you down incorrect paths because it merges (2) and (3). The definition you picked for the broad concept you have in your mind has no level "infinity" because you snuck the naturals into the definition as the indexing set (defined using the successor function). If we strictly look at point (2), yes, there's no "infinity". The general concept you're looking at though might more naturally fit in a world where there are infinities (i.e., let's look at point (3) a bit more). As a rule of thumb, if you're looking at a set of things indexed by the naturals, especially if they have a successor function, especially if they're defined inductively, especially if their interesting properties are defined in terms of all previous items, it's natural to take a look at indexing via the ordinals and trying to define them via transfinite induction. For this particular set of things, that may or may not be straightforward. The notions of unprovability, undecidability, ... are a bit intricate, and you need to define them with respect to the system being studied and the system being used to study them. Right now, your inductive definition _seems_ to also require a predecessor function (which, if intrinsic to the property being analyzed would preclude many attempts to wrangle in some infinities), but I wouldn't be surprised if a careful re-writing found that to be an extraneous detail, in which case you could add in a limiting case (defining f(w) in terms of f(n) for all n<w for all limit ordinals w).

daxfohl 3y ago
Fwiw I'm going back to my original hypothesis and saying there's no limit at infinity, but there is a class of questions that are in none of the levels, essentially meaning you can't prove anything about their solvability. It's impossible to prove that any particular question is in that class, by definition, but it may be possible to prove that there exist questions that are. Which opens the philosophical question of why so many questions aren't.