AFTD Auto-Formalizing Theoretical Domains

finite_lopsided_avoidance_of_card_bound

theoremverified

In a nonempty finite probability universe, finite bad events satisfying the negative-dependency cardinality inequalities and asymmetric weight inequalities can all be avoided.

Statement

theorem finite_lopsided_avoidance_of_card_bound
    {I Ω : Type*} [Fintype I] [DecidableEq I]
    [Fintype Ω] [DecidableEq Ω] [Nonempty Ω]
    (A : I → Finset Ω) (N : I → Finset I) (p x : I → ℝ)
    (hx0 : ∀ i, 0 ≤ x i) (hx1 : ∀ i, x i < 1)
    (hdep : ∀ i (S : Finset I), i ∉ S → Disjoint S (N i) →
      ((A i ∩ Finset.univ.filter (fun ω => ∀ j ∈ S, ω ∉ A j)).card : ℝ) ≤
        p i * ((Finset.univ.filter (fun ω => ∀ j ∈ S, ω ∉ A j)).card : ℝ))
    (hprob : ∀ i, p i ≤ x i * ∏ j ∈ N i, (1 - x j)) :
    ∃ ω : Ω, ∀ i, ω ∉ A i
Source
Finite-cardinality specialization of EJC 14 (2007) R63, DOI 10.37236/981, Lemma 3; helper for OP-306.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

For any index subset $S \\subseteq I$, let $B(S)$ be the set of sample points in $\\Omega$ avoiding all bad events $A_j$ for $j \\in S$. The goal is to show that $B(I)$, the set of outcomes avoiding all bad events, is nonempty. Applying the abstract lopsided Lovász local lemma product bound to the cardinality function $F(S) = |B(S)|$ yields $|B(I)| \\ge \\prod_{i \\in I} (1 - x_i) \\cdot |B(\\emptyset)|$, because the marginal differences $|B(S)| - |B(S \\cup \\{i\\})| = |A_i \\cap B(S)|$ satisfy the required submodularity and negative-dependency conditions. Since $\\Omega$ is nonempty and each factor $1 - x_i > 0$, this lower bound is strictly positive, ensuring that $|B(I)| > 0$ and providing a sample point that avoids every bad event.

  1. Define $B(S)$ as the set of outcomes avoiding all bad events in $S$, and show $B(S \\cup \{i\}) = B(S) \\setminus A_i$.

    For any index subset $S \\subseteq I$, define $B(S) = \\{\\omega \\in \\Omega \\mid \\forall j \\in S, \\omega \\notin A_j\\}$. An element $\\omega$ belongs to $B(S \\cup \\{i\\})$ if and only if $\\omega \\in B(S)$ and $\\omega \\notin A_i$, which is precisely the set difference $B(S) \\setminus A_i$. This equivalence is verified by unfolding the definition of $B$ and commuting propositional conjunction (`and_comm`).

    lines 11–16

    uses and_comm

      classical
      let B : Finset I → Finset Ω := fun S => Finset.univ.filter (fun ω => ∀ j ∈ S, ω ∉ A j)
      have hB : ∀ i S, B (insert i S) = B S \ A i := by
        intro i S
        ext ω
        simp [B, and_comm]
  2. The marginal change in cardinality $|B(S)| - |B(S \\cup \{i\})|$ equals $|A_i \\cap B(S)|$.

    Set theory gives $|B(S) \\setminus A_i| + |B(S) \\cap A_i| = |B(S)|$ by `Finset.card_sdiff_add_card_inter`. Substituting $B(S \\cup \\{i\\}) = B(S) \\setminus A_i$ and commuting the intersection using `Finset.inter_comm` yields $|B(S \\cup \\{i\\})| + |A_i \\cap B(S)| = |B(S)|$. Subtracting $|B(S \\cup \\{i\\})|$ via linear arithmetic establishes the claim.

    lines 17–24

    uses Finset.card_sdiff_add_card_inter, Finset.inter_comm

      have hdiff : ∀ i S, ((B S).card : ℝ) - ((B (insert i S)).card : ℝ) =
          ((A i ∩ B S).card : ℝ) := by
        intro i S
        have hc := Finset.card_sdiff_add_card_inter (B S) (A i)
        rw [← hB, Finset.inter_comm] at hc
        have hc' : ((B (insert i S)).card : ℝ) + ((A i ∩ B S).card : ℝ) =
            ((B S).card : ℝ) := by exact_mod_cast hc
        linarith
  3. The set-valued function $B$ is antitone: if $S \\subseteq T$, then $B(T) \\subseteq B(S)$.

    If an outcome $\\omega \\in B(T)$ avoids all events $A_j$ for $j \\in T$, then for any index $j \\in S \\subseteq T$, $\\omega$ in particular avoids $A_j$ using `Finset.mem_filter.mp` and `Finset.mem_filter.mpr`, so $\\omega \\in B(S)$.

    lines 25–28

    uses Finset.mem_filter.mpr, Finset.mem_univ, Finset.mem_filter.mp

      have hanti : ∀ S T, S ⊆ T → B T ⊆ B S := by
        intro S T hST ω hω
        exact Finset.mem_filter.mpr ⟨Finset.mem_univ _,
          fun j hj => (Finset.mem_filter.mp hω).2 j (hST hj)⟩
  4. The size of $B(I)$ satisfies the lower bound $|B(I)| \\ge \\prod_{i \\in I} (1 - x_i) \\cdot |B(\\emptyset)|$.

    We invoke `finite_lopsided_function_product_bound` on the cardinality function $F(S) = |B(S)|$. Cardinalities are non-negative (`Nat.cast_nonneg`). Submodularity of $F$ requires $F(T) - F(T \\cup \\{i\\}) \\le F(S) - F(S \\cup \\{i\\})$ for $S \\subseteq T$, which rewrites via our difference formula to $|A_i \\cap B(T)| \\le |A_i \\cap B(S)|$; this holds because $B(T) \\subseteq B(S)$ implies $A_i \\cap B(T) \\subseteq A_i \\cap B(S)$ (`Finset.inter_subset_inter_left`) and inclusion preserves cardinality (`Finset.card_le_card`). Finally, the negative-dependency hypothesis rewrites directly via the difference formula into the assumption `hdep`.

    lines 29–36

    uses finite_lopsided_function_product_bound, Nat.cast_nonneg, Finset.card_le_card, Finset.inter_subset_inter_left

      have hbound := finite_lopsided_function_product_bound
        (fun S => ((B S).card : ℝ)) N p x (fun _ => Nat.cast_nonneg _)
        (by
          intro i S T hST _
          rw [hdiff, hdiff]
          exact_mod_cast Finset.card_le_card (Finset.inter_subset_inter_left (hanti S T hST)))
        (by intro i S hi hd; rw [hdiff]; exact hdep i S hi hd)
        hx0 hx1 hprob
  5. The product lower bound $\\prod_{i \\in I} (1 - x_i) \\cdot |B(\\emptyset)|$ is strictly positive.

    Since each $x_i < 1$, each factor $1 - x_i$ is strictly positive, so their finite product is strictly positive by `Finset.prod_pos`. Because the empty set specifies no conditions, $B(\\emptyset) = \\Omega$, whose cardinality is positive (`Fintype.card_pos`, `Finset.card_univ`) as $\\Omega$ is nonempty. The product of two strictly positive reals is strictly positive (`mul_pos`).

    lines 37–42

    uses mul_pos, Finset.prod_pos, Finset.card_univ, Fintype.card_pos

      have hpos : 0 < (∏ i, (1 - x i)) * ((B ∅).card : ℝ) := by
        apply mul_pos
        · exact Finset.prod_pos (fun i _ => by linarith [hx1 i])
        · have he : B ∅ = Finset.univ := by ext ω; simp [B]
          rw [he, Finset.card_univ]
          exact_mod_cast Fintype.card_pos
  6. The set $B(I)$ of outcomes avoiding all bad events is nonempty.

    Chaining the strict positivity of the lower bound with the product bound via `lt_of_lt_of_le` gives $|B(I)| > 0$. A finite set with positive cardinality is nonempty (`Finset.card_pos.mp`).

    lines 43–45

    uses Finset.card_pos.mp, lt_of_lt_of_le

      have hnon : (B Finset.univ).Nonempty := by
        apply Finset.card_pos.mp
        exact_mod_cast (lt_of_lt_of_le hpos hbound)
  7. There exists an outcome $\\omega \\in \\Omega$ avoiding every bad event $A_i$.

    We choose an outcome $\\omega \\in B(I)$ from nonemptiness. Unpacking membership in $B(I)$ via `Finset.mem_filter.mp` and `Finset.mem_univ` confirms that $\\omega \\notin A_i$ for all $i \\in I$.

    lines 46–47

    uses Finset.mem_filter.mp, Finset.mem_univ

      obtain ⟨ω, hω⟩ := hnon
      exact ⟨ω, fun i => (Finset.mem_filter.mp hω).2 i (Finset.mem_univ _)⟩
and_comm
Conjunction is commutative: $a \\land b \\iff b \\land a$.
Finset.card_sdiff_add_card_inter
For finite sets $s$ and $t$, the cardinality of the difference plus the cardinality of the intersection equals the cardinality of the original set: $|s \\setminus t| + |s \\cap t| = |s|$.
Finset.inter_comm
Finite set intersection is commutative: $s \\cap t = t \\cap s$.
Finset.mem_filter.mpr
An element $x$ belongs to the filtered set $\{y \\in s \\mid P(y)\}$ if $x \\in s$ and $P(x)$ holds.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
Finset.mem_filter.mp
If an element $x$ belongs to $\{y \\in s \\mid P(y)\}$, then $x \\in s$ and $P(x)$ holds.
finite_lopsided_function_product_bound
If a real-valued set function $F$ is non-negative, submodular (satisfies diminishing marginal differences), and satisfies the negative-dependency bounds $F(S) - F(S \\cup \{i\}) \\le p_i F(S)$, then $F(\\mathrm{univ}) \\ge \\prod_{i} (1 - x_i) \\cdot F(\\emptyset)$.
Nat.cast_nonneg
The canonical cast of any natural number into an ordered semiring is non-negative ($0 \\le n$).
Finset.card_le_card
If $s \\subseteq t$ for finite sets, then $|s| \\le |t|$.
Finset.inter_subset_inter_left
If $t \\subseteq u$, then $s \\cap t \\subseteq s \\cap u$.
mul_pos
The product of two strictly positive numbers is strictly positive ($0 < a$ and $0 < b$ implies $0 < a \\cdot b$).
Finset.prod_pos
A finite product of strictly positive elements in an ordered algebraic structure is strictly positive.
Finset.card_univ
The cardinality of the universal finset `Finset.univ` on a finite type equals the cardinality of the type (`Fintype.card`).
Fintype.card_pos
A nonempty finite type has strictly positive cardinality ($0 < |\\Omega|$).
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
lt_of_lt_of_le
Strict inequality is transitive with non-strict inequality: if $a < b$ and $b \\le c$, then $a < c$.

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 finite_lopsided_avoidance_of_card_bound    {I Ω : Type*} [Fintype I] [DecidableEq I]    [Fintype Ω] [DecidableEq Ω] [Nonempty Ω]    (A : I → Finset Ω) (N : I → Finset I) (p x : I → ℝ)    (hx0 : ∀ i, 0 ≤ x i) (hx1 : ∀ i, x i < 1)    (hdep : ∀ i (S : Finset I), i ∉ S → Disjoint S (N i) →      ((A i ∩ Finset.univ.filter (fun ω => ∀ j ∈ S, ω ∉ A j)).card : ℝ) ≤        p i * ((Finset.univ.filter (fun ω => ∀ j ∈ S, ω ∉ A j)).card : ℝ))    (hprob : ∀ i, p i ≤ x i * ∏ j ∈ N i, (1 - x j)) :    ∃ ω : Ω, ∀ i, ω ∉ A i := by  classical  let B : Finset I → Finset Ω := fun S => Finset.univ.filter (fun ω => ∀ j ∈ S, ω ∉ A j)  have hB : ∀ i S, B (insert i S) = B S \ A i := by    intro i S    ext ω    simp [B, and_comm]  have hdiff : ∀ i S, ((B S).card : ℝ) - ((B (insert i S)).card : ℝ) =      ((A i ∩ B S).card : ℝ) := by    intro i S    have hc := Finset.card_sdiff_add_card_inter (B S) (A i)    rw [← hB, Finset.inter_comm] at hc    have hc' : ((B (insert i S)).card : ℝ) + ((A i ∩ B S).card : ℝ) =        ((B S).card : ℝ) := by exact_mod_cast hc    linarith  have hanti : ∀ S T, S ⊆ T → B T ⊆ B S := by    intro S T hST ω hω    exact Finset.mem_filter.mpr ⟨Finset.mem_univ _,      fun j hj => (Finset.mem_filter.mp hω).2 j (hST hj)⟩  have hbound := finite_lopsided_function_product_bound    (fun S => ((B S).card : ℝ)) N p x (fun _ => Nat.cast_nonneg _)    (by      intro i S T hST _      rw [hdiff, hdiff]      exact_mod_cast Finset.card_le_card (Finset.inter_subset_inter_left (hanti S T hST)))    (by intro i S hi hd; rw [hdiff]; exact hdep i S hi hd)    hx0 hx1 hprob  have hpos : 0 < (∏ i, (1 - x i)) * ((B ∅).card : ℝ) := by    apply mul_pos    · exact Finset.prod_pos (fun i _ => by linarith [hx1 i])    · have he : B ∅ = Finset.univ := by ext ω; simp [B]      rw [he, Finset.card_univ]      exact_mod_cast Fintype.card_pos  have hnon : (B Finset.univ).Nonempty := by    apply Finset.card_pos.mp    exact_mod_cast (lt_of_lt_of_le hpos hbound)  obtain ⟨ω, hω⟩ := hnon  exact ⟨ω, fun i => (Finset.mem_filter.mp hω).2 i (Finset.mem_univ _)⟩
See it in the graphDiscuss this resultChallenge it