1
$\begingroup$

Elementary equivalence is an important concept in mathematical logic. Two models $\mathfrak{M}$ and $\mathfrak{N}$ of the same signature are elementarily equivalent, written $\mathfrak{M} \equiv \mathfrak{N}$, provided they make true the same formulae: $$ \mathfrak{M} \equiv \mathfrak{N} \qquad\text{iff}\qquad \{\phi\ |\ \mathfrak{M} \models \phi\} = \{\phi\ |\ \mathfrak{N} \models \phi\} $$

Obviously, one can also define an asymmetric version of this: $$ \mathfrak{M} \preceq \mathfrak{N} \qquad\text{iff}\qquad \{\phi\ |\ \mathfrak{M} \models \phi\} \subseteq \{\phi\ |\ \mathfrak{N} \models \phi\} $$ Now my question: what is the name of this partial order $\preceq$ in the literature and has it been discussed anywhere?

Edit following FPE's suggestions below: $\preceq$ is not terribly interesting a relation, because in classical logic, $\mathfrak{M} \preceq \mathfrak{N}$ already implies that $\mathfrak{M} \equiv \mathfrak{N}$. However I'm investigating a logic without negation where $\{\phi\ |\ \mathfrak{M} \models \phi\}$ is not a complete theory.

$\endgroup$
6
  • 1
    $\begingroup$ $\preceq$ usually means something stronger than $\equiv$: namely $M\preceq N$ iff $M\subseteq N$ and for any $\overline m\in M$ and any formula $\varphi(\overline x)$ we have $M\models \varphi(\overline m)\iff N\models \varphi(\overline m)$. $\endgroup$ – tomasz May 15 '14 at 10:38
  • $\begingroup$ @tomasz Thanks, I'm using $\preceq$ as a generic asymmetric relation symbol. $\endgroup$ – Martin Berger May 15 '14 at 10:41
  • 1
    $\begingroup$ Yeah, I guessed as much. Still, I thought you should be (made) aware that it is very much non-generic in model theory (indeed, you could argue that it is one of the central notions). $\endgroup$ – tomasz May 15 '14 at 10:46
  • 1
    $\begingroup$ That of $M$ being an elementary substructure of $N$, sorry for not spelling it out before. $\endgroup$ – tomasz May 15 '14 at 10:53
  • 1
    $\begingroup$ On the other hand there are some useful partial orders of the form$$\mathfrak M\le\mathfrak N\text{ iff }\{\phi\in\Phi|\mathfrak M\models\phi\}\subseteq\{\phi\in\Phi|\mathfrak N\models\phi\}$$where $\Phi$ is some particular (e.g. syntactically defined) set of formulae such as the set of all Horn formulae, or the set of all positive formulae, or the set of all universal formulae, etc. $\endgroup$ – bof May 15 '14 at 11:00
3
$\begingroup$

Suppose that $\mathcal M\preceq \mathcal N$ (with your definition, I'm not meaning elementary substructure), and let $\phi$ be such that $\mathcal N\models \phi$. Then $\mathcal N\not\models \neg\phi$, i.e. by assumption $\mathcal M\not\models \neg\phi$, which means that $\mathcal M\models \phi$! Hence taking your definition, we have that $\mathcal M\preceq \mathcal N$ implies $\mathcal M\equiv \mathcal N$. This comes from the fact that the theory $T := \mathrm{Th}(\mathcal M)$ of a structure is a complete theory, therefore any theory that contains $T$ is in fact equal to it.

$\endgroup$
5
  • $\begingroup$ Thanks. The logic I'm working with doesn't have the property that $Th(\mathcal{M})$ is complete. Are such logics investigated anywhere? $\endgroup$ – Martin Berger May 15 '14 at 10:56
  • $\begingroup$ Aren't you working in classical logic? How do you define $\mathcal M\models \neg\phi$ in your logic? $\endgroup$ – zarathustra May 15 '14 at 11:01
  • 1
    $\begingroup$ The logic I work with doesn't have negation. Indeed it's about a novel account of negation. If negation is added to the logic, $Th(\mathcal{M})$ becomes a complete theory. $\endgroup$ – Martin Berger May 15 '14 at 11:06
  • 1
    $\begingroup$ @MartinBerger: Maybe you should add this type of information in your original post, because it is of great importance when it comes to answering it! $\endgroup$ – zarathustra May 15 '14 at 11:08
  • $\begingroup$ yes, good point. $\endgroup$ – Martin Berger May 15 '14 at 11:13

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.