Section 4, proof (p. 232) — if 3 ≤ n ≤ 3m, P splits into three nonempty parts of size at most m
ProvedInteractiveConsistency.Impossibility.partition_of_le_three_mulbyzantine-agreementcombinatoricsdistributed-computingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite set with elements and let be a natural number. If
then can be partitioned into three nonempty, pairwise disjoint sets , , with , each of which has at most members.
This is the first step of the impossibility proof: each of , , then has at least members, so each may serve as the set of nonfaulty processors.
Formalization Note The page writes "Since "; the hypothesis needed for three nonempty parts is implicit there and is stated explicitly here.
Preamble
import Mathlib
Formal statement
namespace InteractiveConsistency.Impossibility
/-- Pease, Shostak & Lamport (1980), Section 4, proof of the THEOREM, p. 232: since `3 ≤ n ≤ 3m`
(`n = |P|`), `P` can be partitioned into three nonempty sets `A`, `B`, `C`, each of which has no
more than `m` members. -/
theorem partition_of_le_three_mul {α : Type*} [DecidableEq α] (P : Finset α) (m : ℕ)
(h3 : 3 ≤ P.card) (hn : P.card ≤ 3 * m) :
∃ A B C : Finset α,
A.Nonempty ∧ B.Nonempty ∧ C.Nonempty ∧
Disjoint A B ∧ Disjoint A C ∧ Disjoint B C ∧
A ∪ B ∪ C = P ∧
A.card ≤ m ∧ B.card ≤ m ∧ C.card ≤ m := by sorry
end InteractiveConsistency.Impossibility
Source
Pease, Shostak & Lamport, Reaching agreement in the presence of faults, J. ACM 27 (1980), p. 232, Section 4, proof of the THEOREM, first paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.