Proof by Contradiction

6 Key excerpts on "Proof by Contradiction"

• 

  eBook - ePub

  Philosophy of Mathematics

  Classic and Contemporary Studies

  • Ahmet Cevik(Author)
  • 2021(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Proving a theorem formally can be very tedious. Mathematicians do not prove theorems in the formal manner as formal proofs are in most cases used by computer programmes or formal axiomatic systems for verification and automation purposes. Fortunately, we do not need to worry about formal proofs in this book. 2.2.1 Direct proof A direct proof is a way of proving any statement of the form p → q, using the rules of inference, starting from the assumption p to arrive at the conclusion q. We give the following example. Proposition 2.1 For any integers m and n, if m and n are odd, then m + n is even. Proof. If m and n are odd numbers, then for some integers a and b, we have that m = 2 a + 1 and n = 2 b + 1. Therefore, m + n = (2 a + 1) + (2 b + 1) = 2 a + 2 b + 2 = 2 (a + b + 1). Since m + n is two times the number a + b + 1, we conclude that m + n is an even number. □ 2.2.2 Proof by contrapositive Another way of proving a statement of the type p → q is by proving its contrapositive form. It can be easily shown using the truth table method that p → q is logically equivalent to ¬ q → ¬ p. So proving the contrapositive form is same as proving the original statement. Proposition 2.2 If n 2 is odd, then so is n. Proof. The contrapositive form of the given statement can be wrtten as “If n is even, then so is n 2”. We shall prove the contrapositive form. If n is even, then for some k, n = 2 k. Then, n 2 = (2 k) 2 = 4 k 2 = 2 (2 k 2). Therefore, since n 2 is two times the number 2 k 2, n 2 must be even. □ 2.2.3 Proof by Contradiction In logic and mathematics, Proof by Contradiction is a powerful method to establish the truth or falsity of a statement. Suppose we want to prove a proposition p. To prove p by contradiction, we first assume that ¬ p holds. Then we derive a contradiction and conclude that our assumption ¬ p must be false, meaning that it cannot be the case that ¬ p. That is, ¬ (¬ p) must hold. In classical logic, ¬ (¬ p) is logically equivalent to p

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  The Elements of Advanced Mathematics

  • Steven G. Krantz(Author)
  • 2022(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  A cannot both be true. An assumption that leads to this eventuality cannot be valid. That is the essence of Proof by Contradiction.

  Historically, Theorem 2.5.1 was extremely important. Prior to Pythagoras (∼300 B.C.E.), the ancient Greeks (following Eudoxus) believed that all numbers (at least all numbers that arise in real life) are rational. However, by the Pythagorean theorem, the length of the diagonal of a unit square is a number whose square is 2. And our theorem asserts that such a number cannot be rational. We now know that there are many nonrational, or irrational, numbers. In fact, in Section 4.5 , we shall learn that, in a certain sense to be made precise, “most” numbers are irrational.

  Here is a second example of a Proof by Contradiction:

  Theorem 2.5.3 (Dirichlet) Suppose that

  n + 1

  pieces of mail are delivered to n mailboxes. Then some mailbox contains at least two pieces of mail.

  Proof: Seeking a contradiction, we suppose that the assertion is false. Then each mailbox contains either zero or one piece of mail. But then the total amount of mail in all the mailboxes cannot exceed

  1 + 1 + ⋯ + 1

  ︸

  n   times

  .

  In other words, there are at most n pieces of mail. That conclusion contradicts the fact that there are

  n + 1

  pieces of mail. We conclude that some mailbox contains at least two pieces of mail. □

  The last theorem, due to Gustav Lejeune Dirichlet (1805–1859), was classically known as the Dirichletscher Schubfachschluss. This German name translates to “Dirichlet's drawer shutting principle.” Today, at least in this country, it is more commonly known as “the pigeonhole principle.” Since pigeonholes are no longer a common artifact of everyday life, we have illustrated the idea using mailboxes.

  EXAMPLE 2.5.4 Draw the unit interval I

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Transition to Analysis with Proof

  • Steven Krantz(Author)
  • 2017(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  ’ ) . That is a contradiction. I

  POINT OF CONFUSION 2.23 People do not usually reason by “Proof by Contradiction” in ordinary, everyday discourse. It is too subtle for those purposes. The speaker could not easily follow the logic, and neither could the listener.

  But Proof by Contradiction is a powerful tool. Alan Turing used the method to crack the German enigma code during World War II. Proof by Contradiction is particularly helpful in establishing existence results, but it can be used for many other purposes as well.

  A Look Back

  1. What are the characteristics of a Proof by Contradiction?
  2. How does a Proof by Contradiction differ from a direct proof?
  3. Why is the method of Proof by Contradiction valid?
  4. Prove by contradiction that the sum of two even numbers is even.

  Exercises

  1. Prove that, if n red letters and n blue letters are distributed among n mailboxes, then either some mailbox contains at least two red letters or some mailbox contains at least two blue letters or else some mailbox contains at least one red and one blue letter.
  2. Prove that, if m is a power of 3 and n is a power of 3, then m  + n is never a power of 3.
  3. What is special about the number 3 in Exercise 2? What other natural numbers can be used in its place?
  4. Imitate the proof of Pythagoras’s theorem to show that the number 5 does not have a rational square root.
  5. Prove that, if n is a natural number and if n has a rational square root, then in fact the square root of n is an integer.
  6. Complete this sketch to obtain an alternative proof that the number 2 does not have a rational square root:

  • Take it for granted that it is known that each positive integer has one and only one factorization into prime factors (a prime number is a positive integer, greater than 1, that can be divided evenly only by 1 and itself).

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  How to Solve Mathematical Problems

  • Wayne A. Wickelgren(Author)
  • 2012(Publication Date)
  • Dover Publications

    (Publisher)

  The method of indirect proof in mathematics is an extremely important example of the problem-solving method of contradiction. To prove that a statement follows from certain givens, the method of indirect proof is to assume the contrary is true and show that the contrary statement, in combination with the givens, results in a contradiction. Therefore, since the contrary statement is false, the original statement must be true. You will note that, in this case, for the method of indirect proof to be valid there must be only two possible alternatives: either the goal statement is true (can be derived from the givens) or it is false (the contradiction of the statement can be derived from the givens, but the original statement cannot). For the method of contradiction to be valid, the statement must be either true or false. The truth value of the statement cannot be undecidable. In addition, the set of given statements must themselves be free of internal contradiction; otherwise, contradictions could be derived from a possible goal in combination with the givens, not because of a contradiction between the goal and the givens, but because of a contradiction within the givens. However, the beginning student need not be very concerned with these limitations on the use of the method of contradiction. By and large, whenever it appears reasonable to use the method of contradiction, it is valid to use it.

  There are, of course, innumerable examples of the use of indirect proof in every area of mathematics. Here is one example:

  Given that you have already proved the theorem that all squares of nonzero integers are positive, prove that equation x 2 + 1 = 0 has no integer solution.

  Stop reading and attempt to prove the theorem, using the method of contradiction (indirect proof).

  The first step in applying the method of contradiction to this problem is to assume the contradiction of the theorem — namely, that x has an integer solution, x = c , where c is an integer. If you have so far not solved the problem, stop reading and try again.

  Given that x 2 + 1 = 0, subtract 1 from both sides of the equation to get x 2 = —1. Now substitute c for x , getting c 2

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Discrete Mathematics with Ducks

  • sarah-marie belcastro(Author)
  • 2018(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  that aloud three times...) You may astutely notice that this is actually proving the contrapositive. In this case, we might start by drafting a Proof by Contradiction, continue by discovering that we’ve proven the contrapositive, and write the clean version of the proof as a contrapositive proof.

  More commonly when using Proof by Contradiction, the P in

  P ⇒ Q

  is a compound statement containing several conditions (e.g.,

  if k is an integer,

  ℓ

  is even, and the moon is green

  ), and we will only contradict one part of P rather than proving the negation of P as a whole (e.g., showing that the moon is not green and thus deriving a contradiction).

  Less common but still useful is assuming Q is false and deriving a contradiction unrelated to the statements under consideration—for example, showing that Q is false implies that 2 is an odd number.

  Template for a Proof by Contradiction:

  1. Restate the theorem in the form if (conditions) are true, then (conclusion) is true .
  2. On a scratch sheet, write suppose not . Then write out (conditions) and the negation of (conclusion).
  3. Try to simplify the statement of
     ¬
     (conclusion) and see what this might mean.
  4. Attempt to derive a contradiction of some kind—to one or more of (conditions) or to a commonly known mathematical truth.
  5. Repeat attempts until you are successful.
  6. Write up the results on a clean sheet, as follows.
     • Theorem: (State theorem here.)
     • Proof: Suppose not. That is, suppose (conditions) are true but (conclusion) is false.
     • (Translate this to a simpler statement if applicable. Derive a contradiction.)
     • Contradiction!
     • Therefore, (conclusion) is true. (Draw a box or checkmark or write Q.E.D. to indicate that you’re done.)

  Example 1.29 We will prove that there are infinitely many powers of 2, i.e.,

  2 0

  ,

  2 1

  ,

  2 2

  , ⋯

  . Suppose not. Then there are finitely many powers of 2; let the number of them be n . Therefore, we can sort them in increasing order of size. Consider the largest of these, k . Then

  2 k

  is not one of the n powers of 2; it is larger than any of them because

  2 k

  > k

  . Therefore, there are at least

  n + 1

  powers of 2, which contradicts the supposition that there were only n

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Basic Discrete Mathematics

  Logic, Set Theory, and Probability

  • Richard Kohar(Author)
  • 2016(Publication Date)
  • WSPC

    (Publisher)

  1 better by gaining more insight. The moment that a mathematician suspects that it can be easily done with a computer, they will walk away to look for another problem. Not that there is no challenge, but doing work for the sake of work does not yield any insight and hence, it provides no challenge to treat a computer like a calculator on steroids. Therefore, mathematicians are not concentrated solely on calculations, but on why these calculations work. In the figurative sense of a pencil, mathematical proofs are more about communication, and not so much about the truth. Communicating can employ a computer, but as a means of presentation—in a journal, blog, or forum—for comment by others or as a processor to construct a lecture presentation to share as if it was a big piece of paper.

  In this book, you will encounter both kinds of proofs, formal and mathematical. We will begin by looking at formal proofs in this chapter.

  2.2 Rules of Inference

  In previous courses, you have seen the laws of arithmetic; see Table 2.2 .2 These same concepts from arithmetic can be applied to propositions yielding the rules of inference. The rules of inference in logic provides a systematic way of showing propositions are equivalent to each other.

  2.2.1 Fundamental Logical Equivalences

  The fundamental logical equivalences are listed below. They can all be formally justified using truth tables. Table 2.1 Correspondences between arithmetic and logic. Table 2.2 Laws of Arithmetic

  Let p, q, and r be any three propositions (prime or compound), and be a tautology and be a contradiction:

  2.2.2 Logical Equivalences for Implication and Biconditional

  Let p, q, and r be any three propositions (prime or compound):

  Example 2.2.1 — Illustrating the Use of the Implication Rule.

  Apply the Implication Rule (2.24) to the statement

  (p ∧ q) → q.

  Solution

  Notice at the beginning of the rules that we stated p, q, and r could be compound propositions. In fact, p ∧ q is simply a compound proposition which we can denote by r.

  Example 2.2.2

  Prove that ¬(p → q) ⇔ p ∧ ¬q.

  Solution

  By truth table:

  Since the fourth and sixth columns are the same, by the definition of logical equivalence we can conclude ¬(p → q) ⇔ p ∧ ¬q.

  By the rules of inference:

  The application of the rules of inference in the order shown above may not necessarily be the only valid sequence. You will find that as you prove logical equivalences that there is more than one option at various points. The only way to find out if this option will lead you down the right path is to try it. This will likely involve a generous amount of scrap paper; mathematics is not known for being environmentally friendly. Here is an alternative proof for the above example.

  Sign up to read

  Learn more about book