Ludium
Sign In
Mathematical Reasoning: Writing and Proof
Introduction to Writing Proofs
01What Is a Statement? Truth Values and If-Then02Quantifiers and Counterexamples: What One Example Can Prove03The Truth Table for If-Then: When a Conditional Is False04Using Conditionals: Theorems, Counterexamples and ClosureProblem set0/10Problem set 20/10
01Even and Odd Integers: Why a Proof Starts From the Definition02The Know-Show Table: Proving Odd Times Odd Is Odd03Writing Proofs for a Reader: Six Guidelines and Sums of Even and Odd04Backward Answers Must Imply the Goal: Two More Direct ProofsProblem set0/10Problem set 20/10
Logical Reasoning
01Logical Operators: Truth Rules for And, Or, Not and If-Then02Only If, Necessary and Sufficient: Truth Tables and Tautologies03Logical Equivalence: De Morgan's Laws and the Contrapositive04Negating If-Then and Proving Equivalences by ChainsProblem set0/10Problem set 20/10
01Sets and Variables: The Roster Method and the Universal Set02Element, Subset and Truth Set: Open Sentences as Predicates03Set Builder Notation, the Empty Set, and Sentences True for All xProblem set0/10Problem set 20/10
01Quantifiers: When For Every and There Exists Statements Are True02Negating Quantified Statements: The Quantifier Switches03Counterexamples and Negating Definitions With Quantifiers04Statements With Two Quantifiers: Why the Order MattersProblem set0/10Problem set 20/10
Constructing Proofs
01Divisibility: Definition, Notation, and Non-Divisors02Proving Divisibility Is Transitive: Axioms, Definitions, Proof03A Divisor of Two Numbers Divides Their Sum, and Counterexamples04Congruence Modulo n: A Proof Mod 8 and 7 Rules for Writing ProofsProblem set0/10Problem set 20/10
01Proving the Contrapositive When a Direct Proof Stalls02Writing a Proof by Contrapositive: ab = 0 and De Morgan03Proving Biconditionals: Two Conditionals, Each Marked04Constructive and Nonconstructive Proofs of ExistenceProblem set0/10Problem set 20/10
Contradiction, Cases and Proof Writing
01Why Proof by Contradiction Works and How to Negate the Claim02Writing a Proof by Contradiction: x/y + y/x and Negations03Proving Nonexistence by Contradiction: Even Equals Odd04Proof That √2 Is Irrational: Rational and Irrational NumbersProblem set0/10Problem set 20/10
01Proof by Cases: Why It Works, and Why n² + n Is Even02Choosing Exhaustive Cases and Writing a Case Proof03Absolute Value by Cases: Proving |x| = A and |-x| = |x|04The Triangle Inequality by Cases: |x + y| ≤ |x| + |y|Problem set0/10Problem set 20/10
01Many Ways to Write 27 = 4q + r, and a Mod 6 Proof02The Division Algorithm: One Quotient, One Remainder03Proof by Remainders: Why 3 Divides n³ - n04Adding, Multiplying and Powering Congruences05Congruence Is Reflexive, Symmetric and Transitive06Each Integer Is Congruent to Its Remainder: Squares Mod 507Ruling Out Cases to Prove a² ≡ 1 (mod 6)Problem set0/10Problem set 20/10
01Direct, Contrapositive or Contradiction: Choosing a Proof02Proof by Cases, Equivalences, and Existence Proofs03Writing a Proof for a Reader: Openings and Signposts04Writing the Math in a Proof: Displays and a Clear EndingProblem set0/10Problem set 20/10
Mathematical Induction
01Inductive Sets: Why a Table of Cases Is Not a Proof02The Principle of Mathematical Induction as an Axiom03Induction on Sums: Add the Next Term to Both Sides04Why Both Steps Matter: Proving 4 Divides 5ⁿ − 1Problem set0/10Problem set 20/10
01When Ordinary Induction Falls Short: n! vs 2ⁿ and Primes02Extended Induction: Start the Basis Step at Any Integer M03Strong Induction: Every Integer Above 1 Factors into Primes04Three Basis Cases: Every n from 8 On Is a Sum of 3s and 5sProblem set0/10Problem set 20/10
01Defining Sequences by Recursion: From Halving to n!02Fibonacci Numbers: Patterns, Rabbits and Sanskrit Verse03Every Third Fibonacci Number Is Even: An Induction Proof04Geometric Series by Induction: a(1 − rⁿ)/(1 − r)Problem set0/10Problem set 20/10
Set Theory
01Intersection, Union, Difference, Complement: And, Or, Not for Sets02Venn Diagrams for Two Sets: Four Regions and De Morgan's Law03Proper Subsets, the Empty Set and Set Equality04Venn Diagrams for Three Sets: Eight Regions and Subset Conditions05Power Sets Have 2ⁿ Elements: Cardinality and the Number SystemsProblem set0/10Problem set 20/10
01Choose-an-Element Proofs: Multiples of 6 Are a Subset of the Evens02Complements Reverse Subsets: A ⊆ B Implies Bᶜ ⊆ Aᶜ03Proving Set Equality by Two Inclusions: A − (A − B) = A ∩ B04Proving a Set Is Empty: Disjoint Sets and Element ChasingProblem set0/10Problem set 20/10
01De Morgan's Law for Unions and Cycles of Conditionals02Laws of Union and Intersection: Proving A ∩ B = B ∩ A03Distributive Law: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)04Complement Laws and Proofs by the Algebra of SetsProblem set0/10Problem set 20/10
01Ordered Pairs as Solutions: The Truth Set of 2x + 3y = 1202The Cartesian Product A × B: Listing Pairs, Testing Laws03Products of Intervals Are Rectangles in the Plane04Proving A × (B ∪ C) = (A × B) ∪ (A × C)Problem set0/10Problem set 20/10
01Union and Intersection of a Family: Some Versus All02Indexed Unions: Subscripts for Infinitely Many Sets03Families Indexed by Any Set: One Interval per Real Number04De Morgan's Laws for Any Family, and Pairwise DisjointProblem set0/10Problem set 20/10
Functions
01What Is a Function? Exactly One Output for Each Input02Functions Without Formulas: Birthdays and Sums of Divisors03Images and Preimages: The Formal Definition of a Function04The Range of a Function: From Graphs and Arrow DiagramsProblem set0/10Problem set 20/10

Inductive Sets: Why a Table of Cases Is Not a Proof

Why can no table of checked cases prove a statement about every natural number, and what does an inductive set capture?


Loading…

←Previous Writing the Math in a Proof: Displays and a Clear EndingNext The Principle of Mathematical Induction as an Axiom →

Your summary note

    1. 1

      Evidence from a table of cases versus proof

      Tabulate 5n−15^n - 15n−1 for n=1n = 1n=1 to 666 as multiples of 4, or check 12+⋯+n2=n(n+1)(2n+1)61^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}12+⋯+n2=6n(n+1)(2n+1)​ for several nnn, and state that no finite table proves (∀n∈N)(P(n))(\forall n \in \mathbb{N})(P(n))(∀n∈N)(P(n)).

    2. 2

      The definition of an inductive set

      Write the definition as (∀k∈Z)(k∈T→k+1∈T)(\forall k \in \mathbb{Z})(k \in T \to k + 1 \in T)(∀k∈Z)(k∈T→k+1∈T), and record that N\mathbb{N}N, {n∈Z∣n≥−3}\{n \in \mathbb{Z} \mid n \geq -3\}{n∈Z∣n≥−3} and Z\mathbb{Z}Z are all inductive despite starting in different places or nowhere.

    3. 3

      Showing a set is not inductive

      Negate the definition step by step to reach (∃k∈Z)(k∈T∧k+1∉T)(\exists k \in \mathbb{Z})(k \in T \wedge k + 1 \notin T)(∃k∈Z)(k∈T∧k+1∈/T), and give the single counterexample for {1,2,…,20}\{1, 2, \ldots, 20\}{1,2,…,20}, {n∈Z∣n≤100}\{n \in \mathbb{Z} \mid n \leq 100\}{n∈Z∣n≤100} and the odd naturals.

    4. 4

      An inductive subset of N\mathbb{N}N containing 1

      Starting from T⊆NT \subseteq \mathbb{N}T⊆N, 1∈T1 \in T1∈T and TTT inductive, derive 2,3,4∈T2, 3, 4 \in T2,3,4∈T in turn, describe reaching 100∈T100 \in T100∈T, and note that concluding T=NT = \mathbb{N}T=N rests on an unproved 'and so on'.

    Attempt 1 of 2