Direct Proof

Direct proof is not a niche technique confined to introductory logic courses — it is the connective tissue of essentially every branch of mathematics. In real analysis, epsilon-delta arguments proving continuity or convergence ("assume $\varepsilon > 0$ is given, choose $\delta$ accordingly, derive $|f(x)-f(a)|<\varepsilon$") are direct proofs of a universally quantified implication. In linear algebra, proving that a linear map is injective from "assume $T(v)=0$" to "derive $v=0$" is a direct proof. In number theory, the divisibility and modular-arithmetic arguments of Example 2 are the daily bread of the subject, underlying results from Fermat's Little Theorem to the RSA correctness proof in cryptography, where one directly derives $c^d \equiv m \pmod n$ from the hypotheses on the keys $e,d,n$. In computer science, direct proof underlies correctness proofs of algorithms via loop invariants: assume the invariant holds before an iteration (hypothesis), execute the loop body, and derive that it holds after (conclusion) — precisely the direct-proof skeleton, iterated. In statistics and probability, deriving that an estimator is unbiased ("assume the model; compute $\mathbb{E}[\hat\theta]$; show it equals $\theta$") is a direct proof. In physics and engineering, deriving a conserved quantity from stated symmetry assumptions (as in Noether's theorem applications) is structurally the same: assume the hypotheses of the symmetry, compute forward, and land on the conserved quantity. Wherever a result is phrased as "if [conditions], then [conclusion]" and the natural strategy is to unpack the conditions and compute or reason forward, direct proof is the tool being used — even when authors no longer name it explicitly.

Ask the tutor: Can you show me how to convert a messy scratch-work "backward" derivation into a clean forward-facing direct proof?

Think of $P \Rightarrow Q$ as a bridge you must show can be crossed: not that it necessarily will be crossed (we never assert $P$ is true, unconditionally), but that if you stand on the $P$-side, there is a walkable path to the $Q$-side. A direct proof is that walkable path, laid down plank by plank. Each plank ($S_i$) must be nailed to the ones before it — either because it is already known ground (an axiom, definition, prior theorem) or because it is a logically forced consequence of planks already laid. This is different from merely believing $Q$ is true, or checking it in a few cases. The chain has to work for every situation in which $P$ holds — including one you haven't thought to check — because at no point did the argument use any feature of a particular instance beyond what $P$ itself guarantees. That is the discipline enforced by keeping $x_0$ "arbitrary": if the proof secretly used, say, that $x_0 = 4$, then it has not proved the universal statement at all, only a single instance of it. Picture the conditional as a labeled arrow in a directed graph of truth: $P$ points to $Q$ only if every route from the "$P$ true" region lands inside the "$Q$ true" region. Direct proof is the act of tracing one such route explicitly, using only sanctioned moves.

This is exactly the content of the Deduction Theorem specialized to a single hypothesis, together with the semantic soundness of the underlying inference rules. It is the metatheorem that certifies "assume $P$, derive $Q$, conclude $P \Rightarrow Q$" as a legitimate proof strategy rather than a rhetorical shortcut.

This proof technique used here is mathematical induction on proof length, applied at the metatheoretic level to justify a proof strategy — not to be confused with the object-level statements $S_i$ themselves, which may or may not involve induction. The argument is non-circular: the Deduction Theorem is proved purely from the semantics of $\Rightarrow$ and axioms $A_1, A_2$, never assuming in advance that "assume-and-derive" is valid — that conclusion is exactly what gets extracted at the end.

Example 1 — an algebraic implication with mixed parity. Claim. For all integers $m$ and $n$, if $m$ is even and $n$ is odd, then $3m^2 + 5n$ is odd. Proof. Let $m, n$ be arbitrary integers, and assume $m$ is even and $n$ is odd. (This is the hypothesis $P$.) By definition of even, there exists an integer $a$ such that $m = 2a$. By definition of odd, there exists an integer $b$ such that $n = 2b+1$. Compute:

Rewrite:

Let $k = 6a^2 + 5b + 2$. Since $a, b$ are integers, $k$ is an integer (integers are closed under the operations of multiplication and addition, and $6a^2, 5b, 2$ are each integers). Thus

with $k \in \mathbb{Z}$, which by definition means $3m^2+5n$ is odd. This is exactly $Q$. Since $m, n$ were arbitrary integers satisfying the hypothesis, the implication holds for all such $m,n$. $\blacksquare$ Note the structural anatomy: $S_1$ is "$m$ even and $n$ odd"; the definitions of even/odd supply $S_2, S_3$ (existence of $a,b$); algebraic simplification (a chain of equalities, each justified by ring axioms) supplies $S_4,\dots,S_7$; the final rewriting into the form $2k+1$ is the crucial creative step, and it lands exactly on the definition of odd, giving $S_n = Q$.

Example 2 — a divisibility implication with an explicit witness construction. Claim. For all integers $x$, if $x \equiv 4 \pmod 7$, then $x^2 + 3x \equiv 6 \pmod 7$. Here $\equiv \pmod 7$ means: $a \equiv b \pmod 7$ if and only if $7 \mid (a-b)$, i.e. there exists an integer $t$ with $a - b = 7t$. Proof. Let $x$ be an arbitrary integer, and assume $x \equiv 4 \pmod 7$. By definition, there is an integer $t$ with

We must show $x^2 + 3x \equiv 6 \pmod 7$, i.e. that $7 \mid \big((x^2+3x) - 6\big)$. Substitute $x = 4+7t$:

Expand:

Sum:

Subtract $6$:

Wait — check divisibility by $7$ directly on each term: $49t^2 = 7(7t^2)$, $77t = 7(11t)$, and $22 = 7\cdot 3 + 1$, so $22$ is not divisible by 7. This signals an arithmetic slip — let's recompute $16+12$: that is $28$, correct, and $28 - 6 = 22$. So in fact

which is not a multiple of $7$ in general (its constant term $22 \equiv 1 \pmod 7$). This means the original claim as stated is false — a valuable check, since $x\equiv 4\pmod 7$ gives $x^2+3x \equiv 16+12 = 28 \equiv 0 \pmod 7$, not $6$. Let us correct the claim to match the true computation and redo the proof honestly, since a direct proof must track arithmetic exactly. Corrected claim. For all integers $x$, if $x \equiv 4 \pmod 7$, then $x^2 + 3x \equiv 0 \pmod 7$. Proof. Let $x$ be an arbitrary integer with $x \equiv 4 \pmod 7$, so $x = 4+7t$ for some integer $t$, as above. Then, from the expansion just derived,

Let $k = 7t^2+11t+4 \in \mathbb{Z}$. Then $x^2+3x = 7k$, so $7 \mid (x^2+3x - 0)$, i.e. $x^2+3x \equiv 0 \pmod 7$. Since $x$ was an arbitrary integer satisfying the hypothesis, this holds for all such $x$. $\blacksquare$ (This detour is left visible deliberately: it demonstrates that a direct proof is only as good as its arithmetic, and that the method — substitute the witness, expand, factor out the modulus — is exactly what to do once the correct target congruence is identified.)