PA00A1 · theorem

scaled_pair_order_successor_lift_product_is_factorial

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

A bounded injective order and its successor lift multiply to n factorial.

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

∀ b. ∀ c. ∀ f. ∀ g. ∀ n. ∀ Q. ∀ F. BoundedPrefix(b,c,n)InjectivePrefix(b,c,n) → (∀ x. ∀ y. Lt(x,n)BetaAt(b,c,x,y)BetaAt(f,g,x,S y)) → Product(f,g,n,Q)Factorial(n,F) → Q = F

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

7 occurrences

In local proof propositions

8 occurrences

Exact expanded native-PA statement
forall b c f g n Q F. (forall fom_index_enr_generic_bounded. (exists fom_gap_enr_generic_bounded_index_bound. fom_gap_enr_generic_bounded_index_bound + S (fom_index_enr_generic_bounded) = n) -> exists fom_value_enr_generic_bounded. ((((exists fom_beta_height_enr_generic_bounded_entry. fom_beta_height_enr_generic_bounded_entry + S (fom_value_enr_generic_bounded) = S ((S (fom_index_enr_generic_bounded)) * c)) /\ exists fom_beta_quotient_enr_generic_bounded_entry. b = fom_beta_quotient_enr_generic_bounded_entry * S ((S (fom_index_enr_generic_bounded)) * c) + (fom_value_enr_generic_bounded))) /\ (exists fom_gap_enr_generic_bounded_value_bound. fom_gap_enr_generic_bounded_value_bound + S (fom_value_enr_generic_bounded) = n))) -> (forall wpo_injective_left_enr_generic_injective wpo_injective_right_enr_generic_injective wpo_injective_value_enr_generic_injective. (exists wpo_gap_enr_generic_injective_left_bound. wpo_gap_enr_generic_injective_left_bound + S (wpo_injective_left_enr_generic_injective) = n) -> (exists wpo_gap_enr_generic_injective_right_bound. wpo_gap_enr_generic_injective_right_bound + S (wpo_injective_right_enr_generic_injective) = n) -> (((exists wpo_beta_height_enr_generic_injective_left_entry. wpo_beta_height_enr_generic_injective_left_entry + S (wpo_injective_value_enr_generic_injective) = S ((S (wpo_injective_left_enr_generic_injective)) * c)) /\ exists wpo_beta_quotient_enr_generic_injective_left_entry. b = wpo_beta_quotient_enr_generic_injective_left_entry * S ((S (wpo_injective_left_enr_generic_injective)) * c) + (wpo_injective_value_enr_generic_injective))) -> (((exists wpo_beta_height_enr_generic_injective_right_entry. wpo_beta_height_enr_generic_injective_right_entry + S (wpo_injective_value_enr_generic_injective) = S ((S (wpo_injective_right_enr_generic_injective)) * c)) /\ exists wpo_beta_quotient_enr_generic_injective_right_entry. b = wpo_beta_quotient_enr_generic_injective_right_entry * S ((S (wpo_injective_right_enr_generic_injective)) * c) + (wpo_injective_value_enr_generic_injective))) -> wpo_injective_left_enr_generic_injective = wpo_injective_right_enr_generic_injective) -> (forall wsl_index_enr_generic_lift wsl_value_enr_generic_lift. (exists wpo_gap_enr_generic_lift_bound. wpo_gap_enr_generic_lift_bound + S (wsl_index_enr_generic_lift) = n) -> (((exists wpo_beta_height_enr_generic_lift_source. wpo_beta_height_enr_generic_lift_source + S (wsl_value_enr_generic_lift) = S ((S (wsl_index_enr_generic_lift)) * c)) /\ exists wpo_beta_quotient_enr_generic_lift_source. b = wpo_beta_quotient_enr_generic_lift_source * S ((S (wsl_index_enr_generic_lift)) * c) + (wsl_value_enr_generic_lift))) -> (((exists wpo_beta_height_enr_generic_lift_target. wpo_beta_height_enr_generic_lift_target + S (S wsl_value_enr_generic_lift) = S ((S (wsl_index_enr_generic_lift)) * g)) /\ exists wpo_beta_quotient_enr_generic_lift_target. f = wpo_beta_quotient_enr_generic_lift_target * S ((S (wsl_index_enr_generic_lift)) * g) + (S wsl_value_enr_generic_lift)))) -> (exists ff_u_enr_lifted_product ff_v_enr_lifted_product. ((((exists ff_h_enr_lifted_product_start. ff_h_enr_lifted_product_start + S (1) = S ((S (0)) * ff_v_enr_lifted_product)) /\ exists ff_q_enr_lifted_product_start. ff_u_enr_lifted_product = ff_q_enr_lifted_product_start * S ((S (0)) * ff_v_enr_lifted_product) + (1))) /\ ((((exists ff_h_enr_lifted_product_terminal. ff_h_enr_lifted_product_terminal + S (Q) = S ((S (n)) * ff_v_enr_lifted_product)) /\ exists ff_q_enr_lifted_product_terminal. ff_u_enr_lifted_product = ff_q_enr_lifted_product_terminal * S ((S (n)) * ff_v_enr_lifted_product) + (Q))) /\ forall ff_i_enr_lifted_product. (exists ff_lt_enr_lifted_product_bound. ff_lt_enr_lifted_product_bound + S ff_i_enr_lifted_product = n) -> exists ff_p_enr_lifted_product ff_r_enr_lifted_product ff_s_enr_lifted_product. ((((exists ff_h_enr_lifted_product_factor. ff_h_enr_lifted_product_factor + S (ff_p_enr_lifted_product) = S ((S (ff_i_enr_lifted_product)) * g)) /\ exists ff_q_enr_lifted_product_factor. f = ff_q_enr_lifted_product_factor * S ((S (ff_i_enr_lifted_product)) * g) + (ff_p_enr_lifted_product))) /\ ((((exists ff_h_enr_lifted_product_partial. ff_h_enr_lifted_product_partial + S (ff_r_enr_lifted_product) = S ((S (ff_i_enr_lifted_product)) * ff_v_enr_lifted_product)) /\ exists ff_q_enr_lifted_product_partial. ff_u_enr_lifted_product = ff_q_enr_lifted_product_partial * S ((S (ff_i_enr_lifted_product)) * ff_v_enr_lifted_product) + (ff_r_enr_lifted_product))) /\ ((((exists ff_h_enr_lifted_product_successor. ff_h_enr_lifted_product_successor + S (ff_s_enr_lifted_product) = S ((S (S ff_i_enr_lifted_product)) * ff_v_enr_lifted_product)) /\ exists ff_q_enr_lifted_product_successor. ff_u_enr_lifted_product = ff_q_enr_lifted_product_successor * S ((S (S ff_i_enr_lifted_product)) * ff_v_enr_lifted_product) + (ff_s_enr_lifted_product))) /\ ff_s_enr_lifted_product = ff_r_enr_lifted_product * ff_p_enr_lifted_product)))))) -> (exists ff_b_enr_factorial ff_c_enr_factorial. ((forall ff_i_enr_factorial_range. (exists ff_lt_enr_factorial_range_bound. ff_lt_enr_factorial_range_bound + S ff_i_enr_factorial_range = n) -> (((exists ff_h_enr_factorial_range_decoded. ff_h_enr_factorial_range_decoded + S (1 + ff_i_enr_factorial_range) = S ((S (ff_i_enr_factorial_range)) * ff_c_enr_factorial)) /\ exists ff_q_enr_factorial_range_decoded. ff_b_enr_factorial = ff_q_enr_factorial_range_decoded * S ((S (ff_i_enr_factorial_range)) * ff_c_enr_factorial) + (1 + ff_i_enr_factorial_range)))) /\ (exists ff_u_enr_factorial_product ff_v_enr_factorial_product. ((((exists ff_h_enr_factorial_product_start. ff_h_enr_factorial_product_start + S (1) = S ((S (0)) * ff_v_enr_factorial_product)) /\ exists ff_q_enr_factorial_product_start. ff_u_enr_factorial_product = ff_q_enr_factorial_product_start * S ((S (0)) * ff_v_enr_factorial_product) + (1))) /\ ((((exists ff_h_enr_factorial_product_terminal. ff_h_enr_factorial_product_terminal + S (F) = S ((S (n)) * ff_v_enr_factorial_product)) /\ exists ff_q_enr_factorial_product_terminal. ff_u_enr_factorial_product = ff_q_enr_factorial_product_terminal * S ((S (n)) * ff_v_enr_factorial_product) + (F))) /\ forall ff_i_enr_factorial_product. (exists ff_lt_enr_factorial_product_bound. ff_lt_enr_factorial_product_bound + S ff_i_enr_factorial_product = n) -> exists ff_p_enr_factorial_product ff_r_enr_factorial_product ff_s_enr_factorial_product. ((((exists ff_h_enr_factorial_product_factor. ff_h_enr_factorial_product_factor + S (ff_p_enr_factorial_product) = S ((S (ff_i_enr_factorial_product)) * ff_c_enr_factorial)) /\ exists ff_q_enr_factorial_product_factor. ff_b_enr_factorial = ff_q_enr_factorial_product_factor * S ((S (ff_i_enr_factorial_product)) * ff_c_enr_factorial) + (ff_p_enr_factorial_product))) /\ ((((exists ff_h_enr_factorial_product_partial. ff_h_enr_factorial_product_partial + S (ff_r_enr_factorial_product) = S ((S (ff_i_enr_factorial_product)) * ff_v_enr_factorial_product)) /\ exists ff_q_enr_factorial_product_partial. ff_u_enr_factorial_product = ff_q_enr_factorial_product_partial * S ((S (ff_i_enr_factorial_product)) * ff_v_enr_factorial_product) + (ff_r_enr_factorial_product))) /\ ((((exists ff_h_enr_factorial_product_successor. ff_h_enr_factorial_product_successor + S (ff_s_enr_factorial_product) = S ((S (S ff_i_enr_factorial_product)) * ff_v_enr_factorial_product)) /\ exists ff_q_enr_factorial_product_successor. ff_u_enr_factorial_product = ff_q_enr_factorial_product_successor * S ((S (S ff_i_enr_factorial_product)) * ff_v_enr_factorial_product) + (ff_s_enr_factorial_product))) /\ ff_s_enr_factorial_product = ff_r_enr_factorial_product * ff_p_enr_factorial_product)))))))) -> Q = F

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

82 script commands · 16 reading checkpoints · 8 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 b
  2. L2
    intro c
  3. L3
    intro f
  4. L4
    intro g
  5. L5
    intro n
  6. L6
    intro Q
  7. L7
    intro F
  8. L8
    intro hbounded
  9. L9
    intro hinjective
  10. L10
    intro hlift
02Fix variables and assumptionsL11–12

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

  1. L11
    intro hproduct
  2. L12
    intro hfactorial
03Separate the logical casesL13–15

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

  1. L13
    cases hfactorial
  2. L14
    cases hfactorial_witness
  3. L15
    cases hfactorial_witness_witness
04Establish halignedL16–22

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

  1. L16
    have haligned : ∀ fpr_i_enr_alignment_x. ∀ fpr_j_enr_alignment_x. ∀ fpr_x_enr_alignment_x. Lt(fpr_i_enr_alignment_x,n) → BetaAt(b,c,fpr_i_enr_alignment_x,fpr_j_enr_alignment_x) → BetaAt(x,x1,fpr_j_enr_alignment_x,fpr_x_enr_alignment_x) → BetaAt(f,g,fpr_i_enr_alignment_x,fpr_x_enr_alignment_x)Definitions: Lt(fpr_i_enr_alignment_x,n)BetaAt(b,c,fpr_i_enr_alignment_x,fpr_j_enr_alignment_x)BetaAt(x,x1,fpr_j_enr_alignment_x,fpr_x_enr_alignment_x)BetaAt(f,g,fpr_i_enr_alignment_x,fpr_x_enr_alignment_x)Original native command in the exact edition
  2. L17
    intro i
  3. L18
    intro j
  4. L19
    intro y
  5. L20
    intro hi
  6. L21
    intro hmap
  7. L22
    intro hsource
05Establish hbounded_dataL23–26

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

  1. L23
    have hbounded_data : ∃ w. BetaAt(b,c,i,w) ∧ Lt(w,n)Definitions: BetaAt(b,c,i,w)Lt(w,n)Original native command in the exact edition
  2. L24
    specialize hbounded i
  3. L25
    apply hbounded
  4. L26
    exact hi
06Separate the logical casesL27–28

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

  1. L27
    cases hbounded_data
  2. L28
    cases hbounded_data_witness
07Establish hj_eqL29–37

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

  1. L29
    have hj_eq : j = x2
  2. L30
    specialize beta_at_unique b
  3. L31
    specialize beta_at_unique c
  4. L32
    specialize beta_at_unique i
  5. L33
    specialize beta_at_unique j
  6. L34
    specialize beta_at_unique x2
  7. L35
    apply beta_at_unique
  8. L36
    exact hmap
  9. L37
    exact hbounded_data_witness_left
08Establish hj_boundL38–40

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

  1. L38
    have hj_bound : Lt(j,n)Definitions: Lt(j,n)Original native command in the exact edition
  2. L39
    rewrite hj_eq
  3. L40
    exact hbounded_data_witness_right
09Establish hy_eqL41–50

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

  1. L41
    have hy_eq : y = 1 + j
  2. L42
    specialize beta_range_entry_eq x
  3. L43
    specialize beta_range_entry_eq x1
  4. L44
    specialize beta_range_entry_eq 1
  5. L45
    specialize beta_range_entry_eq n
  6. L46
    specialize beta_range_entry_eq j
  7. L47
    specialize beta_range_entry_eq y
  8. L48
    apply beta_range_entry_eq
  9. L49
    exact hfactorial_witness_witness_left
  10. L50
    exact hj_bound
10Use earlier factsL51–51

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

  1. L51
    exact hsource
11Establish hliftedL52–57

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

  1. L52
    have hlifted : BetaAt(f,g,i,S j)Definitions: BetaAt(f,g,i,S j)Original native command in the exact edition
  2. L53
    specialize hlift i
  3. L54
    specialize hlift j
  4. L55
    apply hlift
  5. L56
    exact hi
  6. L57
    exact hmap
12Establish honeL58–64

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

  1. L58
    have hone : 1 + j = S j
  2. L59
    simp [add_succ_left, zero_add]
  3. L60
    rewrite hy_eq
  4. L61
    rewrite hy_eq
  5. L62
    rewrite hone
  6. L63
    rewrite hone
  7. L64
    exact hlifted
13Establish hfactorial_eqL65–74

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

  1. L65
    have hfactorial_eq : F = Q
  2. L66
    specialize beta_product_permutation_invariant n
  3. L67
    specialize beta_product_permutation_invariant b
  4. L68
    specialize beta_product_permutation_invariant c
  5. L69
    specialize beta_product_permutation_invariant x
  6. L70
    specialize beta_product_permutation_invariant x1
  7. L71
    specialize beta_product_permutation_invariant f
  8. L72
    specialize beta_product_permutation_invariant g
  9. L73
    specialize beta_product_permutation_invariant F
  10. L74
    specialize beta_product_permutation_invariant Q
14Use earlier factsL75–80

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

  1. L75
    apply beta_product_permutation_invariant
  2. L76
    exact hbounded
  3. L77
    exact hinjective
  4. L78
    exact haligned
  5. L79
    exact hfactorial_witness_witness_right
  6. L80
    exact hproduct
15Calculate and transport equalitiesL81–81

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

  1. L81
    symm
16Use earlier factsL82–82

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

  1. L82
    exact hfactorial_eq

Library-wide reading audit

Original defined command ledger · 82 lines
  1. 0001intro b
  2. 0002intro c
  3. 0003intro f
  4. 0004intro g
  5. 0005intro n
  6. 0006intro Q
  7. 0007intro F
  8. 0008intro hbounded
  9. 0009intro hinjective
  10. 0010intro hlift
  11. 0011intro hproduct
  12. 0012intro hfactorial
  13. 0013cases hfactorial
  14. 0014cases hfactorial_witness
  15. 0015cases hfactorial_witness_witness
  16. 0016have haligned : ∀ fpr_i_enr_alignment_x. ∀ fpr_j_enr_alignment_x. ∀ fpr_x_enr_alignment_x. Lt(fpr_i_enr_alignment_x,n)BetaAt(b,c,fpr_i_enr_alignment_x,fpr_j_enr_alignment_x)BetaAt(x,x1,fpr_j_enr_alignment_x,fpr_x_enr_alignment_x)BetaAt(f,g,fpr_i_enr_alignment_x,fpr_x_enr_alignment_x)
    Exact native replay linehave haligned : forall fpr_i_enr_alignment_x fpr_j_enr_alignment_x fpr_x_enr_alignment_x. (exists fpr_h_enr_alignment_x. fpr_h_enr_alignment_x + S fpr_i_enr_alignment_x = n) -> (((exists ff_h_enr_alignment_x_map. ff_h_enr_alignment_x_map + S (fpr_j_enr_alignment_x) = S ((S (fpr_i_enr_alignment_x)) * c)) /\ exists ff_q_enr_alignment_x_map. b = ff_q_enr_alignment_x_map * S ((S (fpr_i_enr_alignment_x)) * c) + (fpr_j_enr_alignment_x))) -> (((exists ff_h_enr_alignment_x_source. ff_h_enr_alignment_x_source + S (fpr_x_enr_alignment_x) = S ((S (fpr_j_enr_alignment_x)) * x1)) /\ exists ff_q_enr_alignment_x_source. x = ff_q_enr_alignment_x_source * S ((S (fpr_j_enr_alignment_x)) * x1) + (fpr_x_enr_alignment_x))) -> (((exists ff_h_enr_alignment_x_target. ff_h_enr_alignment_x_target + S (fpr_x_enr_alignment_x) = S ((S (fpr_i_enr_alignment_x)) * g)) /\ exists ff_q_enr_alignment_x_target. f = ff_q_enr_alignment_x_target * S ((S (fpr_i_enr_alignment_x)) * g) + (fpr_x_enr_alignment_x)))
  17. 0017intro i
  18. 0018intro j
  19. 0019intro y
  20. 0020intro hi
  21. 0021intro hmap
  22. 0022intro hsource
  23. 0023have hbounded_data : ∃ w. BetaAt(b,c,i,w)Lt(w,n)
    Exact native replay linehave hbounded_data : exists w. (((exists ff_h_enr_generic_bounded_entry. ff_h_enr_generic_bounded_entry + S (w) = S ((S (i)) * c)) /\ exists ff_q_enr_generic_bounded_entry. b = ff_q_enr_generic_bounded_entry * S ((S (i)) * c) + (w))) /\ (exists wpo_gap_enr_generic_bounded_value. wpo_gap_enr_generic_bounded_value + S (w) = n)
  24. 0024specialize hbounded i
  25. 0025apply hbounded
  26. 0026exact hi
  27. 0027cases hbounded_data
  28. 0028cases hbounded_data_witness
  29. 0029have hj_eq : j = x2
  30. 0030specialize beta_at_unique b
  31. 0031specialize beta_at_unique c
  32. 0032specialize beta_at_unique i
  33. 0033specialize beta_at_unique j
  34. 0034specialize beta_at_unique x2
  35. 0035apply beta_at_unique
  36. 0036exact hmap
  37. 0037exact hbounded_data_witness_left
  38. 0038have hj_bound : Lt(j,n)
    Exact native replay linehave hj_bound : exists gap. gap + S j = n
  39. 0039rewrite hj_eq
  40. 0040exact hbounded_data_witness_right
  41. 0041have hy_eq : y = 1 + j
  42. 0042specialize beta_range_entry_eq x
  43. 0043specialize beta_range_entry_eq x1
  44. 0044specialize beta_range_entry_eq 1
  45. 0045specialize beta_range_entry_eq n
  46. 0046specialize beta_range_entry_eq j
  47. 0047specialize beta_range_entry_eq y
  48. 0048apply beta_range_entry_eq
  49. 0049exact hfactorial_witness_witness_left
  50. 0050exact hj_bound
  51. 0051exact hsource
  52. 0052have hlifted : BetaAt(f,g,i,S j)
    Exact native replay linehave hlifted : ((exists ff_h_enr_generic_lifted_at_i. ff_h_enr_generic_lifted_at_i + S (S j) = S ((S (i)) * g)) /\ exists ff_q_enr_generic_lifted_at_i. f = ff_q_enr_generic_lifted_at_i * S ((S (i)) * g) + (S j))
  53. 0053specialize hlift i
  54. 0054specialize hlift j
  55. 0055apply hlift
  56. 0056exact hi
  57. 0057exact hmap
  58. 0058have hone : 1 + j = S j
  59. 0059simp [add_succ_left, zero_add]
  60. 0060rewrite hy_eq
  61. 0061rewrite hy_eq
  62. 0062rewrite hone
  63. 0063rewrite hone
  64. 0064exact hlifted
  65. 0065have hfactorial_eq : F = Q
  66. 0066specialize beta_product_permutation_invariant n
  67. 0067specialize beta_product_permutation_invariant b
  68. 0068specialize beta_product_permutation_invariant c
  69. 0069specialize beta_product_permutation_invariant x
  70. 0070specialize beta_product_permutation_invariant x1
  71. 0071specialize beta_product_permutation_invariant f
  72. 0072specialize beta_product_permutation_invariant g
  73. 0073specialize beta_product_permutation_invariant F
  74. 0074specialize beta_product_permutation_invariant Q
  75. 0075apply beta_product_permutation_invariant
  76. 0076exact hbounded
  77. 0077exact hinjective
  78. 0078exact haligned
  79. 0079exact hfactorial_witness_witness_right
  80. 0080exact hproduct
  81. 0081symm
  82. 0082exact hfactorial_eq