BT00Q3

power_divides_decidable

Alpha body-checked ยท checked-use disabled

Divisibility by a relational power is constructively decidable.

Exact expanded PA statement

forall p e a. (exists bpv_result_decision. ((exists ff_b_decision_power ff_c_decision_power. ((forall ff_i_decision_power_repeat. (exists ff_lt_decision_power_repeat_bound. ff_lt_decision_power_repeat_bound + S ff_i_decision_power_repeat = e) -> (((exists ff_h_decision_power_repeat_decoded. ff_h_decision_power_repeat_decoded + S (p) = S ((S (ff_i_decision_power_repeat)) * ff_c_decision_power)) /\ exists ff_q_decision_power_repeat_decoded. ff_b_decision_power = ff_q_decision_power_repeat_decoded * S ((S (ff_i_decision_power_repeat)) * ff_c_decision_power) + (p)))) /\ (exists ff_u_decision_power_product ff_v_decision_power_product. ((((exists ff_h_decision_power_product_start. ff_h_decision_power_product_start + S (1) = S ((S (0)) * ff_v_decision_power_product)) /\ exists ff_q_decision_power_product_start. ff_u_decision_power_product = ff_q_decision_power_product_start * S ((S (0)) * ff_v_decision_power_product) + (1))) /\ ((((exists ff_h_decision_power_product_terminal. ff_h_decision_power_product_terminal + S (bpv_result_decision) = S ((S (e)) * ff_v_decision_power_product)) /\ exists ff_q_decision_power_product_terminal. ff_u_decision_power_product = ff_q_decision_power_product_terminal * S ((S (e)) * ff_v_decision_power_product) + (bpv_result_decision))) /\ forall ff_i_decision_power_product. (exists ff_lt_decision_power_product_bound. ff_lt_decision_power_product_bound + S ff_i_decision_power_product = e) -> exists ff_p_decision_power_product ff_r_decision_power_product ff_s_decision_power_product. ((((exists ff_h_decision_power_product_factor. ff_h_decision_power_product_factor + S (ff_p_decision_power_product) = S ((S (ff_i_decision_power_product)) * ff_c_decision_power)) /\ exists ff_q_decision_power_product_factor. ff_b_decision_power = ff_q_decision_power_product_factor * S ((S (ff_i_decision_power_product)) * ff_c_decision_power) + (ff_p_decision_power_product))) /\ ((((exists ff_h_decision_power_product_partial. ff_h_decision_power_product_partial + S (ff_r_decision_power_product) = S ((S (ff_i_decision_power_product)) * ff_v_decision_power_product)) /\ exists ff_q_decision_power_product_partial. ff_u_decision_power_product = ff_q_decision_power_product_partial * S ((S (ff_i_decision_power_product)) * ff_v_decision_power_product) + (ff_r_decision_power_product))) /\ ((((exists ff_h_decision_power_product_successor. ff_h_decision_power_product_successor + S (ff_s_decision_power_product) = S ((S (S ff_i_decision_power_product)) * ff_v_decision_power_product)) /\ exists ff_q_decision_power_product_successor. ff_u_decision_power_product = ff_q_decision_power_product_successor * S ((S (S ff_i_decision_power_product)) * ff_v_decision_power_product) + (ff_s_decision_power_product))) /\ ff_s_decision_power_product = ff_r_decision_power_product * ff_p_decision_power_product)))))))) /\ (exists bpv_factor_decision_divides. a = bpv_result_decision * bpv_factor_decision_divides))) \/ ~(exists bpv_result_decision. ((exists ff_b_decision_power ff_c_decision_power. ((forall ff_i_decision_power_repeat. (exists ff_lt_decision_power_repeat_bound. ff_lt_decision_power_repeat_bound + S ff_i_decision_power_repeat = e) -> (((exists ff_h_decision_power_repeat_decoded. ff_h_decision_power_repeat_decoded + S (p) = S ((S (ff_i_decision_power_repeat)) * ff_c_decision_power)) /\ exists ff_q_decision_power_repeat_decoded. ff_b_decision_power = ff_q_decision_power_repeat_decoded * S ((S (ff_i_decision_power_repeat)) * ff_c_decision_power) + (p)))) /\ (exists ff_u_decision_power_product ff_v_decision_power_product. ((((exists ff_h_decision_power_product_start. ff_h_decision_power_product_start + S (1) = S ((S (0)) * ff_v_decision_power_product)) /\ exists ff_q_decision_power_product_start. ff_u_decision_power_product = ff_q_decision_power_product_start * S ((S (0)) * ff_v_decision_power_product) + (1))) /\ ((((exists ff_h_decision_power_product_terminal. ff_h_decision_power_product_terminal + S (bpv_result_decision) = S ((S (e)) * ff_v_decision_power_product)) /\ exists ff_q_decision_power_product_terminal. ff_u_decision_power_product = ff_q_decision_power_product_terminal * S ((S (e)) * ff_v_decision_power_product) + (bpv_result_decision))) /\ forall ff_i_decision_power_product. (exists ff_lt_decision_power_product_bound. ff_lt_decision_power_product_bound + S ff_i_decision_power_product = e) -> exists ff_p_decision_power_product ff_r_decision_power_product ff_s_decision_power_product. ((((exists ff_h_decision_power_product_factor. ff_h_decision_power_product_factor + S (ff_p_decision_power_product) = S ((S (ff_i_decision_power_product)) * ff_c_decision_power)) /\ exists ff_q_decision_power_product_factor. ff_b_decision_power = ff_q_decision_power_product_factor * S ((S (ff_i_decision_power_product)) * ff_c_decision_power) + (ff_p_decision_power_product))) /\ ((((exists ff_h_decision_power_product_partial. ff_h_decision_power_product_partial + S (ff_r_decision_power_product) = S ((S (ff_i_decision_power_product)) * ff_v_decision_power_product)) /\ exists ff_q_decision_power_product_partial. ff_u_decision_power_product = ff_q_decision_power_product_partial * S ((S (ff_i_decision_power_product)) * ff_v_decision_power_product) + (ff_r_decision_power_product))) /\ ((((exists ff_h_decision_power_product_successor. ff_h_decision_power_product_successor + S (ff_s_decision_power_product) = S ((S (S ff_i_decision_power_product)) * ff_v_decision_power_product)) /\ exists ff_q_decision_power_product_successor. ff_u_decision_power_product = ff_q_decision_power_product_successor * S ((S (S ff_i_decision_power_product)) * ff_v_decision_power_product) + (ff_s_decision_power_product))) /\ ff_s_decision_power_product = ff_r_decision_power_product * ff_p_decision_power_product)))))))) /\ (exists bpv_factor_decision_divides. a = bpv_result_decision * bpv_factor_decision_divides)))

Structural proof guide

Divisibility by a relational power is constructively decidable.

Direct prerequisites: pow_exists, multiple_decidable, pow_functional. The authored body proceeds by case analysis (4), intermediate claims (3), equality transport (1).

Proof neighborhood

Direct dependencies

Direct dependents

Formal native tactic body

Dependencies are hypotheses of this body receipt. The focused endpoint audits separately check the complete empty-context certificates.

  1. 0001intro p
  2. 0002intro e
  3. 0003intro a
  4. 0004have hpower : exists r. (exists ff_b_decision_witness ff_c_decision_witness. ((forall ff_i_decision_witness_repeat. (exists ff_lt_decision_witness_repeat_bound. ff_lt_decision_witness_repeat_bound + S ff_i_decision_witness_repeat = e) -> (((exists ff_h_decision_witness_repeat_decoded. ff_h_decision_witness_repeat_decoded + S (p) = S ((S (ff_i_decision_witness_repeat)) * ff_c_decision_witness)) /\ exists ff_q_decision_witness_repeat_decoded. ff_b_decision_witness = ff_q_decision_witness_repeat_decoded * S ((S (ff_i_decision_witness_repeat)) * ff_c_decision_witness) + (p)))) /\ (exists ff_u_decision_witness_product ff_v_decision_witness_product. ((((exists ff_h_decision_witness_product_start. ff_h_decision_witness_product_start + S (1) = S ((S (0)) * ff_v_decision_witness_product)) /\ exists ff_q_decision_witness_product_start. ff_u_decision_witness_product = ff_q_decision_witness_product_start * S ((S (0)) * ff_v_decision_witness_product) + (1))) /\ ((((exists ff_h_decision_witness_product_terminal. ff_h_decision_witness_product_terminal + S (r) = S ((S (e)) * ff_v_decision_witness_product)) /\ exists ff_q_decision_witness_product_terminal. ff_u_decision_witness_product = ff_q_decision_witness_product_terminal * S ((S (e)) * ff_v_decision_witness_product) + (r))) /\ forall ff_i_decision_witness_product. (exists ff_lt_decision_witness_product_bound. ff_lt_decision_witness_product_bound + S ff_i_decision_witness_product = e) -> exists ff_p_decision_witness_product ff_r_decision_witness_product ff_s_decision_witness_product. ((((exists ff_h_decision_witness_product_factor. ff_h_decision_witness_product_factor + S (ff_p_decision_witness_product) = S ((S (ff_i_decision_witness_product)) * ff_c_decision_witness)) /\ exists ff_q_decision_witness_product_factor. ff_b_decision_witness = ff_q_decision_witness_product_factor * S ((S (ff_i_decision_witness_product)) * ff_c_decision_witness) + (ff_p_decision_witness_product))) /\ ((((exists ff_h_decision_witness_product_partial. ff_h_decision_witness_product_partial + S (ff_r_decision_witness_product) = S ((S (ff_i_decision_witness_product)) * ff_v_decision_witness_product)) /\ exists ff_q_decision_witness_product_partial. ff_u_decision_witness_product = ff_q_decision_witness_product_partial * S ((S (ff_i_decision_witness_product)) * ff_v_decision_witness_product) + (ff_r_decision_witness_product))) /\ ((((exists ff_h_decision_witness_product_successor. ff_h_decision_witness_product_successor + S (ff_s_decision_witness_product) = S ((S (S ff_i_decision_witness_product)) * ff_v_decision_witness_product)) /\ exists ff_q_decision_witness_product_successor. ff_u_decision_witness_product = ff_q_decision_witness_product_successor * S ((S (S ff_i_decision_witness_product)) * ff_v_decision_witness_product) + (ff_s_decision_witness_product))) /\ ff_s_decision_witness_product = ff_r_decision_witness_product * ff_p_decision_witness_product))))))))
  5. 0005specialize pow_exists p
  6. 0006specialize pow_exists e
  7. 0007exact pow_exists
  8. 0008cases hpower
  9. 0009have hdiv : (exists q. a = x * q) \/ ~(exists q. a = x * q)
  10. 0010specialize multiple_decidable x
  11. 0011specialize multiple_decidable a
  12. 0012exact multiple_decidable
  13. 0013cases hdiv
  14. 0014left
  15. 0015exists x
  16. 0016split
  17. 0017exact hpower_witness
  18. 0018exact hdiv_left
  19. 0019right
  20. 0020intro hother
  21. 0021cases hother
  22. 0022cases hother_witness
  23. 0023have heq : x1 = x
  24. 0024specialize pow_functional p
  25. 0025specialize pow_functional e
  26. 0026specialize pow_functional x1
  27. 0027specialize pow_functional x
  28. 0028apply pow_functional
  29. 0029exact hother_witness_left
  30. 0030exact hpower_witness
  31. 0031apply hdiv_right
  32. 0032rewrite heq at hother_witness_right
  33. 0033exact hother_witness_right