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

\begin{document}
\title{6.3, 6.6}
\author{Andrew Lounsbury}
\date{April 20, 2020}
\maketitle

\section{6.3, p.181}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{enumerate}
    \item[1.]
    If $A$ is a set of formulas, then $Th(A) = \{\sigma \mid A \vdash \sigma\}$ is a theory. 
    \begin{proof}
        Let $\phi$ be a formula such that $Th(A) \vdash \phi$. We must show $A \vdash \phi$ so that $\phi \in Th(A)$. \\
        $Th(A) \vdash \phi$ means there are $\sigma_i \in Th(A)$, $1 \le i \le n$,  such that $D = (\sigma_1,\dots,\sigma_n,\phi)$ is a deduction. Since $A \vdash \sigma_1,\dots, A \vdash \sigma_n$, we know that, for each $i$, there are $\sigma_{ij} \in A$, $1 \le j \le n$ such that $(\sigma_{i1},\dots,\sigma_{in},\sigma_i)$ is a deduction in $A$. When we line up these deductions so that $D$ is the very last deduction listed, we have a deduction of $\phi$ in $A$. Thus, $\phi \in Th(A)$, and $Th(A)$ is a theory. 
    \end{proof}
\end{enumerate}

\section{6.6, p.192}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{enumerate}
    \item[1.]
    The universal quantification over sets $A$ in $\mathbb{N}$ makes mathematical induction a principle of higher-order logic (second order, to be precise). 

    \item[2.]
    Suppose $\theta$ and $\eta$ are two sentences that assert their own refutability in $PA$. That is, 
    \[
        PA \vdash \left[\theta \leftrightarrow \neg Thm_{PA}\left(\ol{\ulcorner \theta \urcorner}\right)\right]
    \]
    and
    \[
        PA \vdash \left[\eta \leftrightarrow \neg Thm_{PA}\left(\ol{\ulcorner \eta \urcorner}\right)\right]. 
    \]
    Then, $PA \vdash \theta \leftrightarrow \eta$. 
    \begin{proof}
        \begin{alignat*}{2}
            PA &\vdash \theta && \\
            PA &\vdash \neg Thm_{PA}(\ol{\ulcorner \theta \urcorner}) && def.\\
            PA &\vdash \neg\theta && (D1) \\
            PA &\vdash Thm_{PA}(\ol{\ulcorner \theta \urcorner}) && (D1) \\
            PA &\vdash Thm_{PA}(\ol{\ulcorner Thm_{PA}(\ol{\ulcorner \theta \urcorner}) \urcorner}) && (D2) \\
            PA &\vdash Thm_{PA}(\ol{\ulcorner \neg\theta \lor \eta \urcorner}) && (3) \\
            PA &\vdash Thm_{PA}(\ol{\ulcorner \theta \rightarrow \eta \urcorner}) && \\
            PA &\vdash \left[Thm_{PA}(\ol{\ulcorner \theta \urcorner}) \land Thm_{PA}(\ol{\ulcorner \theta \rightarrow \eta \urcorner})\right] && (4,7) \\
            PA &\vdash Thm_{PA}(\ol{\ulcorner \eta \urcorner}) && (D3) \\
            PA &\vdash \eta && (D1)
        \end{alignat*}
        Thus, $PA \vdash \theta \rightarrow \eta$. 
        \begin{alignat}{2}
            PA &\vdash \eta && \\
            PA &\vdash \neg Thm_{PA}(\ol{\ulcorner \eta \urcorner}) && def.\\
            PA &\vdash \neg\eta && (D1) \\
            PA &\vdash Thm_{PA}(\ol{\ulcorner \eta \urcorner}) && (D1) \\
            PA &\vdash Thm_{PA}(\ol{\ulcorner Thm_{PA}(\ol{\ulcorner \eta \urcorner}) \urcorner}) && (D2) \\
            PA &\vdash Thm_{PA}(\ol{\ulcorner \neg\eta \lor \theta \urcorner}) && (13) \\
            PA &\vdash Thm_{PA}(\ol{\ulcorner \eta \rightarrow \theta \urcorner}) && \\
            PA &\vdash \left[Thm_{PA}(\ol{\ulcorner \eta \urcorner}) \land Thm_{PA}(\ol{\ulcorner \eta \rightarrow \theta \urcorner})\right] && (14,17) \\
            PA &\vdash Thm_{PA}(\ol{\ulcorner \theta \urcorner}) && (D3) \\
            PA &\vdash \theta && (D1)
        \end{alignat}
        Therefore, $PA \vdash \theta \leftrightarrow \eta$. 
    \end{proof}
\end{enumerate}
\end{document}