Mathematical proof Study Guide

📖 Core Concepts Mathematical proof – a deductive argument showing a statement follows logically from its assumptions. Axioms – basic, accepted assumptions; every proof can be built from them together with rules of inference. Formal vs. informal proof – formal: only symbols, each line follows by a rule of inference; informal: mixes symbols with natural language. Conjecture – a proposition believed true but not yet proved; when repeatedly used as an assumption it may be called a hypothesis. Undecidable statement – cannot be proved or disproved from a given axiom system. Gödel’s First Incompleteness Theorem – any sufficiently rich axiom system contains true statements that are undecidable within that system. 📌 Must Remember A proof must meet the community’s standards of rigor; vague or incomplete arguments are rejected. Direct proof: combine axioms, definitions, and known theorems to reach the conclusion. Induction: prove a base case and show $P(n) \Rightarrow P(n+1)$ to conclude $P(n)$ holds for all $n\in\mathbb{N}$. Contraposition: “if $p$ then $q$” ⇔ “if $\neg q$ then $\neg p$”. Contradiction (reductio ad absurdum): assume the statement, derive a logical inconsistency, then reject the assumption. Construction: exhibit a concrete example that satisfies the required property (existence proof). Exhaustion: split the claim into finitely many cases and prove each one. Probabilistic proof: show a non‑zero probability of selecting an object with the desired property → existence is guaranteed. Combinatorial proof: prove equality by counting the same set in two different ways (often via a bijection). Non‑constructive proof: establish existence without giving an explicit example, usually via contradiction. Computer‑assisted proof: use programs or massive calculations to verify many cases (e.g., four‑color theorem). 🔄 Key Processes Formal proof construction Start with axioms/assumptions. Apply a rule of inference to obtain a new formula. Repeat until the desired statement appears. Mathematical induction Base step: prove $P(0)$ (or $P(1)$). Inductive step: assume $P(k)$ (induction hypothesis) → prove $P(k+1)$. Conclude $P(n)$ true ∀ $n\in\mathbb{N}$. Proof by contraposition Identify original implication “if $p$ then $q$”. Prove the contrapositive “if $\neg q$ then $\neg p$”. Proof by contradiction Assume the negation of the target statement. Derive a contradiction (e.g., $A$ and $\neg A$). Conclude the original statement must be true. Combinatorial counting proof Define set $S$ counted in two ways. Compute $\lvert S\rvert$ via method 1 → expression A. Compute $\lvert S\rvert$ via method 2 → expression B. Conclude $A = B$. 🔍 Key Comparisons Direct proof vs. proof by contradiction Direct: builds the conclusion forward from premises. Contradiction: assumes the opposite, shows inconsistency. Constructive vs. non‑constructive existence proof Constructive: provides an explicit example. Non‑constructive: proves existence without giving an example. Proof by exhaustion vs. computer‑assisted proof Exhaustion: manual case‑by‑case verification (finite, doable by hand). Computer‑assisted: many cases delegated to a program. Induction vs. contraposition Induction: leverages a natural number ordering. Contraposition: flips an implication; no ordering needed. ⚠️ Common Misunderstandings “Induction proves one case” – it proves all natural numbers once base and step are established. “Contradiction proves the statement directly” – it actually proves the negation is impossible, so the original must be true. “A probabilistic proof gives a concrete example” – it only shows a non‑zero chance, not an explicit construction. “If a statement is undecidable, it is false” – undecidable means neither provable nor disprovable within the given axioms, not that it is false. 🧠 Mental Models / Intuition Proof as a chain – each link (line) must follow from previous links using a known rule; break the chain at any point and you see the logical gap. Induction as dominoes – base case knocks down the first domino; the inductive step shows that if one domino falls, the next one does too, so all fall. Contraposition as “reverse engineering” – sometimes it’s easier to show that the only way the conclusion could fail forces the hypothesis to fail. 🚩 Exceptions & Edge Cases Undecidable statements exist only relative to a particular axiom system; changing the axioms can make them decidable. Gödel’s theorem applies to any system capable of encoding arithmetic; trivial systems (e.g., propositional logic) are not subject to the same limitation. 📍 When to Use Which Direct proof – when the conclusion follows straightforwardly from definitions or known theorems. Induction – when the statement quantifies over natural numbers or recursively defined objects. Contraposition – when the contrapositive is simpler to prove than the original implication. Contradiction – when assuming the opposite leads quickly to an impossible statement (e.g., “an integer is both even and odd”). Construction – when you can explicitly exhibit an object (useful for existence questions). Exhaustion – when the domain splits into a small, manageable number of distinct cases. Probabilistic proof – when counting all cases is infeasible but a non‑zero probability can be shown (often in combinatorics). Combinatorial proof – when two expressions count the same set; look for a bijection or double‑counting argument. Computer‑assisted proof – when the number of cases exceeds manual capability but can be algorithmically checked. 👀 Patterns to Recognize “If … then …” statements often invite contraposition or contradiction. Statements about “for all $n$” hint at induction. Equality of two sums/products suggests a combinatorial (double‑counting) proof. Existence claims without a constructive example may be non‑constructive or probabilistic. Finite case splits → consider proof by exhaustion or computer assistance. 🗂️ Exam Traps Choosing contradiction when a direct proof is shorter – exam may penalize unnecessary complexity. Treating a probabilistic proof as constructive – the exam may ask for an explicit example; a probabilistic argument won’t earn full credit. Assuming undecidable → false – a distractor that claims undecidable statements are false; remember undecidable ≠ false. Confusing “contrapositive” with “inverse” – the inverse “if not $p$ then not $q$” is not logically equivalent; watch answer choices that swap them. Leaving out the base case in induction – many options omit the base case, making the argument invalid. --- Use this guide for a quick, confidence‑boosting review before your exam!