op_1370_three_two_singletons
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 alli j : ιwithi ≠ 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.
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).
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| + 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).
uses
op_1370_incomparable_two_sets_card_boundhave 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)
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).
uses
pow_succhave hp : 2 ^ n = 2 * 2 ^ (n - 1) := by have : n = (n - 1) + 1 := by omega conv_lhs => rw [this] rw [pow_succ] omega
∑ 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.
uses
Fin.sum_univ_three,Finset.card_singletonrw [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
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 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