I'm working through section 4.3. on model theory from Dirk van Dalen's Logic and Structure (fifth ed.) and am struggling with van Dalen's sometimes sloppy way of presenting proofs.

As usual let a structure $\mathfrak{A}$ be elementarily embeddable in a structure $\mathfrak{B}$ ($\mathfrak{A} \prec \mathfrak{B}$), if $\mathfrak{A}$ is isomorphic to some elementary substructure of $\mathfrak{B}$. Furthermore, let $\hat{\mathfrak{A}}$ be the structure resulting from $\mathfrak{A}$ by adding all the members of its domain as constants.

One crucial lemma in van Dalen's treatment of non-standard models is the following:

$\mathfrak{A} \prec \mathfrak{B} \Leftrightarrow \hat{\mathfrak{B}} \models Th(\hat{\mathfrak{A}})$

where $\models$ is the usual first-order satisfaction relation generalized for sets of sentences and $Th(\mathfrak{A})$ the set of sentences true in $\mathfrak{A}$.

Now, my main source of confusion in the proof of the left-to-right direction is that van Dalen assumes without proof that $\hat{\mathfrak{A}} \models \phi(\bar{a_1}, \ldots, \bar{a_n})$ entails $ \mathfrak{A} \models \phi(\bar{a_1}, \ldots, \bar{a_n})$ (let $\vec{a_i}$ abbreviate the sequence $\bar{a_1}, \ldots, \bar{a_n}$) and $\mathfrak{B} \models \phi(\vec{a_i})$ entails $\hat{\mathfrak{B}} \models \phi(\vec{a_i})$. Why is that so?

Concerning the right-to-left direction it's easy to prove that $\mathfrak{A}$ is a substructure of $\mathfrak{B}$ and that $\mathfrak{A} \models \phi(\vec{a_i}) \Rightarrow \mathfrak{B} \models \phi(\vec{a_i})$ for all ${a_i}$ from the domain of $\mathfrak{A}$. But I don't get the converse direction.

Any help would be greatly appreciated.

  • $\begingroup$ You probably mean $\hat {\mathfrak A} \models \phi(\bar a_1, ..., \bar a_n)$ entails $\mathfrak A \models \phi(\bar a_1, ..., \bar a_n)$. If this is not clear, then try to prove it by induction on $\phi$. The proof might depend on exact definitions van Dalen uses. So you are better of including them in the question. $\endgroup$ – Levon Haykazyan Aug 24 '14 at 19:12
  • $\begingroup$ Extending language $\mathfrak{L}$ by adding constant symbols for all elements $a\in A$ of the domain of some structure $\mathfrak{A}$ and interpretating these as the original elemnts $a\in A$ is just an equivalent (and sometimes more conveneint if u want to avoid explicit variable assignment functions) way for assigning truth values - to sentences. See for instance "There is a second common approach to defining truth values that does not rely on variable assignment functions.." at en.wikipedia.org/wiki/First-order_logic $\endgroup$ – FWE Aug 25 '14 at 17:52

As per Yoneda's comment, you have to consider the basic definition of interpretation; see Ch.3.4 Semantics, page 64-on, at page 65 :

Let us now present a definition of interpretation for the general case. Consider [the structure] $\mathfrak{A} = \langle A,R_1,\ldots, R_n,F_1,\ldots, F_m, \{ c_i |i \in I \} \rangle$ of a given similarity type $\langle r_1,\ldots, r_n; a_1,\ldots, a_m; |I| \rangle$ [where, see page 54 : ] the $c_i$ are elements of A (constants).

I think that it is better to call them distinguished elements, in order to avoid confusion with the constants $\overline c_i$, which are symbols of the language [see page 56]; of course, the $c_i$'s are the reference of the $\overline c_i$'s.

The corresponding language has predicate symbols $\overline R_1,\ldots,\overline R_n$, function symbols $\overline F_1,\ldots, \overline F_m$ and constant symbols $\overline c_i$. $L(\mathfrak A)$, moreover, has constant symbols $\overline a$ for all $a \in |\mathfrak A|$.

Then see page 67 :

If $\varphi$ is a formula with free variables, say $FV(\varphi) = \{ z_1,\ldots, z_k \}$, then we say that $\varphi$ is satisfied by $a_1,\ldots, a_k \in |\mathfrak{A}|$ if $\mathfrak{A} \vDash \varphi[\overline a_1,\ldots, \overline a_k/z_1,\ldots, z_k]$ [...].

The definition of $\hat{\mathfrak{A}}$, page 112, is nothing new :

Since we will often join all elements of $|\mathfrak A|$ to $\mathfrak A$ as constants, it is convenient to have a special notation for the enriched structure: $\hat{\mathfrak{A}} = (\mathfrak{A}, |\mathfrak{A}|)$.

Thus, we have that : $\hat{\mathfrak{A}} \vDash \varphi (\overline a_1,\ldots, \overline a_n)$ entails $\mathfrak{A} \vDash \varphi(\overline a_1,\ldots, \overline a_n)$ because the enriched strucure $\hat{\mathfrak{A}}$ is obtained from $\mathfrak{A}$ "adding" all the $a \in |\mathfrak{A}|$ as distinguished elements.

In this way, for the strucuture $\hat{\mathfrak{A}} = (\mathfrak{A}, |\mathfrak{A}|)$, the two sets of constants [symbols] : $\{ \overline c_i |i \in I \}$ and $\{ \overline c_i |i \in I \} \cup \{ \overline a_i |$ for all $a \in |\mathfrak{A}| \}$ are the same.

What happened is that we have expanded the original language $L$ to $L'$, adding new symbols : a name for each object in the domain.

Having expanded the language, we have to expand also the strucuture, because a structure $\mathfrak A$ is a domain $A$ plus a function $\mathcal I$ "mapping" the symbols of the language into objects and subsets of $A$.

Thus, we have to extend the mapping $\mathcal I$ in order to take into account the new symbols of the expanded language : but the domain does not change.

See C.C.Chang & H.Jerome Keisler, Model Theory (3rd ed - Dover reprint), page 21 :

The processes of expansion and reduction [of a model or structure] do not change the universe of the model.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.