3
$\begingroup$

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.

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ Usually by definition a structure has non empty domain. $\endgroup$ – Achilles Apr 18 '15 at 11:40
  • $\begingroup$ I'm aware, that's exactly what this question is about, what are the things that change when you do admit an empty domain, instead of the standard. $\endgroup$ – Sara Apr 18 '15 at 11:43
  • 2
    $\begingroup$ @Sebastian: Hodges' well-known book Model Theory allows models to have empty domains. Empty domains make the logic more complicated so it is very common for logicians to disallow them, model theorists seem to be divided in their opinions on this topic. $\endgroup$ – Rob Arthan Apr 18 '15 at 12:27
  • $\begingroup$ Okay, I see. In that case I retract my comment. Thanks for letting me know. $\endgroup$ – Achilles Apr 18 '15 at 12:30
5
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ It is very common for the equivalent of option 2 to be described using a variable assignment function that is partial and is only required to assign values to the free variables of the formula of interest. $\endgroup$ – Rob Arthan Apr 18 '15 at 15:13
  • $\begingroup$ Thank you to both of you, this is very helpful, I will be careful with the semantics I use, I usually work with variable assignment functions, so I think that @RobArthan comment can help me state the bridge between what you said and the semantics I use. $\endgroup$ – Sara Apr 19 '15 at 9:37

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.