finite_lopsided_avoidance_of_card_bound
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
- finite_lopsided_function_product_boundAn abstract finite-set function with nonnegative values, decreasing event increments and local negative-dependency bounds satisfies the…
- Used by 1
- canonical_permutation_avoidance_of_local_lemmaFor finitely many injective partial assignments on n points, if weights in [0,1) satisfy the asymmetric local-lemma inequalities for the…
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.
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`).
uses
and_commclassical 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]
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.
uses
Finset.card_sdiff_add_card_inter,Finset.inter_commhave 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
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)$.
uses
Finset.mem_filter.mpr,Finset.mem_univ,Finset.mem_filter.mphave 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)⟩
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`.
uses
finite_lopsided_function_product_bound,Nat.cast_nonneg,Finset.card_le_card,Finset.inter_subset_inter_lefthave 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
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`).
uses
mul_pos,Finset.prod_pos,Finset.card_univ,Fintype.card_poshave 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
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`).
uses
Finset.card_pos.mp,lt_of_lt_of_lehave hnon : (B Finset.univ).Nonempty := by apply Finset.card_pos.mp exact_mod_cast (lt_of_lt_of_le hpos hbound)
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$.
uses
Finset.mem_filter.mp,Finset.mem_univobtain ⟨ω, 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
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 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 _)⟩