We now have propositional and predicate logic that can help us express statements about any domain. We will develop proof strategies to craft valid argument for proving that such statements are true or disproving them (by showing they are false). We will practice these strategies with statements about sets and numbers, both because they are familiar and because they can be used to build cryptographic systems. Then we will apply proof strategies more broadly to prove statements about data structures and machine learning applications.
When a predicate \(P(x)\) is over a finite domain:
To show that \(\forall x P(x)\) is true: check that \(P(x)\) evaluates to \(T\) at each domain element by evaluating over and over.
To show that \(\forall x P(x)\) is false: find one counterexample, a domain element where \(P(x)\) evaluates to \(F\).
To show that \(\exists x P(x)\) is true: find one witness, a domain element where \(P(x)\) evaluates to \(T\).
To show that \(\exists x P(x)\) is false: check that \(P(x)\) evaluates to \(F\) at each domain element by evaluating over and over.
Definitions:
A set is an unordered collection of elements. When \(A\) and \(B\) are sets, \(A = B\) (set equality) means \[\forall x ( x\in A \leftrightarrow x \in B)\]
When \(A\) and \(B\) are sets, \(A \subseteq B\) (“\(A\) is a subset of \(B\)") means \[\forall x (x \in A \to x \in B)\]
When \(A\) and \(B\) are sets, \(A \subsetneq B\) (“\(A\) is a proper subset of \(B\)") means \[(A\subseteq B) \wedge (A \neq B)\]
To prove that one set is a subset of another, e.g. to show \(A \subseteq B\):
To prove that two sets are equal, e.g. to show \(A = B\):
Example: \(\{ 43, 7, 9 \} = \{ 7, 43, 9, 7\}\)
Prove or disprove: \(\{ \texttt{A}, \texttt{C}, \texttt{U}, \texttt{G}\} \subseteq \{ \texttt{A}\texttt{A}, \texttt{A}\texttt{C}, \texttt{A}\texttt{U}, \texttt{A}\texttt{G}\}\)
Prove or disprove: For some set \(B\), \(\emptyset \in B\).
Prove or disprove: For every set \(B\), \(\emptyset \in B\).
Prove or disprove: The empty set is a subset of every set.
Prove or disprove: The empty set is a proper subset of every set.
Prove or disprove: \(\{ 4, 6 \} \subseteq \{ n \mid \exists c \in \mathbb{Z} ( n = 4c) \}\)
Prove or disprove: \(\{ 4, 6 \} \subseteq \{ n ~\textbf{mod}~10 \mid \exists c \in \mathbb{Z} ( n = 4c) \}\)
Suppose \(P(x)\) is a predicate over a domain \(D\).
True or False: To translate the statement “There are at least two elements in \(D\) where the predicate \(P\) evaluates to true", we could write \[\exists x_1 \in D \, \exists x_2 \in D \, (P(x_1) \wedge P(x_2))\]
True or False: To translate the statement “There are at most two elements in \(D\) where the predicate \(P\) evaluates to true", we could write \[\forall x_1 \in D \, \forall x_2 \in D \, \forall x_3 \in D \, \left(~ (~P(x_1) \wedge P(x_2) \wedge P(x_3) ~) \to (~ x_1 = x_2 \vee x_2 = x_3 \vee x_1 = x_3~)~\right)\]
For each of the following English statements, select the correct translation, or select None.
Challenge: determine which of the statements are true and which are false.
Every set is a subset of itself.
Every set is an element of itself.
Some set is an element of all sets.
Some set is a subset of all sets.
\(\forall X ~\exists Y ~(X \in Y)\)
\(\exists X ~\forall Y ~(X \in Y)\)
\(\forall X ~\exists Y ~(X \subseteq Y)\)
\(\exists X ~\forall Y ~(X \subseteq Y)\)
\(\forall X ~(X \in X)\)
\(\forall X ~(X \subseteq X)\)
We want to hear how the term and this class are going for you. Please complete the midquarter feedback form: https://forms.gle/w3D7ifAWnD5sWwHf9
Cartesian product: When \(A\) and \(B\) are sets, \[A \times B = \{ (a,b) \mid a \in A \wedge b \in B \}\]
Example: \(\{43, 9\} \times \{9, \mathbb{Z}\} =\)
Example: \(\mathbb{Z} \times \emptyset =\)
Union: When \(A\) and \(B\) are sets, \[A \cup B = \{ x \mid x \in A \vee x \in B \}\]
Example: \(\{43, 9\} \cup \{9, \mathbb{Z}\} =\)
Example: \(\mathbb{Z} \cup \emptyset =\)
Intersection: When \(A\) and \(B\) are sets, \[A \cap B = \{ x \mid x \in A \wedge x \in B \}\] Example: \(\{43, 9\} \cap \{9,\mathbb{Z}\} =\)
Example: \(\mathbb{Z} \cap \emptyset =\)
Set difference: When \(A\) and \(B\) are sets,
\[A - B = \{ x \mid x \in A \wedge x \notin B \}\]
Example: \(\{43, 9\} - \{9, \mathbb{Z}\} =\)
Example: \(\mathbb{Z} - \emptyset =\)
Disjoint sets: sets \(A\) and \(B\) are disjoint means \(A \cap B = \emptyset\)
Example: \(\{43, 9\}, \{9, \mathbb{Z}\}\) are not disjoint
Example: The sets \(\mathbb{Z}\) and \(\emptyset\) are disjoint
Power set: When \(U\) is a set, \(\mathcal{P}(U) = \{ X \mid X \subseteq U\}\)
Example: \(\mathcal{P}(\{43, 9\}) =\)
Example: \(\mathcal{P}(\emptyset) =\)
Let \(W = \mathcal{P}( \{ 1,2,3,4,5\} )\)
Example elements in \(W\) are:
Prove or disprove: \(\forall A \in W\, \forall B \in W\, \left( A \subseteq B ~\to ~ \mathcal{P}(A) \subseteq \mathcal{P}(B) \right)\)
Extra example: Prove or disprove: \(\forall A \in W\, \forall B \in W\, \left( \mathcal{P}(A) =\mathcal{P}(B) ~\to ~ A = B \right)\)
Extra example: Prove or disprove: \(\forall A \in W\, \forall B \in W\, \forall C \in W\, \left( A\cup B = A \cup C ~\to ~ B = C \right)\)
Let \(W = \mathcal{P}(\{1,2,3,4,5\})\). The statement \[\forall A \in W~ \forall B\in W~ \forall C \in W~ ( A \cup B = A \cup C ~\to~ B = C)\] is false. Which of the following choices for \(A, B, C\) could be used to give a counterexample to this claim? (Select all and only that apply.)
\(A = \{ 1, 2, 3 \}, B = \{ 1, 2\}, C= \{1, 3\}\)
\(A = \{ 1, 2, 3 \}, B = \{ 2\}, C= \{2\}\)
\(A = \{ \emptyset, 1, 2, 3 \}, B = \{ 1, 2\}, C= \{1, 3\}\)
\(A = \{ 1, 2, 3 \}, B = \{ 1, 2\}, C= \{1, 4\}\)
\(A = \{ 1, 2 \}, B = \{ 2, 3\}, C= \{1, 3\}\)
\(A = \{ 1,2 \}, B = \{ 1,3\}, C = \{ 1,3\}\)
Let \(W = \mathcal{P}(\{1,2,3,4,5\})\). Consider the statement \[\forall A \in W~ \forall B\in W~ \big( ( \mathcal{P}(A) = \mathcal{P}(B) )~\to~ (A = B) \big)\]
This statement is true. A proof of this statement starts with universal generalization, c onsidering arbitrary \(A\) and \(B\) in \(W\). At this point, it remains to prove that \(( \mathcal{P}(A) = \mathcal{P}(B) )~\to~ (A = B)\) is true about these arbitrary elements. There are two ways to proceed:
First approach: By direct proof, in which we assume the hypothesis of the conditional and work to show that the conclusion follows.
Second approach: By proving the contrapositive version of the conditional instead, in which we assume the negation of the conclusion and work to show that the negation of hypothesis follows.
First approach, assumption.
First approach, “need to show".
Second approach, assumption.
Second approach, “need to show".
Pick an option from below for the assumption and “need to show" in each approach.
2
\(\forall X ( X \subseteq A \leftrightarrow X \subseteq B)\)
\(\exists X ( X \subseteq A \leftrightarrow X \subseteq B)\)
\(\forall X ( X \subseteq A \oplus X \subseteq B)\)
\(\exists X ( X \subseteq A \oplus X \subseteq B)\)
\(\forall x ( x \in A \leftrightarrow x \in B)\)
\(\exists x ( x \in A \leftrightarrow x \in B)\)
\(\forall x ( x \in A \oplus x \in B)\)
\(\exists x ( x \in A \oplus x \in B)\)
Addition and multiplication of real numbers are each commutative and associative.
The product of two positive numbers is positive, of two negative numbers is positive, and of a positive and a negative number is negative.
The sum of two integers, the product of two integers, and the difference between two integers are each integers.
For every integer \(x\) there is no integer strictly between \(x\) and \(x+1\),
When \(x, y\) are positive integers, \(xy \geq x\) and \(xy \geq y\).
Definition: When \(a\) and \(b\) are integers and \(a\) is nonzero, \(a\) divides \(b\) means there is an integer \(c\) such that \(b = ac\) .
Symbolically, \(F(~(a,b)~) = \phantom{\exists c\in \mathbb{Z}~(b=ac)}\) and is a predicate over the domain
Other (synonymous) ways to say that \(F(~(a,b)~)\) is true:
\(a\) is a factor of \(b\) \(a\) is a divisor of \(b\) \(b\) is a multiple of \(a\) \(a | b\)
When \(a\) is a positive integer and \(b\) is any integer, \(a | b\) exactly when \(b \textbf{ mod } a = 0\)
When \(a\) is a positive integer and \(b\) is any integer, \(a | b\) exactly \(b = a \cdot (b \textbf{ div } a)\)
Translate these quantified statements by matching to English statement on right.
2 \(\exists a\in \mathbb{Z}^{\neq 0} ~(~F(~(a,a)~)~)\)
\(\exists a\in \mathbb{Z}^{\neq 0} ~(~\lnot F(~(a,a)~)~)\)
\(\forall a\in \mathbb{Z}^{\neq 0} ~(~F(~(a,a)~)~)\)
\(\forall a\in \mathbb{Z}^{\neq 0} ~(~\lnot F(~(a,a)~)~)\)
Every nonzero integer is a factor of itself.
No nonzero integer is a factor of itself.
At least one nonzero integer is a factor of itself.
Some nonzero integer is not a factor of itself.
Claim: Every nonzero integer is a factor of itself.
Proof:
Prove or Disprove: There is a nonzero integer that does not divide its square.
Prove or Disprove: Every positive factor of a positive integer is less than or equal to it.
Claim: Every nonzero integer is a factor of itself and every nonzero integer divides its square.
Definition: an integer \(n\) is even means that there is an integer \(a\) such that \(n = 2a\); an integer \(n\) is odd means that there is an integer \(a\) such that \(n = 2a+1\). Equivalently, an integer \(n\) is even means \(n ~\textbf{ mod }~2 = 0\); an integer \(n\) is odd means \(n ~\textbf{ mod }~2 = 1\). Also, an integer is even if and only if it is not odd.
Definition: An integer \(p\) greater than \(1\) is called prime means the only positive factors of \(p\) are \(1\) and \(p\). A positive integer that is greater than \(1\) and is not prime is called composite.
Extra examples: Use the definition to prove that \(1\) is not prime, \(2\) is prime, \(3\) is prime, \(4\) is not prime, \(5\) is prime, \(6\) is not prime, and \(7\) is prime.
True or False: The statement “There are three consecutive positive integers that are prime."
Hint: These numbers would be of the form \(p, p+1, p+2\) (where \(p\) is a positive integer).
Proof: We need to show
True or False: The statement “There are three consecutive odd positive integers that are prime."
Hint: These numbers would be of the form \(p, p+2, p+4\) (where \(p\) is an odd positive integer).
Proof: We need to show
Recall the predicate \(F(~(a,b)~) = ``a \text{ is a factor of } b"\) over the domain \(\mathbb{Z}^{\neq 0} \times \mathbb{Z}\) we worked with in class. Consider the following quantified statements
2
\(\forall x \in \mathbb{Z} ~(F(~(1,x)~))\)
\(\forall x \in \mathbb{Z}^{\neq 0} ~(F(~(x,1)~))\)
\(\exists x \in \mathbb{Z} ~(F(~(1,x)~))\)
\(\exists x \in \mathbb{Z}^{\neq 0} ~(F(~(x,1)~))\)
\(\forall x \in \mathbb{Z}^{\neq 0} ~\exists y \in \mathbb{Z} ~(F(~(x,y)~))\)
\(\exists x \in \mathbb{Z}^{\neq 0} ~\forall y \in \mathbb{Z} ~(F(~(x,y)~))\)
\(\forall y \in \mathbb{Z} ~\exists x \in \mathbb{Z}^{\neq 0} ~(F(~(x,y)~))\)
\(\exists y \in \mathbb{Z} ~\forall x \in \mathbb{Z}^{\neq 0} ~(F(~(x,y)~))\)
Select the statement whose translation is
“The number \(1\) is a factor of every integer."
or write NONE if none of (i)-(viii) work.
Select the statement whose translation is
“Every integer has at least one nonzero factor."
or write NONE if none of (i)-(viii) work.
Select the statement whose translation is
“There is an integer of which all nonzero integers are a factor."
or write NONE if none of (i)-(viii) work.
For each statement (i)-(viii), determine if it is true or false.
Which of the following formalizes the definition of the predicate \(Pr(x)\) over the set of integers, and evaluates to \(T\) exactly when \(x\) is prime. (Select all and only correct options.)
\(\forall a \in \mathbb{Z}^{\neq 0}~( ~(x > 1 \land a >0) \to F(~(a,x)~))\)
\(\lnot \exists a \in \mathbb{Z}^{\neq 0} ~(x > 1 \land (a=1 \lor a=x) \land F(~(a,x)~))\)
\((x > 1) \land \forall a \in \mathbb{Z}^{\neq 0}~( ~(~ a>0 \land F(~(a,x)~)~) \to (a=1 \lor a=x)~)\)
\((x > 1) \land \forall a \in \mathbb{Z}^{\neq 0}~( ~(~ a>1 \land \lnot (a=x) ~) \to \lnot F(~(a,x)~)~)\)