\documentclass{article} \usepackage[utf8]{inputenc} \usepackage{amssymb} \usepackage{amsmath} \title{Model Theory Homework 2} \begin{document} \maketitle \begin{description} \item[2.5.3] Let $\mathcal L'$ be the language with one binary relation $<$ and one constant symbol $x_q$ for every rational number $q$. % \[x_{-1} < x_0 < x_1 \] % \[x_{-2} < x_{-\frac 3 2} < x_{-1} < x_{\frac 1 2} < x_0 < x_{\frac 1 2} < x_1 < x_{\frac 3 2} < x_2 \] % \[x_{-3} < x_{-\frac 8 3} < x_{-\frac 5 2} < x_{-\frac 7 3} < x_{-2} < x_{-\frac 5 3}< x_{-\frac 3 2} < x_{-\frac % 4 3} < % x_{-1} < x_{-\frac 2 3} < x_{-\frac 1 2} < x_{-\frac 1 3}\] % \[ < x_0 < x_{\frac 1 3} < x_{\frac 1 2} < x_{\frac 2 3} < x_1 % < x_{\frac 4 3} < x_{\frac 3 2} < x_{\frac 5 3} < x_2 < x_{\frac 7 3} < x_{\frac 5 2} < x_{\frac 8 3} < x_3 \] Define a set of rational numbers $X_n$ as $\{ \frac a b\ \mathrm{simplified} \in \mathbb Q \mid -n \leq x \leq n \wedge b \leq n \}$. $X_n$ is finite because it has a bounded denominator and bounded numerator too. Let $Y_n$ be the set of sentences $\{ x_a < x_b \mid a, b \in X_n \wedge a < b \}$. Each $Y_n$ is satisfiable because after a renaming of variables, it states that there are $2n \cdot n + 1$ distinct objects that are linearly ordered in a certain way. Because $Y$ is infinite, there are at least $2n \cdot n + 1$ elements, mapping each of the $2n \cdot n + 1$ variables into the elements in the unique order preserving way shows that $Y_n$ is satisfiable. By compactness, there are interpretations of the variables $x_q$ for all $q \in \mathbb Q$ such that each $Y_n$ is true. Define a map $\mathbb Q \to Y$ sending $q \to x_q^Y$. If it is order preserving, then it will be injective, so to show it is an embedding, it suffices to show that this map is order preserving. Given $a < b$ rationals, because every rational is eventually in $Y_n$ for some n, there will be a $m$ such that both $a$ and $b$ are in $Y_m$. By construction, $x_a < x_b$ will be a sentence in $Y_m$. Thus the interpretation of $x_a$ will be less than the interpretation of $x_b$, which is precisely stating that the map is order preserving. \item[2.5.4] We first show that every torsion-free finitely generated abelian group can have a total order satisfying the additivity property. Let $G$ be a finitely generated torsion-free abelian group. By the classification of finitely generated abelian groups, $G$ is isomorphic to $\mathbb Z^{n}$. Let $f \colon G \mathbb Z^{n}$ be such an isomorphism. $Z^{n}$ has an total order satisfying the additivity property, namely the lexographic ordering. As isomorphisms are truth preserving, the corresponding order on $G$, defined by $a < b \Leftrightarrow f(a) < f(b)$ will also be a linear order satisfying the additivity property. Let $G$ be an abelian group. Let $\tau$ have a binary relation $<$, one binary function $+$ and one constant $x_g$ for every $g \in G$. Let $T$ be a $tau$-theory, defined as follows. For every $x_a, x_b, x_c, x_g$ constants in $\tau$ (so that $a,b,c,d \in G$), let $T$ contain the following axioms: Well-definedness axioms $(x_a \neq x_b)$ for $a \neq b$. Abelian group axioms ($x_a + x_b = x_{a+b}$) Partial order axioms ($\neg (x_a < x_a)$, $(x_a < x_b) \Rightarrow \neg (x_b < x_a)$, $(x_a < x_b) \wedge (x_b < x_c) \Rightarrow (x_a < x_c)$). Total order axioms ($(x_a < x_b) \vee (x_b < x_a) \vee (x_b = x_a)$) Additivity axioms ($(x_a < x_b) \wedge ((x_c < x_d) \vee x_c = x_d) \Rightarrow x_a+x_c < x_b + x_d $) Suppose $T$ were satisfiable by some structure $M$. Then the subset $X$ of $M$ $\{ x^M_a \mid a \in G \}$ is a abelian group (with identity $x_e^M$, $e$ is the identity in $G$), and it is an isomorphism under the homomorphism $a \mapsto x_a^M$. It is also a total order, satisfying the additivity constraint. By fixing some group isomorphism $f \colon X \to G$, we can define a total order with the additivity constraint by $a < b \Leftrightarrow f(a) < f(b)$. This proves the required statement. We show $T$ is satisfiable by compactness, by showing every finite subset of $T$ is satisfiable. A finite subset $T_0$ of $T$ can only contain finitely many constants $x_g$, corresponding to finitely many elements $g_1, \ldots, g_n \in G$. Consider the subgroup $S$ generated by $g_1, \ldots, g_n$. It is a finitely generated torsion-free abelian group. It can have a additive total order put on it. Then $S$ is a model of $T_0$, hence we are done. \item[2.5.8a] Recall that $b \in \mathcal M$ is $A$-definable if there is a formula $\phi(v, \bar w)$ and $\bar a \in A$ such that $\mathcal M \vDash \phi(b, \bar a)$, and $b$ is the only element of $\mathcal M$ that such that $\phi(y, \bar a)$. Let $\mathcal M'$ be an elementary extension of $\mathcal M$. Then as elementary extensions are truth-preserving, $\mathcal M \vDash \phi(b, \bar a) \Leftrightarrow \mathcal M' \vDash \phi(b, \bar a)$ We show $\mathrm{Def}^{\mathcal M}(A) \supset \mathrm{Def}^{\mathcal M'}(A)$ Let $b \in \mathrm{Def}^{\mathcal M'}(A)$. We have $\mathcal M' \vDash \phi(b, \bar a)$. By the Tarski-Vaught test, $b \in M$. Thus $\phi(b, \bar a)$ holds. Let $b'$ be another element of $\mathcal M$ such that $\mathcal M \vDash \phi(b', \bar a)$. By truth-preservation of the inclusion, $\mathcal M' \vDash \phi(b', \bar a)$, so $b = b'$ and we are done. We show $\mathrm{Def}^{\mathcal M}(A) \subset \mathrm{Def}^{\mathcal M'}(A)$ Let $b \in \mathrm{Def}^{\mathcal M}(A)$. By the above, we have $\mathcal M' \vDash \phi(b, \bar a)$. Let $b'$ be another element of $\mathcal M'$ such that $\mathcal M' \vDash \phi(b', \bar a)$. By the Tarski-Vaught Test, elementary substructures are closed under formulas, so $b' \in M'$. Thus, as the inclusion is truth-preserving, $\mathcal M \vDash \phi(b', \bar a)$, so $b' = b$. Thus $b \in \mathrm{Def}^{\mathcal M'}(A)$. Recall that $b$ is algebraic over $A$ if there is a formula $\phi(v, \bar w)$ and $\bar a \in A$ such that $\mathcal M \vDash \phi(b, \bar a)$ and there are are only finitely many elements $y \in \mathcal M$ such that $\phi(y, \bar a)$. Let $\mathcal M'$ be an elementary extension of $\mathcal M$. We show $\mathrm{Alg}^{\mathcal M}(A) \supset \mathrm{Alg}^{\mathcal M'}(A)$ Let $b \in \mathrm{Alg}^{\mathcal M'}(A)$. We have $\mathcal M' \vDash \phi(b, \bar a)$. By the Tarski-Vaught test, $b \in M$. Thus $\mathcal M \vDash \phi(b, \bar a)$. Let $B$ be the the subset of $b' \in \mathcal M$ such that $\mathcal M \vDash \phi(b', \bar a)$. By truth-preservation of the inclusion, for any $b' \in B$, $\mathcal M' \vDash \phi(b', \bar a)$, so $B \subset \{ y \in \mathcal M \mid \phi(y, \bar a)\}$. $B$ is a subset of a finite set, thus finite, and we are done. We show $\mathrm{Alg}^{\mathcal M}(A) \subset \mathrm{Alg}^{\mathcal M'}(A)$ Let $b \in \mathrm{Alg}^{\mathcal M}(A)$. By the above, we have $\mathcal M' \vDash \phi(b, \bar a)$. Let $B$ be the subset $b' \in \mathcal M'$ such that $\mathcal M' \vDash \phi(b', \bar a)$. By the Tarski-Vaught Test, elementary substructures are closed under formulas, so $b' \in M'$. Thus, as the inclusion is truth-preserving, for any $\b' \in B$, $\mathcal M \vDash \phi(b', \bar a)$, so $B \subset \{ y \in \mathcal M \mid \phi(y, \bar a)\}$. $B$ is a subset of a finite set, thus finite, and we are done. \item[2.5.8b] Let $\tau$ be a signature with one constant symbol $c$. Let $\mathcal M$ be a $\tau$-structure with the set $\mathbb N$ and $c^{\mathcal M} = 0$. Let $\mathcal N$ be a $\tau$-structure also with the set $\mathbb N$ and $c^{\mathcal M} = 1$. Then $0$ is $\varnothing$-definable in $\mathcal M$ (by the symbol $c$), and not definable in $\mathcal N$ (not preserved by automorphisms (pick your favorite automorphism fixing 1 and moving 0)). Similarly, $0$ is algebraic in $\mathcal M$, but not algebraic in $\mathcal N$, because there is no finite set containing $0$ and fixed under automorphisms fixing 1. \item[2.5.13] $T$ is $\kappa$-categorical for all $\kappa \ge \aleph_{0}$. We try to classify models of $T$. Given $\mathcal M$ a model of $T$, define an equivalence relation on $\mathcal M$ as follows. $x \sim y$ if there is $n \in \mathbb Z$ such that $x = s^{n}(y)$. $s^{n}$ is defined as the composition of $s$ $n$-times if $n$ is positive, the identity if $n$ is zero, and the composition of $s^{-1}$ $n$-times if $n$ is negative. This is clearly an equivalence relation. Each equivalence class has $\aleph_{0}$ elements, one can define a bijection between each equivalence class an $\mathbb Z$ as follows. Pick an element $x$ of an equivalence class. We know that every other element of the equivalence class is going to be in the form $s^{n}(x)$ for some $n \in \mathbb Z$. These elements are all distinct (as $s$ has no cycles), thus sending every element to the corresponding $n$ gives the desired bijection. By the above, we know that $|M| = \aleph_{0} \cdot E$, where $E$ is the number of equivalence classes. By properties of cardinal arithmetic, either $E$ is countable and $|M| = \aleph_{0}$, or $E = |M|$. Given two models $\mathcal M$ and $\mathcal N$ of $t$ of the same cardinality, by the above, they have the same cardinality of equivalence classes. Pick $m_{a}$ and $n_{a}$ an element of every equivalence class in $\mathcal M$ and $\mathcal N$ respectively. $m_{a}$ and $n_{a}$ satisfy no nontrivial $\tau$-formulas, because they all lie in separate $\tau$-equivalence classes. Thus they have the same quantifier-free type, so the substructures they generated are isomorphic (I'm glad I pushed off writing up the solutions until after this was covered). But $m_{a}$ and $n_{a}$ both generated $\mathcal M$ and $\mathcal N$ respectively, so $\mathcal M$ is isomorphic to $\mathcal N$. Thus $T$ is $\kappa$-categorical for all $\kappa \ge \aleph_{0}$. We show $T$ is not categorical for $\kappa = \aleph_{0}$. Consider $\mathcal M = \mathbb Z$ with $s(x) = x+1$. Consider $\mathcal N = \mathbb Z \cup \mathbb Z$ where $s(x) = x +1$ in the same copy of $\mathbb Z$. Both of these functions are bijections without cycles, so both $\mathcal M$ and $\mathcal N$ are models of $T$. Given $x,y \in M$, $\mathcal M$ satisfies satisfies one of the sentences $\{ s^{n}(x) = y\}$ for $n \in \mathbb Z$ (defined because $s$ is a bijection). This is because given two integers, you can always increment or decrement them to obtain each other. However, this is not true for $\mathcal N$, because given $x$ and $y$ in separate copies of $\mathbb Z$, and $s$ stays in the same copy of $\mathbb Z$, this is not true for $\mathcal N$. If there was an isomorphism between $\mathcal M$ and $\mathcal N$, then it would preserve ``truth'' (for some definition of truth), but the above sentence is not preserved. \item[2.5.13] There is an equivalence of categories between abelian group such that all elements have order 2 and $\mathbb F_{2}$-vector spaces. Given such an abelian group, define scalar multiplication by 1 as the identity, and scalar multiplication by 0 as the 0 map. Given a $\mathbb F_{2}$-vector space, take the underlying abelian group, and all elements will have order 2 because $x + x = 1\cdot x + 1 \cdot x = 2 \cdot x = 0 \cdot x = 0$. Checking the details is left as an exercise to the grader. Now, as there is one vector space of every infinite dimension up to isomorphism, there is only one abelian group with all elements order 2 up to isomorphism for each infinite cardinality (as infinite dimension $\Leftrightarrow$ infinite cardinality for vector spaces over finite fields). To make $T$ complete, we need to make sure there are no finite models, so we can apply Tarski-Vaught. Add to $T$ one axiom of the form $\exists x_1 \cdots \exists x_{n} \bigwedge\limits_{i < j <=n} x_{i} \neq x_{j}$ for every natural number $n$. Thus $T$ now has only finite models, and by Tarski-Vaught, $T$ is complete, as it is $\kappa$-categorical for some (in fact for all) infinite $\kappa$. \item[2.5.17a] We first show that as $T$ is $\forall\exists$ axiomatizable, then given any totally ordered set $I$, and models $\mathcal M_{i}$ indexed by $I$ and elementary embeddings $\mathcal M_{i} \subset \mathcal M_{j}$ whenever $i < j$, then $\bigcup_{i} M_{i} \vDash T$. It suffices to show this for every sentence $\phi \in T$, because satisfaction of a theory is checked on sentences. Suppose that $\phi$ is $\forall x_{1} \cdots, \forall x_{n} \exists \bar y P(\bar x, \bar y)$. Then we want to show that given $n$ elements $x_{1}, \ldots, x_{n}$, then there is $\bar y \in \bigcup_{i} M_{i}^{m}$ such that $P(\bar x, \bar y)$. As each $x_{i}$ is in the union, then $x_{i} \in M_{j}$ for some $j$ depending on $i$. Take the maximum of such $j$ (as there are only finitely many), so we may assume $x_{i}\in M_{k}$ for a fixed $k$. Then, as $M_{k} \vDash T$, there is $\bar y \in M_{k}$ such that $P(\bar x, \bar y)$. Take the image of $\bar y$ in the union $\bigcup_{i} M_{i}$, and so $\bigcup_{i} M_{i} \vDash P(\bar x, \bar y)$ because $P(\bar x, \bar y)$ is atomic, and truth of atomic formulas are preserved under moving to a bigger structure. Now, as the question makes no sense if $T$ is not satisfiable, we may assume that $T$ is satisfiable. In that case, let $\mathcal M \vDash T$. We define a chain of models of $T$. Consider the set of sentences $S$ of the form $\exists \bar v \phi(\bar v, \bar a)$ where $\bar a$ are free variables. Pick a well ordering of them, and let $\phi_{\alpha}$ be the sentence in position $\alpha$ for $\alpha$ some ordinals. Define the chain of models by transfinite induction. Let $\mathcal M_{0} = \mathcal M$. This clearly satisfies the cardinality condition. Let $\mathcal M_{\lambda} = \bigcup_{\alpha < \lambda} \mathcal M_{\alpha}$. This satisfies and is a model of $T$ because the union of a chain of models of $T$ is a chain as $T$ is $\forall\exists$ axiomatizable. Suppose $\lambda$ is a successor ordinal, say $\xi + 1$. Then let $\mathcal M_{\lambda} = \mathcal M_{\xi}$ if there do not exist $\bar a \in \mathcal M_{\xi}$ and a model $\mathcal N \supseteq M_{\xi}$ such that $\mathcal N \vDash \phi_{\xi}(\bar a)$. Otherwise, let $M_{\lambda}$ be such an $\mathcal N$. Without loss of generality, by applying Lowenheim-Skolem, we may assume that $M_{\lambda}$ has the same cardinality as $\mathcal M_\xi$. Now, take the union of the $\mathcal M_{\alpha}$, call it $\mathcal N$. I claim that $\mathcal N$ is existentially closed. Suppose $\mathcal N' \supseteq \mathcal N$ and $\mathcal N' \vDash \exists \bar v \phi(\bar v, \bar a)$ with $\bar a \in \mathcal N'$. Suppose the sentence $\exists \bar v \phi(\bar v, \bar a)$ was enumerated at stage $M_{\lambda}$. As there was a extension of $M_{\lambda}$ satisfying $\exists \bar v \phi(\bar v, \bar a)$ (it is $\mathcal N'$), a solution must have been added at stage $M_{\lambda + 1}$. Thus as existentials are closed under taking a superstructure, $\mathcal N$ must satisfy $\exists \bar v \phi(\bar v, \bar a)$. The required cardinality $|\mathcal M| + \aleph_{0} + |\mathcal L|$ is achieved, because there are $\aleph_{0} + |\mathcal L|$ sentences, and each stage does not increase the original cardinality of $|\mathcal M|$. \item[2.5.17b] Let $\mathcal M$ be a nonexistentially closed model. By downward Lowenheim-Skolem, there is a elementary substructure of $\mathcal M$, $\mathcal M_{\kappa}$of any cardinality $|M| \geq \kappa \geq |\mathcal L|$. As $\mathcal M$ is not existentially closed, there is $\mathcal N \supseteq \mathcal M$ such that $\mathcal N$ satisfies a existential statement not satisfied by $\mathcal M$. This existential statement will not be satisfied by $\mathcal M_{\kappa}$, as it is elementarily equivalent to $\mathcal M$. As $\mathcal M_{\kappa}$ is also a substructure of $\mathcal N$, $\mathcal M_{\kappa}$ is not existentially closed. By upward Lowenheim-Skolem, there is an elementary superstructure of $\mathcal M$, $\mathcal M_\kappa$ of any cardinality $\kappa \geq |M|$. By hypothesis there is a existential statement $\varphi$ that is satisfied by some  extension $\mathcal N$ but is not satisfied by $\mathcal M$. I claim that there is an extension of $\mathcal M_\kappa$, $\mathcal N_\kappa$ such that $M_\kappa \subseteq N_\kappa$ and $N_\kappa$ satisfies $\varphi$, so that $\mathcal M_\kappa$ will be an nonexistentially closed model of cardinality $\kappa$. Such an $\mathcal N_\kappa$ equivalently satisfies $\varphi$ and $\mathrm{Diag}(\mathcal M_\kappa)$, so it suffices to show that $\phi$ and $\mathrm{Diag}(\mathcal M_\kappa)$ is satisfiable. We show by compactness that every finite subset is satisfiable, or without loss of generality that any finite subset of $\mathrm{Diag}(\mathcal M_\kappa)$ and $\phi$ is satisfiable by $\mathcal N$. A finite subset of $\mathrm{Diag}{\mathcal M_\kappa}$, say $\phi_1, \ldots, \phi_n$ only contains finitely many constants. We want to show that there are interpretations of constants of $\mathcal M_\kappa$ in $\mathcal N$, or equivalently $\mathcal N \vDash \exists c_1, \ldots, \exists c_n\ \phi_1 \wedge \ldots \wedge \phi_n$ and $\mathcal N \vDash \varphi$. The latter is true by definition, and the former is true if $\mathcal M \vDash \exists c_1, \ldots, \exists c_n \ \phi_1 \wedge \ldots \wedge \phi_n$, as existentials are closed under supermodels. But this is true as $\mathcal M \equiv \mathcal M_\kappa$. Thus there are interpretations of the constants for any finite set of sentences $\phi_1, \ldots, \phi_n$ (send any other constant to something arbitrary) so by compactness $\phi \cup \mathrm{Diag}(\mathcal M_\kappa)$ is satisfiable. \item[2.5.17c] Let $\mathcal M$ be a model of $T$ with cardinality $\kappa$. Then by part a, $\mathcal M$ can be embedded into a existentially closed model with the same cardinality $\kappa$. But such an embedding must be an isomorphism, so $\mathcal M$ is existentially closed. We proceed by contradiction. Suppose $T$ has an non-existentially closed model. Then by part b, $T$ has a non-existentially closed model in every cardinality, in particular, one in cardinality $\kappa$. But the only model of $T$ with cardinality $\kappa$ is existentially closed, a contradiction. \end{description} \end{document}