O'Reilly logo

Good Math by Mark C. Chu-Carroll

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Building a Simple Proof with a Tree

Truth trees work by creating a contradiction. We take a statement that we want to prove true, turn it around by negating it, and then show that that negation leads to contradictions.

For example, I can use this basic method to prove that there isn’t a largest even number, N:

Example: Prove there is no such thing as a largest even number, N.

  1. We’ll start by inverting the fact to prove, and then we’ll show that it leads to a contradiction. Suppose that there is a largest even number, N.

  2. Since N is the largest even number, then for every other even number n, n < N.

  3. N is a natural number; therefore, it can be added with other natural numbers.

  4. If we add 2 to N, the result will be even and it will be larger ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required