AFTD Auto-Formalizing Theoretical Domains

op1370_lower_independent_fibers

theoremverified

For two downward-closed families on a finite Boolean cube that attain equality in the uniform correlation inequality, at every coordinate the two slices coincide for at least one family.

Statement

theorem op1370_lower_independent_fibers (n : ℕ) (𝒜 ℬ : Finset (Finset (Fin n)))
    (h𝒜 : IsLowerSet (𝒜 : Set (Finset (Fin n))))
    (hℬ : IsLowerSet (ℬ : Set (Finset (Fin n))))
    (hEq : 𝒜.card * ℬ.card = 2 ^ n * (𝒜 ∩ ℬ).card) (x : Fin n) :
    𝒜.memberSubfamily x = 𝒜.nonMemberSubfamily x ∨
      ℬ.memberSubfamily x = ℬ.nonMemberSubfamily x
Source
A coordinate-slice equality lemma for a balanced-case route to OP-1370, arXiv:2611.12199, Conjecture 4.3.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 2

The proof, explained

We decompose the Boolean cube along coordinate x into two slices, the 1-slice and the 0-slice, over an (n-1)-element subcube. Because 𝒜 and ℬ are downward-closed, their 1-slices are subsets of their 0-slices; assuming for contradiction that neither family has equal slices yields strict inequalities |𝒜₁| < |𝒜₀| and |ℬ₁| < |ℬ₀|. Expanding the strictly positive product (|𝒜₀| - |𝒜₁|)(|ℬ₀| - |ℬ₁|) > 0 and applying the correlation inequality to each pair of slices contradicts the equality |𝒜||ℬ| = 2^n |𝒜 ∩ ℬ|.

  1. The coordinate x is removed to form the subcube domain s = univ \ {x}, which has size n - 1.

    We define s as the complement of {x} in Fin n and evaluate its cardinality |s| = n - 1.

    lines 10–12

      classical
      let s : Finset (Fin n) := Finset.univ.erase x
      have hs : s.card = n - 1 := by simp [s]
  2. Every set in the 0-slice (non-member subfamily) and 1-slice (member subfamily) along coordinate x is a subset of s.

    By definition of both slices, any member set t does not contain x. Therefore, every element y ∈ t satisfies y ≠ x, which places y in s = univ \ {x}.

    lines 13–24

    uses mem_nonMemberSubfamily, mem_erase, mem_univ, and_true, mem_memberSubfamily

      have h0 (𝒞 : Finset (Finset (Fin n))) : ∀ t ∈ 𝒞.nonMemberSubfamily x, t ⊆ s := by
        intro t ht y hy
        rw [mem_nonMemberSubfamily] at ht
        simp only [s, mem_erase, mem_univ, and_true]
        intro hxy
        exact ht.2 (hxy ▸ hy)
      have h1 (𝒞 : Finset (Finset (Fin n))) : ∀ t ∈ 𝒞.memberSubfamily x, t ⊆ s := by
        intro t ht y hy
        rw [mem_memberSubfamily] at ht
        simp only [s, mem_erase, mem_univ, and_true]
        intro hxy
        exact ht.2 (hxy ▸ hy)
  3. For both downward-closed families 𝒜 and ℬ, the 1-slice is contained in the 0-slice, so |𝒜₁| ≤ |𝒜₀| and |ℬ₁| ≤ |ℬ₀|.

    Because 𝒜 and ℬ are downward-closed, removing x from a set in the family leaves another set in the family, meaning 𝒜₁ ⊆ 𝒜₀ and ℬ₁ ⊆ ℬ₀. The inequalities on cardinalities follow immediately.

    lines 25–28

    uses card_le_card

      have hAsub : 𝒜.memberSubfamily x ⊆ 𝒜.nonMemberSubfamily x := h𝒜.memberSubfamily_subset_nonMemberSubfamily
      have hBsub : ℬ.memberSubfamily x ⊆ ℬ.nonMemberSubfamily x := hℬ.memberSubfamily_subset_nonMemberSubfamily
      have hA := card_le_card hAsub
      have hB := card_le_card hBsub
  4. The uniform correlation inequality holds on the subcube for the 0-slices and for the 1-slices: |𝒜₀| |ℬ₀| ≤ 2^|s| |𝒜₀ ∩ ℬ₀| and |𝒜₁| |ℬ₁| ≤ 2^|s| |𝒜₁ ∩ ℬ₁|.

    The slices of a downward-closed family are themselves downward-closed families consisting entirely of subsets of s, so Kleitman's correlation inequality applies to both the 0-slices and the 1-slices.

    lines 29–30

      have h00 := h𝒜.nonMemberSubfamily.le_card_inter_finset' hℬ.nonMemberSubfamily (h0 𝒜) (h0 ℬ)
      have h11 := h𝒜.memberSubfamily.le_card_inter_finset' hℬ.memberSubfamily (h1 𝒜) (h1 ℬ)
  5. The total cube size factors as 2^n = 2 * 2^|s|.

    Since x ∈ Fin n, n is strictly positive, so 2^n = 2^(|s| + 1) = 2 * 2^|s|.

    lines 31–33

    uses Nat.lt_of_le_of_lt, Nat.zero_le, Nat.mul_comm, pow_succ, Nat.sub_add_cancel

      have hn : 0 < n := Nat.lt_of_le_of_lt (Nat.zero_le x.val) x.isLt
      have hp : 2 ^ n = 2 * 2 ^ s.card := by
        rw [hs, Nat.mul_comm (2 : ℕ) (2 ^ (n - 1)), ← pow_succ, Nat.sub_add_cancel hn]
  6. The equality condition decomposes by slices along x into (|𝒜₁| + |𝒜₀|) * (|ℬ₁| + |ℬ₀|) = 2 * 2^|s| * (|𝒜₁ ∩ ℬ₁| + |𝒜₀ ∩ ℬ₀|).

    We partition 𝒜, ℬ, and 𝒜 ∩ ℬ into their respective 1-slices and 0-slices along x, and substitute 2^n = 2 * 2^|s| into the assumed equality.

    lines 34–38

    uses card_memberSubfamily_add_card_nonMemberSubfamily, memberSubfamily_inter, nonMemberSubfamily_inter

      have hEq' := hEq
      rw [← card_memberSubfamily_add_card_nonMemberSubfamily x 𝒜,
          ← card_memberSubfamily_add_card_nonMemberSubfamily x ℬ,
          ← card_memberSubfamily_add_card_nonMemberSubfamily x (𝒜 ∩ ℬ),
          memberSubfamily_inter, nonMemberSubfamily_inter, hp] at hEq'
  7. Assuming for contradiction that neither family has identical slices, both 1-slices are strictly smaller than their 0-slices: |𝒜₁| < |𝒜₀| and |ℬ₁| < |ℬ₀|.

    If 𝒜₁ ≠ 𝒜₀ and ℬ₁ ≠ ℬ₀, the inclusions 𝒜₁ ⊆ 𝒜₀ and ℬ₁ ⊆ ℬ₀ are proper, which implies strict inequalities between their finite cardinalities.

    lines 39–44

    uses Finset.card_lt_card, lt_of_le_of_ne

      by_contra h
      push_neg at h
      have ha : (𝒜.memberSubfamily x).card < (𝒜.nonMemberSubfamily x).card := by
        exact Finset.card_lt_card (lt_of_le_of_ne hAsub h.1)
      have hb : (ℬ.memberSubfamily x).card < (ℬ.nonMemberSubfamily x).card := by
        exact Finset.card_lt_card (lt_of_le_of_ne hBsub h.2)
  8. Contradiction: the strict inequalities force a strictly positive difference that contradicts the correlation equality. automation

    The identity (|𝒜₀| - |𝒜₁|)(|ℬ₀| - |ℬ₁|) > 0 expands to (|𝒜₁| + |𝒜₀|)(|ℬ₁| + |ℬ₀|) < 2(|𝒜₀||ℬ₀| + |𝒜₁||ℬ₁|). Together with the subcube correlation bounds |𝒜₀||ℬ₀| ≤ 2^|s| |𝒜₀ ∩ ℬ₀| and |𝒜₁||ℬ₁| ≤ 2^|s| |𝒜₁ ∩ ℬ₁|, this strictly bounds the left-hand side below 2 * 2^|s| * (|𝒜₁ ∩ ℬ₁| + |𝒜₀ ∩ ℬ₀|), contradicting their equality. Nonlinear arithmetic closes the goal.

    line 45

      nlinarith
and_true
For any proposition p, p ∧ True is equivalent to p.
card_le_card
If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
card_memberSubfamily_add_card_nonMemberSubfamily
The size of a family is the sum of the sizes of its member and non-member subfamilies at coordinate a: |𝒜₁| + |𝒜₀| = |𝒜|.
Finset.card_lt_card
If s ⊂ t for finite sets s and t, then |s| < |t|.
lt_of_le_of_ne
In any partial order, if a ≤ b and a ≠ b, then a < b.
mem_erase
An element y belongs to s \ {x} if and only if y ≠ x and y ∈ s.
mem_memberSubfamily
A set s belongs to the member subfamily of 𝒜 at a if and only if s ∪ {a} ∈ 𝒜 and a ∉ s.
mem_nonMemberSubfamily
A set s belongs to the non-member subfamily of 𝒜 at a if and only if s ∈ 𝒜 and a ∉ s.
mem_univ
Every element of a finite type belongs to the universal finset univ.
memberSubfamily_inter
The member subfamily of an intersection is the intersection of the member subfamilies: (𝒜 ∩ ℬ)₁ = 𝒜₁ ∩ ℬ₁.
Nat.lt_of_le_of_lt
If a ≤ b and b < c, then a < c.
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
Nat.sub_add_cancel
If m ≤ n, then (n - m) + m = n.
Nat.zero_le
For any natural number n, 0 ≤ n.
nonMemberSubfamily_inter
The non-member subfamily of an intersection is the intersection of the non-member subfamilies: (𝒜 ∩ ℬ)₀ = 𝒜₀ ∩ ℬ₀.
pow_succ
For any monoid element a and natural number n, a^(n + 1) = a^n * a.

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 Finsetset_option maxHeartbeats 2000000theorem op1370_lower_independent_fibers (n : ℕ) (𝒜 ℬ : Finset (Finset (Fin n)))    (h𝒜 : IsLowerSet (𝒜 : Set (Finset (Fin n))))    (hℬ : IsLowerSet (ℬ : Set (Finset (Fin n))))    (hEq : 𝒜.card * ℬ.card = 2 ^ n * (𝒜 ∩ ℬ).card) (x : Fin n) :    𝒜.memberSubfamily x = 𝒜.nonMemberSubfamily x ∨      ℬ.memberSubfamily x = ℬ.nonMemberSubfamily x := by  classical  let s : Finset (Fin n) := Finset.univ.erase x  have hs : s.card = n - 1 := by simp [s]  have h0 (𝒞 : Finset (Finset (Fin n))) : ∀ t ∈ 𝒞.nonMemberSubfamily x, t ⊆ s := by    intro t ht y hy    rw [mem_nonMemberSubfamily] at ht    simp only [s, mem_erase, mem_univ, and_true]    intro hxy    exact ht.2 (hxy ▸ hy)  have h1 (𝒞 : Finset (Finset (Fin n))) : ∀ t ∈ 𝒞.memberSubfamily x, t ⊆ s := by    intro t ht y hy    rw [mem_memberSubfamily] at ht    simp only [s, mem_erase, mem_univ, and_true]    intro hxy    exact ht.2 (hxy ▸ hy)  have hAsub : 𝒜.memberSubfamily x ⊆ 𝒜.nonMemberSubfamily x := h𝒜.memberSubfamily_subset_nonMemberSubfamily  have hBsub : ℬ.memberSubfamily x ⊆ ℬ.nonMemberSubfamily x := hℬ.memberSubfamily_subset_nonMemberSubfamily  have hA := card_le_card hAsub  have hB := card_le_card hBsub  have h00 := h𝒜.nonMemberSubfamily.le_card_inter_finset' hℬ.nonMemberSubfamily (h0 𝒜) (h0 ℬ)  have h11 := h𝒜.memberSubfamily.le_card_inter_finset' hℬ.memberSubfamily (h1 𝒜) (h1 ℬ)  have hn : 0 < n := Nat.lt_of_le_of_lt (Nat.zero_le x.val) x.isLt  have hp : 2 ^ n = 2 * 2 ^ s.card := by    rw [hs, Nat.mul_comm (2 : ℕ) (2 ^ (n - 1)), ← pow_succ, Nat.sub_add_cancel hn]  have hEq' := hEq  rw [← card_memberSubfamily_add_card_nonMemberSubfamily x 𝒜,      ← card_memberSubfamily_add_card_nonMemberSubfamily x ℬ,      ← card_memberSubfamily_add_card_nonMemberSubfamily x (𝒜 ∩ ℬ),      memberSubfamily_inter, nonMemberSubfamily_inter, hp] at hEq'  by_contra h  push_neg at h  have ha : (𝒜.memberSubfamily x).card < (𝒜.nonMemberSubfamily x).card := by    exact Finset.card_lt_card (lt_of_le_of_ne hAsub h.1)  have hb : (ℬ.memberSubfamily x).card < (ℬ.nonMemberSubfamily x).card := by    exact Finset.card_lt_card (lt_of_le_of_ne hBsub h.2)  nlinarith
See it in the graphDiscuss this resultChallenge it