Lecture · 15 min · advanced

Logic and proof

Implication, quantifiers, and a clean argument

The grammar of mathematical argument

A proof is not a sequence of true statements. It is a sequence of inferences. “ $P$ , therefore $Q$ ” is licensed only when $P \Rightarrow Q$ has already been established, or is an axiom, or is a previously proved theorem. The rest is rhetoric.

On the board today

—Translate “if $P$ then $Q$ ” and its contrapositive.
—Negate quantified statements carefully.
—Distinguish $\forall$ and $\exists$ in definitions (e.g. continuity vs. a bound).

Contrapositive

(P \Rightarrow Q) \equiv (\neg Q \Rightarrow \neg P)

Logically equivalent. The converse $Q \Rightarrow P$ is a different claim.

To disprove $\forall x P (x)$ , a single counterexample suffices. To prove it, you must handle a generic $x$ , not an example. Negating $\forall x \exists y P (x, y)$ produces $\exists x \forall y \neg P (x, y)$ — the quantifiers flip, and the inner statement is negated. This is how “not continuous” is written with $ε$ - $δ$ .

Worked example · Direct vs contrapositive

Prove: if $n^{2}$ is even, then $n$ is even.

1.Contrapositive: if $n$ is odd, then $n^{2}$ is odd.
2.Write $n = 2 k + 1$ . Then $n^{2} = 4 k (k + 1) + 1$ , which is odd.

The contrapositive is easier because “odd” has a clean algebraic form.

Pause the lecture

Is the converse of “if $n$ is divisible by $4$ , then $n$ is even” true?

Common mistake. Proving a universal claim with an example, or disproving an existential claim with an example that fails. Existence is proved by exhibiting one; universality is disproved by exhibiting one.

Practice this lecture

Previous Next