Results 1 to 3 of 3

Math Help - proof isomorphism implies elementary equivalence

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    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
    Last edited by nsarocket17; October 26th 2009 at 03:08 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by nsarocket17 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2009
    Posts
    125
    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.
    Last edited by Taluivren; October 27th 2009 at 09:46 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. elementary anti-equivalence?
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: August 27th 2011, 07:23 AM
  2. Proof of p implies (q implies p)
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: December 24th 2010, 04:09 AM
  3. [SOLVED] Proof that x^2 = 1 implies x = 1 or x = -1
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: October 19th 2010, 11:22 AM
  4. Replies: 2
    Last Post: September 22nd 2009, 05:56 AM
  5. Replies: 6
    Last Post: January 21st 2009, 02:13 PM

Search Tags


/mathhelpforum @mathhelpforum