So the subject I'm stumbling around a bit is elementary equivalence and elementary substructures. So maybe you could help me sort things out.

So the definitions as I know them.

Structures $M, N$ over signature $S$ are called elementary equivalent if for every formula $\phi$ over $S$, $M \vDash \phi \iff N \vDash \phi$. $M, N$ being isomorphic implies they are elementary equivalent (but not vice versa).

A substructure $N$ of structure $M$ is called an elementary substructure of $M$, if for every formula $\phi$, and for every $b_1, \cdots, b_n \in N: N \vDash \phi (b_1, \cdots, b_n) \iff M \vDash \phi(b_1, \cdots, b_n) $

All is cool up to now. My problem is understanding the examples given to show that a substructure might be elementary equivalent with its structure, but is not an elementary substructure. To my understanding, in order to prove a substructure isn't elementary, you need to find a formula $\phi(v_1 \cdots v_n)$ so that for every $b_1, \cdots, b_n \in N$, so that $M$ won't satisfy $\phi (b_1, \cdots ,b_n)$, and $N$ will, or vice versa.

So an example: $M=(\mathbb Z; +,0)$, and its substructure $N=(2\mathbb Z;+,0)$, and we need to show that $N$ is not an elementary substructure of $M$. So before that, we can see that they are elementary equivalent, as they are isomorphic.

So, for the rebuttal: Lets take $\phi: \forall x \exists y: y+y=x$. But this formula is 'independent' of choosing variables (there are not free variables), so by being vacuously truth it seems that for every $b_1, \cdots, b_n \in N$, we have $N \vDash \phi(b_1, \cdots, b_n)$ and $M \not\vDash \phi(b_1, \cdots, b_n)$ so $N$ is not elementary equivalent.

My question is: Is using this type of formula correct for refutal? Or should I only use formulas with free variables, such as $\phi \exists y: y+y=x$, and then $M \vDash \phi(6)$, but $N$ doesn't.

The second, smaller question: Doesn't $\phi: \forall x \exists y: y+y=x$ show they are not actually elementary equivalent?

I deeply apologize for the wall of text. Any help will be greatly appreciated! Thank you.


The sentence $\forall x\exists y(y+y=x)$ is true in neither $\mathbb{Z}$ nor $2\mathbb{Z}$. So the sentence does not refute elementary equivalence.

But there is no $y$ in $2\mathbb{Z}$ such that $y+y=2$, while there is in $\mathbb{Z}$, so $2\mathbb{Z}$ is not an elementary substructure of $\mathbb{Z}$. There is no real difference between using formulas with free variables, for which we substitute elements of $N$, and sentences in an extended language with symbols for elements of $N$.


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.