PA00A1

scaled_pair_order_successor_lift_product_is_factorial

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

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

Exact expanded 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

Structural proof guide

Generated structural guide

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

Use the direct prerequisites beta_at_unique, beta_range_entry_eq, beta_product_permutation_invariant, add_succ_left, zero_add as previously established PA formulas.

The proof proceeds by case analysis (5), intermediate claims (8), equality transport (5), certified simplification (1).

Referenced ingredients

Proof neighborhood

Direct dependencies

Direct dependents

Formal native tactic body

Dependencies are introduced as named hypotheses before line 1. Linked names are exact direct references. This Alpha-v16 checked-use theorem is independently kernel-checked when replayed; it is not a Stable theorem.

  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 : 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 : 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 : 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 : ((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