MV0010

mobius_squarefree_fresh_prime_product

Adjoining an actual prime not dividing a squarefree input preserves squarefreeness; Euclid cancellation excludes every possible squared prime divisor.

Alpha v34 checked-use · first admitted v31 · independently kernel and Lean verified; not Stable

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

Mobius(n,z) is positive-domain only, independently defined from squarefreeness and actual prime-factor parity. Signed codes 0, 2 and 1 represent zero, +1 and -1. This family proves values and prime-adjunction laws; the separate Möbius-inversion family supplies the complete G007 endpoint.

Exact theorem in conservative defined notation

∀ p. ∀ n. Prime(p) → Squarefree(n) → ¬Dvd(p,n) → Squarefree(p · n)

Every linked abbreviation expands hygienically to the identical original native formula.

Definition DAG

Squarefree(n) · 2Dvd(d,n) · 1Prime(p) · 1

Actual proof prerequisites

prime_nonzero · checked external prerequisitemul_ne_zero · checked external prerequisiteeq_decidable · checked external prerequisitemul_left_cancel_nonzero · checked external prerequisitemul_assoc · checked external prerequisitesquarefree_excludes_prime_square · checked external prerequisitegauss_coprime_cancel · checked external prerequisitecoprime_mul_left · checked external prerequisitedistinct_primes_coprime · checked external prerequisite
Original expanded first-order statement 
forall p n. (~((p) = 1) /\ forall pvs_left_fresh_prime pvs_right_fresh_prime. (p) = pvs_left_fresh_prime * pvs_right_fresh_prime -> pvs_left_fresh_prime = 1 \/ pvs_right_fresh_prime = 1) -> (((~((n) = 0)) /\ (forall sfd_prime_fresh_squarefree. (~((sfd_prime_fresh_squarefree) = 1) /\ forall pvs_left_fresh_squarefreedomain pvs_right_fresh_squarefreedomain. (sfd_prime_fresh_squarefree) = pvs_left_fresh_squarefreedomain * pvs_right_fresh_squarefreedomain -> pvs_left_fresh_squarefreedomain = 1 \/ pvs_right_fresh_squarefreedomain = 1) -> (exists pvs_le_gap_fresh_squarefreebound. pvs_le_gap_fresh_squarefreebound + (sfd_prime_fresh_squarefree) = (n)) -> ~(exists pvs_factor_fresh_squarefreesquare. (n) = (sfd_prime_fresh_squarefree * sfd_prime_fresh_squarefree) * pvs_factor_fresh_squarefreesquare)))) -> ~(exists pvs_factor_fresh_nondivisor. (n) = (p) * pvs_factor_fresh_nondivisor) -> (((~((p * n) = 0)) /\ (forall sfd_prime_fresh_product. (~((sfd_prime_fresh_product) = 1) /\ forall pvs_left_fresh_productdomain pvs_right_fresh_productdomain. (sfd_prime_fresh_product) = pvs_left_fresh_productdomain * pvs_right_fresh_productdomain -> pvs_left_fresh_productdomain = 1 \/ pvs_right_fresh_productdomain = 1) -> (exists pvs_le_gap_fresh_productbound. pvs_le_gap_fresh_productbound + (sfd_prime_fresh_product) = (p * n)) -> ~(exists pvs_factor_fresh_productsquare. (p * n) = (sfd_prime_fresh_product * sfd_prime_fresh_product) * pvs_factor_fresh_productsquare))))

Complete tactic proof in conservative notation

All 70 original proof lines are preserved. Only local proposition formulas are abbreviated; every abbreviation has an exact binder-safe expansion check. The linked exact edition contains the unchanged replay script.

Read the argument

Proof checkpoints

70 script commands · 20 reading checkpoints · 1 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.

01Fix variables and assumptionsL1–5

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

  1. L1
    intro p
  2. L2
    intro n
  3. L3
    intro hp
  4. L4
    intro hsf
  5. L5
    intro hfresh
02Separate the logical casesL6–7

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

  1. L6
    cases hsf
  2. L7
    split
03Fix variables and assumptionsL8–8

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

  1. L8
    intro hz
04Use earlier factsL9–11

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

  1. L9
    specialize mul_ne_zero (p)
  2. L10
    specialize mul_ne_zero (n)
  3. L11
    apply mul_ne_zero
05Fix variables and assumptionsL12–12

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

  1. L12
    intro hpz
06Use earlier factsL13–18

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

  1. L13
    specialize prime_nonzero (p)
  2. L14
    apply prime_nonzero
  3. L15
    exact hp
  4. L16
    exact hpz
  5. L17
    exact hsf_left
  6. L18
    exact hz
07Fix variables and assumptionsL19–22

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

  1. L19
    intro q
  2. L20
    intro hq
  3. L21
    intro hbound
  4. L22
    intro hdiv
08Establish heqL23–26

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

  1. L23
    have heq : q = p \/ ~(q = p)
  2. L24
    specialize eq_decidable (q)
  3. L25
    specialize eq_decidable (p)
  4. L26
    apply eq_decidable
09Separate the logical casesL27–27

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

  1. L27
    cases heq
10Use earlier factsL28–28

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

  1. L28
    apply hfresh
11Calculate and transport equalitiesL29–30

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

  1. L29
    rewrite heq_left at hdiv
  2. L30
    rewrite heq_left at hdiv
12Separate the logical casesL31–31

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

  1. L31
    cases hdiv
13Construct an explicit witnessL32–32

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

  1. L32
    exists x
14Use earlier factsL33–36

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

  1. L33
    specialize mul_left_cancel_nonzero (p)
  2. L34
    specialize mul_left_cancel_nonzero (n)
  3. L35
    specialize mul_left_cancel_nonzero (p * x)
  4. L36
    apply mul_left_cancel_nonzero
15Fix variables and assumptionsL37–37

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

  1. L37
    intro hz
16Use earlier factsL38–41

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

  1. L38
    specialize prime_nonzero (p)
  2. L39
    apply prime_nonzero
  3. L40
    exact hp
  4. L41
    exact hz
17Calculate and transport equalitiesL42–42

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

  1. L42
    trans (p * p) * x
18Use earlier factsL43–52

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

  1. L43
    exact hdiv_witness
  2. L44
    apply mul_assoc
  3. L45
    specialize squarefree_excludes_prime_square (n)
  4. L46
    specialize squarefree_excludes_prime_square (q)
  5. L47
    apply squarefree_excludes_prime_square
  6. L48
    exact hsf
  7. L49
    exact hq
  8. L50
    specialize gauss_coprime_cancel (q * q)
  9. L51
    specialize gauss_coprime_cancel (p)
  10. L52
    specialize gauss_coprime_cancel (n)
19Use earlier factsL53–62

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

  1. L53
    apply gauss_coprime_cancel
  2. L54
    specialize coprime_mul_left (q)
  3. L55
    specialize coprime_mul_left (q)
  4. L56
    specialize coprime_mul_left (p)
  5. L57
    apply coprime_mul_left
  6. L58
    specialize distinct_primes_coprime (q)
  7. L59
    specialize distinct_primes_coprime (p)
  8. L60
    apply distinct_primes_coprime
  9. L61
    exact hq
  10. L62
    exact hp
20Use earlier factsL63–70

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

  1. L63
    exact heq_right
  2. L64
    specialize distinct_primes_coprime (q)
  3. L65
    specialize distinct_primes_coprime (p)
  4. L66
    apply distinct_primes_coprime
  5. L67
    exact hq
  6. L68
    exact hp
  7. L69
    exact heq_right
  8. L70
    exact hdiv

Library-wide reading audit

Original defined command ledger · 70 lines
  1. 0001intro p
  2. 0002intro n
  3. 0003intro hp
  4. 0004intro hsf
  5. 0005intro hfresh
  6. 0006cases hsf
  7. 0007split
  8. 0008intro hz
  9. 0009specialize mul_ne_zero (p)
  10. 0010specialize mul_ne_zero (n)
  11. 0011apply mul_ne_zero
  12. 0012intro hpz
  13. 0013specialize prime_nonzero (p)
  14. 0014apply prime_nonzero
  15. 0015exact hp
  16. 0016exact hpz
  17. 0017exact hsf_left
  18. 0018exact hz
  19. 0019intro q
  20. 0020intro hq
  21. 0021intro hbound
  22. 0022intro hdiv
  23. 0023have heq : q = p \/ ~(q = p)
  24. 0024specialize eq_decidable (q)
  25. 0025specialize eq_decidable (p)
  26. 0026apply eq_decidable
  27. 0027cases heq
  28. 0028apply hfresh
  29. 0029rewrite heq_left at hdiv
  30. 0030rewrite heq_left at hdiv
  31. 0031cases hdiv
  32. 0032exists x
  33. 0033specialize mul_left_cancel_nonzero (p)
  34. 0034specialize mul_left_cancel_nonzero (n)
  35. 0035specialize mul_left_cancel_nonzero (p * x)
  36. 0036apply mul_left_cancel_nonzero
  37. 0037intro hz
  38. 0038specialize prime_nonzero (p)
  39. 0039apply prime_nonzero
  40. 0040exact hp
  41. 0041exact hz
  42. 0042trans (p * p) * x
  43. 0043exact hdiv_witness
  44. 0044apply mul_assoc
  45. 0045specialize squarefree_excludes_prime_square (n)
  46. 0046specialize squarefree_excludes_prime_square (q)
  47. 0047apply squarefree_excludes_prime_square
  48. 0048exact hsf
  49. 0049exact hq
  50. 0050specialize gauss_coprime_cancel (q * q)
  51. 0051specialize gauss_coprime_cancel (p)
  52. 0052specialize gauss_coprime_cancel (n)
  53. 0053apply gauss_coprime_cancel
  54. 0054specialize coprime_mul_left (q)
  55. 0055specialize coprime_mul_left (q)
  56. 0056specialize coprime_mul_left (p)
  57. 0057apply coprime_mul_left
  58. 0058specialize distinct_primes_coprime (q)
  59. 0059specialize distinct_primes_coprime (p)
  60. 0060apply distinct_primes_coprime
  61. 0061exact hq
  62. 0062exact hp
  63. 0063exact heq_right
  64. 0064specialize distinct_primes_coprime (q)
  65. 0065specialize distinct_primes_coprime (p)
  66. 0066apply distinct_primes_coprime
  67. 0067exact hq
  68. 0068exact hp
  69. 0069exact heq_right
  70. 0070exact hdiv