Proof Via the Contrapositive

Return to Course Outline

Previous Lecture

Misc

Exam

The first hour (actually 50 minute) exam is Friday, Feb. 22.

Grading is similar to problem sets (each question graded as all, 3/4, 1/2, etc. of what I expect) but more lenient regarding exceeding expectations.

There is a sample exam (the first exam from last time I taught this course) available on Canvas.

Our exam will cover material from the beginning of the semester through problem set 3 (e.g., mathematical statements, direct proofs, propositional logic, sets, predicates).

Expect 3 to 5 short-answer questions, similar (in my mind at least) to problem set questions.

You’ll have the whole class period to do the test.

Open references (book, notes, online references), but closed person.

Quotation Marks in LaTeX

You can create proper looking left and right quotation marks by using backward single-quotation mark characters for left quotation marks, and regular single-quotation mark characters for right ones.

See an example source file here and the PDF it produces here.

Questions?

Proof by the Contrapositive

Part of section 3.2.

Example

Prove that for all integers n, if n is not divisible by 2, then n is also not divisible by 4.

The contrapositive is “for all integers n, if n is divisible by 4, then n is divisible by 2.” Notice that this is simply replacing the conditional inside the universal quantifier with an equivalent conditional, it doesn’t change the quantifier at all.

Here is LaTeX source for a proof, and the resulting PDF file.

A Conjecture

Motivated by the “integers x satisfying sin x = 1” question on the problem set.

For all integers n ≠ 0, if x is irrational, then nx is also irrational. (The original conjecture was “for all integers n, if x is irrational, then nx is also irrational,” which was discovered to be untrue if n = 0 in the course of constructing a proof. This shows both the value of doing careful proofs, and how mathematicians often find small errors in their conjectures which they can fix to produce a true claim.)

A rational number is one of the from a/b where a, b are integers and b ≠ 0. An irrational number is simply a number that isn’t rational.

The proof is by the contrapositive, i.e., it proves that for all integers n, if nx is rational, then x is also rational.

Here is LaTeX source for the formal proof, and here is the corresponding PDF.

Next

(After exam)

Proofs about biconditionals.

Read the rest of section 3.2

Next Lecture