PA0048

bit_count_zero

Stable checked-use theorem · independently closed

An empty bit prefix contains zero ones.

Exact expanded PA statement

forall b c l n. l = 0 -> (((exists ff_u_zero_sum ff_v_zero_sum. ((((exists ff_h_zero_sum_start. ff_h_zero_sum_start + S (0) = S ((S (0)) * ff_v_zero_sum)) /\ exists ff_q_zero_sum_start. ff_u_zero_sum = ff_q_zero_sum_start * S ((S (0)) * ff_v_zero_sum) + (0))) /\ ((((exists ff_h_zero_sum_terminal. ff_h_zero_sum_terminal + S (n) = S ((S (l)) * ff_v_zero_sum)) /\ exists ff_q_zero_sum_terminal. ff_u_zero_sum = ff_q_zero_sum_terminal * S ((S (l)) * ff_v_zero_sum) + (n))) /\ forall ff_i_zero_sum. (exists ff_lt_zero_sum_bound. ff_lt_zero_sum_bound + S ff_i_zero_sum = l) -> exists ff_a_zero_sum ff_r_zero_sum ff_s_zero_sum. ((((exists ff_h_zero_sum_summand. ff_h_zero_sum_summand + S (ff_a_zero_sum) = S ((S (ff_i_zero_sum)) * c)) /\ exists ff_q_zero_sum_summand. b = ff_q_zero_sum_summand * S ((S (ff_i_zero_sum)) * c) + (ff_a_zero_sum))) /\ ((((exists ff_h_zero_sum_partial. ff_h_zero_sum_partial + S (ff_r_zero_sum) = S ((S (ff_i_zero_sum)) * ff_v_zero_sum)) /\ exists ff_q_zero_sum_partial. ff_u_zero_sum = ff_q_zero_sum_partial * S ((S (ff_i_zero_sum)) * ff_v_zero_sum) + (ff_r_zero_sum))) /\ ((((exists ff_h_zero_sum_successor. ff_h_zero_sum_successor + S (ff_s_zero_sum) = S ((S (S ff_i_zero_sum)) * ff_v_zero_sum)) /\ exists ff_q_zero_sum_successor. ff_u_zero_sum = ff_q_zero_sum_successor * S ((S (S ff_i_zero_sum)) * ff_v_zero_sum) + (ff_s_zero_sum))) /\ ff_s_zero_sum = ff_r_zero_sum + ff_a_zero_sum)))))) /\ (forall ff_i_zero_bits. (exists ff_lt_zero_bits_bound. ff_lt_zero_bits_bound + S ff_i_zero_bits = l) -> exists ff_bit_zero_bits. ((((exists ff_h_zero_bits_decoded. ff_h_zero_bits_decoded + S (ff_bit_zero_bits) = S ((S (ff_i_zero_bits)) * c)) /\ exists ff_q_zero_bits_decoded. b = ff_q_zero_bits_decoded * S ((S (ff_i_zero_bits)) * c) + (ff_bit_zero_bits))) /\ (ff_bit_zero_bits = 0 \/ ff_bit_zero_bits = 1))))) -> n = 0

Structural proof guide

Generated structural guide

An empty bit prefix contains zero ones.

Use the direct prerequisites beta_sum_zero as previously established PA formulas.

The proof proceeds by case analysis (1), equality transport (3).

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.

  1. 0001intro b
  2. 0002intro c
  3. 0003intro l
  4. 0004intro n
  5. 0005intro hl
  6. 0006intro hcount
  7. 0007rewrite hl at hcount
  8. 0008rewrite hl at hcount
  9. 0009rewrite hl at hcount
  10. 0010cases hcount
  11. 0011specialize beta_sum_zero b
  12. 0012specialize beta_sum_zero c
  13. 0013specialize beta_sum_zero n
  14. 0014apply beta_sum_zero
  15. 0015exact hcount_left