\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 7}
\author{Due April 9, 2019}

\maketitle
 

 
\begin{enumerate}
	\item Recall from class that there is partial computable $\phi:\bN^2\to \bN$ that enumerates all partial computable functions.  Show that 'partial' is critical here; that is, show that there is no total computable $\phi:\bN^2 \to \bN$ such that, for every computable $f:\bN \to \bN$, there is $e\in \bN$ such that for all $n \in \bN$,
	$$\phi(e, n) = f(n)$$
	\item We saw how to build finite sets diagonal indiscernibles from a strengthening of (finite) Ramsey's Theorem.  Now use Ramsey's Theorem to find finite sets of regular indiscernibles: Let $\Gamma$ be a finite collection of formulas (in the language of arithmetic).  Show that (in $\bN$ or any model of $PA$) for every $n \in \bN$, there are $x_1, \dots x_n$ that are $\Gamma$-indiscernible, which means, for every $\phi(y_1, \dots, y_k) \in \Gamma$ and $i_1 < \dots <i_k \leq n$ and $j_1 < \dots <j_k \leq n$, we have
	$$\phi(x_{i_1}, \dots, x_{i_k}) \iff \phi(x_{j_1}, \dots, x_{j_k})$$
	\item Finite is boring, so let's strengthen the previous problem to the infinite using the compactness theorem: Show that there is a model $M$ of $PA$ and $\{x_n : n \in \bN\} \subset M$ such that, for any formula $\phi(y_1, \dots, y_k)$ in the language of arithmetic and $i_1 < \dots <i_k \in \bN$ and $j_1 < \dots <j_k \in \bN$, we have
	$$\phi(x_{i_1}, \dots, x_{i_k}) \iff \phi(x_{j_1}, \dots, x_{j_k})$$
\end{enumerate}
\end{document}

