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

\begin{document}
\title{1.9-2.4}
\author{Andrew Lounsbury}
\date{February 11, 2020}
\maketitle

\section{1.9, p.38}

\begin{enumerate}
\item
For any formulas $\alpha$ and $\beta$, $\{\alpha, \alpha \rightarrow \beta\} \vDash \beta$. 
\begin{proof}
	Let $\fA$ be an $\Ell$-structure. 
	Suppose $\fA \vDash \{\alpha, \alpha \ra \beta\}$. So, $\fA \vDash \alpha[s]$ and $\fA \vDash (\alpha \ra \beta)[s]$ for every assignment function $s$ into $\fA$. Then, $\fA \nvDash \alpha[s]$ for every $s$ or $\fA \vDash \beta[s]$ for every $s$. Since $\fA \vDash \alpha[s]$ for every $s$, it must be the case that $\fA \vDash \beta[s]$ for every $s$. Therefore, $\{\alpha, \alpha \ra \beta\} \vDash \beta$. 
\end{proof}

Modus ponens

\item[4.]
	\begin{enumerate}
	\item
	If $\vDash(\phi \rightarrow \psi)$, then $\phi \vDash \psi$. 
	\begin{proof}
	%Suppose $\vDash(\phi \ra \psi)$ so that $(\phi \ra \psi)$ is true in every $\Ell$-structure with every assignment function $s$. So, $\fA \vDash (\phi \ra \psi)[s]$ for every $\Ell$-structure $\fA$ and any assignment function $s$. So, $\fA \nvDash \phi[s]$ or $\fA \vDash \psi[s]$ for every $\fA$ and any $s$. 
	
	Suppose $\vDash(\phi \ra \psi)$ so that $\fA \vDash (\phi \ra \psi)[s]$ for every $\fA$ and every $s$. Then, $\fA \vDash \phi[s] \implies \fA \vDash \psi[s]$ for every $\fA$ and every $s$. Hence, for every $\fA, s_1$, and $s_2$, we have $\fA \vDash \phi[s_1] \implies \fA \vDash \psi[s_2]$. Thus, $\phi \vDash \psi$. 
	\end{proof}
	
	\item
	If $\phi$ is $x < y$ and $\psi$ is $z < w$, then $\phi \vDash \psi$, but $\nvDash(\phi \rightarrow \psi)$. 
	\begin{proof}
	To show $\phi \vDash \psi$, suppose $\fA \vDash x < y$ so that $\fA \vDash x < y[s]$ for every $s$. So, $<^{\fA} = A \times A$, where $A$ is the universe of $\fA$. In other words, $a <^{\fA} b$ holds for any $a$ and $b$ in $A$, which means $\fA \vDash z < w[s]$ for all $s$. Hence, $\fA \vDash z < w$. Thus, $\fA \vDash \phi[s] \implies \fA \vDash \psi[s]$ for every $\fA$ and every $s$, which means $\fA \vDash(\phi \ra \psi)[s]$ for every $\fA$. Therefore, $\vDash (\phi \ra \psi)$, which gives $x < y \vDash z < w$. \\
	Now, let $\fN$ (the structure for natural numbers) be the model and let $s$ be an assignment function into $\fN$ such that $s(x) = s(w) = 0$ and $s(y) = s(z) = 1$. Then, $\fN \nvDash x < y$ and $\fN \nvDash z < w$, so $\fN \nvDash (x < y \ra z < w)$. Therefore, $\nvDash (x < y \ra z < w)$, or $\nvDash (\phi \ra \psi)$, as desired. 
	\end{proof}
	\end{enumerate}
\end{enumerate}

\section{2.2,p.47}

\begin{enumerate}
	\item
	$\Sigma = \{[(A(x) \land A(x)) \ra B(x,y)], A(x), [B(x,y) \ra A(x)]\}$ \\
	ROI: modus ponens
		\begin{enumerate}
			\item
			$A(x), ~A(x) \land A(x), ~(A(x) \land A(x)) \ra B(x,y), ~B(x,y)$
			
			Not a deduction: $(A(x) \land A(x)) \ra A(x)$ is not in $\Sigma$, and $A(x) \land A(x)$ (probably?) cannot be deduced given $A(x)$ alone. 
			
			\item
			$B(x,y) \ra A(x), ~A(x), ~B(x,y)$
			
			Not a deduction: We must have $B(x,y)$ in order to deduce $A(x)$, and we must have $(A(x) \ra B(x,y))$ is in $\Sigma$ in order to deduce $B(x,y)$. 
			
			\item
			$(A(x) \land A(x)) \ra B(x,y), ~B(x,y) \ra A(x), ~(A(x) \land A(x)) \ra A(x)$
			This is a deduction. 
			
			\end{enumerate}
			
	\item[4.]
	$\Ell \is \{R^1\}$ \\
	$B = \{R(x_1),~ R(x_1) \ra R(x_2),~ R(x_2) \ra R(x_3), \ldots, R(x_i) \ra R(x_{i+1})\}$ \\
	ROI: modus ponens

	$B \vdash R(x_j$ for each natural number $j \ge 1$. 
	\begin{proof}
		\bc We have $B \vdash R(x_1)$ and $B \vdash (R(x_1) \ra R(x_2))$. Thus, $B \vdash R(x_2)$. \\
		\ind Suppose $B \vdash R(x_k)$ for some $k \in \N$. By our definition of $B$, we have that $B \vdash (R(x_k) \ra R(x_{k+1})$. Hence, $B \vdash R(x_{k+1})$. Therefore, $B \vdash R(x_i)$ for every natural number $j \ge 1$. 
	\end{proof}
		
\end{enumerate}

\section{2.4, p. 54}

\begin{enumerate}
\item[3.]
see notes

\item[5.]
	\begin{enumerate}
	\item
	$D = (\ex x \neg R(x)), \neg\fa x R(x), (\fa x P(x)) \lor (\fa x R(x)), \fa x P(x), (\fa x P(x)) \ra Q(y), Q(y))$
	
	Considering the deduction $D$, we see that $\phi :\equiv Q(y)$ is a propositional consequence of $\Gamma$. 
	
	\item
	The only formula in $\Gamma$ that might allow us to determine (deduce?) that $\phi$ is true is $Q(y) \lor x + y < z$, but the assumption (?) of the only other formula we have at our disposal forces $Q(y)$ to be true. We cannot determine whether or not $\phi$ is true, so $\phi$ is not a propositional consequence of $\Gamma$. 
	
	\item
	$D = ((\neg P(x,y,x)) \land (\neg x < y), \neg x < y, (x < y) \lor M(w,p), M(w,p))$
	
	Assuming (?) the formulas of $\Gamma$, we have found through the deduction $D$ that $\phi :\equiv \neg M(w,p)$ is false. Thus, $\phi$ is a propositional consequence of $\Gamma$. (1st \& 3rd formulas contradict each other?)
	
	\end{enumerate}

\end{enumerate}
\end{document}