ElementaryEmbedding 2002-08-28 23:56:58 2007-11-14 16:51:51 Definition elementary substructure elementary extension elementary chain % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here %\PMlinkescapeword{theory} Let $\tau$ be a signature and $\mathcal{A}$ and $\mathcal{B}$ be two structures for $\tau$ such that $f:\mathcal{A}\to \mathcal{B}$ is an embedding. Then $f$ is said to be \emph{elementary} if for every first-order formula $\phi \in F(\tau)$, we have $$\mathcal{A}\vDash\phi \quad \mbox{iff} \quad \mathcal{B}\vDash \phi.$$ In the expression above, $\mathcal{A}\vDash\phi$ means: if we write $\phi=\phi(x_1,\ldots,x_n)$ where the free variables of $\phi$ are all in $\lbrace x_1,\ldots,x_n\rbrace$, then $\phi(a_1,\ldots,a_n)$ holds in $\mathcal{A}$ for any $a_i\in \mathcal{A}$ (the underlying universe of $\mathcal{A}$). If $\mathcal{A}$ is a substructure of $\mathcal{B}$ such that the inclusion homomorphism is an elementary embedding, then we say that $\mathcal{A}$ is an \emph{elementary substructure} of $\mathcal{B}$, or that $\mathcal{B}$ is an elementary extension of $\mathcal{A}$. \textbf{Remark}. A chain $\mathcal{A}_1\subseteq \mathcal{A}_2\subseteq \cdots \subseteq \mathcal{A}_n \subseteq \cdots$ of $\tau$-structures is called an \emph{elementary chain} if $\mathcal{A}_i$ is an elementary substructure of $\mathcal{A}_{i+1}$ for each $i=1,2,\ldots$. It can be shown (Tarski and Vaught) that $$\bigcup_{i<\omega} \mathcal{A}_i$$ is a $\tau$-structure that is an elementary extension of $\mathcal{A}_i$ for every $i$. %If $\mathcal{A}$ and $\mathcal{B}$ are models of $\mathcal{L}$ such that for each $t\in T$, $A_t\subseteq B_t$, then we say $\mathcal{B}$ is an \emph{elementary extension} of $\mathcal{A}$, or, equivalently, $\mathcal{A}$ is an \emph{elementary substructure} of $\mathcal{B}$ if, whenever $\phi$ is a formula of $\mathcal{L}$ with free variables included in $x_1,\ldots,x_n$ (of types $t_1,\ldots,t_n$) and $a_1,\ldots,a_n$ are such that $a_i\in t_i$ for each $i\leq n$ then: %$$\mathcal{A}\vDash \phi(a_1,\ldots,a_n)\text{iff}\mathcal{B}\vDash \phi(a_1,\ldots,a_n)$$ %If $\mathcal{A}$ and $\mathcal{B}$ are models of $\mathcal{L}$ then a collection of one-to-one functions $f_t:A_t\rightarrow B_t$ for each $t\in T$ is an \emph{elementary embedding} of $\mathcal{A}$ if whenever $\phi$ is a formula of type $\mathcal{L}$ with free variables included in $x_1,\ldots,x_n$ (of types $t_1,\ldots,t_n$) and $a_1,\ldots,a_n$ are such that $a_i\in t_i$ for each $i\leq n$ then: %$$\mathcal{A}\vDash \phi(a_1,\ldots,a_n)\text{iff}\mathcal{B}\vDash \phi(f_{t_1}(a_1),\ldots,f_{t_n}(a_n))$$