PA009P

beta_prefix_append_two_bounded_into

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

A two-entry append remains bounded when the old prefix and both appended values are bounded.

Exact expanded PA statement

forall b c z d l n a e. (((((exists wpo_beta_height_wpoi_append_bounded_trace_first. wpo_beta_height_wpoi_append_bounded_trace_first + S (a) = S ((S (l)) * d)) /\ exists wpo_beta_quotient_wpoi_append_bounded_trace_first. z = wpo_beta_quotient_wpoi_append_bounded_trace_first * S ((S (l)) * d) + (a))) /\ ((((exists wpo_beta_height_wpoi_append_bounded_trace_second. wpo_beta_height_wpoi_append_bounded_trace_second + S (e) = S ((S (S (l))) * d)) /\ exists wpo_beta_quotient_wpoi_append_bounded_trace_second. z = wpo_beta_quotient_wpoi_append_bounded_trace_second * S ((S (S (l))) * d) + (e))) /\ (forall wpo_old_index_wpoi_append_bounded_trace wpo_old_value_wpoi_append_bounded_trace. (exists wpo_gap_wpoi_append_bounded_trace_old_bound. wpo_gap_wpoi_append_bounded_trace_old_bound + S (wpo_old_index_wpoi_append_bounded_trace) = l) -> (((exists wpo_beta_height_wpoi_append_bounded_trace_old_entry. wpo_beta_height_wpoi_append_bounded_trace_old_entry + S (wpo_old_value_wpoi_append_bounded_trace) = S ((S (wpo_old_index_wpoi_append_bounded_trace)) * c)) /\ exists wpo_beta_quotient_wpoi_append_bounded_trace_old_entry. b = wpo_beta_quotient_wpoi_append_bounded_trace_old_entry * S ((S (wpo_old_index_wpoi_append_bounded_trace)) * c) + (wpo_old_value_wpoi_append_bounded_trace))) -> (((exists wpo_beta_height_wpoi_append_bounded_trace_new_entry. wpo_beta_height_wpoi_append_bounded_trace_new_entry + S (wpo_old_value_wpoi_append_bounded_trace) = S ((S (wpo_old_index_wpoi_append_bounded_trace)) * d)) /\ exists wpo_beta_quotient_wpoi_append_bounded_trace_new_entry. z = wpo_beta_quotient_wpoi_append_bounded_trace_new_entry * S ((S (wpo_old_index_wpoi_append_bounded_trace)) * d) + (wpo_old_value_wpoi_append_bounded_trace))))))) -> (forall fom_index_wpoi_append_bounded_before. (exists fom_gap_wpoi_append_bounded_before_index_bound. fom_gap_wpoi_append_bounded_before_index_bound + S (fom_index_wpoi_append_bounded_before) = l) -> exists fom_value_wpoi_append_bounded_before. ((((exists fom_beta_height_wpoi_append_bounded_before_entry. fom_beta_height_wpoi_append_bounded_before_entry + S (fom_value_wpoi_append_bounded_before) = S ((S (fom_index_wpoi_append_bounded_before)) * c)) /\ exists fom_beta_quotient_wpoi_append_bounded_before_entry. b = fom_beta_quotient_wpoi_append_bounded_before_entry * S ((S (fom_index_wpoi_append_bounded_before)) * c) + (fom_value_wpoi_append_bounded_before))) /\ (exists fom_gap_wpoi_append_bounded_before_value_bound. fom_gap_wpoi_append_bounded_before_value_bound + S (fom_value_wpoi_append_bounded_before) = n))) -> (exists wpo_gap_wpoi_append_first_bound. wpo_gap_wpoi_append_first_bound + S (a) = n) -> (exists wpo_gap_wpoi_append_second_bound. wpo_gap_wpoi_append_second_bound + S (e) = n) -> (forall fom_index_wpoi_append_bounded_after. (exists fom_gap_wpoi_append_bounded_after_index_bound. fom_gap_wpoi_append_bounded_after_index_bound + S (fom_index_wpoi_append_bounded_after) = S (S l)) -> exists fom_value_wpoi_append_bounded_after. ((((exists fom_beta_height_wpoi_append_bounded_after_entry. fom_beta_height_wpoi_append_bounded_after_entry + S (fom_value_wpoi_append_bounded_after) = S ((S (fom_index_wpoi_append_bounded_after)) * d)) /\ exists fom_beta_quotient_wpoi_append_bounded_after_entry. z = fom_beta_quotient_wpoi_append_bounded_after_entry * S ((S (fom_index_wpoi_append_bounded_after)) * d) + (fom_value_wpoi_append_bounded_after))) /\ (exists fom_gap_wpoi_append_bounded_after_value_bound. fom_gap_wpoi_append_bounded_after_value_bound + S (fom_value_wpoi_append_bounded_after) = n)))

Structural proof guide

Generated structural guide

A two-entry append remains bounded when the old prefix and both appended values are bounded.

Use the direct prerequisites finite_lt_succ_eq_or_lt as previously established PA formulas.

The proof proceeds by case analysis (6), intermediate claims (3), equality transport (4).

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 z
  4. 0004intro d
  5. 0005intro l
  6. 0006intro n
  7. 0007intro a
  8. 0008intro e
  9. 0009intro htrace
  10. 0010intro hold_bounded
  11. 0011intro hfirst_bounded
  12. 0012intro hsecond_bounded
  13. 0013cases htrace
  14. 0014cases htrace_right
  15. 0015intro q
  16. 0016intro hq
  17. 0017have htop : q = S l \/ exists h. h + S q = S l
  18. 0018specialize finite_lt_succ_eq_or_lt (S l)
  19. 0019specialize finite_lt_succ_eq_or_lt q
  20. 0020apply finite_lt_succ_eq_or_lt
  21. 0021exact hq
  22. 0022cases htop
  23. 0023exists e
  24. 0024split
  25. 0025rewrite htop_left
  26. 0026rewrite htop_left
  27. 0027exact htrace_right_left
  28. 0028exact hsecond_bounded
  29. 0029have hmiddle : q = l \/ exists h. h + S q = l
  30. 0030specialize finite_lt_succ_eq_or_lt l
  31. 0031specialize finite_lt_succ_eq_or_lt q
  32. 0032apply finite_lt_succ_eq_or_lt
  33. 0033exact htop_right
  34. 0034cases hmiddle
  35. 0035exists a
  36. 0036split
  37. 0037rewrite hmiddle_left
  38. 0038rewrite hmiddle_left
  39. 0039exact htrace_left
  40. 0040exact hfirst_bounded
  41. 0041have hold_entry : exists w. ((((exists wpo_beta_height_wpoi_append_bounded_old_entry. wpo_beta_height_wpoi_append_bounded_old_entry + S (w) = S ((S (q)) * c)) /\ exists wpo_beta_quotient_wpoi_append_bounded_old_entry. b = wpo_beta_quotient_wpoi_append_bounded_old_entry * S ((S (q)) * c) + (w))) /\ (exists wpo_gap_wpoi_append_bounded_old_value_bound. wpo_gap_wpoi_append_bounded_old_value_bound + S (w) = n))
  42. 0042specialize hold_bounded q
  43. 0043apply hold_bounded
  44. 0044exact hmiddle_right
  45. 0045cases hold_entry
  46. 0046cases hold_entry_witness
  47. 0047exists x
  48. 0048split
  49. 0049specialize htrace_right_right q
  50. 0050specialize htrace_right_right x
  51. 0051apply htrace_right_right
  52. 0052exact hmiddle_right
  53. 0053exact hold_entry_witness_left
  54. 0054exact hold_entry_witness_right