6
$\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$
0

3 Answers 3

8
$\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$
3
  • $\begingroup$ would you please explain it more ? $\endgroup$
    – Perceptual
    Jan 7, 2016 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, 2016 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$
    – Perceptual
    Jan 7, 2016 at 14:56
1
$\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$
3
  • $\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$
    – Perceptual
    Jan 7, 2016 at 14:53
  • 2
    $\begingroup$ This is true, but not an answer. $\endgroup$ Jan 7, 2016 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$ Jan 7, 2016 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$
3
  • 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$ Dec 13, 2016 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$ Dec 14, 2016 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$ Dec 14, 2016 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.