🗄️
math-debrief
  • Math Debrief
  • Math: TIMELINE
  • 100-fundamentals
    • debrief-name: math section-code: 000 section-name: general section-desc: Elementary topics pervasive
      • About Mathematics
      • abstraction-in-math
      • About Math
      • Axiom schema
      • Basic concepts in math
      • Collections
      • Elementary concepts in objects
      • Elements of mathematics
      • math-as-a-language
      • Mathematical structures
      • List of mathematics-based methods
      • Mathematics and Reality
      • Mathematics: General
      • Controversial mathematics
      • the-elements-of-math
      • What is mathematics
    • The foundation of mathematics
      • Mathematical foundations
      • Foundations of Mathematics
      • Axiomatization of mathematics
      • Foundational crisis of mathematics
      • Foundations
      • Hilbert's problems
      • impl-of-math-in-set-theory
      • Gödel's Incompleteness Theorem
      • Theorems in the foundations of mathematics
      • The list of FOM candidates
      • Logicism
    • Philosophy of mathematics
      • Constructive mathematics
      • Constructive mathematics
      • Metamathematics
      • Philosophy of mathematics
      • Schools of mathematics
    • terms
      • Terms
      • Arithmetic
      • Axiom
      • The Axiomatic Method
      • discrete-math
      • 201 Discrete mathematics
      • Euclidean space
      • Formal system
      • Function
      • Generalization
      • Geometry
      • Higher-order
      • Impredicativity
      • Level of measurement
      • Mathematical definition
      • FAQ
      • Mathematical function
      • Mathematical induction
      • Mathematical object
      • Mathematical object
      • Equivalent definitions of mathematical structures
      • Mathematics
      • Mathematical model
      • mathematical-notation
      • Mathematical pages
      • Mathematical terminology
      • Mathematical adjective
      • Numbers
      • plane
      • Primer: Set Theory
      • Mathematical primitive
      • Set
      • Space
      • theory
      • Variable
  • 200 Set and Set theory
    • Sets: Hierarchy
    • set.TERMS
    • SETS › TOPICS
    • 201 Set concepts
      • Mathematical collections
      • The notion of sets
      • Specification of sets
    • Set cardinality
      • Cardinality of the continuum
      • Cardinality
      • Set Cardinality
      • cardinality2
      • Set cardinality
    • Set operations
      • Disjoint sets
      • Overlapping sets
      • Product
      • set-interactions
      • Set qualities
      • Set relations
    • Set properties
      • Basic set properties
      • Set properties
    • Set relations
      • Basic set relations
      • Disjoint sets
      • Inclusion relation
      • Membership Relation
      • Set membership
    • Summary
      • Set FAQ
      • Sets: Summary
    • Set theories
      • Axiomatic set theory
      • Set Theories
      • Naive Set Theory
      • Morse-Kelley set theory
      • von Neumann-Bernays-Gödel Set Theory
      • Quine's New Foundations (NF)
      • Cantor's set theory
      • Zermelo-Fraenkel set theory
    • Axioms of set theory
      • axiom-of-choice
      • The Axiom of Extensionality
      • Axiom of infinity
      • axiom-of-pairing
      • Axiom of powerset
      • Axiom of Regularity
      • Axiom of replacement
      • Axiom of union
      • Axiom of well-ordering
      • axiom-schema-of-comprehension
      • Axiom Schema of Specification
      • Axioms of set theories
      • List of axioms in set theory
      • ZFC Axioms
    • Sets: Terms
      • Bell Number
      • Cardinal number
      • Class (set theory)
      • Closure
      • empty-set
      • Extended set operations
      • Extensions by definitions
      • Family of sets
      • Fundamental sets
      • fundamental-sets2
      • Georg Cantor
      • History of set theory
      • Implementation of mathematics in set theory
      • Indexed family of sets
      • Extensional and intensional definitions
      • Involution
      • list-of-axioms-of-set-theory
      • Implementation of mathematics in set theory
      • Set membership
      • Naive Set Theory
      • Number of relations
      • empty-relation
      • Set Partitioning
      • Powerset
      • Russell's paradox
      • Set-builder notation
      • Set equivalence
      • Set Notation in latex
      • Set notation
      • Set partition
      • Intensional and extensional set specification
      • Set notation
      • Basic concepts in set theory
      • set-theory
      • Set Types
      • set
      • subset
      • Transfinite number
      • Tuples
      • ur-elements
  • Relations
    • basic-concepts
      • algebraic-axioms
      • Elements of a relation
      • Types of Relations
      • Named Relations
      • Relation theory
      • Relations
      • Types of relations
    • Relations
      • Definitions
      • Reflexivity
      • Symmetry
      • Transitivity
    • relation-properties
      • Uniqueness properties of relations
    • Types of relations
      • Transitivity
      • Binary Relation
      • Congruence relation
      • Connex relation
      • axioms-sets-zfc
      • Endorelation
      • Equivalence relation
      • Euclidean
      • Finitary relation
      • Heterogeneous relation
      • Homogeneous relation
      • Transitivity
      • Partial equivalence relation
      • Transitivity
      • Transitivity
      • Reflexive relation
      • Reflexivity
      • Index of relations
      • Serial relation
      • Symmetry
      • Transitivity
      • Ternary relation
      • Trichotomy
      • Universal relation
      • Well-foundedness
    • terms
      • Relations
      • Binary relation
      • Relations
      • _finitary-rel
      • Relations: Overview
      • Relations
      • Index of relations
      • Binary relations
      • Composition of relations
      • Equivalence class
      • Notation
      • Relation
      • Relations
      • Sets: Summary
      • Aggregation: Sets, Relations, Functions
  • Order theory
    • Order theory
    • List of order structures in mathematics
    • List of order theory topics
    • Order theory
      • Hasse diagram
      • Order theory
      • ordered-set
      • Partial order
      • Partially ordered set
      • Total order
  • Function Theory
    • Function Theory: GLOSSARY
    • Function Theory: HIERARCHY
    • Function Theory: LINKS
    • Function Theory: TERMS
    • Function Theory: TOPIC
    • Function Theory: WIKI
    • _articles
      • about-functions
      • Function
      • Formal definition
      • Definition
      • constant
      • Introduction
      • Types of functions
      • Functions: Summary of Notations
      • Functions: Overview
      • Properties of functions
      • Function properties
      • Functions: Summary
      • Function
    • Abjections
      • Bijective function
      • Function (abjections)
      • Injective function
      • Surjective function
    • topics
      • Function: TERMS
      • Codomain
      • Composition of functions
      • Currying
      • Division of functions
      • Domain
      • Function fixed points
      • Function cardinality
      • Function definition
      • Elements of a function
      • Function in mathematics
      • Function notion
      • Function operations
      • Function properties
      • Functional statements
      • Functions in programing languages
      • Image and Preimage
      • Image
      • Inverse function
      • Notion of functions
      • Number and types of functions between two sets
      • Operation
      • Range
      • Successor function
      • Time complexity classes
  • debrief-name: math section-code: 280 section-name: domain-theory section-desc:
    • Domain theory: LINKS
    • Domain theory
  • Logic
    • Logic: CHRONO TERMS
    • Logic: CLUSTERS
    • lo.GLOSSARY
    • Logic: Wiki links
    • 305-basic-concepts
      • Introduction to Logic
      • Argumentation
      • Logic: Basic terminology
      • Logic: Terminology
      • Truth function
      • Truth function
    • README
      • Mathematical Logic
      • Types of Logic
      • BHK interpretation
      • FOL
      • Index of Logic Forms
      • History of logic
      • Logic Indices
      • Interpretation of symbols in logic and math
      • logic-systems
      • Mathematical Logic: People and Events
      • Index of logical fallacies
      • Logical symbols
      • Mathematical conjecture
      • Mathematical induction
      • Mathematical lemma
      • Mathematical Logic
      • Mathematical proof
      • Mathematical theorem
      • Mathematical theory
      • Monotonicity of entailment
      • Satisfiability Modulo Theories
      • Sequent Calculus
      • Sequent
      • Tableaux
      • Truth tables
    • 360-propositional-logic
      • Propositional Logic
      • Propositional Logic
    • 370-predicate-logic
      • Predicate Logic
      • First-order logic
      • Predicate calculus
      • Examples of predicate formulae
    • 380-proof-theory
      • Argument-deduction-proof distinctions
      • Direct proof
      • Mathematical induction
      • Mathematical induction
      • Mathematical proof
      • Natural deduction
      • Natural deduction
      • Proof by induction
      • Proof by induction
      • proof-calculus
      • Proof Theory
      • Structural induction
      • System L
      • Proof theory
    • Logic: Indices
      • Gödel's Incompleteness Theorem
      • The History of Mathematical Logic
      • forallx
      • Logic for CS
      • Lectures in Logic and Set Theory
      • _logicomix
    • Logic
      • Logical connectives
      • Logical equivalence
    • Rules of Inference
      • WIKI
      • Conjunction elimination
      • Conjunction introduction
      • Cut rule
      • Disjunction elimination
      • Disjunction introduction
      • Disjunctive syllogism
      • Exportation
      • implication-elimination
      • implication-introduction
      • Rules of Inference: Index
      • Rules of inference
      • Rules of Inference for Natural Deduction
      • Logical Inference
      • Reiteration
      • Rule of inference
      • Structural rules
      • substitution
    • Logic
      • The principle of bivalence
      • The principle of explosion
      • The Law of Identity (ID)
      • Laws of thought
      • Properties of logic systems
      • List of laws in logic
      • The law of non-contradiction
    • Logic
      • Logic systems: LINKS
      • Logic system
      • logic-systems
      • logic-typ
      • logics-by-purpose
      • _logics
      • Affine logic
      • Algebraic logic
      • Bunched logic
      • Classical logic
      • Traditional first-order logic
      • Hoare logic
      • Linear logic
      • Modal logic
      • Non-monotonic logic
      • Syntax
      • Predicate logic
      • Propositional Logic
      • Relevance logic
      • Separation logic
      • Substructural logics
      • Syllogistic logic
    • Logic: Sections: Elementary
    • Logic: Topics
      • Pages in Logic
      • Logic ❱ Terms ❱ List
      • Logic ❱ Terms ❱ Definitions
      • Absoluteness
      • Assumption
      • Automated theorem proving
      • Canonical normal form
      • Categorical proposition
      • Classical linear logic
      • Consequence
      • Decidability
      • Deduction systems
      • deduction-theorem
      • Deductive reasoning
      • Diagonal lemma
      • Fallacy
      • Fitch notation
      • Formal language
      • formal-system
      • Formalism
      • Formula
      • functionally complete
      • Hilbert system
      • Hoare logic
      • horn-clause
      • Mathematical induction
      • Induction
      • Inductive Reasoning
      • Intuitionistic logic
      • Intuitionistic logic
      • Intuitionistic logic
      • Judgement
      • Judgments
      • Linear logic
      • Logic in computer science
      • Logic
      • Logical connective
      • Logical consequence
      • Logical constant
      • Logical form
      • axioms-sets
      • Logical reasoning
      • Ludics
      • Non-logical symbol
      • Predicate
      • Premise
      • Quantification
      • Realizability
      • Boolean satisfiability problem
      • DPLL algorithm
      • Satisfiability
      • Semantics of logic
      • Skolemization
      • SAT and SMT
      • Syntax
      • Tautology
      • Term
      • Unification
      • Validity
  • 510 Lambda Calculi
    • Lambda Calculus: GLOSSARY
    • Lambda calculi: LINKS
    • Lambda Calculus: OUTLINE
    • Lambda Calculus: Basic concepts
      • Introduction
      • Lambda expressions
      • Free variables
    • Lambda Calculi
      • Lambda calculus: LINKS
      • Lambda calculus combinators in Haskell
      • Lambda calculus: Combinators
      • Combinators
      • combos-all.js
      • combos-bird.js
      • combos-birds-list.js
      • combos-birds.js
      • Fixed-point combinator
      • Fixpoint operator
      • Lambda calculus: Fixpoint
    • combinatory-logic
      • algebraic-structures
      • Combinatory logic
      • Combinatory logic
      • relation-classification
      • 04-definition
    • Lambda calculus encoding schemes
      • bohm-berarducci-encoding
      • Index of Church encodings
      • Church encodings
      • Church Numerals
      • Encoding data structures
      • Encoding schemes in lambda calculi
      • Lambda encoding
      • Mogensen-Scott encoding
      • Parigot encoding
      • encodings
        • Encoding data structures
        • Encoding of Data Types in the λ-calculus
        • church-booleans
        • Church data structures
        • Church encoding
        • Church Numerals: Church encoding of natural numbers
        • Lambda Calculus: Church encoding
        • Lambda Calculus: Church encoding
        • church-numerals
        • Lambda Calculus: Church encoding: Numerals
        • Church pair
        • Pair
        • Lambda Calculus: Church encoding
        • Alternative encodings
        • Encoding schemes
        • Encoding schemes
        • Encodings in Untyped Lambda Calculus
        • Lambda calculus
        • Scott encoding
        • Lambda calculus: Scott encoding
    • lambda-calculus-evaluation
      • Call-by-name
      • Call-by-need
      • Call-by-value
    • lambda-calculus-forms
      • Beta normal form
      • Lambda terms
      • Fixity of lambda-terms
    • lambda-calculus-reductions
      • Alpha conversion
      • Beta reduction
      • Delta reduction
      • Eta conversion
      • Eta conversion
      • Lambda calculus: η-conversion
    • lambda-calculus
      • Alonzo Church
      • Inference rules for lambda calculus
      • Lambda Calculus: Introduction
      • Lambda abstraction
      • Lambda application
      • Lambda Calculus: Definition
      • About λ-calculus
      • Type inference
      • Lambda Calculus
      • Lambda Calculus: Introduction
      • Introduction to λ-calculus
      • Lambda calculus
      • Definition of Lambda Calculus
      • Functions in lambda calculus
      • History of Lambda Calculus
      • Using the Lambda Calculus
      • Name capturing
      • Variable occurrences
      • Variables
    • Lambda Calculus
      • Church-Rosser theorem
      • Curry's paradox
      • De Bruijn index
      • de Bruijn notation
      • Deductive lambda calculus
      • Kleene-Rosser paradox
      • Aspects of the lambda calculus
      • Function Refactoring
      • Lambda lifting
      • Let expression
      • Reduction strategy
      • Substitution
    • typed-lambda-calculi
      • Lambda Cube
      • Simply typed lambda calculus
      • System F
      • Typed lambda calculi
  • Type theory
    • Type Theory: GLOSSARY
    • Type theorists
    • Type Theory: SUMMARY
    • TERMS: Type Theory
      • Types
      • History of type theory
      • History of Type Theory
    • curry-howard-correspondence
      • The Curry-Howard Correspondence in Haskell
      • Curry-Howard correspondence
      • Curry-Howard correspondence
      • Curry-Howard correspondence
      • Curry-Howard-Lambek correspondence - HaskellWiki
    • dependent-types
      • Dependent type
      • Dependent type
    • Hindley-Milner type-system
      • Hindley-Milner type system
      • Monomorphism vs polymorphism
      • Let-polymorphism
      • The Hindley-Milner type system
      • Algorithm W in Haskell
      • Hindley-Milner Type Inference: W Algorithm
      • hindley–milner-type-system
      • Hindley-Milner type system
      • HM inference examples
      • HM in ML
      • Type Inference
    • Homotopy type theory
      • Homotopy type theory
      • Univalent Type theory as the foundations of mathematics
    • Intuitionistic type theory
      • Inductive definition
      • Inductive type
      • Intuitionistic type theory
    • Type Theory
      • TTTools
      • Coinduction
      • Impredicativity
      • Lean
      • Subsumption
    • Type Theory : Topics
      • Type Theory : Terms
      • Recursion types
      • Recursive data type
      • Subtyping
      • Type Class
      • Type Equivalence
      • Type Inference
      • Type rule
      • Type system
      • Variance
    • type-theories
      • Calculus of Constructions
      • Constructive type theory
      • ramified-type-theory
      • simple-type-theory
      • Substructural type systems
    • type-theory-general
      • Linear types
      • History of Type Theory
      • Type Theory
      • Overview
      • Type Theory
  • Abstract Algebra
    • 410-group-theory
      • Abelian group
    • algebras
      • Associative Algebra
      • Field
      • Group-like algebraic structures
      • group
      • Lattice
      • Magma
      • monoid
      • Overview of Algebras
      • Quasigroup
      • Rack and quandle
      • Ring
      • Semigroup
      • Algebra of sets
      • Setoid
    • boolean-algebra
      • Boolean algebra
      • Axioms in Boolean Algebra
      • Boolean algebra
      • Boolean Algebra Laws
      • Boolean Algebra Laws
      • Two-element Boolean algebra
      • Boolean algebra
      • Boolean domain
    • terms
      • Algebra
      • Axioms of abstract algebra
      • Algebraic notation for algebraic data types
      • Algebraic structure
      • Algebraic structure
      • Field of sets
      • Homomorphism
      • Isomorphism
      • Algebraic structures
      • Mathematical structure
      • Polynomials
      • Relation algebra
  • Category Theory
    • CT GLOSSARY
    • Category Theory: OUTLINE
    • CT SUMMARY
    • A First Introduction to Categories (2009)
      • Sets, maps, composition
      • 02-history
      • axioms-logic
      • Bijection of functions
      • Commutative diagram
      • Directed graph
      • CT prerequisites
      • String diagram
      • Transitive closure
    • Category Theory Fundamentals
      • Introduction
      • Interpretation
      • Fundamental concepts
      • Category theory
      • Category
      • Category Theory: Definitions
    • Key concepts
      • Duality
      • Functor
      • Homeset
      • Initial Object
      • Morphism
      • Natural transformation
      • Object
      • Terminal Object
    • Categorical constructions
      • Categorical constructions
      • Coproduct
      • Diagram
      • Product
      • Universal construction
    • Types of categories
      • Concrete category
      • Discrete category
      • Functor category
      • Groupoid
      • Hask
      • Kleisli category
      • Locally small category
      • Monoid
      • monoidal-categories.md
      • Index of named categories
      • Opposite category
      • Ordered category
      • Set category
      • Small category
      • Subcategory
    • Types of Functors
      • Adjoint functor
      • relation-arity
      • Endofunctor
      • Faithful functor
      • Forgetful functor
      • Hom functor
      • Identity functor
      • Inverse functor
      • Monad
      • Powerset functor
    • Types of Morphisms
      • Anamorphism
      • Automorphism
      • Catamorphism
      • Endomorphism
      • Epimorphism
      • Homomorphism
      • Hylomorphism
      • Idempotent morphism
      • Identity morphism
      • Inverse morphism
      • Isomorphism
      • Metamorphism
      • monomorphism
      • Natural isomorphism
      • Split morphism
    • 20-advanced-concepts
      • Coalgebra
      • (Co)Inductive types
      • Recursion Schemes
    • Category Theory
      • Category Theory: TERMS
      • Algebraic Data Types
      • Category Theory
      • Category
      • Coproduct
      • Function type
      • Functoriality
      • Initial Object
      • Limits and Colimits
      • Natural Transformation
      • 5. Products
      • Terminal Object
    • Category Theory :: Contents
      • CT :: Links
      • Category Theory :: Terms
      • Category :: Definition
      • F-Algebra
      • Functor
      • Initial object
      • Monoid
      • Natural Transformation
      • Number of morphisms
      • Terminal object
      • Transitive closure
      • Types of morphisms
      • Categories by cardinality
      • Types of functors
  • Number Theory
    • Invariance and Monovariance Principle
    • 615-arithmetic
      • Addition
      • Aliquot sum
      • Arithmetic function
      • Laws
      • Arithmetic operations
      • Index of arithmetic operations
      • Arithmetic operations
      • Arithmetic
      • Divisibility rules
      • Divisibility
      • division
      • Divisor Function
      • Divisor Summatory Function
      • Divisor
      • Euclidean division
      • Hyperoperations
      • hyperops
      • Modular arithmetic
      • Multiplication
      • Number Theory: primer in numbers
      • Percentage
      • Rules of Divisibility
      • Subtraction
    • The fundamental sets of numbers
      • Algebraic numbers
      • Complex numbers
      • Fractions
      • Fundamental number sets
      • Imaginary numbers
      • Integers
      • Irrational numbers
      • Natural number
      • Rational numbers
      • Real numbers
      • Transcendental numbers
      • Ulam's spiral
      • The whole numbers
    • COUNTING THEORY
      • Counting Theory
      • counting
      • Fundamental Counting Rules
    • 630-combinatorics
      • Combinatorics
      • Combinations
      • Combinatorics
      • Counting theory
      • Counting theory
      • Enumerative combinatorics
      • Partition
      • Pascals triangle
      • Permutations
      • Twelvefold way
    • Probability theory
      • Statistics › Probability theory: Glossary
      • Statistics › Probability theory › Topics
      • Statistics › Probability theory › Wiki Links
      • Conditional Probability
      • Distribution
      • Probability theory
      • Probability
    • Number theory
      • euclids-lemma
      • gcd-lcm
      • Induction
      • Infinity
      • Numbers and numerals with interesting properties
      • Lagrange's four-square theorem
      • Matrix
      • Matrix
      • List of Number Systems
      • Number Theory
      • Number Theory with Glenn Olsen
      • Number
      • Arithmetic
      • Numbers
      • numeral-prefixes
      • Numeral system
      • Numeral
      • Ordinal numbers
      • Parity
      • Peano axioms
      • Polynomial
      • Polynomial
      • Positional notation
      • Probability
      • Symbol
      • Well Ordering Principle
    • topics
      • Coprimality
      • Facorization of composite numbers
      • Fundamental Theorem of Arithmetic
      • Prime factorisation
      • Prime number
      • Prime numbers
  • Theory of computation
    • Theory of computation: Abbreviations
    • Theory of computation: CHRONOLOGICAL TOPICS
    • Theory of computation: GLOSSARY
    • Theory of Computation: HIERARCHY
    • Theory of computation: LINKS
    • Theory of computation: TERMS
    • Theory of computation: TOPICS
    • Theory of computation: WIKI
    • Theory of Computation
      • _toc-more
      • Theory of Computation
    • 610-automata-theory
      • Abstract machine
      • Automata Theory
      • Automaton
      • Edit distance
      • Finite-state Machine
      • Automata Theory: WIKI
    • Formal systems
      • Abstract interpretation
      • Alphabet
      • Binary combinatory logic
      • Chomsky hierarchy
      • Epsilon calculus
      • Formal language
      • Iota and Jot
      • Regular expression
      • Regular Language
      • SKI combinator calculus
    • 621-grammar
      • Backus-Naur Form (BNF)
      • Context-free grammar
      • Context-sensitive grammar
      • Extended Backus–Naur Form (EBNF)
      • Regular Language
      • Terminal and nonterminal symbols
    • 622-syntax
      • Syntax
    • 624-semantics
      • Axiomatic semantics
      • Denotational Semantics: Summary
      • Denotational Semantics
      • Denotational Semantics
      • Denotational semantics
      • Formal semantics
      • Operational semantics
      • Semantics in CS
      • Semantics
    • 630-computability-theory
      • Computability (recursion) theory: TERMS
      • Computability (recursion) theory: TOPICS
      • Effective Computability
      • Church Thesis
      • Church-Turing Thesis
      • Computability theory
      • Computability
      • Computable function
      • Entscheidungsproblem
      • Halting problem
      • Machine that always halts
      • McCarthy Formalism
      • Super-recursive algorithm
      • Recursion theory
    • 632-recursive-function-theory
      • Recursion Theory
      • Ackermann function
      • General recursive function
      • Minimization operator
      • Partial functions
      • Recursion Function Theory
      • Sudan function
    • 634-primitive-recursive-functions
      • Primitive Recursive Function
      • Initial functions
      • The list of primitive recursive functions
      • Primitive combination
      • Primitive composition
      • Primitive recursion
      • Successor function
    • 640-models-of-computation
      • Models of computation: Summaries
      • Model of computation
    • 680-complexity-theory
      • Algorithmic Complexity
      • Complexity Theory
  • debrief-name: math section-code: 900 section-name: aggregations section-desc: Aggregations, indices,
    • Index of closures
    • List of mathematical entities
    • List of mathematical objects
    • Enumeration of mathematical structures
    • Math : Axioms as Formulae
    • 950-math-areas
      • Areas of mathematics
      • Areas of mathematics
    • 970-links
      • check
      • Math: Links
      • Math Debrief: Links
      • Math Primer: LINKS
      • Links
      • Math: LINKS: ncatlab
      • Math: LINKS
      • WIKI
      • WIKI
      • WIKI_ALL
      • Math: Wiki lists
      • Glossary of areas of mathematics
      • WIKI_collections
      • Mathematics for Computer Science
      • Mathematics Classification
      • math
      • Resources
      • Math on YouTubel Video Playlists
      • wiki resources
    • 980-hierarchy
      • HIERAR
      • Math: Hierarchy
      • Math HIERARCHY
      • classification
        • Mathematics
        • https://ncatlab.org/nlab/all_pages https://ncatlab.org/nlab/all_pages/reference https://ncatlab.org/
        • Math Classification and Topical Pages
        • Areas of mathematics
        • Areas of mathematics
        • Math Classification: CCS
        • Math hierarchy
        • Computational mathematics
        • Taxonomy: Mathematics
        • Areas of mathematics
        • Mathematics Subject Classification
        • Math fields
        • math-topics
        • Mathematics Subject Classification – MSC
        • MSC Classification Codes
        • mss-top-levels-filenames
        • MSC classification: Top Levels
        • Math classification
    • 990-appendix
      • Math glossary at ENCYCLOPÆDIA BRITANNICA
      • Bibliography
      • Math: Abbreviations
      • math.GLOSSARY
    • Math : Canon
      • Main branches of mathematics
      • Enumeration: Math paradigms
      • enum-math-symbols
      • List of mathematical theories
      • enum-algebras
        • Group-like algebraic structures
        • Group
        • Groupoid
        • magma
        • Monoid
        • Semigroup
      • enum-axioms-indices
        • 03-variants
        • axioms-relations
        • disjoint-sets
        • ordered-pair
      • enum-axioms
        • Axiom of Extensionality
        • Axioms
          • List of Axioms
          • List of Axioms
          • LINKS
          • Index of axioms
          • Index of axioms
          • List of Axioms
          • List of Axioms in Relations
          • _laws
          • Index of axioms
          • Index of properties
          • Axioms in Boolean Algebra
          • Axioms for the Real Numbers and Integers
          • Axioms for the Real Numbers and Integers
          • ZF Axioms
          • ZFC Axioms
          • Axioms in logic
          • Axioms in set theory
          • List of axioms in set theory
        • Axioms
          • Absorption
          • Annihilation
          • Associativity
          • Cancellation
          • Closure
          • Commutativity
          • Complement laws
          • Distributivity
          • Domination
          • Idempotency
          • identity
          • Invertibility
          • involution
          • Linearity
          • Monotonicity
          • Well-definedness
          • Well-formedness
          • Well-foundedness
          • Well-ordering
      • enum-inference-rules
        • Enumeration: Rules of Inference
        • Enumeration: Rules of Inference for Intuitionistic Natural Deduction
      • Math › Logic formulae
        • Logic formulas concerning functions
        • Logic formulas concerning orders
        • Logic formulas concerning relations
        • Logic formulas concerning sets
      • enum-logic-system-elements
        • Conjecture
      • enum-logic-system-properties
        • Completeness
        • Consistency
        • Decidability
      • enum-topical-hierarchies
        • Outline of category theory
    • Mathematical Lists and Indices
      • Index of algebraic structures
      • Math equations and formulas
      • The fundamental number sets
      • index-of-math-elements
      • Arity
      • List of binary relations
      • Pretty formulae
      • Index of integer sequences
      • List of conjectures
      • Mathematical objects
      • Theorems
      • List of mathematical theories
      • list-of-unsolved-problems
      • Lists of problems in math
      • People
      • list-of-quotes-and-phrases
    • Mathematical elements
      • Mathematical (elements): PAGES
      • Mathematical abstraction
      • Mathematical analysis
      • Mathematical argumentation
      • Mathematical axiom
      • Mathematical concept
      • Mathematical constant
      • Mathematical deduction
      • Mathematical definition
      • Mathematical element
      • Mathematical expression
      • Mathematical formula
      • Mathematical method
      • Mathematical model
      • Mathematical notation
      • Mathematical object
      • Mathematical primitive
      • Mathematical reasoning
      • Mathematical statement
      • Mathematical structure
      • Mathematical symbol
      • Mathematical synthesis
  • debrief-name: math section-code: 800 section-name: misc section-desc: Misc and unclassified mathemat
    • 810-statistics
      • STATISTICS: HIERARCHY
      • STATISTICS: TERMS
      • Statistics › Topics
      • Statistics WIKI LINKS
      • Mathematical Concepts
      • Linear Regression
    • 888-calculus
      • Calculus
      • Math › Calculus › TERMS
Powered by GitBook
On this page
  • History[edit]
  • Description[edit]
  • Examples[edit]
  • Sum of consecutive natural numbers[edit]
  • A trigonometric inequality[edit]
  • Variants[edit]
  • Induction basis other than 0 or 1[edit]
  • Induction on more than one counter[edit]
  • Infinite descent[edit]
  • Prefix induction[edit]
  • Complete (strong) induction[edit]
  • Forward-backward induction[edit]
  • Example of error in the inductive step[edit]
  • Formalization [edit]
  • Transfinite induction[edit]
  • Relationship to the well-ordering principle[edit]
  • See also[edit]
  • Notes[edit]
  • References[edit]
  • Introduction[edit]
  • History[edit]

Was this helpful?

  1. Logic
  2. 380-proof-theory

Mathematical induction

PreviousDirect proofNextMathematical induction

Last updated 3 years ago

Was this helpful?

Mathematical induction

Mathematical induction is a technique. It is essentially used to prove that a statement P(n) holds for every n = 0, 1, 2, 3, . . . ; that is, the overall statement is a sequence of infinitely many cases P(0), P(1), P(2), P(3), . . . . Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder:

Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step).

A proof by induction consists of two cases. The first, the base case (or basis), proves the statement for n = 0 without assuming any knowledge of other cases. The second case, the induction step, proves that if the statement holds for any given case n = k, then it must also hold for the next case n = k + 1. These two steps establish that the statement holds for every natural number n. The base case does not necessarily begin with n = 0, but often with n = 1, and possibly with any fixed natural number n = N, establishing the truth of the statement for all natural numbers n ≥ N.

The method can be extended to prove statements about more general structures, such as ; this generalization, known as , is used in and . Mathematical induction in this extended sense is closely related to . Mathematical induction is an used in , and in some form is the foundation of all .

Although its name may suggest otherwise, mathematical induction should not be confused with as used in (see ). The mathematical method examines infinitely many cases to prove a general statement, but does so by a finite chain of involving the n, which can take infinitely many values.

History[]

In 370 BC, 's may have contained an early example of an implicit inductive proof. An opposite iterated technique, counting down rather than up, is found in the , where it was argued that if 1,000,000 grains of sand formed a heap, and removing one grain from a heap left it a heap, then a single grain of sand (or even no grains) forms a heap.

In India, early implicit proofs by mathematical induction appear in 's "", and in the al-Fakhri written by around 1000 AD, who applied it to to prove the and properties of .

None of these ancient mathematicians, however, explicitly stated the induction hypothesis. Another similar case (contrary to what Vacca has written, as Freudenthal carefully showed) was that of in his Arithmeticorum libri duo (1575), who used the technique to prove that the sum of the first n odd integers is _n_2.

The earliest rigorous use of induction was by (1288–1344). The first explicit formulation of the principle of induction was given by in his Traité du triangle arithmétique (1665). Another Frenchman, , made ample use of a related principle: indirect proof by .

The induction hypothesis was also employed by the Swiss , and from then on it became well known. The modern formal treatment of the principle came only in the 19th century, with , , , , and .

Description[]

The simplest and most common form of mathematical induction infers that a statement involving a n (that is, an integer n ≥ 0 or 1) holds for all values of n. The proof consists of two steps:

  1. The initial or base case: prove that the statement holds for 0, or 1.

  2. The induction step, inductive step, or step case: prove that for every n, if the statement holds for n, then it holds for n + 1. In other words, assume that the statement holds for some arbitrary natural number n, and prove that the statement holds for n + 1.

The hypothesis in the inductive step, that the statement holds for a particular n, is called the induction hypothesis or inductive hypothesis. To prove the inductive step, one assumes the induction hypothesis for n and then uses this assumption to prove that the statement holds for n + 1.

Authors who prefer to define natural numbers to begin at 0 use that value in the base case; those who define natural numbers to begin at 1 use that value.

Mathematical induction can be used to prove the following statement P(n) for all natural numbers n.

Base case: Show that the statement holds for the smallest natural number n = 0.

Inductive step: Show that for any k ≥ 0, if P(k) holds, then P(k+1) also holds.

Assume the induction hypothesis that for a particular k, the single case n = k holds, meaning P(k) is true:

It follows that:

Algebraically, the right hand side simplifies as:

Equating the extreme left hand and right hand sides, we deduce that:

That is, the statement P(_k+_1) also holds true, establishing the inductive step.

If one wishes to prove a statement, not for all natural numbers, but only for all numbers n greater than or equal to a certain number b, then the proof by induction consists of the following:

  1. Showing that the statement holds when n = b.

  2. Showing that if the statement holds for an arbitrary number n ≥ b, then the same statement also holds for n + 1.

This can be used, for example, to show that 2_n_ ≥ n + 5 for n ≥ 3.

Assume an infinite supply of 4- and 5-dollar coins. Induction can be used to prove that any whole amount of dollars greater than or equal to 12 can be formed by a combination of such coins. Let S(k) denote the statement "k dollars can be formed by a combination of 4- and 5-dollar coins". The proof that S(k) is true for all k ≥ 12 can then be achieved by induction on k as follows:

Base case: Showing that S(k) holds for k = 12 is simple: take three 4-dollar coins.

Induction step: Given that S(k) holds for some value of k ≥ 12 (induction hypothesis), prove that S(k + 1) holds, too:

Assume S(k) is true for some arbitrary k ≥ 12. If there is a solution for k dollars that includes at least one 4-dollar coin, replace it by a 5-dollar coin to make k + 1 dollars. Otherwise, if only 5-dollar coins are used, k must be a multiple of 5 and so at least 15; but then we can replace three 5-dollar coins by four 4-dollar coins to make k + 1 dollars. In each case, S(k + 1) is true.

Therefore, by the principle of induction, S(k) holds for all k ≥ 12, and the proof is complete.

The validity of this method can be verified from the usual principle of mathematical induction. Using mathematical induction on the statement P(n) defined as "Q(m) is false for all natural numbers m less than or equal to n", it follows that P(n) holds for all n, which means that Q(n) is false for every natural number n.

The most common form of proof by mathematical induction requires proving in the inductive step that

whereupon the induction principle "automates" n applications of this step in getting from P(0) to P(n). This could be called "predecessor induction" because each step proves something about a number from something about that number's predecessor.

A variant of interest in computational complexity is "prefix induction", in which one proves the following statement in the inductive step:

or equivalently

The induction principle then "automates" log n applications of this inference in getting from P(0) to P(n). In fact, it is called "prefix induction" because each step proves something about a number from something about the "prefix" of that number — as formed by truncating the low bit of its binary representation. It can also be viewed as an application of traditional induction on the length of that binary representation.

If traditional predecessor induction is interpreted computationally as an n-step loop, then prefix induction would correspond to a log-n-step loop. Because of that, proofs using prefix induction are "more feasibly constructive" than proofs using predecessor induction.

One can take the idea a step further: one must prove

Complete induction is most useful when several instances of the inductive hypothesis are required for each inductive step. For example, complete induction can be used to show that

However, there will be slight differences in the structure and the assumptions of the proof, starting with the extended base case:

The base case holds.

In words, the base case P(0) and the inductive step (namely, that the induction hypothesis P(k) implies P(k + 1)) together imply that P(n) for any natural number n. The axiom of induction asserts the validity of inferring that P(n) holds for any natural number n from the base case and the inductive step.

The axiom of structural induction for the natural numbers was first formulated by Peano, who used it to specify the natural numbers together with the following four other axioms:

  1. 0 is a natural number.

  2. The successor function s of every natural number yields a natural number (s(x) = x + 1).

  3. The successor function is injective.

A may be read as a set representing a proposition, and containing natural numbers, for which the proposition holds. This is not an axiom, but a theorem, given that natural numbers are defined in the language of ZFC set theory by axioms, analogous to Peano's.

Applied to a well-founded set, transfinite induction can be formulated as a single step. To prove that a statement P(n) holds for each ordinal number:

  1. Show, for each ordinal number n, that if P(m) holds for all m < n, then P(n) also holds.

Proofs by transfinite induction typically distinguish three cases:

  1. when n is a minimal element, i.e. there is no element smaller than n;

  2. when n has a direct predecessor, i.e. the set of elements which are smaller than n has a largest element;

  • For any natural number n, n + 1 is greater than n.

  • For any natural number n, no natural number is between n and n + 1.

  • No natural number is less than zero.

It can then be proved that induction, given the above-listed axioms, implies the well-ordering principle. The following proof uses complete induction and the first and fourth axioms.

  • Every natural number is either 0 or n + 1 for some natural number n.

  • Fowler, D. (1994). "Could the Greeks Have Used Mathematical Induction? Did They Use It?". Physis. XXXI: 253–265.

  • Unguru, S. (1991). "Greek Mathematics and Mathematical Induction". Physis. XXVIII: 273–289.

  • Unguru, S. (1994). "Fowling after Induction". Physis. XXXI: 267–272.

Examples[]

Sum of consecutive natural numbers[]

{\displaystyle P(n)!:\ \ 0+1+2+\cdots +n,=,{\frac {n(n+1)}{2}}.}

This states a general formula for the sum of the natural numbers less than or equal to a given number; in fact an infinite sequence of statements: , , , etc.

Proposition. For any ,

Proof. Let P(n) be the statement We give a proof by induction on n.

P(0) is clearly true:

{\displaystyle (0+1+2+\cdots +k)+(k{+}1)\ =\ {\frac {k(k{+}1)}{2}}+(k{+}1).}
{\displaystyle {\begin{aligned}{\frac {k(k{+}1)}{2}}+(k{+}1)&\ =\ {\frac {k(k{+}1)+2(k{+}1)}{2}}\&\ =\ {\frac {(k{+}1)(k{+}2)}{2}}\&\ =\ {\frac {(k{+}1)((k{+}1)+1)}{2}}.\end{aligned}}}

Conclusion: Since both the base case and the inductive step have been proved as true, by mathematical induction the statement P(n) holds for every natural number n.

A trigonometric inequality[]

Induction is often used to prove inequalities. As an example, we prove that for any real number and natural number .

At first glance, it may appear that a more general version, for any real numbers , could be proven without induction; but the case shows it may be false for non-integer values of . This suggests we examine the statement specifically for natural values of , and induction is the readiest tool.

Proposition. For any , .

Proof. Fix an arbitrary real number , and let be the statement . We induct on .

Base case: The calculation verifies .

Inductive step: We show the implication for any natural number . Assume the induction hypothesis: for a given value , the single case is true. Using the and the , we deduce:

{\displaystyle {\begin{array}{rcll}|\sin(k{+}1)x|&=&|\sin kx,\cos x+\sin x,\cos kx,|&{\text{(angle addition)}}\&\leq &|!\sin kx,\cos x|+|!\sin x,\cos kx|&{\text{(triangle inequality)}}\&=&|!\sin kx|,|!\cos x|+|!\sin x|,|!\cos kx|&\&\leq &|!\sin kx|+|!\sin x|&(,|!\cos t|\leq 1)\&\leq &k,|!\sin x|+|!\sin x|&{\text{(induction hypothesis}})\&\ =\ &(k{+}1),|!\sin x|.&\end{array}}}

The inequality between the extreme left hand and right-hand quantities shows that is true, which completes the inductive step.

Conclusion: The proposition holds for all natural numbers . ∎

Variants[]

In practice, proofs by induction are often structured differently, depending on the exact nature of the property to be proven. All variants of induction are special cases of transfinite induction; see .

Induction basis other than 0 or 1[]

In this way, one can prove that some statement P(n) holds for all n ≥ 1, or even for all n ≥ −5. This form of mathematical induction is actually a special case of the previous form, because if the statement to be proved is P(n) then proving it with these two rules is equivalent with proving P(n + b) for all natural numbers n with an induction base case 0.

Example: forming dollar amounts by coins[]

In this example, although S(k) also holds for , the above proof cannot be modified to replace the minimum amount of 12 dollar to any lower value m. For m = 11, the base case is actually false; for m = 10, the second case in the induction step (replacing three 5- by four 4-dollar coins) will not work; let alone for even lower m.

Induction on more than one counter[]

It is sometimes desirable to prove a statement involving two natural numbers, n and m, by iterating the induction process. That is, one proves a base case and an inductive step for n, and in each of those proves a base case and an inductive step for m. See, for example, the accompanying . More complicated arguments involving three or more counters are also possible.

Infinite descent[]

The method of infinite descent is a variation of mathematical induction which was used by . It is used to show that some statement Q(n) is false for all natural numbers n. Its traditional form consists of showing that if Q(n) is true for some natural number n, it also holds for some strictly smaller natural number m. Because there are no infinite decreasing sequences of natural numbers, this situation would be impossible, thereby showing (by contradiction) that Q(n) cannot be true for any n.

Prefix induction[]

\forall k(P(k)\to P(k+1))
\forall k(P(k)\to P(2k)\land P(2k+1))
\forall k\left(P\left(\left\lfloor {\frac {k}{2}}\right\rfloor \right)\to P(k)\right)

Predecessor induction can trivially simulate prefix induction on the same statement. Prefix induction can simulate predecessor induction, but only at the cost of making the statement more syntactically complex (adding a bounded ), so the interesting results relating prefix induction to polynomial-time computation depend on excluding unbounded quantifiers entirely, and limiting the alternation of bounded universal and allowed in the statement.

\forall k\left(P\left(\left\lfloor {\sqrt {k}}\right\rfloor \right)\to P(k)\right)

whereupon the induction principle "automates" log log n applications of this inference in getting from P(0) to P(n). This form of induction has been used, analogously, to study log-time parallel computation.[]

Complete (strong) induction[]

Another variant, called complete induction, course of values induction or strong induction (in contrast to which the basic form of induction is sometimes known as weak induction), makes the inductive step easier to prove by using a stronger hypothesis: one proves the statement under the assumption that holds for all natural numbers less than ; by contrast, the basic form only assumes . The name "strong induction" does not mean that this method can prove more than "weak induction", but merely refers to the stronger hypothesis used in the inductive step.

In fact, it can be shown that the two methods are actually equivalent, as explained below. In this form of complete induction, one still has to prove the base case, , and it may even be necessary to prove extra-base cases such as before the general argument applies, as in the example below of the Fibonacci number .

Although the form just described requires one to prove the base case, this is unnecessary if one can prove (assuming for all lower ) for all . This is a special case of as described below, although it is no longer equivalent to ordinary induction. In this form the base case is subsumed by the case , where is proved with no other assumed; this case may need to be handled separately, but sometimes the same argument applies for and , making the proof simpler and more elegant. In this method, however, it is vital to ensure that the proof of does not implicitly assume that , e.g. by saying "choose an arbitrary ", or by assuming that a set of m elements has an element.

Complete induction is equivalent to ordinary mathematical induction as described above, in the sense that a proof by one method can be transformed into a proof by the other. Suppose there is a proof of by complete induction. Let mean " holds for all such that ". Then holds for all if and only if holds for all , and our proof of is easily transformed into a proof of by (ordinary) induction. If, on the other hand, had been proven by ordinary induction, the proof would already effectively be one by complete induction: is proved in the base case, using no assumptions, and is proved in the inductive step, in which one may assume all earlier cases but need only use the case .

Example: Fibonacci numbers[]

F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}

where is the _n_th , (the ) and are the roots of the polynomial . By using the fact that for each , the identity above can be verified by direct calculation for if one assumes that it already holds for both and . To complete the proof, the identity must be verified in the two base cases: and .

Example: prime factorization[]

Another proof by complete induction uses the hypothesis that the statement holds for all smaller more thoroughly. Consider the statement that "every greater than 1 is a product of (one or more) ", which is the "" part of the . For proving the inductive step, the induction hypothesis is that for a given the statement holds for all smaller . If is prime then it is certainly a product of primes, and if not, then by definition it is a product: , where neither of the factors is equal to 1; hence neither is equal to , and so both are greater than 1 and smaller than . The induction hypothesis now applies to and , so each one is a product of primes. Thus is a product of products of primes, and hence by extension a product of primes itself.

Example: dollar amounts revisited[]

We shall look to prove the same example as , this time with strong induction. The statement remains the same:

{\displaystyle S(n):,,n\geq 12\to ,\exists ,a,b\in \mathbb {N} .,,n=4a+5b}

Base case: Show that holds for .

{\displaystyle {\begin{aligned}4\cdot 3+5\cdot 0=12\4\cdot 2+5\cdot 1=13\4\cdot 1+5\cdot 2=14\4\cdot 0+5\cdot 3=15\end{aligned}}}

Induction hypothesis: Given some , assume holds for all with .

Inductive step: Prove that holds.

Choosing , and observing that shows that holds, by inductive hypothesis. That is, the sum can be formed by some combination of and dollar coins. Then, simply adding a dollar coin to that combination yields the sum . That is, holds. Q.E.D.

Forward-backward induction[]

Sometimes, it is more convenient to deduce backwards, proving the statement for , given its validity for . However, proving the validity of the statement for no single number suffices to establish the base case; instead, one needs to prove the statement for an infinite subset of the natural numbers. For example, first used forward (regular) induction to prove the for all powers of 2, and then used backwards induction to show it for all natural numbers.

Example of error in the inductive step[]

The inductive step must be proved for all values of n. To illustrate this, Joel E. Cohen proposed the following argument, which purports to prove by mathematical induction that :

The base case is trivial (as any horse is the same color as itself), and the inductive step is correct in all cases . However, the logic of the inductive step is incorrect for , because of the statement that "the two sets overlap" is false (there are only horses prior to either removal and after removal, the sets of one horse each do not overlap).

Formalization []

In , one can write down the " of induction" as follows:

,

where P(.) is a variable for predicates involving one natural number and k and n are variables for .

The first quantifier in the axiom ranges over predicates rather than over individual numbers. This is a second-order quantifier, which means that this axiom is stated in . Axiomatizing arithmetic induction in requires an containing a separate axiom for each possible predicate. The article contains further discussion of this issue.

0 is not in the of s.

In , quantification over predicates is not allowed, but one can still express induction by quantification over sets:

{\displaystyle \forall A{\Bigl (}0\in A\land \forall k\in \mathbb {N} {\bigl (}k\in A\to (k+1)\in A{\bigr )}\to \mathbb {N} \subseteq A{\Bigr )}}

Transfinite induction[]

One variation of the principle of complete induction can be generalized for statements about elements of any , that is, a set with an < that contains no . Every set representing an is well-founded, the set of natural numbers is one of them.

This form of induction, when applied to a set of ordinal numbers (which form a and hence well-founded class), is called . It is an important proof technique in , and other fields.

when n has no direct predecessor, i.e. n is a so-called .

Strictly speaking, it is not necessary in transfinite induction to prove a base case, because it is a special case of the proposition that if P is true of all n < m, then P is true of m. It is vacuously true precisely because there are no values of n < m that could serve as counterexamples. So the special cases are special cases of the general case.

Relationship to the well-ordering principle[]

The principle of mathematical induction is usually stated as an of the natural numbers; see . It is strictly stronger than the in the context of the other Peano axioms. Suppose the following:

The axiom: For any natural numbers n and m, n is less than or equal to m if and only if m is not less than n.

Proof. Suppose there exists a non-empty set, S, of natural numbers that has no least element. Let P(n) be the assertion that n is not in S. Then P(0) is true, for if it were false then 0 is the least element of S. Furthermore, let n be a natural number, and suppose P(m) is true for all natural numbers m less than n + 1. Then if P(n + 1) is false n + 1 is in S, thus being a minimal element in S, a contradiction. Thus P(n + 1) is true. Therefore, by the complete induction principle, P(n) holds for all natural numbers n; so S is empty, a contradiction.

"" for the set {(0, n): n ∈ ℕ} ∪ {(1, n): n ∈ ℕ}. Numbers refer to the second component of pairs; the first can be obtained from color or location.

On the other hand, the set {(0, n): n ∈ ℕ} ∪ {(1, n): n ∈ ℕ}, shown in the picture, is well-ordered:35lf by the . Moreover, except for the induction axiom, it satisfies all Peano axioms, where Peano's constant 0 is interpreted as the pair (0,0), and Peano's successor function is defined on pairs by succ(x, n) = (x, n + 1) for all _x_∈{0,1} and _n_∈ℕ. As an example for the violation of the induction axiom, define the predicate P(x, n) as (x, n) = (0, 0) or (x, n) = (succ(y, m)) for some _y_∈{0,1} and _m_∈ℕ. Then the base case P(0,0) is trivially true, and so is the step case: if P(x, n), then P(succ(x, n)). However, P is not true for all pairs in the set.

Peano's axioms with the induction principle uniquely model the natural numbers. Replacing the induction principle with the well-ordering principle allows for more exotic models that fulfill all the axioms.

It is mistakenly printed in several books and sources that the well-ordering principle is equivalent to the induction axiom. In the context of the other Peano axioms, this is not the case, but in the context of other axioms, they are equivalent; specifically, the well-ordering principle implies the induction axiom in the context of the first two above listed axioms and

The common mistake in many erroneous proofs is to assume that n − 1 is a unique and well-defined natural number, a property which is not implied by the other Peano axioms.

See also[]

Notes[]

Matt DeVos, ,

Gerardo con Diaz, 2 May 2013 at the ,

. Math Vault. 1 August 2019. Retrieved 23 October 2019.

Anderson, Robert B. (1979). . New York: John Wiley & Sons. p. . .

Suber, Peter. . Earlham College. Retrieved 26 March 2011.

.

.

^ , p. 197: 'The process of reasoning called "Mathematical Induction" has had several independent origins. It has been traced back to the Swiss Jakob (James) Bernoulli, the Frenchman B. Pascal and P. Fermat, and the Italian F. Maurolycus. [...] By reading a little between the lines one can find traces of mathematical induction still earlier, in the writings of the Hindus and the Greeks, as, for instance, in the "cyclic method" of Bhaskara, and in Euclid's proof that the number of primes is infinite.'

, p. 62-84.

"The earliest implicit proof by mathematical induction was given around 1000 in a work by the Persian mathematician Al-Karaji"

, p. 62.

.

.

"It is sometimes required to prove a theorem which shall be true whenever a certain quantity n which it involves shall be an integer or whole number and the method of proof is usually of the following kind. 1st. The theorem is proved to be true when n = 1. 2ndly. It is proved that if the theorem is true when n is a given whole number, it will be true if n is the next greater integer. Hence the theorem is true universally. . .. This species of argument may be termed a continued " (Boole circa 1849 Elementary Treatise on Logic not mathematical pages 40–41 reprinted in and Bornet, Gérard (1997), George Boole: Selected Manuscripts on Logic and its Philosophy, Birkhäuser Verlag, Berlin, )

.

.

Ted Sundstrom, Mathematical Reasoning, p. 190, Pearson, 2006,

Buss, Samuel (1986). Bounded Arithmetic. Naples: Bibliopolis.

. brilliant.org. Retrieved 23 October 2019.

Cauchy, Augustin-Louis (1821). 14 October 2017 at the Paris. The proof of the inequality of arithmetic and geometric means can be found on pages 457ff.

Cohen, Joel E. (1961), "On the nature of mathematical proof", Opus. Reprinted in A Random Walk in Science (R. L. Weber, ed.), Crane, Russak & Co., 1973.

^ Öhman, Lars–Daniel (6 May 2019). . The Mathematical Intelligencer. 41 (3): 33–40. :.

References[]

Introduction[]

; Daoud, A. (2011). . Sydney: Kew Books. . (Ch. 8.)

, , , 2001 [1994]

Hermes, Hans (1973). Introduction to Mathematical Logic. Hochschultext. London: Springer. . .

(1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley. . (Section 1.2.1: Mathematical Induction, pp. 11–21.)

; Fomin, Sergei V. (1975). . Silverman, R. A. (trans., ed.). New York: Dover. . (Section 3.8: Transfinite induction, pp. 28–29.)

History[]

Acerbi, Fabio (August 2000). . . 55 (1): 57–76. :. .

Bussey, W. H. (1917). "The Origin of Mathematical Induction". . 24 (5): 199–207. :. .

(1918). "Origin of the Name "Mathematical Induction"". The American Mathematical Monthly. 25 (5): 197–201. :. .

(1953). "Zur Geschichte der vollständigen Induction". . 6: 17–37.

Hyde, Dominic; Raffman, Diana (2018), Zalta, Edward N. (ed.), , (Summer 2018 ed.), Metaphysics Research Lab, Stanford University, retrieved 23 October 2019

Katz, Victor J. (1998). History of Mathematics: An Introduction. . .

(1881). . . 4 (1–4): 85–95. :. . . Reprinted (CP 3.252-88), (W 4:299-309)

Rabinovitch, Nachum L. (1970). "Rabbi Levi Ben Gershon and the origins of mathematical induction". Archive for History of Exact Sciences. 6 (3): 237–248. :.

Rashed, Roshdi (1972). "L'induction mathématique: al-Karajī, as-Samaw'al". Archive for History of Exact Sciences (in French). 9 (1): 1–21. :.

Rashed, R. (1994), "Mathematical induction: al-Karajī and al-Samawʾal", , Boston Studies in the Philosophy of Science, 156, Springer Science & Business Media,

Shields, Paul (1997). "Peirce's Axiomatization of Arithmetic". In Houser; et al. (eds.). .

Simonson, Charles G. (Winter 2000). (PDF). Bekhol Derakhekha Daehu. Bar-Ilan University Press. 10: 5–21.

Vacca, G. (1909). . . 16 (2): 70–73. :.

Yadegari, Mohammad (1978). "The Use of Mathematical Induction by Abū Kāmil Shujā' Ibn Aslam (850-930)". . 69 (2): 259–262. :. .

mathematical proof
natural number
[3]
well-founded
trees
structural induction
mathematical logic
computer science
recursion
inference rule
formal proofs
correctness proofs for computer programs
[4]
inductive reasoning
philosophy
Problem of induction
deductive reasoning
variable
[5]
edit
Plato
Parmenides
[6]
sorites paradox
[7]
Bhaskara
cyclic method
[8]
al-Karaji
arithmetic sequences
binomial theorem
Pascal's triangle
[9]
[10]
[11]
Francesco Maurolico
Gersonides
[12]
[13]
Pascal
Fermat
infinite descent
Jakob Bernoulli
George Boole
[14]
Augustus de Morgan
Charles Sanders Peirce
[15]
[16]
Giuseppe Peano
Richard Dedekind
[8]
edit
natural number
edit
edit
∎
edit
edit
below
edit
[17]
edit
edit
proof of commutativity
addition of natural numbers
edit
Pierre de Fermat
edit
universal quantifier
existential quantifiers
[18]
citation needed
edit
edit
edit
edit
above
edit
edit
all horses are of the same color
[21]
edit
second-order logic
axiom
natural numbers
second-order logic
first-order logic
axiom schema
Peano axioms
range
first-order
ZFC set theory
edit
well-founded set
irreflexive relation
infinite descending chains
ordinal number
well-ordered
transfinite induction
set theory
topology
limit ordinal
vacuous
edit
axiom
Peano axioms
well-ordering principle
trichotomy
Q.E.D.
Number line
[22]
lexicographic order
[22]
[22]
[22]
[22]
edit
Combinatorial proof
Induction puzzles
Proof by exhaustion
Recursion
Recursion (computer science)
Structural induction
Transfinite induction
edit
^
Mathematical Induction
Simon Fraser University
^
Mathematical Induction
Archived
Wayback Machine
Harvard University
^
"The Definitive Glossary of Higher Mathematical Jargon — Proof by Induction"
^
Proving Programs Correct
1
ISBN
978-0471033950
^
"Mathematical Induction"
^
Acerbi 2000
^
Hyde & Raffman 2018
Jump up to: a
b
Cajori (1918)
^
Rashed 1994
^
Mathematical Knowledge and the Interplay of Practices
^
Rashed 1994
^
Simonson 2000
^
Rabinovitch 1970
^
sorites
Grattan-Guinness, Ivor
ISBN
3-7643-5456-9
^
Peirce 1881
^
Shields 1997
^
ISBN
978-0131877184
^
^
"Forward-Backward Induction | Brilliant Math & Science Wiki"
^
Cours d'analyse de l'École Royale Polytechnique, première partie, Analyse algébrique,
Archived
Wayback Machine
^
Jump up to: a
b
c
d
e
"Are Induction and Well-Ordering Equivalent?"
doi
10.1007/s00283-019-09898-4
edit
edit
Franklin, J.
Proof in Mathematics: An Introduction
ISBN
978-0-646-54509-7
"Mathematical induction"
Encyclopedia of Mathematics
EMS Press
ISBN
978-3540058199
ISSN
1431-4657
Knuth, Donald E.
ISBN
978-0-201-89683-1
Kolmogorov, Andrey N.
Introductory Real Analysis
ISBN
978-0-486-61226-3
edit
"Plato: Parmenides 149a7-c3. A Proof by Complete Induction?"
Archive for History of Exact Sciences
doi
10.1007/s004070000020
JSTOR
41134098
American Mathematical Monthly
doi
10.2307/2974308
JSTOR
2974308
Cajori, Florian
doi
10.2307/2972638
JSTOR
2972638
Freudenthal, Hans
Archives Internationales d'Histoire des Sciences
"Sorites Paradox"
The Stanford Encyclopedia of Philosophy
Addison-Wesley
ISBN
0-321-01618-1
Peirce, Charles Sanders
"On the Logic of Number"
American Journal of Mathematics
doi
10.2307/2369151
JSTOR
2369151
MR
1507856
doi
10.1007/BF00327237
doi
10.1007/BF00348537
The Development of Arabic Mathematics: Between Arithmetic and Algebra
ISBN
9780792325659
Studies in the Logic of Charles S. Peirce
"The Mathematics of Levi ben Gershon, the Ralbag"
"Maurolycus, the First Discoverer of the Principle of Mathematical Induction"
Bulletin of the American Mathematical Society
doi
10.1090/S0002-9904-1909-01860-9
Isis
doi
10.1086/352009
JSTOR
230435
angle addition formula
triangle inequality
transfinite induction
Fibonacci number
golden ratio
natural number
prime numbers
existence
fundamental theorem of arithmetic
Augustin Louis Cauchy
inequality of arithmetic and geometric means
[19]
[20]
{\displaystyle 0={\tfrac {(0)(0+1)}{2}}}
{\displaystyle 0+1+2={\tfrac {(2)(2+1)}{2}}}
{\displaystyle 0+1={\tfrac {(1)(1+1)}{2}}}
n\in \mathbb {N}
{\displaystyle 0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.}
{\displaystyle 0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.}
x
{\displaystyle 0={\tfrac {0(0+1)}{2}},.}
{\displaystyle 0+1+\cdots +k\ =\ {\frac {k(k{+}1)}{2}}.}
{\displaystyle |!\sin nx|\leq n|!\sin x|}
n
n
n
{\displaystyle n,x}
x
{\displaystyle x\in \mathbb {R} ,n\in \mathbb {N} }
{\textstyle n={\frac {1}{2}},,x=\pi }
{\displaystyle 0+1+2+\cdots +k+(k{+}1)\ =\ {\frac {(k{+}1)((k{+}1)+1)}{2}}.}
n
P(n)
P(0)
{\displaystyle |!\sin 0x|=0\leq 0=0,|!\sin x|}
{\displaystyle P(k)\implies P(k{+}1)}
{\displaystyle n=k\geq 0}
k
P(k)
{\displaystyle |!\sin nx|\leq n,|!\sin x|}
{\displaystyle |!\sin nx|\leq n,|!\sin x|}
{\displaystyle |!\sin nx|\leq n,|!\sin x|}
P(n)
n
P(n)
n
{\displaystyle P(m+1)}
P(0)
{\textstyle k\in {4,5,8,9,10}}
m+1
P(m)
{\displaystyle P(k{+}1)}
P(m)
P(n)
n
P(0)
P(n)
P(1)
m=0
{\displaystyle F_{n}}
m=0
m\geq 0
P(m)
P(n)
P(m)
m>0
m>0
n<m
n
{\displaystyle Q(n)}
{\displaystyle Q(n)}
m
{\displaystyle 0\leq m\leq n}
P(n)
n
P(n)
{\displaystyle Q(n)}
P(0)
P(n)
P(n)
F_{n}
{\displaystyle P(n+1)}
x^{2}-x-1
{\textstyle \psi ={{1-{\sqrt {5}}} \over 2}}
{\textstyle \varphi ={{1+{\sqrt {5}}} \over 2}}
{\displaystyle F_{n+2}=F_{n+1}+F_{n}}
{\textstyle F_{n+2}}
{\displaystyle n\in {\mathbb {N}}}
{\textstyle F_{n+1}}
n
m
n=0
{\textstyle F_{n}}
m
n>1
n>1
{\textstyle n=1}
m
m
n_{1}
{\displaystyle m=n_{1}n_{2}}
n_{2}
m
{\displaystyle j>15}
{\displaystyle S(k)}
{\displaystyle k=12,13,14,15}
{\displaystyle S(m)}
{\displaystyle 12\leq m<j}
{\displaystyle S(j)}
{\displaystyle m=j-4}
{\displaystyle S(j-4)}
{\displaystyle 15<j\to 12\leq j-4<j}
{\displaystyle j-4}
4
4
5
n
{\displaystyle S(j)}
n>1
n-1
j
{\displaystyle n+1=2}
n=1
n=1
{\displaystyle \forall P{\Bigl (}P(0)\land \forall k{\bigl (}P(k)\to P(k+1){\bigr )}\to \forall n{\bigl (}P(n){\bigr )}{\Bigr )}}