COMP 61: Discrete Math
Lecture 6: Week 4, Tuesday, February 4
- Covered: Proof by contrapositive, proof by contradiction
- Class notes (see full notes if you want to practice step-by-step; otherwise see condensed)
- Textbook sources
- Scheinerman: chapter 4, section 20.
- Rosen (Discrete Mathematics and its Applications, 2nd ed.), chapter 3. Example 15 is about sqrt(2) being irrational. Example 21 is about infinite number of primes (similar to what was done in class, but not quite the same).
- Links
- Book of Proof, chapter 5, by Richard Hammack. See 5.1 in particular, for proof by contrapositive. It contains some of the examples I used. See 5.3 for tips on how to write well.
- Book of Proof, chapter 6. It has a proof for root(2) being irrational, and for infinite number of primes (by inspection it seems identical to what I showed in class).
- The "principle of explosion", by xkcd 704
- Infinite number of primes, by xkcd 622
- Be rational...
- Further comments
- Irrational vs complex (vs transcendental, etc) ... Complex numbers have two components, the real and the imaginary. The field of complex numbers contains the field of real numbers, which contains rational and irrational numbers. So, any rational or irrational number is actually a complex number with no imaginary component. But there are complex numbers that are neither rational nor rational, although the real component of such a complex number can be rational or irrational.
Real transcendental numbers are irrational, but they are even more special in some sense, because they are not the root of any polynomial. For instance pi is one such number, but sqrt(2) is not.
