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

 
\newcommand{\N}{\mathbb{N}}
\newcommand{\bN}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}

\newcommand{\cC}{\mathcal{C}}

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

\maketitle
 
For simplicity, we will assume all our language $\tau$ are at most countable. 
 
\begin{enumerate}
	\item In class, we used the \L o\'{s} Test to determine that $T_S$ is complete:
	\begin{lt}
	If a theory $T$ \underline{with no finite models} is categorical in an infinite cardinal, then it is complete.
	\end{lt}
	Prove this.  Two things from 141a that will help are:
	\begin{enumerate}
		\item Recall that a theory $T$ is categorical in a cardinal $\kappa$ iff every two models of $T$ of size $\kappa$ are isomorphic.  Being isomorphic implies that two structures satisfy the same theory.
		\item {\bf The L\"{o}wehnheim-Skolem Theorem:} If $M$ is an infinite structure in a language $\tau$ and $\kappa$ is an infinite cardinal, then there is a structure $N$ of size $\kappa$ such that $M \equiv N$ (this relation is \emph{elementary equivalence} and means that the two structures satisfy the same first-order theory).
	\end{enumerate}
	\item Using our characterization of models of $T_S$, show that $T_S$ is categorical in every uncountable cardinal.
	\item Prove the following test for quantifier elimination by induction on formulas:
	\begin{theorem}
	Let $T$ be a (first-order) theory in a language $\tau$.  Assume that for every formula $\phi(y_1, \dots, y_n)$ of the form
	$$\exists x \bigwedge_{1 \leq i < n} \phi_i(x, y_1, \dots, y_n)$$
	with each $\phi_i$ atomic or negated atomic (and all free variables listed), there is a quantifier-free formula $\psi(y_1, \dots, y_n)$ such that 
	$$T \vDash \forall y_1, \dots, y_n \left( \phi(y_1, \dots, y_n) \leftrightarrow \psi(y_1, \dots, y_n)\right)$$
	Show that $T$ has quantifier elimination.
	\end{theorem}
	
	\item Using that $T_S$ eliminates quantifiers, show that $A \subset \bN$ is definable in $\bN_S$ iff $A$ is finite or its complement is finite (cofinite).
\end{enumerate}

\newpage
\begin{center}
{\bf Review}
\end{center}

Let's review the inductive definitions of formulas:
\begin{enumerate}
	\item {\bf Language} A \underline{language} $\tau$ (also called vocabulary or similarity type) is a collection of function symbols, relations symbols, and constant symbols (the relation and function symbols come with their arity attached).  In natural numbers with successor, the language $\tau_S$ consists of a unary function symbol $S$ and a constant symbol $0$ (and no relation symbols).
	\item {\bf Structure} A \underline{structure} $M$ (also called a model) in a language $\tau$ consists of 
	\begin{itemize}
		\item an underlying set or universe (often denoted using the same symbol); and
		\item interpretations of the symbols of the language inside the universe.
	\end{itemize}
	In $\tau_S$, a structure $M$ consists of a set $X$ along with a unary function $F:X \to X$ and a distinguished constant $a \in X$.  To connect them to the language, we will write $S^M = F$ and $0^M = a$.
	\item {\bf Terms} The \underline{terms} of a language $\tau$ are the expressions that the language can form.  The set of terms is defined inductively by
	\begin{enumerate}
		\item a variable (such as $x, y, \dots$) is a term;
		\item a constant symbol is a term; and 
		\item if $F$ is an $n$-ary function symbol in $\tau$ and $t_1, \dots, t_n$ are terms, then $F(t_1, \dots, t_n)$ is a term.
	\end{enumerate}
	In $\tau_S$, some work can show that all terms are of the form `$S^n0$' or `$S^nx$' for some variable $x$.
	\item {\bf Formulas}  \underline{Formulas} are the things that the language can express.  The set of formulas is defined inductively by
	\begin{enumerate}
		\item if $R$ is an $n$-ary relation or equality and $t_1, \dots, t_n$ are terms, then $R(t_1, \dots, t_n)$ is a formula;
		\item if $\phi(x_1, \dots, x_n)$ is a formula, then so is $\neg \phi(x_1, \dots, x_n)$;
		\item if $\phi(x_1, \dots, x_n)$ and $\psi(x_1, \dots, x_n)$ are formulas, then so are $\phi\wedge\psi(x_1, \dots, x_n)$ and $\phi \vee \psi(x_1, \dots, x_n)$; and 
		\item if $\phi(y,x_1, \dots, x_n)$ is a formula, then so are $\forall y  \phi(y,x_1, \dots, x_n)$ and $\exists y \phi(y,x_1, \dots, x_n)$.
	\end{enumerate}
	A free variable in a formula $\phi$ is a variable that is used but never quantified over.  If a formula has no free variables, then it is a \underline{sentence}.  All the formulas listed in $T_S$ are sentences.\\
	
	The formulas listed in the first item are called the \underline{atomic formulas}.  A formula built without quantification (the fourth item) is called a \underline{quantifier-free formula}.
	\item {\bf Evaluating Truth} Structures are semantic objects and formulas are syntactic objects, and these are brought together by evaluating formulas in structures.  Let $M$ be a $\tau$-structure, $\phi(x_1, \dots, x_n)$ a $\tau$-formula, and $m_1, \dots, m_n \in M$.  We want to evaluate if the formula $\phi$ holds in $M$ when substituting $m_1, \dots, m_n$ for the free variables $x_1, \dots, x_n$.  If this is the case, we write
	$$M \vDash \phi(m_1, \dots, m_n)$$
	The formal definition of this is an inductive definition going through the inductive definitions of terms and formula; in the end, it is precisely the procedure you might guess.  For instance, in the structure $(\bN, S, 0)$ with the formula 
	$$``\exists z (SSSx = z \to (S0 = y))"$$
	 and the tuple $7, 1$, we have $\bN_S \vDash \phi(7, 3)$ iff there is a $z \in \bN$ such $SSS7 = 10 = z$ implies $S0 = 1 = y$.  This is of course true by taking $z = 4$.
\end{enumerate}

\end{document}


