Addition is cancellative

Depends on

• Addition of natural numbers
• The von Neumann naturals form a Peano system
• The principle of mathematical induction

Used by

• A commutative monoid in which cancellation holds need not be a group: (ℕ, +) Counterexample
• A count that overcounts because the blocks are not disjoint, and exactly where the sum rule's hypothesis is spent Counterexample
• Finite sums and finite products of natural numbers, ∑_k<n aₖ and ∏_k<n aₖ in ℕ Definition
• The factorial n! and the falling factorial n^underlinek, defined by recursion in ℕ Definition
• The multinomial coefficient binomnk₀,…,kₘ₋₁ as the number of ordered partitions of an n-set into blocks of prescribed sizes Definition
• Discreteness: σ(n) is the immediate successor Lemma
• Finite sums re-indexed along an injection, with a zero term deleted, and concatenated; and the closure properties of linear independence: an independent list is injective and never 0_V, its sublists are independent, a list is independent exactly when it is injective with linearly independent image, and every subset of a linearly independent set is linearly independent Lemma
• Laws of finite sums and products in ℕ, and ι(∑_k<n aₖ) = ∑_k<n ι(aₖ) Lemma
• Order is compatible with addition Lemma
• Order is compatible with multiplication Lemma
• The integer-defining relation is an equivalence relation Lemma
• Trichotomy of the order on ℕ Lemma
• ≤ is a linear order on ℕ Theorem
• A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A Theorem
• binomnk k! (n-k)! = n! for k ≤ n; hence binomnk k! = n^underlinek, the quotient n!/(k!(n-k)!) is a natural number, and binomnk = binomnn-k Theorem
• For all m and n there is a list of mn pairwise distinct reals with no strictly increasing sublist of length m+1 and no strictly decreasing sublist of length n+1 Theorem
• For m ≥ 1 the number of weak compositions of n into m parts is binomn+m-1m-1, and the number of compositions is binomn-1m-1 for n ≥ 1 Theorem
• For positive integers a and b and every prime p: vₚ(gcd(a,b)) = min{vₚ(a), vₚ(b)} and vₚ(lcm(a,b)) = max{vₚ(a), vₚ(b)}; so the exponent-wise greatest common divisor is the gcd of the divisibility page and not a second notion Theorem
• Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either Theorem
• Local LYM inequality comparing a uniform family with its upper shadow Theorem
• ℕ × ℕ ≈ ℕ Theorem
• Pascal's rule binomn+1k+1 = binomnk + binomnk+1, and the hockey-stick identity ∑_i ≤ nbinomik = binomn+1k+1 Theorem
• The binomial theorem in ℝ: (x+y)ⁿ = ∑_k<n+1 ιbinomnk xᵏ y^ n-k Theorem
• The multinomial coefficient equals n!/∏_i<m kᵢ!, and (x₀+…+xₘ₋₁)ⁿ = ∑ ιbinomnk∏_i<m xᵢ^kᵢ in ℝ Theorem
• The number of injections from a k-element set into an n-element set is n^underlinek Theorem
• The set A^B of functions B → A between finite sets is finite, with | A^B| = | A|^| B| Theorem
• The Steinitz exchange lemma: if L ⊆ V is linearly independent and S ⊆ V spans V with S finite of size n, then L is finite with |L| = m ≤ n, and there is T ⊆ S of size n - m such that L ∪ T spans V Theorem
• The sum rule: a finite disjoint union is finite with | A ∪ B| = | A| + | B| and |⋃_i ∈ I Aᵢ| = ∑_i ∈ I| Aᵢ|, and a sum over a finite index set splits along a partition Theorem
• Vandermonde's identity binomm+nk = ∑_i<k+1binommibinomnk-i Theorem

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 18 results over 10 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

• T. Tao, Analysis I, 3rd ed., §2.1-2.3 (Peano axioms, recursion, arithmetic) (standard reference, not scraped)
• Peano axioms (Wikipedia) (standard reference, not scraped)
• W. Aitken, MATH 378 Ch. 1: The Peano Axioms (CSU San Marcos) (standard reference, not scraped)