What are the L-sentences that are true in an empty structure?

Question

I am looking for an algorithm or set of rules to figure out whether a sentence (in first order logic) is true when we are dealing with an empty set as domain. Clearly, it has to be a sentence (no free variables) or there would be nothing to assign. It's also clear to me that universal formulas will be true while existential ones won't, but I think I might be missing something else, maybe... what happens when the formula is $\forall\exists$ and $\exists\forall$? My guess would be to just take the first quantifier, but might be wrong about that... I would appreciate your input and suggestions about this.

Answer 1

The algorithm you are looking for is probably this: for quantified sentences, use just the first quantifier: $\forall$ sentences are true and $\exists$ sentences are false.

But the situation is more complicated. Remember that truth-in-a-structure is a defined notion.

There are two general ways of defining semantics for first-order structures, and they disagree when the structure is empty. They are:

1. Define the notion of a 'variable assignment' function. Then a sentence is defined to be true if it is satisfied by some variable interpretation (or, in some books, by every variable interpretation; this is equivalent for sentences in non-empty models).

2. Add a constant $c_a$ to the language for each element $a$ of the domain. Then a sentence of the form $(\forall x)\phi(x)$ is true if $\phi(c_a)$ is true for every element $a$ of the domain.

For non-empty structures, these give equivalent results. But for empty structures they do not, so the collection of true sentences of an empty structure depends on what convention you follow for defining the set of true sentences.

Option (2) works basically they way you want. But option (1) does not. There are no variable assignment functions, because the set of variables is always non-empty even if the domain is empty. So if we say that a sentence is true if it is satisfied by some variable assignment, then no sentence is true. If we say that a sentence is true if it is satisfied by every variable assignment, then every sentence is true. This is not what you would immediately expect.

Even if we use option (2), when we look at empty structures we lose many sentences that are true in all nonempty models. For example, the prenex normal form of $(\forall x)(x = x) \land \bot$ is $(\forall x)(x = x \land \bot)$. The former is false in an empty structure, while the latter is true under option (2). But those two sentences are equivalent in every nonempty structure. Many of the inference rules of first-order logic, like the ones used for prenex normal form, have hidden assumptions that the domain is non-empty.