Is the theory of finite sets in the language of pure equality the minimal theory?

132 Views Asked by At

Consider the first-order language of pure equality. Consider $Th(K)$, where $K$ is the class of finite sets. I conjecture that it is the minimal theory, that is to say, the theory axiomatized by the empty set of axioms. Is this true?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, this is correct.

By definition, the empty theory in the empty language is the theory of all sets of all cardinalities, so it suffices to show that every satisfiable pure-equality sentence has a finite model.

So let $\varphi$ be a sentence in the empty language with no finite models. By compactness, $\neg\varphi$ has an infinite model; by Lowenheim-Skolem (and the fact that a pure set is determined up to isomorphism by its cardinality) all infinite pure sets are elementarily equivalent, so every infinite set satisfies $\neg\varphi$. Consequently $\varphi$ is unsatisfiable.


In fact, a more general result holds: every satisfiable sentence in a language consisting only of $1$-ary relation symbols and $0$-ary function symbols (= constant symbols) has a finite model. This is largely the same argument, the point being that a structure in such a language is really just a list of pure sets (we need higher arity relations/functions to be able to have any real "interactivity").