op_1370_case_n3_t3
Base case n = 3, t = 3 of Conjecture 4.3 of arXiv:2611.12199 (OP-1370): if π : Fin 3 β Finset (Finset (Fin 3)) is a family such that each π i is non-empty and uncomplemented, and π is strongly incomparable, then β i : Fin 3, (π i).card β€ 3.
Statement
theorem op_1370_case_n3_t3 (π : Fin 3 β Finset (Finset (Fin 3))) (hne : β i, (π i).Nonempty) (hunc : β i, is_uncomplemented (π i)) (hinc : strongly_incomparable π) : β i, (π i).card β€ 3- Related work
- arXiv:2611.12199 Conjecture 4.3
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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β¦
Read back from the Lean
For every 3-family of collections of subsets of Fin 3 (that is, π : Fin 3 β Finset (Finset (Fin 3))), if:
1. each collection π i is nonempty,
2. each collection π i is uncomplemented (no set and its complement both belong to π i), and
3. the family π is strongly incomparable (for any distinct indices i β j, no set in π i is a subset of any set in π j),
then the sum over all i : Fin 3 of the cardinalities of π i is at most 3.
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
This is a summary of the proof that the sum of the cardinalities of three strongly incomparable nonempty uncomplemented families on a 3-element set is at most 3. The proof first shows that every set in each family must have size 1 or 2, then eliminates the mixed case, showing all sets must have the same size, which limits the total number to at most 3.
test claim
test explanation
lemma op_1370_case_n3_t3_exists_third (i j : Fin 3) (hij : i β j) : β k : Fin 3, k β i β§ k β j := by fin_cases i <;> fin_cases j <;> try contradiction Β· exact β¨2, by decide, by decideβ© Β· exact β¨1, by decide, by decideβ© Β· exact β¨2, by decide, by decideβ© Β· exact β¨0, by decide, by decideβ© Β· exact β¨1, by decide, by decideβ© Β· exact β¨0, by decide, by decideβ© lemma op_1370_case_n3_t3_no_card_one_and_two_ne (π : Fin 3 β Finset (Finset (Fin 3))) (hne : β i, (π i).Nonempty) (hinc : strongly_incomparable π) (i j : Fin 3) (hij : i β j) {A B : Finset (Fin 3)} (hA : A β π i) (hB : B β π j) (hAc : A.card = 1) (hBc : B.card = 2) : False := by obtain β¨x, hxβ© := card_eq_one.mp hAc have hx_not_in_B : x β B := by intro hx_in_B have : A β B := by rw [hx] exact singleton_subset_iff.mpr hx_in_B exact hinc i j hij A hA B hB this have hB_eq : B = {x}αΆ := by have hsub : B β {x}αΆ := by intro y hy simp only [mem_compl, mem_singleton] rintro rfl exact hx_not_in_B hy have hcard_compl : ({x}αΆ : Finset (Fin 3)).card = 2 := by simp [card_compl] exact eq_of_subset_of_card_le hsub (by rw [hBc, hcard_compl]) obtain β¨k, hki, hkjβ© := op_1370_case_n3_t3_exists_third i j hij obtain β¨C, hCβ© := hne k have hx_not_in_C : x β C := by intro hx_in_C have : A β C := by rw [hx] exact singleton_subset_iff.mpr hx_in_C exact hinc i k hki.symm A hA C hC this have hC_sub_B : C β B := by rw [hB_eq] intro y hy simp only [mem_compl, mem_singleton] rintro rfl exact hx_not_in_C hy exact hinc k j hkj C hC B hB hC_sub_B lemma op_1370_case_n3_t3_card_mem_eq_one_or_two (π : Fin 3 β Finset (Finset (Fin 3))) (hne : β i, (π i).Nonempty) (hinc : strongly_incomparable π) (i : Fin 3) {A : Finset (Fin 3)} (hA : A β π i) : A.card = 1 β¨ A.card = 2 := by have hle : A.card β€ 3 := by have := A.card_le_univ simpa using this have : A.card = 0 β¨ A.card = 1 β¨ A.card = 2 β¨ A.card = 3 := by omega rcases this with h | h | h | h Β· have : A = β := card_eq_zero.mp h subst this obtain β¨j, hjβ© : β j : Fin 3, i β j := by fin_cases i <;> decide obtain β¨B, hBβ© := hne j exact False.elim (hinc i j hj β hA B hB (empty_subset B)) Β· left; exact h Β· right; exact h Β· have : A = univ := eq_univ_of_card A (by simpa using h) subst this obtain β¨j, hjβ© : β j : Fin 3, j β i := by fin_cases i <;> decide obtain β¨B, hBβ© := hne j exact False.elim (hinc j i hj B hB univ hA (subset_univ B)) lemma op_1370_case_n3_t3_no_card_one_and_two (π : Fin 3 β Finset (Finset (Fin 3))) (hne : β i, (π i).Nonempty) (hinc : strongly_incomparable π) (i j : Fin 3) {A B : Finset (Fin 3)} (hA : A β π i) (hB : B β π j) (hAc : A.card = 1) (hBc : B.card = 2) : False := by by_cases hij : i = j Β· subst hij obtain β¨k, hkβ© : β k : Fin 3, k β i := by fin_cases i <;> decide obtain β¨C, hCβ© := hne k rcases op_1370_case_n3_t3_card_mem_eq_one_or_two π hne hinc k hC with hC1 | hC2 Β· exact op_1370_case_n3_t3_no_card_one_and_two_ne π hne hinc k i hk hC hB hC1 hBc Β· exact op_1370_case_n3_t3_no_card_one_and_two_ne π hne hinc i k hk.symm hA hC hAc hC2 Β· exact op_1370_case_n3_t3_no_card_one_and_two_ne π hne hinc i j hij hA hB hAc hBc lemma op_1370_case_n3_t3_all_one_or_all_two (π : Fin 3 β Finset (Finset (Fin 3))) (hne : β i, (π i).Nonempty) (hinc : strongly_incomparable π) : (β i, β A β π i, A.card = 1) β¨ (β i, β A β π i, A.card = 2) := by obtain β¨S, hSβ© := hne 0 rcases op_1370_case_n3_t3_card_mem_eq_one_or_two π hne hinc 0 hS with hS1 | hS2 Β· left intro i A hA rcases op_1370_case_n3_t3_card_mem_eq_one_or_two π hne hinc i hA with hA1 | hA2 Β· exact hA1 Β· exact False.elim (op_1370_case_n3_t3_no_card_one_and_two π hne hinc 0 i hS hA hS1 hA2) Β· right intro i A hA rcases op_1370_case_n3_t3_card_mem_eq_one_or_two π hne hinc i hA with hA1 | hA2 Β· exact False.elim (op_1370_case_n3_t3_no_card_one_and_two π hne hinc i 0 hA hS hA1 hS2) Β· exact hA2 /-- Base case n = 3, t = 3 of OP-1370: three non-empty uncomplemented strongly incomparable families of subsets of [3] have total size at most 3. -/ theorem op_1370_case_n3_t3 (π : Fin 3 β Finset (Finset (Fin 3))) (hne : β i, (π i).Nonempty) (hunc : β i, is_uncomplemented (π i)) (hinc : strongly_incomparable π) : β i, (π i).card β€ 3 := by have _ := hunc have hdisj : ((Finset.univ : Finset (Fin 3)) : Set (Fin 3)).PairwiseDisjoint π := by intro i _ j _ hij change Disjoint (π i) (π j) rw [Finset.disjoint_iff_ne] intro A hAi B hAj rintro rfl exact hinc i j hij A hAi A hAj subset_rfl have heq : (Finset.univ.biUnion π).card = β i, (π i).card := Finset.card_biUnion hdisj rw [β heq] rcases op_1370_case_n3_t3_all_one_or_all_two π hne hinc with h1 | h2 Β· have hsub : Finset.univ.biUnion π β Finset.powersetCard 1 (Finset.univ : Finset (Fin 3)) := by intro A hA rw [Finset.mem_biUnion] at hA obtain β¨i, -, hiβ© := hA rw [Finset.mem_powersetCard_univ] exact h1 i A hi have hle := Finset.card_le_card hsub have hpow : (Finset.powersetCard 1 (Finset.univ : Finset (Fin 3))).card = 3 := by rw [Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin] rfl omega Β· have hsub : Finset.univ.biUnion π β Finset.powersetCard 2 (Finset.univ : Finset (Fin 3)) := by intro A hA rw [Finset.mem_biUnion] at hA obtain β¨i, -, hiβ© := hA rw [Finset.mem_powersetCard_univ] exact h2 i A hi have hle := Finset.card_le_card hsub have hpow : (Finset.powersetCard 2 (Finset.univ : Finset (Fin 3))).card = 3 := by rw [Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin] rfl omega
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.
open Finsetlemma op_1370_case_n3_t3_exists_third (i j : Fin 3) (hij : i β j) : β k : Fin 3, k β i β§ k β j := by fin_cases i <;> fin_cases j <;> try contradiction Β· exact β¨2, by decide, by decideβ© Β· exact β¨1, by decide, by decideβ© Β· exact β¨2, by decide, by decideβ© Β· exact β¨0, by decide, by decideβ© Β· exact β¨1, by decide, by decideβ© Β· exact β¨0, by decide, by decideβ©lemma op_1370_case_n3_t3_no_card_one_and_two_ne (π : Fin 3 β Finset (Finset (Fin 3))) (hne : β i, (π i).Nonempty) (hinc : strongly_incomparable π) (i j : Fin 3) (hij : i β j) {A B : Finset (Fin 3)} (hA : A β π i) (hB : B β π j) (hAc : A.card = 1) (hBc : B.card = 2) : False := by obtain β¨x, hxβ© := card_eq_one.mp hAc have hx_not_in_B : x β B := by intro hx_in_B have : A β B := by rw [hx] exact singleton_subset_iff.mpr hx_in_B exact hinc i j hij A hA B hB this have hB_eq : B = {x}αΆ := by have hsub : B β {x}αΆ := by intro y hy simp only [mem_compl, mem_singleton] rintro rfl exact hx_not_in_B hy have hcard_compl : ({x}αΆ : Finset (Fin 3)).card = 2 := by simp [card_compl] exact eq_of_subset_of_card_le hsub (by rw [hBc, hcard_compl]) obtain β¨k, hki, hkjβ© := op_1370_case_n3_t3_exists_third i j hij obtain β¨C, hCβ© := hne k have hx_not_in_C : x β C := by intro hx_in_C have : A β C := by rw [hx] exact singleton_subset_iff.mpr hx_in_C exact hinc i k hki.symm A hA C hC this have hC_sub_B : C β B := by rw [hB_eq] intro y hy simp only [mem_compl, mem_singleton] rintro rfl exact hx_not_in_C hy exact hinc k j hkj C hC B hB hC_sub_Blemma op_1370_case_n3_t3_card_mem_eq_one_or_two (π : Fin 3 β Finset (Finset (Fin 3))) (hne : β i, (π i).Nonempty) (hinc : strongly_incomparable π) (i : Fin 3) {A : Finset (Fin 3)} (hA : A β π i) : A.card = 1 β¨ A.card = 2 := by have hle : A.card β€ 3 := by have := A.card_le_univ simpa using this have : A.card = 0 β¨ A.card = 1 β¨ A.card = 2 β¨ A.card = 3 := by omega rcases this with h | h | h | h Β· have : A = β := card_eq_zero.mp h subst this obtain β¨j, hjβ© : β j : Fin 3, i β j := by fin_cases i <;> decide obtain β¨B, hBβ© := hne j exact False.elim (hinc i j hj β hA B hB (empty_subset B)) Β· left; exact h Β· right; exact h Β· have : A = univ := eq_univ_of_card A (by simpa using h) subst this obtain β¨j, hjβ© : β j : Fin 3, j β i := by fin_cases i <;> decide obtain β¨B, hBβ© := hne j exact False.elim (hinc j i hj B hB univ hA (subset_univ B))lemma op_1370_case_n3_t3_no_card_one_and_two (π : Fin 3 β Finset (Finset (Fin 3))) (hne : β i, (π i).Nonempty) (hinc : strongly_incomparable π) (i j : Fin 3) {A B : Finset (Fin 3)} (hA : A β π i) (hB : B β π j) (hAc : A.card = 1) (hBc : B.card = 2) : False := by by_cases hij : i = j Β· subst hij obtain β¨k, hkβ© : β k : Fin 3, k β i := by fin_cases i <;> decide obtain β¨C, hCβ© := hne k rcases op_1370_case_n3_t3_card_mem_eq_one_or_two π hne hinc k hC with hC1 | hC2 Β· exact op_1370_case_n3_t3_no_card_one_and_two_ne π hne hinc k i hk hC hB hC1 hBc Β· exact op_1370_case_n3_t3_no_card_one_and_two_ne π hne hinc i k hk.symm hA hC hAc hC2 Β· exact op_1370_case_n3_t3_no_card_one_and_two_ne π hne hinc i j hij hA hB hAc hBclemma op_1370_case_n3_t3_all_one_or_all_two (π : Fin 3 β Finset (Finset (Fin 3))) (hne : β i, (π i).Nonempty) (hinc : strongly_incomparable π) : (β i, β A β π i, A.card = 1) β¨ (β i, β A β π i, A.card = 2) := by obtain β¨S, hSβ© := hne 0 rcases op_1370_case_n3_t3_card_mem_eq_one_or_two π hne hinc 0 hS with hS1 | hS2 Β· left intro i A hA rcases op_1370_case_n3_t3_card_mem_eq_one_or_two π hne hinc i hA with hA1 | hA2 Β· exact hA1 Β· exact False.elim (op_1370_case_n3_t3_no_card_one_and_two π hne hinc 0 i hS hA hS1 hA2) Β· right intro i A hA rcases op_1370_case_n3_t3_card_mem_eq_one_or_two π hne hinc i hA with hA1 | hA2 Β· exact False.elim (op_1370_case_n3_t3_no_card_one_and_two π hne hinc i 0 hA hS hA1 hS2) Β· exact hA2/-- Base case n = 3, t = 3 of OP-1370: three non-empty uncomplemented strongly incomparable families of subsets of [3] have total size at most 3. -/theorem op_1370_case_n3_t3 (π : Fin 3 β Finset (Finset (Fin 3))) (hne : β i, (π i).Nonempty) (hunc : β i, is_uncomplemented (π i)) (hinc : strongly_incomparable π) : β i, (π i).card β€ 3 := by have _ := hunc have hdisj : ((Finset.univ : Finset (Fin 3)) : Set (Fin 3)).PairwiseDisjoint π := by intro i _ j _ hij change Disjoint (π i) (π j) rw [Finset.disjoint_iff_ne] intro A hAi B hAj rintro rfl exact hinc i j hij A hAi A hAj subset_rfl have heq : (Finset.univ.biUnion π).card = β i, (π i).card := Finset.card_biUnion hdisj rw [β heq] rcases op_1370_case_n3_t3_all_one_or_all_two π hne hinc with h1 | h2 Β· have hsub : Finset.univ.biUnion π β Finset.powersetCard 1 (Finset.univ : Finset (Fin 3)) := by intro A hA rw [Finset.mem_biUnion] at hA obtain β¨i, -, hiβ© := hA rw [Finset.mem_powersetCard_univ] exact h1 i A hi have hle := Finset.card_le_card hsub have hpow : (Finset.powersetCard 1 (Finset.univ : Finset (Fin 3))).card = 3 := by rw [Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin] rfl omega Β· have hsub : Finset.univ.biUnion π β Finset.powersetCard 2 (Finset.univ : Finset (Fin 3)) := by intro A hA rw [Finset.mem_biUnion] at hA obtain β¨i, -, hiβ© := hA rw [Finset.mem_powersetCard_univ] exact h2 i A hi have hle := Finset.card_le_card hsub have hpow : (Finset.powersetCard 2 (Finset.univ : Finset (Fin 3))).card = 3 := by rw [Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin] rfl omega