This is a bit of a soft question, but I am interested in a list of classes of structures (in the sense of model theory) which are "surprisingly" first-order axiomatizable classes. Meaning, the class of structures is defined in such a way that it is not at all obvious that it is in fact first-order axiomatizable. So, for example, the class of fields with exactly 3 elements is axiomatizable, but not surprisingly so.
$\begingroup$
$\endgroup$
8
-
6$\begingroup$ Besides that one negative example, a positive example or two would help establish what you are asking for. $\endgroup$– Lee MosherJan 5 at 17:15
-
1$\begingroup$ @GregNisbet I would say that the class of models of $Th(\mathbb{N})$ is obviously first-order axiomatizable. More generally, this is true for any $Th(\mathfrak{A})$, by definition of "$Th$." $\endgroup$– Noah SchweberJan 5 at 18:47
-
1$\begingroup$ @GregNisbet The non-obviousness there is about the "coherence" of $Th(\mathbb{N})$, though; once we understand (or temporarily take for granted) that it makes sense, it's literally trivial that the class of its models is elementary. $\endgroup$– Noah SchweberJan 5 at 18:57
-
1$\begingroup$ To the OP, here are two nice near-misses: the class of finite symmetric groups is surprisingly "finitely axiomatizable on the class of finite structures," and the class of "$\omega$s of $\mathsf{ZFC}$-models" is surprisingly non-elementary even when we restrict attention to countable structures. See 1, 2 respectively. $\endgroup$– Noah SchweberJan 5 at 19:06
-
1$\begingroup$ So basically, you're asking about non-first-order properties that have non-obvious first-order equivalents. $\endgroup$– tomaszJan 6 at 16:28
|
Show 3 more comments
3 Answers
$\begingroup$
$\endgroup$
3
The class of graphs that are 2-colorable.
A graph is 2-colorable if there is an equivalence relation on the set of verteces that has 2cclasses and is such that no adiacent vertexes are in in the same classs.
The description above is second-order, but it is equivalent to the class of graphs without odd cycles, hence first-order axiomatizable.
-
1$\begingroup$ How does one say "there are no odd cycles" in a first-order way? $\endgroup$– KarlJan 6 at 16:43
-
3$\begingroup$ @Karl: For each $n$, you say that there is no cycle of length $2n+1$. $\endgroup$– tomaszJan 6 at 17:08
-
4$\begingroup$ More generally, there are many examples in graph theory of a priori existential second-order properties that turn out to be equivalent to the nonexistence of a certain type of finite obstacle, and thus are first-order-expressible. $\endgroup$ Jan 6 at 18:00
$\begingroup$
$\endgroup$
Here's a class of examples which connects to a currently-0pen large-cardinals-flavored question:
Given a first-order theory $T$, let $NE(T)$ be the class of structures not embeddable in a model of $T$. On the face of things, the definition of this class of structures is even worse than second-order, since (even ignoring finite structures) we need the Lowenheim-Skolem theorem to reduce "not embeddable into a model of $T$" to a $\Pi^1_1$ condition. However, $NE(T)$ is always elementary. This is a quick application of compactness (which is also the key step in the proof of the Los-Tarski theorem): we have $\mathcal{M}\in NE(T)$ iff the theory $T\cup AtDiag(\mathcal{M})$ is inconsistent, which happens iff some "finite bad configuration" occurs in $\mathcal{M}$. So in fact we get that $NE(T)$ is not only always elementary, it's always axiomatizable by a set of existential sentences!
Things get more interesting when we iterate this idea. What about, for example, the class $NE_2(T)$ of structures $\mathcal{M}$ which can be embedded into an element of $NE(T)$? Or the "higher $NE_n(T)$s" ($n\in\omega$)? While true elementariness is definitely too much to hope for now, we might at least hope for single-sentence-axiomatizability in infinitary first-order logic $\mathcal{L}_{\infty,\infty}$. (This is closely-related to question 57/58 of Hamkins and Woloszyn). While this is still open to the best of my knowledge, we do have some partial progress: the answer is affirmative assuming an appropriate large cardinal hypothesis, and in particular we get a conditional affirmative answer to H/W's question. In fact, assuming a really strong large cardinal axiom (Vopenka's principle), we get a kind of preservation-of-definability argument: if $T$ is an $\mathcal{L}$-theory for any logic $\mathcal{L}$, then the $NE_n(T)$s are uniformly-infinitarily-$\mathcal{L}$-definable in an appropriate sense. See the end of this post for the argument.
answered Jan 14 at 20:05
$\begingroup$
$\endgroup$
How about the class of fields $K$ with a finitely generated (over $K$) algebraic closure?
(It consists of the fields which are either real closed or algebraically closed.)
I think most equivalent definitions (given on Wikipedia) of real closed fields can be turned into examples of this.
