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

%1.5: 1,6
%1.6: 3,7
%1.7: 1,5

\begin{document}
\title{1.6-1.8}
\author{Andrew Lounsbury}
\date{February 4, 2020}
\maketitle

\section{1.6, p.26}

\begin{enumerate}
	\item[3.]
	$\Ell$ is $\{\flat,\sharp^3,\natural^2\}$

	$\{0,\sharp, \natural\}$, where $\sharp:\R^3 \to \R$ is defined as $\sharp(x,y,z) = x+y+z$ and $\natural$ is defined as $<$, is a model for $\Ell$. 

	$\{0,\sharp, \natural\}$, where $\sharp:\{0,1,2,3,4,5\}^3 \to \{0,1,2,3,4,5\}$ is defined as $\sharp(x,y,z) = x+y+z$ and $\natural$ is defined as $<$, is a model for $\Ell$. 

	\item[7.]
	$\Ell_{NT}$ is $\{0,S,+,\cdot,E,<\}$ \\
	Let $\fA = (\N,0^{\fA},S^{\fA},+^{\fA},\cdot^{\fA},E^{\fA},<^{\fA})$ be an $\Ell_{NT}$-structure defined as follows
	\begin{gather*}
	S^{\fA}(t) :\equiv St \\
	+^{\fA}(t,s) :\equiv +ts \\
	\cdot^{\fA}(t,s) :\equiv \cdot ts \\
	E^{\fA}(t,s) :\equiv Ets \\
	<^{\fA}(t,s) :\equiv <ts
	\end{gather*}

	Let $\phi :\equiv S0+S0+SS0$ and let $s$ be an assignment function into $\fA$. Then, 
	\begin{align*}
	\ol{s}(S0+S0) &\text{ is } +^{\fA}(S^{\fA}(0^{\fA}),S^{\fA}(0^{\fA})) \\
	&\text{ is } +^{\fA}(S^{\fA}(0),S^{\fA}(0)) \\
	&\text{ is }+^{\fA}(S0,S0) \\
	&\text{ is } +S0S0,
	\end{align*}
	and
	\begin{align*}
	\ol{s}(SS0) &\text{ is } S^{\fA}(S^{\fA}(0^{\fA})) \\
	&\text{ is } S^{\fA}(S^{\fA}(0)) \\
	&\text{ is } S^{\fA}(S0) \\
	&\text{ is } SS0. 
	\end{align*}
	Since $\ol{s}(S0+S0)$ is not the same as $\ol{s}(SS0)$, $\fA \nvDash \phi[s]$ and $\phi$ is not true in $\fA$. 
	%\begin{align*}
	%\ol{s}(S0+S0) &\text{ is } +^{\fN}(S^{\fN}(0^{\fN}),S^{\fN}(0^{\fN})) \\
	%&\text{ is } +^{\fN}(1,1) \\
	%&\text{ is } 2,
	%\end{align*}
	%and
	%\begin{align*}
	%\ol{s}(SS0) &\text{ is } S^{\fN}(S^{\fN}(0^{\fN})) \\
	%&\text{ is } S^{\fN}(1) \\
	%&\text{ is } 2. 
	%\end{align*}

\end{enumerate}

\section{1.7, p.32}

\begin{enumerate}
	\item[1.]
	The structure $\fN$ makes the sentence $\phi :\equiv 1+1 = 2$ true. 
	\begin{proof}
		Let $s$ be an assignment function into $\fN$. 
		\begin{align*}
			\ol{s}(1+1) & \text{ is } +^{\fN}(1^{\fN},1^{\fN}) \\
			& \text{ is } 2. 
		\end{align*}
		and
		\begin{align*}
			\ol{s}(2) & \text{ is } 2^{\fN} \\
			& \text{ is } 2,
		\end{align*}
		Since $\ol{s}(1+1)$ is the same as $\ol{s}(2)$, $\fN \vDash \phi[s]$ and $\phi$ is true in $\fN$. 
	\end{proof}

	The structure $\fA = (\N,0,S,+,\cdot,E,<)$, where $+$ is defined as $+(t,s) = t^2+s+1$ makes $\phi :\equiv 1+1 = 2$ false. 
	\begin{proof}
		Let $s$ be an assignment function into $\fA$. 
		\begin{align*}
			s(1+1) & \is +^{\fA}(1^{\fA},1^{\fA}) \\
			& \is 1^2+1+1 \\
			& \is 3
		\end{align*}
		and 
		\begin{align*}
			s(2) & \is 2^{\fA} \\
			& \is 2
		\end{align*}
		Since $\ol{s}(1+1)$ is the same as $\ol{s}(2)$, $\fN \nvDash \phi[s]$ and $\phi$ is false in $\fA$. 
	\end{proof}

	The structure $\fN$ makes the sentence $\phi :\equiv (\fa x)(x+1 = x)$ false.
	\begin{proof}
		Let $s$ be an assignment function into $\fN$. Then, 
		\begin{align*}
			\sbar[x|n](x+1) & \is +^{\fN}(x,1^{\fN}) \\
			& \is x+1
		\end{align*}
		for each $n \in \N$, and 
		\[
			\sbar[x|n](x) = x
		\]
		for each $n \in \N$. Since $\sbar[x|n](x+1)$ and $\sbar[x|n](x)$ are not the same for every $n \in \N$, $\fN \nvDash \phi[s(x|n)]$ and $\phi$ is not true in $\fN$. 
	\end{proof}

	The structure $\fA = (\N,0,S,+,\cdot,E,<)$, where $+$ is defined as $+(t,s) = ts$, makes $\phi :\equiv (\fa x)(x+1 = x)$ true. 
	\begin{proof}
		Let $s$ be an assignment function into $\fN$. Then, 
		\begin{align*}
			\sbar[x|n](x+1) & \is +^{\fA}(x,1^{\fA}) \\
			& \is x,
		\end{align*}
		for each $n \in \N$, and 
		\begin{align*}
			\sbar[x|n](x) = x
		\end{align*}
		for each $n \in \N$. Since $\sbar[x|n](x+1)$ and $\sbar[x|n](x)$ are the same for every $n \in \N$, $\fA \vDash \phi[s(x|n)]$ and $\phi$ is true in $\fA$. 
	\end{proof}

	\item[5.]
	Let $\fA$ be a structure for the language of set theory, $\Ell_{ST}$, which is $\{\in\}$. Let $A = \{u,v,w,\{u\},\{u,v\},\{u,v,w\}\}$. Then, the sentence $\phi :\equiv (\fa y \in y)(\ex x \in x)(x = y)$ is false in $\fA$. 

	\begin{align*}
		\fA \vDash \phi[s] & \text{ iff For every } a \in A, \fA \vDash \neg(\fa x \in x)\neg(x = y)[s(y|a)] \\
		& \text{ iff For every } a \in A, \fA \nvDash (\fa x \in x)\neg(x = y)[s(y|a)] \\
		& \text{ iff For every } a \in A, \text{ there is a }b \in A, \text{ such that } \\
		&\fA \nvDash (\fa x \in x)\neg(x = y)[s(y|a)(x|b)] \\
	\end{align*}

	\begin{proof}
		Let $s$ be an assignment function into $\fA$. \\
		Write $\phi$ as 
		\begin{align*}
			\phi &:\equiv (\fa y \in y)(\ex x \in x)(x = y) \\
			&:\equiv (\fa y \in y)\neg(\fa x \in x)\neg(x = y) \\
			&:\equiv (\fa y \in y)\neg(\fa x \in x)\neg(\alpha) \\
			&:\equiv (\fa y \in y)\neg(\fa x \in x)(\beta) \\
			&:\equiv (\fa y \in y)\neg(\gamma) \\
			&:\equiv (\fa y \in y)(\delta). 
		\end{align*}
		We have that $\sbar(x) = x$ and $\sbar(y) = y$. Since these are not the same, $\fA \nvDash \alpha[s]$, which means $\fA \vDash \beta[s]$. \\
		Then, we have that $\sbar[x|a](x) = x$ for every $a \in A$ and $\sbar[x|b](y) = b$ for every $b \in A$. Since these are not the same for every $b \in A$, we know $\fA \nvDash \gamma[s(x|a)]$, which tells us that $\fA \vDash \delta[s]$. \\
		Now, $\sbar[y|a](x) = a$ for every $a \in A$ and $\sbar[y|b](y) = y$ for every $b \in A$. Since these are not the same, $\fA \nvDash \phi[s]$. Thus, $\phi$ is false in $\fA$. 
	\end{proof}
\end{enumerate}

\section{1.8, p.36}

\begin{enumerate}
	\item[2.]
	\begin{enumerate}
		\item
		$\phi :\equiv \fa x(x = y \rightarrow Sx = Sy)$, $t$ is $S0$ \\
		$\phi_t^x :\equiv \fa x(t = y \rightarrow Sx = Sy)$
		
		\item
		$\phi :\equiv \fa y(x = y \rightarrow Sx = Sy)$, $t$ is $Sy$ \\
		$\phi_t^x :\equiv \fa y(x = y \rightarrow St = Sy)$	
		
		\item
		$\phi :\equiv x = y \rightarrow (\fa x)(Sx = Sy)$, $t$ is $Sy$ \\
		$\phi_t^x :\equiv x = y \rightarrow (\fa x)(St = Sy)$
		
	\end{enumerate}
	
	\item[3.]
	If $t$ is variable-free, then $t$ is always substitutable for $x$ in $\phi$. 
	\begin{proof}
		We induct on the complexity of $\phi$. \\
		\bc Suppose $\phi$ is atomic. By the definition of substitutability, $t$ is substitutable in $\phi$. \\
		\is Suppose $t$ is substitutable for $x$ in formulas $\alpha$ and $\beta$. \\
		If $\phi$ is of the form $\neg(\alpha)$ or $(\alpha \lor \beta)$, then $t$ is substitutable for $x$ in $\phi$ by definition given in clauses (2) and (3) of Definition 1.8.3, respectively. If $\phi :\equiv (\fa y)(\alpha)$, then $t$ is substitutable for $x$ in $\phi$ by the fact that $t$ does not contain the variable $y$ and $t$ is substitutable for $x$ in $\alpha$. 
	\end{proof}

\end{enumerate}
\end{document}