Math 776
Spring 2016

Homeworks:

1. Due Feb. 18:
   1. Construct two structures $\mathcal A$ and $\mathcal B$ so that $\mathcal A \equiv \mathcal B$ (i.e. they are elementarily equivalent), but there is no elementary embedding from $\mathcal A$ to $\mathcal B$ and there is no elementary embedding from $\mathcal B$ to $\mathcal A$.
   2. Construct two structure $\mathcal A$ and $\mathcal B$ so that there is an elementary embedding $h:\mathcal A\rightarrow \mathcal B$ and an elementary embedding $g:\mathcal B\rightarrow\mathcal A$, but $\mathcal A\not\cong \mathcal B$.
   3. Let $\mathcal A$ be an $\mathcal L$-structure and $\phi(x,y)$ be an $\mathcal L$-formula. Suppose $X\subseteq A$ is an infinite set so that $\{(x,y)\in X\mid \mathcal A\models \phi(x,y)\}$ gives a linear ordering of $X$. Let $\tau$ be any linear order. Show that there is a structure $\mathcal B$ and a set $Y\subseteq B$ so that $\mathcal A\preceq \mathcal B$ and $\{(x,y)\in Y\mid \mathcal B \models \phi(x,y)\}$ gives a linear ordering on $Y$ isomorphic to $\tau$.
   4. We say that a set $A\subseteq \omega$ is a spectrum if there is a language $\mathcal{L}$ and a sentence $\phi$ so that $n\in A$ if and only if there is a model of $\phi$ of size $n$ (we call this $A$ the spectrum of $\phi$). The spectrum problem (still open and apparently quite hard) is to characterize which subsets of $\omega$ are spectra. In particular, it is no known if the complement of a spectrum is a spectrum. The following are easier:
      1. Show that if $X$ is any finite or co-finite subset of $\omega$, then $X$ is a spectrum.
      2. Show that the set of even numbers is a spectrum.
      3. Show that the set of odd numbers is a spectrum.
      4. Show that for any $n,m\in \omega$, the set of integers congruent to $n$ mod $m$ is a spectrum.
      5. Show that the set of powers of primes is a spectrum.
      6. Show that the set of powers of 17 is a spectrum.
      7. Show that if $X$ and $Y$ are spectra, then $X\cup Y$ is a spectrum and $X\cap Y$ is a spectrum.
   5. Let $\phi$ be a sentence so that the spectrum of $\phi$ is infinite. Show that $\phi$ has an infinite model. If $\phi$ has an infinite model, must the spectrum of $\phi$ be infinite?
   6. Let $\mathcal{A}$ be the structure $(\mathbb{N},S)$ where $S$ is the successor function, i.e. $S$ is a unary function symbol which sends $n$ to $n+1$. Show that $\text{Th}(\mathcal{A})$ is $\kappa$-categorical for any uncountable $\kappa$.
2. Due March 18:
   1. We say that $\mathcal A \preceq_k \mathcal B$ if whenever $\psi(\bar{x})$ is an $\exists_k$ formula (i.e. $\exists\forall\exists\ldots $ for length $k$) and $\bar{a}\in A$, then $\mathcal A \models \psi(\bar{a})$ if and only if $\mathcal B \models \psi(\bar{a})$. Let $L$ be a language, $T$ an theory in $L$, $n$ an integer $\geq 2$, and $\phi(\bar{x})$ an $L$-formula. Show that the following are equivalent:
      1. $\phi$ is equivalent modulo $T$ to a $\forall_n$ formula (defined like $\exists_n$, but it starts with a $\forall$).
      2. If $\mathcal A$ and $\mathcal B$ are models of $T$ such that $\mathcal{A} \preceq_{n-1} \mathcal{B}$, and $\bar{a}$ is a tuple from $A$ so that $\mathcal{B}\models \phi(\bar{a})$, then $\mathcal A \models \phi(\bar{a})$.
      3. $\phi$ is preserved in unions of $\preceq_{n-2}$-chains of models of $T$ (i.e., if $\mathcal{A}_i$ for $i\in \omega$ is a $\preceq_{n-2}$-chain of models of $T$ and $\mathcal{B}$, the union of the chain, is also a model of $T$, and $\bar{a}\in A_0$ is so that $\mathcal{A}_i\models \phi(\bar{a})$ for each $i$, then $\mathcal{B}\models \phi(\bar{a})$ as well).
   2. Let $L$ be a language and $T$ a theory in $L$. Show that the following are equivalent:
      1. $T$ is equivalent to a set of sentences of $L$ of the form $\forall x \exists \bar{y} \phi(x,\bar{y})$ (note that $x$ is a single variable, not a tuple) with $\phi$ quantifier-free.
      2. If $\mathcal A$ is an $L$-structure and for every element $a\in A$ there is a substructure of $\mathcal A$ which contains $a$ and is a model of $T$, then $\mathcal A \models T$
   3. Let $L$ be a language and $T$ a theory in $L$. Show that the following are equivalent:
      1. Whenever $\mathcal A$ and $\mathcal B$ are models of $T$ with $\mathcal A \preceq \mathcal B$, and $\mathcal A\subseteq \mathcal C \subseteq \mathcal B$, then $\mathcal C \models T$.
      2. Whenever $\mathcal A$ and $\mathcal B$ are models of $T$ with $A\preceq_2 \mathcal B$ and $\mathcal A \subseteq \mathcal C\subseteq \mathcal B$, then $\mathcal C\models T$.
      3. $T$ is equivalent to a set of $\exists\forall$ sentences.
   4. Let $L$ be the language $\{<\}\cup \{R_i\mid i\in \omega\}$ where $<$ and the $R_i$ are binary. Let $T$ be the theory that says $<$ is a linear order which is discrete (i.e. every element has an immediate predecessor and an immediate successor). Further, $T$ says that $R_i(x,y)$ holds if and only if $y>x$ and there are exactly $i$ elements in the interval between $x$ and $y$. Show that $T$ has quantifier elimination and is complete. Use this to conclude that the theory $T'$ in language $\{<\}$ which says that $<$ is a discrete linear order is also complete.

Source of Problems:

Links

1. Andres Caicedo's notes on proving compactness via the ultraproduct construction.