BA0042

continued_fraction_convergent_index_is_valid

The actual prefix computation proves the advertised index belongs to the complete G071 list; it is not merely a tagged pair of positive integers.

Alpha v34 checked-use · first admitted v29 · independently kernel and Lean verified; not Stable

Current library: Alpha v34, 4,223 checked-use theorems; Stable remains 432. Historical first admissions, original proof editions, and non-admitted aliases are preserved. Exact original first-admission records.

The initial 0/1 convergent is included: u is natural, not necessarily positive. Comparison denominators are strictly smaller and positive. Signed competitors are represented by an arbitrary difference rp−rn. Approximation inequalities are proved from the trace, never stored as assumptions in Convergent.

Exact theorem in conservative defined notation

∀ a. ∀ b. ∀ s. ∀ h. ∀ e. ∀ L. ∀ i. ∀ u. ∀ v. ContinuedFractionTrace(a,b,s,h,e,L)Convergent(s,i,u,v)Lt(i,L)

Every linked abbreviation expands hygienically to the identical original native formula.

Definition DAG

Actual proof prerequisites

Original expanded first-order statement
forall a b s h e L i u v. (exists cf_gcd_convergent_index_history. ((((exists ff_h_cf_convergent_index_history_initial_state. ff_h_cf_convergent_index_history_initial_state + S (((cf_gcd_convergent_index_history) + (((0) + (0)) * S ((0) + (0)) + ((0) + (0)))) * S ((cf_gcd_convergent_index_history) + (((0) + (0)) * S ((0) + (0)) + ((0) + (0)))) + ((((0) + (0)) * S ((0) + (0)) + ((0) + (0))) + (((0) + (0)) * S ((0) + (0)) + ((0) + (0))))) = S ((S (0)) * e)) /\ exists ff_q_cf_convergent_index_history_initial_state. h = ff_q_cf_convergent_index_history_initial_state * S ((S (0)) * e) + (((cf_gcd_convergent_index_history) + (((0) + (0)) * S ((0) + (0)) + ((0) + (0)))) * S ((cf_gcd_convergent_index_history) + (((0) + (0)) * S ((0) + (0)) + ((0) + (0)))) + ((((0) + (0)) * S ((0) + (0)) + ((0) + (0))) + (((0) + (0)) * S ((0) + (0)) + ((0) + (0))))))) /\ ((((exists ff_h_cf_convergent_index_history_terminal_state. ff_h_cf_convergent_index_history_terminal_state + S (((a) + (((b) + (s)) * S ((b) + (s)) + ((s) + (s)))) * S ((a) + (((b) + (s)) * S ((b) + (s)) + ((s) + (s)))) + ((((b) + (s)) * S ((b) + (s)) + ((s) + (s))) + (((b) + (s)) * S ((b) + (s)) + ((s) + (s))))) = S ((S (L)) * e)) /\ exists ff_q_cf_convergent_index_history_terminal_state. h = ff_q_cf_convergent_index_history_terminal_state * S ((S (L)) * e) + (((a) + (((b) + (s)) * S ((b) + (s)) + ((s) + (s)))) * S ((a) + (((b) + (s)) * S ((b) + (s)) + ((s) + (s)))) + ((((b) + (s)) * S ((b) + (s)) + ((s) + (s))) + (((b) + (s)) * S ((b) + (s)) + ((s) + (s))))))) /\ forall cf_index_convergent_index_history. (exists ff_lt_cf_convergent_index_history_index. ff_lt_cf_convergent_index_history_index + S cf_index_convergent_index_history = L) -> exists cf_old_a_convergent_index_history cf_old_b_convergent_index_history cf_tail_convergent_index_history cf_new_a_convergent_index_history cf_new_b_convergent_index_history cf_head_convergent_index_history cf_quotient_convergent_index_history. ((((exists ff_h_cf_convergent_index_history_previous_state. ff_h_cf_convergent_index_history_previous_state + S (((cf_old_a_convergent_index_history) + (((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) * S ((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) + ((cf_tail_convergent_index_history) + (cf_tail_convergent_index_history)))) * S ((cf_old_a_convergent_index_history) + (((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) * S ((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) + ((cf_tail_convergent_index_history) + (cf_tail_convergent_index_history)))) + ((((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) * S ((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) + ((cf_tail_convergent_index_history) + (cf_tail_convergent_index_history))) + (((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) * S ((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) + ((cf_tail_convergent_index_history) + (cf_tail_convergent_index_history))))) = S ((S (cf_index_convergent_index_history)) * e)) /\ exists ff_q_cf_convergent_index_history_previous_state. h = ff_q_cf_convergent_index_history_previous_state * S ((S (cf_index_convergent_index_history)) * e) + (((cf_old_a_convergent_index_history) + (((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) * S ((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) + ((cf_tail_convergent_index_history) + (cf_tail_convergent_index_history)))) * S ((cf_old_a_convergent_index_history) + (((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) * S ((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) + ((cf_tail_convergent_index_history) + (cf_tail_convergent_index_history)))) + ((((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) * S ((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) + ((cf_tail_convergent_index_history) + (cf_tail_convergent_index_history))) + (((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) * S ((cf_old_b_convergent_index_history) + (cf_tail_convergent_index_history)) + ((cf_tail_convergent_index_history) + (cf_tail_convergent_index_history))))))) /\ ((((exists ff_h_cf_convergent_index_history_following_state. ff_h_cf_convergent_index_history_following_state + S (((cf_new_a_convergent_index_history) + (((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) * S ((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) + ((cf_head_convergent_index_history) + (cf_head_convergent_index_history)))) * S ((cf_new_a_convergent_index_history) + (((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) * S ((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) + ((cf_head_convergent_index_history) + (cf_head_convergent_index_history)))) + ((((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) * S ((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) + ((cf_head_convergent_index_history) + (cf_head_convergent_index_history))) + (((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) * S ((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) + ((cf_head_convergent_index_history) + (cf_head_convergent_index_history))))) = S ((S (S cf_index_convergent_index_history)) * e)) /\ exists ff_q_cf_convergent_index_history_following_state. h = ff_q_cf_convergent_index_history_following_state * S ((S (S cf_index_convergent_index_history)) * e) + (((cf_new_a_convergent_index_history) + (((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) * S ((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) + ((cf_head_convergent_index_history) + (cf_head_convergent_index_history)))) * S ((cf_new_a_convergent_index_history) + (((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) * S ((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) + ((cf_head_convergent_index_history) + (cf_head_convergent_index_history)))) + ((((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) * S ((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) + ((cf_head_convergent_index_history) + (cf_head_convergent_index_history))) + (((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) * S ((cf_new_b_convergent_index_history) + (cf_head_convergent_index_history)) + ((cf_head_convergent_index_history) + (cf_head_convergent_index_history))))))) /\ (cf_new_b_convergent_index_history = cf_old_a_convergent_index_history /\ (cf_new_a_convergent_index_history = cf_new_b_convergent_index_history * cf_quotient_convergent_index_history + cf_old_b_convergent_index_history /\ ((exists ff_lt_cf_convergent_index_history_remainder. ff_lt_cf_convergent_index_history_remainder + S cf_old_b_convergent_index_history = cf_new_b_convergent_index_history) /\ (cf_head_convergent_index_history = S ((cf_quotient_convergent_index_history + cf_tail_convergent_index_history) * S (cf_quotient_convergent_index_history + cf_tail_convergent_index_history) + (cf_tail_convergent_index_history + cf_tail_convergent_index_history))))))))))) -> (exists cfc_previous_numerator_existing_convergent cfc_previous_denominator_existing_convergent cfc_code_existing_convergent cfc_scale_existing_convergent. ((~(v = 0)) /\ (exists cfc_tail_existing_convergentcomputation. ((exists cfc_state_existing_convergentcomputationinitial. ((exists cfc_left_existing_convergentcomputationinitialcode cfc_right_existing_convergentcomputationinitialcode cfc_matrix_existing_convergentcomputationinitialcode. ((cfc_left_existing_convergentcomputationinitialcode = ((1) + (0)) * S ((1) + (0)) + ((0) + (0))) /\ ((cfc_right_existing_convergentcomputationinitialcode = ((0) + (1)) * S ((0) + (1)) + ((1) + (1))) /\ ((cfc_matrix_existing_convergentcomputationinitialcode = ((cfc_left_existing_convergentcomputationinitialcode) + (cfc_right_existing_convergentcomputationinitialcode)) * S ((cfc_left_existing_convergentcomputationinitialcode) + (cfc_right_existing_convergentcomputationinitialcode)) + ((cfc_right_existing_convergentcomputationinitialcode) + (cfc_right_existing_convergentcomputationinitialcode))) /\ ((cfc_state_existing_convergentcomputationinitial) = ((cfc_tail_existing_convergentcomputation) + (cfc_matrix_existing_convergentcomputationinitialcode)) * S ((cfc_tail_existing_convergentcomputation) + (cfc_matrix_existing_convergentcomputationinitialcode)) + ((cfc_matrix_existing_convergentcomputationinitialcode) + (cfc_matrix_existing_convergentcomputationinitialcode))))))) /\ (((exists ff_h_existing_convergentcomputationinitialentry. ff_h_existing_convergentcomputationinitialentry + S (cfc_state_existing_convergentcomputationinitial) = S ((S (0)) * cfc_scale_existing_convergent)) /\ exists ff_q_existing_convergentcomputationinitialentry. cfc_code_existing_convergent = ff_q_existing_convergentcomputationinitialentry * S ((S (0)) * cfc_scale_existing_convergent) + (cfc_state_existing_convergentcomputationinitial))))) /\ ((exists cfc_state_existing_convergentcomputationterminal. ((exists cfc_left_existing_convergentcomputationterminalcode cfc_right_existing_convergentcomputationterminalcode cfc_matrix_existing_convergentcomputationterminalcode. ((cfc_left_existing_convergentcomputationterminalcode = ((u) + (cfc_previous_numerator_existing_convergent)) * S ((u) + (cfc_previous_numerator_existing_convergent)) + ((cfc_previous_numerator_existing_convergent) + (cfc_previous_numerator_existing_convergent))) /\ ((cfc_right_existing_convergentcomputationterminalcode = ((v) + (cfc_previous_denominator_existing_convergent)) * S ((v) + (cfc_previous_denominator_existing_convergent)) + ((cfc_previous_denominator_existing_convergent) + (cfc_previous_denominator_existing_convergent))) /\ ((cfc_matrix_existing_convergentcomputationterminalcode = ((cfc_left_existing_convergentcomputationterminalcode) + (cfc_right_existing_convergentcomputationterminalcode)) * S ((cfc_left_existing_convergentcomputationterminalcode) + (cfc_right_existing_convergentcomputationterminalcode)) + ((cfc_right_existing_convergentcomputationterminalcode) + (cfc_right_existing_convergentcomputationterminalcode))) /\ ((cfc_state_existing_convergentcomputationterminal) = ((s) + (cfc_matrix_existing_convergentcomputationterminalcode)) * S ((s) + (cfc_matrix_existing_convergentcomputationterminalcode)) + ((cfc_matrix_existing_convergentcomputationterminalcode) + (cfc_matrix_existing_convergentcomputationterminalcode))))))) /\ (((exists ff_h_existing_convergentcomputationterminalentry. ff_h_existing_convergentcomputationterminalentry + S (cfc_state_existing_convergentcomputationterminal) = S ((S (S (i))) * cfc_scale_existing_convergent)) /\ exists ff_q_existing_convergentcomputationterminalentry. cfc_code_existing_convergent = ff_q_existing_convergentcomputationterminalentry * S ((S (S (i))) * cfc_scale_existing_convergent) + (cfc_state_existing_convergentcomputationterminal))))) /\ (forall cfc_index_existing_convergentcomputation. (exists cfba_gap_existing_convergentcomputationbound. cfba_gap_existing_convergentcomputationbound + S (cfc_index_existing_convergentcomputation) = (S (i))) -> exists cfc_old_existing_convergentcomputation cfc_a_existing_convergentcomputation cfc_b_existing_convergentcomputation cfc_c_existing_convergentcomputation cfc_d_existing_convergentcomputation cfc_new_existing_convergentcomputation cfc_quotient_existing_convergentcomputation. ((exists cfc_state_existing_convergentcomputationprevious. ((exists cfc_left_existing_convergentcomputationpreviouscode cfc_right_existing_convergentcomputationpreviouscode cfc_matrix_existing_convergentcomputationpreviouscode. ((cfc_left_existing_convergentcomputationpreviouscode = ((cfc_a_existing_convergentcomputation) + (cfc_b_existing_convergentcomputation)) * S ((cfc_a_existing_convergentcomputation) + (cfc_b_existing_convergentcomputation)) + ((cfc_b_existing_convergentcomputation) + (cfc_b_existing_convergentcomputation))) /\ ((cfc_right_existing_convergentcomputationpreviouscode = ((cfc_c_existing_convergentcomputation) + (cfc_d_existing_convergentcomputation)) * S ((cfc_c_existing_convergentcomputation) + (cfc_d_existing_convergentcomputation)) + ((cfc_d_existing_convergentcomputation) + (cfc_d_existing_convergentcomputation))) /\ ((cfc_matrix_existing_convergentcomputationpreviouscode = ((cfc_left_existing_convergentcomputationpreviouscode) + (cfc_right_existing_convergentcomputationpreviouscode)) * S ((cfc_left_existing_convergentcomputationpreviouscode) + (cfc_right_existing_convergentcomputationpreviouscode)) + ((cfc_right_existing_convergentcomputationpreviouscode) + (cfc_right_existing_convergentcomputationpreviouscode))) /\ ((cfc_state_existing_convergentcomputationprevious) = ((cfc_old_existing_convergentcomputation) + (cfc_matrix_existing_convergentcomputationpreviouscode)) * S ((cfc_old_existing_convergentcomputation) + (cfc_matrix_existing_convergentcomputationpreviouscode)) + ((cfc_matrix_existing_convergentcomputationpreviouscode) + (cfc_matrix_existing_convergentcomputationpreviouscode))))))) /\ (((exists ff_h_existing_convergentcomputationpreviousentry. ff_h_existing_convergentcomputationpreviousentry + S (cfc_state_existing_convergentcomputationprevious) = S ((S (cfc_index_existing_convergentcomputation)) * cfc_scale_existing_convergent)) /\ exists ff_q_existing_convergentcomputationpreviousentry. cfc_code_existing_convergent = ff_q_existing_convergentcomputationpreviousentry * S ((S (cfc_index_existing_convergentcomputation)) * cfc_scale_existing_convergent) + (cfc_state_existing_convergentcomputationprevious))))) /\ ((exists cfc_state_existing_convergentcomputationfollowing. ((exists cfc_left_existing_convergentcomputationfollowingcode cfc_right_existing_convergentcomputationfollowingcode cfc_matrix_existing_convergentcomputationfollowingcode. ((cfc_left_existing_convergentcomputationfollowingcode = (((cfc_quotient_existing_convergentcomputation * cfc_a_existing_convergentcomputation + cfc_c_existing_convergentcomputation)) + ((cfc_quotient_existing_convergentcomputation * cfc_b_existing_convergentcomputation + cfc_d_existing_convergentcomputation))) * S (((cfc_quotient_existing_convergentcomputation * cfc_a_existing_convergentcomputation + cfc_c_existing_convergentcomputation)) + ((cfc_quotient_existing_convergentcomputation * cfc_b_existing_convergentcomputation + cfc_d_existing_convergentcomputation))) + (((cfc_quotient_existing_convergentcomputation * cfc_b_existing_convergentcomputation + cfc_d_existing_convergentcomputation)) + ((cfc_quotient_existing_convergentcomputation * cfc_b_existing_convergentcomputation + cfc_d_existing_convergentcomputation)))) /\ ((cfc_right_existing_convergentcomputationfollowingcode = ((cfc_a_existing_convergentcomputation) + (cfc_b_existing_convergentcomputation)) * S ((cfc_a_existing_convergentcomputation) + (cfc_b_existing_convergentcomputation)) + ((cfc_b_existing_convergentcomputation) + (cfc_b_existing_convergentcomputation))) /\ ((cfc_matrix_existing_convergentcomputationfollowingcode = ((cfc_left_existing_convergentcomputationfollowingcode) + (cfc_right_existing_convergentcomputationfollowingcode)) * S ((cfc_left_existing_convergentcomputationfollowingcode) + (cfc_right_existing_convergentcomputationfollowingcode)) + ((cfc_right_existing_convergentcomputationfollowingcode) + (cfc_right_existing_convergentcomputationfollowingcode))) /\ ((cfc_state_existing_convergentcomputationfollowing) = ((cfc_new_existing_convergentcomputation) + (cfc_matrix_existing_convergentcomputationfollowingcode)) * S ((cfc_new_existing_convergentcomputation) + (cfc_matrix_existing_convergentcomputationfollowingcode)) + ((cfc_matrix_existing_convergentcomputationfollowingcode) + (cfc_matrix_existing_convergentcomputationfollowingcode))))))) /\ (((exists ff_h_existing_convergentcomputationfollowingentry. ff_h_existing_convergentcomputationfollowingentry + S (cfc_state_existing_convergentcomputationfollowing) = S ((S (S cfc_index_existing_convergentcomputation)) * cfc_scale_existing_convergent)) /\ exists ff_q_existing_convergentcomputationfollowingentry. cfc_code_existing_convergent = ff_q_existing_convergentcomputationfollowingentry * S ((S (S cfc_index_existing_convergentcomputation)) * cfc_scale_existing_convergent) + (cfc_state_existing_convergentcomputationfollowing))))) /\ (cfc_new_existing_convergentcomputation = S ((cfc_quotient_existing_convergentcomputation + cfc_old_existing_convergentcomputation) * S (cfc_quotient_existing_convergentcomputation + cfc_old_existing_convergentcomputation) + (cfc_old_existing_convergentcomputation + cfc_old_existing_convergentcomputation))))))))))) -> (exists cfba_gap_convergent_index_valid. cfba_gap_convergent_index_valid + S (i) = (L))

Complete tactic proof in conservative notation

All 32 original proof lines are preserved. Only local proposition formulas are abbreviated; every abbreviation has an exact binder-safe expansion check. The linked exact edition contains the unchanged replay script.

Read the argument

Proof checkpoints

32 script commands · 5 reading checkpoints · 0 local claims

This is a reading aid, not a new proof or a proof-tree certificate. Checkpoint groups are consecutive commands, not inferred branch boundaries. Every step links to the preserved script.

Definition notation is shown below. Open the paired exact edition for the original native formulas. Source pairing is not a new equivalence certificate.

Named ingredients (1)
01Fix variables and assumptionsL1–10

Work with arbitrary variables or the premises of the current implication.

  1. L1
    intro a
  2. L2
    intro b
  3. L3
    intro s
  4. L4
    intro h
  5. L5
    intro e
  6. L6
    intro L
  7. L7
    intro i
  8. L8
    intro u
  9. L9
    intro v
  10. L10
    intro ht
02Fix variables and assumptionsL11–11

Work with arbitrary variables or the premises of the current implication.

  1. L11
    intro hc
03Separate the logical casesL12–16

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L12
    cases hc
  2. L13
    cases hc_witness
  3. L14
    cases hc_witness_witness
  4. L15
    cases hc_witness_witness_witness
  5. L16
    cases hc_witness_witness_witness_witness
04Use earlier factsL17–26

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L17
    specialize cf_convergent_actual_prefix_index_bound (S i)
  2. L18
    specialize cf_convergent_actual_prefix_index_bound (a)
  3. L19
    specialize cf_convergent_actual_prefix_index_bound (b)
  4. L20
    specialize cf_convergent_actual_prefix_index_bound (s)
  5. L21
    specialize cf_convergent_actual_prefix_index_bound (h)
  6. L22
    specialize cf_convergent_actual_prefix_index_bound (e)
  7. L23
    specialize cf_convergent_actual_prefix_index_bound (L)
  8. L24
    specialize cf_convergent_actual_prefix_index_bound (x2)
  9. L25
    specialize cf_convergent_actual_prefix_index_bound (x3)
  10. L26
    specialize cf_convergent_actual_prefix_index_bound (u)
05Use earlier factsL27–32

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L27
    specialize cf_convergent_actual_prefix_index_bound (x)
  2. L28
    specialize cf_convergent_actual_prefix_index_bound (v)
  3. L29
    specialize cf_convergent_actual_prefix_index_bound (x1)
  4. L30
    apply cf_convergent_actual_prefix_index_bound
  5. L31
    exact ht
  6. L32
    exact hc_witness_witness_witness_witness_right

Library-wide reading audit

Original defined command ledger · 32 lines
  1. 0001intro a
  2. 0002intro b
  3. 0003intro s
  4. 0004intro h
  5. 0005intro e
  6. 0006intro L
  7. 0007intro i
  8. 0008intro u
  9. 0009intro v
  10. 0010intro ht
  11. 0011intro hc
  12. 0012cases hc
  13. 0013cases hc_witness
  14. 0014cases hc_witness_witness
  15. 0015cases hc_witness_witness_witness
  16. 0016cases hc_witness_witness_witness_witness
  17. 0017specialize cf_convergent_actual_prefix_index_bound (S i)
  18. 0018specialize cf_convergent_actual_prefix_index_bound (a)
  19. 0019specialize cf_convergent_actual_prefix_index_bound (b)
  20. 0020specialize cf_convergent_actual_prefix_index_bound (s)
  21. 0021specialize cf_convergent_actual_prefix_index_bound (h)
  22. 0022specialize cf_convergent_actual_prefix_index_bound (e)
  23. 0023specialize cf_convergent_actual_prefix_index_bound (L)
  24. 0024specialize cf_convergent_actual_prefix_index_bound (x2)
  25. 0025specialize cf_convergent_actual_prefix_index_bound (x3)
  26. 0026specialize cf_convergent_actual_prefix_index_bound (u)
  27. 0027specialize cf_convergent_actual_prefix_index_bound (x)
  28. 0028specialize cf_convergent_actual_prefix_index_bound (v)
  29. 0029specialize cf_convergent_actual_prefix_index_bound (x1)
  30. 0030apply cf_convergent_actual_prefix_index_bound
  31. 0031exact ht
  32. 0032exact hc_witness_witness_witness_witness_right