\input{config}

\title{Problem Set 5}
\author[Daniel Gonzalez Cedre]{Discrete Mathematics}
\publisher{University of Notre Dame}
\date{Due on the \red{27\textsuperscript{th} of February, 2024}}

\begin{document}

\maketitle

\marginnote{%
  Recall that the natural numbers are defined recursively as follows.
  \begin{align*}
    0     &\defeq \emptyset \\
    \s{n} &\defeq n \union \set{n}
  \end{align*}
  % We define the basic arithmetic arithmetic operations on $\naturals$ as follows.
  Addition on $\naturals$ is defined below.
  \begin{align*}
    n + 0     &\defeq n \\
    n + \s{m} &\defeq \s{n + m}
  \end{align*}
  Multiplication on $\naturals$ is defined below.
  \begin{align*}
    n \cdot 0     &\defeq 0 \\
    n \cdot \s{m} &\defeq (n \cdot m) + n
  \end{align*}
  Exponentiation on $\naturals$ is defined below.
  \begin{align*}
    n^0       &\defeq 1 \\
    n^{\s{m}} &\defeq n \cdot n^{m}
  \end{align*}
  We define the iterated sum of a sequence of terms $f(0), f(1), f(2), \dots$ as follows.
  \begin{align*}
    \sum_{i = 0}^{0} f(i)     &\defeq f(0) \\
    \sum_{i = 0}^{\s{n}} f(i) &\defeq \term*{\sum_{i = 0}^{n} f(i)} + f\term*{\s{n}}
  \end{align*}
  % We define the linear partial order you are familiar with on $\naturals$ below.
  % \begin{align*}
    % n \leq m  &\iffbydefn (\exists x \in \naturals)(n + x = m) \\
    % n < m     &\iffbydefn (n \leq m) \land (n \neq m)
  % \end{align*}
  You may rely on the following theorems:

  $(\forall x \in \naturals)(\s{x} = x + 1)$.

  $(\forall x \in \naturals)(\s{x} = 1 + x)$.

  $(\forall x, y, z \in \naturals)(x + (y + z) = (x + y) + z)$.
  % \begin{itemize}
    % \item
      % $(\forall x \in \naturals)(\s{x} = x + 1)$.
    % \item
      % $(\forall x \in \naturals)(\s{x} = 1 + x)$.
    % \item
      % % $(\forall x, y, z \in \naturals)
      % % $x + (y + z) = (x + y) + z$ for all $x, y \in \naturals$.
      % $(\forall x, y, z \in \naturals)(x + (y + z) = (x + y) + z)$.
  % \end{itemize}
}

\begin{enumerate}
  % \item[(15 pts) \quad 1.]
    % Show that $\forall x \forall y \forall z (x \union (y \intersect z) = (x \union y) \intersect (x \union z))$.
  % \item[(15 pts) \quad 1.]
    % Show $(\forall x, y, z \in \naturals)\term*{\term*{x \leq y} \implies \term*{x + z \leq y + z}}$

  \item[(10 pts) \quad 1.]
    Find and explain the flaw(s) in this argument.
    \begin{mdframed}
      We prove every nonempty set of people all have the same age.
      \begin{proof}
        % We induct on the number of people in the set.
        We denote the age of a person $p$ by $\alpha(p)$.

        \begin{case}[Basis Step]
          Suppose $P = \set{p}$ is a set with one person in it.
          Clearly, all the people in $P$ have the same age as each other.
          % Then, $p \in P$ for some person $p$.
          % This person has some age $\alpha(p)$, and since $\forall x (x \in P \iff x = p)$, we must have $\forall x (x \in P \iff \alpha(x) = \alpha(p))$.
          % Clearly, $\forall x \forall y (x \in P \land y \in P \iff \alpha(x) = \alpha(y))$, so everyone in $P$ has the same age.
        \end{case}
        \begin{case}[Inductive Step]
          Let $k \in \naturals_+$ and suppose any set of $k$-many people all have the same age.
          Let $P = \set{p_1, p_2, \dots p_k, p_{k + 1}}$ be a set with $k + 1$ people in it.
          Consider $L \defeq \set{p_1, \dots p_k}$ and $R \defeq \set{p_2, \dots p_{k + 1}}$.
          Since $L$ and $R$ both have $k$ people, we know everyone in these sets has the same age by the \emph{inductive hypothesis.}
          % Everyone in $L \intersect R = \set{p_2, \dots p_k}$ has the same age for the same reason.

          Let $\ell, r \in P$.
          If $\ell \in L \land r \in L$, then $\alpha(\ell) = \alpha(r)$.
          Similarly, if $\ell \in R \land r \in R$, then $\alpha(\ell) = \alpha(r)$.
          Now, suppose $\ell \in L \land r \in R$.
          % Then, $\alpha(\ell) = \alpha(p_1)$ and $\alpha(p_{k + 1}) = \alpha(r)$.
          \begin{equation*}
            \alpha(\ell) = \alpha(p_1) = \alpha(p_2) = \alpha(p_{k + 1}) = \alpha(r)
          \end{equation*}
          So, all people in $P$ have the same age.
        \end{case}

        Therefore, everyone on Earth has the same age.
      \end{proof}
    \end{mdframed}

  \item[(20 pts) \quad 2.]
    % Show that $\forall x \term{x \neq \s{x}}$.
    Show that $\forall x \term{x \neq x \union \set{x}}$.

  \item[(15 pts) \quad 3.]
    We will work up to a proof of the commutativity of addition on $\naturals$.
    \begin{enumerate}
      \item
        Show $(\forall x \in \naturals)(x + 0 = 0 + x)$.
      \item
        Show $(\forall x, y \in \naturals)(x + \s{y} = \s{y} + x)$.
      \item
        Show $(\forall x, y \in \naturals)(x + y = y + x)$.
    \end{enumerate}

  \item[(15 pts) \quad 4.]
    Show $(\forall x, y, z \in \naturals)\term*{x \cdot (y + z) = (x \cdot y) + (x \cdot z)}$.

  % \item[(0 pts) \quad 4.]
    % Show $(\forall x, y, z \in \naturals)\term*{x \cdot (y \cdot z) = (x \cdot y) \cdot z}$.

  % \item[(20 pts) \quad 3.]
    % Show that $(\forall x \in \naturals)(\forall y \in \naturals)(x < y \implies x \in y)$.

  \item[(20 pts) \quad 5.]
    % The \defn{Fibonacci sequence} is the function $\mathfrak{F}: \naturals \to \naturals$ defined below.
    % \begin{align*}
      % \mathfrak{F}(0) &\defeq 0 \\
      % \mathfrak{F}(1) &\defeq 1 \\
      % \mathfrak{F}(n + 2) &\defeq \mathfrak{F}(n + 1) + \mathfrak{F}(n)
    % \end{align*}
    % For this problem, you may assume the commutativity of addition and multiplication, associativity of addition and multiplication, and that multiplication distributes over addition on $\naturals$.
    For this problem, you may assume the commutativity and associativity of addition and multiplication over $\naturals$.
    You may also assume multiplication distributes over addition on $\naturals$.
    Prove the following statement for all $n \in \naturals$.
    \begin{equation*}
      1 + \sum_{i = 0}^{n} 2^i = 2^{n + 1}
    \end{equation*}

  \item[(20 pts) \quad 6.]
    We say $x$ is \defn{$\in$-transitive} by definition when $(\forall y \in x)(\forall z \in y)(z \in x)$. \\
    Show that every natural number is $\in$-transitive.
    % Show that $(\forall x \in \naturals)(x \text{ is transitive})$.
    % \begin{enumerate}
      % \item
        % Show that $\forall x \term{x \neq \s{x}}$.
      % % \item
        % % Show that $(\forall x, y \in \naturals)(x < y \implies x \in y)$.
      % \item
        % Show that $(\forall x \in \naturals)(x \text{ is transitive})$.
    % \end{enumerate}
\end{enumerate}

\end{document}
