What's an example of a theory that's consistent yet has no model?

Solution 1:

Take the second-theory in the language of $\leq$ which states that:

1. $(A,\leq)$ is a linear order without a maximal element.
2. Every non-empty set has a minimal element.
3. Every bounded set has a maximal element.

This means that $(A,\leq)$ is isomorphic to $\Bbb N$ with its usual order. Now add uncountably many constant symbols to the language $c_i$ for $i\in I$, and add the axioms $c_i\neq c_j$ for each $i\neq j$.

Of course this theory cannot have a model, since a model would be isomorphic to $\Bbb N$ but it will have uncountably many elements. But given any finite number of axioms we can interpret them in the usual order on $\Bbb N$, so they cannot possible prove a contradiction. Therefore the theory is consistent.

If you don't want to use an uncountable language, add $c_i$ for $i\in\Bbb Z\setminus\Bbb N$, and claim that $c_i<c_j$ whenever $i<j$. Again finitely many axioms are interpretable in the usual $\Bbb N$ showing consistency, but there is no model which is isomorphic to $\Bbb N$ and is not well-ordered.

If you don't want to use an infinite language, just add one constant symbol, $c$ and axioms that say that $c$ is not the minimal element, not the successor of the minimal element, and so on and so forth (note that the successor function is definable in $\Bbb N$ with $\leq$, even in first-order logic). The same argument from above applies.

Solution 2:

If you just want a general logic where a theory is syntactically consistent but has no model, start with the usual first-order logic, but consider the semantics where we have only finite models. There are many consistent theories that have only infinite models; in our new logic these theories will be consistent but will have no models at all.

That example has the same issue as second-order logic, actually. The completeness theorem for second-order logic does not hold if we use a particular semantics, known as full semantics. The point of full semantics is that it excludes by fiat many models that would otherwise satisfy second-order theories, just like our first-order logic with only finite models.

Intuitively, it is easy to see why this would cause the completeness theorem to fail: the completeness theorem says that every consistent theory has a model in the general sense. But if we start to reduce the set of "allowable" models, we may well exclude all the models of some particular theory. The theory will still be syntactically consistent - it hasn't changed at all!

We can find examples of theories with no full model by taking theories that are syntactically incomplete, but which have only one full model. For example, there is an axiomatization $T$ of arithmetic with the property that its only full model is the standard model. If we take $T + \lnot\text{Con}(T)$, this will be consistent by Goedel's incompleteness theorem, but it will have no full model.

I have written something else about this here.