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

\begin{document}
\title{5.2-5.5}
\author{Andrew Lounsbury}
\date{March 5, 2020}
\maketitle

\section{5.2, p.119}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{enumerate}
	\item
	$N \nvdash (\fa x)(\fa y) x+y = y+x$ and $N \nvdash \neg[(\fa x)(\fa y) x+y = y+x]$. 
	\begin{proof}
		We must find an $\Ell_{NT}$-structure such that $\fA \vDash N$ and $\fA \nvDash \neg[(\fa x)(\fa y) x+y = y+x]$. \\
		Section 2.8.1 8: There exists such a $\fA$. \\
		\underline{Proof of 8}: 
		Let $\fA$ be a structure with $0^{\fA} = 0$, the underlying set $A = \N \cup \{\alpha,\beta\}$, where $\alpha$ and $\beta$ are nonstandard, and the following functions and relation
		\[
			S^{\fA}(x) = 
			\begin{cases}
			x+1 & x \in \N \\
			x & x \in \{\alpha,\beta\}
			\end{cases}
		\]
		\[
			x +^{\fA} y = 
			\begin{cases}
			x+y & x,y \in \N \\
			x & x \in \{\alpha,\beta\} \text{ and } y \in \N \\
			y & o/w
			\end{cases}
		\]
		\[
			x \cdot^{\fA} y = 
			\begin{cases}
			x \cdot y & x,y \in \N \\
			x & x \in \{\alpha,\beta\} \text{ and } y \in \N \\
			y & o/w
			\end{cases}
		\]
		(this one is a bit tricky)
		\[
			x E^{\fA} y = 
			\begin{cases}
				x^y & x,y \in \N \\
				0 & x \in \{\alpha,\beta\} \text{ and } y \in \N \\
				1 & o/w
			\end{cases}
		\]
		\[
			x <^{\fA} y 
			\begin{cases}
				\text{ when }x,y \in \N \text{ and } x < y \\
				\text{ or when } x \in \{a,b\} \text{ and } y \in \N
			\end{cases}
		\]
		Specifically, $(\fa x)\neg x <^{\fA} x$ is false. \\
		To save some time typing and because the first four axioms are covered in the text, we will just show $\fA \vDash \{N_5,\dots,N_{11}\}$. (I'm not entirely sure why they're able to ignore them in the text. It is necessary to consider them in order find an $\Ell_{NT}$-structure that doesn't model commutativity of addition, isn't it?) \\
		\underline{$N_5$}: Clear. \\
		\underline{$N_6$}: Clear when $x,y \in \N$. \\
		Let $x \in \{\alpha,\beta\}$ and $y \in \N$. Then, $x \cdot^{\fA} S^{\fA} y = x \cdot^{\fA} (y+1) = x$ and $(x \cdot^{\fA} y) +^{\fA} x = x +^{\fA} x = x$. \\
		\underline{$N_7$}: Clear when $x,y \in \N$. \\
		Let $x \in \{\alpha,\beta\}$ and $y \in \N$. Then, $xE^{\fA}0 = 1$ and $S^{\fA}0 = 1$. \\
		\underline{$N_8$}: Clear when $x,y \in \N$. \\
		Let $x \in \{\alpha,\beta\}$ and $y \in \N$. Then, $xE^{\fA}(S^{\fA}y) = xE^{\fA}(y+1) = 0$ and $(xE^{\fA}y) \cdot^{\fA} x = 0 \cdot^{\fA} x = 0$. \\
		\underline{$N_9$}: Clear. \\
		\underline{$N_{10}$}: In English this says $x$ is less than $y+1$ when $x$ is less than or equal to $y$, so this is clear when $x,y \in \N$. Since our nonstandard $\alpha$ and $\beta$ are less than any $y \in \N$, this is also clear when $x \in \{\alpha,\beta\}$ and $y \in \N$ and otherwise. \\
		\underline{$N_{11}$}: Following our definition of $<^{\fA}$, this is fairly clear as well. \\
		Thus $\fA$ is an $\Ell_{NT}$ structure such that $\fA \nvDash (\fa x)(\fa y)x+y = y+x$ since we defined $<^{\fA}$ such that $(\fa x)x <^{\fA} x$ is not true. $\square$ \\
		Now, by the Soundness Theorem, we have $N \nvdash (\fa x)(\fa y)x+y = y+x$. \\
		On the other hand $\fN$ is structure such that $\fN \vDash N$ and $\fN \nvDash \neg [(\fa x)(\fa y)x+y = y+x]$, so $N \nvdash \neg(\fa x)(\fa y)x+y = y+x$ again by the Soundness Theorem. 
	\end{proof}
\end{enumerate}

\section{5.3, p.128}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{enumerate}
\item[2.]
	\begin{enumerate}
		Suppose $A \subset \N$ is represented by $\phi(x)$ and $B \subset \N$ is represented by $\psi(x)$. Then, 
		\item
		$\phi(x) \lor \psi(x)$ represents $A \cup B$
		\begin{proof}
			Let $a \in A \cup B$. We must show $N \vdash \phi(\ol{a}) \lor \psi(\ol{a})$. \\
			If $a \in A$, then $N \vdash \phi(\ol{a})$ since $\phi(x)$ represents $A$. \\
			$\phi(x)$, $\therefore \phi(x) \lor \psi(x)$ \\
			$N \vdash \phi(\ol{a}) \lor \psi(\ol{a})$ by the (PC) rule of inference. \\
			If $b \in A$, then $N \vdash \psi(\ol{a})$ since $\psi(x)$ represents $B$. \\
			$\psi(x)$, $\therefore \phi(x) \lor \psi(x)$ \\
			$N \vdash \phi(\ol{a}) \lor \psi(\ol{a})$ by the (PC) rule of inference. \\
			On the other hand, suppose $a \notin A \cup B$. We must show $N \vdash \neg(\phi(\ol{a}) \lor \psi(\ol{a}))$. \\
			Since $a \notin A$ and $a \notin B$, we know $N \vdash \neg\phi(\ol{a})$ and $N \vdash \neg\psi(\ol{a})$ since $\phi(x)$ and $\psi(x)$ represent $A$ and $B$ respectively. \\
			$\neg\phi(\ol{a})$ and $\neg\psi(\ol{a})$, $\therefore \neg(\phi(\ol{a}) \lor \psi(\ol{a}))$ \\
			Thus, $N \vdash \neg(\phi(\ol{a}) \lor \psi(\ol{a}))$ by the (PC) rule of inference. \\
			Thus, $\phi(x) \lor \psi(x)$ represents $A \cup B$. 
		\end{proof}
		
		\item
		$\phi(x) \land \psi(x)$ represents $A \cap B$
		\begin{proof}
			Let $a \in A \cap B$ so that $a \in A$ and $a \in B$. \\
			$N \vdash \phi(\ol{a})$ and $N \vdash \psi(\ol{a})$ since $\phi(x)$ and $\psi(x)$ represent $A$ and $B$ respectively. \\
			$\phi(x)$ and $\psi(x)$, $\therefore \phi(x) \land \psi(x)$ \\
			Therefore, $N \vdash \phi(\ol{a}) \land \psi(\ol{a})$ by the (PC) rule of inference. 
		\end{proof}
		
		\item
		$\neg\phi(x)$ represents $A^c$, the complement of $A$. 
		\begin{proof}
			Let $a \in A^c$ so that $a \notin A$. Then, $N \vdash \neg\phi(\ol{a})$ since $\phi(x)$ represents $A$. 
			If, on the other hand $a \notin A^c$ so that $a \in A$. Then, $N \vdash \phi(\ol{a})$, or $N \vdash \neg(\neg\phi(\ol{a}))$ since $\phi(x)$ represents $A$. By Definition 5.3.1, $\neg\phi(x)$ represents $A^c$. 
		\end{proof}
		
	\end{enumerate}

	\item[3.]
	Every finite subset of the natural numbers is representable, and every subset of $\N$ whose complement is finite is also representable. 
	\begin{proof}
		\underline{Lemma 2.8.4}: If $a = b$, then $N \vdash \ol{a} = \ol{b}$. If $a \neq b$, then $N \vdash \ol{a} \neq \ol{b}$. \\
		For any $n \in \N$, $\phi(x) :\equiv x = \ol{n}$ represents $\{n\}$. \\
		A finite set is a union of these sets, and by Exercise 2 part (a), any finite set is representable. \\
		By part (c) of Exercise 2, every subset of $\N$ whose complement is finite is also representable. 
	\end{proof}

	\item[7.]
	$Divides(x,y) :\equiv (\ex z)(x \cdot z = y)$

	I'm not entirely sure what sets like \textsc{Divides} contain. Something like \textsc{Even} is easy enough to understand, but not so much with things like \textsc{Divides} and \textsc{Primepair}. Since every prime has an adjacent prime, I would think that all primes would lie in \textsc{Primepair}, but then \textsc{Primepair}$ = $\textsc{Prime}. As for \textsc{Divides}, I can only imagine it contains numbers that...divide another number(?), which would would be all of them, which doesn't make much sense. They don't contain pairs of numbers, do they? 

\end{enumerate}

\section{5.5, p.136}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{enumerate}
	\item[2.]
		\begin{enumerate}
		\item
		The sequence of symbol numbers for $=+000$ is $(7,11,9,9,9)$, and the code is $2^83^{12}5^{10}7^{10}11^{10}$. 
		
		\item
		The sequence of symbol numbers for $=Ev_1Sv_2 \cdot Ev_1v_2v_1$ is \\
		$(7,17,2,11,4,15,17,2,4,2)$, and the code is $2^8 3^{18} 5^3 7^{12} 11^5 13^{16} 17^{18} 19^3 23^5 29^3$. 
		
		\item
		The sequence of symbol numbers for $(=00 \lor (\neg < 00))$ is \\
		$(21,7,9,9,3,21,1,19,9,9,23,23)$, and the code is \\
		$2^{22} 3^8 5^{10} 7^{10} 11^4 13^{22} 17^2 19^{20} 23^{10} 29^{10} 31^{24} 37^{24}$. 
		
		\item
		We have $(\ex v_2)(< v_2 0) \equiv (\neg\fa\neg v_2)(< v_2 0)$. The sequence of symbol numbers is $(21,1,5,1,4,23,21,19,4,9,23)$, and the code is $2^{22} 3^2 5^6 7^2 11^5 13^{24} 17^{22} 19^{20} 23^5 29^{10} 31^{24}$. 
		
		\end{enumerate}

\end{enumerate}
\end{document}