Addition is cancellative

Depends on

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

Used by

• (n+1) Cₙ=C(2n, n) Corollary
• 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
• Counting-measure tails decrease to the empty set while every term has infinite measure 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^k̲, defined by recursion in ℕ Definition
• The multinomial coefficient C(n, k₀,…,kₘ₋₁) as the number of ordered partitions of an n-set into blocks of prescribed sizes Definition
• FALSE: continuity from above needs no finiteness hypothesis False statement
• 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
• C(n, k) k! (n-k)! = n! for k ≤ n; hence C(n, k) k! = n^k̲, the quotient n!/(k!(n-k)!) is a natural number, and C(n, k) = C(n, n-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 C(n+m-1, m-1), and the number of compositions is C(n-1, m-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 C(n+1, k+1) = C(n, k) + C(n, k+1), and the hockey-stick identity ∑_i ≤ nC(i, k) = C(n+1, k+1) Theorem
• The binomial theorem in ℝ: (x+y)ⁿ = ∑_k<n+1 iotaC(n, k) xᵏ y^ n-k Theorem
• The multinomial coefficient equals n!/∏_i<m kᵢ!, and (x₀+…+xₘ₋₁)ⁿ = ∑ iotaC(n, k)∏_i<m xᵢ^kᵢ in ℝ Theorem
• The number of injections from a k-element set into an n-element set is n^k̲ 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 C(m+n, k) = ∑_i<k+1C(m, i)C(n, k-i) Theorem

Dependency tree · two levels

10 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on 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)