2
$\begingroup$

I'm working through the fifth edition of Dirk van Dalen's 'Logic and Structure' and got stuck in section 4.3 on model theory.

Let a structure (of some type) be a tuple $ \mathfrak{A} = (A; R_1, \ldots, R_n; f_1, \ldots f_m; \lbrace a_i : i \in I \rbrace)$, where the $R_j, f_k$ are relations and functions on the set $A$ and $a_i \in A$. Let $\hat{\mathfrak{A}} = (\mathfrak{A}, A)$. As usual, let the diagram of $\mathfrak{A}$ be the set of closed atoms and negated closed atoms true in $\mathfrak{A}$.

Now, I got to understand the proof of (part of) some very simple lemmas. Here's the first one (in van Dalen's numbering it appears as 4.3.8):

$\mathfrak{A}$ is isomorphic to some substructure of $\mathfrak{B} \Rightarrow \hat{\mathfrak{B}}$ is a model of the diagram of $\mathfrak{A}$

The proof offered is clear to me with the exception of the very first step: From the assumption it's supposed to follow (or so it seems to me) that $\mathfrak{A}, \mathfrak{B}$ are isomorphic. But why is that so?

Here's the second one (it is numbered as 4.3.9):

$\hat{\mathfrak{B}}$ is a model of the theory of $\hat{\mathfrak{A}} \Rightarrow \mathfrak{A}$ is isomorphic to some elementary substructure of $\mathfrak{B}$

It's evident how to show that $\mathfrak{A}$ is a substructure of $\mathfrak{B}$. But I have a hard time seeing how to prove that the two structures have the same true sentences with parameters in $\mathfrak{A}$, i.e. that for all $a_1, \ldots, a_n \in A, \mathfrak{A} \models \varphi(\bar{a_1}, \ldots, \bar{a_n})$ iff $\mathfrak{B} \models \varphi(\bar{a_1}, \ldots, \bar{a_n})$.

Any help would be appreciated.

$\endgroup$
1
$\begingroup$

Hint

For 4.3.8, we have that :

$\mathfrak{A}$ is isomorphic to some substructure of $\mathfrak{B}$.

We call this substructure $\mathfrak{B}^*$ and we have that : $\mathfrak{A} \cong \mathfrak{B}^*$ and this means [page 111] (considering the case of relations and simplifying the formula) that :

there is a function $f$ which is bijective and satisfies :

$a\in P^{\mathfrak{A}} $ iff $ \ f(a) \in P^{\mathfrak{B}^{*}}$, for all $P$.

This is the same as :

$\mathfrak A \vDash P(a) \ $ iff $\mathfrak B^* \vDash P(f(a))$.

Now the issue is : how to "move" from $\mathfrak B^* \vDash P(f(a))$ to $\mathfrak B \vDash P(f(a))$ ? This is ensured by the condition of embedding or substructure; see Definition 4.3.4 [page 112] and :

Notation $\mathfrak{A} \subseteq \mathfrak{B}$. Note that it is not sufficient for $\mathfrak{A}$ to be contained in $\mathfrak{B}$ “as a set”; the relations and functions of $\mathfrak{B}$ have to be extensions of the corresponding ones on $\mathfrak{A}$, in the specific way indicated above.

The "closure" of relations and functions in $\mathfrak{B}^*$ holds also for $\mathfrak{B}$.


The same argument applies to 4.3.9 : we have to take into account that $\mathfrak{A} \subseteq \mathfrak{B}$ means not only that $|\mathfrak{A}| \subseteq |\mathfrak{B}|$, but also that relations and functions in $\mathfrak{B}$ defined on elements in $|\mathfrak{A}|$ must be "closed" in $|\mathfrak{A}|$.

$\endgroup$

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.