Section 3, Induction Step ¶4 (p. 231) — Q̂ = Q − {q} has ≥ ⌊(n+m)/2⌋ members and satisfies step (1) of the recursive call
ProvedInteractiveConsistency.OralAlgorithm.hat_quorum_step_oneLet be a finite set of processors, , , and a processor. Suppose has more than members and satisfies for every string over with (so and satisfy step (1) for and ). Let . Then
- ;
- ;
- ;
- for every and every string over with ,
Items 1, 3 and 4 say that and satisfy step (1) of the recursive call (for faults, processor set , view ) for every target ; item 2 is the count step (2) needs. In the paper's proof this is the parenthetical remark that settles the case where exits at step (1) and executes step (2).
Formalization Note. The page prints ""; the first is a printed slip for , and the statement uses directly: item 4 is σ (p' :: ((w ++ [q']) ++ [q])) = v. is (P.card + (m' + 1)) / 2 and item 3 is (P.erase q).card + m' < 2 * (Q.erase q).card.
import Mathlib import Definitions.Def_InteractiveConsistency_OralAlgorithm_Scenario
namespace InteractiveConsistency.OralAlgorithm
theorem hat_quorum_step_one {α V : Type*} [DecidableEq α] (P : Finset α) (m' : ℕ)
(σ : List α → V) (p' q : α) (hqP : q ∈ P)
(Q : Finset α) (hQP : Q ⊆ P) (hQcard : P.card + (m' + 1) < 2 * Q.card) (v : V)
(hv : ∀ w : List α, IsStringOver Q w → w.length ≤ m' + 1 → σ (p' :: (w ++ [q])) = v) :
Q.erase q ⊆ P.erase q ∧
(P.card + (m' + 1)) / 2 ≤ (Q.erase q).card ∧
(P.erase q).card + m' < 2 * (Q.erase q).card ∧
∀ q' ∈ Q.erase q, ∀ w : List α, IsStringOver (Q.erase q) w → w.length ≤ m' →
σ (p' :: ((w ++ [q']) ++ [q])) = v := by sorry
end InteractiveConsistency.OralAlgorithm
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.