PA00AT

beta_prefix_append_two_orbit_closed

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

Appending both directions of a decoded two-cycle preserves orbit closure of the used prefix.

Exact expanded PA statement

forall u v b c z d l a e. (((((exists wpo_beta_height_closure_trace_first. wpo_beta_height_closure_trace_first + S (a) = S ((S (l)) * d)) /\ exists wpo_beta_quotient_closure_trace_first. z = wpo_beta_quotient_closure_trace_first * S ((S (l)) * d) + (a))) /\ ((((exists wpo_beta_height_closure_trace_second. wpo_beta_height_closure_trace_second + S (e) = S ((S (S (l))) * d)) /\ exists wpo_beta_quotient_closure_trace_second. z = wpo_beta_quotient_closure_trace_second * S ((S (S (l))) * d) + (e))) /\ (forall wpo_old_index_closure_trace wpo_old_value_closure_trace. (exists wpo_gap_closure_trace_old_bound. wpo_gap_closure_trace_old_bound + S (wpo_old_index_closure_trace) = l) -> (((exists wpo_beta_height_closure_trace_old_entry. wpo_beta_height_closure_trace_old_entry + S (wpo_old_value_closure_trace) = S ((S (wpo_old_index_closure_trace)) * c)) /\ exists wpo_beta_quotient_closure_trace_old_entry. b = wpo_beta_quotient_closure_trace_old_entry * S ((S (wpo_old_index_closure_trace)) * c) + (wpo_old_value_closure_trace))) -> (((exists wpo_beta_height_closure_trace_new_entry. wpo_beta_height_closure_trace_new_entry + S (wpo_old_value_closure_trace) = S ((S (wpo_old_index_closure_trace)) * d)) /\ exists wpo_beta_quotient_closure_trace_new_entry. z = wpo_beta_quotient_closure_trace_new_entry * S ((S (wpo_old_index_closure_trace)) * d) + (wpo_old_value_closure_trace))))))) -> (forall wpo_position_closure_before wpo_source_closure_before wpo_mate_closure_before. (exists wpo_gap_closure_before_position_bound. wpo_gap_closure_before_position_bound + S (wpo_position_closure_before) = l) -> (((exists wpo_beta_height_closure_before_source_entry. wpo_beta_height_closure_before_source_entry + S (wpo_source_closure_before) = S ((S (wpo_position_closure_before)) * c)) /\ exists wpo_beta_quotient_closure_before_source_entry. b = wpo_beta_quotient_closure_before_source_entry * S ((S (wpo_position_closure_before)) * c) + (wpo_source_closure_before))) -> (((exists wpo_beta_height_closure_before_inverse_entry. wpo_beta_height_closure_before_inverse_entry + S (wpo_mate_closure_before) = S ((S (wpo_source_closure_before)) * v)) /\ exists wpo_beta_quotient_closure_before_inverse_entry. u = wpo_beta_quotient_closure_before_inverse_entry * S ((S (wpo_source_closure_before)) * v) + (wpo_mate_closure_before))) -> exists wpo_mate_position_closure_before. ((exists wpo_gap_closure_before_mate_bound. wpo_gap_closure_before_mate_bound + S (wpo_mate_position_closure_before) = l) /\ (((exists wpo_beta_height_closure_before_mate_entry. wpo_beta_height_closure_before_mate_entry + S (wpo_mate_closure_before) = S ((S (wpo_mate_position_closure_before)) * c)) /\ exists wpo_beta_quotient_closure_before_mate_entry. b = wpo_beta_quotient_closure_before_mate_entry * S ((S (wpo_mate_position_closure_before)) * c) + (wpo_mate_closure_before))))) -> (((exists wpo_beta_height_closure_forward. wpo_beta_height_closure_forward + S (e) = S ((S (a)) * v)) /\ exists wpo_beta_quotient_closure_forward. u = wpo_beta_quotient_closure_forward * S ((S (a)) * v) + (e))) -> (((exists wpo_beta_height_closure_back. wpo_beta_height_closure_back + S (a) = S ((S (e)) * v)) /\ exists wpo_beta_quotient_closure_back. u = wpo_beta_quotient_closure_back * S ((S (e)) * v) + (a))) -> (forall wpo_position_closure_after wpo_source_closure_after wpo_mate_closure_after. (exists wpo_gap_closure_after_position_bound. wpo_gap_closure_after_position_bound + S (wpo_position_closure_after) = S (S l)) -> (((exists wpo_beta_height_closure_after_source_entry. wpo_beta_height_closure_after_source_entry + S (wpo_source_closure_after) = S ((S (wpo_position_closure_after)) * d)) /\ exists wpo_beta_quotient_closure_after_source_entry. z = wpo_beta_quotient_closure_after_source_entry * S ((S (wpo_position_closure_after)) * d) + (wpo_source_closure_after))) -> (((exists wpo_beta_height_closure_after_inverse_entry. wpo_beta_height_closure_after_inverse_entry + S (wpo_mate_closure_after) = S ((S (wpo_source_closure_after)) * v)) /\ exists wpo_beta_quotient_closure_after_inverse_entry. u = wpo_beta_quotient_closure_after_inverse_entry * S ((S (wpo_source_closure_after)) * v) + (wpo_mate_closure_after))) -> exists wpo_mate_position_closure_after. ((exists wpo_gap_closure_after_mate_bound. wpo_gap_closure_after_mate_bound + S (wpo_mate_position_closure_after) = S (S l)) /\ (((exists wpo_beta_height_closure_after_mate_entry. wpo_beta_height_closure_after_mate_entry + S (wpo_mate_closure_after) = S ((S (wpo_mate_position_closure_after)) * d)) /\ exists wpo_beta_quotient_closure_after_mate_entry. z = wpo_beta_quotient_closure_after_mate_entry * S ((S (wpo_mate_position_closure_after)) * d) + (wpo_mate_closure_after)))))

Structural proof guide

Generated structural guide

Appending both directions of a decoded two-cycle preserves orbit closure of the used prefix.

Use the direct prerequisites beta_prefix_append_two_reflect, beta_at_unique, le_refl, le_succ as previously established PA formulas.

The proof proceeds by case analysis (9), intermediate claims (7), equality transport (8).

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 u
  2. 0002intro v
  3. 0003intro b
  4. 0004intro c
  5. 0005intro z
  6. 0006intro d
  7. 0007intro l
  8. 0008intro a
  9. 0009intro e
  10. 0010intro htrace
  11. 0011intro hclosed
  12. 0012intro hforward
  13. 0013intro hback
  14. 0014have htrace_parts : ((((exists wpo_beta_height_closure_trace_first. wpo_beta_height_closure_trace_first + S (a) = S ((S (l)) * d)) /\ exists wpo_beta_quotient_closure_trace_first. z = wpo_beta_quotient_closure_trace_first * S ((S (l)) * d) + (a))) /\ ((((exists wpo_beta_height_closure_trace_second. wpo_beta_height_closure_trace_second + S (e) = S ((S (S (l))) * d)) /\ exists wpo_beta_quotient_closure_trace_second. z = wpo_beta_quotient_closure_trace_second * S ((S (S (l))) * d) + (e))) /\ (forall wpo_old_index_closure_trace wpo_old_value_closure_trace. (exists wpo_gap_closure_trace_old_bound. wpo_gap_closure_trace_old_bound + S (wpo_old_index_closure_trace) = l) -> (((exists wpo_beta_height_closure_trace_old_entry. wpo_beta_height_closure_trace_old_entry + S (wpo_old_value_closure_trace) = S ((S (wpo_old_index_closure_trace)) * c)) /\ exists wpo_beta_quotient_closure_trace_old_entry. b = wpo_beta_quotient_closure_trace_old_entry * S ((S (wpo_old_index_closure_trace)) * c) + (wpo_old_value_closure_trace))) -> (((exists wpo_beta_height_closure_trace_new_entry. wpo_beta_height_closure_trace_new_entry + S (wpo_old_value_closure_trace) = S ((S (wpo_old_index_closure_trace)) * d)) /\ exists wpo_beta_quotient_closure_trace_new_entry. z = wpo_beta_quotient_closure_trace_new_entry * S ((S (wpo_old_index_closure_trace)) * d) + (wpo_old_value_closure_trace))))))
  15. 0015exact htrace
  16. 0016cases htrace_parts
  17. 0017cases htrace_parts_right
  18. 0018intro q
  19. 0019intro s
  20. 0020intro m
  21. 0021intro hq
  22. 0022intro hsource
  23. 0023intro hinverse
  24. 0024have hreflect_all : forall q s. (exists wpo_gap_closure_reflection_bound. wpo_gap_closure_reflection_bound + S (q) = S (S l)) -> (((exists wpo_beta_height_closure_reflection_entry. wpo_beta_height_closure_reflection_entry + S (s) = S ((S (q)) * d)) /\ exists wpo_beta_quotient_closure_reflection_entry. z = wpo_beta_quotient_closure_reflection_entry * S ((S (q)) * d) + (s))) -> (((q = S (l) /\ s = e) \/ ((q = l /\ s = a) \/ ((exists wpo_gap_closure_reflection_old_bound. wpo_gap_closure_reflection_old_bound + S (q) = l) /\ (((exists wpo_beta_height_closure_reflection_old_entry. wpo_beta_height_closure_reflection_old_entry + S (s) = S ((S (q)) * c)) /\ exists wpo_beta_quotient_closure_reflection_old_entry. b = wpo_beta_quotient_closure_reflection_old_entry * S ((S (q)) * c) + (s)))))))
  25. 0025specialize beta_prefix_append_two_reflect b
  26. 0026specialize beta_prefix_append_two_reflect c
  27. 0027specialize beta_prefix_append_two_reflect z
  28. 0028specialize beta_prefix_append_two_reflect d
  29. 0029specialize beta_prefix_append_two_reflect l
  30. 0030specialize beta_prefix_append_two_reflect a
  31. 0031specialize beta_prefix_append_two_reflect e
  32. 0032apply beta_prefix_append_two_reflect
  33. 0033exact htrace
  34. 0034have hreflect : ((q = S (l) /\ s = e) \/ ((q = l /\ s = a) \/ ((exists wpo_gap_closure_reflection_old_bound. wpo_gap_closure_reflection_old_bound + S (q) = l) /\ (((exists wpo_beta_height_closure_reflection_old_entry. wpo_beta_height_closure_reflection_old_entry + S (s) = S ((S (q)) * c)) /\ exists wpo_beta_quotient_closure_reflection_old_entry. b = wpo_beta_quotient_closure_reflection_old_entry * S ((S (q)) * c) + (s))))))
  35. 0035specialize hreflect_all q
  36. 0036specialize hreflect_all s
  37. 0037apply hreflect_all
  38. 0038exact hq
  39. 0039exact hsource
  40. 0040cases hreflect
  41. 0041cases hreflect_left
  42. 0042have hmate_first : m = a
  43. 0043specialize beta_at_unique u
  44. 0044specialize beta_at_unique v
  45. 0045specialize beta_at_unique e
  46. 0046specialize beta_at_unique m
  47. 0047specialize beta_at_unique a
  48. 0048apply beta_at_unique
  49. 0049rewrite hreflect_left_right at hinverse
  50. 0050rewrite hreflect_left_right at hinverse
  51. 0051exact hinverse
  52. 0052exact hback
  53. 0053exists l
  54. 0054split
  55. 0055specialize le_succ (S l)
  56. 0056specialize le_succ (S l)
  57. 0057apply le_succ
  58. 0058specialize le_refl (S l)
  59. 0059exact le_refl
  60. 0060rewrite hmate_first
  61. 0061rewrite hmate_first
  62. 0062exact htrace_parts_left
  63. 0063cases hreflect_right
  64. 0064cases hreflect_right_left
  65. 0065have hmate_second : m = e
  66. 0066specialize beta_at_unique u
  67. 0067specialize beta_at_unique v
  68. 0068specialize beta_at_unique a
  69. 0069specialize beta_at_unique m
  70. 0070specialize beta_at_unique e
  71. 0071apply beta_at_unique
  72. 0072rewrite hreflect_right_left_right at hinverse
  73. 0073rewrite hreflect_right_left_right at hinverse
  74. 0074exact hinverse
  75. 0075exact hforward
  76. 0076exists (S l)
  77. 0077split
  78. 0078specialize le_refl (S (S l))
  79. 0079exact le_refl
  80. 0080rewrite hmate_second
  81. 0081rewrite hmate_second
  82. 0082exact htrace_parts_right_left
  83. 0083cases hreflect_right_right
  84. 0084have hold_occurrence : exists wpo_index_closure_old_occurrence. ((exists wpo_gap_closure_old_occurrence_bound. wpo_gap_closure_old_occurrence_bound + S (wpo_index_closure_old_occurrence) = l) /\ (((exists wpo_beta_height_closure_old_occurrence_entry. wpo_beta_height_closure_old_occurrence_entry + S (m) = S ((S (wpo_index_closure_old_occurrence)) * c)) /\ exists wpo_beta_quotient_closure_old_occurrence_entry. b = wpo_beta_quotient_closure_old_occurrence_entry * S ((S (wpo_index_closure_old_occurrence)) * c) + (m))))
  85. 0085specialize hclosed q
  86. 0086specialize hclosed s
  87. 0087specialize hclosed m
  88. 0088apply hclosed
  89. 0089exact hreflect_right_right_left
  90. 0090exact hreflect_right_right_right
  91. 0091exact hinverse
  92. 0092cases hold_occurrence
  93. 0093cases hold_occurrence_witness
  94. 0094exists x
  95. 0095split
  96. 0096have hlift : exists h. h + S x = S l
  97. 0097specialize le_succ (S x)
  98. 0098specialize le_succ l
  99. 0099apply le_succ
  100. 0100exact hold_occurrence_witness_left
  101. 0101specialize le_succ (S x)
  102. 0102specialize le_succ (S l)
  103. 0103apply le_succ
  104. 0104exact hlift
  105. 0105specialize htrace_parts_right_right x
  106. 0106specialize htrace_parts_right_right m
  107. 0107apply htrace_parts_right_right
  108. 0108exact hold_occurrence_witness_left
  109. 0109exact hold_occurrence_witness_right