PA00BA · theorem

paired_pair_order_product_one_exists

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

The complete successor-lifted nonendpoint factor product is one modulo p.

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. ∀ u. ∀ v. ∀ b. ∀ c. ∀ m. InversePrefix(p,n,u,v,n) → (∀ x. Lt(x,m + m) → ∃ y. BetaAt(b,c,x,y)Lt(y,n)) → (∀ x. Lt(x,m) → ∃ y. ∃ z. BetaAt(b,c,x + x,y) ∧ (BetaAt(b,c,S (x + x),z)BetaAt(u,v,y,z))) → ∃ x. ∃ y. ∃ z. (∀ k. ∀ i. Lt(k,m + m)BetaAt(b,c,k,i)BetaAt(x,y,k,S i)) ∧ ((∀ k. ∀ i. ∀ j. Lt(k,m)BetaAt(x,y,k + k,i)BetaAt(x,y,S (k + k),j)BalancedInverse(p,i,j)) ∧ (Product(x,y,m + m,z)ModEq(p,z,1)))

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

17 occurrences

In local proof propositions

7 occurrences

Exact expanded native-PA statement
forall p n u v b c m. (forall wip_index_wsl_inverse. (exists wip_gap_wsl_inverse_prefix_bound. wip_gap_wsl_inverse_prefix_bound + S wip_index_wsl_inverse = n) -> exists wip_mate_wsl_inverse. ((((exists wip_beta_height_wsl_inverse_decoded. wip_beta_height_wsl_inverse_decoded + S (wip_mate_wsl_inverse) = S ((S (wip_index_wsl_inverse)) * v)) /\ exists wip_beta_quotient_wsl_inverse_decoded. u = wip_beta_quotient_wsl_inverse_decoded * S ((S (wip_index_wsl_inverse)) * v) + (wip_mate_wsl_inverse))) /\ ((exists wip_gap_wsl_inverse_inverse_index_bound. wip_gap_wsl_inverse_inverse_index_bound + S wip_index_wsl_inverse = n) /\ ((exists wip_gap_wsl_inverse_inverse_mate_bound. wip_gap_wsl_inverse_inverse_mate_bound + S wip_mate_wsl_inverse = n) /\ (exists wip_mod_left_wsl_inverse_inverse_mod wip_mod_right_wsl_inverse_inverse_mod. ((S wip_index_wsl_inverse) * S wip_mate_wsl_inverse) + p * wip_mod_left_wsl_inverse_inverse_mod = 1 + p * wip_mod_right_wsl_inverse_inverse_mod))))) -> (forall fom_index_wsl_bounded. (exists fom_gap_wsl_bounded_index_bound. fom_gap_wsl_bounded_index_bound + S (fom_index_wsl_bounded) = m + m) -> exists fom_value_wsl_bounded. ((((exists fom_beta_height_wsl_bounded_entry. fom_beta_height_wsl_bounded_entry + S (fom_value_wsl_bounded) = S ((S (fom_index_wsl_bounded)) * c)) /\ exists fom_beta_quotient_wsl_bounded_entry. b = fom_beta_quotient_wsl_bounded_entry * S ((S (fom_index_wsl_bounded)) * c) + (fom_value_wsl_bounded))) /\ (exists fom_gap_wsl_bounded_value_bound. fom_gap_wsl_bounded_value_bound + S (fom_value_wsl_bounded) = n))) -> (forall wpop_pair_wsl_pairs. (exists wpo_gap_wsl_pairs_pair_bound. wpo_gap_wsl_pairs_pair_bound + S (wpop_pair_wsl_pairs) = m) -> exists wpop_left_wsl_pairs wpop_right_wsl_pairs. ((((exists wpo_beta_height_wsl_pairs_left_entry. wpo_beta_height_wsl_pairs_left_entry + S (wpop_left_wsl_pairs) = S ((S (wpop_pair_wsl_pairs + wpop_pair_wsl_pairs)) * c)) /\ exists wpo_beta_quotient_wsl_pairs_left_entry. b = wpo_beta_quotient_wsl_pairs_left_entry * S ((S (wpop_pair_wsl_pairs + wpop_pair_wsl_pairs)) * c) + (wpop_left_wsl_pairs))) /\ ((((exists wpo_beta_height_wsl_pairs_right_entry. wpo_beta_height_wsl_pairs_right_entry + S (wpop_right_wsl_pairs) = S ((S (S (wpop_pair_wsl_pairs + wpop_pair_wsl_pairs))) * c)) /\ exists wpo_beta_quotient_wsl_pairs_right_entry. b = wpo_beta_quotient_wsl_pairs_right_entry * S ((S (S (wpop_pair_wsl_pairs + wpop_pair_wsl_pairs))) * c) + (wpop_right_wsl_pairs))) /\ (((exists wpo_beta_height_wsl_pairs_inverse_entry. wpo_beta_height_wsl_pairs_inverse_entry + S (wpop_right_wsl_pairs) = S ((S (wpop_left_wsl_pairs)) * v)) /\ exists wpo_beta_quotient_wsl_pairs_inverse_entry. u = wpo_beta_quotient_wsl_pairs_inverse_entry * S ((S (wpop_left_wsl_pairs)) * v) + (wpop_right_wsl_pairs)))))) -> (exists f g Q. ((forall wsl_index_wsl_lift wsl_value_wsl_lift. (exists wpo_gap_wsl_lift_bound. wpo_gap_wsl_lift_bound + S (wsl_index_wsl_lift) = m + m) -> (((exists wpo_beta_height_wsl_lift_source. wpo_beta_height_wsl_lift_source + S (wsl_value_wsl_lift) = S ((S (wsl_index_wsl_lift)) * c)) /\ exists wpo_beta_quotient_wsl_lift_source. b = wpo_beta_quotient_wsl_lift_source * S ((S (wsl_index_wsl_lift)) * c) + (wsl_value_wsl_lift))) -> (((exists wpo_beta_height_wsl_lift_target. wpo_beta_height_wsl_lift_target + S (S wsl_value_wsl_lift) = S ((S (wsl_index_wsl_lift)) * g)) /\ exists wpo_beta_quotient_wsl_lift_target. f = wpo_beta_quotient_wsl_lift_target * S ((S (wsl_index_wsl_lift)) * g) + (S wsl_value_wsl_lift)))) /\ ((forall wpp_pair_wsl_adjacent wpp_left_wsl_adjacent wpp_right_wsl_adjacent. (exists wpp_gap_wsl_adjacent_pair_bound. wpp_gap_wsl_adjacent_pair_bound + S (wpp_pair_wsl_adjacent) = m) -> (((exists wpp_beta_height_wsl_adjacent_left_entry. wpp_beta_height_wsl_adjacent_left_entry + S (wpp_left_wsl_adjacent) = S ((S ((wpp_pair_wsl_adjacent + wpp_pair_wsl_adjacent))) * g)) /\ exists wpp_beta_quotient_wsl_adjacent_left_entry. f = wpp_beta_quotient_wsl_adjacent_left_entry * S ((S ((wpp_pair_wsl_adjacent + wpp_pair_wsl_adjacent))) * g) + (wpp_left_wsl_adjacent))) -> (((exists wpp_beta_height_wsl_adjacent_right_entry. wpp_beta_height_wsl_adjacent_right_entry + S (wpp_right_wsl_adjacent) = S ((S (S (wpp_pair_wsl_adjacent + wpp_pair_wsl_adjacent))) * g)) /\ exists wpp_beta_quotient_wsl_adjacent_right_entry. f = wpp_beta_quotient_wsl_adjacent_right_entry * S ((S (S (wpp_pair_wsl_adjacent + wpp_pair_wsl_adjacent))) * g) + (wpp_right_wsl_adjacent))) -> (exists wpp_mod_left_wsl_adjacent_pair_mod wpp_mod_right_wsl_adjacent_pair_mod. (wpp_left_wsl_adjacent * wpp_right_wsl_adjacent) + p * wpp_mod_left_wsl_adjacent_pair_mod = (1) + p * wpp_mod_right_wsl_adjacent_pair_mod)) /\ ((exists wpp_trace_code_wsl_product wpp_trace_scale_wsl_product. ((((exists wpp_beta_height_wsl_product_start. wpp_beta_height_wsl_product_start + S (1) = S ((S (0)) * wpp_trace_scale_wsl_product)) /\ exists wpp_beta_quotient_wsl_product_start. wpp_trace_code_wsl_product = wpp_beta_quotient_wsl_product_start * S ((S (0)) * wpp_trace_scale_wsl_product) + (1))) /\ ((((exists wpp_beta_height_wsl_product_terminal. wpp_beta_height_wsl_product_terminal + S (Q) = S ((S (m + m)) * wpp_trace_scale_wsl_product)) /\ exists wpp_beta_quotient_wsl_product_terminal. wpp_trace_code_wsl_product = wpp_beta_quotient_wsl_product_terminal * S ((S (m + m)) * wpp_trace_scale_wsl_product) + (Q))) /\ forall wpp_index_wsl_product. (exists wpp_gap_wsl_product_bound. wpp_gap_wsl_product_bound + S (wpp_index_wsl_product) = m + m) -> exists wpp_factor_wsl_product wpp_prefix_wsl_product wpp_successor_wsl_product. ((((exists wpp_beta_height_wsl_product_factor. wpp_beta_height_wsl_product_factor + S (wpp_factor_wsl_product) = S ((S (wpp_index_wsl_product)) * g)) /\ exists wpp_beta_quotient_wsl_product_factor. f = wpp_beta_quotient_wsl_product_factor * S ((S (wpp_index_wsl_product)) * g) + (wpp_factor_wsl_product))) /\ ((((exists wpp_beta_height_wsl_product_prefix. wpp_beta_height_wsl_product_prefix + S (wpp_prefix_wsl_product) = S ((S (wpp_index_wsl_product)) * wpp_trace_scale_wsl_product)) /\ exists wpp_beta_quotient_wsl_product_prefix. wpp_trace_code_wsl_product = wpp_beta_quotient_wsl_product_prefix * S ((S (wpp_index_wsl_product)) * wpp_trace_scale_wsl_product) + (wpp_prefix_wsl_product))) /\ ((((exists wpp_beta_height_wsl_product_successor. wpp_beta_height_wsl_product_successor + S (wpp_successor_wsl_product) = S ((S (S (wpp_index_wsl_product))) * wpp_trace_scale_wsl_product)) /\ exists wpp_beta_quotient_wsl_product_successor. wpp_trace_code_wsl_product = wpp_beta_quotient_wsl_product_successor * S ((S (S (wpp_index_wsl_product))) * wpp_trace_scale_wsl_product) + (wpp_successor_wsl_product))) /\ wpp_successor_wsl_product = wpp_prefix_wsl_product * wpp_factor_wsl_product)))))) /\ (exists wpp_mod_left_wsl_product_mod_one wpp_mod_right_wsl_product_mod_one. (Q) + p * wpp_mod_left_wsl_product_mod_one = (1) + p * wpp_mod_right_wsl_product_mod_one)))))

Proof neighborhood

Direct theorem prerequisites

Direct theorem dependents

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

52 script commands · 16 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.

Named ingredients (3)
01Fix variables and assumptionsL1–10

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

  1. L1
    intro p
  2. L2
    intro n
  3. L3
    intro u
  4. L4
    intro v
  5. L5
    intro b
  6. L6
    intro c
  7. L7
    intro m
  8. L8
    intro hinverse
  9. L9
    intro hbounded
  10. L10
    intro hpairs
02Establish hfactorsL11–20

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply paired pair order factor code exists.

  1. L11
    have hfactors : ∃ f. ∃ g. (∀ x. ∀ y. Lt(x,m + m) → BetaAt(b,c,x,y) → BetaAt(f,g,x,S y)) ∧ (∀ x. ∀ y. ∀ z. Lt(x,m) → BetaAt(f,g,x + x,y) → BetaAt(f,g,S (x + x),z) → BalancedInverse(p,y,z))Definitions: Lt(x,m + m)BetaAt(b,c,x,y)BetaAt(f,g,x,S y)Lt(x,m)BetaAt(f,g,x + x,y)BetaAt(f,g,S (x + x),z)BalancedInverse(p,y,z)Original native command in the exact edition
  2. L12
    specialize paired_pair_order_factor_code_exists p
  3. L13
    specialize paired_pair_order_factor_code_exists n
  4. L14
    specialize paired_pair_order_factor_code_exists u
  5. L15
    specialize paired_pair_order_factor_code_exists v
  6. L16
    specialize paired_pair_order_factor_code_exists b
  7. L17
    specialize paired_pair_order_factor_code_exists c
  8. L18
    specialize paired_pair_order_factor_code_exists m
  9. L19
    apply paired_pair_order_factor_code_exists
  10. L20
    exact hinverse
03Use earlier factsL21–22

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

  1. L21
    exact hbounded
  2. L22
    exact hpairs
04Separate the logical casesL23–25

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

  1. L23
    cases hfactors
  2. L24
    cases hfactors_witness
  3. L25
    cases hfactors_witness_witness
05Use earlier factsL26–28

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

  1. L26
    specialize beta_product_exists x
  2. L27
    specialize beta_product_exists x1
  3. L28
    specialize beta_product_exists (m + m)
06Separate the logical casesL29–31

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

  1. L29
    cases beta_product_exists
  2. L30
    cases beta_product_exists_witness
  3. L31
    cases beta_product_exists_witness_witness
07Construct an explicit witnessL32–34

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

  1. L32
    exists x
  2. L33
    exists x1
  3. L34
    exists x2
08Separate the logical casesL35–35

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

  1. L35
    split
09Use earlier factsL36–36

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

  1. L36
    exact hfactors_witness_witness_left
10Separate the logical casesL37–37

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

  1. L37
    split
11Use earlier factsL38–38

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

  1. L38
    exact hfactors_witness_witness_right
12Separate the logical casesL39–39

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

  1. L39
    split
13Construct an explicit witnessL40–41

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

  1. L40
    exists x3
  2. L41
    exists x4
14Use earlier factsL42–49

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

  1. L42
    exact beta_product_exists_witness_witness_witness
  2. L43
    specialize beta_adjacent_unit_pairs_product_one p
  3. L44
    specialize beta_adjacent_unit_pairs_product_one x
  4. L45
    specialize beta_adjacent_unit_pairs_product_one x1
  5. L46
    specialize beta_adjacent_unit_pairs_product_one m
  6. L47
    specialize beta_adjacent_unit_pairs_product_one x2
  7. L48
    apply beta_adjacent_unit_pairs_product_one
  8. L49
    exact hfactors_witness_witness_right
15Construct an explicit witnessL50–51

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

  1. L50
    exists x3
  2. L51
    exists x4
16Use earlier factsL52–52

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

  1. L52
    exact beta_product_exists_witness_witness_witness

Library-wide reading audit

Original defined command ledger · 52 lines
  1. 0001intro p
  2. 0002intro n
  3. 0003intro u
  4. 0004intro v
  5. 0005intro b
  6. 0006intro c
  7. 0007intro m
  8. 0008intro hinverse
  9. 0009intro hbounded
  10. 0010intro hpairs
  11. 0011have hfactors : ∃ f. ∃ g. (∀ x. ∀ y. Lt(x,m + m)BetaAt(b,c,x,y)BetaAt(f,g,x,S y)) ∧ (∀ x. ∀ y. ∀ z. Lt(x,m)BetaAt(f,g,x + x,y)BetaAt(f,g,S (x + x),z)BalancedInverse(p,y,z))
    Exact native replay linehave hfactors : exists f g. ((forall wsl_index_wsl_lift wsl_value_wsl_lift. (exists wpo_gap_wsl_lift_bound. wpo_gap_wsl_lift_bound + S (wsl_index_wsl_lift) = m + m) -> (((exists wpo_beta_height_wsl_lift_source. wpo_beta_height_wsl_lift_source + S (wsl_value_wsl_lift) = S ((S (wsl_index_wsl_lift)) * c)) /\ exists wpo_beta_quotient_wsl_lift_source. b = wpo_beta_quotient_wsl_lift_source * S ((S (wsl_index_wsl_lift)) * c) + (wsl_value_wsl_lift))) -> (((exists wpo_beta_height_wsl_lift_target. wpo_beta_height_wsl_lift_target + S (S wsl_value_wsl_lift) = S ((S (wsl_index_wsl_lift)) * g)) /\ exists wpo_beta_quotient_wsl_lift_target. f = wpo_beta_quotient_wsl_lift_target * S ((S (wsl_index_wsl_lift)) * g) + (S wsl_value_wsl_lift)))) /\ (forall wpp_pair_wsl_adjacent wpp_left_wsl_adjacent wpp_right_wsl_adjacent. (exists wpp_gap_wsl_adjacent_pair_bound. wpp_gap_wsl_adjacent_pair_bound + S (wpp_pair_wsl_adjacent) = m) -> (((exists wpp_beta_height_wsl_adjacent_left_entry. wpp_beta_height_wsl_adjacent_left_entry + S (wpp_left_wsl_adjacent) = S ((S ((wpp_pair_wsl_adjacent + wpp_pair_wsl_adjacent))) * g)) /\ exists wpp_beta_quotient_wsl_adjacent_left_entry. f = wpp_beta_quotient_wsl_adjacent_left_entry * S ((S ((wpp_pair_wsl_adjacent + wpp_pair_wsl_adjacent))) * g) + (wpp_left_wsl_adjacent))) -> (((exists wpp_beta_height_wsl_adjacent_right_entry. wpp_beta_height_wsl_adjacent_right_entry + S (wpp_right_wsl_adjacent) = S ((S (S (wpp_pair_wsl_adjacent + wpp_pair_wsl_adjacent))) * g)) /\ exists wpp_beta_quotient_wsl_adjacent_right_entry. f = wpp_beta_quotient_wsl_adjacent_right_entry * S ((S (S (wpp_pair_wsl_adjacent + wpp_pair_wsl_adjacent))) * g) + (wpp_right_wsl_adjacent))) -> (exists wpp_mod_left_wsl_adjacent_pair_mod wpp_mod_right_wsl_adjacent_pair_mod. (wpp_left_wsl_adjacent * wpp_right_wsl_adjacent) + p * wpp_mod_left_wsl_adjacent_pair_mod = (1) + p * wpp_mod_right_wsl_adjacent_pair_mod)))
  12. 0012specialize paired_pair_order_factor_code_exists p
  13. 0013specialize paired_pair_order_factor_code_exists n
  14. 0014specialize paired_pair_order_factor_code_exists u
  15. 0015specialize paired_pair_order_factor_code_exists v
  16. 0016specialize paired_pair_order_factor_code_exists b
  17. 0017specialize paired_pair_order_factor_code_exists c
  18. 0018specialize paired_pair_order_factor_code_exists m
  19. 0019apply paired_pair_order_factor_code_exists
  20. 0020exact hinverse
  21. 0021exact hbounded
  22. 0022exact hpairs
  23. 0023cases hfactors
  24. 0024cases hfactors_witness
  25. 0025cases hfactors_witness_witness
  26. 0026specialize beta_product_exists x
  27. 0027specialize beta_product_exists x1
  28. 0028specialize beta_product_exists (m + m)
  29. 0029cases beta_product_exists
  30. 0030cases beta_product_exists_witness
  31. 0031cases beta_product_exists_witness_witness
  32. 0032exists x
  33. 0033exists x1
  34. 0034exists x2
  35. 0035split
  36. 0036exact hfactors_witness_witness_left
  37. 0037split
  38. 0038exact hfactors_witness_witness_right
  39. 0039split
  40. 0040exists x3
  41. 0041exists x4
  42. 0042exact beta_product_exists_witness_witness_witness
  43. 0043specialize beta_adjacent_unit_pairs_product_one p
  44. 0044specialize beta_adjacent_unit_pairs_product_one x
  45. 0045specialize beta_adjacent_unit_pairs_product_one x1
  46. 0046specialize beta_adjacent_unit_pairs_product_one m
  47. 0047specialize beta_adjacent_unit_pairs_product_one x2
  48. 0048apply beta_adjacent_unit_pairs_product_one
  49. 0049exact hfactors_witness_witness_right
  50. 0050exists x3
  51. 0051exists x4
  52. 0052exact beta_product_exists_witness_witness_witness