\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{hw5-cardinality-functions-relations}
\date{Due: 03/12/2026 at 5pm (late submission until 8am next morning)}
\begin{document}
\maketitle
\thispagestyle{fancy}


{\bf In this assignment},  you will work with cardinality, functions, and binary relations and prove 
properties about them, practicing proof strategies and applications.


{\bf Relevant class material}: Weeks 8, 9, 10.

You will submit this assignment via Gradescope
(\href{https://www.gradescope.com}{https://www.gradescope.com}) 
in the assignment called ``hw5-cardinality-functions-relations''.

\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 Binary relations. In the review quiz, we considered the binary relation on 
    $\mathbb{Z}^+$ defined by 
    \[\{(a,b) \mid \exists c \in \mathbb{Z}(b = ac)\}
    \]
    Let's call that relation $R_1$.
    Consider the following other binary relations on $\mathbb{Z}^{+}$:
    \[
    R_2 = \{ (a,b) \in \mathbb{Z}^+ \times \mathbb{Z}^+ \mid gcd (~ (a,b) ~) = 1\}    
    \]
    \[
    R_3 = \{ (a,b) \in \mathbb{Z}^+ \times \mathbb{Z}^+ \mid a+b \leq 2026\}    
    \]


    \rule{0.5\textwidth}{.4pt}
    
    {\it Sample response that can be used as reference for the detail expected 
    in your answer:} 
    To prove that $R_1$ is not symmetric we need to find a counterexample 
    to 
    \[
        \forall x \in \mathbb{Z}^+ \forall y \in \mathbb{Z}^+ \left(~(x,y) \in R_1 \to (y,x) \in R_1 ~\right)
    \]
    Consider $x = 2$ and $y=4$. Then $(x,y) \in R_1$ because $\exists c \in \mathbb{Z} ( y = xc )$ is witnessed
    by the integer $c = 2$, since $4 = 2 \cdot 2$. However, $\exists c  \in \mathbb{Z} ( x = yc )$ is not
    true: to prove this, we consider an arbitrary integer $c$ and consider the two 
    (exhaustive) cases $c \geq 1$ and $c < 1$. 
    In case 1,
    assume $c \geq 1$, and then $yc = 4c \geq 4 > 3$ so $yc \neq 2 = x$. In case 2, assume $c < 1$ so $c \leq 0$,
    and then $yc = 4c \leq 0$ so is not equal to $2$, which is $x$. Thus, we've found positive integers 
    $x$ and $y$ where $(x,y) \in R_1$ and $(y,x) \notin R_1$ so $R_1$ is not symmetric.

    \rule{0.5\textwidth}{.4pt}
    


    \begin{enumerate}
        \item Give example positive integers that are related
        according to each of these three relations. In other words, give 
        example values $(a_1, b_1)$, $(a_2, b_2)$, and $(a_3, b_3)$ such that
        $(a_i, b_i) \in R_i$ for each $i =1,2,3$.
        \item Prove that $R_2$ is not transitive.
        \item Prove that $R_3$ is not reflexive.
        \item Prove that $R_2$ is symmetric. 
        \item Prove that $R_3$ is not anti-symmetric.
        \item Give an example relation on $\mathbb{Z}^+$ that is both symmetric and anti-symmetric.
        Briefly justify your example.
        \end{enumerate}
    

    \item Equivalence relations.  Recall that we say $a$ is {\bf congruent to} $b$ \textbf{mod} $n$ 
    means $(a, b) \in R_{(\textbf{mod } n)}$, that is $(a \textbf{ mod } n = b \textbf{ mod } n)$.
    A common notation is to write this as $a \equiv b (\textbf{mod } n)$.
    
    A {\bf modular inverse} of an integer $x$ relative to modulus $n$ (where $n$ 
    is a positive number and $x$ is an integer between $0$ and $n-1$, inclusive) 
    is defined to be an integer $y$ between $0$ and $n-1$ (inclusive) such that 
    $xy \equiv 1 (\textbf{mod } n)$.
    \begin{enumerate}
        \item Fill in the two multiplication tables below. In the left table,  each  cell in 
        row labelled $a$ and column labelled $b$ is an integer $p$ in the set $\{0, 1, 2, 3, 4\}$
        satisfying $ab \equiv p ({\textbf{mod } 5})$.
        In the right table, 
        each  cell in 
        row labelled $a$ and column labelled $b$ is an integer $p$ in the set $\{0, 1, 2, 3, 4, 5\}$
        satisfying $ab \equiv p ({\textbf{mod } 6})$.

        \begin{center}
            \begin{tabular}{|c||c|c|c|c|c|}
                \hline
                  & 0 & 1 & 2 & 3 & 4 \\
                  \hline \hline
                0 & 0 & 0 & 0 & 0 & 0 \\
                \hline
                1 & 0 & ~ & ~ & ~ & ~ \\
                \hline
                2 & 0 & ~ & ~ & ~ & ~ \\
                \hline
                3 & 0 & ~ & ~ & ~ & ~ \\
                \hline
                4 & 0 & ~ & ~ & ~ & ~ \\
                \hline
            \end{tabular}
            \hspace{2in}
            \begin{tabular}{|c||c|c|c|c|c|c|}
                \hline
                  & 0 & 1 & 2 & 3 & 4 &5 \\
                  \hline \hline
                0 & 0 & 0 & 0 & 0 & 0 & 0\\
                \hline
                1 & 0 & ~ & ~ & ~ & ~ &\\
                \hline
                2 & 0 & ~ & ~ & ~ & ~ &\\
                \hline
                3 & 0 & ~ & ~ & ~ & ~ &\\
                \hline
                4 & 0 & ~ & ~ & ~ & ~ &\\
                \hline
                5 & 0 & ~ & ~ & ~ & ~ &\\
                \hline
            \end{tabular}
        \end{center}

        \item Does each integer $x$ between $1$ and $4$ (inclusive) have a modular inverse relative to modulus $5$? Does each integer $y$ between $1$ and $5$ (inclusive) have a modular inverse relative to modulus $6$?  Justify your answers using appropriate proof strategies and definitions.

        \item Is there an example of integers $x_1, x_2$ between $1$ and $4$ (inclusive) so that $x_1x_2 \equiv 0 (\textbf{mod } 5)$? Is there an example of integers $y_1, y_2$ between $1$ and $5$ (inclusive) so that $y_1y_2 \equiv 0 (\textbf{mod } 6)$?    Justify your answers using appropriate proof strategies and definitions.

    \end{enumerate}
    


    \item Partial orders. 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 definition 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}
         \]
     
    For this question, we'll restrict our attention to just linked lists with data in the set $\{0,1\}$
    which have length $0$, $1$, or $2$. Let's call this restricted set of lists $L'$.
    
    {\it Note}: $L'$ has $7$ distinct elements.

    Define two different partial orders with domain $L'$. For each of the partial orders, you  can specify its definition by
    listing the set of ordered pairs with roster method, giving a set builder
    definition, giving a recursive definition, or using a clear and precise English description of which lists are related to one another.
    Then, draw the Hasse diagram for each of the two partial orders you defined.


    \item Equivalence classes and partitions. 
    Recall that 
    in a movie recommendation system, each 
    user's ratings of movies is represented as a $n$-tuple (with the positive integer $n$ 
    being the number of movies in the database), and each component of 
    the $n$-tuple is an element of the collection $\{-1,0,1\}$. Assume there are five movies in the database, 
    so that each user's ratings
    can be represented as a $5$-tuple. We call $Rt_5$ the set of all ratings $5$-tuples.
    Consider the binary relation on the  set of all 
    $5$-tuples where each  component of the $5$-tuple is an element of the collection $\{-1,0,1\}$:
    \[
        G = \{ (u,v) \in Rt_5 \times Rt_5 \mid \text{the number of $1$s in $u$ is the same as the number of $1$s in $v$} \}
    \]
    This is an equivalence relation (you do not need to prove this).

    Recall that the {\bf equivalence class} of an element $x \in X$ for an equivalence relation $\sim$ on the set $X$ 
    is the set $\{s \in X | (x, s) \in \sim \}$. We write this as $[x]_\sim$.
    
    \begin{enumerate}
        \item Find a ratings $5$-tuple $v$ such that $[v]_{G} = \{v \}$. Justify your choice of $v$.
        \item Find distinct ratings $5$-tuples $u_1, u_2$ ($u_1 \neq u_2$) whose equivalence classes $[u_1]_{G}$ and $[u_2]_{G}$ have the same size.
        \item Find distinct ratings $5$-tuples $w_1, w_2$ ($w_1 \neq w_2$) whose equivalence classes $[w_1]_{G}$ and $[w_2]_{G}$ have different sizes.
    \end{enumerate}


    \item Modular exponentiation.
    Imagine you are playing the role of Alice in the Diffie Hellman key agreement (exchange) protocol.  
    You and Bob have agreed to use the prime $p = 7$ and its primitive root $a = 3$.
    Your secret integer is $k_1 = 3$.
        
        \begin{enumerate}
        \item  
        Calculate the number you send to Bob, 
        $a^{k_1} \textrm{\bf ~mod~} p$.  Use the modular exponentiation algorithm
        for the calculation. Include a trace of the algorithm in your solution.

        

\begin{algorithm}[caption={Modular Exponentation}]
    procedure $modular~exponentiation$($b$: integer; 
                 $n = (a_{k-1}a_{k-2} \ldots a_1 a_0)_2$, $m$: positive integers)
    $x$ := $1$
    $power$ := $b$ mod $m$
    for $i$:= $0$ to $k-1$
      if $a_i = 1$ then $x$:= $(x \cdot power)$ mod $m$
      $power$ := $(power \cdot power)$ mod $m$
    return $x$ $\{x~\textrm{equals}~b^n \textbf{ mod } m\} $
\end{algorithm}         
        \item  Bob sends you the number $5$. Compute  your shared key, $\left(a^{k_2}\right)^{k_1}  
        \textrm{\bf ~mod~} p$.
        Hint: $a^{k_2} \textrm{\bf ~mod~} p$ is what Bob sent you.  Include all relevant calculations, annotated with explanations, 
        for full credit.
        
        
        \item What are some possible values for Bob's secret integer?  What 
        algorithm are you using to compute them?
        \end{enumerate}


    \end{enumerate}
\end{document}
