3.1: Direct Proofs and Indirect Proofs
Read the opening discussion, "Proofs," Section 1, "The Axiomatic Method," and Sections 2 - 6, inclusive. In Unit 3, you will get a chance to apply a lot of what you have thought about and mastered in Units 1 and 2. Our domain of discourse is number theory, in particular proofs in elementary number theory.
Consider the following comparison of direct and indirect proofs. A direct proof is an argument that shows that the conclusion logically follows from the premises or assumptions by applying rules of inference in a sequence of steps.
Sections 1, 2, 4, and 5 deal with direct proofs. Section 2, "Proving an Implication," refers to statement such as P implies Q, and proving that Q is a consequence of P. In a logic system, P logically follows from the axioms and valid statements of the logic system, is another way of saying that P is a consequence of the axioms and valid statements or P is implied by them. This is what is meant by proving an implication.
Section 3 is related to indirect proof. Section 6 discusses indirect proof, also known as proof by contradiction, directly. An indirect proof, in contrast, is a proof in which the theorem to be proved is assumed false, and from this assumption, it is shown that a contradiction follows. Because the logic system is consistent, i.e. there are no contradictions, the theorem must be true. (Two statements are contradictions when they cannot both be true, and they cannot both be false.)
Read example 1 through example 4 on pages SF-3 to SF-6. It discusses proofs for sets.
3.1.1: Odd and Even Numbers
Read Section 1 through example 1 on pages NT-1 and NT-2. There are several commonly used sets of numbers that will be introduced to you; the first is the set of odd and even integers, i.e. the set of integers.
3.1.2: Prime Numbers
Read Section 1 beginning at "Prime Numbers and Factorization" on page NT-3, and continue up to example 3 on page NT-4. Example 3 also applies to 3.1.4 and 3.2.2 below. Prime numbers are the next set of commonly used numbers to be introduced. The introduction of prime numbers leads to the discussion of factoring an integer.
3.1.3: Proving and Disproving Universal Statements
3.1.3.1: Proof by Using the Method of Exhaustion
Reread example 2 on page NT-2, with special attention to the proof method, called proof by induction (an exhaustive proof method). This reading discusses a universal statement, which is just a statement that involves universal quantification.
A statement may be provable by evaluating it or by manipulating the symbols using definitions, rules, and theorems to transform the statement to an equivalent statement. Use of truth tables to evaluate a statement is an example of the former. This is also an example of the Method of Exhaustion. If a Universal statement has a finite set for its bound variable (a variable that is quantified is bound and the set of values that it can take is its range or domain), then it can be proven by proving it for each value in the range of the bound variable. If the set is countable, a proof by induction may be applicable. Induction is studied in Unit 4 of this course. Equivalently, the Universal statement can be proved by showing that it is true for an arbitrary value.
3.1.3.2: Disproof by Counterexample
Read over the Exercises for Section 1 on pages NT-10 - NT-13. Note the use of counterexamples. A universally quantified statement may be false. It can be proven false by showing that there exists an instance of the universally bound variable for which the statement is false. The instance is called a counter example. Exercises often have useful information, also applicable outside of the exercise.
3.1.4: Proving and Disproving an Existential Statement
Read example 5 on pages NT-5 and NT-6. An existential statement can be proved directly by specifying the instance of the existentially bound variable that makes the statement true. To disprove an existential statement, transform its negation to an equivalent universal statement, by using the property where the negation of an existential quantifier becomes a universal quantifier, (negating there exists an x such that P(x) becomes for all x not P(x)). Then, prove the universal statement.