AFTD Auto-Formalizing Theoretical Domains

op_1370_case_n3_t3

theoremverifiedoriginal

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 all i j : ΞΉ with i β‰  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.

  1. test claim

    test explanation

    lines 3–135

    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

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
See it in the graphDiscuss this resultChallenge it