3
$\begingroup$

Imagine we have two L-structures $M$ and $N$. For each L-sentence $\phi$ , $M$ models $\phi$ iff $N$ models $\phi$. We call $M$ and $N$ two elementary equivalent L-structures.

We say $M$ and $N$ are isomorphic if there exists a function from $U_M$ to $U_N$ which is 1 to 1 and onto and preserves symbols. ( i mean an embedding which is also onto )

Now i want to prove that if two structures are isomorphic, then they are elementary equivalent.

Note : When we speak about L-formulas, we prove these kind of questions by induction on the complexity of the formulas. but in this case, we have sentences not formulas.

$\endgroup$
6
$\begingroup$

Choose an isomorphism $f$. Prove the more general statement: for any formula $\phi$, if we consider any assignment of values in $M$ to the variables, and the corresponding (via $f$) assignment in $N$, the formula $\phi$ will be satisfied by the one assignment if and only if it is satisfied by the other.

$\endgroup$
  • $\begingroup$ would you please explain it more ? $\endgroup$ – Arman Malekzadeh Jan 7 '16 at 14:11
  • $\begingroup$ @ArmanMalekzade In order to prove it for all formulas, you can induct on the recursive definition of a formula. The base case, for example, includes proving that it holds for formulas of the form $t_1 = t_2$ where $t_1$ and $t_2$ are terms. $\endgroup$ – 6005 Jan 7 '16 at 14:53
  • $\begingroup$ @6005 i found something like that in here : cs.rice.edu/~vardi/comp409/lec20.pdf ( page 3 ) but i can't understand what are the functions mentioned as h and $\alpha$ $\endgroup$ – Arman Malekzadeh Jan 7 '16 at 14:56
2
$\begingroup$

Your notion of isomorphism is incomplete and does not suffice to prove the property you're after.

For the structures $M$ and $N$ to be "isomorphic" in the usual sense, you need not only a bijection between the universes, but the bijection also needs to preserve the meanings of function and predicate symbols.

$\endgroup$
  • $\begingroup$ i fixed that one too... is that correct now ? :) i meant an embedding . i just forgot to write it :) i'm sorry dude $\endgroup$ – Arman Malekzadeh Jan 7 '16 at 14:53
  • 1
    $\begingroup$ This is true, but not an answer. $\endgroup$ – YoTengoUnLCD Jan 7 '16 at 14:59
  • 2
    $\begingroup$ @YoTengoUnLCD: It was an answer to the original question. When the question is "how do I prove A from B" and A doesn't actually follow from B, a perfectly good answer is "you don't, because such-and-such". This holds even if the question uses a non-standard (and confusing) name for its B. $\endgroup$ – Henning Makholm Jan 7 '16 at 15:25
-1
$\begingroup$

The structures (2Z, 0,+) and (Z,0,+) are isomorphic in the language of gropus but are not elementary equivalent. E.g. the closed formula "There exists v such that (v+v=2)" is not satisfied in the first but is satisfied in the second.

$\endgroup$
  • 2
    $\begingroup$ $\exists v\, (v+v=2)$ is not a sentence in the language $\{0,+\}$, since it uses the symbol $2$. If you add the constant $2$ to the language, then you have correctly observed that $(2\mathbb{Z},0,2,+)$ is not elementarily equivalent to $(\mathbb{Z},0,2+)$.... but these structures are not isomorphic, either! $\endgroup$ – Alex Kruckman Dec 13 '16 at 15:58
  • 1
    $\begingroup$ Alex, you are absolutely right. I confused the notion of elementary substructures with elementary equivalent structures! Thanks a lot $\endgroup$ – George Chailos Dec 14 '16 at 21:25
  • 1
    $\begingroup$ Alex, You are absolutely right and thanks a lot. I somehow confused the concept of elementary substructure wilth elementary equivalent structures. The structure (2Z,0, +) is a substructure of (Z,0,+) and isomorphic to it, though it is not an elementary substructure of it (for the reason I provided). But as you pointed out is an elementary equivalent structure to (Z,0,+) since elementary equivalence concerns only closed formulas of the underlying languagey $\endgroup$ – George Chailos Dec 14 '16 at 21:32

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.