Foundation Primitive Recognition Calculus Grow Integer Divisibility Dvd Z Add

Adding what divides

In ordinary arithmetic, divisibility has a simple additive property: if a number divides two other numbers, it divides their sum. For instance, since 3 divides both 6 and 9, it also divides 15. The theorem dvdZ_add establishes the same property in a more abstract setting, where numbers are replaced by objects called signed orbits, which are equivalence classes of signed integers under a balancing relation.

The statement reads: if a divides b and a divides c, then a divides the sum of b and c. Here divisibility, written dvdZ, means there exists some signed orbit c such that a multiplied by c is balanced with b. The proof uses the fact that balanced signed orbits have equal integer representatives, and then applies ordinary integer arithmetic to show the sum property holds. The theorem is checked mechanically in the framework's machine-checked library of formal theorems, with no additional axioms beyond the standard logical ones.

This result is one of several basic properties proved for dvdZ. The library also shows that divisibility is reflexive (every element divides itself) and transitive (if a divides b and b divides c, then a divides c). Together these properties mean dvdZ behaves like the familiar divisibility relation on integers, even though it is defined on the more abstract signed orbits.

What dvdZ_add does not claim is that the sum of two divisors of a number is itself a divisor of that number. That would be false in ordinary arithmetic: 2 and 3 both divide 6, but their sum 5 does not. The theorem only goes in the direction it states, from two separate divisibility facts to a divisibility fact about their sum, and it does not assert any converse or stronger additive closure.

theorem dvdZ_add (a b c : SignedOrbit) (hab : dvdZ a b) (hac : dvdZ a c) :
    dvdZ a (SignedOrbit.add b c) := by
  obtain ⟨w, hw⟩ := hab
  obtain ⟨v, hv⟩ := hac
  refine ⟨SignedOrbit.add w v, balanced_of_toInt_eq ?_⟩
  have hw' := balanced_toInt_eq hw
  have hv' := balanced_toInt_eq hv
  rw [SignedOrbit.mul_toInt] at hw' hv'
  rw [SignedOrbit.mul_toInt, SignedOrbit.add_toInt, SignedOrbit.add_toInt]
  linear_combination hw' + hv'

theorem dvdZ_add (a b c : SignedOrbit) (hab : dvdZ a b) (hac : dvdZ a c) :
    dvdZ a (SignedOrbit.add b c) := by
  obtain ⟨w, hw⟩ := hab
  obtain ⟨v, hv⟩ := hac
  refine ⟨SignedOrbit.add w v, balanced_of_toInt_eq ?_⟩
  have hw' := balanced_toInt_eq hw
  have hv' := balanced_toInt_eq hv
  rw [SignedOrbit.mul_toInt] at hw' hv'
  rw [SignedOrbit.mul_toInt, SignedOrbit.add_toInt, SignedOrbit.add_toInt]
  linear_combination hw' + hv'

theorem dvdZ_refl (a : SignedOrbit) : dvdZ a a := by
  refine ⟨SignedOrbit.one, balanced_of_toInt_eq ?_⟩
  rw [SignedOrbit.mul_toInt, SignedOrbit.one_toInt]
  omega

theorem dvdZ_trans (a b c : SignedOrbit) (hab : dvdZ a b) (hbc : dvdZ b c) : dvdZ a c := by
  obtain ⟨w, hw⟩ := hab
  obtain ⟨v, hv⟩ := hbc
  refine ⟨SignedOrbit.mul w v, balanced_of_toInt_eq ?_⟩
  have hw' := balanced_toInt_eq hw
  have hv' := balanced_toInt_eq hv
  rw [SignedOrbit.mul_toInt] at hw' hv'
  rw [SignedOrbit.mul_toInt, SignedOrbit.mul_toInt]
  linear_combination v.toInt * hw' + hv'

What this page does not claim

The theorem does not claim that the sum of two divisors of a number is itself a divisor of that number. The theorem does not claim any converse direction, such as that divisibility of a sum implies divisibility of either summand. The theorem does not assert that signed orbits are the same as ordinary integers, only that this divisibility property carries over.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Foundation/PrimitiveRecognitionCalculus/Grow/IntegerDivisibility.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: