Can tautologies have free variables?

Question

In propositional logic, a tautology is defined as a statement that is true no matter the truth values assigned to its propositional variables. So, in propositional logic, All apples are red or there exists an apple that is not red is a tautology.

Now, Wikipedia says:

A tautology in first-order logic is a sentence that can be obtained by taking a tautology of propositional logic and uniformly replacing each propositional variable by a first-order formula (one formula per propositional variable).

So, I understand that in first-order logic, (∀x∈N x is even) ∨ ¬(∀x∈N x is even) is a tautology as it is obtained by replacing the propositional variable A in the tautology A ∨ ¬A with (∀x∈N x is even).

However, I haven’t been able to find a text that states whether open sentences can be tautologies. For example, the open sentence (x is even) ∨ ¬(x is even) is obtained by replacing the propositional variable B in the tautology B ∨ ¬B with x is even. B would be an open sentence, which doesn’t have a truth value, so how could B ∨ ¬B be true? Is (x is even) ∨ ¬(x is even) a tautology?

Answer 1

Wikipedia says:

A tautology in first-order logic is a sentence that can be obtained by taking a tautology of propositional logic and uniformly replacing each propositional variable by a first-order formula (one formula per propositional variable).

Wikipedia is defining a tautology as a formula whose truth-functional form is true whatever its atomic propositions' truth values; so, it does not admit x=x (whose truth-functional form is just P) as a tautology. On the other hand, some authors refer to every logical validity as a tautology, so call x=x a tautology.

Everyone, though, agrees that (x is even) ∨ ¬(x is even) (whose truth-functional form is P ∨ ¬P) is a tautology. Therefore, the answer to your main question

Can tautologies have free variables?

is Yes.

the open sentence (x is even) ∨ ¬(x is even) is obtained from B ∨ ¬B. B would be an open sentence, which doesn’t have a truth value, so how could B ∨ ¬B be true?

(x is even) ∨ ¬(x is even) is an open formula, but its truth-functional form B ∨ ¬B is a closed formula (i.e., a sentence) that is tautological.

In propositional logic, a tautology is defined as a statement that is true no matter the truth values assigned to its propositional variables. So, in propositional logic, All apples are red or there exists an apple that is not red is a tautology.

The first-order validity All apples are red or there exists an apple that is not red has truth-functional form P ∨ Q, so is actually not a propositional-logic tautology.

Answer 2

Short answer: yes.

Long answer:

Say that a formula is elementary if it is either an atomic formula or a formula of the form $\exists x \phi$ for some $\phi$. Examples of elementary formulas are $P(x)$, $\exists x P(x)$, $\exists x \neg P(x)$, $\exists x (\neg P(x) \vee P(x))$. On the other hand, $\neg P(x)$ and $\exists x P(x) \rightarrow Q(y)$ are not elementary. Note that every quantified sentence is an elementary formula. For the purposes of defining tautological implication, quantified sentences are treated as black boxes, with no internal structure.

(Note also that, given this definition, one could define an appropriate propositional language by just taking the elementary formulas to be the propositional variables of this language (Enderton takes this approach: cf. A Mathematical Introduction to Logic, pp. 114ff). In that case, $P(x)$, $\exists x P(x)$, $\exists x \neg P(x)$, etc., would be treated as distinct sentence letters or propositional variables. They would be the same as $P, Q, R$, just with a different shape. One could then define a formula to be a tautology if it is a tautology in the propositional language generated by taking the elementary formulas as the propositional variables. It should be clear that this approach and the approach below are basically the same.)

Define a valuation $v$ as a function from the set of all elementary formulas to $\{0, 1\}$. This valuation can easily be extended to Boolean combinations of such formulas, by taking $v(\neg \phi) = 0$ iff $v(\phi)=1)$, etc. We can then say that a first-order formula $\phi$ is a tautology if $v(\phi)=1$ for every such valuation. (These definitions were taken from Shoenfield, Mathematical Logic, p. 26, but they are pretty standard.)

The idea is that such a formula is true by its mere propositional form, no matter its first-order content. If the formula is an open formula, then the idea is that its every instance will be true merely in virtue of its propositional form, where an instance of $\phi$ is the result of (uniformly) replacing its free variables for closed terms.

Notice that your example, $\forall x E(x) \vee \forall x \neg E(x)$ is not a tautology by this definition, since, in this approach, the negation sign inside the scope of the quantifier is black boxed. (In fact, since we took the existential quantifier as primitive, this sentence would actually be an abbreviation of $\neg \exists x \neg E(x) \vee \neg \exists x \neg \neg E(x)$, but the point still stands.) So this would be treated as similar to $P \vee Q$.

Finally, this notion of tautology is rather useful, since it allows us to use resources from propositional logic when dealing with first-order logic. In particular, since tautological consequence is decidable, this may be useful in searching for proofs---if the implication between two first-order formulas reduces to a tautological implication, there is actually an algorithm to find the proof of one from the other. This is one of the ideas behind Herbrand's Theorem.

Answer 3

No, if you take the stance that open sentences can't have a truth value, but there is a more fundamental misunderstanding here.

The variables we have in propositional and in first-order logic are of a different kind.

In propositional logic, we have variables for propositions, i.e. expressions that directly evaluate to true or false according to the valuation function. There is no notion of free or bound propositional variables, as there are no variable binding operators (no quantifiers or the like) in propositional logic.

In first-order logic, variables stand for individuals, and these individual variables are subject to binding by quantifiers ($\forall, \exists$), hence here we do have a distinction between free and bound variables, and thus closed and open sentences. In first-order logic, the expressions which have a truth value are complex formulas made up of (possibly) individual variables and predicates, and we speak of open or closed formulas depending on whether there occur any free variables in it.

---

Furthermore, "All apples are red or there exists an apple that is not red" is not a tautology in propositional logic. It is of the form $A \lor B$, not $A \lor \neg A$, because the second sentence is not a literal negation of the first, it is a syntactically different sentence.

"All apples are red or not all apples are red" would be of the form $A \lor \neg A$, and thus a tautology in propositional logic. Therefore $\forall x (\text{Apple}(x) \to \text{Red}(x)) \lor \neg \forall x (\text{Apple}(x) \to \text{Red}(x))$ (inserting $\forall x (\text{Apple}(x) \to \text{Red}(x))$ for $A$) must also be a tautology in first-order logic.

"There exists an apple that is not red" is logically equivalent to "Not all apples are red", but this can only be shown in first-order logic, because propositional logic is not fine-grained enough to express the quantifier structure. We can show that $\forall x (\text{Apple}(x) \to \text{Red}(x)) \lor \exists x (\text{Apple}(x) \lor \neg \text{Red}(x))$ is a tautology in first-order logic, but it is not an instance of any propositional logic tautology.

"$x$ is even" is not a formula in the language of propositional logic, we only have propositional variables available there. The best we can do in propositional logic is express this as $A \lor \neg A$ with propositional variable $A$, where the question of free or bound does not arise. In first-order logic, we can express it more fine-grained as $\text{Even}(x) \lor \neg \text{Even}(x)$, with the individual variable $x$ free, and this is indeed an open sentence which, depending on your semantics, can not be assigned a truth value. You could say that only first-order sentences obtained by substituting closed sentences for propositional variables are also tautologies because only they are guaranteed to have a truth value.