hw6-proofs-cardinality-relations

CSE20S24

Due: 6/6/24 at 5pm (no penalty late submission until 8am next morning)

In this assignment, you will work with binary relations and prove properties about them, practicing proof strategies and applications.

Relevant class material: Weeks 9,10.

You will submit this assignment via Gradescope (https://www.gradescope.com) in the assignment called “hw6-proofs-cardinality-relations”.

For all HW assignments: These homework assignments may be done individually or in groups of up to 3 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, 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.

Each homework question will be graded either for correctness (including clear and precise explanations and justifications of all answers) or fair effort completeness. You may collaborate on “graded for correctness” questions only with CSE 20 students in your group; if your group has questions about a problem, you may ask in drop-in help hours or post a private post (visible only to the Instructors) on Piazza. For “graded for completeness” questions: collaboration is allowed with any CSE 20 students this quarter; if your group has questions about a problem, you may ask in drop-in help hours or post a public post on Piazza.

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.

Integrity reminders

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.

Assigned questions

  1. 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 2024 \}\]


    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.


    1. (Graded for completeness) 1 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\).

    2. (Graded for correctness) 2 Prove that \(R_2\) is not transitive.

    3. (Graded for correctness) Prove that \(R_3\) is not reflexive.

    4. (Graded for correctness) Prove that \(R_2\) is symmetric.

    5. (Graded for correctness) Prove that \(R_3\) is not anti-symmetric.

    6. (Graded for completeness) Give an example relation on \(\mathbb{Z}^+\) that is both symmetric and anti-symmetric. Briefly justify your example.

  2. Equivalence relations. Recall that we say \(a\) is congruent to \(b\) 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 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)\).

    1. (Graded for completeness) Fill in the multiplication table below so that 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})\). Then, use this multiplication table to find the modular inverse of each number in \(\{0,1,2,3,4\}\) or to explain why it does not exist.

      0 1 2 3 4
      0 0 0 0 0 0
      1 0        
      2 0        
      3 0        
      4 0        
    2. (Graded for correctness) Find an example \(n\) and integer \(x\) between \(1\) and \(n-1\) (inclusive) so that there is no modular inverse of \(x\) relative to \(n\). Justify your example by exhausting through all the possible values of \(y\) between \(0\) and \(n-1\) and showing that none of them have \(xy \equiv 1 (\textbf{mod } n)\). Note: \(0\) does not have a modular inverse relative to \(n\). In this question, you’re looking for a value of \(n\) where some nonzero number also doesn’t have a modular inverse relative to \(n\).

  3. (Graded for correctness) 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'\).

    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.

  4. 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 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\).

    1. (Graded for correctness) Find a ratings \(5\)-tuple \(v\) such that \([v]_{G} = \{v \}\). Justify your choice of \(v\).

    2. (Graded for completeness) 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.

    3. (Graded for completeness) 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.

  5. 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\).

    1. (Graded for fair effort completeness3) 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.

      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\}\)

    2. (Graded for fair effort completeness) 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.

    3. (Graded for fair effort completeness) What are some possible values for Bob’s secret integer? What algorithm are you using to compute them?


  1. This means you will get full credit so long as your submission demonstrates honest effort to answer the question. You will not be penalized for incorrect answers. To demonstrate your honest effort in answering the question, 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.↩︎

  2. This means your solution will be evaluated not only on the correctness of your answers, but on your ability to present your ideas 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.↩︎

  3. This means you will get full credit so long as your submission demonstrates honest effort to answer the question. You will not be penalized for incorrect answers.↩︎