PA005Y

pow_mul_exp

Stable checked-use theorem · independently closed

Iterated relational powers multiply their exponents.

Exact expanded PA statement

forall a e f p x y z. p = e * f -> (exists ff_b_mul_base ff_c_mul_base. ((forall ff_i_mul_base_repeat. (exists ff_lt_mul_base_repeat_bound. ff_lt_mul_base_repeat_bound + S ff_i_mul_base_repeat = e) -> (((exists ff_h_mul_base_repeat_decoded. ff_h_mul_base_repeat_decoded + S (a) = S ((S (ff_i_mul_base_repeat)) * ff_c_mul_base)) /\ exists ff_q_mul_base_repeat_decoded. ff_b_mul_base = ff_q_mul_base_repeat_decoded * S ((S (ff_i_mul_base_repeat)) * ff_c_mul_base) + (a)))) /\ (exists ff_u_mul_base_product ff_v_mul_base_product. ((((exists ff_h_mul_base_product_start. ff_h_mul_base_product_start + S (1) = S ((S (0)) * ff_v_mul_base_product)) /\ exists ff_q_mul_base_product_start. ff_u_mul_base_product = ff_q_mul_base_product_start * S ((S (0)) * ff_v_mul_base_product) + (1))) /\ ((((exists ff_h_mul_base_product_terminal. ff_h_mul_base_product_terminal + S (x) = S ((S (e)) * ff_v_mul_base_product)) /\ exists ff_q_mul_base_product_terminal. ff_u_mul_base_product = ff_q_mul_base_product_terminal * S ((S (e)) * ff_v_mul_base_product) + (x))) /\ forall ff_i_mul_base_product. (exists ff_lt_mul_base_product_bound. ff_lt_mul_base_product_bound + S ff_i_mul_base_product = e) -> exists ff_p_mul_base_product ff_r_mul_base_product ff_s_mul_base_product. ((((exists ff_h_mul_base_product_factor. ff_h_mul_base_product_factor + S (ff_p_mul_base_product) = S ((S (ff_i_mul_base_product)) * ff_c_mul_base)) /\ exists ff_q_mul_base_product_factor. ff_b_mul_base = ff_q_mul_base_product_factor * S ((S (ff_i_mul_base_product)) * ff_c_mul_base) + (ff_p_mul_base_product))) /\ ((((exists ff_h_mul_base_product_partial. ff_h_mul_base_product_partial + S (ff_r_mul_base_product) = S ((S (ff_i_mul_base_product)) * ff_v_mul_base_product)) /\ exists ff_q_mul_base_product_partial. ff_u_mul_base_product = ff_q_mul_base_product_partial * S ((S (ff_i_mul_base_product)) * ff_v_mul_base_product) + (ff_r_mul_base_product))) /\ ((((exists ff_h_mul_base_product_successor. ff_h_mul_base_product_successor + S (ff_s_mul_base_product) = S ((S (S ff_i_mul_base_product)) * ff_v_mul_base_product)) /\ exists ff_q_mul_base_product_successor. ff_u_mul_base_product = ff_q_mul_base_product_successor * S ((S (S ff_i_mul_base_product)) * ff_v_mul_base_product) + (ff_s_mul_base_product))) /\ ff_s_mul_base_product = ff_r_mul_base_product * ff_p_mul_base_product)))))))) -> (exists ff_b_mul_outer ff_c_mul_outer. ((forall ff_i_mul_outer_repeat. (exists ff_lt_mul_outer_repeat_bound. ff_lt_mul_outer_repeat_bound + S ff_i_mul_outer_repeat = f) -> (((exists ff_h_mul_outer_repeat_decoded. ff_h_mul_outer_repeat_decoded + S (x) = S ((S (ff_i_mul_outer_repeat)) * ff_c_mul_outer)) /\ exists ff_q_mul_outer_repeat_decoded. ff_b_mul_outer = ff_q_mul_outer_repeat_decoded * S ((S (ff_i_mul_outer_repeat)) * ff_c_mul_outer) + (x)))) /\ (exists ff_u_mul_outer_product ff_v_mul_outer_product. ((((exists ff_h_mul_outer_product_start. ff_h_mul_outer_product_start + S (1) = S ((S (0)) * ff_v_mul_outer_product)) /\ exists ff_q_mul_outer_product_start. ff_u_mul_outer_product = ff_q_mul_outer_product_start * S ((S (0)) * ff_v_mul_outer_product) + (1))) /\ ((((exists ff_h_mul_outer_product_terminal. ff_h_mul_outer_product_terminal + S (y) = S ((S (f)) * ff_v_mul_outer_product)) /\ exists ff_q_mul_outer_product_terminal. ff_u_mul_outer_product = ff_q_mul_outer_product_terminal * S ((S (f)) * ff_v_mul_outer_product) + (y))) /\ forall ff_i_mul_outer_product. (exists ff_lt_mul_outer_product_bound. ff_lt_mul_outer_product_bound + S ff_i_mul_outer_product = f) -> exists ff_p_mul_outer_product ff_r_mul_outer_product ff_s_mul_outer_product. ((((exists ff_h_mul_outer_product_factor. ff_h_mul_outer_product_factor + S (ff_p_mul_outer_product) = S ((S (ff_i_mul_outer_product)) * ff_c_mul_outer)) /\ exists ff_q_mul_outer_product_factor. ff_b_mul_outer = ff_q_mul_outer_product_factor * S ((S (ff_i_mul_outer_product)) * ff_c_mul_outer) + (ff_p_mul_outer_product))) /\ ((((exists ff_h_mul_outer_product_partial. ff_h_mul_outer_product_partial + S (ff_r_mul_outer_product) = S ((S (ff_i_mul_outer_product)) * ff_v_mul_outer_product)) /\ exists ff_q_mul_outer_product_partial. ff_u_mul_outer_product = ff_q_mul_outer_product_partial * S ((S (ff_i_mul_outer_product)) * ff_v_mul_outer_product) + (ff_r_mul_outer_product))) /\ ((((exists ff_h_mul_outer_product_successor. ff_h_mul_outer_product_successor + S (ff_s_mul_outer_product) = S ((S (S ff_i_mul_outer_product)) * ff_v_mul_outer_product)) /\ exists ff_q_mul_outer_product_successor. ff_u_mul_outer_product = ff_q_mul_outer_product_successor * S ((S (S ff_i_mul_outer_product)) * ff_v_mul_outer_product) + (ff_s_mul_outer_product))) /\ ff_s_mul_outer_product = ff_r_mul_outer_product * ff_p_mul_outer_product)))))))) -> (exists ff_b_mul_total ff_c_mul_total. ((forall ff_i_mul_total_repeat. (exists ff_lt_mul_total_repeat_bound. ff_lt_mul_total_repeat_bound + S ff_i_mul_total_repeat = p) -> (((exists ff_h_mul_total_repeat_decoded. ff_h_mul_total_repeat_decoded + S (a) = S ((S (ff_i_mul_total_repeat)) * ff_c_mul_total)) /\ exists ff_q_mul_total_repeat_decoded. ff_b_mul_total = ff_q_mul_total_repeat_decoded * S ((S (ff_i_mul_total_repeat)) * ff_c_mul_total) + (a)))) /\ (exists ff_u_mul_total_product ff_v_mul_total_product. ((((exists ff_h_mul_total_product_start. ff_h_mul_total_product_start + S (1) = S ((S (0)) * ff_v_mul_total_product)) /\ exists ff_q_mul_total_product_start. ff_u_mul_total_product = ff_q_mul_total_product_start * S ((S (0)) * ff_v_mul_total_product) + (1))) /\ ((((exists ff_h_mul_total_product_terminal. ff_h_mul_total_product_terminal + S (z) = S ((S (p)) * ff_v_mul_total_product)) /\ exists ff_q_mul_total_product_terminal. ff_u_mul_total_product = ff_q_mul_total_product_terminal * S ((S (p)) * ff_v_mul_total_product) + (z))) /\ forall ff_i_mul_total_product. (exists ff_lt_mul_total_product_bound. ff_lt_mul_total_product_bound + S ff_i_mul_total_product = p) -> exists ff_p_mul_total_product ff_r_mul_total_product ff_s_mul_total_product. ((((exists ff_h_mul_total_product_factor. ff_h_mul_total_product_factor + S (ff_p_mul_total_product) = S ((S (ff_i_mul_total_product)) * ff_c_mul_total)) /\ exists ff_q_mul_total_product_factor. ff_b_mul_total = ff_q_mul_total_product_factor * S ((S (ff_i_mul_total_product)) * ff_c_mul_total) + (ff_p_mul_total_product))) /\ ((((exists ff_h_mul_total_product_partial. ff_h_mul_total_product_partial + S (ff_r_mul_total_product) = S ((S (ff_i_mul_total_product)) * ff_v_mul_total_product)) /\ exists ff_q_mul_total_product_partial. ff_u_mul_total_product = ff_q_mul_total_product_partial * S ((S (ff_i_mul_total_product)) * ff_v_mul_total_product) + (ff_r_mul_total_product))) /\ ((((exists ff_h_mul_total_product_successor. ff_h_mul_total_product_successor + S (ff_s_mul_total_product) = S ((S (S ff_i_mul_total_product)) * ff_v_mul_total_product)) /\ exists ff_q_mul_total_product_successor. ff_u_mul_total_product = ff_q_mul_total_product_successor * S ((S (S ff_i_mul_total_product)) * ff_v_mul_total_product) + (ff_s_mul_total_product))) /\ ff_s_mul_total_product = ff_r_mul_total_product * ff_p_mul_total_product)))))))) -> y = z

Structural proof guide

Generated structural guide

Iterated relational powers multiply their exponents.

Use the direct prerequisites pow_zero, pow_successor_decompose, pow_exists, pow_add as previously established PA formulas.

The proof proceeds by structural induction (1), case analysis (3), intermediate claims (7), equality transport (5).

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 Stable checked-use theorem is independently kernel-checked when replayed.

  1. 0001intro a
  2. 0002intro e
  3. 0003induction f
  4. 0004intro p
  5. 0005intro x
  6. 0006intro y
  7. 0007intro z
  8. 0008intro hp
  9. 0009intro hx
  10. 0010intro hy
  11. 0011intro hz
  12. 0012rewrite PA5 at hp
  13. 0013rewrite hp at hz
  14. 0014rewrite hp at hz
  15. 0015rewrite hp at hz
  16. 0016rewrite hp at hz
  17. 0017have hy1 : y = 1
  18. 0018specialize pow_zero x
  19. 0019specialize pow_zero 0
  20. 0020specialize pow_zero y
  21. 0021apply pow_zero
  22. 0022refl
  23. 0023exact hy
  24. 0024have hz1 : z = 1
  25. 0025specialize pow_zero a
  26. 0026specialize pow_zero 0
  27. 0027specialize pow_zero z
  28. 0028apply pow_zero
  29. 0029refl
  30. 0030exact hz
  31. 0031trans 1
  32. 0032exact hy1
  33. 0033symm
  34. 0034exact hz1
  35. 0035intro p
  36. 0036intro x
  37. 0037intro y
  38. 0038intro z
  39. 0039intro hp
  40. 0040intro hx
  41. 0041intro hy
  42. 0042intro hz
  43. 0043have hy_step : exists r. (exists ff_b_mul_y_prefix ff_c_mul_y_prefix. ((forall ff_i_mul_y_prefix_repeat. (exists ff_lt_mul_y_prefix_repeat_bound. ff_lt_mul_y_prefix_repeat_bound + S ff_i_mul_y_prefix_repeat = f) -> (((exists ff_h_mul_y_prefix_repeat_decoded. ff_h_mul_y_prefix_repeat_decoded + S (x) = S ((S (ff_i_mul_y_prefix_repeat)) * ff_c_mul_y_prefix)) /\ exists ff_q_mul_y_prefix_repeat_decoded. ff_b_mul_y_prefix = ff_q_mul_y_prefix_repeat_decoded * S ((S (ff_i_mul_y_prefix_repeat)) * ff_c_mul_y_prefix) + (x)))) /\ (exists ff_u_mul_y_prefix_product ff_v_mul_y_prefix_product. ((((exists ff_h_mul_y_prefix_product_start. ff_h_mul_y_prefix_product_start + S (1) = S ((S (0)) * ff_v_mul_y_prefix_product)) /\ exists ff_q_mul_y_prefix_product_start. ff_u_mul_y_prefix_product = ff_q_mul_y_prefix_product_start * S ((S (0)) * ff_v_mul_y_prefix_product) + (1))) /\ ((((exists ff_h_mul_y_prefix_product_terminal. ff_h_mul_y_prefix_product_terminal + S (r) = S ((S (f)) * ff_v_mul_y_prefix_product)) /\ exists ff_q_mul_y_prefix_product_terminal. ff_u_mul_y_prefix_product = ff_q_mul_y_prefix_product_terminal * S ((S (f)) * ff_v_mul_y_prefix_product) + (r))) /\ forall ff_i_mul_y_prefix_product. (exists ff_lt_mul_y_prefix_product_bound. ff_lt_mul_y_prefix_product_bound + S ff_i_mul_y_prefix_product = f) -> exists ff_p_mul_y_prefix_product ff_r_mul_y_prefix_product ff_s_mul_y_prefix_product. ((((exists ff_h_mul_y_prefix_product_factor. ff_h_mul_y_prefix_product_factor + S (ff_p_mul_y_prefix_product) = S ((S (ff_i_mul_y_prefix_product)) * ff_c_mul_y_prefix)) /\ exists ff_q_mul_y_prefix_product_factor. ff_b_mul_y_prefix = ff_q_mul_y_prefix_product_factor * S ((S (ff_i_mul_y_prefix_product)) * ff_c_mul_y_prefix) + (ff_p_mul_y_prefix_product))) /\ ((((exists ff_h_mul_y_prefix_product_partial. ff_h_mul_y_prefix_product_partial + S (ff_r_mul_y_prefix_product) = S ((S (ff_i_mul_y_prefix_product)) * ff_v_mul_y_prefix_product)) /\ exists ff_q_mul_y_prefix_product_partial. ff_u_mul_y_prefix_product = ff_q_mul_y_prefix_product_partial * S ((S (ff_i_mul_y_prefix_product)) * ff_v_mul_y_prefix_product) + (ff_r_mul_y_prefix_product))) /\ ((((exists ff_h_mul_y_prefix_product_successor. ff_h_mul_y_prefix_product_successor + S (ff_s_mul_y_prefix_product) = S ((S (S ff_i_mul_y_prefix_product)) * ff_v_mul_y_prefix_product)) /\ exists ff_q_mul_y_prefix_product_successor. ff_u_mul_y_prefix_product = ff_q_mul_y_prefix_product_successor * S ((S (S ff_i_mul_y_prefix_product)) * ff_v_mul_y_prefix_product) + (ff_s_mul_y_prefix_product))) /\ ff_s_mul_y_prefix_product = ff_r_mul_y_prefix_product * ff_p_mul_y_prefix_product)))))))) /\ y = r * x
  44. 0044specialize pow_successor_decompose x
  45. 0045specialize pow_successor_decompose f
  46. 0046specialize pow_successor_decompose (S f)
  47. 0047specialize pow_successor_decompose y
  48. 0048apply pow_successor_decompose
  49. 0049refl
  50. 0050exact hy
  51. 0051cases hy_step
  52. 0052cases hy_step_witness
  53. 0053have hqpow : exists r. (exists pa_b_mul_total_prefix pa_c_mul_total_prefix. ((forall pa_i_mul_total_prefix_repeat. (exists pa_lt_mul_total_prefix_repeat_bound. pa_lt_mul_total_prefix_repeat_bound + S pa_i_mul_total_prefix_repeat = e * f) -> (((exists pa_h_mul_total_prefix_repeat_decoded. pa_h_mul_total_prefix_repeat_decoded + S (a) = S ((S (pa_i_mul_total_prefix_repeat)) * pa_c_mul_total_prefix)) /\ exists pa_q_mul_total_prefix_repeat_decoded. pa_b_mul_total_prefix = pa_q_mul_total_prefix_repeat_decoded * S ((S (pa_i_mul_total_prefix_repeat)) * pa_c_mul_total_prefix) + (a)))) /\ (exists pa_u_mul_total_prefix_product pa_v_mul_total_prefix_product. ((((exists pa_h_mul_total_prefix_product_start. pa_h_mul_total_prefix_product_start + S (1) = S ((S (0)) * pa_v_mul_total_prefix_product)) /\ exists pa_q_mul_total_prefix_product_start. pa_u_mul_total_prefix_product = pa_q_mul_total_prefix_product_start * S ((S (0)) * pa_v_mul_total_prefix_product) + (1))) /\ ((((exists pa_h_mul_total_prefix_product_terminal. pa_h_mul_total_prefix_product_terminal + S (r) = S ((S (e * f)) * pa_v_mul_total_prefix_product)) /\ exists pa_q_mul_total_prefix_product_terminal. pa_u_mul_total_prefix_product = pa_q_mul_total_prefix_product_terminal * S ((S (e * f)) * pa_v_mul_total_prefix_product) + (r))) /\ forall pa_i_mul_total_prefix_product. (exists pa_lt_mul_total_prefix_product_bound. pa_lt_mul_total_prefix_product_bound + S pa_i_mul_total_prefix_product = e * f) -> exists pa_p_mul_total_prefix_product pa_r_mul_total_prefix_product pa_s_mul_total_prefix_product. ((((exists pa_h_mul_total_prefix_product_factor. pa_h_mul_total_prefix_product_factor + S (pa_p_mul_total_prefix_product) = S ((S (pa_i_mul_total_prefix_product)) * pa_c_mul_total_prefix)) /\ exists pa_q_mul_total_prefix_product_factor. pa_b_mul_total_prefix = pa_q_mul_total_prefix_product_factor * S ((S (pa_i_mul_total_prefix_product)) * pa_c_mul_total_prefix) + (pa_p_mul_total_prefix_product))) /\ ((((exists pa_h_mul_total_prefix_product_partial. pa_h_mul_total_prefix_product_partial + S (pa_r_mul_total_prefix_product) = S ((S (pa_i_mul_total_prefix_product)) * pa_v_mul_total_prefix_product)) /\ exists pa_q_mul_total_prefix_product_partial. pa_u_mul_total_prefix_product = pa_q_mul_total_prefix_product_partial * S ((S (pa_i_mul_total_prefix_product)) * pa_v_mul_total_prefix_product) + (pa_r_mul_total_prefix_product))) /\ ((((exists pa_h_mul_total_prefix_product_successor. pa_h_mul_total_prefix_product_successor + S (pa_s_mul_total_prefix_product) = S ((S (S pa_i_mul_total_prefix_product)) * pa_v_mul_total_prefix_product)) /\ exists pa_q_mul_total_prefix_product_successor. pa_u_mul_total_prefix_product = pa_q_mul_total_prefix_product_successor * S ((S (S pa_i_mul_total_prefix_product)) * pa_v_mul_total_prefix_product) + (pa_s_mul_total_prefix_product))) /\ pa_s_mul_total_prefix_product = pa_r_mul_total_prefix_product * pa_p_mul_total_prefix_product))))))))
  54. 0054specialize pow_exists a
  55. 0055specialize pow_exists (e * f)
  56. 0056exact pow_exists
  57. 0057cases hqpow
  58. 0058have hprefix : x1 = x2
  59. 0059specialize IH (e * f)
  60. 0060specialize IH x
  61. 0061specialize IH x1
  62. 0062specialize IH x2
  63. 0063apply IH
  64. 0064refl
  65. 0065exact hx
  66. 0066exact hy_step_witness_left
  67. 0067exact hqpow_witness
  68. 0068have hpsum : p = (e * f) + e
  69. 0069trans e * S f
  70. 0070exact hp
  71. 0071apply PA6
  72. 0072have htotal : z = x2 * x
  73. 0073specialize pow_add a
  74. 0074specialize pow_add (e * f)
  75. 0075specialize pow_add e
  76. 0076specialize pow_add p
  77. 0077specialize pow_add x2
  78. 0078specialize pow_add x
  79. 0079specialize pow_add z
  80. 0080apply pow_add
  81. 0081exact hpsum
  82. 0082exact hqpow_witness
  83. 0083exact hx
  84. 0084exact hz
  85. 0085trans x1 * x
  86. 0086exact hy_step_witness_right
  87. 0087trans x2 * x
  88. 0088congr
  89. 0089exact hprefix
  90. 0090refl
  91. 0091symm
  92. 0092exact htotal