\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 3}
\author{Due Feb. 19, 2019}

\maketitle
 
 
\begin{enumerate}
	\item We say that the very weak Robinson arithmetic can prove some unquantified statements.  Show one of these, such as: for all $n, k \in \bN$,
	$$Q \vDash `S^n0 = S^k0\text{'} \iff n = k$$
	\item Recall that second-order logic extends first-order by allowing for quantification over subsets of the universe.  This includes quantification over subsets of tuples of the universe and testing for membership.
	
	I made some bold claims about tautologies in second-order logic.  Back that up by doing the following: define a sentence $\phi$ in second-order logic whose truth is dependent on set-theory.
	
	The way we discussed this in class was to first build up the notion of a set being infinite using bijections to a proper subset.  Then we can begin countably infinite by being infinite and having every subset finite or in bijection with the whole.  Then we said we could express the Continuum Hypothesis (which we might have heard is independent of $ZFC$).  One useful way to phrase the continuum hypothesis is the following: if $X$ is countably infinite and $\cP(X)$ is the power set of $X$, then every subset of $\cP(X)$ is either countable or the same size as $\cP(X)$.
	
	\item Show that $PA$ proves that $\leq$ is a total order, i. e., $\forall x,y (x \leq y \vee y \leq x)$.  Since $Q$ doesn't prove this, induction is probably helpful...
	
	\item Show that the primitive recursive relations and functions are closed under the `bounded leastness' quantifier.  We will actually use the following statement, which you're welcome to prove: if $R(y, \bx)$ is a primitive recursive relation and $G(\bz)$ is a primitive recursive function, then
	$$\mu y \leq G(\bz) . R(y, \bx)$$
	is a primitive recursive function.
\end{enumerate}

\end{document}

