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

\begin{document}
\title{2.5 - 2.7}
\author{Andrew Lounsbury}
\date{February 16, 2020}
\maketitle

\section{2.5, p.58}

\begin{enumerate}
    \item[2.]
    (E1) and (E3) are valid. 
    \begin{proof}
        Let $\fA$ be an $\Ell$-structure and $s$ an assignment function into $\fA$. It is obvious that $\sbar(x)$ is the same as $\sbar(x)$, so $\fA \vDash (x = x)[s]$ for any $\fA$ with any $s$. Hence, (E1) is valid. \\
        For (E3), suppose $\fA \vDash [(x_1 = y_1) \land (x_2 = y_2) \land \cdots \land (x_n = y_n)][s]$. That is, $s(x_i)$ is $s(y_i)$ for each $i$. 
        \begin{align*}
            (\sbar(x_1),\ldots,\sbar(x_n)) &= (s(x_1),\dots,s(x_n)) \in A^n, \\
            &\stackrel{?}= (x_1,\dots,x_n) \in R^{\fA} \\
            (\sbar(y_1),\ldots,\sbar(y_n)) &= (s(y_1),\dots,s(y_n)) \in A^n.  \\
            &\stackrel{?}= (y_1,\dots,y_n) \in R^{\fA}.
        \end{align*}
        Hence, $\fA \vDash R(x_1,\dots,x_n)[s]$ and $\fA \vDash R(y_1,\dots,y_n)[s]$ for any $\fA$ and any $s$. Since $x_i = y_i$ for each $i$, we know that $\fA \vDash (R(x_1,\dots,x_n) = R(y_1,\dots,y_n))[s]$ for any $\fA$ and any $s$. 
    \end{proof}

    \item[4.]
    If $x$ is not free in $\psi$, then $(\phi \ra \psi) \vDash [(\ex x \phi) \ra \psi]$. 
    \begin{proof}
        Suppose $x$ is not free in $\psi$ and suppose that $\fA \vDash (\phi \ra \psi)$ for some structure $\fA$. So, if $\fA \vDash \phi[s_1]$ for any $s_1$, then $\fA \vDash \psi[s_2]$ for any $s_2$. Now, suppose $\fA \vDash (\ex x \phi)[s]$ so that there is an element $a$ in $A$ for which $\fA \vDash \phi[s(x|a)]$ for any $s$. \\
        We must show $\fA \vDash \psi[s]$ for any $s$. The antecedent tells us that $\fA \vDash \psi[t(x|a)]$ for some element $a$ in $A$ and for any $t$. Since $x$ is not free in $\psi$, any other variable is substitutable for $x$ in $\phi$. Hence, $\fA \vDash \psi[t]$ for any assignment function $t$. 
        %\begin{align*}
        %\fA \vDash (\phi \ra \psi)\\
        %\fA \vDash \phi[s_1] \text{ for any } s_1 \implies \fA \vDash \psi[s_2] &\text{ for any } s_2 \\
        %\fA \vDash (\ex x \phi)[s] &\text{ for any } s \\
        %\fA \vDash \phi[s(x|a)] &\text{ for some element } a \text{ in } A \text{ and any } s \\
        %\fA \vDash \psi[t(x|a)] &\text{ for some element } a \text{ in } A \text{ and any } t \\
        %\text{Since } x \text{ is not free, } \fA \vDash \psi[t] &\text{ for any assignment function } t
        %\end{align*}
        Thus, $\fA \vDash [(\ex x \phi) \ra \psi]$, and $(\phi \ra \psi) \vDash [(\ex x \phi) \ra \psi]$. 
    \end{proof}
\end{enumerate}

\section{2.7, p.66}

\begin{enumerate}
    \item[4.]
    Let $\eta$ be a sentence. Then, $\Sigma \vdash \eta$ if and only if \\
    $\Sigma \cup (\neg \eta) \vdash [(\fa x)x = x] \land \neg [(\fa x)x = x]$. 
    \begin{proof}
        Suppose $\Sigma \vdash \eta$. From $\eta$, we can deduce 
        \[
            [(\fa x)x = x] \lor \neg [(\fa x)x = x] \ra \eta
        \]
        since $[(\fa x)x = x] \lor \neg [(\fa x)x = x]$ is a tautology. We then deduce the contrapositive $\neg \eta \ra [(\fa x)x = x] \land \neg [(\fa x)x = x]$. So, 
        \[
            \Sigma \vdash (\neg \eta \ra [(\fa x)x = x] \land \neg [(\fa x)x = x]). 
        \]
        By the Deduction Theorem, $\Sigma \cup (\neg \eta) \vdash [(\fa x)x = x] \land \neg [(\fa x)x = x]$. \\
        Now, suppose 
        \[
            \Sigma \cup (\neg \eta) \vdash [(\fa x)x = x] \land \neg [(\fa x)x = x],
        \]
        so that 
        \[
            \Sigma \vdash (\neg \eta \ra [(\fa x)x = x] \land \neg [(\fa x)x = x])
        \]
        by the Deduction Theorem. The contrapositive of this results in a tautology implying $\eta$:
        \[
            \Sigma \vdash ([(\fa x)x = x] \lor \neg[(\fa x)x = x] \ra \eta). 
        \]
        Therefore, $\Sigma \vdash \eta$. 
    \end{proof}

    \item[5.]
    Let $P$ be a unary relation symbol. Then, $\vdash [(\fa x)P(x)] \ra [(\ex x) P(x)]$. 
    \begin{proof}
        Suppose $\vdash (\fa x)P(x)$ but $\neg (\ex x) P(x)$. So, for every $x$, $P(x)$ is true, and there is no $x$ such that $P(x)$ is true. This is a blatant contradiction. 
    \end{proof}
\end{enumerate}
\end{document}