Undecidability of predicate logic: schemas/formulas which are neither valid nor invalid

Question

It has been shown that the set of valid argument schemas of predicate logic is effectively numerable, while the set of its invalid schemas is not. From this follows that the set of valid schemas of predicate logic is not decidable.

Question 1: But how can it be that the set of valid schemas is effectively numerable without the set of invalid schemas being effectively numerable too? Is that because there are schemas which are neither valid nor invalid? If yes, could you provide some examples?

Question 2: Also, does saying that the set of valid schemas of predicate logic is undecidable amount to say that the set of valid formulas of predicate logic is undecidable?

Answer 1

First, some clarification about your use of the phrase 'valid (or invalid) schema': as you can read in Noah's answer, there is some ambiguity surrounding 'invalid', but there is also some ambiguity regarding 'schema'. That is, 'schema' is often used to capture an inference 'pattern', such as Modus Ponens. As such, one schema could represent an infinite number of actual inferences. And here are some examples of invalid schemas:

"Modus moron" rule of inference?

As logicians, we have only identified a limited number of these schemas ... meaning that if we stick to those schemas we have identified, it is decidable whether they are valid or invalid. I know that this is not what you mean, but it's just that 'schema' can give people the wrong idea.

So, I assume that by 'valid schema' you simply mean that we are dealing with a set of sentences $\Gamma$ and a sentence $\phi$ such that $\Gamma \vDash \phi$, and that by 'valid formula' you mean any sentence $\phi$ such that $\vDash \phi$.

Question 1: The fact that the set of valid schemas is effectively enumerable is the same as saying that there is an effective procedure, or algorithm, or computer program that, when given a valid schema, will eventually declare it to be valid, but when given an invalid schema, it will not declare it to be invalid.

However, not declaring something to be invalid is not the same as declaring it to be invalid ... True: if the program says "Yes, it's valid" for every valid schema, then any time the program comes back with something other than that (whether that's "No, it's invalid", or "Bananas!"), you know that you are dealing with an invalid schema .... but another possibility is for it to go into an infinite loop for some of those, in which case it doesn't declare anything at all.

Indeed, given that validity for first-order logic is undecidable, we know that such any algorithm that is complete for the valid schemas, has to go into an infinite loop for some of the invalid schemas ... Otherwise first-order logic would be decidable. As such, the algorithm can be said to 'semi-decide' validity of logical inferences. Or: while logical inference is not decidable, it is semi-decidable.

Question 2: Yes. Proof by contradiction. Suppose we could decide on the validity of first-order logic formulas. Then we could decide on the validity of $\Gamma \vDash \phi$ as well: simply conjunct all the statements of $\Gamma$ together into one big statement $\Delta$, and then decide whether $\Delta \rightarrow \phi$ is valid. Clearly, $\Gamma \vDash \phi$ if and only if $\vDash \Delta \rightarrow \phi$. But, we already know we can't decide the valid schemas. So, we can't decide the valid formulas either.

Of course, the set of valid formulas is recursively enumerable, and there we use a reduction the other way: given any formula $\phi$, we give the set of statements $\Gamma = \{ \}$ as well as $\phi$ to the algorithm that semi-decides the validity of logical inference: we know that for any $\vDash \phi$ it will come back and declare that $\{ \} \vDash \phi$. So: validity of formulas is semi-decidable as well.

Answer 2

I think you might be getting tripped up by the word "invalid," which has two reasonable meanings in this context:

• "has no models," and

• "is not valid."

If we use the first meaning, then the invalid sentences are effectively enumerable (they're exactly the negations of the valid sentences); however, there are lots of sentences which are neither valid nor invalid. For example, "$\forall x\exists y (R(x, y))$" (where $R$ is a binary relation symbol) is neither valid nor invalid.

If we use the second meaning, then every sentence is either valid or invalid; however, the invalid sentences are not effectively enumerable. The valid sentences are effectively enumerable since $\varphi$ is valid iff it has a proof, and we may effectively search through proofs (and hence enumerate the valid sentences). On the other hand, to tell if a sentence is invalid, we need a countermodel - a model in which it fails. Such a model might have to be infinite, and there's no way to search through all the models in an effective manner. More generally, the complement of an effectively enumerable set is not in general effectively enumerable, but rather effectively co-enumerable. (It is true that if $A$ and $\mathbb{N}\setminus A$ are each effectively enumerable, then they are also each decidable; but that's not relevant here, since we only know that one piece is effectively enumerable.)

The right picture to have is the following. Avoiding the term "invalid" for clarity, there are three types of sentences: those true in every model (valid), those false in every model (contradictory), and those true in some models but false in others (contingent). The valid and contradictory sentences are each effectively enumerable; however, the contingent ones are not, and in fact none of the three classes is decidable.