\documentclass[12pt]{article}
\usepackage{mymacros}

\begin{document}
\title{4.2, 4.5}
\author{Andrew Lounsbury}
\date{February 23, 2020}
\maketitle

\section{4.2, p.107}

\begin{enumerate}
\item
	\begin{enumerate}
	\item
	$\underline{S0+S0 = SS0}$
	
	Yes: it's atomic
	
	\item
	$\underline{\neg(0 < 0 \lor 0 < S0)}$
	
	Yes: Let $\alpha:\equiv 0 < 0$ and $\beta:\equiv 0 < S0$. \\
	$\alpha$ and $\beta$ are atomic \\
	$\alpha \lor \beta$ a $\Sigma$-formula (case 2) \\
	$\neg(\alpha \lor \beta)$ a $\Sigma$-formula
	
	\item
	$\underline{(\fa x < \ol{17}) x < \ol{17}}$
	
	Yes: case 4 - $(\fa x < t)\alpha$
	
	\item
	$\underline{S0 \cdot S0 = S0 \land (\ex y < x)(\ex z < y) y+z = x}$
	
	Yes: Let $\alpha:\equiv S0 \cdot S0 = S0$ and $\beta:\equiv (\ex y < x)(\ex z < y) y+z = x$. \\
	$\alpha$ is atomic \\
	$\beta$ is a $\Sigma$-formula by case 4 \\
	$\alpha \land \beta$ is a $\Sigma$-formula by case 3
	
	\item
	$\underline{(\fa y)(y < 0 \ra 0 = 0)}$
	
	No: unbounded universal quantifier
	
	\item
	$\underline{(\ex x)(x < x)}$
	
	Yes: case 4
	
	\end{enumerate}
\item
A formula is Cool if and only if it is a $\Sigma$-formula. 
\begin{proof}

\end{proof}

\item
$\underline{\alpha:\equiv x < y \lor (\fa z < w) x+\ol{17} = \ol{42}}$
	\begin{enumerate}
		\item
		Yes: Let $\beta:\equiv x < y$ and $\delta:\equiv (\fa z < w) x+\ol{17} = \ol{42}$. \\
		$\beta$ is atomic \\
		$x+\ol{17} = \ol{42}$ is atomic, so $\delta$ is a $\Pi$-formula \\
		$\beta \lor \delta$ is a $\Pi$-formula by case 3
		
		\item
		$\neg\alpha:\equiv y \le x \land \neg(\fa z < w) x+\ol{17} = \ol{42}$
		
		Yes: Let $\beta:\equiv y \le x$ and $\delta :\equiv \neg(\fa z < w) x+\ol{17} = \ol{42}$. \\
		$\beta$ is a $\Pi$-formula \\
		$x+\ol{17} = \ol{42}$ is a $\Pi$-formula, so $(\fa z < w) x+\ol{17} = \ol{42}$ is a $\Pi$-formula \\
		$\delta$ is a $\Pi$-formula by case 2 \\
		$\beta \land \delta$ is a $\Pi$-formula by case 3
		
		\item
		$\neg\alpha:\equiv y \le x \land (\ex z < w) x+\ol{17} \neq \ol{42}$
		
		\item
		If $\alpha$ is any $\Sigma$-formula, then $\neg \alpha$ is logically equivalent to a $\Pi$-formula. 
		\begin{proof}
		We induct on the complexity of $\alpha$. \\
		If $\alpha$ is atomic, then $\neg\alpha$ is clearly a $\Pi$-formula. \\
		If $\alpha:\equiv \neg\beta$, where $\beta$ is an atomic formula, then $\neg\alpha:\equiv \beta$ is clearly a $\Pi$-formula. \\
		Suppose $\alpha:\equiv \beta \land \delta$, where $\beta$ and $\delta$ are $\Sigma$-formulas. 
		\end{proof}
		
	\end{enumerate}

\end{enumerate}

\section{4.5, p.112}

\begin{enumerate}
\item
	\begin{enumerate}
		\item
		$\left<3,0,4,2,1\right> = 2^4 \cdot 3^1 \cdot 5^5 \cdot 7^3 \cdot 11^2 = 6,225,450,000$
		
		\item
		$(16910355000)_3 = (2^3 \cdot 3^1 \cdot 5^4 \cdot 7 \cdot 11^3)_3 = (\left<2,0,3,0,4\right>)_3 = 3$
		
		\item
		$|16910355000| = |\left<2,0,3,0,4\right>| = 5$
		
		\item
		$(16910355000)_{42} = 0$
		
		\item
		$\left<2,7,1,8\right> \frown \left<2,8,1\right> = \left<2,7,1,8,2,8,1\right> = 2^3 \cdot 3^8 \cdot 5^2 \cdot 7^9 \cdot 11^3 \cdot 13^9 \cdot 17^2$
		
		\item
		$17 \frown 42 = 0$ \\
		2 is the only prime code number. 
		
	\end{enumerate}
\item
Consider $6$: $\left<6\right> = 2^7 = 128$, so $|\left<6\right>| = |128| = |2^7| = 1$, but $|6| = |2 \cdot 3| = 2$. 

\end{enumerate}
\end{document}