\documentclass[12pt]{article}
 \usepackage[margin=1in]{geometry} 
\usepackage{amsmath,amsthm,amssymb,amsfonts}
 
 \newtheorem*{lt}{\L o\'{s} Test}
  \newtheorem*{theorem}{Theorem}

 

\newcommand{\bN}{\mathbb{N}}
\newcommand{\bQ}{\mathbb{Q}}
\newcommand{\bR}{\mathbb{R}}
\newcommand{\bZ}{\mathbb{Z}}

\newcommand{\cC}{\mathcal{C}}
\newcommand{\cP}{\mathcal{P}}

\newcommand{\bx}{\bold{x}}
\newcommand{\by}{\bold{y}}
\newcommand{\bz}{\bold{z}}

\newcommand{\id}{\text{I}}
 
\newenvironment{problem}[2][Problem]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
%If you want to title your bold things something different just make another thing exactly like this but replace "problem" with the name of the thing you want, like theorem or lemma or whatever
 \date{}
\begin{document}
 
%\renewcommand{\qedsymbol}{\filledbox}
%Good resources for looking up how to do stuff:
%Binary operators: http://www.access2science.com/latex/Binary.html
%General help: http://en.wikibooks.org/wiki/LaTeX/Mathematics
%Or just google stuff
 
\title{Math 141b Problem Set 6}
\author{Due March 12, 2019}

\maketitle
 

 
\begin{enumerate}
	\item Show that there are continuum many countable models of $PA$.\\
	Recall the outline from class:
	\begin{itemize}
		\item For each set $X$ of primes, use compactness to find a model $M_X$ that has an element $m$ which is divisible by the $n$th prime iff $n \in X$ (we don't say anything about the nonstandard primes).
		\item Given $M \vDash PA$, set 
		\begin{eqnarray*}
		spec(M) = \left\{X \subset \bN : X\text{ is a set of primes and }M\text{ has an element }m_X\text{ that is divisible by the $n$th prime iff }n \in X\right\}
		\end{eqnarray*}
		If $M$ is countable, show that $spec(M)$ is countable.
		\item Conclude that there are continuum many models of $PA$.
	\end{itemize}
	\item Let $\bN_{PA}$ be the standard model of $PA$ (so the universe is $\bN$ and it has addition,etc. in the language) and let $M$ be a nonstandard model of $PA$.
	\begin{enumerate}
		\item Let $\phi(\bx)$ be a $\Delta_0$-sentence.  Show that, for any $n_1, \dots, n_k \in \bN$, we have
		$$\bN_{PA} \vDash ``\phi(n_1, \dots, n_k)" \iff M \vDash ``\phi(n_1, \dots, n_k)"$$
		\item Let $\psi(\bx)$ be a $\Sigma_1$-sentence.  Show that, for any $n_1, \dots, n_k \in \bN$, we have
		$$\bN_{PA} \vDash`` \psi(n_1, \dots, n_k)" \implies M \vDash ``\psi(n_1, \dots, n_k)"$$
	\end{enumerate}
	\item Ultraproducts are great! But if we want to move beyond first-order logic, we need to look at particular types of ultrafilter.  Call an ultrafilter $U$ on a set $I$ countably complete (or $\omega_1$-complete) iff, for all $\{X_n \in U : n \in \bN\}$, $\bigcap_{n \in \bN} X_n \in U$.  Show one of the following (they're the same idea):
	\begin{itemize}
		\item If $U$ is a countably complete ultrafilter, then $\prod \bN/U$ is isomorphic to $\bN$.
		\item We say a binary relation $R$ is \emph{well-founded} iff there is no infinite $R$-decreasing sequence (i.e., there is no $x_n$ for $n \in \bN$ such that $x_{n+1} R x_n$ for all $n$.  If $U$ is a countably complete and each $M_i = (X_i, R_i)$ is well-founded, then the ultraproduct $\prod M_i/U$ is well-founded.
	\end{itemize}
	Unfortunately $ZFC + "\text{there is a countably complete, non-principal ultrafilter}"$ proves $Con(ZFC)$, so it's a strong assumption.
	\item We know that nonstandard models of $PA$ must contain a copy of $\bN$ followed by a linearly ordered set of $\bZ$-chains from our previous work about fragments of arithmetic.  Show that the the $\bZ$-chains actually form a dense linear ordering (recall PS2, \#4).
\end{enumerate}


\end{document}

