Direct Proof

A proof is a program that runs on brains

A theorem is almost always an implication, usually with a hidden $\forall$ out front (you X-rayed those in the last two lessons): "for all integers $n$, if $P(n)$ then $Q(n)$." A direct proof of $P \to Q$ does the obvious-but-disciplined thing: assume $P$, and through a chain of justified steps, arrive at $Q$. That's it. Every step must follow from definitions, earlier steps, or established facts. Nothing smuggled in.

Think of a proof as a program that runs on brains: you write the steps once, and anyone who executes them reaches the same forced conclusion. The hypothesis is your input; the conclusion is your output; the steps are the code. A gap in the proof is a bug, and bugs are not tolerated. I have zero sympathy for bugs. None. The reactor doesn't care about your feelings.

Definitions are the ammunition

You cannot prove a damn thing about "even" until you know exactly what "even" means. Vague notions are useless in a proof — they are worse than useless, they are active saboteurs. Precise definitions are the only ammunition you get. Here are the three you'll fire today, stated with zero wiggle room. Throughout, lowercase letters are integers.

• Even. An integer $n$ is even if $n = 2k$ for some integer $k$.
• Odd. An integer $n$ is odd if $n = 2k + 1$ for some integer $k$.
• Divides. For integers $a, b$ with $a \ne 0$, we say "$a$ divides $b$" (written $a \mid b$) if $b = a m$ for some integer $m$.

Each definition is an existence claim in disguise — "even" means "there exists an integer $k$ with $n = 2k$." So when you assume $n$ is even, you immediately get to name that witness: "since $n$ is even, write $n = 2k$ for some integer $k$." That naming move is the heartbeat of every proof below.

Worked: the sum of two evens is even

Claim. For all integers $m, n$: if $m$ and $n$ are even, then $m + n$ is even.

Proof. Assume $m$ and $n$ are even. By the definition of even, there exist integers $j$ and $k$ with $m = 2j$ and $n = 2k$. Then $m + n = 2j + 2k = 2(j + k),$ where we factored out the $2$ using distributivity (one of the laws of arithmetic — that law is doing real work here, not decoration). Since $j + k$ is an integer, $m + n$ has the form $2 \cdot (\text{integer})$, which is exactly the definition of even. Therefore $m + n$ is even. $\blacksquare$

Watch the shape: assume the hypothesis, unwrap each "even" into its witness, manipulate to expose the target form $2 \cdot (\text{integer})$, then re-wrap by citing the definition. Unwrap, manipulate, re-wrap. Unglamorous as hell, and it proves a shocking amount of mathematics.

Worked: the product of two odds is odd

Claim. For all integers $m, n$: if $m$ and $n$ are odd, then $mn$ is odd.

Proof. Assume $m$ and $n$ are odd. By definition, write $m = 2j + 1$ and $n = 2k + 1$ for integers $j, k$. Then $mn = (2j + 1)(2k + 1) = 4jk + 2j + 2k + 1 = 2(2jk + j + k) + 1,$ where the expansion uses distributivity and the regrouping uses associativity and commutativity — the arithmetic laws, earning their keep again. Set $\ell = 2jk + j + k$, an integer. Then $mn = 2\ell + 1$, which is the definition of odd. Therefore $mn$ is odd. $\blacksquare$

Same rhythm. The only "cleverness" was the algebra to force a "$2 \cdot (\text{integer}) + 1$" shape — and even that wasn't cleverness, it was just following where the definition told you to go. The definition is the compass. Stop trying to be clever and start following the compass.

Worked: divisibility is transitive

Claim. For all integers $a, b, c$ (with $a, b \ne 0$): if $a \mid b$ and $b \mid c$, then $a \mid c$.

Proof. Assume $a \mid b$ and $b \mid c$. By the definition of "divides," there exist integers $s$ and $t$ with $b = a s$ and $c = b t$. Substitute the first into the second: $c = b t = (a s) t = a (s t),$ using associativity of multiplication. Since $s t$ is an integer, $c = a \cdot (\text{integer})$, which is the definition of $a \mid c$. Therefore $a \mid c$. $\blacksquare$

The engine was substitution: $b$ appeared in two facts, so we routed one through the other. Keep an eye out for shared symbols — they're exactly where proofs connect, and ignoring them is how students stare at a problem for an hour accomplishing nothing.

Why an "arbitrary" element proves "for all"

Every claim above was a $\forall$ statement, yet none of them checked infinitely many cases. How is that legal? Because we proved it for a completely arbitrary integer — we named it $n$ (or $m$, $a$, …) and assumed nothing special about it. We never used "$n$ is positive" or "$n = 7$"; we only used "$n$ is an integer satisfying the hypothesis."

So the argument works verbatim no matter which integer you plug in. If it holds for a no-name, assumption-free element, it holds for all of them. That's the universal-proof principle: to prove $\forall x,\ P(x)$, take an arbitrary $x$, assume only that it's in the domain, and prove $P(x)$. Don't pick a specific example — examples prove $\exists$, never $\forall$ (the asymmetry from the quantifiers lesson — you remember, right? Tell me you remember). Pick a generic.

Style rules (break these and I will know)

A proof is writing, not a pile of symbols. The non-negotiables:

1. Write in sentences. "Since $m = 2j$, we have…" — prose with embedded math, not a naked equation dump.
2. Justify every step. "by definition of even," "by distributivity," "by substitution." A step without a reason is a confession.
3. Never start from what you want to prove. Begin at the hypothesis and move toward the conclusion. Assuming the conclusion and shuffling it around is the most common way to fake a proof — and it proves nothing. Start at $P$, end at $Q$.
4. Mark the end. $\blacksquare$ or "QED" — tell the reader the program has halted.

Now go. You have the definitions, you have the rhythm, you have the laws of arithmetic underneath you like a solid floor. Stop reading and do the damn gauntlet.