# Does the law of excluded middle hold in first-order logic?

In propositional logic, we create well-formed formulas out of logical connective symbols and propositional variables. Then we can consider a valuation function that first assigns a true/false value to each propositional variable, and then assigns a true/false value to every well-formed formula by certain rules. If I'm not mistaken, all well-formed formulas of the form $$\varphi \vee \neg\varphi$$ (where $$\varphi$$ is a well-formed formula) are true for all possible valuations, so they are tautologies. Thus, we can conclude that the law of excluded middle holds for propositional logic.

Now in first-order logic, I know that we need to assign an interpretation or structure to our language, and then based on certain rules we assign true/false values to the relevant well-formed formulas that are propositions.

Question: In FOL, does every wff of the form $$\varphi \vee \neg\varphi$$ (where $$\varphi$$ is a wff) always evaluate to being true? Truth assignment in first-order logic seems so different than in propositional logic that I am not able to reason through such a simple question.

• Yes. If there aren’t any quantifiers then first-order logic reduces to propositional logic. Commented Sep 4, 2022 at 22:05
• It holds even when $\varphi$ is a formula with quantifiers. The easiest way to see that this must be true is the Completeness Theorem. There can be no model in which neither $\varphi$ nor $\lnot \varphi$ holds. Commented Sep 4, 2022 at 22:15
• @RobertShore This is not a valid argument. The fact that there can be no model in which neither $\phi$ nor $\neg \phi$ holds only shows that $\models \neg (\neg \phi \land \neg \neg \phi)$, but it does not show $\models \phi \lor \neg \phi$. Commented Sep 4, 2022 at 23:51

• Ok, I want to clarify a few things with some questions. So your answer holds even if $\varphi$ from $\varphi \vee \neg\varphi$ has quantifiers in it? And the way you prove this is essentially identical to the proof in propositional logic by treating all atomic formulas as propositional variables? Am I correct in these assertions? Commented Sep 4, 2022 at 22:36
• Yes. Provided that it really is the same $\varphi$ left and right. E.g. $\forall x \exists y P(x,y) \lor \neg \forall x \exists y P(x,y)$. And as a proof you would typically say that it's valid because it's an instance of a propositional tautology, which can then be proved by means of your choice. If you write a proof arguing about valuations/interpretations, it will be sufficient to look at the truth functions of the connectives without looking into the predicates and quantifiers. Commented Sep 4, 2022 at 23:17