Section 3.4  Arguments with Quantified Statements

• Be familiar with the concept of universal instantiation: If a property is true for every element of a set S, then it is true for a particular element s of S. See pages 146- 147 of the text and class notes.

• Be familiar the argument form Universal Modus Ponens:   ∀x , P (x) → Q (x) P (a) for some a ∴ Q (a)

Review Examples 3.4. 1, 3.4.2 and the proof example on pages 148- 149 of the text.

• Be familiar the argument form Universal Modus Tollens:   ∀x , P (x) → Q (x)

~  Q (a) for some a

∴ ~ P (a)

Review Examples 3.4.3, 3.4.4.

• Know the meaning of the terms valid argument and sound argument. See page 150 of the text.

• Be familiar with the use of diagrams to test for validity and invalidity of arguments. Review Examples 3.4.5, 3.4.6 and example 3.4.7.

• Be familiar with the invalid converse and invalid  inverse argument forms:

∀x , P (x) → Q (x)                                 ∀x , P (x) → Q (x)

Q (a) for some a                                                 ~ P (a) for some a

∴ P (a) Invalid (converse error)                      ∴ ~ Q (a) Invalid (inverse error)

• Be familiar how to use Venn diagrams to check the validity of an argument. Review Examples 3.4.5 -3.4.7, WebAssign HW.

• Be familiar with the Universal Transitivity argument form:   ∀x , P (x) → Q (x)

∀x , Q (x) → R(x)

∴ ∀x , P (x) → R(x)

See page 154 of the text and review Example 3.4.8.

Section 4.1     Direct Proof and Counterexample: Introduction

• Be familiar with the assumptions used in elementary proof including the use of basic algebra, the three properties of equals (reflexive, symmetric, transitive), the use of substitution, and the fact that there is no integer strictly        between 0 and 1, and that the set of integers is closed under addition, subtraction and multiplication.

• Know the formal definitions of even and odd integers, and the definitions of a prime integer and composite integer (see pages 162- 163 of the text). Review Examples 4.1.1 and 4.1.2.

• Be familiar with how to prove an existential statement by finding an example that makes conclusion true. Review Example 4.1.3.

• Be familiar with how to disprove a universal statement by finding a counterexample which makes the conclusion false. Review Example 4.1.4.

• Be familiar with how to use the Method of Exhaustion to prove a universal statement true when the quantified variable’s domain is afinite set. Review Example 4.1.5 and Worksheet 3

• Be familiar who to use the method of Generalizingfrom the Generic Particular to prove a universal statement true when the quantified variable’s an infinite set. Review the “Math Trick,” pages 166- 167.

• Be familiar with  how the Method of Direct Proof  to prove statements of the form ∀x ∈ D, P (x) → Q (x) by    supposing that P (x) is true for a particular but arbitrary chosen element x of D. This means that x should satisfy no extra conditions beyond the facts that x ∈ D and P (x) are assumed. Also, be familiar with principle of         Existential Instantiation which allows an object whose existence is assumed or has been deduced to given a      name. Review Example 4.1.7 and Theorem 4. 1. 1: The some of two even integers is even.

Section 4.1     Direct Proof and Counterexample: Introduction (continued)

• Know that a proof starting point includes a statement of what is assumed and that the end of a proof should include a statement of the “conclusion to be shown.” Review Examples 4.1.8 and Example 4.1.9.

Section 4.2     Direct Proof and Counterexamples II: Writing Advise 

•  Review the eight points of the Directionsfor Writing Proofs of Universal Statements and the seven Common Mistakes. In particular,

(1) know that giving list of examples is not the same as proving a proof,

(2) the invalid use of the same variable name to mean two different things, and

(3) incorrectly assuming the truth of that what is to be proved to prove

“that that what is to be proved” (a form of circular reasoning/jumping to the conclusion).

•  Review Examples 4.2.1 and Theorem 4.2. 1: The difference of any odd integer and any even integer is odd.

•  Review Example 4.2.3 of how to disprove an existential statement.

Section 4.3  Direct Proof and Counterexamples III: Rational  Numbers 

•  Know the definition of a rational number (see page 183 of the text) and review Example 4.3.1. In particular, be   familiar with how to prove that a real number with a repeating digits after the decimal point is a rational number. For example, 10.123123123 … = 10113/999, so it is a rational number.

•  Be aware of the Zero Product Property of two real numbers: ∀x ∈ R, ∀y ∈ R, xy = 0 → (x = 0) ∨ (y = 0).

•  Know why every integer is a rational number (see Theorem 4.3. 1) and review Example 4.3.2 and the Theorem 4.3.2: The sum of any two rational numbers is rational.

•  Be able to prove properties about the sum, product, difference of even and odd integers such as  the product of two odd integers is odd. Review Examples 4.3.3 and 4.3.4.

Section 4.7  Indirect Argument: Contradiction and Contraposition

•  Recall that Proof by Contradiction of the universal statement ∀x ∈ D, P (x) is proof form where

one proves ∀x ∈ D, ~ P (x) → c , and more generally where one proves ∀x ∈ D, P (x) → Q (x) by proving ∀x ∈ D, P (x) ^ ( ~ Q (x)) → P (x) ^ ( ~ P (x)) 三 ∀x ∈ D, P (x) ^ ( ~ Q (x)) → c

•  Be familiar how the Method of Proof by Contradiction is used to prove

Theorem 4.7. 1: There is no greatest integer, Theorem 4.7.2: There is no integer that is both even and odd, x and Theorem 4.7.2 The sum of any rational number and any irrational number is irrational.

•  Be familiar with the Method of Proof by Contraposition which is used to prove Proposition 4.7.4: For every integer n, if n2 is even, the n is even.

•  Recall that the contrapositive of the universal statement ∀x ∈ D, P (x) → Q (x) is the logically equivalent statement ∀x ∈ D, ( ~ Q (x)) → ( ~ P (x)).

•  Be aware that a Proof by Contraposition ∀x ∈ D, ( ~ Q (x)) → ( ~ P (x)) into a Proof By  Contradiction by

changing the proof’s supposition from “Suppose there exists an arbitrary element x ∈ D such       that ~ Q (x)”  to  “Suppose there exists an arbitrary element x ∈ D such that P (x) and  ~ Q (x)” . See page 223 of the text.

Section 4.8 Indirect Argument: Two Famous Theorems 

•  Be familiar with the proof that    2 is irrational (see Theorem 4,8,1)  which is based on the fact that a rational   number r can be expressed as r =  where m , n ∈ Z have no factors in common; that is, r =  is a reduced fraction.