Smallest set of models to which only the tautologies are universally true?

Question

Consider a first order language with a certain signature $\sigma$ (e.g. $(+,0)$). A tautology is a $\sigma$-formula (i.e. a first order formula with the standard logical symbols, variables, and $+,0$) that is true for all $\sigma$-structures.

So we have already a set $S$ of models (namely the set of all $\sigma$-structures) in which the following property is true:

Definition. Given a set of models $S$, the set $\Phi_S$ is defined as the set of formulas $\phi$ such that $\phi$ is true in every model in $S$.

Definition. $S$ satisfies property $P_S$ iff $\Phi_S$ exactly equals the set of tautologies.

But presumably we can remove some models from the set while still retaining the property $P_S$. My question is, is there a smallest set $S$ of models that satisfies $P_S$? i.e. a smallest set of models such that only the tautologies are true for all of them.

Answer 1

By counting sentences (per Hagen von Eitzen's comment), there is a countable $S$ with the property you want. Combined with the Lowenheim-Skolem theorem, there is in fact a countable $S$ consisting entirely of countable structures with the desired property.

Refining things further, we have results from computability theory. For every satisfiable sentence $\sigma$ there is an infinite computable binary tree $T_\sigma$ such that every path through $T_\sigma$ computes a model of $\sigma$. So every basis theorem for closed sets in Cantor space yields such an $S$. For example, the set of structures with domain $\subseteq\mathbb{N}$ which are low - of which there are only countably many - has the desired property.

---

It's worth pointing out that we can ask the same question about other logics. Hagen von Eitzen's comment applies in general - if $\mathcal{L}$ is a logic with $\kappa$-many sentences, we can find a desired $S$ with cardinality $\kappa$. We can further control $S$ by computing the Lowenheim number of $\mathcal{L}$, namely the least $\lambda$ such that every satisfiable $\mathcal{L}$-sentence has a model of size $<\lambda$. For example, the Lowenheim number of the nicest infinitary logic $\mathcal{L}_{\omega_1,\omega}$ is just $\aleph_0$ as with first-order logic, while the Lowenheim number of second-order logic is gigantic.

(A good proof that the Lowenheim number of $\mathcal{L}_{\omega_1,\omega}$ is $\aleph_0$ can be found in Marker's recent book. On the other hand, here's a delightfully stupid proof: if $\varphi$ is a satisfiable $\mathcal{L}_{\omega_1,\omega}$-sentence, take a forcing extension $V[G]\supset V$ in which some model of $\varphi$ is countable and apply Mostowski absoluteness to the sentence "$\varphi$ has a countable model.")

Answer 2

Let $X$ be the topological space of complete theories with signature $\sigma$ (or, the Stone space of the Lindenbaum-Tarski algebra of the empty theory over $\sigma$). Explicitly, the topology on $X$ is defined by taking as a basis the sets $U_\varphi=\{T\in X:\varphi\in T\}$ for each sentence $\varphi$. Then a set $S$ of models satisfies $P_S$ iff the set of the complete theories of the elements of $S$ is dense in $X$. Indeed, a nonempty basic open set is exactly the set of models that satisfy some sentence whose negation is not a tautology, so intersecting every such set just means that the only sentences that are false in all of your theories are the negations of tautologies.

So, you are asking for a minimal dense subset of $X$. If you mean minimal in cardinality, then trivially such a set exists since cardinals are well-ordered. You need an infinite set, since you need to witness every possible finite cardinality of a model, and clearly you don't need more points than the cardinality of the language (just pick a point to witness each sentence). So over a countable language, a minimal dense subset is always countably infinite. Over an uncountable language the size of a minimal dense subset seems harder to determine in general; for instance, in a signature consisting of $2^{\aleph_0}$ constant symbols, it is a nontrivial theorem that there is still a countable dense subset (this is closely related to the fact that the space $\{0,1\}^{\mathbb{R}}$ is separable).

If you mean minimal with respect to inclusion, then usually such a dense subset does not exist. Indeed, an inclusion-minimal dense subset of $X$ exists iff isolated points are dense in $X$: if isolated points are dense then the set of all isolated points is in a strong sense the smallest dense subset (it is contained in every other dense subset), and conversely if isolated points are not dense then every dense subset contains a non-isolated point and then you can omit that point and still have a dense subset. An isolated point of $X$ is a theory which is generated by a single sentence. Such theories clearly can only be dense over a finite signature (since a single sentence can only involve finitely many symbols). If the signature has a binary relation symbol, then you can write a single axiom which contains enough of ZF to interpret Robinson arithmetic and then the theory cannot be extended to any computable complete theory, and in particular no complete theory extending it can be generated by a single sentence. This then gives a nonempty open subset of $X$ with no isolated points, so isolated points are not dense. Similarly if you have a relation symbol of higher arity or a binary function symbol you can interpret Robinson arithmetic and isolated points are not dense in $X$.

On the other hand if the signature has only finitely many constant and unary relation symbols then it is easy to see $X$ is countable and thus isolated points are dense. This leaves open only the cases where there are unary function symbols but no symbols of higher arity. A single unary function symbol will make $X$ uncountable (consider possible lengths of cycles for the unary function), but I think isolated points might still be dense.