0

Would "this sentence is false" make a theory containing it both undecidable & incomplete, while "this sentence is unprovable" make a theory containing it incomplete(syntatically) but not necessarily undecidable(semantic)?

It seems to me that there is no algorithm to decide if the first sentence is true, hence theory is undecidable, and it's not provable, hence the theory is incomplete.

Meanwhile, the truth of the second sentence seems decidable as true, while it can't be provable.

3

No, there is not really a connection here.

You have to be careful: natural-language sentences generally aren't even expressible in a given formal framework, and even when they are they don't necessarily behave as expected.

For example - assuming we're looking at classical first-order logic - the sentence "This statement is false" is never expressible in any good sense; this is due to Tarski, and is essentially an elaboration of the liar paradox.

The sentence "This statement is unprovable" is a more interesting situation. First, we can't really just say "unprovable," we need to talk about unprovability relative to a specific theory; and that theory has to be reasonably nice for provability to be talked about internally. But it gets worse: consider the theory T = PA + "PA is inconsistent." T is consistent, incomplete, and undecidable (a good exercise - remember that PA doesn't prove its own consistency and is essentially incomplete) and yet T proves "For all p, T proves p" and so in particular T proves the statement

"The statement "This statement is T-unprovable" is false."

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.