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

\begin{document}
\title{1.4}
\author{Andrew Lounsbury}
\date{January 30, 2020}
\maketitle

\section{1.4, p.17}

\begin{enumerate}
    \item[1.]
    The sum of the interior angles in a convex $n$-gon is $(n-2) \cdot 180^{\circ}$. 
    \begin{proof}
    \underline{Base case}: 
    ~\vspace{1in} \\
    \underline{Induction step}: Suppose a $k$-gon, where $k$ is arbitrary, has interior angles that sum to $(k-2) \cdot 180^{\circ}$. This $k$-gon has $k$ interior angles. If we add another edge to form a $(k+1)$-gon, that $(k+1)$-gon has $k+1$ interior angles. If we pick a point on the $(k+1)$-gon and connect it to the other $k+1-3 = k-2$ nonadjacent points, we split the $(k+1)$-gon into $k-1$ triangles whose angles together form the angles of the $(k+1)$-gon. Since each triangle's interior angles has $180^{\circ}$, the sum of the $(k+1)$-gon's interior angles is $(k-1) \cdot 180^{\circ} = ((k+1)-2) \cdot 180^{\circ}$, as desired.
    \end{proof}

    \item[5.]
    Let $\Ell$ be the language $\{0,<\}$. \\
    The number of symbols in any formula is divisible by 3. 
    \begin{proof}
    The atomic formulas here are $0 = 0$ and $0 < 0$, and each has 3 symbols. If $\alpha$ and $\beta$ are atomic formulas with $a$ symbols in $\alpha$ and $b$ symbols in $\beta$, then $(\neg\alpha)$ has $a+3$ symbols, $(\alpha \lor \beta)$ has $a+b+3$ symbols and $(\forall v)(\alpha)$ has $a+6$ symbols. Since $3 \mid a$ and $3 \mid b$, we also have $3 \mid a+b+3, 3 \mid a+6$, and $3 \mid a+b+3$. Thus, the number of symbols is always divisible by 3. 
    \end{proof}

    \item[6.]
    If $s$ and $t$ are terms, then $s$ is not an initial segment of $t$. 
    \begin{proof}
    \bc If $s$ is a variable or a constant symbol and $t$ is as well, then when we write $t:\equiv su$, where $u$ is a nonempty string, we know that $u$ must be an empty, contradicting the assumption that $s$ is an initial segment of $t$. \\
    In the case where $t:\equiv ft_1\cdots t_n$ and $f$ is a function symbol and $t_1,\dots,t_n$ are terms, we would have to have $s:\equiv f$, where $f$ is a nullary function symbol. However, this means $u$ must be empty, a contradiction. \\
    \is Now, suppose the term $s:\equiv ft_1\cdots t_n$, is an initial segment of the term $t$. If $t$ is a variable or a constant, then when we try to write $t:\equiv su$ for some nonempty string $u$, we must have $s:\equiv f$, where $f$ is a nullary function symbol. This forces $u$ to be an empty string, which is a contradiction. \\
    In the case where $t:= gr_1\cdots r_m$, where $g$ is a function symbol and $r_1,\dots,r_m$ are terms, we must have $f:\equiv g$ since they are the functions at the beginning of $s$ and $t$, respectively. 
    \end{proof}

\end{enumerate}
\end{document}