\documentstyle[12pt]{article} \newcommand{\disj}{\mathop{\vee}} \newcommand{\Disj}{\mathop{\bigvee\kern -6pt\bigvee}} \newcommand{\nor}{\oplus} \newcommand{\elemsup}{\succeq} \newcommand{\substruc}{\subseteq} \newcommand{\modq}{{\goth Q}} \newcommand{\modr}{{\goth R}} \newcommand{\moda}{{\goth A}} \newcommand{\modb}{{\goth B}} \newcommand{\modc}{{\goth C}} \newcommand{\modn}{{\goth N}} \newcommand{\augmoda}{{(\moda,a)_{a\in A}}} \newcommand{\blank}{\;\tilde{ }\;} \newcommand{\cont}{{\frak c}} \newcommand{\arrow}{\rightarrow} \newcommand{\conj}{\mathop{\wedge}} \newcommand{\elemequiv}{\equiv} \newcommand{\elemsub}{\preceq} \newcommand{\implies}{\rightarrow} \newcommand{\intersect}{\cap} \newcommand{\isom}{\simeq} \newcommand{\problem}{\par\bigskip\noindent {\bf Problem: }} \newcommand{\proof}{\par\noindent proof:\par} \newcommand{\rationals}{{\Bbb Q}} \newcommand{\rmand}{{\mbox{ and }}} \newcommand{\rmiff}{{\mbox{ iff }}} \newcommand{\reals}{{\Bbb R}} \newcommand{\superset}{\supset} \newcommand{\Union}{\bigcup} \newcommand{\union}{\cup} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newcommand{\res}{\upharpoonright} \newcommand{\propsub}{\subsetneqq} \newcommand{\qed}{\nopagebreak\par\noindent\nopagebreak$\blacksquare$\par} \input amssym.def \input amssym \begin{document} \begin{flushright} A. Miller\\ M776\\ January 1992 \end{flushright} \bigskip \begin{center} First Order Logic \end{center} Let $\emptyset$ denote the empty set ($\{\}$). The finite ordinals are written $$ 0 = \emptyset, 1 =\{\emptyset\}, 2 =\{\emptyset,\{\emptyset\}\}, \ldots, n = \{ 0,1,\ldots,n-1\},\cdots$$ The first infinite ordinal is written ${\omega}=\{ 0,1,2,\ldots\}$. For ordinals $\alpha$ and $\beta$ we write $\alpha<\beta$ for $\alpha \in \beta$. We begin with the syntax of first order logic. The {logical symbols} are $\disj,\neg,\exists,=$ and for each $n\in\omega$ a variable symbol $x_n$. There are also grammatical symbols such as paranthesis and commas that we use to parse things correctly but have no meaning. For clarity we usually use $x,y,z,u,v,$ etc. to refer to arbitrary variables. The {nonlogical symbols} consist of a given set $L$ that may include operation symbols, predicate symbols, and constant symbols. The case where $L$ is empty is referred to as the {language of pure equality}. Each symbol $s\in L$ has a nonnegative integer $\#(s)$ called its {arity} assigned to it. If $\#(s)=0$, then $s$ is a constant symbol. If $f$ is an operation symbol and $\#(f)=n$ then $f$ is an $n$-ary operation symbol. Similarly if $R$ is a predicate symbol and $\#(R)=n$ then $R$ is an $n$-ary predicate symbol. In addition we always have that ``$=$'' is a logical binary predicate symbol. For the {theory of groups} the appropriate language is $L=\{e,\cdot,^{-1}\}$ where ``$e$'' is a constant symbol, so $\#(e)=0$, ``$\cdot$'' is a binary operation symbol, so $\#(\cdot)=2$, and ``$^{-1}$'' is a unary operation symbol, so $\#( ^{-1})=1 $) . For the {theory of partially order sets} we have that $L=\{\leq\}$ where $\leq$ is a binary relation symbol, so $\#(\leq)=2$. Our next goal is to define what it means to be a formula of first order logic. Let $L$ be a fixed language. An expression is a finite string of symbols that are either logical symbols or symbols from $L$. The set of {terms} of $L$ is the smallest set of expressions that contain the variables, constant symbols of $L$ (if any), and is closed under the formation rule: if $t_1,t_2,\ldots,t_n$ are terms of $L$ and $f$ is an $n$-ary operation symbol of $L$, then $t=f(t_1,t_2,\ldots,t_n)$ is a term of $L$. If $L$ has no function symbols then the only terms of $L$ are the variables and constant symbols. So for example if $c$ is a constant symbol, $f$ is a 3-ary operation symbol, $g$ is a binary operation symbol, and $h$ is a unary operation symbol, then $h(f(g(x,h(y)),y,h(c)))$ is a term. The set of {atomic formulas} of $L$ is the set of all expressions of the form $R( t_1,t_2,\ldots,t_n)$, where $t_1,t_2,\ldots,t_n$ are terms of $L$ and $R$ is a $n$-ary predicate symbol of $L$. Since we always have equality as a binary relation we always have atomic formulas of the form $t_1=t_2$. The set of {formulas} of $L$ is the smallest set of expressions that includes the atomic formulas and is closed under the formation rule: if $\theta$ and $\psi$ are $L$ formulas and $x$ is any variable, then $(\theta \disj \psi)$, $\neg\theta$, and $\exists x \,\theta$ are $L$ formulas. We think of other logical connectives as being abbreviations, e.g. $(\theta \implies\psi)$ abbreviates $(\neg\theta \disj \psi)$, and $\forall x \,\theta $ abbreviates $\neg\exists x \,\neg\theta$. We often add and sometimes drop parentheses to improve readability. Also we write $x\not=y$ for the formally correct but harder to read $\neg x=y$. It is common practice to write symbols not only in {prefix} form as above but also in {postfix} and {infix} forms. For example in our example of group theory instead of writing the term $\cdot(x,y)$ we usually write it in infix form $x \cdot y$, and $^{-1}(x)$ is usually written in postfix form $x^{-1}$. Similarly in language of partially ordered sets we usually write $x\leq y$ instead of the prefix form $\leq(x,y)$. Binary relations such as partial orders and equivalence relations are most often written in infix form. We regard the more natural forms we write as abbreviations of the more formally correct prefix notation. Next we want to describe the syntactical concept of {substitution}. To do so we must first describe what it means for an occurrence of a variable $x$ in a formula $\theta$ to be {free}. If an occurrence of a variable $x$ in a formula $\theta$ is not free it is said to be {bound}. Example: $$ (\exists x\,\, x = y \disj x = f(y) )$$ Both occurrences of $y$ are free, the first two occur of $x$ are bound, and the last occurrence of $x$ is free. In the formula: $$ \exists x\,\, (x = y \disj x = f(y) )$$ all three occurrence of $x$ are bound. Formally we proceed as follows. All occurrences of variables in an atomic formula are free. The free occurrences of $x$ in $\neg\theta$ are exactly the free occurrences of $x$ in $\theta$. The free occurrences of $x$ in $(\theta\disj\psi)$ are exactly the free occurrences of $x$ in $\theta$ and in $\psi$. If $x$ and $y$ are distinct variables, then the free occurrences of $x$ in $\exists y\,\,\theta$ are exactly the free occurrences of $x$ in $\theta$. And finally no occurrence of $x$ in $\exists x\,\,\theta$ is free. This gives the inductive definition of free and bound variables. We show that $x$ might occur freely in $\theta$ by writing $\theta(x)$. If $c$ is a constant symbol the formula $\theta(c)$ is gotten by substituting $c$ for all free occurrences (if any) of $x$ in $\theta$. For example: if $\theta(x)$ is $\exists y\; (y=x\conj\forall x\; x=y)$, then $\theta(c)$ is $\exists y\; (y=c\conj\forall x\;x=y)$. We usually write $\theta( x_1,x_2,\ldots,x_n)$ to indicate that the free variables of $\theta$ are amongst the $x_1,x_2,\ldots,x_n$. A formula is called a sentence if no variable occurs freely in it. Our next goal is to describe the semantics of first order logic. A {structure} $\moda$ for the language $L$ is a pair consisting of a set $A$ called the universe of $\moda$ and an assignment or interpretation function from the nonlogical symbols of $L$ to individuals, relations , and functions on $A$. Thus for each constant symbol $c$ in $L$ we have an assignment $c^{\moda}\in A$, for each $n$-ary operation symbol $f$ in $L$ we have a function $f^{\moda}: A^n\arrow A$, and for each $n$-ary predicate symbol $R$ we have a relation $R^{\moda}\subseteq A^n$. The symbol $=$ is always interpreted as the binary relation of equality, which is why we consider it a logical symbol, ie. for any structure $\moda$ we have $=^{\moda}$ is $\{(x,x):x\in A\}$. We use the word structure and {model} interchangeably. For example, suppose $L$ is the language of group theory. One structure for this theory is $\modq=({\Bbb Q},+,-x,0)$ where the universe is the rationals, $\cdot^{\modq}$ is ordinary addition of rationals, $^{-1^{\modq}}$ is the function taking each rational $r$ to $-r$, and $e^{\modq}=0$. Another structure in this language is $\modr=({\Bbb R}^+,\times,{1 \over x},1)$ where the universe is the set of positive real numbers, $\cdot^{\modr}$ is multiplication, $^{-1^{\modr}}$ is the function x goes to $1 \over x$, and $e^{\modr}=1$. Another example is the group $S_n$ of permutations. Here $\cdot^{S_n}$ is composition of functions, $^{-1^{S_n}}$ is the functional which takes each permutation to its inverse, and $e^{S_n}$ is the identity permutation. Of course there are many examples of structures in this language which are not groups. For another example, the language of partially ordered sets is $L=\{\leq\}$ where $\leq$ is a binary relation symbol. Then the following are all $L$-structures which happen to be partial orders: $({\Bbb R},\{(x,y)\in {\Bbb R}^2: x\leq y\})$, $({\Bbb Q},\{(x,y)\in {\Bbb Q}^2: x\geq y\})$, and $({\Bbb N},\{(x,y)\in {\Bbb N}^2: x\mbox{ divides }y\})$. For any nonempty set $A$ and $R\subseteq A^2$, $(A,R)$ is an $L$-structure. If in addition the relation $R$ is transitive, reflexive, and antisymmetric, then $(A,R)$ is a partial order. Next we define what it means for an $L$ structure $\moda$ to model or satisfy an $L$ sentence $\theta$, this is written ${\moda\models\theta}$. For example, $({\Bbb Q},+,0)\models \forall x \exists y \; x\cdot y=e$, because for all $p\in {\Bbb Q}$ there exists $q\in {\Bbb Q}$ such that $p+q=0$. Usually it is not the case that every element of a model has a constant symbol which names it. Let ${L_{\moda}=L\union\{c_a: a\in A\}}$ where each ${c_a}$ is a new constant symbol. Let ${(\moda,a)_{a\in A}}$ be the $L_{\moda}$ structure gotten by augmenting the structure $\moda$ by interpreting each symbol $c_a$ as the element $a$. We begin by defining $(\moda,a)_{a\in A}\models\theta$ where $\theta$ is any $L_\moda$ sentence. The interpretation function can be extended to the variable free terms of $L_{\moda}$ by the rule: $$ (f( t_1,t_2,\ldots,t_n))^{\augmoda} = f^{\augmoda}( t_1^{\augmoda},t_2^{\augmoda},\ldots,t_n^{\augmoda})$$ Hence for each variable free term $t$ we get an interpretation $t^{\augmoda}\in A$. For example if $L=\{S,c\}$ where $S$ is a unary operation symbol and $c$ is a constant symbol, and ${\goth Z}$ is the $L$-structure with universe ${\Bbb Z}$ and where $S^{\goth Z}(x)=x+1$ and $c^{\goth Z}=0$, then $S(S(S(S(c))))^{\goth Z}=4$. Our definition of $\models$ is by induction on the {logical complexity} of the sentence $\theta$, i.e. the number of logical symbols in $\theta$. \begin{enumerate} \item $\augmoda\models R(t_1,\ldots,t_n)$ iff $( t_1^{\augmoda},\ldots,t_n^{\augmoda})\in R^{\augmoda}$. \item $\augmoda\models\neg\theta$ iff not $\augmoda\models\theta$. \item $\augmoda\models(\theta\disj\psi)$ iff $\augmoda\models\theta$ or $\augmoda\models\psi$. \item $\augmoda\models\exists x\,\theta(x)$ iff there exist an $b$ in the universe $A$ such that $\augmoda\models\theta(c_b)$. \end{enumerate} If $\theta$ is an $L$-sentence and $\moda$ is and $L$-structure, then we define {$\moda\models\theta$} iff $\theta$ is true in the augmented structure, ie. $\augmoda\models\theta$. If $L_1 \subseteq L_2$ and $\moda$ is a $L_2$ structure, then the reduct of $\moda$ to $L_1$, written ${\moda\res L_1}$, is the $L_1$ structure with the same universe as $\moda$ and same relations, operations, and constants as $\moda$ for the symbols of $L_1$. \begin{lemma} Let $L_1\subseteq L_2$ and $\moda$ be an $L_2$ structure. Then for any $\theta$ an $L_1$ sentence, $$\moda\models\theta \mbox{ iff } \moda\res L_1\models\theta$$ \end{lemma} \proof Prove by induction on the number of logical symbols in the sentence that for any $L_{1\moda}$ sentence $\theta$: $$(\moda,a)_{a\in A}\models\theta \mbox{ iff } (\moda,a)_{a\in A}\res L_{1\moda} \models\theta$$ Let $\moda_2=(\moda,a)_{a\in A}$ and $\moda_1=(\moda,a)_{a\in A}\res L_{1\moda}$. atomic sentences: By induction on the size of the term, for any $L_{1\moda}$ variable free term $t$ we have that $t^{\moda_1}=t^{\moda_2}$. For any $n$-ary relation symbol $R$ in $L_1$ we have $R^{\moda_1}=R^{\moda_2}$ (since $\moda_1$ is a reduct of $\moda_2$). Hence for any atomic $L_{1\moda}$-sentence $R(t_1,\ldots,t_n)$, $$\moda_1\models R(t_1,\ldots,t_n) \mbox{ iff } \langle t_1^{\moda_1},\ldots t_n^{\moda_1}\rangle \in R^{\moda_1} \mbox{ iff } \langle t_1^{\moda_2},\ldots t_n^{\moda_2}\rangle \in R^{\moda_2} $$ $$\mbox{ iff } \moda_2\models R(t_1,\ldots,t_n) $$ negation: $\moda_1\models \neg\theta$ iff not $\moda_1\models \theta$ iff (by induction) not $\moda_2\models \theta$ iff $\moda_2\models \neg\theta$. disjunction: $\moda_1\models (\theta\disj\rho)$ iff $\moda_1\models \theta$ or $\moda_1\models\rho)$ iff (by induction) $\moda_2\models \theta$ or $\moda_2\models\rho)$ iff $\moda_2\models (\theta\disj\rho)$. existential quantifier: $\moda_1\models \exists x\theta(x)$ iff there exists $a\in A$ such that $\moda_1\models \theta(c_a)$ iff there exists $a\in A$ such that $\moda_2\models \theta(c_a)$ iff $\moda_2\models \exists x\theta(x)$. \qed %%%%% compactness \begin{center} Compactness Theorem \end{center} The compactness theorem (for countable languages) was proved by Kurt G\"{o}del in 1930. Malcev extended it to uncountable languages in 1936. The proof we give here was found by Henkin in 1949. We say that a set of $L$ sentences $\Sigma$ is {finitely satisfiable} iff every finite subset of $\Sigma$ has a model. $\Sigma$ is {complete} iff for every $L$ sentence $\theta$ either $\theta$ is in $\Sigma$ or $\neg\theta$ is in $\Sigma$. \begin{lemma} For every finitely satisfiable set of $L$ sentences $\Sigma$ there is a complete finitely satisfiable set of $L$ sentences $\Sigma^\prime\supseteq \Sigma$. \end{lemma} \proof Let $B=\{Q:Q\supseteq \Sigma$ is finitely satisfiable$\}$. $B$ is closed under unions of chains, because if $C\subseteq B$ is a chain, and $F\subseteq \union C$ is finite then there exists $Q\in C$ with $F\subseteq Q$, hence $F$ has a model. By the maximum principal, there exist $\Sigma^\prime\in B$ maximal. But for every $L$ sentence $\theta$ either $\Sigma^\prime\union\{\theta\}$ is finitely satisfiable or $\Sigma^\prime\union\{\neg\theta\}$ is finitely satisfiable. Otherwise there exists finite $F_0,F_1\subseteq\Sigma^\prime$ such that $F_0\union\{\theta\}$ has no model and $F_1\union\{\neg\theta\}$ has no model. But $F_0\union F_1$ has a model $\moda$ since $\Sigma$ is finitely satisfiable. Either $\moda\models\theta$ or $\moda\models\neg\theta$. This is a contradiction. \qed \begin{lemma} If $\Sigma$ is a finitely satisfiable set of $L$ sentences, and $\theta(x)$ is an $L$ formula with one free variable $x$, and $c$ a new constant symbol (not in $L$), then $\Sigma \union \{(\exists x \,\theta (x)) \implies \theta(c)\}$ is finitely satisfiable \end{lemma} \proof This new sentence is called a {Henkin sentence} and $c$ is called the {Henkin constant}. Suppose it is not finitely satisfiable, then there exists $F\subseteq\Sigma$ finite such that $F\union\{(\exists x \,\theta (x)) \implies \theta(c)\}$ has no model. Let $\moda$ be an $L$-structure modeling $F$. Since the constant $c$ is not in the language $L$ we are free to interpret it any way we like. If $\moda\models\exists x \,\theta (x)$ choose $c\in A$ so that $(\moda,c)\models\theta(c)$, otherwise choose $c\in A$ arbitrarily. In either case $(\moda,c)$ models $F$ and the Henkin sentence. \qed \par\medskip We say that a set of $L$ sentences $\Sigma$ is {Henkin} iff for every $L$ formula $\theta(x)$ with one free variable $x$, there is a constant symbol $c$ in $L$ such that $(\exists x \,\theta (x)) \implies \theta(c) \in \Sigma$. \begin{lemma} If $\Sigma$ is a finitely satisfiable set of $L$ sentences, then there exists $\Sigma^\prime\supseteq \Sigma$ with $L^\prime\supseteq L$ and $\Sigma^\prime$ a finitely satisfiable Henkin set of $L^\prime$ sentences. \end{lemma} \proof For any set of $\Sigma$ of $L$ sentence, let $$\Sigma^*=\Sigma\union\{ (\exists x \,\theta (x)) \implies \theta(c_{\theta}): \theta(x)\mbox{ an }L\mbox{ formula with one free variable}\}$$ The language of $\Sigma^*$ contains a new constant symbol $c_{\theta}$ for each $L$ formula $\theta(x)$. $\Sigma^*$ is finitely satisfiable, since any finite subset of it is contained in a set of the form $$F\union\{(\exists x \,\theta_1 (x)) \implies \theta(c_{\theta_1}),\ldots, (\exists x \,\theta_n (x)) \implies \theta(c_{\theta_n})\}$$ where $F\subseteq\Sigma$ is finite. To prove this set has a model use induction on $n$ and note that from the point of view of $$\Sigma\union\{(\exists x \,\theta_1 (x)) \implies \theta(c_{\theta_1}),\ldots, (\exists x \,\theta_{n-1} (x)) \implies \theta(c_{\theta_{n-1}})\}$$ $c_{\theta_n}$ is a new constant symbol, so we can apply the last lemma. Now let $\Sigma_0=\Sigma$ and let $\Sigma_{m+1}=\Sigma_m^*$. Then $\Sigma^\prime=\union_{m=0,1,\ldots}\Sigma_m$ is Henkin and finitely satisfiable, since it is the union of a chain of finitely satisfiable sets. \qed \par\medskip If $\Sigma$ is a set of $L$ sentences, then the {canonical structure} $\moda$ built from $\Sigma$ is the following. Let $X$ be the set of all variable free terms of $L$. For $t_1,t_2\in X$ define $t_1\sim t_2$ iff $(t_1 = t_2) \in \Sigma$. Assuming that $\sim$ is an equivalence relation let $[t]$ be the equivalence class of $t\in X$. The universe of the canonical model $\moda$ is the set of equivalence classes of $\sim$. For any $n$-ary relation symbol $R$ we define $([t_1],[t_2],\ldots,[t_n])\in R^{\moda}$ iff $R(t_1,t_2,\ldots,t_n)\in \Sigma$. We define $f^{\moda}([t_1],[t_2],\ldots,[t_n])=[f(t_1,t_2,\ldots,t_n)]$. and $c^{\moda}=[c]$ for $n$-ary operation symbols $f$ and constant symbols $c$. \begin{lemma} If $\Sigma$ is a finitely satisfiable complete Henkin set of $L$ sentences, then the canonical model $\moda$ built from $\Sigma$ is well defined and for every $L$ sentence $\theta$, $\moda\models \theta$ iff $\theta \in \Sigma$. \end{lemma} \proof First we show that $\sim$ is an equivalence relation. Suppose $t,t_1,t_2,t_3$ are variable free terms. $t\sim t$: If $t=t\notin \Sigma$ then, since $\Sigma$ is complete we have that $\neg t=t\in \Sigma$. But clearly $\neg t=t$ has no models and so $\Sigma$ is not finitely satisfiable. $t_1\sim t_2$ implies $t_2\sim t_1$: If not by completeness of $\Sigma$ we must have that $t_1=t_2$ and $\neg t_2=t_1$ are both in $\Sigma$. But then $\Sigma$ was not finitely satisfiable. ($t_1\sim t_2$ and $t_2\sim t_3$) implies $t_1\sim t_3$: If not by completeness of $\Sigma$ we must have that $t_1=t_2$, $t_2=t_3$, and $\neg t_1=t_3$ are all in $\Sigma$. But then $\Sigma$ was not finitely satisfiable. So $\sim$ is an equivalence relation. Next we show that it is a congruence relation. Suppose $t_1,\ldots,t_n,t_1^\prime,\ldots,t_n^\prime$ are variable free terms and $f$ is an n-ary operation symbol. Then if $t_1\sim t_1^\prime,\ldots,t_n\sim t_n^\prime$ then $f(t_1,\ldots,t_n)\sim f(t_1^\prime,\ldots,t_n^\prime)$. This amounts to saying if $\{t_1=t_1^{\prime},\ldots,t_n=t_n^{\prime}\}\subseteq\Sigma$, then $f(t_1,\ldots,t_n)= f(t_1^\prime,\ldots,t_n^\prime)\in\Sigma$. But again since $\Sigma$ is complete we would have $$f(t_1,\ldots,t_n)\not= f(t_1^\prime,\ldots,t_n^\prime)\in\Sigma$$ but $\{t_1=t_1^{\prime},\ldots,t_n=t_n^{\prime}, f(t_1,\ldots,t_n)\not= f(t_1^\prime,\ldots,t_n^\prime)\}$ has no models and so $\Sigma$ wouldn't be finitely satisfiable. By a completely similar argument: Suppose $t_1,\ldots,t_n,t_1^\prime,\ldots,t_n^\prime$ are variable free terms and $R$ is an n-ary operation symbol. Then if $t_1\sim t_1^\prime,\ldots,t_n\sim t_n^\prime$ then $R(t_1,\ldots,t_n)\in\Sigma$ iff $R(t_1^\prime,\ldots,t_n^\prime)\in\Sigma$. This shows the canonical model is well defined. Now we prove by induction on the number of logical symbols for any $L$ sentence $\theta$ $$\moda\models \theta \iff \theta \in \Sigma$$ The atomic formula case is by definition. $\neg$: $\moda\models\neg\theta$ iff not $\moda\models\theta$ iff(by induction) not $\theta\in\Sigma$ iff(by completeness) $\neg\theta\in\Sigma$. $\disj$:$\moda\models(\theta\disj\rho)$ iff $\moda\models\theta$ or $\moda\models\rho$ iff(by induction) $\theta\in\Sigma$ or $\rho\in\Sigma$ iff $(\theta\disj\rho)\in\Sigma$. This last ``iff'' uses completeness and finite satisfiability of $\Sigma$. For left to right, if $(\theta\disj\rho)\notin\Sigma$ then by completeness $\neg(\theta\disj\rho)\in\Sigma$ but $\{\theta,\rho,\neg(\theta\disj\rho)\}$ has no model. For right to left, if $\theta\notin\Sigma$ and $\rho\notin\Sigma$, then by completeness $\neg\theta\in\Sigma$ and $\neg\rho\in\Sigma$, but $\{(\theta\disj\rho),\neg\theta,\neg\rho\}$ has no model. $\exists$: $\moda\models\exists x\theta(x)$ implies there exists $a\in A$ such that $\moda\models\theta(a)$ implies(by induction) $\theta(a)\in\Sigma$ implies $\exists x\theta(x)\in\Sigma$, (since otherwise $\neg\exists x\theta(x)\in\Sigma$ but $\{\neg\exists x\theta(x),\theta(a)\}$ has no model. Hence $\moda\models\exists x\theta(x)$ implies $\exists x\theta(x)\in\Sigma$. For the other direction suppose $\exists x\theta(x)\in\Sigma$, then since $\Sigma$ is Henkin for some constant symbol $c$ we have $(\exists x\theta(x))\implies\theta(c)\in\Sigma$. Using completeness and finitely satisfiable we must have $\theta(c)\in\Sigma$. By induction $\moda\models\theta(c)$ hence $\moda\models\exists x\theta(x)$. \qed \par\bigskip \noindent {\bf Compactness Theorem.} For any language $L$ and set of $L$ sentences $\Sigma$, \centerline{$\Sigma$ has a model iff every finite subset of $\Sigma$ has a model.} \bigskip \proof First Henkinize $\Sigma$, then complete it. Then take its canonical model. \qed \bigskip \begin{center} Some naive set theory \end{center} Define $ {|X|=|Y|}$ iff there is a one-to-one onto map from $X$ to $Y$. We say $X$ and $Y$ have the same cardinality. Define $ {|X|\leq |Y|}$ iff there is a one-to-one map from $X$ to $Y$. We may think of the cardinal numbers as these equivalence classes which we will denote with greek letters $\kappa$ or $\gamma$. The axiom of choice implies that for any two sets $X$ and $Y$ either $|X|\leq |Y|$ or $|Y|\leq |X|$. The Cantor-Bendixson Theorem says that if $|X|\leq |Y|$ and $|Y|\leq |X|$ then $|X|=|Y|$. The first infinite cardinal is written either $\omega$ or $\aleph_0$. A set is {countable} iff it is either finite or of the same cardinality as $\omega$. A set is {uncountable} iff it is not countable. $ {{\Bbb R}}$ is the set of real numbers and we use $ {{\cont} = |\Bbb R|}$ to denote its cardinality which is also called the cardinality of the continuum. The first uncountable cardinal is written either $\aleph_1$ or $\omega_1$. Cantor's continuum hypothesis is the assertion that $\cont=\aleph_1$. A basic fact of the cardinality is that the union of $\kappa$ many sets of cardinality $\kappa$ has cardinal $\kappa$, eg the countable union of countable sets is countable. A more precisely statement would be: for any infinite cardinal $\kappa$ and if $\{X_i:i\in I\}$ is family of sets such that $|X_i|\leq\kappa$ for each $i\in I$ and $|I|\leq\kappa$, then $|\Union\{X_i:i\in I\}|\leq\kappa$. For cardinals $\kappa$ and $\gamma$ we define $ {\kappa +\gamma}$ to be the cardinality of the union of $A$ and $B$ where $A$ and $B$ are disjoint and $|A|=\kappa$ and $|B|=\gamma$. Note that if at least one of $\kappa$ and $\gamma$ is infinite, then $\kappa+\gamma=max(\kappa,\gamma)$. For $\kappa$ a cardinal $\kappa^{<\omega}$ is the set of all finite sequences of elements of $\kappa$. It is a fact that if $\kappa$ is an infinite cardinal, then $|\kappa^{<\omega}|=\kappa$. The reason is that $\kappa\times\kappa$ has cardinality $\kappa$ since it the $\kappa$ union of the sets ${\alpha}\times\kappa$ for $\alpha\in\kappa$. Similarly $\kappa\times\kappa\times\kappa=\kappa^3$ has cardinality $\kappa$. But then $|\kappa^{<\omega}|=\kappa$, since $\kappa^{<\omega}=\Union\{\kappa^n:n\in\omega\}$ is a countable union of sets of cardinality $\kappa$. \bigskip \begin{center} Lowenheim-Skolem Theorems \end{center} The first version of the Lowenheim-Skolem Theorem was proved in 1915. The final version that is presented here was developed by Tarski in the 1950's. \begin{lemma} The number of $L$ formulas is $|L|+\aleph_0$. \end{lemma} \proof There are only countably many logical symbols. Hence if $\kappa=|L|+\aleph_0$ then every formula may be regarded as an element of $\kappa^{<\omega}$ and we know $|\kappa^{<\omega}|=\kappa$. \qed For any theory $T$ in a language $L$ if $T$ has a model, then it has one of cardinality less than or equal to $|L|+\aleph_0$. This is because the canonical model of the completion of Henkinization of T has cardinality $\leq|L|+\aleph_0$. $ {{\moda} \substruc {\modb}}$ means that ${\moda}$ is a {substructure} of ${\modb}$, equivalently ${\modb}$ is an {extension} or {superstructure} of ${\moda}$. This means that both structures are in the same language $L$, $A \subseteq B$, for every $n$-ary relation symbol $R$ of $L$, $ R^{\moda} = R^{\modb} \intersect A^n$, for every $n$-ary function symbol $f$ of $L$, $f^{\moda} = f^{\modb} \res A^n $, and for every constant symbol $c$ of $L$, $ c^{\moda} = c^{\modb} $. $ {{\moda} \elemsub {\modb}}$ means that ${\moda}$ is an {elementary substructure} of ${\modb}$, equivalently ${\modb}$ is an {elementary extension} of ${\moda}$. This means that ${\moda} \subseteq {\modb}$ and for every formula $\theta(x_1,x_2,\ldots,x_n)$ of the language $L$ and for every $a_1,a_2,\ldots,a_n \in A$ we have $$({\moda },a)_{a\in A} \models \theta (c_{a_1},c_{a_2},\ldots,c_{a_n}) \mbox{ iff } ({\modb },a)_{a\in A} \models \theta (c_{a_1},c_{a_2},\ldots,c_{a_n})$$ To ease the notational complexity we will write $ {\moda\models\theta(a_1,\ldots,a_n)}$ instead of $({\moda },a)_{a\in A} \models \theta (c_{a_1},c_{a_2},\ldots,c_{a_n})$. It should be kept in mind that the language $L$ may have no constant symbols in it. \problem Let $\moda=(\omega,<)$ and let $\modb=(Evens,<)$. Show that $\modb\subseteq\moda$ but $\modb$ is not an elementary substructure of $\moda$. \begin{lemma} (Tarski-Vaught criterion) Suppose $\moda\subseteq\modb$ are $L$ structures and for every $L$ formula $\theta(x,y_1,y_2,\ldots,y_n)$, for all $a_1,a_2,\ldots,a_n \in A$, and $b \in B$ $$ \modb\models\theta(b,a_1,a_2,\ldots,a_n)\mbox{ implies there exists } a \in A\,\,\, \modb\models\theta(a,a_1,a_2,\ldots,a_n)$$ then $\moda\elemsub\modb$. \end{lemma} \proof The proof is by induction on the number of logical symbols in the formula $\theta$. The atomic formula case is trivial because $\moda$ is a substructure of $\modb$. $\neg$: $\moda\models\neg\theta$ iff not $\moda\models\theta$ iff(by induction) not $\modb\models\theta$ iff $\modb\models\neg\theta$. $\disj$: $\moda\models(\theta\disj\rho)$ iff $\moda\models\theta$ or $\moda\models\rho$ iff(by induction) $\modb\models\theta$ or $\modb\models\rho$ iff $\modb\models(\theta\disj\rho)$. $\exists$: $\moda\models\exists x \theta(x,a_1,\ldots,a_n)$ implies there exists $a\in A$ such that $$\moda\models \theta(a,a_1,\ldots,a_n)$$ which implies (by induction) $\modb\models \theta(a,a_1,\ldots,a_n)$. For the other direction we use the criterion. $\modb\models\exists x \theta(x,a_1,\ldots,a_n)$ implies there exists $a\in A$ such that $$\modb\models\theta(a,a_1,\ldots,a_n).$$ Hence by induction $\moda\models\theta(a,a_1,\ldots,a_n)$ and so $\moda\models\exists x \theta(x,a_1,\ldots,a_n)$. \qed \begin{lemma} Suppose $X\subseteq B$ and $|X|=\kappa \geq |L|+\aleph_0$ where $\modb$ is an $L$ structure. Then there exists $X^*\supseteq X, |X^*|=\kappa$, and for every formula $\theta(x,y_1,y_2,\ldots,y_n)$, for all $a_1,a_2,\ldots,a_n \in X$, and $b \in B$ $$ \modb\models\theta(b,a_1,a_2,\ldots,a_n)\implies \exists a \in X^*\,\, \modb\models\theta(a,a_1,a_2,\ldots,a_n)$$ \end{lemma} \proof A linear order $( L, \leq)$ is a {wellorder} iff for every nonempty $X\subseteq L$ there exists $x \in X$ such that for every $y \in X$ $x \leq y$. The axiom of choice implies that every set can be wellordered. Fix $\leq$ a wellordering of $B$. For any $L$ formula $\theta(x,y_1,\ldots,y_n)$ and $a_1,\ldots,a_n\in B$ define $a_{\theta(x,a_1,\ldots,a_n)}\in B$ to be the $\leq$ least element $b$ of $B$ such that $\modb\models\theta(b,a_1,\ldots,a_n)$ if one exists otherwise let it be arbitrary. Now let $X_0=X$, $L_0=L$, and for any $m<\omega$ let $X_{m+1}=$ $$\{a_{\theta(x,a_1,\ldots,a_n)}:\theta(x,y_1,\ldots,y_n) \mbox{ is an } L_m\mbox{ formula and }\{ a_1,\ldots,a_n\}\subseteq X_m\}$$ and let $L_{m+1}\superset L_m$ be the language with all these new constant symbols adjoined. Clearly if $X_m$ and $L_m$ have cardinality $\kappa$ then so do $X_{m+1}$ and $L_{m+1}$, since $|\kappa^{<\omega}|=\kappa$. Let $X^*=\union_{m<\omega}X_m$, then it has cardinality $\kappa$ since it is the countable union of sets of cardinality $\kappa$. For every formula $\theta(x,a_1,a_2,\ldots,a_n)$ there exist some $m<\omega$ such that $\{a_1,a_2,\ldots,a_n\}\subseteq X_m$ and so the criterion for $\theta(x,a_1,a_2,\ldots,a_n)$ is satisfied at stage $m+1$. \qed \bigskip Definition: $ {|{\moda}|}$ is the cardinality of the universe $A$ of ${\moda}$. \par\bigskip \noindent {\bf Downward Lowenheim-Skolem Theorem.} Suppose ${\modb}$ is an infinite structure in the language $L$, $\kappa$ is a cardinal such that $\aleph _0 + |L| \leq \kappa \leq |{\modb}|$, and $X\subseteq B$ such that $|X|\leq \kappa$. Then there is a structure ${\moda}$ such that ${\moda} \elemsub {\modb}$, $X\subseteq A$, and $|{\moda}|=\kappa$. \bigskip \proof By the lemma there exists $X^*\supseteq X$ of cardinality $\kappa$ satisfying the criterion. But note that the criterion implies that $X^*$ is closed under the operations of $\modb$. (Just look at the sentence $\exists x\;\; x=f(a_1,\ldots,a_n)$.) Consequently there is a substructure $\moda$ of $\modb$ with universe $A=X^*$. By the Tarski-Vaught criterion $\moda\elemsub\modb$. \qed \par\bigskip $ {{\moda} \isom {\modb}}$ means that ${\moda}$ and ${\modb}$ are {isomorphic}, that is, there is a bijection $ j : A \arrow B$ such that for every n-ary relation symbol R and for every $a_1,a_2,\ldots,a_n \in A$, $$\langle a_1,a_2,\ldots,a_n\rangle \in R^{\moda} \mbox{ iff } \langle j(a_1),j(a_2), \ldots,j(a_n)\rangle \in R^{\modb} $$ and for every n-ary function symbol $f$ and for every $a_1,a_2,\ldots,a_n \in A$, $$j(f^{\moda}(a_1,a_2,\ldots,a_n))= f^{\modb}(j(a_1),j(a_2),\ldots,j(a_n))$$ (for n=0 this means that for every constant symbol $c$, $j( c^{\moda}) = c^{\modb}$.) \begin{lemma} Suppose $j$ is an isomorphism between the $L$ structures $\moda$ and $\modb$. Then for any $L$ formula $\theta(x_1,x_2,\ldots,x_n)$ and any $a_1,a_2,\ldots,a_n \in A$, $$\moda\models \theta(a_1,a_2,\ldots,a_n) \mbox{ iff }\modb\models \theta(j(a_1),j(a_2),\ldots,j(a_n))$$ \end{lemma} \proof First show by induction that for every $L$-term $\tau(x_1,\ldots,x_n)$ and sequence $a_1,\ldots,a_n\in A$ that $j(\tau^\moda(a_1,\ldots,a_n)))=\tau^\modb(j(a_1),\ldots,j(a_n)$. The proof of the lemma is by induction on the logical complexity of $\theta$. For atomic formula it follows from the definition of isomorphism. The propositional steps are easy and the quantifier step is handled by using that $j$ is onto. \qed A map $j:\moda\arrow\modb$ is an {elementary embedding} iff it is an isomorphism of $\moda$ with an elementary substructure of $\modb$, we write $ {\moda\elemsub^j\modb}$. \begin{lemma} A map $j:\moda\arrow\modb$ is an elementary embedding iff for any formula $\theta(x_1,x_2,\ldots,x_n)$ and any $a_1,a_2,\ldots,a_n \in A$, $$\moda\models \theta(a_1,a_2,\ldots,a_n) \mbox{ iff }\modb\models \theta(j(a_1),j(a_2),\ldots,j(a_n))$$ \end{lemma} \proof Just unravel the definitions. \unitlength=1.00mm \linethickness{0.4pt} \begin{picture}(55,20) \put(0,0){\framebox(55,20)[]{}} \put(10.00,10.00){\circle{10.00}} \put(38.00,10.00){\circle{10.00}} \put(39.00,10.00){\circle{15.00}} \put(11.00,10.00){\vector(1,0){26.00}} \put(24.00,13.00){\makebox(0,0)[cc]{$j$}} \put(10.00,10.00){\makebox(0,0)[cc]{$\moda$}} \put(43.00,13.00){\makebox(0,0)[cc]{$\modb$}} \put(39.00,10.00){\makebox(0,0)[cc]{$\moda^\prime$}} \end{picture} \qed \begin{lemma} Suppose that $\moda\elemsub^j\modb$, then there exists a structure $\modb^\prime$ isomorphic to $\modb$ such that $\moda\elemsub\modb^{\prime}$. Furthermore $j$ is the restriction of this isomorphism to $A$. \end{lemma} \proof Let $B^\prime$ be a superset of $A$ such that the map $j$ can be extended to a bijection $j:B^{\prime}\arrow B$, (which we also will call $j$). Now define $f^{\modb^{\prime}}$ and $R^{\modb^{\prime}}$ in such away as to make $j$ an isomorphism. This means that $$R^{\modb^{\prime}}=\{(b_1,\ldots,b_n): (j(b_1),\ldots,j(b_n))\in R^{\modb}\}$$ $$f^{\modb^{\prime}}(b_1,\ldots,b_n)= j^{-1}(f^{\modb}(j(b_1),\ldots,j(b_n))$$ Now check that $\modb^{\prime}$ works. \qed The {elementary diagram} of $\moda$ is defined as follows: $$D(\moda)=\{\theta:\theta \mbox{ is an } L_{\moda} \mbox{ sentence and } (\moda,a)_{a\in A}\models\theta\}$$ This means that $ {D(\moda)}$ is the theory of $\moda$ with constants adjoined for each element of the universe. \begin{lemma} If $\moda$ is an $L$ structure and $\modb$ is an $L_{\moda}$ structure such that $\modb\models D(\moda)$, then there is a $j$ such that $\moda\elemsub^j\modb\res L$. \end{lemma} \proof Define $j:A\arrow B$ by $j(a)=c_a^{\modb}$. \qed \par\bigskip \noindent {\bf Upward Lowenheim-Skolem Theorem.} For any infinite structure ${\moda}$ in the language $L$ and cardinal $\kappa$ such that $|{\moda}| + |L| \leq \kappa$, there is a structure ${\modb}$ such that ${\moda} \elemsub {\modb}$ and $|{\modb}|$=$\kappa$. \bigskip \proof Let $\Sigma=D(\moda)\union\{c_{\alpha}\not=c_{\beta}:\alpha,\beta<\kappa, \alpha\not=\beta\}$ where the $c_{\alpha}$ are totally new constant symbols. $\Sigma$ is finitely satisfiable. To see this let $F\subseteq\Sigma$ be finite. Then there exists a finite $G\subseteq\kappa$ such that $F\subseteq D(\moda)\union \{c_{\alpha}\not=c_{\beta}:\alpha,\beta\in G, \alpha\not=\beta\}$. Since the model $\moda$ is infinite we can choose distinct elements of $a_\alpha\in A$ for $\alpha\in G$ and then $(\moda,a_{\alpha})_{\alpha\in G}\models F$. It follows from the compactness theorem that $\Sigma$ has a model. Since the language of $\Sigma$ has cardinality $\kappa$ by the downward Lowenheim Skolem theorem $\Sigma$ has a model $\modc$ of cardinality $\kappa$. By the lemma there exists $j$ such that $\moda\elemsub^j\modc\res L$. By the other lemma $\modc\res L$ is isomorphic to a model $\modb$ such that $\moda\elemsub\modb$. \qed \end{document}