It has been pointed out in the comments that there is a major flaw in this answer, as it was intended to outline a proof in less than formal terms, but in doing so missed a point of significant importance. Though the work below follows from the four axioms I posit below, there is no evident way to formalize a notion of provability that satisfies the axioms below. This should trouble us, because having "provability" just be a word not corresponding to any formal notion is problematic.
The comments contain further discussion and this answer contains a formal treatment of the question.
First, let's examine what it would mean for a problem to be 2-fold unprovable. By your notation, call a problem n-fold unprovable if there is no proof that the problem is (n-1)-fold unprovable or not (where 0-fold unprovable is taken to mean "provable"). Here, a statement which is 1-fold unprovable is one which is independent of a system.
We take "provable" to mean "there is a proof or disproof of $P$".
(A) If $P$ is provable then "$P$ is provable" is provable.
This seems clear, since, knowing that a proof of $P$ exists, we can certainly find it by enumerating all the proofs (if the axioms are recursively enumerable), and thus prove that $P$ is provable.
(B) $P$ is provable if and only if $\neg P$ is provable.
Clearly, if a proof or disproof of $P$ exists, we can easily disprove or prove $\neg P$.
(C) If $P$ is provable and $P\rightarrow Q$ is provable, then $Q$ is provable.
Which is clear, given how proofs are constructed. We also need
(D) If $P$ is provably true, then $P$ is true.
From here, we can argue:
- If $P$ is provable, then "$P$ is provable" is provable (from (A)).
- If "$P$ is provable" is unprovable, then $P$ is unprovable (contrapositive of (1)).
- If "$P$ is unprovable" is unprovable, then "$P$ is provable" is unprovable (from (B)).
- If "$P$ is unprovable" is unprovable, then $P$ is unprovable (syllogism of (3) and (2))
Which is clearly a problem, since we can quickly reach a contradiction if we take
- ""$P$ is unprovable" is unprovable" is provably true.
- "$P$ is unprovable" is unprovable. (from (D))
- "$P$ is unprovable" is provable (from 5, 4, and (C), noting that 4 is provable since we just proved it).
- "$P$ is unprovable" is provable and "$P$ is unprovable" is unprovable (6 and 7)
A contradiction. As we accept A, B, and C, it must be that the given (5) implies a contradiction and is thus false, meaning that one can never prove that $P$ is 2-fold unprovable - thus if a statement is 2-fold unprovable, it is also 3-fold unprovable, since no proof that it is 2-fold unprovable could exist. Indeed, every higher ordinal befalls the same argument.
So, we might consider that there are potentially 4 classes of statements:
- Those with a proof
- Those with a disproof
- Those that can be proved to have neither proof nor disproof.
- Those of which nothing can be said. (i.e. 2-fold unprovable ones, but nothing can be said, because any proof that a statement belongs to this class is inconsistent by above argument)
The problem is that we can never actually choose an example of a statement in some formal system and show, using that same system, that a statement is in the last class. Using a similar statement to Godel - though not providing any construction thereof, and assuming that a similar construction to Godel's would suffice - one might question that statement
This statement is unprovable or false.
It could not be proven false (as it is true if there is a proof that it is false), nor proven true (as it asserts no such proof exists), nor proven independent (as that would prove the statement as well), nor proven 2-fold independent (as such a proof would show it to be independent). This is paradoxical, but demonstrates that there must be some statements which cannot be demonstrated to be in any class - implying that there are 2-fold unprovable statements.
A more concrete, but perhaps less satisfying, proof that statements of the fourth class exist if we consider turing machines. Consider that, if a turing machine halts, we can prove that it halts - we just run it and, at the end, observe that it halted. The converse is that, if there is no proof of whether turing machine halts, then it must not halt - meaning that, similarly to before, if there is a proof that there is no proof that a turing machine halts, we can prove that the machine does not halt. Thus, one can never prove that "T halts" is unprovable*.
Now, if we assume that the theory we are talking about satisfies the constraints of Godel's theorem. The constraints can be expressed as "The axiomatic system can simulate Turing machines and Turing machines can enumerate the axioms". So, that means, for any machine $T$, we could create a machine which enumerates every theorem of a system and looks for a proof of "$T$ halts" or "$T$ doesn't halt" - and, if our system always proves "true" or "false" (since, "undecidable" was ruled out in the previous paragraph), it would be guaranteed to eventually find one. This would implies the halting problem is decidable. It is not. Ergo, some statements cannot be proven to be true, false, or undecidable.
These proofs work intuitively; there are formal systems that defy them (for instance, every statement in the theory of true arithmetic is either true or false - but it has infinitely many axioms). This is hard to avoid since "unprovability" is, of course, relative to a given formal system, and it is possible "P is unprovable is unprovable in system A" is a theorem of a different system B. However, any system that satisfies the conditions of Godel's proof will, in itself, have 2-fold unprovable statements, and these statements will also be 3-fold unprovable and so on.
* Other statements, like the Goldbach conjecture, would work similarly: If they are false, there would be a counterexample, and we could use this to disprove the conjecture. This does, paradoxically, mean that if no proof or disproof of it exists in a system which models it, then it is true. However, this does not mean that it must be possible to prove or disprove it - it could be unprovable. It's just that we could never prove that it is unprovable within that same system, because that's equivalent to showing no counterexamples. Indeed, if it is unprovable, then it is 2-fold unprovable, 3-fold unprovable and so on- absolutely nothing might be said of it.