How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced — the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted — a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated — a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
The integers form a totally ordered ring
Statement
The relation of Order on the integers is well defined and is a total order on ; it is compatible with addition ( implies ) and positives are closed under multiplication ( and imply ). Thus is a totally ordered commutative ring.
Facts & Assumptions
Given: Integers , , with the operations of Arithmetic on the integers.
Addition on is commutative and associative (Addition is commutative, Addition is associative).
The order on is total, antisymmetric, and transitive ( is a linear order on ).
Natural order is translation-invariant: (Order is compatible with addition).
By the definition of natural order, exactly when for some natural ; if , such a gap is nonzero (Order on the natural numbers).
Natural multiplication is commutative and associative, distributes over addition, and has the usual zero and identity laws; multiplication by a nonzero natural preserves strict order (Multiplication is commutative, Multiplication is associative, Distributivity and the successor law for multiplication, Zero and one under multiplication, Order is compatible with multiplication).
The integer operations make a commutative ring with multiplicative identity (The integers form a commutative ring).
Proof
Suppose and , i.e. and .
Suppose .
Totality: in either or , so or .
Antisymmetry: and give and , hence , which is as classes.
Transitivity: from and , adding gives ; regrouping, ; cancelling, , i.e. .
Compatibility with addition: reads , which regroups to , equivalent to , i.e. .
Suppose and , i.e. and .
Adding : .
Regrouping with the equations of step 1.1: .
Write and with nonzero naturals .
So ; cancelling gives . Applying the same argument with primed and unprimed representatives exchanged proves the converse implication, so the relation is independent of representatives.
Expanding both components of : and , so .
Since are nonzero, and by [L4]. Hence [L5] gives , and step 3.2 yields , which is .
The order is well defined, total, compatible with addition, and positives are closed under multiplication; together with [L6], this makes a totally ordered commutative ring.
Depends on
- The integers as equivalence classes of pairs of naturals
- Arithmetic on the integers
- Order on the integers
- Order on the natural numbers
- The integers form a commutative ring
- Addition is commutative
- Addition is associative
- $\le$ is a linear order on $\mathbb{N}$
- Order is compatible with addition
- Multiplication is commutative
- Multiplication is associative
- Distributivity and the successor law for multiplication
- Zero and one under multiplication
- Order is compatible with multiplication
Used by
- A rational root of xᵏ = m is an integer: if k ≥ 1, m ∈ ℤ, x ∈ ℚ and xᵏ is the image of m, then x is the image of an integer Corollary
- Division with remainder for any nonzero divisor: for a ∈ ℤ and b ≠ 0 there are unique q, r ∈ ℤ with a = qb + r and 0 ≤ r < |b| Corollary
- Every nonzero integer n is u ∏_i<r pᵢ with u ∈ {1,-1} and every pᵢ prime; u and r are determined by n, and the list is determined up to a permutation Corollary
- For an integer p > 1: p is prime if and only if, for all integers a and b, p ∣ ab implies p ∣ a or p ∣ b Corollary
- If a prime p divides a finite product ∏_i<n aᵢ of integers then p ∣ aᵢ for some i < n; at n = 0 the product is 1 and the hypothesis cannot hold Corollary
- If d = gcd(a,b) is nonzero then a/d and b/d are coprime Corollary
- The extended Euclidean algorithm: the same descent produces integers x, y with ax + by = gcd(a,b), so Bézout coefficients are computed and not merely shown to exist Corollary
- 2ℤ is closed under addition, negation and multiplication and is not a subring of ℤ, because it does not contain 1 Counterexample
- 6 ∣ 4 · 9 while 6 ∤ 4 and 6 ∤ 9: dividing a product does not force dividing a factor, and the coprimality hypothesis is what fails Counterexample
- A nonempty subset of a group closed under the operation need not be a subgroup: the nonnegative integers inside (ℤ, +) Counterexample
- If 1 were admitted as a prime, uniqueness would fail: 6 = 2 · 3 = 1 · 2 · 3 = 1 · 1 · 2 · 3, lists of different lengths that no permutation matches Counterexample
- In the multiplicative monoid H = {1, 4, 7, 10, …} of positive integers one more than a multiple of 3, the element 100 has two genuinely different factorisations into irreducibles, 4 · 25 and 10 · 10 Counterexample
- The common divisors of (0,0) are all of ℤ and have no greatest element in the order of ℤ, so gcd(0,0) cannot be defined as a maximum and is fixed by convention Counterexample
- ℤ and {n + 1/n : n ≥ 2} are disjoint closed subsets of ℝ at distance 0, so the set-to-set distance is not a metric Counterexample
- Common divisor, and the greatest common divisor gcd(a,b), with the convention gcd(0,0) := 0 Definition
- Common multiple, and the least common multiple lcm(a,b), taken to be 0 when a = 0 or b = 0 Definition
- Integer powers aᵐ Definition
- Ordered ring: a ring with a total order compatible with addition and with positives closed under multiplication Definition
- Powers gⁿ: natural exponents in a monoid and integer exponents in a group, with g⁰ = e Definition
- Prime and composite integers: p is prime when p > 1 and its only positive divisors are 1 and p Definition
- The absolute value |a| of an integer Definition
- The divisibility poset of positive integers Definition
- The formal Laurent series ℝ((t⁻¹)): support bounded below, valuation, leading coefficient Definition
- The p-adic valuation vₚ(a) of a nonzero integer: the greatest k ∈ ℕ with pᵏ ∣ a Definition
- (ℤ, +) is an abelian group, (ℤ, ·) is a commutative monoid that is not a group, and its group of units is {1, -1} Example
- 2 is prime, and it is the only even prime: every even integer n > 2 is composite Example
- 360 = 2³ · 3² · 5 and 84 = 2² · 3 · 7, with gcd(360,84) = 12 and lcm(360,84) = 2520 read off the exponents Example
- ax + by = c has an integer solution exactly when gcd(a,b) ∣ c: 6x + 15y = 9 is solvable and 6x + 15y = 7 is not Example
- Consecutive Fibonacci numbers are coprime, and for every m ∈ ℕ the Euclidean algorithm on (Fₘ₊₃, Fₘ₊₂) takes exactly m+1 divisions, with quotient 1 in the first m of them and quotient 2 in the last Example
- Eisenstein proves xⁿ-2 irreducible over ℚ for every positive n Example
- Every positive divisor of the order of a finite cyclic group occurs as the order of a subgroup Example
- For every n ∈ ℕ there are n consecutive composite integers: with N := ∏_j<n(j+2), each of N+2, …, N+n+1 is composite Example
- For n ≥ 1 the congruence classes modulo n form an abelian group (ℤ/n, +) of order n, generated by the class of 1 Example
- gcd(1071, 462) = 21 by the Euclidean algorithm, with the back-substitution giving 21 = 7 · 462 - 3 · 1071 Example
- No rational squares to 3 or to 6, and none cubes to 2: three instances of the rational-root corollary Example
- nℤ is a subgroup of (ℤ, +) for every n ∈ ℤ, and every subgroup of (ℤ, +) has this form Example
- Reduction modulo 2 proves x³+17x+391 irreducible over ℚ Example
- The 2-adic absolute value gives an ultrametric on ℚ, in which every triangle is isosceles and every point of a ball is a centre Example
- The polynomial x²-2 is irreducible over ℚ Example
- The trigonometry-free oscillator ψ(x) = inf_n ∈ ℤ |x - n| is well defined and attained at a nearest integer, takes values in [0, 1/2], vanishes exactly on ℤ, equals 1/2 at half-integers, and is 1-periodic Example
…and 49 more results.
Cited to discharge well-definedness by Order on the integers.
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 36 results over 14 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., §4.1 (standard reference, not scraped)
- Integer — construction from pairs of naturals (Wikipedia) (standard reference, not scraped)