\documentclass[12pt, oneside]{article}

\usepackage[letterpaper, scale=0.8, centering]{geometry}
\usepackage{fancyhdr}
\setlength{\parindent}{0em}
\setlength{\parskip}{1em}

\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0pt}
\rfoot{{\footnotesize Copyright Mia Minnes, 2026, Version \today~(\thepage)}}

\usepackage{titlesec}

\author{CSE20W26}

\newcommand{\instructions}{{\bf For all HW assignments:} 
These homework assignments may be done individually or in groups of up to four students.
Please ensure your name(s) and PID(s)
are clearly visible on the first page of your homework
submission, start each question on a new page, and upload the PDF to Gradescope.
If you're working in a group, {\it submit only one submission per group}: one partner uploads the
submission through their Gradescope account and then adds the other group member(s) to the Gradescope submission
by selecting their name(s) in the ``Add Group Members'' dialog box. You will need to re-add your group member(s)
every time you resubmit a new version of your assignment.

All submitted homework for this class must be typed. 
You can use a word processing editor if you like (Microsoft Word, Open Office, Notepad, Vim, Google Docs, etc.) 
but you might find it useful to take this opportunity to learn LaTeX. 
LaTeX is a markup language used widely in computer science and mathematics. 
The homework assignments are typed using LaTeX and you can use the source files 
as templates for typesetting your solutions.

{\bf Integrity reminders}
\begin{itemize}
\item Problems should be solved together, not divided up between the partners. The homework is
designed to give you practice with the main concepts and techniques of the course, 
while getting to know and learn from your classmates.
\item Use only resources explicitly allowed for each assignment. Resources not affiliated with this quarter's version of the class may use inconsistent notation or definitions. When consulting resources, balance
getting the help you need while also protecting the learning experience you will have when the `aha' moments of solving the problem authentically happen.
\item Do not share written solutions or partial solutions for homework with 
other students in the class who are not in your group. Doing so would dilute their learning 
experience and detract from their success in the class.
\end{itemize}

When evaluating your homework solutions, we will be considering:
\begin{itemize}
\item The correctness of any final answers.
\item Whether ideas are presented clearly and logically. You should explain how you arrived at your conclusions, using
mathematically sound reasoning. Whether you use formal proof techniques or 
write a more informal argument
for why something is true, your answers should always be well-supported. 
Your goal should be to convince the
reader that your results and methods are sound. A rule of thumb for the level of detail to include is to imagine someone who is taking the class alongside you but missed about a week's worth of content: does your writeup have enough detail for them to learn from it?
\end{itemize}
To demonstrate your honest effort in answering homework questions, we 
expect you to include your attempt to answer *each* part of the question. 
If you get stuck with your attempt, you can still demonstrate 
your effort by explaining where you got stuck and what 
you did to try to get unstuck (e.g. reviewing annotated notes from class, checking the relevant textbook sections, looking up comparable questions on the relevant weekly review quizzes, asking questions on Piazza, 
attending (instructor/TA/tutor) office hours, consulting generative AI tools, etc.). 
}



\usepackage{amssymb,amsmath,pifont,amsfonts,comment,enumerate,enumitem}
\usepackage{currfile,xstring,hyperref,tabularx,graphicx,wasysym}
\usepackage[labelformat=empty]{caption}
\usepackage{xcolor}
\usepackage{multicol,multirow,array,listings,tabularx,lastpage,textcomp,booktabs}

\lstnewenvironment{algorithm}[1][] {   
    \lstset{ mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\rmfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={,procedure, div, for, to, input, output, return, datatype, function, in, if, else, foreach, while, begin, end, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}
\lstnewenvironment{java}[1][]
{   
    \lstset{
        language=java,
        mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\ttfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={, int, double, for, return, if, else, while, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}

\newcommand\abs[1]{\lvert~#1~\rvert}
\newcommand{\st}{\mid}

\newcommand{\A}[0]{\texttt{A}}
\newcommand{\C}[0]{\texttt{C}}
\newcommand{\G}[0]{\texttt{G}}
\newcommand{\U}[0]{\texttt{U}}

\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}

  

\title{hw4-proofs-sets-recursion}
\date{Due: 02/26/2026 at 5pm (late submission until 8am next morning)}
\begin{document}
\maketitle
\thispagestyle{fancy}


{\bf In this assignment}, you will analyze statements and determine if they are true or false using valid proof strategies.
You will also determine if candidate arguments are valid.
You will work with recursively defined sets and functions and prove 
properties about them, practicing induction and other proof strategies.


{\bf Relevant class material}: Weeks 5, 6, and 7.

You will submit this assignment via Gradescope
(\href{https://www.gradescope.com}{https://www.gradescope.com}) 
in the assignment called ``hw4-proofs-sets-recursion''.

\instructions

In your proofs and disproofs of statements below, justify each  step
by reference to  a component of the  following proof  strategies
we  have discussed so far, and/or to relevant definitions and calculations.

\vspace{-10pt}

\begin{itemize}
    \item A counterexample can be used to prove that  $\forall x P(x)$ is {\bf false}.
    \item  A witness can be used  to  prove that  $\exists x P(x)$ is {\bf true}.
    \item {\bf Proof of universal by exhaustion}: To prove that $\forall x \, P(x)$
is true when $P$ has a finite domain, evaluate the predicate at {\bf each} domain element to confirm that it is always T.
    \item  {\bf Proof by universal generalization}: To prove that $\forall x \, P(x)$
is true, we can take an arbitrary element $e$ from the domain and show that $P(e)$ is true, without making any assumptions about $e$ other than that it comes from the domain.
    \item To  prove  that $\exists x P(x)$ is {\bf false}, write the universal statement that is logically equivalent to its negation and then prove it true using universal generalization.
    
\newpage
    \item {\bf Strategies for conjunction}: To prove that $p \land q$ is true, have two subgoals: subgoal (1) prove $p$ 
is  true; and, subgoal (2) prove $q$ is true. To prove that $p \land q$ is false, it's enough to prove that $p$ is false.
 To prove that $p \land q$ is false, it's enough to prove that $q$ is false.
    \item {\bf Proof of Conditional by Direct Proof}: To prove that the implication $p \to q$ is true, we can assume $p$ is true and use that assumption to show $q$ is true.
    \item {\bf Proof of Conditional by Contrapositive Proof}: To prove that the implication $p \to q$ is true, we can assume $\neg q$ is true and use that assumption to show $\neg p$ is true.
    \item {\bf Proof by Cases}: To prove $q$ when we know $p_1 \lor p_2$, show that $p_1 \to q$ and $p_2 \to q$.
    \item  
    {\bf Proof by Structural Induction}: To prove that $\forall x \in X \, P(x)$ where $X$ is a recursively defined set, prove two cases:
        
        \begin{tabularx}{\textwidth}{l X}
        Basis Step: & Show the statement holds for elements specified in the basis step of the definition. \\
        Recursive Step: & Show that if the statement is true for each of the elements used to construct
    new elements in the recursive step of the definition, the result holds for these new elements.
    \end{tabularx}
    
    \item {\bf Proof by Mathematical Induction}: To prove a universal quantification over the set of  all integers greater than  or  equal to some base integer $b$:
    
    \begin{tabularx}{\textwidth}{l X}
        Basis Step: & Show the statement holds for $b$. \\
        Recursive Step: & Consider an arbitrary integer $n$ greater than or  equal to  $b$, assume
        (as the {\bf induction hypothesis})  that the property holds  for $n$, and use  this and
        other facts to  prove that  the property holds for $n+1$.
    \end{tabularx}
    
    \item {\bf Proof by Strong Induction} To prove that a universal quantification over the set of all integers greater than or equal to some  base integer $b$ holds,  pick a  fixed nonnegative integer  $j$ and then: \hfill 
    
    \begin{tabularx}{\textwidth}{l X}
        Basis Step: & Show the statement holds for $b$, $b+1$, \ldots, $b+j$. \\
        Recursive Step: & Consider an arbitrary integer $n$ greater than or  equal to  $b+j$, assume
        (as the {\bf strong  induction hypothesis})  that the property holds  for {\bf each of} $b$, $b+1$, \ldots, $n$, 	
        and use  this and
        other facts to  prove that  the property holds for $n+1$.
    \end{tabularx}

    \item {\bf Proof by Contradiction} 

    To prove that a statement $p$ is true, pick another statement $r$ and once we show
    that $\neg p  \to (r \wedge  \neg r)$ then  we can conclude that  $p$ is  true.
    
    {\it Informally} The statement we care about can't possibly be false, so it must be true.
\end{itemize}


\newpage
{\bf Assigned questions}

\begin{enumerate}[labelindent=0pt, leftmargin=0pt]    
    
    \item Number properties. Consider the predicate  $F(~(a,b)~)  = ``a \text{ is a factor of } b"$ 
    over  the domain $\mathbb{Z}^{\neq 0} \times \mathbb{Z}$. Consider the following quantified
    statements
    \begin{multicols}{2}
    \begin{enumerate}[label=(\roman*)]
    \item $\forall x \in \mathbb{Z} ~(F(~(1,x~)))$
    \item $\forall x \in \mathbb{Z}^{\neq 0} ~(F(~(x,1)~))$
    \item $\exists x \in \mathbb{Z} ~(F(~(1,x)~))$
    \item $\exists x \in \mathbb{Z}^{\neq 0} ~(F(~(x,1)~))$
    \item $\forall x \in \mathbb{Z}^{\neq 0} ~\exists y \in \mathbb{Z} ~(F(~(x,y)~))$
    \item $\exists x \in \mathbb{Z}^{\neq 0} ~\forall y \in \mathbb{Z} ~(F(~(x,y)~))$
    \item $\forall y \in \mathbb{Z} ~\exists x \in \mathbb{Z}^{\neq 0} ~(F(~(x,y)~))$
    \item $\exists y \in \mathbb{Z} ~\forall x \in \mathbb{Z}^{\neq 0} ~(F(~(x,y)~))$
    \end{enumerate}
    \end{multicols}
    
    \begin{enumerate}
    
    \item
    Which of the statements (i) - (viii) is being {\bf proved} by the following proof:
    
    \begin{quote}
      By universal generalization, {\bf choose} $e$ to be an {\bf arbitrary} integer. 
      We need to show that $F(~(1,e)~)$. By definition of the  predicate $F$, we can rewrite 
      this goal as $\exists c \in \mathbb{Z}~(e = c \cdot 1)$. We pick the {\bf witness} $c = e$, 
      which is an integer and therefore in the domain. Calculating, 
      $c \cdot 1 = e \cdot 1 = e$, as required. Since the predicate $F(1,e)$ evaluates to true 
      for the arbitrary integer $e$, the claim has been proved. $\square$
    \end{quote}
    
    
    {\it Hint: it may be useful to 
    identify the key words in the proof that indicate proof strategies.}
    
    \item
    Which of the statements (i) - (viii) is being {\bf disproved} by the following proof:
    
    \begin{quote}
      To disprove the statement, we need to find a counterexample. We choose $2$, a nonzero
      integer so in the domain. We need to show that $\lnot F(~(2,1)~)$. By definition of the predicate $F$, we 
      can rewrite this goal as $1 \textbf{ mod } 2 \neq 0$. By definition of integer division, since 
      $1 = 0 \cdot 2  + 1$ (and $0 \leq 1 < 2$), $1 \textbf { mod } 2 = 1$ which is nonzero so the counterexample works to 
      disprove the original statement.
       $\square$
    \end{quote}
    
    {\it Hint: it may be useful to 
    identify the key words in the proof that indicate proof strategies.}
    
    \item 
    Translate the statement to English, state whether is it true or false, and then justify your answer (by proving the statement or its negation).
({\it Graded for correctness of translation and evaluation of statement (is it true or false?) 
    and fair effort completeness of the proof}) 

    $$\exists x \in \mathbb{Z}^{\neq 0}~ \exists y \in \mathbb{Z}^{\neq 0} ~(~\lnot(x = y) \land F(~(x,y)~) \land F(~(y,x)~)~)$$
    
    \item 
    Translate the statement to English, state whether is it true or false, and then justify your answer (by proving the statement or its negation).
    ({\it Graded for correctness of translation and evaluation of statement (is it true or false?) 
    and fair effort completeness of the proof}) 
    $$\forall x \in \mathbb{Z}^{\neq 0}~ \forall y \in \mathbb{Z}^{\neq 0} ~(~F(~(x,y)~) \to \lnot F(~(y,x)~)~)$$
    
    \item 
    Translate the statement to English, state whether is it true or false, and then justify your answer (by proving the statement or its negation)
    ({\it Graded for correctness of translation and evaluation of statement (is it true or false?) 
    and fair effort completeness of the proof}) 
    $$\exists x \in \mathbb{Z}^{\neq 0}~ \exists y \in \mathbb{Z}~(~F(~(x,y)~) \land  F(~(x+1, y)~) \land F(~(x+2, y)~)~)$$
    
    \item 
    Translate the statement to English, state whether is it true or false, and then justify your answer (by proving the statement or its negation).
    ({\it Graded for correctness of translation and evaluation of statement (is it true or false?) 
    and fair effort completeness of the proof}) 
    $$\forall x \in \mathbb{Z}^{\neq 0}~ (~F(~(x,x^2)~) \land F(~(x,x^3)~)~)$$
    
    \end{enumerate}
    
    \item Structural induction. Recall that we define the set of bases as $B  =  \{ \A, \C, \U, \G \}$.
The set of RNA strands $S$ is defined (recursively) by:
\[
\begin{array}{ll}
\textrm{Basis Step: } & \A \in S, \C \in S, \U \in S, \G \in S \\
\textrm{Recursive Step: } & \textrm{If } s \in S\textrm{ and }b \in B \textrm{, then }sb \in S
\end{array}
\]
where $sb$ is string concatenation. 
The function \textit{rnalen} that computes the length of RNA strands in $S$ is defined recursively by
$rnalen: S  \to \mathbb{Z}^+$


\begin{quote}
Basis step: If $b \in B$ then $rnalen(b)  = 1$

Recursive step: If $s \in S$ and $b \in B$, then $rnalen(sb)  = 1 + rnalen(s)$
\end{quote}

The function \textit{basecount} that computes the number of a given base 
$b$ appearing in a RNA strand $s$ is defined recursively:
    
\[
\begin{array}{llll}
& & \textit{basecount} : S \times B & \to \mathbb{N} \\
\textrm{Basis Step:} &  \textrm{If } b_1 \in B, b_2 \in B & \textit{basecount}(~(b_1, b_2)~) & =
        \begin{cases}
            1 & \textrm{when } b_1 = b_2 \\
            0 & \textrm{when } b_1 \neq b_2 \\
        \end{cases} \\
\textrm{Recursive Step:} & \textrm{If } s \in S, b_1 \in B, b_2 \in B &\textit{basecount}(~(s b_1, b_2)~) & =
        \begin{cases}
            1 + \textit{basecount}(~(s, b_2)~) & \textrm{when } b_1 = b_2 \\
            \textit{basecount}(~(s, b_2)~) & \textrm{when } b_1 \neq b_2 \\
        \end{cases}
\end{array}
\]
\begin{enumerate}
\item 
Translate the statement to English, state whether is it true or false, and then justify your answer (by proving the statement or its negation).
({\it Graded for correctness of translation and evaluation of statement (is it true or false?) 
    and fair effort completeness of the proof}) 
$$\forall b \in B ~\exists s \in S ~(~rnalen(s) = basecount(~(s,b)~)~)$$

\item
Translate the statement to English, state whether is it true or false, and then justify your answer (by proving the statement or its negation).
({\it Graded for correctness of translation and evaluation of statement (is it true or false?) 
    and fair effort completeness of the proof}) 
$$\forall s \in S~ (rnalen(s) > basecount( ~(s,\A)~))$$

\item 
Translate the statement to English, state whether is it true or false, and then justify your answer (by proving the statement or its negation).
({\it Graded for correctness of translation and evaluation of statement (is it true or false?) 
    and fair effort completeness of the proof}) 
$$\forall s \in S~ \forall b \in B ~( basecount( ~(s,b)~) > 0)$$

\end{enumerate}
   \item Games and induction.  The game of Nim-Var is a two-player game (which is a variant of Nim).
    At the start of the game, there are two piles, each containing $n$ 
    jelly beans
    ($n$ is a positive integer).  On a player's turn, that player picks one 
    of the two piles and does {\bf one} of the following: either
    \begin{itemize}
    \item removes some positive number of jelly beans from that pile, {\bf or}
    \item moves some positive number of jelly beans (that is less than the
    current total number of jelly beans in the pile) from that pile to the other.  
    {\it Note: if there is only one jelly bean left in a pile, the player cannot move
    this jelly bean to the other pile.}
    \end{itemize}
    The player to take the last jelly bean wins.  
    Use strong induction to prove that the second player always has a winning strategy in Nim-Move.
    A complete and correct solution will first identify what the strategy is, and then prove that 
    following this strategy will lead the second player to win the game (no matter what the first 
    player chooses to do at each turn).
    
    
    
    \item Linked Lists. Recall the recursive definition of the set of linked lists of 
    natural numbers (from class)
    \[
    \begin{array}{ll}
        \textrm{Basis Step: } & [] \in L \\
        \textrm{Recursive Step: } & \textrm{If } l \in L\textrm{ and }n \in \mathbb{N} \textrm{, then } (n, l) \in L
    \end{array}
    \]
    and the definitions of the function which gives the length of a linked list of natural numbers 
    $length: L \to \mathbb{N}$
        \[
        \begin{array}{llll}
            \textrm{Basis Step:} &  & length(~[]~) &= 0 \\
            \textrm{Recursive Step:} & \textrm{If } l \in L\textrm{ and }n \in \mathbb{N}\textrm{, then  } & length(~(n, l)~)  &= 1+ length(l)
        \end{array}
    \]
    the function $append : L \times \mathbb{N} \to L$ that 
    adds an element at the end of a linked list
    \[
        \begin{array}{llll}
        \textrm{Basis Step:} & \textrm{If } m \in \mathbb{N}\textrm{ then } & append(~([], m)~) & = (m, [])\\
        \textrm{Recursive Step:} & \textrm{If } l \in L\textrm{ and }n \in \mathbb{N}\textrm{ and }m \in \mathbb{N}\textrm{, then  } & append(~(~(n, l), m~)~)  &= (n, append(~(l, m)~)~)
        \end{array}
    \]
    and the function $prepend : L \times \mathbb{N} \to L$ that adds an element at the 
    front of a linked list 
    \[
    prepend(~(l, n)~) = (n, l)
    \]

    \rule{0.5\textwidth}{.4pt}
    
    {\it Sample response that can be used as reference for the detail expected 
    in your answer:} 
    To evaluate the result of $length(~(4,(2,(7,[])))~)$ we calculate: 
    \begin{align*}
        length(~(4,(2,(7,[])))~) &= 1 + length ( ~(2,(7,[]))~) \\
        & \qquad \qquad \text{using recursive step of definition of $length$, with $n=4, l=(2,(7,[]))$} \\
        &= 1 + 1 + length ( ~(7,[])~) \\
        & \qquad \qquad \text{using recursive step of definition of $length$, with $n=2, l=(7,[])$} \\
        &= 1 + 1 + 1+ length ( ~[]~) \\
        & \qquad \qquad \text{using recursive step of definition of $length$, with $n=7, l=[]$} \\
        &= 1 + 1 + 1 + 0\\
        & \qquad \qquad \text{using basis step of definition of $length$, since input to $length$ is $[]$} \\
    \end{align*}
    \rule{0.5\textwidth}{.4pt}
    

    In this question, we'll consider the combination of these functions with a new function, one 
    that removes the element at the front of the list (if there is any). We define $remove: L \to L$
    by
    \[
        \begin{array}{ll}
            \textrm{Basis Step: } & remove([]) = [] \\
            \textrm{Recursive Step: } & \textrm{If } l \in L\textrm{ and }n \in \mathbb{N} \textrm{, then } remove(~(n, l)~) = l
        \end{array}        
    \]
    \begin{enumerate}
        \item What is the result of $remove(~append(~(prepend~(~(~(10,[]), 5~)~), 20)~)~)$? 
        For full credit, include all intermediate steps with brief justifications for each.
        \item Prove the statement
        \[
            \forall l \in L \left(~ remove( prepend(~(l,0)~)) = l ~\right) 
        \]
        \item Disprove the statement
        \[
            \forall l \in L \left(~ remove( append(~(l,0)~)) = l ~\right) 
        \]
    \end{enumerate}

    \item Primes, divisors, and proof strategies. For each statement below, identify the {\bf main logical structure or connective} of the 
    statement, list the proof strategies that could be used to prove and to disprove a statement with that structure, 
    then identify whether the statement is true or false and justify with a proof of the statement or its negation. 
    ({\it Graded for correctness of identification of logical structure and proof strategies and evaluation of statement (is it true or false?) 
    and fair effort completeness of the proof}) 


    \rule{0.5\textwidth}{.4pt}
    
    {\it Sample response that can be used as reference for the detail expected 
    in your answer:} 

    Consider the statement: There is a greatest negative integer.

    The main logical structure for this statement is that it is an {\bf existential} statement, as we can 
    see by translating it to symbols: 
    \[
        \exists g \in \mathbb{Z}^{-} \forall x \in \mathbb{Z}^{-} ( g \geq x)
    \]
    To prove an existential statement, the main proof strategy we could use is to find a witness. 
    Proof by cases and proof by contradiction could also be used, because 
    both can be used to prove any statement (no matter its logical structure).

    To disprove an existential statement, we would need to prove its negation, which (using DeMorgan's Laws) can be 
    written as a universal statement. Therefore, to disprove this statement the strategies we could use are 
    universal generalization or structural induction (because $\mathbb{Z}^{-}$ is a recursively defined set) or 
    proof by cases or proof by contradiction. Notice that proof by exhaustion is not possible because the domain is not finite.

    The statement is true, as we can see from the witness $g = -1$, since it is in the domain $\mathbb{Z}^{-}$ and when we evaluate
    \[
        \forall x \in \mathbb{Z}^{-} ( -1 \geq x)
    \]
    we can proceed by universal generalization and take an arbitrary negative integer $x$, which by definition means $x < 0$, 
    and since $x$ is an integer, guarantees $x \leq -1 = g$, as required.
    \rule{0.5\textwidth}{.4pt}

        \begin{enumerate}
            \item The quotient of any even number with any nonzero even number is even.
            \item There are two odd numbers (not necessarily distinct) whose sum is even.
            \item The greatest common divisor of 5 and 23 is 1 and the greatest common divisior of 7 and 19 is 1.
            \item There are two positive integers greater than 20 that have the same greatest common divisor with 20.
        \end{enumerate}
\end{enumerate}
\end{document}
