Introduction to Proof

Return to Course Outline

Previous Lecture

Questions?

Problem set question 1: the reasons can be truth tables or English explanations, maybe even briefer than truth tables.

Direct Proofs

Section 1.2

Example

Prove that if x is an even integer and y is an integer, then xy is an even integer.

Intuition

x = 2n

So xy = 2ny which is a multiple of 2 and so even.

Formally

Theorem: if x is an even integer and y is an integer, then xy is an even integer.

Proof: Assuming that x is an even integer and y is an integer, we will prove that xy is an even integer. By definition an even integer x can be written as x = 2n for some integer n. Using this definition and regrouping we see...

xy = (2n)y

= 2(ny)

Since the integers are closed under multiplication, ny is an integer, call it p, yielding

xy = 2p

Since there exists an integer p such that xy = 2p, xy is an even integer. We have therefore shown that if x is an even integer and y is an integer, then xy is an even integer. QED

Take-Aways

Proof is a 2-stage process: intuition then formality.

A formal proof is a logically rigorous exposition of why some claim is true. “Logically rigorous” means that each step in the argument follows via accepted mathematical rules from previous ones or the initial assumptions. “Exposition” means that the proof is indeed meant for people, and so is a grammatical, clear, and otherwise well-written presentation of the argument.

Next

Writing proofs with LaTeX.

No reading.

Bring a computer able to run LaTeX if you want to “play along” with my examples.

Next Lecture