HW4 Proofs and Sets

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.

Instructions and academic integrity reminders for all homework assignments in CSE20 this quarter are on the class website and on the hw1-definitions-and-notations assignment.

You will submit this assignment via Gradescope (https://www.gradescope.com) in the assignment called “hw4-proofs-and-sets”.

Resources: To review the topics you are working with for this assignment, see the class material from Week 5. We will post frequently asked questions and our answers to them in a pinned Piazza post.

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.

• A counterexample can be used to prove that \(\forall x P(x)\) is false.

• A witness can be used to prove that \(\exists x P(x)\) is true.

• Proof of universal by exhaustion: To prove that \(\forall x \, P(x)\) is true when \(P\) has a finite domain, evaluate the predicate at each domain element to confirm that it is always T.

• 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.

• To prove that \(\exists x P(x)\) is false, write the universal statement that is logically equivalent to its negation and then prove it true using universal generalization.

• 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.

• 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.

• 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.

• Proof of disjuction using equivalent conditional: To prove that the disjunction \(p \lor q\) is true, we can rewrite it equivalently as \(\lnot p \to q\) and then use direct proof or contrapositive proof.

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

Assigned questions

1. Consider the predicate \(Pr(x)\) over the set of integers, which evaluates to \(T\) exactly when \(x\) is prime. Consider the following statements.

   2

   1. \(\exists x \in \mathbb{Z}~ \forall y \in \mathbb{Z}~(~x \leq y \to Pr(y)~)\)

   2. \(\exists x \in \mathbb{Z}~ \forall y \in \mathbb{Z}~(~y \leq x \to Pr(y)~)\)

   3. \(\forall x \in \mathbb{Z}~ \exists y \in \mathbb{Z}~(~x \leq y \to Pr(y)~)\)

   4. \(\forall x \in \mathbb{Z}~ \exists y \in \mathbb{Z}~(~y \leq x \to Pr(y)~)\)

   5. \(\exists x \in \mathbb{Z}~ \forall y \in \mathbb{Z}~(~Pr(y) \to y \leq x~)\)

   6. \(\exists x \in \mathbb{Z}~ \forall y \in \mathbb{Z}~(~Pr(y) \to x \leq y~)\)

   7. \(\forall x \in \mathbb{Z}~ \exists y \in \mathbb{Z}~(~Pr(y) \to y \leq x~)\)

   8. \(\forall x \in \mathbb{Z}~ \exists y \in \mathbb{Z}~(~Pr(y) \to x \leq y~)\)

   1. (Graded for correctness of choice and fair effort completeness in justification ¹) Which of the statements (i) - (viii) is being proved by the following proof:

      Choose \(x = 1\), an integer, and we will work to show it is a witness for the existential claim. By universal generalization, choose \(e\) to be an arbitrary integer. Towards a direct proof, assume that \(Pr(e)\) holds. We WTS that \(1 \leq e\). By definition of the predicate \(Pr\), since \(Pr(e)\) is true, \(e > 1\). By definition of \(\leq\), this means that \(1 \leq e\), as required and the claim has been proved. \(\square\)

      Hint: it may be useful to identify the key words in the proof that indicate proof strategies.

   2. (Graded for correctness of choice and fair effort completeness in justification) Which of the statements (i) - (viii) is being disproved by the following proof:

      To disprove the statement, we will prove the universal statement that is logically equivalent to its negation. By universal generalization, choose \(e\) to be an arbitrary integer. We need to find a witness integer \(y\) such that \(y \leq e\) and \(\lnot Pr(y)\). Notice that \(e > 1 \lor e \leq 1\) is true, and we proceed in a proof by cases. Case 1: Assume \(e > 1\) and WTS there is a witness integer \(y\) such that \(y \leq e\) and \(\lnot Pr(y)\). Choose \(y = 0\), an integer. Then, since by case assumption \(1 < e\), we have \(y = 0 \leq 1 \leq e\). Moreover, since \(y = 0\), \(y > 1\) is false and so (by the definition of \(Pr\)), the predicate \(Pr\) evaluated at \(y\) is false, as required to prove the conjunction \(y \leq e\) and \(\lnot Pr(y)\). Case 2: Assume \(e \leq 1\) and WTS there is a witness integer \(y\) such that \(y \leq e\) and \(\lnot Pr(y)\). Choose \(y = e-1\), an integer (because subtracting \(1\) from the integer \(e\) still gives an integer). By definition of subtraction, \(y = e-1 \leq e\). Moreover, since by the case assumption \(y = e-1 \leq 1-1= 0\), \(y > 1\) is false. Thus, (by the definition of \(Pr\)), the predicate \(Pr\) evaluated at \(y\) is false. We have proved the conjunction \(y \leq e\) and \(\lnot Pr(y)\) as required. Since each case is complete, the proof by cases is complete and the original statement has been disproved. \(\square\)

      Hint: it may be useful to identify the key words in the proof that indicate proof strategies.

   3. (Graded for correctness of evaluation of statement (is it true or false?) and fair effort completeness of the translation and of the proof) Translate the statement to English and then prove or disprove it \[\forall x \in \mathbb{Z}~ \forall y \in \mathbb{Z}~(~x \neq y \to (Pr(x) \lor Pr(y))~)\]

   4. (Graded for correctness of evaluation of statement (is it true or false?) and fair effort completeness of the translation and proof) Translate the statement to English and then prove or disprove it \[\left( ~\forall x \in \mathbb{Z} ~Pr(x)~\right) \oplus \left(~\exists x \in \mathbb{Z} ~Pr(x) ~\right)\]

   5. (Graded for correctness of evaluation of statement (is it true or false?) and fair effort completeness of the translation and of the proof) Translate the statement to English and then prove or disprove it \[\forall x \in \mathbb{Z}~ \forall y \in \mathbb{Z}~(~(~Pr(x) \land Pr(y)~) \leftrightarrow Pr(x+y)~)\]

   6. (Graded for correctness of evaluation of statement (is it true or false?) and fair effort completeness of the translation and of the proof) Translate the statement to English and then prove or disprove it \[\forall x \in \mathbb{Z}~ (~Pr(x) \to \exists y \in \mathbb{Z}~(~x < y \land Pr(y)~)\]

2. Let \(W = \mathcal{P}(\{1,2,3,4,5\})\).

   ---

   Sample response that can be used as reference for the detail expected in your answers for this question:

   To give a witness for the existential claim \[\exists B \in W~( B \in ~\{ X \in W ~|~ 1 \in X \} \cap \{ X \in W ~|~ 2 \in X \}~~)\] consider \(B = \{ 1,2\}\). To prove that this is a valid witness, we need to show that it is in the domain of quantification \(W\) and that it makes the predicate being quantified evaluate to true. By definition of set-builder notation and intersection, it’s enough to prove that \(\{1,2\} \in W\) and that \(1 \in \{1,2\}\) and that \(2 \in \{1,2\}\).

   • By definition of power set, elements of \(W\) are subsets of \(\{1,2,3,4,5\}\). Since each element in \(\{1,2\}\) is an element of \(\{1,2,3,4,5\}\), \(\{1,2\}\) is a subset of \(\{1,2,3,4,5\}\) and hence is an element of \(W\).

   • Also, by definition of the roster method, \(1 \in \{1,2\}\).

   • Similarly, by definition of roster method, \(2 \in \{1,2\}\).

   Thus \(B = \{1,2\}\) is an element of the domain which is in the intersection of the two sets mentioned in the predicate being quantified and is a witness to the existential claim. QED

   ---

   1. (Graded for correctness) Give a witness to the existential claim \[\exists X \in W ~(~X \cup X = \emptyset~)\] Justify your example by explanations that include references to the relevant definitions.

   2. (Graded for correctness) Give a counterexample to the universal claim \[\forall X \in W ~( \{ a \in X \mid a \textrm{ is even} \} \subsetneq X~)\] Justify your example by explanations that include references to the relevant definitions.

   3. (Graded for correctness) Give a witness to the existential claim \[\exists (X,Y) \in W \times W ~(~X \cup Y = Y~)\] Justify your example by explanations that include references to the relevant definitions.

3. Recall our representation of movie preferences in a three-movie database using \(1\) in a component to indicate liking the movie represented by that component, \(-1\) to indicate not liking the movie, and \(0\) to indicate neutral opinion or haven’t seen the movie. We call \(Rt\) the set of all ratings \(3\)-tuples. We defined the function \(d_0: Rt\times Rt \to \mathbb{R}\) which takes an ordered pair of ratings \(3\)-tuples and returns a measure of the distance between them given by \[d_0 (~(~ (x_1, x_2, x_3), (y_1, y_2, y_3) ~) ~) = \sqrt{ (x_1 - y_1)^2 + (x_2 - y_2)^2 + (x_3 -y_3)^2}\] Another measure of the distance between a pair of ratings \(3\)-tuples is given by the following function \(d_1: Rt\times Rt \to \mathbb{R}\) given by \[d_1 (~(~ (x_1, x_2, x_3), (y_1, y_2, y_3) ~) ~) = \sum_{i=1}^3 |x_i - y_i|\]

   1. For each of the statements below, first translate them symbolically (using quantifiers, logical operators, and arithmetic operations), then determine whether each is true or false by applying the proof strategies to prove each statement or its negation. (Graded for correctness of evaluation of statement (is it true or false?) and fair effort completeness of the translation and of the proof)

      1. For all ordered pairs of ratings \(3\)-tuples, the value of the function \(d_0\) is greater than the value of the function \(d_1\).

      2. The maximum value of the function \(d_1\) is greater than the maximum value of the function \(d_0\).

   2. (Graded for correctness) Write a statement about 3-tuples of movie ratings that uses the function \(d_1\) and has at least one universal and one existential quantifier. Your response will be graded correct if all the syntax in your statement is correct.

   3. (Graded for fair effort completeness) Translate the property you wrote symbolically in the last step to English. Indicate if it is true, false, or if you don’t know (sometimes we can write interesting properties, and we’re not sure if they are true or not!). Give informal justification for whether you think it is true/ false, or explain why the proof strategies we have so far do not appear to be sufficient to determine whether the statement holds.