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 = zStructural 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.
- 0001
intro a - 0002
intro e - 0003
induction f - 0004
intro p - 0005
intro x - 0006
intro y - 0007
intro z - 0008
intro hp - 0009
intro hx - 0010
intro hy - 0011
intro hz - 0012
rewrite PA5 at hp - 0013
rewrite hp at hz - 0014
rewrite hp at hz - 0015
rewrite hp at hz - 0016
rewrite hp at hz - 0017
have hy1 : y = 1 - 0018
specialize pow_zero x - 0019
specialize pow_zero 0 - 0020
specialize pow_zero y - 0021
apply pow_zero - 0022
refl - 0023
exact hy - 0024
have hz1 : z = 1 - 0025
specialize pow_zero a - 0026
specialize pow_zero 0 - 0027
specialize pow_zero z - 0028
apply pow_zero - 0029
refl - 0030
exact hz - 0031
trans 1 - 0032
exact hy1 - 0033
symm - 0034
exact hz1 - 0035
intro p - 0036
intro x - 0037
intro y - 0038
intro z - 0039
intro hp - 0040
intro hx - 0041
intro hy - 0042
intro hz - 0043
have 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 - 0044
specialize pow_successor_decompose x - 0045
specialize pow_successor_decompose f - 0046
specialize pow_successor_decompose (S f) - 0047
specialize pow_successor_decompose y - 0048
apply pow_successor_decompose - 0049
refl - 0050
exact hy - 0051
cases hy_step - 0052
cases hy_step_witness - 0053
have 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)))))))) - 0054
specialize pow_exists a - 0055
specialize pow_exists (e * f) - 0056
exact pow_exists - 0057
cases hqpow - 0058
have hprefix : x1 = x2 - 0059
specialize IH (e * f) - 0060
specialize IH x - 0061
specialize IH x1 - 0062
specialize IH x2 - 0063
apply IH - 0064
refl - 0065
exact hx - 0066
exact hy_step_witness_left - 0067
exact hqpow_witness - 0068
have hpsum : p = (e * f) + e - 0069
trans e * S f - 0070
exact hp - 0071
apply PA6 - 0072
have htotal : z = x2 * x - 0073
specialize pow_add a - 0074
specialize pow_add (e * f) - 0075
specialize pow_add e - 0076
specialize pow_add p - 0077
specialize pow_add x2 - 0078
specialize pow_add x - 0079
specialize pow_add z - 0080
apply pow_add - 0081
exact hpsum - 0082
exact hqpow_witness - 0083
exact hx - 0084
exact hz - 0085
trans x1 * x - 0086
exact hy_step_witness_right - 0087
trans x2 * x - 0088
congr - 0089
exact hprefix - 0090
refl - 0091
symm - 0092
exact htotal