mathematical induction
Enable an agent to recognise mathematical induction, record its proof obligations, assess whether they are discharged, and choose justified next proof steps.
Research draft, second pass
A second pass drafted this model: the structure a model of this thing needs, and what is known about it in the world. The line under this one says how the second half was obtained - researched against sources, or recalled without web access, in which case nothing here was read anywhere and every claim is a lead to verify. Unreviewed either way.
recalled by Codex without web access - no source was read
Researched by: Codex
Purpose and description
Enable an agent to recognise mathematical induction, record its proof obligations, assess whether they are discharged, and choose justified next proof steps.
Mathematical induction is a deductive proof method that establishes a proposition for every natural number from a specified starting value by proving it at that value and proving that its truth at any such number implies its truth at the next.
It can be Extract an indexed proposition and generate its base-case and inductive-step obligations.; Choose ordinary or strong induction by inspecting the earlier instances needed by the proposed step.; Check that quantifiers and side conditions permit each use of the induction hypothesis.; Detect missing initial cases, uncovered indices and circular dependencies.; Propose a strengthened proposition or generalised parameter when the current induction hypothesis is insufficient.; Issue the quantified conclusion only after the required obligations and index coverage are established..
Distinguishing features
The argument proves a universally quantified proposition over an explicitly specified natural-number range; checking many examples alone does not qualify.
An ordinary induction step derives P(k+1) from an admissible assumption P(k), with k arbitrary in the stated range.
A strong induction step may assume P(j) for every admissible j up to k when deriving P(k+1), rather than assuming the desired result without an index restriction.
Established starting cases and the transition rule together cover every index claimed by the conclusion.
The method yields a deductive conclusion conditional on its premises and mathematical setting, rather than a confidence estimate based on observed regularities.
Scope
+ The indexed proposition, natural-number domain, starting index and quantified parameters
+ Ordinary and strong induction and the justification for choosing between them
+ Base cases, induction hypotheses, inductive steps and their dependency coverage
+ Validity conditions, unresolved proof obligations and common induction errors
+ The relationship between a completed induction argument and its quantified conclusion
- Empirical or statistical induction from observations to probable generalisations
- Recursive definitions and algorithms except for their role in an induction argument
- Structural induction over syntax trees or other inductively generated objects as an independently modelled method
- General well-founded and transfinite induction beyond natural-number indexing
- The mathematical subject matter of the theorem being proved
- Proof-assistant infrastructure and general proof-document management
Characteristics
- Indexed proposition
- Predicate P(n), with any additional parameters and quantifiers explicit The base cases, induction hypothesis and conclusion must refer to the same proposition.
- Index domain and starting index
- A specified natural-number range n ≥ n₀, with the convention for whether zero belongs to the natural numbers recorded Determines the first required cases and the extent of the conclusion.
- Induction formulation
- Ordinary induction; strong induction; explicitly justified natural-number variant Determines which earlier instances may be assumed during the inductive step.
- Parameter quantifier placement
- Parameters fixed throughout the induction; universally quantified inside P(n); explicitly constrained dependent parameters Controls whether the induction hypothesis can be instantiated at changed parameter values.
- Base-case coverage
- Not specified; required cases identified; partially proved; all required cases proved A valid transition cannot compensate for missing starting cases.
- Inductive dependency
- The earlier indices or indexed statements used to prove the target instance Exposes unavailable assumptions, dependency gaps and circular reasoning.
- Proof-obligation status
- Unassessed; incomplete; invalid as written; discharged relative to stated premises Distinguishes an induction plan from an argument that supports its conclusion.
- Verification basis
- Unchecked argument; human-reviewed argument; mechanically checked argument in an identified formal system Records how the assessment was established without conflating mathematical validity with a particular checking procedure.
Also called
Where this came from
wikidata · CC0 1.0
Drafted structure
Bundle to layer to finding to question, as the second pass will find it: 6 bundles · 11 layers · 15 findings · 25 questions.
Indexed claim The exact proposition and range to which induction is applied.
An induction argument can appear complete while proving a different proposition or a smaller range than intended.
Predicate and quantifiers
Makes the induction variable and other variables logically explicit.
Stable induction predicate
Record P(n) with its quantifier structure so that each proof stage can be checked against the intended claim.
- What exactly is P(n), including every side condition and quantifier? definition
- Which parameters remain fixed, and which must be universally quantified inside P(n) for the step to work? boundary
Natural-number range
Identifies the initial index and every index included in the intended conclusion.
Declared index coverage
Record the admissible indices explicitly rather than relying on an unstated convention about natural numbers.
- Does the claim begin at zero, one or another specified natural number? definition
- Does the intended conclusion cover all subsequent natural numbers or only a restricted subset requiring an additional argument? boundary
Induction principle The rule that licenses passage from starting cases and conditional steps to a universal conclusion.
Different formulations grant different induction hypotheses and must not be mixed implicitly.
Formulation selection
Matches the induction formulation to the proof's dependency requirements.
Permitted hypothesis
Record whether the step may use only P(k), every P(j) from the starting index through k, or another explicitly justified collection.
- Is the argument using ordinary induction, strong induction or a stated variant? definition
- Which earlier instances does the proposed step need, and does the selected formulation permit all of them? action
Logical setting
Records how the induction principle is supplied in the mathematical setting being used.
Principle justification
Identify the adopted induction rule, axiom instance or theorem when the argument requires formal grounding.
- Which stated rule, axiom schema or established theorem licenses this induction argument? provenance
- Does the chosen formal setting impose restrictions on the predicates to which that principle applies? boundary
Base and step obligations The mathematical work required to establish the starting cases and the general transition.
A named induction method supplies no conclusion until its concrete obligations have been proved.
Initial cases
Determines and verifies the starting cases required by the transition.
Sufficient starting cases
Record each required initial instance and its proof, including extra instances needed by transitions using several predecessors.
- Which initial cases are required before the proposed transition can establish subsequent cases? definition
- Has each required case been established without invoking an unproved instance of the induction claim? action
General transition
Checks the conditional derivation at an arbitrary admissible index.
Valid successor derivation
Record the induction hypothesis, target instance and derivation, including conditions needed for intermediate operations.
- Starting from the permitted induction hypothesis, what establishes P(k+1) for arbitrary admissible k? action
- Are all required side conditions, such as nonzero divisors or valid predecessor indices, established throughout the step? boundary
Dependency and coverage Whether the proof reaches its entire claimed range using only justified dependencies.
Locally plausible steps can conceal circular assumptions or leave whole classes of indices unproved.
Hypothesis use
Audits every appeal to an earlier indexed instance.
Admissible instantiation
Connect each use of the induction hypothesis to an allowed index and compatible parameter values.
- For each appeal to the induction hypothesis, which index and parameter values are substituted? definition
- Does any appeal require the target instance, a later instance or a parameter substitution not licensed by the hypothesis? boundary
Reachability of indices
Checks that established starting cases and the actual transition cover the claimed index domain.
No uncovered index classes
Identify coverage gaps, such as proving only even indices with a step of two and a single even base case.
- Can every claimed index be reached from an established base case through the proved transitions? boundary
- If the transition advances by more than one, which additional starting cases or reindexing argument are needed? action
Assessment and repair The supported conclusion, remaining obligations and justified ways to revise an unsuccessful induction.
An agent must distinguish a false claim from an inadequate induction attempt and preserve that distinction when acting.
Completion assessment
Separates verified obligations from unsupported assertions and records the basis of review.
Conclusion warrant
Record the precise universal statement supported by discharged obligations and the premises on which it depends.
- Which obligations remain unresolved, and what exact conclusion is warranted by those already discharged? action
- What review or formal checking supports the recorded completion status? provenance
Failed attempt repair
Classifies failures and identifies changes that could produce a valid argument.
Claim or method revision
Distinguish a counterexample to the claim from missing base cases, an insufficient hypothesis or an invalid derivation.
- Does the failure exhibit a counterexample to P(n), or only a gap in this attempted proof? boundary
- Would strengthening P(n), generalising a parameter, changing the starting index or using strong induction resolve the identified gap? action
Evidence and external alignment What the world already says about this thing, gathered so the model can be checked against it.
A model that cannot be lined up against existing standards, identifiers and practice cannot be adopted by anyone who already uses them.
Reported evidence
Findings from the breadth pass, kept separate from the structural claims.
Check these first
Recalled without web access and unsourced; every item is a lead to verify.
- No sense was supplied; this describes the mathematical proof method, not a particular written exposition or creative work.
- Structural, well-founded and transfinite induction are generalizations of the natural-number method; the listed kinds overlap rather than forming disjoint categories.
- The starting natural number may be 0 or 1 by convention; formal treatments also distinguish induction as an axiom schema from a single second-order axiom.
- Which of these check these first hold for the sense of mathematical induction this model covers, and on what evidence? provenance
Kinds and varieties
Recalled without web access and unsourced; every item is a lead to verify.
- Ordinary (weak) induction
- Strong (complete) induction
- Simultaneous (mutual) induction
- Structural induction
- Well-founded induction
- Transfinite induction
- Which of these kinds and varieties hold for the sense of mathematical induction this model covers, and on what evidence? provenance
Real-world use
Recalled without web access and unsourced; every item is a lead to verify.
- Proving formulas for finite sums, inequalities and divisibility properties
- Establishing properties of recursively defined sequences
- Proving correctness of recursive algorithms
- Proving properties of syntax trees and other inductively defined structures
- Establishing invariants across successive computation steps
- Which of these real-world use hold for the sense of mathematical induction this model covers, and on what evidence? provenance
Failure modes and hazards
Recalled without web access and unsourced; every item is a lead to verify.
- Omitting a necessary base case or choosing a base case that does not cover the claimed domain
- Assuming the conclusion for the next case instead of deriving it from the induction hypothesis
- Proving an inductive step that fails at a boundary or skips cases
- Using an induction hypothesis too weak to support the required step
- Applying generalized induction without establishing that the underlying relation is well-founded
- Which of these failure modes and hazards hold for the sense of mathematical induction this model covers, and on what evidence? provenance
Neighbouring kinds and how to tell them apart
Recalled without web access and unsourced; every item is a lead to verify.
- Inductive reasoning - Inductive reasoning extrapolates from observations; mathematical induction is deductive and establishes every case covered by its premises.
- Recursion - Recursion defines objects or computations through simpler cases; induction proves propositions about cases.
- Well-ordering principle - The well-ordering principle asserts that every nonempty subset of the natural numbers has a least element; induction supplies a proof principle, equivalent under suitable foundational assumptions.
- Proof by infinite descent - Infinite descent rules out a counterexample by deriving a strictly smaller one indefinitely; ordinary induction proceeds from a base case through a successor implication.
- Proof by exhaustion - Exhaustion checks every case individually in a finite domain; induction uses a general step to cover an unbounded sequence of cases.
- Which of these neighbouring kinds and how to tell them apart hold for the sense of mathematical induction this model covers, and on what evidence? provenance
What the second pass must settle
- Does the existing Vercy catalogue already contain an authoritative model of mathematical induction or a proof-method model to which this registry entry should link?
- Should structural and well-founded induction be represented as neighbouring models or included as explicitly distinguished variants within this registry entry?
- Which authoritative sources should ground the published treatment of ordinary and strong induction and their relationship?
- How much formal-system detail should agents be required to record for informal proofs versus mechanically checked proofs?
- Should simultaneous induction and induction with non-unit steps receive dedicated layers, or be represented through explicitly justified variants and dependency coverage?