We’ll use a language LL that has at least one constant symbol. We have a set of quantifier-free sentences (Γ\Gamma).

We’ll say that an LL-structure is minimal if it has no proper substructure (there is no strictly smaller domain for the structure, symbols are interpreted in the same way).

We suppose that Γ\Gamma is satisfiable and that for any quantifier-free sentence σ\sigma, either σ∈Γ\sigma \in \Gamma or ¬σ∈Γ\neg \sigma \in \Gamma.

I am trying to prove that there is a unique minimal LL-structure, up to isomorphism, which is a model of Γ\Gamma.

I can’t quite get a grasp on this one as I’m discovering Model Theory. I would imagine going for a model with a domain that has just enough elements to give an interpretation to all constants in a way that satisfies the formulas in Γ\Gamma. Now with possibly infinitely many formulas, this is hard to do… But for finite subset of Γ\Gamma we can find such a model (can’t justify this formally though). Then I’d use Compactness. But I’m stuck for anything that comes after (uniqueness up to isomorphism, minimality). Maybe I should go for an explicit construction?

I’m confused and any help would be very much appreciated

=================

=================

2 Answers

2

=================

Exercise 1 Show that an LL-structure is minimal if and only if every element is the interpretation of a term. Moreover, show that, given any LL-structure, the set of interpretations of terms forms a substructure.

Exercise 2 For any given LL-structure, define the atomic theory of the structure to be the set of quantifier-free sentences it satisfies. Use the result of Exercise 1 to show that two minimal LL-structures are isomorphic if and only if they have the same atomic theory.

Exercise 3 From the above two exercises, conclude the desired result.

Extra credit In Exercise 2, show moreover that the isomorphism between the structures is unique. Conclude that, given Γ\Gamma as in the problem statement, Γ\Gamma has a minimal model that is unique up to a unique isomorphism.

Here is a solution to Exercise 2.

Assume we have LL-structures MM and NN, and an LL-structure isormophism f:M→Nf:M \to N. It is routine to show, by induction on the complexity of the sentences, that M⊨σM \models \sigma if and only if N⊨σN \models \sigma, for any quantifier free sentence σ\sigma. Therefore MM and NN have the same atomic theory.

Assume LL-structures MM and NN are minimal and have the same atomic theory Γ\Gamma. We will build an LL-structure isomorphism f:M→Nf:M \to N. Let a∈Ma \in M. We know that a=tMa = t^M for some LL-term tt, by Exercise 1. Set f(a)=tNf(a) = t^N and note that tNt^N is the only possible choice of value for f(a)f(a) if we want ff to be an isomorphism, since isomorphisms preserve the interpretation of terms. Observe that the chosen value of f(a)f(a) does not depend on the choice of tt: if a=tM1a = t_1^M, also, then the sentence t=t1t = t_1 is in Γ\Gamma, so tN=tN1t^N = t_1^N as well. It remains to show that ff is injective, surjective, and preserves the interpretation of symbols in LL.

(Injectivity.) Assume f(a1)=f(a2)=bf(a_1) = f(a_2) = b. Take terms t1t_1 and t2t_2 such that a1=tM1a_1 = t_1^M and a2=tM2a_2 = t_2^M. Then, by the construction of ff, tN1=tN2=bt_1^N = t_2^N = b, so N⊨t1=t2N \models t_1 = t_2, so M⊨t1=t2M \models t_1 = t_2, so a1=a2a_1 = a_2, as desired.

(Surjectivity.) Let b∈Nb \in N. Since NN is minimal, by Exercise 1, we know that b=tNb = t^N for some term tt. Then f(tM)=bf(t^M) = b, as desired.

(Preservation of symbols.) Let R(x1,…,xn)R(x_1,\ldots,x_n) be a relation in LL, and let a1,…,an∈Ma_1,\ldots,a_n \in M. Take terms t1,…,tnt_1,\ldots,t_n such that ai=tMia_i = t_i^M. Then

M⊨R(a1,…,an)⟺M⊨R(t1,…,tn)⟺N⊨R(t1,…,tn)⟺N⊨R(f(a1),…,f(an)),\begin{align*}

M \models R(a_1,\ldots,a_n)

&\iff M \models R(t_1,\ldots,t_n) \\

&\iff N \models R(t_1,\ldots,t_n) \\

&\iff N \models R(f(a_1),\ldots,f(a_n))

\text{,}

\end{align*}

as desired.

Let α(x1,…,xn)\alpha(x_1,\ldots,x_n) be a function in LL, and let a1,…,an∈Ma_1,\ldots,a_n \in M. Take terms t1,…,tnt_1,\ldots,t_n such that ai=tMia_i = t_i^M. Then

f(αM(a1,…,an))=f(α(t1,…,tn)M)=α(t1,…,tn)N=αN(f(a1),…,f(an)),\begin{align*}

f(\alpha^M(a_1,\ldots,a_n))

&= f(\alpha(t_1,\ldots,t_n)^M) \\

&= \alpha(t_1,\ldots,t_n)^N \\

&= \alpha^N(f(a_1),\ldots,f(a_n))

\text{,}

\end{align*}

as desired.

We have now shown that M≅NM \cong N by the unique isomorphism ff.

I can prove 1 definitely but I’m already confused about 2… Then I think I could conclude, the problematic step really is 2 I believe… Could you give me an insight? Thank you so much for your quick answer!

– Kika

yesterday

@Kika I added a more or less full solution to Exercise 2 for you to consult. I hope that helps! I didn’t write down absolutely complete justifications for everything, so let me know if there’s any step that’s troubling you.

– Mike Haskel

yesterday

Thank you very much, it’s all clear, and it also clarifies some things I didn’t quite have a grasp on which is amazing! Thank you again!

– Kika

yesterday

Look at not just constants, but all terms (a term is, inductively either a constant symbol or an nn-ary function symbol applied to nn terms). Define an equivalence relation on terms by saying that t1∼t2t_1 \sim t_2 iff the sentence “t1=t2″”t_1=t_2\!” is in Γ.\Gamma. Now build a structure whose domain is the set of equivalence classes of terms.