# Math 776 Spring 2015

Instructor: Uri Andrews
Email: (My last name)@math.wisc.edu
Office: 513 Van Vleck Hall
Office Hours: W. 2:15-3:15
Class Room: B131

## Homeworks:

Homeworks will be regularly assigned and posted here with due-dates. If you do not yet have the textbook and need to know what the problems are, please drop me an e-mail.
1. Due Feb. 6th:
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 map from $\mathcal A$ to $\mathcal B$ and there is no elementary map 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?
2. Due Feb 27:
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.
5. Show that the theory of the reals $\mathcal R=(\mathbb{R}, +, -, \cdot , 0, 1)$ is model complete but does not have quantifier elimination. Hint: We will show in class that the theory of $(\mathbb{R}, +, -, \cdot , 0, 1, \leq)$ has quantifier elimination. Use this result.

## Source of Problems:

A good source of problems can be found in the "M" section of old qualifying exams. They can all be found here. If you are a math graduate student, do consider taking 770 and the logic qual. After this course, you're most of the way there!