models of PA which are isomorphic but not elementarily equivalent? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T02:08:46Z http://mathoverflow.net/feeds/question/26409 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/26409/models-of-pa-which-are-isomorphic-but-not-elementarily-equivalent models of PA which are isomorphic but not elementarily equivalent? Adam 2010-05-30T02:01:29Z 2010-05-30T03:31:46Z <p>On page 164 of his book <strong>Models of Peano Arithmetic</strong>, Kaye states Friedman's Theorem:</p> <p>Let $M{\vDash}PA$ be nonstandard and countable, let $a\in M$ and let $n\in {\mathbb N}$. Then there is a proper initial segment $I\subseteq_c M$ ($\subseteq_c$ means "cofinal in") containing $a$ such that $I\cong M$ and $I&lt;_{\Sigma_n} M$.</p> <p>However, on the next page he writes "Nor can we expect in general to get initial segments $I$ with $M\cong I &lt; M$ and $M\neq I$, i.e., elementary for all formulas. For example if $M=K_T$ (where $T\neq Th({\mathbb N})$ is a complete extension of PA) then $M$ has no proper elementary substructures, and so certainly has no proper elementary initial segments!"</p> <p>I am confused. If two models in the same language are isomorphic, are they not elementarily equivalent? Of course the converse need not be true.</p> <p>An isomorphism of models is a bijective homomorphism of the language's algebraic portion (constants and functions) which preserves <strong>and reflects</strong> all relations of the language (Hodges, <strong>Model Theory</strong>, p5). Therefore by induction on the structure of any ${\mathcal L}_{\omega,\omega}$ formula, the isomorphism will both preserve and reflect it. So an isomorphism preserves <strong>all</strong> formulas (Hodges, Theorem 2.4.3(c)).</p> <p>If the proper initial segment is isomorphic as a model to the entire model, how could any first-order sentence possibly be true in one and not in the other?</p> <p>Thanks,</p> <ul> <li>a</li> </ul> http://mathoverflow.net/questions/26409/models-of-pa-which-are-isomorphic-but-not-elementarily-equivalent/26412#26412 Answer by François G. Dorais for models of PA which are isomorphic but not elementarily equivalent? François G. Dorais 2010-05-30T03:05:25Z 2010-05-30T03:31:46Z <p>There is a major difference between <em>elementary equivalence</em> and <em>elementary embedding</em>. Moreover, in this case, the actual embedding is somewhat ambiguous. First, let me recap some often confused terminology.</p> <p>Two models are <em>elementary equivalent</em> if they satisfy the same first-order sentences. Any two isomorphic models are always elementary equivalent. An <em>elementary embedding</em> is a map j:A&rarr;B such that, for all first-order formulas &phi;(v<sub>1</sub>,...,v<sub>k</sub>) and all a<sub>1</sub>,...,a<sub>k</sub> &isin; A, A &#8871; &phi;(a<sub>1</sub>,...,a<sub>k</sub>) iff B &#8871; &phi;(j(a<sub>1</sub>),...,j(a<sub>k</sub>)). An isomorphism is always an elementary embedding.</p> <p>The notation A &#8826; B means that A is an <em>elementary submodel</em> of B, i.e. the <em>inclusion map</em> A &sube; B is an elementary embedding from A into B. In your context, the isomorphism (or its inverse) is <em>not</em> the proposed elementary embedding, it is the inclusion map which is in question: it is elementary for &Sigma;<sub>n</sub> formulas, but not elementary for all first-order formulas.</p>