nLab diagram of a first-order structure

Redirected from "quantifier-free diagram".
Contents

Contents

Idea

Given a model MM of a (not necessarily complete) first-order theory TT, one can canonically associate theories T Diag(M)T_{\mathsf{Diag}(M)} and T EDiag(M)T_{\mathsf{EDiag}(M)} whose models are precisely the models NTN \models T into which MM embeds as a substructure and elementary substructure, respectively.

In the case of the latter, this gives a theory whose category of models is precisely the co-slice category M/Mod(T)M/\mathbf{Mod}(T) of models under MM in Mod(T)\mathbf{Mod}(T).

Definition

Let MM be a first-order structure in the language \mathcal{L}. We obtain an expanded language (M)\mathcal{L}(M) by adding to \mathcal{L} new constant symbols c mc_m for each mMm \in M, and MM is naturally an (M)\mathcal{L}(M)-structure by interpreting each new constant as its namesake. The elementary diagram of MM, written EDiag(M)\mathsf{EDiag}(M), is the set of all \mathcal{L}-sentences possibly using constants c mc_m which are true in MM, i.e. the (M)\mathcal{L}(M)-theory of MM.

The quantifier-free diagram of MM, written Diag(M)\mathsf{Diag}(M), is obtained the same way as EDiag(M)\mathsf{EDiag}(M), but only allowing quantifier-free (M)\mathcal{L}(M)-sentences.

If NN models EDiag(M)\mathsf{EDiag}(M), then NN contains MM as an elementary substructure. If NN models Diag(M)\mathsf{Diag}(M), then NN contains MM as an induced substructure.

If we are given MM and TT as above, we simply obtain T Diag(M)T_{\mathsf{Diag}(M)} and T EDiag(M)T_{\mathsf{EDiag}(M)} as the union of TT (viewed as an (M)\mathcal{L}(M)-theory) with Diag(M)\mathsf{Diag}(M) and EDiag(M)\mathsf{EDiag}(M), respectively.

Examples

  • A trivial example is ACF0_0, the theory of algebraically closed fields of characteristic zero (in the language of rings). Since \mathbb{Q} is the prime field of characteristic zero, any algebraically closed field models Diag()\mathsf{Diag}(\mathbb{Q}), and in fact since each element of \mathbb{Q} is already definable in ACF0_0, Diag()\mathsf{Diag}(\mathbb{Q}) is just the quantifier-free part of ACF0_0.

  • Let RR be the countable random graph. Since it is an omega-categorical structure, any countable model of EDiag(R)\mathsf{EDiag}(R) will again be isomorphic to RR. This is not true if we replace EDiag(R)\mathsf{EDiag}(R) with Diag(R)\mathsf{Diag}(R), since there are all sorts of ways to extend RR while ensuring it no longer satisfies the almost-sure theory of finite graphs. (For example, we could add a new vertex and connect it to all the vertices from RR.)

Remarks

  • For T=T Diag(M)T' = T_{\mathsf{Diag}(M)} or T EDiag(M)T_{\mathsf{EDiag}(M)} there is an obvious interpretation TTT \to T' which induces for every NTN \models T' a map of automorphism groups Aut (M)(N)Aut (N)\operatorname{Aut}_{\mathcal{L}(M)}(N) \to \operatorname{Aut}_{\mathcal{L}}(N), corresponding to the inclusion
Aut (N/M)Aut (N) \operatorname{Aut}_{\mathcal{L}}(N/M) \hookrightarrow \operatorname{Aut}_{\mathcal{L}}(N)

of the pointwise stabilizer of MM in NN into the full automorphism group of NN.

  • To add a distinct constant symbol to a theory is to adjoin a new global point to its syntactic category. This doesn’t do very much unless if you additionally specify its type, i.e. the ultrafilter of subobjects above it. When we pass to the quantifier-free diagram of a model, we specify constants named after the model up to quantifier-free types, and when we pass to the elementary diagram of a model, we specify constants named after the model up to complete types.

  • A first-order theory T eliminates quantifiers if and only if it is “substructure-complete”: given any model MM of TT and any substructure NMN \subseteq M, T Diag(N)T_{\mathsf{Diag}(N)} is complete.

Remark

The process of passing from TT to T Diag(M)T_{\mathsf{Diag}(M)} (resp. EDiag\mathsf{EDiag}) is functorial in the way you would expect the process of passing from a category of models to a co-slice category of models to be on corepresenting objects.

That is (now eliminating imaginaries and working with the pretopos completions of syntactic categories): if TT' is an \mathcal{L}'-theory and MM is an \mathcal{L}'-structure, and TT is an \mathcal{L}-theory over TT' via an interpretation TFTT \overset{F}{\to} T', then there are naturally-induced interpretations

T Diag(F *M)T Diag(M)T'_{\mathsf{Diag}(F^*M)} \to T_{\mathsf{Diag}(M)}

and

T EDiag(F *M)T EDiag(M).T'_{\mathsf{EDiag}(F^*M)} \to T_{\mathsf{EDiag}(M)}.
Proof

The interpretation FF induces a “taking reducts” functor

F *=dfMod(F)=Pretop(F,Set):Mod(T)Mod(T).F^* \overset{\operatorname{df}}{=} \mathbf{Mod}(F) = \mathbf{Pretop}(F, \mathbf{Set}) : \mathbf{Mod}(T) \to \mathbf{Mod}(T').

We restrict F *F^* to the full subcategory consisting of those models of TT embedding (resp. elementarily embedding) the structure MM. These are elementary classes, and so those full subcategories are sub-ultracategories of Mod(T)\mathbf{Mod}(T). The restrictions of F *F^* are ultrafunctors

Mod̲(T Diag(M))Mod̲(T Diag(F *M)) \underline{\mathbf{Mod}}(T_{\mathsf{Diag}(M)}) \to \underline{\mathbf{Mod}}(T'_{\mathsf{Diag}(F^*M)})

and

Mod̲(T EDiag(M))Mod̲(T EDiag(F *M)) \underline{\mathbf{Mod}}(T_{\mathsf{EDiag}(M)}) \to \underline{\mathbf{Mod}}(T'_{\mathsf{EDiag}(F^*M)})

because F *F^* already was, and so by Makkai’s strong conceptual completeness, must be reflected by the desired interpretations.

(That the latter functor is well-defined just follows from the fact that specifying an object cCc \in \mathbf{C} and a functor G:CDG : \mathbf{C} \to \mathbf{D} naturally induces a functor on the co-slice categories c/CG(c)/Dc/\mathbf{C} \to G(c)/\mathbf{D}. That the former functor is well-defined is less automatic but still trivial to check.)

References

  • Dave Marker, (2002), Model theory: an introduction, section 2.3

Last revised on May 26, 2017 at 06:47:42. See the history of this page for a list of all contributions to it.