PA00DD

eisenstein_row_indicator_prefix_exists

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

Every finite family of exact cell choices has a beta-coded row prefix.

Exact expanded PA statement

forall p q i l. (forall eri_column_row_indicator_exists_all. (exists eri_gap_row_indicator_exists_all_bound. eri_gap_row_indicator_exists_all_bound + S (eri_column_row_indicator_exists_all) = l) -> exists eri_bit_row_indicator_exists_all. (((eri_bit_row_indicator_exists_all = 0 /\ ((exists eri_gap_row_indicator_exists_all_choice_left. eri_gap_row_indicator_exists_all_choice_left + S (q * S i) = p * S eri_column_row_indicator_exists_all) /\ ~(exists eri_gap_row_indicator_exists_all_choice_right. eri_gap_row_indicator_exists_all_choice_right + S (p * S eri_column_row_indicator_exists_all) = q * S i))) \/ (eri_bit_row_indicator_exists_all = 1 /\ ((exists eri_gap_row_indicator_exists_all_choice_right. eri_gap_row_indicator_exists_all_choice_right + S (p * S eri_column_row_indicator_exists_all) = q * S i) /\ ~(exists eri_gap_row_indicator_exists_all_choice_left. eri_gap_row_indicator_exists_all_choice_left + S (q * S i) = p * S eri_column_row_indicator_exists_all)))))) -> (exists rb rc. (forall eri_column_row_indicator_exists_result. (exists eri_gap_row_indicator_exists_result_bound. eri_gap_row_indicator_exists_result_bound + S (eri_column_row_indicator_exists_result) = l) -> exists eri_bit_row_indicator_exists_result. ((((exists ff_h_eri_row_indicator_exists_result_decoded. ff_h_eri_row_indicator_exists_result_decoded + S (eri_bit_row_indicator_exists_result) = S ((S (eri_column_row_indicator_exists_result)) * rc)) /\ exists ff_q_eri_row_indicator_exists_result_decoded. rb = ff_q_eri_row_indicator_exists_result_decoded * S ((S (eri_column_row_indicator_exists_result)) * rc) + (eri_bit_row_indicator_exists_result))) /\ (((eri_bit_row_indicator_exists_result = 0 /\ ((exists eri_gap_row_indicator_exists_result_choice_left. eri_gap_row_indicator_exists_result_choice_left + S (q * S i) = p * S eri_column_row_indicator_exists_result) /\ ~(exists eri_gap_row_indicator_exists_result_choice_right. eri_gap_row_indicator_exists_result_choice_right + S (p * S eri_column_row_indicator_exists_result) = q * S i))) \/ (eri_bit_row_indicator_exists_result = 1 /\ ((exists eri_gap_row_indicator_exists_result_choice_right. eri_gap_row_indicator_exists_result_choice_right + S (p * S eri_column_row_indicator_exists_result) = q * S i) /\ ~(exists eri_gap_row_indicator_exists_result_choice_left. eri_gap_row_indicator_exists_result_choice_left + S (q * S i) = p * S eri_column_row_indicator_exists_result))))))))

Structural proof guide

Generated structural guide

Every finite family of exact cell choices has a beta-coded row prefix.

Use the direct prerequisites add_eq_zero_right, succ_ne_zero, le_succ, le_refl, eisenstein_row_indicator_prefix_extend as previously established PA formulas.

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

Referenced ingredients

PA0004 add_eq_zero_right PA0005 succ_ne_zero PA002O le_succ PA001A le_refl PA00DC eisenstein_row_indicator_prefix_extend

Proof neighborhood

Direct dependencies

PA0004 add_eq_zero_right PA0005 succ_ne_zero PA002O le_succ PA001A le_refl PA00DC eisenstein_row_indicator_prefix_extend

Direct dependents

PA00DF distinct_odd_prime_half_row_count_exists

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 p
  2. 0002intro q
  3. 0003intro i
  4. 0004induction l
  5. 0005intro hchoices
  6. 0006exists 0
  7. 0007exists 0
  8. 0008intro j
  9. 0009intro hj
  10. 0010exfalso
  11. 0011cases hj
  12. 0012have hsj : S j = 0
  13. 0013specialize add_eq_zero_right x
  14. 0014specialize add_eq_zero_right (S j)
  15. 0015apply add_eq_zero_right
  16. 0016exact hj_witness
  17. 0017specialize succ_ne_zero j
  18. 0018apply succ_ne_zero
  19. 0019exact hsj
  20. 0020intro hchoices
  21. 0021have hprevious_choices : forall eri_column_row_indicator_exists_previous_choices. (exists eri_gap_row_indicator_exists_previous_choices_bound. eri_gap_row_indicator_exists_previous_choices_bound + S (eri_column_row_indicator_exists_previous_choices) = l) -> exists eri_bit_row_indicator_exists_previous_choices. (((eri_bit_row_indicator_exists_previous_choices = 0 /\ ((exists eri_gap_row_indicator_exists_previous_choices_choice_left. eri_gap_row_indicator_exists_previous_choices_choice_left + S (q * S i) = p * S eri_column_row_indicator_exists_previous_choices) /\ ~(exists eri_gap_row_indicator_exists_previous_choices_choice_right. eri_gap_row_indicator_exists_previous_choices_choice_right + S (p * S eri_column_row_indicator_exists_previous_choices) = q * S i))) \/ (eri_bit_row_indicator_exists_previous_choices = 1 /\ ((exists eri_gap_row_indicator_exists_previous_choices_choice_right. eri_gap_row_indicator_exists_previous_choices_choice_right + S (p * S eri_column_row_indicator_exists_previous_choices) = q * S i) /\ ~(exists eri_gap_row_indicator_exists_previous_choices_choice_left. eri_gap_row_indicator_exists_previous_choices_choice_left + S (q * S i) = p * S eri_column_row_indicator_exists_previous_choices)))))
  22. 0022intro j
  23. 0023intro hj
  24. 0024specialize hchoices j
  25. 0025apply hchoices
  26. 0026specialize le_succ (S j)
  27. 0027specialize le_succ l
  28. 0028apply le_succ
  29. 0029exact hj
  30. 0030have hprevious : exists rb rc. (forall eri_column_row_indicator_exists_previous_prefix. (exists eri_gap_row_indicator_exists_previous_prefix_bound. eri_gap_row_indicator_exists_previous_prefix_bound + S (eri_column_row_indicator_exists_previous_prefix) = l) -> exists eri_bit_row_indicator_exists_previous_prefix. ((((exists ff_h_eri_row_indicator_exists_previous_prefix_decoded. ff_h_eri_row_indicator_exists_previous_prefix_decoded + S (eri_bit_row_indicator_exists_previous_prefix) = S ((S (eri_column_row_indicator_exists_previous_prefix)) * rc)) /\ exists ff_q_eri_row_indicator_exists_previous_prefix_decoded. rb = ff_q_eri_row_indicator_exists_previous_prefix_decoded * S ((S (eri_column_row_indicator_exists_previous_prefix)) * rc) + (eri_bit_row_indicator_exists_previous_prefix))) /\ (((eri_bit_row_indicator_exists_previous_prefix = 0 /\ ((exists eri_gap_row_indicator_exists_previous_prefix_choice_left. eri_gap_row_indicator_exists_previous_prefix_choice_left + S (q * S i) = p * S eri_column_row_indicator_exists_previous_prefix) /\ ~(exists eri_gap_row_indicator_exists_previous_prefix_choice_right. eri_gap_row_indicator_exists_previous_prefix_choice_right + S (p * S eri_column_row_indicator_exists_previous_prefix) = q * S i))) \/ (eri_bit_row_indicator_exists_previous_prefix = 1 /\ ((exists eri_gap_row_indicator_exists_previous_prefix_choice_right. eri_gap_row_indicator_exists_previous_prefix_choice_right + S (p * S eri_column_row_indicator_exists_previous_prefix) = q * S i) /\ ~(exists eri_gap_row_indicator_exists_previous_prefix_choice_left. eri_gap_row_indicator_exists_previous_prefix_choice_left + S (q * S i) = p * S eri_column_row_indicator_exists_previous_prefix)))))))
  31. 0031apply IH
  32. 0032exact hprevious_choices
  33. 0033cases hprevious
  34. 0034cases hprevious_witness
  35. 0035have hlast : exists bit. (((bit = 0 /\ ((exists eri_gap_row_indicator_exists_last_choice_left. eri_gap_row_indicator_exists_last_choice_left + S (q * S i) = p * S l) /\ ~(exists eri_gap_row_indicator_exists_last_choice_right. eri_gap_row_indicator_exists_last_choice_right + S (p * S l) = q * S i))) \/ (bit = 1 /\ ((exists eri_gap_row_indicator_exists_last_choice_right. eri_gap_row_indicator_exists_last_choice_right + S (p * S l) = q * S i) /\ ~(exists eri_gap_row_indicator_exists_last_choice_left. eri_gap_row_indicator_exists_last_choice_left + S (q * S i) = p * S l)))))
  36. 0036specialize hchoices l
  37. 0037apply hchoices
  38. 0038specialize le_refl (S l)
  39. 0039exact le_refl
  40. 0040have hnext : exists rb rc. (forall eri_column_row_indicator_exists_successor_prefix. (exists eri_gap_row_indicator_exists_successor_prefix_bound. eri_gap_row_indicator_exists_successor_prefix_bound + S (eri_column_row_indicator_exists_successor_prefix) = S l) -> exists eri_bit_row_indicator_exists_successor_prefix. ((((exists ff_h_eri_row_indicator_exists_successor_prefix_decoded. ff_h_eri_row_indicator_exists_successor_prefix_decoded + S (eri_bit_row_indicator_exists_successor_prefix) = S ((S (eri_column_row_indicator_exists_successor_prefix)) * rc)) /\ exists ff_q_eri_row_indicator_exists_successor_prefix_decoded. rb = ff_q_eri_row_indicator_exists_successor_prefix_decoded * S ((S (eri_column_row_indicator_exists_successor_prefix)) * rc) + (eri_bit_row_indicator_exists_successor_prefix))) /\ (((eri_bit_row_indicator_exists_successor_prefix = 0 /\ ((exists eri_gap_row_indicator_exists_successor_prefix_choice_left. eri_gap_row_indicator_exists_successor_prefix_choice_left + S (q * S i) = p * S eri_column_row_indicator_exists_successor_prefix) /\ ~(exists eri_gap_row_indicator_exists_successor_prefix_choice_right. eri_gap_row_indicator_exists_successor_prefix_choice_right + S (p * S eri_column_row_indicator_exists_successor_prefix) = q * S i))) \/ (eri_bit_row_indicator_exists_successor_prefix = 1 /\ ((exists eri_gap_row_indicator_exists_successor_prefix_choice_right. eri_gap_row_indicator_exists_successor_prefix_choice_right + S (p * S eri_column_row_indicator_exists_successor_prefix) = q * S i) /\ ~(exists eri_gap_row_indicator_exists_successor_prefix_choice_left. eri_gap_row_indicator_exists_successor_prefix_choice_left + S (q * S i) = p * S eri_column_row_indicator_exists_successor_prefix)))))))
  41. 0041specialize eisenstein_row_indicator_prefix_extend p
  42. 0042specialize eisenstein_row_indicator_prefix_extend q
  43. 0043specialize eisenstein_row_indicator_prefix_extend i
  44. 0044specialize eisenstein_row_indicator_prefix_extend x
  45. 0045specialize eisenstein_row_indicator_prefix_extend x1
  46. 0046specialize eisenstein_row_indicator_prefix_extend l
  47. 0047apply eisenstein_row_indicator_prefix_extend
  48. 0048exact hprevious_witness_witness
  49. 0049exact hlast
  50. 0050exact hnext