3
$\begingroup$

In first order logic, from Ebbinghaus' Mathematical Logic VI.3 on p91, definition of $\Delta$-elementary class of structures:

For a set $\Phi$ of $S$-sentences we call $$ Mod^S \Phi := \{\mathfrak{A}\text{ | $\mathfrak{A}$ is an $S$-structure and $\mathfrak{A} \models \Phi$} \} $$ the class of models of $\Phi$.

3.1 Definition. Let $\mathfrak{R}$ be a class of $S$-structures.

(a) $\mathfrak{R}$ is called elementary if there is an $S$-sentence $\phi$ such that $\mathfrak{R} = Mod^S \phi$.

(b) $\mathfrak{R}$ is called $\Delta$-elementary if there is a set $\Phi$ of $S$-sentences such that $\mathfrak{R} = Mod^S \Phi$

and from VI.4 on p94, definition of elementarily equivalent structures

4.1 Definition. (a) Two $S$-structures $\mathfrak{A}$ and $\mathfrak{B}$ are called elementarily equivalent (written: $\mathfrak{A} \equiv \mathfrak{B}$) if for every $S$-sentence $\phi$ we have $\mathfrak{A} \models \phi$ iff $\mathfrak{B} \models \phi$ .

(b) For an $S$-structure $\mathfrak{A}$, let $Th(\mathfrak{A}) := \{\phi \text{ is a $S$-sentence | $ \mathfrak{A} \models \phi$}\}$ . $Th(\mathfrak{A})$ is called the (first-order) theory of $\mathfrak{A}$.

4.2 Lemma. For two $S$-structures $\mathfrak{A}$ and $\mathfrak{B}$, $\mathfrak{B} \equiv \mathfrak{A}$ iff $\mathfrak{B} \models Th(\mathfrak{A})$.

and on p95, relation between the two concepts:

4.3 Theorem. (b) For every structure $\mathfrak{A}$ , the class $\{\mathfrak{B} \text{ | $\mathfrak{B} \equiv \mathfrak{A}$ }\}$ is $\Delta$-elementary; in fact $\{\mathfrak{B} \text{ | $\mathfrak{B} \equiv \mathfrak{A}$ }\} = Mod^S Th(\mathfrak{A})$. Moreover, $\{\mathfrak{B} \text{ | $\mathfrak{B} \equiv \mathfrak{A}$ }\}$ is the smallest $\Delta$-elementary class which contains $\mathfrak{A}$.

4.3(b) shows that a $\Delta$-elementary class contains, together with any given structure, all elementarily equivalent ones.

  • Is it correct that $Mod^S(\Phi)$ may contain $S$-structures which satisfy formulas in $\Phi$ and might further satisfy formulas outside $\Phi$?

  • In 4.1 Definition (a), is it correct that $\mathfrak{A} \equiv \mathfrak{B}$ iff the two structures have the same theory i.e. $Th(\mathfrak{A}) = Th(\mathfrak{B})$?

  • Does 4.2 Lemma say that $\mathfrak{B} \equiv \mathfrak{A}$ iff $Th(\mathfrak{A}) \subseteq Th(\mathfrak{B})$? (Is that equivalent to $Th(\mathfrak{A}) = Th(\mathfrak{B})$?)

  • In 4.3. Theorem (b), in $\{\mathfrak{B} \text{ | $\mathfrak{B} \equiv \mathfrak{A}$ }\} = Mod^S Th(\mathfrak{A})$, the LHS is the set of $\mathfrak{B}$ s.t. $Th(\mathfrak{A}) = Th(\mathfrak{B})$, and the RHS is set of $\mathfrak{B}$ s.t. $Th(\mathfrak{A}) \subseteq Th(\mathfrak{B})$?

  • Is a minimal $\Delta$-elementary class exactly either one elementarily equivalent class, or the union of several elementarily equivalent classes? (In other words, an elementarily equivalent class can be partially in a minimal $\Delta$-elementary class?)

The last two are my main questions, which gives me a contradiction, possible due to my misunderstanding of relevant concepts as in the first three questions.

Thanks.

$\endgroup$

1 Answer 1

4
$\begingroup$

In order:

  • Yes. There are no negative requirements in the definition of $Mod^S(\Phi)$ - although of course we have $$\varphi\in\Phi, \mathfrak{M}\in Mod^S(\Phi)\quad\implies\quad \mathfrak{M}\not\models\neg\varphi.$$

  • Yes, that's correct, basically by definition.

  • Yes, if $Th(\mathfrak{A})\subseteq Th(\mathfrak{B})$ then $Th(\mathfrak{A})=Th(\mathfrak{B})$. This is due to the nature of negation, and in particular the fact that for every $\mathfrak{C},\varphi$ we have $$\varphi\not\in Th(\mathfrak{C})\quad\iff\neg\varphi\in Th(\mathfrak{C}).$$ Consequently, if $\varphi\in Th(\mathfrak{B})\setminus Th(\mathfrak{A})$ then $\neg\varphi\in Th(\mathfrak{A})\setminus Th(\mathfrak{B})$.

  • Yes.

  • A minimal $\Delta$-elementary class is exactly the same thing as an elementary equivalence class. The situation I think you're describing, where a minimal $\Delta$-elementary class overlaps with multiple distinct elementary equivalence classes, cannot occur.

$\endgroup$
5
  • $\begingroup$ Thanks. What possible cases can be for the relation between Δ-elementary classes (not necessarily minimal) and elementary equivalence classes? $\endgroup$
    – Tim
    Jul 31, 2020 at 16:04
  • 1
    $\begingroup$ @Tim Well, every $\Delta$-elementary class is a union of elementary equivalence classes; the converse fails, though (this is a good exercise). $\endgroup$ Jul 31, 2020 at 16:06
  • $\begingroup$ What is "the converse "? $\endgroup$
    – Tim
    Jul 31, 2020 at 16:53
  • 1
    $\begingroup$ @Tim Noah's statement is: If $C$ is a $\Delta$-elementary class, then $C$ is a union of elementary equivalence classes. The converse of this statement is: If $C$ is a union of elementary equivalence classes, then $C$ is a $\Delta$-elementary class. $\endgroup$ Jul 31, 2020 at 17:08
  • $\begingroup$ @Tim As a hint for that exercise - as Alex says, to prove that there is a union of elementary equivalence classes which is not a $\Delta$-elementary class - work in the empty language and consider the (classes of models associated to the) theories $T_n$, where $T_n$ is the full theory of an $n$-element set (remember that since our language is empty, a structure is just a set). $\endgroup$ Jul 31, 2020 at 17:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .