BT00SG · Bertrand theorem

division_remainder_successor_cases

Alpha v34 checked-use theorem · independently kernel and Lean verified; not Stable

Successor division has exactly the carry and no-carry quotient cases.

Current library: Alpha v34, 4,223 checked-use theorems; Stable remains 432. Historical first admissions, original proof editions, and non-admitted aliases are preserved. Exact original first-admission records.

Statement with defined notation

∀ d. ∀ n. ∀ q. ∀ r. ∀ z. ∀ s. DivRem(n,d,q,r) → DivRem(S n,d,z,s) → S r = d ∧ (z = S q ∧ s = 0) ∨ Lt(S r,d) ∧ (z = q ∧ s = S r)

Every purple notation token opens its conservative definition. Expanding the displayed statement recovers the exact first-order Peano-arithmetic formula checked by the unchanged kernel.

Definitions used by this theorem

In the theorem statement

PD0002 Lt PD0007 DivRem

3 occurrences

In local proof propositions

PD0002 Lt

2 occurrences

Exact expanded native-PA statement
forall d n q r z s. (((n) = (d) * (q) + (r) /\ exists blsr_lt_gap_successor_cases_old_bound. blsr_lt_gap_successor_cases_old_bound + S (r) = (d))) -> (((S n) = (d) * (z) + (s) /\ exists blsr_lt_gap_successor_cases_new_bound. blsr_lt_gap_successor_cases_new_bound + S (s) = (d))) -> ((S r = d /\ (z = S q /\ s = 0)) \/ ((exists blsr_lt_gap_successor_cases_no_carry. blsr_lt_gap_successor_cases_no_carry + S (S r) = (d)) /\ (z = q /\ s = S r)))

Proof neighborhood

Direct theorem prerequisites

BT001C le_eq_or_lt BT001U division_remainder_unique

Direct theorem dependents

BT00SH division_successor_quotient_by_bit

Definition-aware tactic body

Only local propositions introduced by have or suffices are compacted. Every changed line has an exact-AST conservative-expansion receipt; the kernel still receives the immutable original tactic script.

Read the argument

Proof checkpoints

70 script commands · 18 reading checkpoints · 6 local claims

This is a reading aid, not a new proof or a proof-tree certificate. Checkpoint groups are consecutive commands, not inferred branch boundaries. Every step links to the preserved script.

Definition notation is shown below. Open the paired exact edition for the original native formulas. Source pairing is not a new equivalence certificate.

Named ingredients (2)
le eq or ltdivision remainder unique
01Fix variables and assumptionsL1–8

Work with arbitrary variables or the premises of the current implication.

  1. L1
    intro d
  2. L2
    intro n
  3. L3
    intro q
  4. L4
    intro r
  5. L5
    intro z
  6. L6
    intro s
  7. L7
    intro hold
  8. L8
    intro hnew
02Separate the logical casesL9–10

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L9
    cases hold
  2. L10
    cases hnew
03Establish hsplitL11–15

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply le eq or lt.

  1. L11
    have hsplit : S r = d ∨ Lt(S r,d)Definitions: Lt(S r,d)Original native command in the exact edition
  2. L12
    specialize le_eq_or_lt (S r)
  3. L13
    specialize le_eq_or_lt d
  4. L14
    apply le_eq_or_lt
  5. L15
    exact hold_right
04Separate the logical casesL16–18

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L16
    cases hsplit
  2. L17
    left
  3. L18
    split
05Use earlier factsL19–19

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L19
    exact hsplit_left
06Establish hequationL20–29

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply PA4.

  1. L20
    have hequation : S n = d * S q + 0
  2. L21
    trans S (d * q + r)
  3. L22
    congr
  4. L23
    exact hold_left
  5. L24
    trans d * q + S r
  6. L25
    symm
  7. L26
    apply PA4
  8. L27
    rewrite hsplit_left
  9. L28
    rewrite PA3
  10. L29
    symm
07Use earlier factsL30–30

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L30
    apply PA6
08Establish hboundL31–31

Establish this local claim before using it. It is not an additional assumption.

  1. L31
    have hbound : Lt(0,d)Definitions: Lt(0,d)Original native command in the exact edition
09Construct an explicit witnessL32–32

Supply the displayed value, then prove that it has the required property.

  1. L32
    exists r
10Calculate and transport equalitiesL33–34

Carry out the recorded arithmetic or equality steps; inspect the exact commands for their direction and premises.

  1. L33
    rewrite PA4
  2. L34
    rewrite PA3
11Use earlier factsL35–35

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L35
    exact hsplit_left
12Establish huniqueL36–45

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply division remainder unique.

  1. L36
    have hunique : z = S q /\ s = 0
  2. L37
    specialize division_remainder_unique d
  3. L38
    specialize division_remainder_unique (S n)
  4. L39
    specialize division_remainder_unique z
  5. L40
    specialize division_remainder_unique s
  6. L41
    specialize division_remainder_unique (S q)
  7. L42
    specialize division_remainder_unique 0
  8. L43
    apply division_remainder_unique
  9. L44
    exact hnew_left
  10. L45
    exact hnew_right
13Use earlier factsL46–48

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L46
    exact hequation
  2. L47
    exact hbound
  3. L48
    exact hunique
14Separate the logical casesL49–50

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L49
    right
  2. L50
    split
15Use earlier factsL51–51

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L51
    exact hsplit_right
16Establish hequationL52–57

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply PA4.

  1. L52
    have hequation : S n = d * q + S r
  2. L53
    trans S (d * q + r)
  3. L54
    congr
  4. L55
    exact hold_left
  5. L56
    symm
  6. L57
    apply PA4
17Establish huniqueL58–67

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply division remainder unique.

  1. L58
    have hunique : z = q /\ s = S r
  2. L59
    specialize division_remainder_unique d
  3. L60
    specialize division_remainder_unique (S n)
  4. L61
    specialize division_remainder_unique z
  5. L62
    specialize division_remainder_unique s
  6. L63
    specialize division_remainder_unique q
  7. L64
    specialize division_remainder_unique (S r)
  8. L65
    apply division_remainder_unique
  9. L66
    exact hnew_left
  10. L67
    exact hnew_right
18Use earlier factsL68–70

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L68
    exact hequation
  2. L69
    exact hsplit_right
  3. L70
    exact hunique

Library-wide reading audit

Original defined command ledger · 70 lines
  1. 0001intro d
  2. 0002intro n
  3. 0003intro q
  4. 0004intro r
  5. 0005intro z
  6. 0006intro s
  7. 0007intro hold
  8. 0008intro hnew
  9. 0009cases hold
  10. 0010cases hnew
  11. 0011have hsplit : S r = d ∨ Lt(S r,d)
    Exact native replay linehave hsplit : S r = d \/ exists blsr_lt_gap_successor_cases_no_carry. blsr_lt_gap_successor_cases_no_carry + S (S r) = (d)
  12. 0012specialize le_eq_or_lt (S r)
  13. 0013specialize le_eq_or_lt d
  14. 0014apply le_eq_or_lt
  15. 0015exact hold_right
  16. 0016cases hsplit
  17. 0017left
  18. 0018split
  19. 0019exact hsplit_left
  20. 0020have hequation : S n = d * S q + 0
  21. 0021trans S (d * q + r)
  22. 0022congr
  23. 0023exact hold_left
  24. 0024trans d * q + S r
  25. 0025symm
  26. 0026apply PA4
  27. 0027rewrite hsplit_left
  28. 0028rewrite PA3
  29. 0029symm
  30. 0030apply PA6
  31. 0031have hbound : Lt(0,d)
    Exact native replay linehave hbound : exists blsr_lt_gap_successor_cases_carry_zero. blsr_lt_gap_successor_cases_carry_zero + S (0) = (d)
  32. 0032exists r
  33. 0033rewrite PA4
  34. 0034rewrite PA3
  35. 0035exact hsplit_left
  36. 0036have hunique : z = S q /\ s = 0
  37. 0037specialize division_remainder_unique d
  38. 0038specialize division_remainder_unique (S n)
  39. 0039specialize division_remainder_unique z
  40. 0040specialize division_remainder_unique s
  41. 0041specialize division_remainder_unique (S q)
  42. 0042specialize division_remainder_unique 0
  43. 0043apply division_remainder_unique
  44. 0044exact hnew_left
  45. 0045exact hnew_right
  46. 0046exact hequation
  47. 0047exact hbound
  48. 0048exact hunique
  49. 0049right
  50. 0050split
  51. 0051exact hsplit_right
  52. 0052have hequation : S n = d * q + S r
  53. 0053trans S (d * q + r)
  54. 0054congr
  55. 0055exact hold_left
  56. 0056symm
  57. 0057apply PA4
  58. 0058have hunique : z = q /\ s = S r
  59. 0059specialize division_remainder_unique d
  60. 0060specialize division_remainder_unique (S n)
  61. 0061specialize division_remainder_unique z
  62. 0062specialize division_remainder_unique s
  63. 0063specialize division_remainder_unique q
  64. 0064specialize division_remainder_unique (S r)
  65. 0065apply division_remainder_unique
  66. 0066exact hnew_left
  67. 0067exact hnew_right
  68. 0068exact hequation
  69. 0069exact hsplit_right
  70. 0070exact hunique