Thread: proof isomorphism implies elementary equivalence

1. proof isomorphism implies elementary equivalence

I need to show that if A and B are isomorphic, then A and B are elementarily equivalent with a proof by induction on formulas.
A and B are first-order structures for a first-order language, L.

A and B are isomorphic if there is a bijection h: domain of A -> domain of B such that
h(c^A)=c^B
h(f^A(a1,...,an))=f^B(a1),...,f^B(an)
(a1,...,an) contained in P^A iff (h(a1),...,h(an)) contained in P^B.

I also am given that
Th(A)={psi l A l= psi}
A is logically equivalent to B iff Th(A) =Th(B)
*where Th(A) means the theory of A

2. Originally Posted by nsarocket17
I need to show that if A and B are isomorphic, then A and B are elementarily equivalent with a proof by induction on formulas.

What are you talking about, anyway?? Groups, rings, algebras, vector spaces, over what field or ring, what equivalent, what formulas...what?!

Tonio

3. Hi nsarocket17,

Here are the hints:

First prove this lemma:
Let $L$ be a language and $\mathcal{A}=\langle A,...\rangle$ and $\mathcal{B}=\langle B,...\rangle$ be $L$-structures and let $h:A \rightarrow B$ be a homomorphism. Then for every term $t=t[v_0,...,v_{n-1}]$ and for all elements $a_0,...,a_{n-1}$ of $A$, the following holds: $h(\bar{t}^{\mathcal{A}}[a_0,...,a_{n-1}])=\bar{t}^{\mathcal{B}}[h(a_0),...,h(a_{n-1})]$.

Proof is very easy, by induction on $t$.

What you're trying to prove is then immediate consequence of the following proposition:
Let $L$ be a language and $\mathcal{A}=\langle A,...\rangle$ and $\mathcal{B}=\langle B,...\rangle$ be $L$-structures, let $h:A \rightarrow B$ be an isomorphism, let $F=F[v_0,...,v_{n-1}]$ be a formula of $L$ and let $a_0,...,a_{n-1}$ be elements of $A$. Then $F$ is satisfied in $\mathcal{A}$ by the sequence $(a_0,...,a_{n-1})$ if and only if $F$ is satisfied in $\mathcal{B}$ by sequence $(h(a_0),...,h(a_{n-1}))$.

Proof of the proposition is again very easy, by induction on $F$. If $F$ is atomic you just use that isomorphisms preserve relations and the lemma above. Induction steps for logical connectives and for quantification are more or less straightforward verifications.