Logic

Proof Techniques

Sherlock Holmes said: 'When you have eliminated the impossible, whatever remains is the truth.' Mathematicians went further. They built an arsenal of techniques, each its own way to uncover truth. Case analysis, induction, construction. Which tool to choose?

**Case analysis in law:** legal arguments systematically run through every scenario. If the defendant is guilty, evidence X, Y, Z must appear; if innocent, an alibi
**Induction in programming:** proofs of correctness for recursive algorithms (sorting, tree traversal) use structural induction
**Constructive proofs in cryptography:** security proofs often require explicit construction of an attack or a simulator. 'An attacker exists' is uninformative

Proof by cases

**Proof by cases** (case analysis) is a technique where we split the domain into exhaustive cases and prove the statement for each separately. It is like a legal defense covering every possible scenario: 'If my client was home, he is innocent. If he was in town, there is an alibi for every moment'.

**Logical foundation:** if P ∨ Q (the cases are exhaustive) and we have proved (P → R) and (Q → R), then R follows in any case. This is the ∨-elimination rule: from 'A or B', 'A entails C', and 'B entails C', conclude C.

**Without loss of generality (WLOG):** sometimes cases are symmetric. You can say 'without loss of generality, let x ≤ y'. This cuts the work in half because the case y ≤ x is proved by swapping variables.

Proving that n² + n is always even for integer n, which case split is correct and optimal?

Mathematical induction

**Mathematical induction** proves statements of the form 'for all natural n, P(n)'. The idea is simple: if the first domino falls and each falling domino topples the next, all of them fall. But in math 'all' really means infinity.

**The induction principle:** to prove ∀n ∈ ℕ. P(n), it suffices to show: 1) **Base:** P(0) or P(1). The first element has the property. 2) **Step:** ∀k. P(k) → P(k+1). If the property holds for k, it holds for k+1.

**Strong induction:** sometimes proving P(k+1) needs not just P(k) but P(k-1), P(k-2), and so on. Strong induction lets you assume P(j) for all j < k+1. Example: proving that every n > 1 factors into primes.

**Structural induction:** a generalization to recursively defined structures (trees, lists, formulas). The base is the primitive elements; the step is the composite constructions. If a property holds on the leaves of a tree and is preserved when subtrees combine, it holds for the whole tree.

In the inductive proof of 1² + 2² + ... + n² = n(n+1)(2n+1)/6, the step from k to k+1 uses what?

Constructive proofs

**A constructive proof** does not just claim that an object exists. It shows how to build it. The difference is between 'somewhere in the city there is a restaurant' and 'here is the address: 15 Pushkin Street'. In programming this means providing not just types, but working code.

**Curry-Howard correspondence:** a constructive proof of ∃x.P(x) is a pair (witness, proof), where the witness is a concrete object x₀ and the proof shows P(x₀). A proof of A → B is a function that turns a proof of A into a proof of B.

**Constructivism in programming:** in languages with dependent types (Coq, Agda, Idris), a proof of existence is code that computes the object. You cannot just say 'either p or ¬p'. You must write an algorithm that decides which.

**Law of excluded middle:** classical logic takes P ∨ ¬P as an axiom. Constructive logic demands an algorithm to choose. This does not make constructivism weaker. It is stricter. Many theorems hold in both logics, but constructive proofs are more informative.

Proof: 'There exists a prime greater than 1000. Consider 1000! + 1. If it is prime, done. If composite, its smallest prime divisor is > 1000.' Is this constructive?

Existence proofs

**An existence proof** (∃x.P(x)) claims that an object with a given property exists. There are three main approaches: **constructive** (name the object), **counting** (count and show > 0), and **by contradiction** (assume absence, derive a contradiction).

**Erdős' probabilistic method:** if a random object has property P with nonzero probability, then an object with P exists. This is non-constructive (it does not point to a concrete object), but extremely powerful in combinatorics.

**Non-constructiveness from contradiction:** Euclid's proof of infinitely many primes is non-constructive. It shows finiteness leads to a contradiction, but it does not build an infinite sequence of primes. For each N we know 'a prime > N exists', but not which one without factoring.

**Existential force:** sometimes non-constructive proofs are the only route. Brouwer's fixed-point theorem: a continuous map of a disk into itself has a fixed point. The proof via algebraic topology does not specify the coordinates of the point.

Non-constructive proofs are 'worse' than constructive ones and should be avoided

Non-constructive methods are legitimate and sometimes the only option. They are less informative, but no less correct

Classical and constructive logic are different systems with different axioms. Classical proofs are valid in classical logic. The question is not 'better or worse' but what information the proof carries: constructive yields an object, non-constructive yields only the fact of existence.

Cantor's diagonal argument proves existence of a number outside any list. Why is it considered constructive?

Key Ideas

**Case analysis** splits the domain into exhaustive subsets and proves the claim for each; you must ensure the cases cover everything
**Mathematical induction** proves claims about infinite sets through a base and a step; strong induction lets you use every previous fact
**Constructive proofs** build the object explicitly, unlike non-constructive ones that merely assert existence
**Existence proofs** use different methods: witness, contradiction, counting, probability, with different levels of information

Вопросы для размышления

Why is a constructive proof more informative than a non-constructive one, even when both prove the same statement?
Give an example of a problem where case analysis is the natural approach but induction is not (and vice versa)
When you have proved a theorem non-constructively, when should you look for a constructive proof and when should you not?

Связанные уроки

ml-03