Clearly and unambiguously communicate computational ideas using appropriate formalism. Translate across levels of abstraction.
Translating between symbolic and English versions of statements using precise mathematical language
Using appropriate signpost words to improve readability of proofs, including ’arbitrary’ and ’assume’
Know, select and apply appropriate computing knowledge and problem-solving techniques. Reason about computation and systems. Use mathematical techniques to solve problems. Determine appropriate conceptual tools to apply to new situations. Know when tools do not apply and try different approaches. Critically analyze and evaluate candidate solutions.
Judging logical equivalence of compound propositions using symbolic manipulation with known equivalences, including DeMorgan’s Law
Writing the converse, contrapositive, and inverse of a given conditional statement
Determining what evidence is required to establish that a quantified statement is true or false
Evaluating quantified statements about finite and infinite domains
Apply proof strategies, including direct proofs and proofs by contradiction, and determine whether a proposed argument is valid or not.
Identifying the proof strategies used in a given proof
Identifying which proof strategies are applicable to prove a given compound proposition based on its logical structure
Carrying out a given proof strategy to prove a given statement
Carrying out a universal generalization argument to prove that a universal statement is true
Using proofs as knowledge discovery tools to decide whether a statement is true or false
Project due this week: May 8, 2024.
Review quiz based on class material each day (due Friday May 10, 2024).
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\):
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)\)
Prove or disprove: \(\forall A \in W\, \forall B \in W\, \left( \mathcal{P}(A) =\mathcal{P}(B) ~\to ~ A = B \right)\)
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)\)
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.
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 when \(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 definitions: The set of RNA strands \(S\) is defined (recursively) by: \[\begin{array}{ll} \textrm{Basis Step: } & \texttt{A}\in S, \texttt{C}\in S, \texttt{U}\in S, \texttt{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 rnalen that computes the length of RNA strands in \(S\) is defined recursively by: \[\begin{array}{llll} & & \textit{rnalen} : S & \to \mathbb{Z}^+ \\ \textrm{Basis Step:} & \textrm{If } b \in B\textrm{ then } & \textit{rnalen}(b) & = 1 \\ \textrm{Recursive Step:} & \textrm{If } s \in S\textrm{ and }b \in B\textrm{, then } & \textit{rnalen}(sb) & = 1 + \textit{rnalen}(s) \end{array}\]
The function basecount that computes the number of a given base \(b\) appearing in a RNA strand \(s\) is defined recursively by: \[\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}\]
At this point, we’ve seen the proof strategies
2
A counterexample to prove that \(\forall x P(x)\) is false.
A witness 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
Proof by universal generalization to prove that \(\forall x \, P(x)\) is true using an arbitrary element of 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.
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
Proof of conditional by contrapositive proof
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.
Which proof strategies could be used to prove each of the following statements?
Hint: first translate the statements to English and identify the main logical structure.
\(\forall s \in S~(~rnalen(s) > 0~)\)
\(\forall b \in B~\exists s \in S~(~basecount(~(s,b)~)~ > 0~)\)
\(\forall s \in S ~\exists b\in B ~(~basecount(~(s,b)~) > 0~)\)
\(\exists s \in S \, (\textit{rnalen(s)} = \textit{basecount}(~(s, \texttt{A})~)\)
\(\forall s \in S \, (\textit{rnalen(s)} \geq \textit{basecount}(~(s, \texttt{A})~))\)
Claim \(\forall s \in S ~(~rnalen(s) > 0~)\)
Proof: Let \(s\) be an arbitrary RNA strand. By the recursive definition of \(S\), either \(s \in B\) or there is some strand \(s_0\) and some base \(b\) such that \(s = s_0 b\). We will show that the inequality holds for both cases.
\(\phantom{Basis}\) Case: Assume \(s \in B\). We need to show \(rnalen(s) > 0\). By the basis step in the definition of \(rnalen\), \[rnalen(s) = 1\] which is greater than \(0\), as required.
\(\phantom{Recursive}\) Case: Assume there is some strand \(s_0\) and some base \(b\) such that \(s = s_0 b\). We will show (the stronger claim) that \[\forall u \in S ~\forall b \in B ~( ~\textit{rnalen}(u) >0 \to \textit{rnalen}(ub) >0 ~)\] Consider an arbitrary RNA strand \(u\) and an arbitrary base \(b\), and assume towards a direct proof,\(~~{\phantom{ this is the induction hypothesis}}~~\) that \[rnalen(u) > 0\] We need to show that \(rnalen(ub) > 0\). \[rnalen(ub) = 1 + rnalen (u) > 1 + 0 = 1 > 0\] as required.
Claim \(\forall s \in S \, (\textit{rnalen(s)} \geq \textit{basecount}(~(s, \texttt{A})~))\):
Proof: We proceed by structural induction on the recursively defined set \(S\).
Basis Case: We need to prove that the inequality holds for each element in the basis step of the recursive definition of \(S\). Need to show \[\begin{aligned} &(~ rnalen(\texttt{A}) \geq basecount(~(\texttt{A}, \texttt{A})~)~) \land (~ rnalen(\texttt{C}) \geq basecount(~(\texttt{C}, \texttt{A})~)~) \\ \land & (~ rnalen(\texttt{U}) \geq basecount(~(\texttt{U}, \texttt{A})~)~) \land (~ rnalen(\texttt{G}) \geq basecount(~(\texttt{G}, \texttt{A})~)~) \end{aligned}\] We calculate, using the definitions of \(rnalen\) and \(basecount\):
Recursive Case: We will prove that \[\forall u \in S ~\forall b \in B ~( ~rnalen(u) \geq basecount(~(u, \texttt{A})~) \to rnalen(ub) \geq basecount(~(ub, \texttt{A})~)\]
Consider arbitrary RNA strand \(u\) and arbitrary base \(b\). Assume, as the induction hypothesis, that \(rnalen(u) \geq basecount(~(u,\texttt{A})~)\). We need to show that \(rnalen(ub) \geq basecount(~(ub, \texttt{A})~)\).
Using the recursive step in the definition of the function \(rnalen\): \[rnalen(ub) = 1 + rnalen(u)\] The recursive step in the definition of the function \(basecount\) has two cases. We notice that \(b = \texttt{A}\lor b \neq \texttt{A}\) and we proceed by cases.
Case i. Assume \(b = \texttt{A}\).
Using the first case in the recursive step in the definition of the function \(basecount\): \[basecount(~(ub, \texttt{A})~) = 1 + basecount(~(u,\texttt{A})~)\] By the induction hypothesis, we know that \(basecount(~(u,\texttt{A})~) \leq rnalen(u)\) so: \[basecount(~(ub, \texttt{A})~) = 1 + basecount(~(u,\texttt{A})~) \leq 1 + rnalen(u) = rnalen (ub)\] and, thus, \(basecount(~(ub,\texttt{A})~) \leq rnalen(ub)\), as required.
Case ii. Assume \(b \neq \texttt{A}\).
Using the second case in the recursive step in the definition of the function \(basecount\): \[basecount(~(ub, \texttt{A})~) = basecount(~(u,\texttt{A})~)\] By the induction hypothesis, we know that \(basecount(~(u,\texttt{A})~) \leq rnalen(u)\) so: \[basecount(~(ub, \texttt{A})~) = basecount(~(u,\texttt{A})~) \leq rnalen(u) < 1 + rnalen(u) = rnalen (ub)\] and, thus, \(basecount(~(ub,\texttt{A})~) \leq rnalen(ub)\), as required.
To organize our proofs, it’s useful to highlight which claims are most important for our overall goals. We use some terminology to describe different roles statements can have.
Theorem: Statement that can be shown to be true, usually an important one.
Less important theorems can be called proposition, fact, result, claim.
Lemma: A less important theorem that is useful in proving a theorem.
Corollary: A theorem that can be proved directly after another one has been proved, without needing a lot of extra work.
Invariant: A theorem that describes a property that is true about an algorithm or system no matter what inputs are used.
Theorem: A robot on an infinite 2-dimensional integer grid starts at \((0,0)\) and at each step moves to diagonally adjacent grid point. This robot can / cannot (circle one) reach \((1,0)\).
Definition The set of positions the robot can visit \(Pos\) is defined by: \[\begin{array}{ll} \textrm{Basis Step: } & (0,0) \in Pos \\ \textrm{Recursive Step: } & \textrm{If } (x,y) \in Pos \textrm{, then } \\ &\phantom{(x+1, y+1), (x+1, y-1), (x-1, y-1), (x-1, y+1)} \textrm{ are also in } Pos \end{array}\]
Example elements of \(Pos\) are:
Lemma: \(\forall (x,y) \in Pos~~( x+y \textrm{ is an even integer}~)\)
Why are we calling this a lemma?
Proof of theorem using lemma: To show is \((1,0) \notin Pos\). Rewriting the lemma to explicitly restrict the domain of the universal, we have \(\forall (x,y) ~(~ (x,y) \in Pos~~ \to ~~(x+y \textrm{ is an even integer})~)\). Since the universal is true, \((~ (1,0) \in Pos~~ \to ~~(1+0 \textrm{ is an even integer})~)\) is a true statement. Evaluating the conclusion of this conditional statement: By definition of long division, since \(1 = 0 \cdot 2 + 1\) (where \(0 \in \mathbb{Z}\) and \(1 \in \mathbb{Z}\) and \(0 \leq 1 < 2\) mean that \(0\) is the quotient and \(1\) is the remainder), \(1 ~\textrm{\bf mod}~ 2 = 1\) which is not \(0\) so the conclusion is false. A true conditional with a false conclusion must have a false hypothesis: \((1,0) \notin Pos\), QED. \(\square\)
Proof of lemma by structural induction:
Basis Step:
Recursive Step: Consider arbitrary \((x,y) \in Pos\). To show is: \[(x+y \text{ is an even integer}) \to (\text{sum of coordinates of next position is even integer})\] Assume as the induction hypothesis, IH that:
The set \(\mathbb{N}\) is recursively defined. Therefore, the function \(sumPow: \mathbb{N} \to \mathbb{N}\) which computes, for input \(i\), the sum of the nonnegative powers of \(2\) up to and including exponent \(i\) is defined recursively by
\[\begin{aligned} {2} \text{Basis step: } \qquad & sumPow(0) = 1 &\\ \text{Recursive step: } & \text{If } x \in \mathbb{N} \text{, then } &sumPow(x+1) = sumPow(x) + 2^{x+1} \end{aligned}\]
\(sumPow(0) =\)
\(sumPow(1) =\)
\(sumPow(2) =\)
Fill in the blanks in the following proof of \[\forall n \in \mathbb{N}~(sumPow(n) = 2^{n+1} - 1)\]
Proof: Since \(\mathbb{N}\) is recursively defined, we proceed by .
Basis case: We need to show that . Evaluating each side: \(LHS = sumPow(0) = 1\) by the basis case in the recursive definition of \(sumPow\); \(RHS = 2^{0+1} - 1 = 2^1 - 1 = 2-1 = 1\). Since \(1=1\), the equality holds.
Recursive case: Consider arbitrary natural number \(n\) and assume, as the that \(sumPow(n) = 2^{n+1} - 1\). We need to show that . Evaluating each side: \[LHS = sumPow(n+1) \overset{\text{rec def}}{=} sumPow(n) + 2^{n+1}\overset{\text{IH}}{=} (2^{n+1} - 1) + 2^{n+1}.\] \[RHS = 2^{(n+1)+1}- 1 \overset{\text{exponent rules}}{=} 2 \cdot 2^{n+1} -1 = \left(2^{n+1} + 2^{n+1} \right) - 1 \overset{\text{regrouping}}{=} (2^{n+1} - 1) + 2^{n+1}\] Thus, \(LHS = RHS\). The structural induction is complete and we have proved the universal generalization. \(\square\)
Set properties
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)\)
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)\)
Number properties
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)~)~)\)
Structural induction
Recall the definitions of the functions \(rnalen\) and \(basecount\) from class.
Select all and only options that give a witness for the existential quantification \[\exists s \in S ~(~rnalen(s) = basecount(~(s,\texttt{U})~)~)\]
\(\texttt{A}\)
\(\texttt{U}\texttt{U}\)
\(\texttt{C}\texttt{U}\)
\((\texttt{U}, 1)\)
None of the above.
Select all and only options that give a counterexample for the universal quantification \[\forall s \in S ~(~rnalen(s) > basecount(~(s,\texttt{G})~)~)\]
\(\texttt{U}\)
\(\texttt{G}\texttt{G}\)
\(\texttt{A}\texttt{G}\)
\(\texttt{C}\texttt{U}\texttt{G}\)
None of the above.
Select all and only the true statements
\(\forall s \in S ~\exists b \in B ~\left(~rnalen(s) = basecount(~(s,b)~)~ \right)\)
\(\exists s \in S ~\forall b \in B ~\left(~rnalen(s) = basecount(~(s,b)~)~ \right)\)
\[\begin{aligned} \forall s_1 \in S~\forall s_2 \in S ~&\forall b \in B ~\big( ~\big( rnalen(s_1) = basecount(~(s_1,b)~) \\ &\land rnalen(s_2) = basecount(~(s_2,b)~) \land rnalen(s_1) = rnalen(s_2) \big) \to s_1 = s_2 \big) \end{aligned}\]
None of the above.
Recall the set \(Pos\) defined by the recursive definition \[\begin{array}{ll} \textrm{Basis Step: } & (0,0) \in Pos\\ \textrm{Recursive Step: } & \textrm{If } (x,y) \in Pos \textrm{ then } (x+1, y+1) \in Pos \textrm{ and } (x+1, y-1) \in Pos \textrm{ and }\\ & (x-1,y-1) \in Pos \textrm{ and } (x-1, y+1) \in Pos \end{array}\]
Select all and only the ordered pairs below that are elements of \(Pos\)
\((0,0)\)
\((4,0)\)
\((1,1)\)
\((1.5,2.5)\)
\((0, -2)\)
What is another description of the set \(Pos\) ? (Select all and only the true descriptions.)
\(\mathbb{Z} \times \mathbb{Z}\)
\(\{ (n,n) ~|~ n \in \mathbb{Z} \}\)
\(\{ (a,b) \in \mathbb{Z} \times \mathbb{Z} ~|~ (a+b) \textbf{ mod } 2 =0 \}\)
Mathematical induction
Select all and only the true statements below about the relationship between structural induction and mathematical induction.
Both structural induction and mathematical induction are proof strategies that may be useful when proving universal claims about recursively defined sets.
Mathematical induction is a special case of structural induction, for the case when the domain of quantification is \(\{ n \in \mathbb{Z} \mid n \geq b\}\) for some integer \(b\).
Universal claims about the set of all integers may be proved using structural induction but not using mathematical induction.
Consider the following function definitions \[2^n: \mathbb{N} \to \mathbb{N} \text{ given by } 2^0 = 1 ~~\text{ and }~~ 2^{n+1} = 2 \cdot 2^n\] \[n!: \mathbb{N} \to \mathbb{N} \text{ given by } 0! = 1 ~~\text{ and }~~ (n+1)! = (n+1) n!\]
Select all and only true statements below:
\(2^0 < 0!\)
\(2^1 < 1!\)
\(2^2 < 2!\)
\(2^3 < 3!\)
\(2^4 < 4!\)
\(2^5 < 5!\)
\(2^6 < 6!\)
\(2^7 < 7!\)
Fill in the blanks in the following proof.
Claim: For all integers \(n\) greater than or equal to \(4\), \(2^n <
n!\)
Proof: We proceed by mathematical
induction on the set of integers greater than or equal to \(4\).
Basis step: Using the BLANK 1,
\[2^4 = 2 \cdot 2^3 = 2 \cdot 2 \cdot 2^2 = 2
\cdot 2 \cdot 2 \cdot 2^1 =
2 \cdot 2 \cdot 2 \cdot 2 \cdot 2^0 =
2 \cdot 2 \cdot 2 \cdot 2 \cdot 1 = 16\] and \[4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2!
= 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0!
= 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24\] Since \(16 < 24\), we have proved that \(2^4 < 4!\) , as required.
Recursive step: Consider an arbitrary
integer \(k\) that is greater than or
equal to \(4\) and assume as the
BLANK 2, that \(2^k < k!\) .
We want to show that \(2^{k+1} <
(k+1)!\) . \[\begin{aligned}
2^{k+1} &= 2 \cdot 2^{k} \qquad \text{by
}\underline{\hspace{0.2in}BLANK 3\hspace{0.2in}}\\
&< 2 \cdot k! \qquad \text{by
}\underline{\hspace{0.2in}BLANK 4\hspace{0.2in}}\\
&< k \cdot k! \qquad \text{by
}\underline{\hspace{0.2in}BLANK 5\hspace{0.2in}}\\
&< (k+1) \cdot k! \qquad \text{by
}\underline{\hspace{0.2in}BLANK 6\hspace{0.2in}}\\
&= (k+1)! \qquad \text{by }\underline{\hspace{0.2in}BLANK
7\hspace{0.2in}}\\
\end{aligned}\] as required.
properties of addition, multiplication, and \(<\) for real numbers
definitions of the functions \(2^n\) and \(n!\)
definition of \(k\)
induction hypothesis
Midquarter feedback