# What's the deal with empty models in first-order logic?

Asaf's answer here reminded me of something that should have been bothering me ever since I learned about it, but which I had more or less forgotten about. In first-order logic, there is a convention to only work with non-empty models of a theory $T$. The reason usually given is that the sentences $(\forall x)(x = x)$ and $(\forall x)(x \neq x)$ both hold in the "empty model" of $T$, so if we want the set of sentences satisfied by a model to be consistent, we need to disallow the empty model.

This smells fishy to me. I can't imagine that a sufficiently categorical setup of first-order logic (in terms of functors $C_T \to \text{Set}$ preserving some structure, where $C_T$ is the "free model of $T$" in an appropriate sense) would have this defect, or if it did it would have it for a reason. So something is incomplete about the standard setup of first-order logic, but I don't know what it could be.

The above looks like an example of too simple to be simple, except that I can't explain it to myself in the same way that I can explain other examples.

-
I don't think I could give you a satisfactory answer, however I can say that categorical way of thinking is not always compatible with the logical way of thinking. This is a good example for such incompatibility. A nice way to spend an hour is to read and contemplate Mathias' "The Ignorance of Bourbaki" which speaks of this incompatibility. –  Asaf Karagila Jun 13 '11 at 22:02
@Asaf: I have read Mathias' critique, and from what I can recall of it, Mathias is not criticizing the categorical way of thinking; he is criticizing a lack of understanding of Godel's work, which I don't think is at all synonymous. –  Qiaochu Yuan Jun 13 '11 at 22:08
@Qiaochu: I agree, however the critique is even further about the fact that logic is arithmetic and categories are geometric, and the two are very incompatible in many cases. This is at least what I got from the paper. –  Asaf Karagila Jun 13 '11 at 22:16
Perhaps we should turn this apparent paradox on its head and say that the empty model is the unique model for any inconsistent theory. After all, $\lnot ( \exists x . \, \top )$ is equivalent (intuitionistically!) to $\forall x . \, \bot$, and if we can deduce $\bot$ we can certainly deduce $\forall x . \, \bot$. –  Zhen Lin Jun 14 '11 at 0:15
Addendum: The empty model, in that sense, is like the zero ring. It has a rather unpleasant property which we ignore in most situations, but it is useful to have it around as e.g. the initial object. –  Zhen Lin Jun 14 '11 at 10:13

Both $(\forall x)(x = x)$ and $(\forall x)(x \not = x)$ do hold in the empty model, and it's perfectly consistent. What we lose when we move to empty models, as Qiaochu Yuan points out, are certain inference rules that we're used to.

For first-order languages that include equality, the set $S$ of statements that are true all models (empty or not) is a proper subset of the set $S_N$ of statements that are true in all nonempty models. Because the vast majority of models we are interested in are nonempty, in logic we typically look at sets of inference rules that generate $S_N$ rather than rules that generate $S$.

One particular example where this is useful is the algorithm to put a formula into prenex normal form, which is only correct when we limit to nonempty models. For example, the formula $(\forall x)(x \not = x) \land \bot$ is false in every model, but its prenex normal form $(\forall x)(x \not = x \land \bot)$ is true in the empty model. The marginal benefit of considering the empty model doesn't outweigh the loss of the beautiful algorithm for prenex normal form that works for every other model. In the rare cases when we do need to consider empty models, we realize we have to work with alternative inference rules; it just isn't usually worth the trouble.

From a different point of view, only considering nonempty models is analogous to only considering Hausdorff manifolds. But with the empty model there is only one object being ignored, which we can always treat as a special case if we need to think about it.

-
Okay, but can't we just add $(\exists x)$ to the beginning of every prenex normal form where $x$ doesn't occur elsewhere in the formula? I don't want to use inference rules that are false for the empty model. –  Qiaochu Yuan Jun 13 '11 at 22:51
You could do something like that, based on whether the original formula is true or false in the empty model. But there are other inference rules that are invalid in empty models, like the substitution rule you mentioned, $(\forall x)\phi \to \phi[t/x]$, and $\phi[t/x] \to (\exists x)\phi$. I think it's easier to just work by cases: the empty model, and everything else. –  Carl Mummert Jun 13 '11 at 23:17
I think this is a bad logical habit. There are situations in ordinary mathematics where one can prove a statement of the form $(\forall x \in S) P$ where $P$ is a false statement not depending on $x$ and $S$ is empty, and if you are in such a situation then the good habit is to check whether $S$ is non-empty before declaring, for example, that you've proven some false statement which implies the Riemann hypothesis. –  Qiaochu Yuan Jun 13 '11 at 23:33
People certainly write that sort of proof all the time, for example by studying properties of some class of spaces which later turns out to have no spaces in it. But that problem won't translate directly to first-order logic because $(\forall x)P$ is not quite the same as $(\forall x \in S) P$. If we try to make $S$ the universe of a first-order theory that has no non-empty models, that theory will just be inconsistent when we look at it with the normal set of inference rules for non-empty models. And in logic we are already very used to checking that our theories are consistent. –  Carl Mummert Jun 14 '11 at 0:13
On the other hand if we make $S$ a predicate, then we can still assume that the overall universe (of sets, say) is nonempty, and use our normal inference rules, which will handle the case where $S$ has no elements. So $(\forall x \in S)P$ is an abbreviation for $(\forall x)(x \in S \to P)$ but the overall universe being quantified over is nonempty. –  Carl Mummert Jun 14 '11 at 0:14

Isn't this a non-issue?

Many of the most common set-ups for the logical axioms were developed long ago, in a time when mathematicians (not just logicians) thought that they wanted to care only about non-empty structures, and so they made sure that $\exists x\, x=x$ was derivable in their logical system. They had to do this in order to have the completeness theorem, that every statement true in every intended model was derivable. And so those systems continue to have that property today.

Meanwhile, many mathematicians developed a fancy to consider the empty structure seriously. So logicians developed logical systems that handle this, in which $\exists x\, x=x$ is not derivable. For example, this is always how I teach first order logic, and it is no problem at all. But as you point out in your answer, one does need to use a different logical set-up.

So if you care about it, then be sure to use the right logical axioms, since definitely you will not want to give up on the completeness theorem.

-
Thanks for the reassurance. In my logic and set theory course we were not told that one could modify the axioms to handle the empty model, and I forgot to ask before the course ended. So I didn't know if this could be easily done. –  Qiaochu Yuan Jun 14 '11 at 0:16
It is true that the most common treatments exclude the empty model, which is traditional and allows for certain conveniences as Carl mentions (and in any case, we are not confused about the empty structure). I think one of the main reasons involves a tradition of dealing with formulas (with free variables) in deductions, rather than with their universally quantified forms. This is sensible only in non-empty structures. –  JDH Jun 14 '11 at 0:48

There are categorical foundations for model theory: Makkai and Reyes, First order categorical logic (LNM 611). Here is a quote from page 72:

An important point is that we allow the (partial) domains $M(s)$ of $M$ to be empty. In model theory, usually the domains are stipulated to be non-empty. This difference slightly effects what sequents are considered logically valid; c.f. below.

-

Suppose that we admit empty structures. There is no real technical hurdle, we are endlessly ingenious.

However, instead of starting with "Let $\mathbb{A}$ be an $L$-structure," many theorems would have to start with "Let $\mathbb{A}$ be a non-empty $L$-structure." Think of the cumulative waste of resources, whole forests destroyed to produce the additional paper needed. And in this electronic age, are bits a renewable resource?

But one must admit there would also be benefits. There could be a new mathematical specialty, nit-picker, whose task would be to point out with glee the various places where a famous mathematician had blundered by forgetting to deal with empty structures. At a time of economic difficulty, this would boost employment, and contribute to the gross national product.

-
I would note that the upcoming SSD technology is especially prone to failure after much rewriting, as this whole process would require ;-) –  Asaf Karagila Jun 13 '11 at 23:13
I disagree that pointing out a failure to deal with empty structures is nit-picking. There are theorems which genuinely deserve to have "non-empty" as a hypothesis (for example, Zorn's lemma), and if you forget to check that a set is non-empty before you apply them, you will say something which is wrong. More generally, the empty set is an extremal case, and a lot of very fruitful mathematics comes from looking at extremal cases. I think it is silly to ignore this just because it makes some theorems easier to state. –  Qiaochu Yuan Jun 13 '11 at 23:18
(I once e-mailed Szamuely to inform him that in his excellent book Galois Groups and Fundamental Groups, whenever he claims that a category is isomorphic to a category of $G$-sets for some group $G$, he should actually say "non-empty $G$-sets." He dismissed this as nit-picking, but the category of $G$-sets is a topos and the category of non-empty $G$-sets isn't, so there is a genuine distinction to be made between the two, and geometrically the non-empty condition is quite natural, so why neglect to state it? All of the theorems about transitive $G$-sets, on the other hand, are correct... –  Qiaochu Yuan Jun 13 '11 at 23:23
...because the empty $G$-set is not transitive, and again this is geometrically quite natural.) –  Qiaochu Yuan Jun 13 '11 at 23:24
@Qiaochu Yuan: To be more serious about these things, a notion has to earn its way. The empty set certainly has, a copy of the whole mathematical universe has been built using $\emptyset$ as the fundamental brick. In mathematical linguistics, the empty word makes the algebra more natural. If empty structures were ever to show an even modest usefulness, of course they would be admitted. –  André Nicolas Jun 13 '11 at 23:33

Okay, if this is the answer, it is quite silly. The axioms of first-order logic in my notes include

$$(\forall x) p \Rightarrow p[t/x]$$

which is manifestly false for the empty model and $p = \perp$ so should just be thrown out and replaced by the correct axiom

$$(\forall x) p \wedge (\exists x) \Rightarrow p[t/x].$$

Nothing changes except for the empty set, where the statement $(\forall x) \perp$ is true but $\perp$ is not, so there is no contradiction.

-
What does $p[t/x]$ mean? –  Asaf Karagila Jun 13 '11 at 22:18
usually something like the formula p with free occurrences of x replaced by t. (edited: you get the point :P ) –  matt Jun 13 '11 at 22:19
There still seems to be an issue for you with empty models with this suggested axiom schema $(\forall x)p \wedge (\exists x) \rightarrow p[t/x]$. For example, take $p$ (with no occurrences of $x$) to be $\exists y (y=y)$. Now if we had an empty model, it fails the antecedent by non-existence of an $x$, but to be a model must satisfy the consequent $p[t/x]$ which is still $\exists y (y=y)$. –  matt Jun 13 '11 at 22:27
@matt: I'm not sure I understand why that's a problem. –  Qiaochu Yuan Jun 13 '11 at 22:36
edit: oop, nevermind. I slipped and was thinking models need to satisfy the consequent when the antecedent failed. That's not true at all :s –  matt Jun 13 '11 at 22:48

Since nobody else has mentioned the phrase, I think what you are looking for is called free logic by those who adopt the convention about what "first-order logic" means that would imply all models are nonempty.

We can construct a $C_T$ that is defective in the same way; we include a bunch of arrows $1 \to T$ to represent indeterminate elements of $T$. Then any lex functor $C_T \to \mathbf{Set}$ must send $T$ to a non-empty set.

Of course, the usual categorical approach of interpreting free variables as generalized elements doesn't have this defect.

-

Honestly, I'm having difficulty seeing the problem.

"The model is empty" translates to "the theory doesn't prove $(\exists x) (x=x)$".

So every theory that can't prove that can have an empty model.

-
I don't understand your argument. If $T$ doesn't prove a statement $P$, it doesn't follow that no model of $T$ satisfies $P$; it only follows that some model of $T$ doesn't satisfy $P$. –  Qiaochu Yuan Jun 13 '11 at 22:27
Yeah I removed that part. –  trutheality Jun 13 '11 at 22:28
Well, now I don't understand your claim that the corresponding theories aren't very interesting. For example, there is a theory $T$ of dynamical systems, which are sets $X$ equipped with a function $f : X \to X$, and the empty set ought to be a model of this theory. Certainly dynamical systems are interesting. –  Qiaochu Yuan Jun 13 '11 at 22:32
But I'm not. Clearly the empty model is not a model of the theory of groups, for example. –  Qiaochu Yuan Jun 13 '11 at 22:38
Okay, I don't disagree with your answer now, but it's also not an answer to my question. –  Qiaochu Yuan Jun 13 '11 at 22:40