PA00A5 · theorem

prime_inverse_prefix_extend

Alpha v34 checked-use theorem · independently closed; not Stable

Append one bounded zero-based inverse index to an inverse prefix.

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

∀ p. ∀ n. ∀ b. ∀ c. ∀ l. p = S n → Prime(p) → Lt(l,n) → InversePrefix(p,n,b,c,l) → ∃ x. ∃ y. InversePrefix(p,n,x,y,S l)

Every purple notation token opens its conservative definition. This is a reading surface; the compiler expands the statement before the unchanged kernel checks it.

Definitions used by this theorem

In the theorem statement

PD0002 Lt PD0004 Prime PD0037 InversePrefix

4 occurrences

In local proof propositions

PD0002 Lt PD0013 BetaAt PD0036 InverseIndex

5 occurrences

Exact expanded native-PA statement
forall p n b c l. p = S n -> ((~(p = 1) /\ forall wip_prime_left_extend_prime wip_prime_right_extend_prime. p = wip_prime_left_extend_prime * wip_prime_right_extend_prime -> wip_prime_left_extend_prime = 1 \/ wip_prime_right_extend_prime = 1)) -> (exists wip_gap_extend_length. wip_gap_extend_length + S l = n) -> (forall wip_index_extend_before. (exists wip_gap_extend_before_prefix_bound. wip_gap_extend_before_prefix_bound + S wip_index_extend_before = l) -> exists wip_mate_extend_before. ((((exists wip_beta_height_extend_before_decoded. wip_beta_height_extend_before_decoded + S (wip_mate_extend_before) = S ((S (wip_index_extend_before)) * c)) /\ exists wip_beta_quotient_extend_before_decoded. b = wip_beta_quotient_extend_before_decoded * S ((S (wip_index_extend_before)) * c) + (wip_mate_extend_before))) /\ ((exists wip_gap_extend_before_inverse_index_bound. wip_gap_extend_before_inverse_index_bound + S wip_index_extend_before = n) /\ ((exists wip_gap_extend_before_inverse_mate_bound. wip_gap_extend_before_inverse_mate_bound + S wip_mate_extend_before = n) /\ (exists wip_mod_left_extend_before_inverse_mod wip_mod_right_extend_before_inverse_mod. ((S wip_index_extend_before) * S wip_mate_extend_before) + p * wip_mod_left_extend_before_inverse_mod = 1 + p * wip_mod_right_extend_before_inverse_mod))))) -> exists z d. (forall wip_index_extend_after. (exists wip_gap_extend_after_prefix_bound. wip_gap_extend_after_prefix_bound + S wip_index_extend_after = S l) -> exists wip_mate_extend_after. ((((exists wip_beta_height_extend_after_decoded. wip_beta_height_extend_after_decoded + S (wip_mate_extend_after) = S ((S (wip_index_extend_after)) * d)) /\ exists wip_beta_quotient_extend_after_decoded. z = wip_beta_quotient_extend_after_decoded * S ((S (wip_index_extend_after)) * d) + (wip_mate_extend_after))) /\ ((exists wip_gap_extend_after_inverse_index_bound. wip_gap_extend_after_inverse_index_bound + S wip_index_extend_after = n) /\ ((exists wip_gap_extend_after_inverse_mate_bound. wip_gap_extend_after_inverse_mate_bound + S wip_mate_extend_after = n) /\ (exists wip_mod_left_extend_after_inverse_mod wip_mod_right_extend_after_inverse_mod. ((S wip_index_extend_after) * S wip_mate_extend_after) + p * wip_mod_left_extend_after_inverse_mod = 1 + p * wip_mod_right_extend_after_inverse_mod)))))

Proof neighborhood

Direct theorem prerequisites

PA00A4 prime_inverse_index_exists PA002X beta_prefix_extend PA003D finite_lt_succ_eq_or_lt

Direct theorem dependents

PA00A6 prime_inverse_prefix_exists_bounded

Definition-aware tactic body

Only local propositions introduced by have or suffices are compacted. The untrusted compiler re-expands each one before the original tactic script is replayed; defined notation is never accepted by the kernel. Open the exact replay line beneath every changed command.

Read the argument

Proof checkpoints

59 script commands · 18 reading checkpoints · 4 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 (3)
prime inverse index existsbeta prefix extendfinite lt succ eq or lt
01Fix variables and assumptionsL1–9

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

  1. L1
    intro p
  2. L2
    intro n
  3. L3
    intro b
  4. L4
    intro c
  5. L5
    intro l
  6. L6
    intro hpn
  7. L7
    intro hp
  8. L8
    intro hln
  9. L9
    intro hprefix
02Establish hnewL10–17

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply prime inverse index exists.

  1. L10
    have hnew : ∃ j. InverseIndex(p,n,l,j)Definitions: InverseIndex(p,n,l,j)Original native command in the exact edition
  2. L11
    specialize prime_inverse_index_exists p
  3. L12
    specialize prime_inverse_index_exists n
  4. L13
    specialize prime_inverse_index_exists l
  5. L14
    apply prime_inverse_index_exists
  6. L15
    exact hpn
  7. L16
    exact hp
  8. L17
    exact hln
03Separate the logical casesL18–18

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

  1. L18
    cases hnew
04Use earlier factsL19–22

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

  1. L19
    specialize beta_prefix_extend l
  2. L20
    specialize beta_prefix_extend b
  3. L21
    specialize beta_prefix_extend c
  4. L22
    specialize beta_prefix_extend x
05Separate the logical casesL23–25

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

  1. L23
    cases beta_prefix_extend
  2. L24
    cases beta_prefix_extend_witness
  3. L25
    cases beta_prefix_extend_witness_witness
06Construct an explicit witnessL26–27

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

  1. L26
    exists x1
  2. L27
    exists x2
07Fix variables and assumptionsL28–29

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

  1. L28
    intro i
  2. L29
    intro hi
08Establish hsplitL30–34

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

  1. L30
    have hsplit : i = l ∨ Lt(i,l)Definitions: Lt(i,l)Original native command in the exact edition
  2. L31
    specialize finite_lt_succ_eq_or_lt l
  3. L32
    specialize finite_lt_succ_eq_or_lt i
  4. L33
    apply finite_lt_succ_eq_or_lt
  5. L34
    exact hi
09Separate the logical casesL35–35

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

  1. L35
    cases hsplit
10Construct an explicit witnessL36–36

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

  1. L36
    exists x
11Separate the logical casesL37–37

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

  1. L37
    split
12Calculate and transport equalitiesL38–39

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

  1. L38
    rewrite hsplit_left
  2. L39
    rewrite hsplit_left
13Establish hnew_entryL40–45

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

  1. L40
    have hnew_entry : BetaAt(x1,x2,l,x)Definitions: BetaAt(x1,x2,l,x)Original native command in the exact edition
  2. L41
    exact beta_prefix_extend_witness_witness_left
  3. L42
    exact hnew_entry
  4. L43
    rewrite hsplit_left
  5. L44
    rewrite hsplit_left
  6. L45
    exact hnew_witness
14Establish holdL46–49

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

  1. L46
    have hold : ∃ j. BetaAt(b,c,i,j) ∧ InverseIndex(p,n,i,j)Definitions: BetaAt(b,c,i,j)InverseIndex(p,n,i,j)Original native command in the exact edition
  2. L47
    specialize hprefix i
  3. L48
    apply hprefix
  4. L49
    exact hsplit_right
15Separate the logical casesL50–51

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

  1. L50
    cases hold
  2. L51
    cases hold_witness
16Construct an explicit witnessL52–52

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

  1. L52
    exists x3
17Separate the logical casesL53–53

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

  1. L53
    split
18Use earlier factsL54–59

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

  1. L54
    specialize beta_prefix_extend_witness_witness_right i
  2. L55
    specialize beta_prefix_extend_witness_witness_right x3
  3. L56
    apply beta_prefix_extend_witness_witness_right
  4. L57
    exact hsplit_right
  5. L58
    exact hold_witness_left
  6. L59
    exact hold_witness_right

Library-wide reading audit

Original defined command ledger · 59 lines
  1. 0001intro p
  2. 0002intro n
  3. 0003intro b
  4. 0004intro c
  5. 0005intro l
  6. 0006intro hpn
  7. 0007intro hp
  8. 0008intro hln
  9. 0009intro hprefix
  10. 0010have hnew : ∃ j. InverseIndex(p,n,l,j)
    Exact native replay linehave hnew : exists j. ((exists wip_gap_extend_new_inverse_index_bound. wip_gap_extend_new_inverse_index_bound + S l = n) /\ ((exists wip_gap_extend_new_inverse_mate_bound. wip_gap_extend_new_inverse_mate_bound + S j = n) /\ (exists wip_mod_left_extend_new_inverse_mod wip_mod_right_extend_new_inverse_mod. ((S l) * S j) + p * wip_mod_left_extend_new_inverse_mod = 1 + p * wip_mod_right_extend_new_inverse_mod)))
  11. 0011specialize prime_inverse_index_exists p
  12. 0012specialize prime_inverse_index_exists n
  13. 0013specialize prime_inverse_index_exists l
  14. 0014apply prime_inverse_index_exists
  15. 0015exact hpn
  16. 0016exact hp
  17. 0017exact hln
  18. 0018cases hnew
  19. 0019specialize beta_prefix_extend l
  20. 0020specialize beta_prefix_extend b
  21. 0021specialize beta_prefix_extend c
  22. 0022specialize beta_prefix_extend x
  23. 0023cases beta_prefix_extend
  24. 0024cases beta_prefix_extend_witness
  25. 0025cases beta_prefix_extend_witness_witness
  26. 0026exists x1
  27. 0027exists x2
  28. 0028intro i
  29. 0029intro hi
  30. 0030have hsplit : i = l ∨ Lt(i,l)
    Exact native replay linehave hsplit : i = l \/ exists h. h + S i = l
  31. 0031specialize finite_lt_succ_eq_or_lt l
  32. 0032specialize finite_lt_succ_eq_or_lt i
  33. 0033apply finite_lt_succ_eq_or_lt
  34. 0034exact hi
  35. 0035cases hsplit
  36. 0036exists x
  37. 0037split
  38. 0038rewrite hsplit_left
  39. 0039rewrite hsplit_left
  40. 0040have hnew_entry : BetaAt(x1,x2,l,x)
    Exact native replay linehave hnew_entry : ((exists wip_beta_height_extend_new_entry. wip_beta_height_extend_new_entry + S (x) = S ((S (l)) * x2)) /\ exists wip_beta_quotient_extend_new_entry. x1 = wip_beta_quotient_extend_new_entry * S ((S (l)) * x2) + (x))
  41. 0041exact beta_prefix_extend_witness_witness_left
  42. 0042exact hnew_entry
  43. 0043rewrite hsplit_left
  44. 0044rewrite hsplit_left
  45. 0045exact hnew_witness
  46. 0046have hold : ∃ j. BetaAt(b,c,i,j) ∧ InverseIndex(p,n,i,j)
    Exact native replay linehave hold : exists j. ((((exists wip_beta_height_extend_old_entry. wip_beta_height_extend_old_entry + S (j) = S ((S (i)) * c)) /\ exists wip_beta_quotient_extend_old_entry. b = wip_beta_quotient_extend_old_entry * S ((S (i)) * c) + (j))) /\ ((exists wip_gap_extend_old_inverse_index_bound. wip_gap_extend_old_inverse_index_bound + S i = n) /\ ((exists wip_gap_extend_old_inverse_mate_bound. wip_gap_extend_old_inverse_mate_bound + S j = n) /\ (exists wip_mod_left_extend_old_inverse_mod wip_mod_right_extend_old_inverse_mod. ((S i) * S j) + p * wip_mod_left_extend_old_inverse_mod = 1 + p * wip_mod_right_extend_old_inverse_mod))))
  47. 0047specialize hprefix i
  48. 0048apply hprefix
  49. 0049exact hsplit_right
  50. 0050cases hold
  51. 0051cases hold_witness
  52. 0052exists x3
  53. 0053split
  54. 0054specialize beta_prefix_extend_witness_witness_right i
  55. 0055specialize beta_prefix_extend_witness_witness_right x3
  56. 0056apply beta_prefix_extend_witness_witness_right
  57. 0057exact hsplit_right
  58. 0058exact hold_witness_left
  59. 0059exact hold_witness_right