prioritized_borel_fork_majority_growth
If every history has a distinct stay extension and a distinct excursion extension colored by a bit, some common visible bit yields at least three halves as many histories.
Statement
theorem prioritized_borel_fork_majority_growth {α : Type} [DecidableEq α] (S : Finset α) (stay exit : α → α) (hs : Function.Injective stay) (he : Function.Injective exit) (hdiff : ∀ a b, stay a ≠ exit b) (color : α → Bool) : ∃ bit, 3 * S.card ≤ 2 * ((S.image stay) ∪ ((S.filter fun a => color a = bit).image exit)).card
- Source
- arXiv:2611.10136, Section 5.3.2, smallest lower-bound arena; three-move fork obstruction
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- prioritized_borel_fork_exponential_historiesFor every history-dependent excursion response and every n, some common n-block output has at least (3/2)^n compatible hidden histories.
- prioritized_borel_fork_prefix_chainFor every n, there is a visible n-block word such that every prefix of length k admits at least k+1 compatible hidden histories.
The proof, explained
The proof uses the pigeonhole principle on the two color classes: at least one boolean bit (true or false) must label at least half of the elements in $S$. Because the injective maps `stay` and `exit` have disjoint ranges, the union of $\text{stay}(S)$ and the exit image of the chosen color class consists of two disjoint sets of size $|S|$ and $|S_{\text{bit}}|$ respectively. Selecting the majority bit ensures that $|S_{\text{bit}}| \ge \frac{1}{2}|S|$, so the union has cardinality at least $\frac{3}{2}|S|$, which is equivalent to $3 |S| \le 2 |T_{\text{bit}}|$.
For any boolean bit, the stay image of $S$ and the exit image of the bit-colored elements of $S$ are disjoint.
By `Finset.disjoint_left.mpr`, it suffices to show that no element $x$ lies in both sets. If $x$ were in both images, then by `Finset.mem_image.mp` there would exist $a, b \in S$ such that $\text{stay}(a) = x = \text{exit}(b)$, directly contradicting the hypothesis `hdiff` that the ranges of `stay` and `exit` are disjoint.
uses
Finset.disjoint_left.mpr,Finset.mem_image.mpclassical have hdisj (bit : Bool) : Disjoint (S.image stay) ((S.filter fun a => color a = bit).image exit) := by apply Finset.disjoint_left.mpr intro x hx hy obtain ⟨a, ha, hax⟩ := Finset.mem_image.mp hx obtain ⟨b, hb, hbx⟩ := Finset.mem_image.mp hy exact hdiff a b (hax.trans hbx.symm)
For any boolean bit, the cardinality of the union of $\text{stay}(S)$ and $\text{exit}(\{a \in S \mid \text{color}(a) = \text{bit}\})$ equals $|S| + |\{a \in S \mid \text{color}(a) = \text{bit}\}|$.
Because the two sets are disjoint, the size of their union is the sum of their sizes by `Finset.card_union_of_disjoint`. Furthermore, because both `stay` and `exit` are injective maps, the cardinality of each image equals the cardinality of its domain by `Finset.card_image_of_injective`.
uses
Finset.card_union_of_disjoint,Finset.card_image_of_injectivehave hcard (bit : Bool) : ((S.image stay) ∪ ((S.filter fun a => color a = bit).image exit)).card = S.card + (S.filter fun a => color a = bit).card := by rw [Finset.card_union_of_disjoint (hdisj bit), Finset.card_image_of_injective _ hs, Finset.card_image_of_injective _ he]
The sum of the sizes of the true and false color classes equals $|S|$.
Filtering by $\text{color}(a) = \text{true}$ partitions $S$ into the elements colored true and those colored false. By `Finset.card_filter_add_card_filter_not`, the sum of the sizes of the elements satisfying the predicate and those satisfying its negation equals the size of $S$.
uses
Finset.card_filter_add_card_filter_nothave hp : (S.filter fun a => color a = true).card + (S.filter fun a => color a = false).card = S.card := by simpa using (Finset.card_filter_add_card_filter_not (s := S) (fun a => color a = true))
If false is at least as common as true, choosing $\text{bit} = \text{false}$ satisfies the growth inequality $3 |S| \le 2 |T_{\text{false}}|$. automation
We split into cases based on whether $|\{a \in S \mid \text{color}(a) = \text{true}\}| \le |\{a \in S \mid \text{color}(a) = \text{false}\}|$. In this branch, `false` is the majority bit, which means $2 |\{a \in S \mid \text{color}(a) = \text{false}\}| \ge |S|$. Rewriting the cardinality of the union with the formula established in step 2, the goal reduces to linear arithmetic on natural numbers, solved by `omega`.
by_cases h : (S.filter fun a => color a = true).card ≤ (S.filter fun a => color a = false).card · refine ⟨false, ?_⟩ rw [hcard] omega
If true is strictly more common than false, choosing $\text{bit} = \text{true}$ satisfies the growth inequality $3 |S| \le 2 |T_{\text{true}}|$. automation
In the opposite case, `true` is the majority bit, so $2 |\{a \in S \mid \text{color}(a) = \text{true}\}| \ge |S|$. Rewriting the size of the union with the formula from step 2, linear integer arithmetic (`omega`) closes the goal.
· refine ⟨true, ?_⟩ rw [hcard] omega
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element of the first belongs to the second.
Finset.mem_image.mp- An element is in the image of a set under a function if and only if it is the image of some element in that set.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the original set.
Finset.card_filter_add_card_filter_not- For any predicate on a finite set, the number of elements satisfying it plus the number of elements not satisfying it equals the cardinality of the set.
- In lines 27 and 30, the linear integer arithmetic tactic `omega` automatically derives the inequality $3 |S| \le 2(|S| + |S_{\text{bit}}|)$ by combining the partition equation $|S_{\text{true}}| + |S_{\text{false}}| = |S|$ with the respective majority assumption.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem prioritized_borel_fork_majority_growth {α : Type} [DecidableEq α] (S : Finset α) (stay exit : α → α) (hs : Function.Injective stay) (he : Function.Injective exit) (hdiff : ∀ a b, stay a ≠ exit b) (color : α → Bool) : ∃ bit, 3 * S.card ≤ 2 * ((S.image stay) ∪ ((S.filter fun a => color a = bit).image exit)).card := by classical have hdisj (bit : Bool) : Disjoint (S.image stay) ((S.filter fun a => color a = bit).image exit) := by apply Finset.disjoint_left.mpr intro x hx hy obtain ⟨a, ha, hax⟩ := Finset.mem_image.mp hx obtain ⟨b, hb, hbx⟩ := Finset.mem_image.mp hy exact hdiff a b (hax.trans hbx.symm) have hcard (bit : Bool) : ((S.image stay) ∪ ((S.filter fun a => color a = bit).image exit)).card = S.card + (S.filter fun a => color a = bit).card := by rw [Finset.card_union_of_disjoint (hdisj bit), Finset.card_image_of_injective _ hs, Finset.card_image_of_injective _ he] have hp : (S.filter fun a => color a = true).card + (S.filter fun a => color a = false).card = S.card := by simpa using (Finset.card_filter_add_card_filter_not (s := S) (fun a => color a = true)) by_cases h : (S.filter fun a => color a = true).card ≤ (S.filter fun a => color a = false).card · refine ⟨false, ?_⟩ rw [hcard] omega · refine ⟨true, ?_⟩ rw [hcard] omega