AFTD Auto-Formalizing Theoretical Domains

op_1370_three_two_singletons

theoremverifiedoriginal

For n at least three, if three mutually strongly incomparable families of subsets of an n-element set have their first two families singleton and the third uncomplemented, then their total size is at most 2^(n-1) - 1.

Statement

theorem op_1370_three_two_singletons (n : ℕ) (hn : 3 ≤ n)
    (𝒜 : Fin 3 → Finset (Finset (Fin n)))
    (A B : Finset (Fin n)) (h0 : 𝒜 0 = {A}) (h1 : 𝒜 1 = {B})
    (hunc : is_uncomplemented (𝒜 2)) (hinc : strongly_incomparable 𝒜) :
    ∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 1
Related work
arXiv:2611.12199, Conjecture 4.3, restricted to three families with two singleton families.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • is_uncomplementedA family of subsets of a finite set is uncomplemented if no set and its complement both belong to the family.
  • strongly_incomparableAn indexed family of finset families 𝒜 : ι → Finset (Finset α) is strongly incomparable if for all i j : ι with i ≠ j, for all…
  • op_1370_incomparable_two_sets_card_boundOn an n-element ground set with n at least three, let A and B be incomparable subsets, and let F be an uncomplemented family every member…

Read back from the Lean

For any natural number $n \ge 3$, any collection of three families of subsets of $\mathrm{Fin}(n)$, denoted $\mathcal{A} : \mathrm{Fin}(3) \to \mathrm{Finset}(\mathrm{Finset}(\mathrm{Fin}(n)))$, and any two subsets $A, B \subseteq \mathrm{Fin}(n)$ such that: 1. $\mathcal{A}(0) = \{A\}$ (the first family is the singleton $\{A\}$), 2. $\mathcal{A}(1) = \{B\}$ (the second family is the singleton $\{B\}$), 3. $\mathcal{A}(2)$ is uncomplemented, and 4. $\mathcal{A}$ is strongly incomparable, the sum of the cardinalities of the three families $\sum_{i \in \mathrm{Fin}(3)} |\mathcal{A}(i)|$ is at most $2^{n - 1} - 1$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

Because 𝒜 0 = {A} and 𝒜 1 = {B} are singletons, strong incomparability guarantees that A and B are mutually incomparable, and that every set in the uncomplemented family 𝒜 2 is incomparable with both A and B. The lemma `op_1370_incomparable_two_sets_card_bound` then gives 2 * |𝒜 2| + 6 ≤ 2^n = 2 * 2^(n - 1). Dividing by 2 shows that the total cardinality |𝒜 0| + |𝒜 1| + |𝒜 2| = |𝒜 2| + 2 is at most 2^(n - 1) - 1.

  1. A ∈ 𝒜 0, B ∈ 𝒜 1, and the sets A and B are mutually incomparable (A ⊈ B and B ⊈ A).

    Since 𝒜 0 = {A} and 𝒜 1 = {B}, the sets A and B belong to their respective families. The strong incomparability hypothesis on 𝒜 then implies that A ⊈ B (using indices 0 ≠ 1) and B ⊈ A (using indices 1 ≠ 0).

    lines 6–10

      classical
      have ha : A ∈ 𝒜 0 := by rw [h0]; simp
      have hb : B ∈ 𝒜 1 := by rw [h1]; simp
      have hab := hinc 0 1 (by decide) A ha B hb
      have hba := hinc 1 0 (by decide) B hb A ha
  2. 2 * |𝒜 2| + 6 ≤ 2^n

    We apply `op_1370_incomparable_two_sets_card_bound` to A, B, and the family 𝒜 2. Its hypotheses are satisfied: n ≥ 3, A and B are mutually incomparable, 𝒜 2 is uncomplemented, and strong incomparability between index 2 and indices 0 and 1 guarantees that every set S ∈ 𝒜 2 is incomparable with both A and B (neither S ⊆ A, A ⊆ S, S ⊆ B, nor B ⊆ S).

    lines 11–15

    uses op_1370_incomparable_two_sets_card_bound

      have hbound := op_1370_incomparable_two_sets_card_bound n hn A B hab hba (𝒜 2) hunc
        (fun S hS => hinc 2 0 (by decide) S hS A ha)
        (fun S hS => hinc 0 2 (by decide) A ha S hS)
        (fun S hS => hinc 2 1 (by decide) S hS B hb)
        (fun S hS => hinc 1 2 (by decide) B hb S hS)
  3. 2^n = 2 * 2^(n - 1)

    Because n ≥ 3, we can rewrite n as (n - 1) + 1. Applying `pow_succ` expands 2^((n - 1) + 1) to 2^(n - 1) * 2, which equals 2 * 2^(n - 1).

    lines 16–20

    uses pow_succ

      have hp : 2 ^ n = 2 * 2 ^ (n - 1) := by
        have : n = (n - 1) + 1 := by omega
        conv_lhs => rw [this]
        rw [pow_succ]
        omega
  4. ∑ i, |𝒜 i| ≤ 2^(n - 1) - 1

    Substituting 2^n = 2 * 2^(n - 1) into the bound gives 2 * |𝒜 2| + 6 ≤ 2 * 2^(n - 1). Expanding the sum over the three families with `Fin.sum_univ_three` and evaluating the singleton sizes |𝒜 0| = 1 and |𝒜 1| = 1 with `Finset.card_singleton` reduces the left-hand side to 1 + 1 + |𝒜 2|. Linear integer arithmetic (`omega`) closes the goal, since 2 * |𝒜 2| + 6 ≤ 2 * 2^(n - 1) implies |𝒜 2| + 2 ≤ 2^(n - 1) - 1.

    lines 21–23

    uses Fin.sum_univ_three, Finset.card_singleton

      rw [hp] at hbound
      simp only [Fin.sum_univ_three, h0, h1, Finset.card_singleton]
      omega
op_1370_incomparable_two_sets_card_bound
If n ≥ 3, A and B are mutually incomparable subsets of an n-element set, and F is an uncomplemented family of subsets mutually incomparable with both A and B, then 2 * |F| + 6 ≤ 2^n.
pow_succ
In a monoid, a^(n + 1) = a^n * a.
Fin.sum_univ_three
The sum of a function over Fin 3 is f(0) + f(1) + f(2).
Finset.card_singleton
A singleton finset has cardinality 1.

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 op_1370_three_two_singletons (n : ℕ) (hn : 3 ≤ n)    (𝒜 : Fin 3 → Finset (Finset (Fin n)))    (A B : Finset (Fin n)) (h0 : 𝒜 0 = {A}) (h1 : 𝒜 1 = {B})    (hunc : is_uncomplemented (𝒜 2)) (hinc : strongly_incomparable 𝒜) :    ∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 1 := by  classical  have ha : A ∈ 𝒜 0 := by rw [h0]; simp  have hb : B ∈ 𝒜 1 := by rw [h1]; simp  have hab := hinc 0 1 (by decide) A ha B hb  have hba := hinc 1 0 (by decide) B hb A ha  have hbound := op_1370_incomparable_two_sets_card_bound n hn A B hab hba (𝒜 2) hunc    (fun S hS => hinc 2 0 (by decide) S hS A ha)    (fun S hS => hinc 0 2 (by decide) A ha S hS)    (fun S hS => hinc 2 1 (by decide) S hS B hb)    (fun S hS => hinc 1 2 (by decide) B hb S hS)  have hp : 2 ^ n = 2 * 2 ^ (n - 1) := by    have : n = (n - 1) + 1 := by omega    conv_lhs => rw [this]    rw [pow_succ]    omega  rw [hp] at hbound  simp only [Fin.sum_univ_three, h0, h1, Finset.card_singleton]  omega
See it in the graphDiscuss this resultChallenge it