# 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

• Some (although very few!) people accept, that the statement "This statement is false" is true and false. Even more people (but still few!) think, that you cannot or should not assign single truth values to all propositions (in particular: constructive logic cannot be formalized with a finite set of truth values) Jul 1 '16 at 13:53
• @virmaior OK, removed that part as it's not relevant to the question. Jul 1 '16 at 14:02
• Provability and truth are not the same thing. The statement can be true and unprovable. Nothing wrong with that. (That's regarding your "if it's false then it should be possible to prove it.") Jul 1 '16 at 14:07
• On what basis, do you state It can't be either true or false. The idea that it must be true or false is a key feature of the bivalency that defines most forms of logic. Again, as with my previous comment, the main question is going to be the order of evaluation for determining whether it's true or false. Jul 1 '16 at 14:09
• You can see Liar Paradox and Self-Reference for discussion and approaches with three-valued logic, where a self-referential sentence receives the value undefined. Jul 1 '16 at 14:17

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.

• This is certainly a better formulation and Gödel's sentence is closely related. StilI hesitant to accept. I updated the question with a more to-the-point summary. Jul 2 '16 at 9:06
• You correctly make a distinction between provability as a syntactic notion and truth as a semantic notion. But then you go on to say that a statement is true if it is provable. Do you mean that as a result of the soundness theorem, or as a matter of definition? The converse of course does not always hold (i.e. some true statements are not provable). Jul 2 '16 at 11:18
• So, P1 is not decidable. But P1 states that P1 is not decidable, so P1 is true. Can a statemente be both undecidable and true? Jul 2 '16 at 12:13
• @EliranH According to my “wafer-thin” understanding of the subject, we say that a statement is true with respect to the theory if it is provable - i.e., the true statements of a theory are precisely the theorems of the theory. Perhaps I should have used the word valid rather than true. The unprovable truths identified by Godel’s theorem are not theorems so they are not truths with respect to the theory. (Continued....)
– nwr
Jul 2 '16 at 16:37
• (... continued) I would say that describing unprovable truths as true would require extending the semantic component of the theory beyond the theory itself to include “meta-theory” arguments. I am probably wrong here. I’m not sure what you mean by the “Soundness Theorem”. I believe a theory is sound if its theorems are valid/true with respect to its semantics, and indeed all interpretations of the semantics of the theory. (I lifted that last bit - “all interpretations...” - from wiki, in case you couldn’t tell.) It’s a fascinating subject and some day I hope to better understand it.
– nwr
Jul 2 '16 at 16:37

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

• Please see the clarified question. I don't think it's a "statement about statements", but rather "statement about logic regarding statements" Jul 1 '16 at 17:48
• P1 is a statement abou P0. If P0 is a meta-statement, and meta-statements are not statements, then P0 is false, and so is P1, because it asserts it is impossible to deduce whether P0 is true or false, and P0 is false. Jul 1 '16 at 18:15
• P1 only references P1 itself. P0 is separate, only mentioned in the same post for comparison. Jul 1 '16 at 19:17
• Ah, yes. Sorry, I misunderstood P1. Jul 1 '16 at 19:58