can we know whether the self-referential statement: "It's not possible to deduce whether P1 is true or false" is undecidable?

Question

Update: Simple concise version

Thanks to Nick R for pointing in the right direction.

The statement P0: "this statement is false" is undecidable.
The statement P1: "this statement is undecidable" is also undecidable.

P0 can be proved to be undecidable but P1 cannot. How could one categorize these different "levels" of undecidability?

---

Original question

Let's first consider the basic contradictory self-reference:

P0 = "Statement P0 is false"

P0 can't be either true or false without contradiction. This is similar to NaN (Not a Number) in mathematics, only with boolean instead of numeric values. Let's define the truth value of P0 as NaB (Not a Boolean).

The statement in the title:

P1 = "It's not possible to deduce whether P1 is true or false"

is similar in that it's self-referencing but doesn't directly contradict itself. Is the truth value of P1 same as P0, which I defined NaB, or something different? A more complex class of instability?

• If P1 is false, then it should be possible to deduce that. I.e. it must be shown that P1 being true leads to contradiction.
• If P1 is true, then it might very well be, we just don't know it.

Both options are possible - neither one can be ruled out, therefore it's not possible to deduce the truth value of P1.

But that's exactly what P1 says, so we've just proved that it is true! Unlike with P0, even supposing that it's neither true or false makes it back to true. Almost as if it's oscillating between not 2 but 3 values (true, false, neither).

Does this mean that the truth value of P1 is some kind of meta-NaB: "Neither a boolean nor a NaB"?

EDIT: Reworded again for clarification. Question is about P1, not P0. P0 is unrelated only there for the comparison

Answer 1

I'm not an expert in this area, so someone may wish to correct me.

Since you appear to be wishing to look at this formally, let's start with a formal view of the problem.

In a formal setting, a statement P is called not decidable if it is impossible to prove P and it is impossible to prove not(P).

Note that provability is a purely syntactic notion here. On the other hand, truth is a semantic notion, and we say that a statement is true in a formal system if it is provable; in other words, we say a statement is true if it is a theorem.

With this in mind we can restate your statement P1 as :

P1 = The statement P1 is not decidable.

If I am not mistaken, this statement is the computability-theoretic equivalent of the Gödel sentence "This statement is not provable". The Gödel sentence of a formal system is the sentence that Gödel encoded into a statement about sets of natural numbers in order to prove his Incompleteness Theorem. The proof shows that the Gödel sentence is not decidable.

By an analogous proof in computability theory, your statement P1 (in its modified form) is not decidable, meaning there is no algorithm to determine if its either valid or not valid - i.e., either true of false.

If this is correct, then you are correct to call P1 "NaB". However, as I say, I'm not an expert in this area so maybe someone can correct me.

So that would be a formal treatment of the statement P1. If we wish to look at P1 informally, then I believe the usual way of dealing with it is deny that P1 has any meaningful content.

Answer 2

"this statement is false"

This implies two different propositions:

1. This is a statement; and
2. The statement in 1. is false.

But I am not sure 1. is trivial. This is a "statement about statements", or a meta-statement (to be precise, a meta-statement of level 1), so I am not sure it is valid to call it a "statement". If it isn't, then it is false, because 1. above is false.

Of course, one can argue that

"this meta-statement is false"

incurs in the problems you point. But then this is a meta-statement level 2, ie, a meta-statement about a meta-statement, and any attempt at asserting a level for a meta-statement results in a higher level meta-statement; "this level 546 meta-statement is false" is a level 547 meta-statement.