AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_majority_growth

theoremverified

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

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}}|$.

  1. 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.

    lines 7–14

    uses Finset.disjoint_left.mpr, Finset.mem_image.mp

      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)
  2. 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`.

    lines 15–19

    uses Finset.card_union_of_disjoint, Finset.card_image_of_injective

      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]
  3. 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$.

    lines 20–22

    uses Finset.card_filter_add_card_filter_not

      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))
  4. 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`.

    lines 23–27

      by_cases h : (S.filter fun a => color a = true).card ≤
          (S.filter fun a => color a = false).card
      · refine ⟨false, ?_⟩
        rw [hcard]
        omega
  5. 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.

    lines 28–30

      · 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.

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

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
See it in the graphDiscuss this resultChallenge it