5
$\begingroup$

I am reading Gorbunov's "Algebraic theory of quasivarieties" and can't prove some statements, which are supposed to be obvious I think. At first, here are some definitions and notations.

For a given $L$-structure $\mathcal{A}$, a subset $X \subseteq A$ and $L_X = L \cup \{c_x \colon x \in X\}$ denote by $\mathcal{A}_X$ the $L_X$-structure, where every constant symbol $c_x$ is interpreted as $x$.

The diagram of $\mathcal{A}$ is the set $D(\mathcal{A})$ of all atomic $L_A$-sentences and their negations that are satisfied by $\mathcal{A}_A$. It is said obvious in the book, that

Proposition: $D(\mathcal{A})$ is satisfied by $L_A$-structure $\mathcal{B}$ iff $a \mapsto c_a^{\mathcal{B}}$ is the embedding of $\mathcal{A}$ into $L$-reduct of $\mathcal{B}$.

For a given signature $L$ denote by $\Gamma(L)$ the signature obtained from $L$ by replacing each $n$-ary functional symbol $f$ with $(n+1)$-ary predicate symbol $R_f$. The graph of $L$-structure $\mathcal{A}$ is the $\Gamma(L)$-structure $\Gamma(\mathcal{A})$ with $A$ as the domain, relations are those from $\mathcal{A}$ and $R_f^{\Gamma(\mathcal{A})}$ for every $n$-ary functional symbol $f \in L$, where $(a_0, \dots, a_n) \in R_f^{\Gamma(\mathcal{A})}$ iff $f^{\mathcal{A}}(a_0, \dots, a_{n-1}) = a_n$.

Any substructure of $\Gamma(\mathcal{A})$ is called a subgraph of $\mathcal{A}$. Finite reduct of a finite subgraph of $\mathcal{A}$ is called local subgraph of $\mathcal{A}$.

$\mathcal{A}$ is said to be locally embeddable into a class $\bf K$ of $L$-structures if every local subgraph of $\mathcal{A}$ is isomorphic to some local subgraph of $\mathcal{B}$, where $\mathcal{B} \in \bf K$.

I can't get the proof of the following

Theorem: If $L$-structure $\mathcal{A}$ is locally embeddable into the class $\bf K$ then it is embeddable into some ultraproduct of $L$-structures from $\bf K$.

Proof:

  1. Local embedding implies that the diagram $D(\mathcal{A})$ is locally satisfiable in $\bf K$.

  2. By compactness $D(\mathcal{A})$ is satisfied by some ultraproduct of $L$-structures from $\bf K$.

All my attempts of proving the proposition or one of the proof steps lead to a lot of writing and it seems really incorrect because I think I am confusing the notations for satisfiability, intepretations in different signatures. I think of a diagram as if we write all possible relations between the elements of $\mathcal{A}$ explicitly without quantifiers.

Questions:

  1. Why is the proposition about diagram satisfiability obvious? My try: assume that $D(\mathcal{A})$ is satisfied by some $L_A$-structure $\mathcal{B}$. In particular, $\mathcal{B} \models \lnot(c_a = c_b)$, for any $a, b \in A \colon a \neq b$, hence this map is injective. Also $\mathcal{B} \models c^{\mathcal{B}}_{f^{\mathcal{A}}(a_1, \dots, a_n)} = f^{\mathcal{B}}(c^{\mathcal{B}}_{a_1}, \dots c^{\mathcal{B}}_{a_n})$ for all functional symbols and $a_1, \dots, a_n \in A$ and $\mathcal{B} \models R^{\mathcal{B}}(c^{\mathcal{B}}_{a_1}, \dots, c^{\mathcal{B}}_{a_n})$ iff $(a_1, \dots a_n) \in R^{\mathcal{A}}$ by definition of the diagram. So this map is the embedding. Conversely, if this map is the embedding into $L$-reduct of $\mathcal{B}$. I think approximately the same argument should be applied here, but this proof seems not rigorous to me and totally not obvious. What is the right way to see the validity of this proposition?

  2. The first step of proof escapes me. Take any local subgraph $\mathcal{A}_{loc}$ of $\mathcal{A}$. I think I am supposed to use the proposition here and here are my thoughts. $\mathcal{A}_{loc}$ is isomorphic to some local subgraph $\mathcal{B}_{loc}$ for some $\mathcal{B} \in \bf K$. In particular it is the embedding, so $D(\mathcal{A}_{loc}) \subset D(\mathcal{A})$ is satisfiable in $\mathcal{B} \in \bf K$. Again, it seems that I do not fully understand the notions of the diagram and satisfiability in different signatures. After that we need to show that every finite subset of $D(\mathcal{A})$ can be ''modeled'' by some local subgraph of $\mathcal{A}$.

  3. I understand that to conclude that $\mathcal{A}$ is embeddable into an ultraproduct from the second step of the proof I need to use the proposition. But in the proposition we are supposing that $D(\mathcal{A})$ is satisfied by some structure of signature $L_A$, while the ultraproduct has signature $L$, so I do not know how should I use it.

Main question: Can you please look through my attempts and explain me, where I am wrong, because I am sure that this is due to my misunderstanding of some notions above. I really want to rigorously prove this statement in order to gain an understanding of all these notions and relations between the structure and its diagram and its satisfiability. It would be great if someone explains me how to prooceed with proving (or at least understanding) each step of the given proof, since I got stuck because my reasoning seems really inexact.

I am sorry for such a long question, but this is due to a big number of definitions. I hope someone who has fine understanding of model theory will quickly understand the point of my question and be able to help me. Thanks in advance!

$\endgroup$
1
$\begingroup$

I am aware that this is an old post and that OP may no longer be interested in an answer, but he or another person might, so:

Let's first address the Proposition: Your approach to show that $a \mapsto c_a^\mathcal B$ is an embedding for every $L_A$-model $\mathcal B$ of $D(\mathcal A)$ works, but as you didn't seem to be convinced, let me spell it out in greater detail:

Let $\tau \colon A \rightarrow B, a \mapsto c_a^\mathcal B$.

For distinct $a,b \in A$ we have $$\mathcal A_A \models \neg c_a \doteq c_b$$ and thus $$\mathcal B \models \neg c_a \doteq c_b$$, i.e. $\tau(a) = c_a^\mathcal B \neq c_b^\mathcal B = \tau(b)$. So $\tau$ is injective.

Given an $L_A$-term t without variables, we have: $$ \mathcal A_A \models t \doteq c_{t^{\mathcal A_A}}.$$ Now $$\mathcal B \models t \doteq c_{t^{\mathcal A_A}}$$ shows that $$t^{\mathcal B} = c_{t^{\mathcal AA}}^{\mathcal B} = \tau(t^{\mathcal A_A}).$$

As a consequence, we have that $\tau(\gamma^{\mathcal A_A}) = \gamma^\mathcal B$ and $$ \begin{eqnarray*}\tau(f^{\mathcal A_A}(a_1, \ldots, a_n)) &=& \tau ( (f c_{a_1} \ldots c_{a_n})^{\mathcal A_A}) \\ &=& (f c_{a_1} \ldots c_{a_n})^\mathcal B \\ &=& f^\mathcal B(\tau(a_1), \ldots, \tau(a_n)) \end{eqnarray*}$$ for all constant-symbols $\gamma \in L_A$, $n$-ary function-symbols $f \in L_A$ and $a_1, \ldots, a_n \in A$.

Also $$ \begin{eqnarray*} R^{\mathcal A_A}(a_1, \ldots, a_n) &\Leftrightarrow& \mathcal A_A \models R c_{a_1} \ldots c_{a_n} \\ &\Leftrightarrow& \mathcal B \models R c_{a_1} \ldots c_{a_n} \\ &\Leftrightarrow& R^\mathcal B(\tau(a_1), \ldots, \tau(a_n)) \end{eqnarray*} $$ for all $n$-ary relation-symbols $R \in L_A$ and $a_1, \ldots, a_n \in A$.

Therefore, $\tau$ is an embedding $\tau: \mathcal A_A \rightarrow \mathcal B$.

Now assume that for an $L_A$ structure $\mathcal B$, $$\tau: A \rightarrow B, a \mapsto c_a^\mathcal B$$ is actually an embedding $\tau: \mathcal A_A \rightarrow B$. Let $\phi$ be an atomic $L_A$ sentence. There are two cases:

  1. $\phi = t_1 \doteq t_2$ for $L_A$-terms $t_1,t_2$ without variables. As $\tau$ is an embedding, we have $\tau(t^\mathcal A) = t^\mathcal B$ for all $L_A$-terms $t$ without variables and thus (as $\tau$ is injective) $$ \begin{eqnarray*} \mathcal A \models t_1 \doteq t_2 &\Leftrightarrow& t_1^\mathcal A = t_2^\mathcal A \\ &\Leftrightarrow& \tau(t_1^\mathcal A) = \tau(t_2^\mathcal A) \\ &\Leftrightarrow& t_1^\mathcal B = t_2^\mathcal B \\ &\Leftrightarrow& \mathcal B \models t_1 \doteq t_2 \end{eqnarray*} $$
  2. $\phi = R t_1 \ldots t_n$ for an $n$-ary relation-symbol $R \in L_A$ and $L_A$-terms $t_1, \ldots, t_n$ without free variables. Now $$ \begin{eqnarray*} \mathcal A \models R t_1 \ldots t_n &\Leftrightarrow& R^\mathcal A(t_1^\mathcal A, \ldots t_n^\mathcal A) \\ &\Leftrightarrow& R^\mathcal B(\tau(t_1^\mathcal A), \ldots, \tau (t_n^\mathcal A)) \\ &\Leftrightarrow& R^\mathcal B(t_1^\mathcal B, \ldots, t_n^\mathcal B) \\ &\Leftrightarrow& \mathcal B \models R t_1 \ldots t_n \end{eqnarray*} $$

If $\phi \in D(\mathcal A)$, this shows $\mathcal A \models \phi \Leftrightarrow \mathcal B \models \phi$ and hence $\mathcal B \models D(\mathcal A)$.


Now, considering the Theorem: After heaving thought about the details, I don't want to type them down right now, as the computation is quite tedious. I'll give an outline instead:

There is a problem with your definition of subgraphs. If $\mathcal A$ contains infinitely many distinct elements corresponding to constant-symbols in $L$, there are no finite substructures of $\Gamma(\mathcal A)$, hence no local subgraphs and the Theorem fails.

You should say that a subraph of $\mathcal A$ is a finite substructure of a finite reduct of $\Gamma(\mathcal A)$ instead. Then you can do the following:

For each finite $T \subset D(\Gamma(\mathcal A))$, let $L_T \subseteq \Gamma(L)$ be the smallest sublanguage s.t. $T$ is an $L_T$-theory. Let $\mathcal A_T$ be the $L_T$-substructure of $\Gamma(\mathcal A)$ consisting of precisely the elements of $A$ corresponding to terms used in $T$. Fix an embedding $\tau_T: \mathcal A_T \rightarrow \Gamma(\mathcal B)$, where the latter is considered as an $L_T$-structure. If $\phi \in D(\mathcal A)$ is an $L(A)$ sentence such that all elements corresponding to terms used in $\phi$ are in $A_T$ and all relation-symbols corresponding to function-symbols in $\phi$ are in $L_T$, then this isomorphism yields $im(\tau_T) \models \phi$, where we formally let $im(\tau_T)$ be an $L_T(A_T)$-structure via $c_a^{im(\tau_T)} = \tau_T(a)$ for $a \in A_T$.

The rest is analogous to the proof of the compactness theorem using ultraproducts.

$\endgroup$
  • $\begingroup$ Thank you, @Stefan, for such a detailed answer! I totally agree with your rigorous proof of the proposition, now it's clear. As regards your proof of the theorem, I need some time to understand it completely. May I ask you a few questions later? $\endgroup$ – Random Jack Feb 20 '15 at 22:03
  • $\begingroup$ @RandomJack Sure, I'm glad to help. $\endgroup$ – Stefan Mesken Feb 21 '15 at 6:30
  • $\begingroup$ After a long absence I'm back, @Stefan. The main point I can't get is connected with different languages and compactness. The class $\mathbf{K}$ contains $L$-structures, so an ultraproduct will also be an $L$-structure. But the proof says (and your proof also uses structures in some extended language like $L_T$) that the diagram (which is a set of $L_A$-sentences) is satisfied by some ultraproduct (which is a $L$-structure). I'm so confused by the question: how some structure in the reduced language can be a model for the theory in the extended language, how should we interpret other symbols? $\endgroup$ – Random Jack Dec 30 '15 at 1:14
  • 1
    $\begingroup$ @RandomJack We just forget about all symbols, that the smaller language doesn't know about. In the situation at hand, it is somewhat useful to first extend $L$ to $L_A$, because this allows us to build a "term model". As we are only interested in an $L$-model, we may then forget about all the additional constant symbols. $\endgroup$ – Stefan Mesken Jan 19 '16 at 18:27

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.