AFTD Auto-Formalizing Theoretical Domains

op1370_independent_upper_difference_hub

theoremverified

For two upper-closed families whose complementary lower-closed families attain equality in the uniform correlation inequality, if the first upper family is proper and the second is nonempty, the difference of the second from the first has a member Z such that every member of the difference has a common superset with Z in the difference.

Statement

theorem op1370_independent_upper_difference_hub (n : ℕ) (U V : Finset (Finset (Fin n)))
    (hU : IsUpperSet (U : Set (Finset (Fin n))))
    (hV : IsUpperSet (V : Set (Finset (Fin n))))
    (hUproper : ∃ X, X ∉ U) (hVne : V.Nonempty)
    (hEq : (Uᶜ).card * (Vᶜ).card = 2 ^ n * ((Uᶜ) ∩ (Vᶜ)).card) :
    ∃ Z ∈ V, Z ∉ U ∧ ∀ X ∈ V, X ∉ U →
      ∃ W ∈ V, W ∉ U ∧ X ⊆ W ∧ Z ⊆ W
Source
Equality-structure lemma for the balanced-case route to OP-1370, arXiv:2611.12199, Conjecture 4.3.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • op1370_lower_independent_fibersFor two downward-closed families on a finite Boolean cube that attain equality in the uniform correlation inequality, at every coordinate…
Used by 1

The proof, explained

The proof establishes that the set P of coordinates where the complement family Vᶜ is sensitive serves as the hub Z ∈ V \ U. Since Uᶜ and Vᶜ are lower sets achieving equality in the uniform correlation inequality, any coordinate where Vᶜ is sensitive must be a coordinate of invariance for Uᶜ, and vice versa. As U is a proper upper set and V is nonempty, the empty set is outside U and the full universe is in V; using the invariance lemma (op1370_fiber_union), the empty set shifts along P to show P ∉ U, while the universe shifts along Pᶜ to show P ∈ V. Finally, for any X ∈ V \ U, the union X ∪ P remains in V by upward closure and stays outside U because Uᶜ is invariant under adding P.

  1. For any family 𝒜 and element x, if the member subfamily and non-member subfamily at x coincide, then S ∈ 𝒜 if and only if S ∪ {x} ∈ 𝒜.

    We split into cases depending on whether x ∈ S. If x ∈ S, inserting x does not change S. If x ∉ S, the assumption that the member subfamily equals the non-member subfamily means S belongs to the member subfamily if and only if it belongs to the non-member subfamily, which translates directly to S ∪ {x} ∈ 𝒜 ↔ S ∈ 𝒜.

    lines 7–10

    uses mem_memberSubfamily, mem_nonMemberSubfamily, not_false_eq_true, and_true

      by_cases hx : x ∈ S
      · simp [hx]
      · have hf : S ∈ 𝒜.memberSubfamily x ↔ S ∈ 𝒜.nonMemberSubfamily x := by rw [h]
        simpa only [mem_memberSubfamily, mem_nonMemberSubfamily, hx, not_false_eq_true, and_true] using hf.symm
  2. If 𝒜 has identical member and non-member subfamilies at every element of T, then S ∈ 𝒜 if and only if S ∪ T ∈ 𝒜.

    By induction on the finite set T. The base case T = ∅ is trivial. In the inductive step T = {x} ∪ T', the induction hypothesis gives S ∈ 𝒜 ↔ S ∪ T' ∈ 𝒜, and op1370_fiber_toggle at x gives S ∪ T' ∈ 𝒜 ↔ S ∪ ({x} ∪ T') ∈ 𝒜.

    lines 16–26

    uses Finset.induction_on, Finset.mem_insert_of_mem, Finset.mem_insert_self, op1370_fiber_toggle, Finset.union_insert

      induction T using Finset.induction_on with
      | empty => simp
      | @insert x T hx ih =>
        have hT : ∀ y ∈ T, 𝒜.memberSubfamily y = 𝒜.nonMemberSubfamily y := by
          intro y hy
          exact h y (Finset.mem_insert_of_mem hy)
        have hx' : 𝒜.memberSubfamily x = 𝒜.nonMemberSubfamily x := h x (Finset.mem_insert_self x T)
        calc
          S ∈ 𝒜 ↔ S ∪ T ∈ 𝒜 := ih hT
          _ ↔ insert x (S ∪ T) ∈ 𝒜 := op1370_fiber_toggle 𝒜 x hx' (S ∪ T)
          _ ↔ S ∪ insert x T ∈ 𝒜 := by rw [Finset.union_insert]
  3. The complements Uᶜ and Vᶜ are lower sets.

    Since U and V are upper sets, their complements in the boolean lattice are lower sets, established via isLowerSet_compl.mpr.

    lines 35–39

    uses coe_compl, isLowerSet_compl.mpr

      classical
      have hL : IsLowerSet ((Uᶜ : Finset (Finset (Fin n))) : Set (Finset (Fin n))) := by
        simpa only [coe_compl] using (isLowerSet_compl.mpr hU)
      have hM : IsLowerSet ((Vᶜ : Finset (Finset (Fin n))) : Set (Finset (Fin n))) := by
        simpa only [coe_compl] using (isLowerSet_compl.mpr hV)
  4. Letting P be the set of coordinates where Vᶜ depends on the coordinate, Uᶜ is independent of every coordinate in P, and Vᶜ is independent of every coordinate outside P.

    We define P as the set of coordinates x where the member and non-member subfamilies of Vᶜ differ. For x ∈ P, equality in the correlation inequality forces Uᶜ to have equal member and non-member subfamilies at x by op1370_lower_independent_fibers. For x ∉ P, Vᶜ has equal member and non-member subfamilies at x by definition of P.

    lines 40–50

    uses op1370_lower_independent_fibers, mem_univ

      let P : Finset (Fin n) := univ.filter fun x =>
        (Vᶜ).memberSubfamily x ≠ (Vᶜ).nonMemberSubfamily x
      have hLfixed : ∀ x ∈ P, (Uᶜ).memberSubfamily x = (Uᶜ).nonMemberSubfamily x := by
        intro x hx
        have hx' := (mem_filter.mp hx).2
        exact (op1370_lower_independent_fibers n (Uᶜ) (Vᶜ) hL hM hEq x).resolve_right hx'
      have hMfixed : ∀ x ∈ Pᶜ, (Vᶜ).memberSubfamily x = (Vᶜ).nonMemberSubfamily x := by
        intro x hx
        have hnot : x ∉ P := mem_compl.mp hx
        by_contra hne
        exact hnot (mem_filter.mpr ⟨mem_univ x, hne⟩)
  5. The empty set is not in U, and the universal set is in V.

    Since U is a proper upper set, any set X ∉ U would contain ∅, so ∅ cannot be in U (otherwise all supersets would be in U). Since V is nonempty, any member Y ∈ V is a subset of the universal set, so the universal set belongs to V because V is an upper set.

    lines 51–56

    uses Finset.empty_subset, subset_univ

      obtain ⟨X, hX⟩ := hUproper
      have hUempty : (∅ : Finset (Fin n)) ∉ U := by
        intro h
        exact hX (hU (Finset.empty_subset X) h)
      obtain ⟨Y, hY⟩ := hVne
      have hVtop : (univ : Finset (Fin n)) ∈ V := hV (subset_univ Y) hY
  6. P does not belong to U.

    Since ∅ ∉ U, the empty set belongs to Uᶜ. Because Uᶜ is independent of all coordinates in P, op1370_fiber_union implies ∅ ∈ Uᶜ ↔ ∅ ∪ P ∈ Uᶜ. Hence P ∈ Uᶜ, meaning P ∉ U.

    lines 57–61

    uses op1370_fiber_union

      have hPnotU : P ∉ U := by
        have h := op1370_fiber_union (Uᶜ) P hLfixed (∅ : Finset (Fin n))
        have he : (∅ : Finset (Fin n)) ∈ Uᶜ := by simpa using hUempty
        have : P ∈ Uᶜ := by simpa using h.mp he
        simpa using this
  7. P belongs to V.

    Since the universal set belongs to V, univ ∉ Vᶜ. Because Vᶜ is independent of all coordinates in Pᶜ, op1370_fiber_union gives P ∈ Vᶜ ↔ P ∪ Pᶜ ∈ Vᶜ. Since P ∪ Pᶜ = univ ∉ Vᶜ, we conclude P ∉ Vᶜ, meaning P ∈ V.

    lines 62–69

    uses op1370_fiber_union

      have hPinV : P ∈ V := by
        have h := op1370_fiber_union (Vᶜ) Pᶜ hMfixed P
        have ht : (univ : Finset (Fin n)) ∉ Vᶜ := by simpa using hVtop
        have hp : P ∉ Vᶜ := by
          intro hp
          apply ht
          simpa using h.mp hp
        simpa using hp
  8. Z = P is the desired set in V \ U, and for any X ∈ V \ U, W = X ∪ P is a common superset belonging to V \ U.

    We have already shown P ∈ V and P ∉ U. Given any X ∈ V with X ∉ U, the union W = X ∪ P is an upper set extension of X, so W ∈ V. Since X ∉ U, we have X ∈ Uᶜ; since Uᶜ is independent of coordinates in P, op1370_fiber_union implies X ∪ P ∈ Uᶜ, so W ∉ U. Both X and P are subsets of W by definition of the union.

    lines 70–76

    uses subset_union_left, subset_union_right, op1370_fiber_union

      refine ⟨P, hPinV, hPnotU, ?_⟩
      intro X hXV hXU
      refine ⟨X ∪ P, hV (subset_union_left) hXV, ?_, subset_union_left, subset_union_right⟩
      have h := op1370_fiber_union (Uᶜ) P hLfixed X
      have hX' : X ∈ Uᶜ := by simpa using hXU
      have : X ∪ P ∈ Uᶜ := h.mp hX'
      simpa using this
not_false_eq_true
An element is not in false proposition is True.
and_true
Conjunction with True simplifies to the proposition itself.
mem_memberSubfamily
A set S belongs to the member subfamily of A at x if and only if x ∉ S and insert x S ∈ A.
mem_nonMemberSubfamily
A set S belongs to the non-member subfamily of A at x if and only if x ∉ S and S ∈ A.
Finset.induction_on
Induction principle for finite sets: a property holds for all finite sets if it holds for the empty set and is preserved under adjoining a new element.
Finset.mem_insert_of_mem
An element of a set s remains an element when another element is inserted into s.
Finset.mem_insert_self
An element is a member of the set formed by inserting it into s.
op1370_fiber_toggle
If a family's member and non-member subfamilies at x coincide, membership in the family is invariant under inserting x.
Finset.union_insert
The union of s with insert a t equals insert a (s ∪ t).
coe_compl
The set coercion of the complement of a finset equals the set complement of the coerced finset.
isLowerSet_compl.mpr
The complement of an upper set is a lower set.
op1370_lower_independent_fibers
For two lower families attaining equality in the correlation inequality, at every coordinate at least one family has equal member and non-member subfamilies.
mem_univ
Every element of a finite type belongs to the universal finset.
Finset.empty_subset
The empty set is a subset of every finite set.
subset_univ
Every finite set of elements of a finite type is a subset of the universal finset.
op1370_fiber_union
If a family has equal member and non-member subfamilies for all elements of T, membership in the family is invariant under taking the union with T.
subset_union_left
A finite set is a subset of its union with another set.
subset_union_right
A finite set is a subset of the union of another set with it.

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

open Finsetlemma op1370_fiber_toggle {α : Type*} [DecidableEq α]    (𝒜 : Finset (Finset α)) (x : α)    (h : 𝒜.memberSubfamily x = 𝒜.nonMemberSubfamily x) (S : Finset α) :    S ∈ 𝒜 ↔ insert x S ∈ 𝒜 := by  by_cases hx : x ∈ S  · simp [hx]  · have hf : S ∈ 𝒜.memberSubfamily x ↔ S ∈ 𝒜.nonMemberSubfamily x := by rw [h]    simpa only [mem_memberSubfamily, mem_nonMemberSubfamily, hx, not_false_eq_true, and_true] using hf.symmlemma op1370_fiber_union {α : Type*} [DecidableEq α]    (𝒜 : Finset (Finset α)) (T : Finset α)    (h : ∀ x ∈ T, 𝒜.memberSubfamily x = 𝒜.nonMemberSubfamily x) (S : Finset α) :    S ∈ 𝒜 ↔ S ∪ T ∈ 𝒜 := by  induction T using Finset.induction_on with  | empty => simp  | @insert x T hx ih =>    have hT : ∀ y ∈ T, 𝒜.memberSubfamily y = 𝒜.nonMemberSubfamily y := by      intro y hy      exact h y (Finset.mem_insert_of_mem hy)    have hx' : 𝒜.memberSubfamily x = 𝒜.nonMemberSubfamily x := h x (Finset.mem_insert_self x T)    calc      S ∈ 𝒜 ↔ S ∪ T ∈ 𝒜 := ih hT      _ ↔ insert x (S ∪ T) ∈ 𝒜 := op1370_fiber_toggle 𝒜 x hx' (S ∪ T)      _ ↔ S ∪ insert x T ∈ 𝒜 := by rw [Finset.union_insert]theorem op1370_independent_upper_difference_hub (n : ℕ) (U V : Finset (Finset (Fin n)))    (hU : IsUpperSet (U : Set (Finset (Fin n))))    (hV : IsUpperSet (V : Set (Finset (Fin n))))    (hUproper : ∃ X, X ∉ U) (hVne : V.Nonempty)    (hEq : (Uᶜ).card * (Vᶜ).card = 2 ^ n * ((Uᶜ) ∩ (Vᶜ)).card) :    ∃ Z ∈ V, Z ∉ U ∧ ∀ X ∈ V, X ∉ U →      ∃ W ∈ V, W ∉ U ∧ X ⊆ W ∧ Z ⊆ W := by  classical  have hL : IsLowerSet ((Uᶜ : Finset (Finset (Fin n))) : Set (Finset (Fin n))) := by    simpa only [coe_compl] using (isLowerSet_compl.mpr hU)  have hM : IsLowerSet ((Vᶜ : Finset (Finset (Fin n))) : Set (Finset (Fin n))) := by    simpa only [coe_compl] using (isLowerSet_compl.mpr hV)  let P : Finset (Fin n) := univ.filter fun x =>    (Vᶜ).memberSubfamily x ≠ (Vᶜ).nonMemberSubfamily x  have hLfixed : ∀ x ∈ P, (Uᶜ).memberSubfamily x = (Uᶜ).nonMemberSubfamily x := by    intro x hx    have hx' := (mem_filter.mp hx).2    exact (op1370_lower_independent_fibers n (Uᶜ) (Vᶜ) hL hM hEq x).resolve_right hx'  have hMfixed : ∀ x ∈ Pᶜ, (Vᶜ).memberSubfamily x = (Vᶜ).nonMemberSubfamily x := by    intro x hx    have hnot : x ∉ P := mem_compl.mp hx    by_contra hne    exact hnot (mem_filter.mpr ⟨mem_univ x, hne⟩)  obtain ⟨X, hX⟩ := hUproper  have hUempty : (∅ : Finset (Fin n)) ∉ U := by    intro h    exact hX (hU (Finset.empty_subset X) h)  obtain ⟨Y, hY⟩ := hVne  have hVtop : (univ : Finset (Fin n)) ∈ V := hV (subset_univ Y) hY  have hPnotU : P ∉ U := by    have h := op1370_fiber_union (Uᶜ) P hLfixed (∅ : Finset (Fin n))    have he : (∅ : Finset (Fin n)) ∈ Uᶜ := by simpa using hUempty    have : P ∈ Uᶜ := by simpa using h.mp he    simpa using this  have hPinV : P ∈ V := by    have h := op1370_fiber_union (Vᶜ) Pᶜ hMfixed P    have ht : (univ : Finset (Fin n)) ∉ Vᶜ := by simpa using hVtop    have hp : P ∉ Vᶜ := by      intro hp      apply ht      simpa using h.mp hp    simpa using hp  refine ⟨P, hPinV, hPnotU, ?_⟩  intro X hXV hXU  refine ⟨X ∪ P, hV (subset_union_left) hXV, ?_, subset_union_left, subset_union_right⟩  have h := op1370_fiber_union (Uᶜ) P hLfixed X  have hX' : X ∈ Uᶜ := by simpa using hXU  have : X ∪ P ∈ Uᶜ := h.mp hX'  simpa using this
See it in the graphDiscuss this resultChallenge it