CSC165H1, Winter 2022 CSC165H1: Worksheet 4—Proofs I (Partial Solutions)
Learning Objectives
By the end of this worksheet, you will:
• Write formal proofs of simple statements and statements with alternating quantifiers.
Copyright By PowCoder代写 加微信 powcoder
• Compare the structure of a mathematical statement with the structure of its corresponding proof. • Write disproofs of statements in predicate logic by first converting the statement to its negation.
1. Two practice proofs. You have now seen some simple proofs, and are ready to start writing your own! In this first part, you’ll prove two statements: an existentially-quantified statement, and a universally-quantified statement.
Rather than jump right to the proof, we’re going to break the process down for you here, to make sure you have all the right terminology and concepts in place for a solid foundation.
(a) Consider the statement “there exists a natural number n that is greater than 3 and satisfies the inequality n2 − 1.5n ≥ 5.”
First, translate this statement into predicate logic. Do not define your own set; in other words, make sure to quantify over N.
(b) Your statement should have one variable. Is it existentially or universally quantified?
(c) In your proof, your first line should be to introduce the variable. When you introduce it, are you going to make the variable’s value a concrete natural number or an arbitrary natural number?
(d) Write your proof of this statement in the space below. Clearly separate your proof header, where you introduce variables and any assumptions, from your proof body, where you write the content of your proof using variables and assumptions from the proof header.
∃n∈N, n>3∧n2 −1.5n≥5.
Existentially quantified.
A concrete natural number.
Proof. Let n = 20. (This is a concrete natural number.)
Then n > 3, and n2 − 1.5n = 202 − 1.5 · 20 = 370, which is greater than 5.
CSC165H1, Winter 2022 CSC165H1: Worksheet 4—Proofs I (Partial Solutions)
(e) Now, consider the statement “Every natural number n greater than 3 satisfies the inequality n2 − 1.5n > 4.” First, translate this statement into predicate logic. Do not define your own set; in other words, make sure to quantify over N. (Should you use ∧ or ⇒ here? Why?)
(f) Your statement should have one variable. Is it existentially or universally quantified?
(g) In your proof, your first line should be to introduce the variable. When you introduce it, are you going to make the variable’s value a concrete natural number or an arbitrary natural number?
(h) Are there any assumptions that you’ll make in your proof? How can you tell based on the structure of the statement?
(i) Write your proof of this statement in the space below. Clearly separate your proof header, where you introduce variables and any assumptions, from your proof body, where you write the content of your proof using variables and assumptions from the proof header.
Warning: we strongly recommend using some scrap paper to do a calculation first, before writing your proof. Please note that all calculations in a proof must be written in the correct top-down direction, meaning the inequality you’re trying to prove should be the last line of your proof.
∀n∈N, n>3⇒n2 −1.5n>4.
Universally quantified.
An arbitrary natural number.
We’ll assume n > 3; this is the hypothesis of the implication in the statement.
Let n ∈ N, and assume n > 3.
We start with our assumption n > 3:
n>3 n − 1.5 > 1.5 n2 − 1.5n > 4.5
n2 − 1.5n > 4
(Multiplying by the inequality n > 3) (since 4.5 > 4)
The trickiest step is the second-last one, in which we multiplied the left side by n and the right side by 3. This is an illustration of one nice manipulation of inequalities: if a > b > 0 and c > d > 0, then ac > bd (i.e., you can multiply corresponding sides of an inequality).
2. Disproofs. Now that you have seen and written your first few proofs, let’s talk about a slight variation of what we’ve done so far: disproving statements.
When we encounter a statement that we think is False, of course we shouldn’t try to prove the statement. Instead, we want to write a disproof of the statement: an argument convincing someone that the statement is actually False. The most common type of disproof is a proof of the negation of the statement; if the negation of the statement is True, then the original statement must be False!
Let’s work through an example of this idea, by considering the following (False) statement:
Every natural number greater than 5 is divisible by 2 or is divisible by 3.
(a) Translate the above statement into predicate logic. You can use the divisibility predicate x | y.
CSC165H1, Winter 2022 CSC165H1: Worksheet 4—Proofs I (Partial Solutions)
∀n∈N, n>5⇒2|n∨3|n.
(b) This statement is False, so we won’t try to prove it—instead, we’ll prove its negation. In the space below, find the negation of the above statement, using negation simplification rules to push negations all the way inside (so that they apply directly to predicates). Note that the negation of x | y is x ∤ y.
¬(∀n∈N, n>5⇒2|n∨3|n) ∃n∈N, ¬(n>5⇒2|n∨3|n) ∃n∈N, n>5∧¬(2|n∨3|n) ∃n∈N, n>5∧2∤n∧3∤n
(c) Finally, prove the negated statement from part (b). This will prove that the original statement is False.
Proof. Let n = 7.
Then n > 5, and 2 does not divide n, and 3 does not divide n.
[Note: because 2 and 7 are concrete numbers, you can say that “2 does not divide 7” without any further
explanation. This is because it is a simple calculation to show that 27 is not an integer.]
3. Alternating quantifiers revisited. We saw last week that statements with alternating quantifiers are trickier to work with because the order in which the variables appear matters: ∀x ∈ S,∃y ∈ T, means something different than ∃y ∈ T,∀x ∈ S, .
In this question, you’ll learn about how to write proofs of statements involving alternating quantifiers, and gain a deeper appreciation of how the structure of a statement informs the structure of a proof of that statement.
(a) First, consider the following statement:
∀x∈R, ∃y∈R, x+y>165.
Notice that the y is existentially quantified, and appears after the x. This means that our choice of y can depend on the value of x.
Complete the following proof by filling in the missing parts: the two blanks in the proof header, and the body of the proof. (The body of the proof should be quite short; the main thinking we want you to do is in the header, to make sure you understand how the quantifiers and order affects things!)
Proof. Letx . Lety .
CSC165H1, Winter 2022 CSC165H1: Worksheet 4—Proofs I (Partial Solutions)
Proof. Let x ∈ R (or, let x be an arbitrary real number). Let y = 166 − x. The value of y depends on x. Wewanttoprovethatx+y>165.
Wecalculate: x+y=x+(166−x)=166,andsox+y>165.
(b) Now consider the following statement (notice that we’ve also changed the domain of x and y from R to N to ensure that the statement is True).
∃y∈N, ∀x∈N, x+y>165.
Here, because y in introduced first in the formula, it must appear first in the proof; it cannot depend on the
value of x. Keeping this in mind, complete the following proof of this statement. Proof. Lety . Letx .
(c) Finally, using everything you’ve learned on this worksheet, disprove the following statement:1 ∃y∈R, ∀x∈R, x+y>165.
Proof. Let y = 166. (The value of y is independent of x.) Let x ∈ N.
Thenx+y=x+166. Sincethesmallestnaturalnumberis0,x≥0,andsox+166≥166>165.
First, we have to compute the negation. We omit the steps here (good practice for you). ∀y∈R, ∃x∈R, x+y≤165.
Proof. Lety∈R. Letx=−y.
Then x + y = y − y = 0, and so x + y ≤ 165.
1The fact that this statement is False, while the exact same one with variables chosen from N is True, is quite interesting. Essen- tially, when we restrict the domain of x to be just the naturals, we have fewer numbers to worry about—fewer opportunities for a counterexample for a chosen y.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com