AFTD Auto-Formalizing Theoretical Domains

op_1370_twoblock_asymmetric_equality_counterexample

theoremverifiedoriginal

There exist two strongly incomparable uncomplemented families of subsets of a seven-element set, each varying at every coordinate, with cardinalities 40 and 24. Their total size is 64, and the two families cannot be complements of one another because their sizes differ.

Statement

theorem op_1370_twoblock_asymmetric_equality_counterexample : ∃ 𝒜 : Fin 2 → Finset (Finset (Fin 7)),
      (∀ i, is_uncomplemented (𝒜 i)) ∧ strongly_incomparable 𝒜 ∧
      (∀ i, ∀ x, (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 i, x ∉ T)) ∧
      (∑ i, (𝒜 i).card = 2^6) ∧ (𝒜 0).card = 40 ∧ (𝒜 1).card = 24
Related work
Counterexample to a proposed two-family equality-structure route for OP-1370, arXiv:2611.12199, Conjecture 4.3.
Verified
16 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

There exists a pair of families of subsets of Fin 7, represented as a map 𝒜 : Fin 2 → Finset (Finset (Fin 7)), such that: 1. For each i : Fin 2, 𝒜 i is uncomplemented (i.e., for every A ∈ 𝒜 i, its complement Aᶜ is not in 𝒜 i); 2. The family 𝒜 is strongly incomparable (i.e., for all i, j : Fin 2 with i ≠ j, no set in 𝒜 i is a subset of any set in 𝒜 j); 3. For each i : Fin 2 and every element x : Fin 7, there exists some S ∈ 𝒜 i containing x, and there exists some T ∈ 𝒜 i not containing x; 4. The sum of the cardinalities of 𝒜 0 and 𝒜 1 is 2^6 (64); 5. The cardinality of 𝒜 0 is 40; and 6. The cardinality of 𝒜 1 is 24.

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

The theorem demonstrates that two strongly incomparable uncomplemented families of subsets of a 7-element set can have total cardinality 2^6 = 64 while having unequal sizes (40 and 24), showing that equality in the size bound does not require the two families to be complements of each other. The counterexample is given by two concrete finite families A and B assembled into a pair f. Each required property—uncomplementedness, strong incomparability, coordinate variation, and cardinalities summing to 64—is verified by finite exhaustive computation in Lean's kernel (`decide +kernel`), and the existential result packages f with these verified properties.

  1. The family op1370_twoblock_asym_a of 40 subsets of Fin 7 is uncomplemented. automation

    Unfolding the definition of is_uncomplemented leaves the condition that for every set A in the family, its complement in Fin 7 is not in the family. Because this is a finite check over 40 explicit subsets, it is evaluated and closed directly in the Lean kernel via `decide +kernel`.

    line 7

    lemma op1370_twoblock_asym_a_uncomp : is_uncomplemented op1370_twoblock_asym_a := by unfold is_uncomplemented; decide +kernel
  2. The family op1370_twoblock_asym_b of 24 subsets of Fin 7 is uncomplemented. automation

    Unfolding is_uncomplemented leaves the goal that no set in op1370_twoblock_asym_b has its complement in the family. This condition over 24 explicit subsets is verified by direct kernel evaluation via `decide +kernel`.

    line 8

    lemma op1370_twoblock_asym_b_uncomp : is_uncomplemented op1370_twoblock_asym_b := by unfold is_uncomplemented; decide +kernel
  3. Both constituent families of op1370_twoblock_asym_f are uncomplemented.

    Introducing the index i in Fin 2 and splitting into cases (i = 0 and i = 1) reduces the goal to the uncomplementedness of op1370_twoblock_asym_a and op1370_twoblock_asym_b, which are discharged by rewriting with the definition of op1370_twoblock_asym_f and using op1370_twoblock_asym_a_uncomp and op1370_twoblock_asym_b_uncomp.

    line 10

    uses op1370_twoblock_asym_a_uncomp, op1370_twoblock_asym_b_uncomp

      intro i; fin_cases i <;> simp [op1370_twoblock_asym_f, op1370_twoblock_asym_a_uncomp, op1370_twoblock_asym_b_uncomp]
  4. The two families in op1370_twoblock_asym_f are strongly incomparable. automation

    Unfolding strongly_incomparable reduces the goal to checking that for distinct indices i ≠ j, no set in the i-th family is a subset of any set in the j-th family. This finite check over all 40 × 24 + 24 × 40 = 1920 pairs is evaluated and closed by `decide +kernel`.

    lines 12–13

      unfold strongly_incomparable
      decide +kernel
  5. Every coordinate in Fin 7 varies in each family of op1370_twoblock_asym_f. automation

    The condition that for each family i and each point x in Fin 7, there exists a set containing x and a set avoiding x, is a finite existential search over the explicit families, verified directly by kernel evaluation via `decide +kernel`.

    line 15

      decide +kernel
  6. The families in op1370_twoblock_asym_f have cardinalities 40 and 24, and their sum is 64. automation

    Computing the cardinalities of the two explicit finite sets gives 40 and 24, and their sum is 40 + 24 = 64 = 2^6. This arithmetic equality is checked by `decide +kernel`.

    line 16

    lemma op1370_twoblock_asym_f_card : (∑ i, (op1370_twoblock_asym_f i).card) = 2^6 ∧ (op1370_twoblock_asym_f 0).card = 40 ∧ (op1370_twoblock_asym_f 1).card = 24 := by decide +kernel
  7. There exists a 2-block family of subsets of Fin 7 satisfying all five counterexample conditions.

    The existential theorem is concluded by providing op1370_twoblock_asym_f as the witness, together with the proofs of the five conjuncts: uncomplementedness (op1370_twoblock_asym_f_uncomp), strong incomparability (op1370_twoblock_asym_f_incomp), coordinate variation (op1370_twoblock_asym_f_vary), and the cardinality equations (op1370_twoblock_asym_f_card).

    line 22

    uses op1370_twoblock_asym_f_uncomp, op1370_twoblock_asym_f_incomp, op1370_twoblock_asym_f_vary, op1370_twoblock_asym_f_card

      exact ⟨op1370_twoblock_asym_f, op1370_twoblock_asym_f_uncomp, op1370_twoblock_asym_f_incomp, op1370_twoblock_asym_f_vary, op1370_twoblock_asym_f_card⟩
op1370_twoblock_asym_a_uncomp
The 40-element family op1370_twoblock_asym_a is uncomplemented: no subset in the family has its complement in the family.
op1370_twoblock_asym_b_uncomp
The 24-element family op1370_twoblock_asym_b is uncomplemented: no subset in the family has its complement in the family.
op1370_twoblock_asym_f_uncomp
Both families in the pair op1370_twoblock_asym_f are uncomplemented.
op1370_twoblock_asym_f_incomp
The two families in op1370_twoblock_asym_f are strongly incomparable: no member of one family is a subset of any member of the other family.
op1370_twoblock_asym_f_vary
Every coordinate in Fin 7 varies in both families of op1370_twoblock_asym_f: for each coordinate and each family, at least one member contains the coordinate and at least one member does not.
op1370_twoblock_asym_f_card
The total cardinality of the families in op1370_twoblock_asym_f is 2^6 = 64, with the first family having size 40 and the second family having size 24.

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 6000000set_option maxRecDepth 8192def op1370_twoblock_asym_a : Finset (Finset (Fin 7)) := {{0, 2}, {1, 2}, {0, 1, 2}, {0, 2, 3}, {1, 2, 3}, {0, 1, 2, 3}, {0, 2, 4}, {1, 2, 4}, {0, 1, 2, 4}, {0, 5}, {1, 5}, {0, 1, 5}, {2, 5}, {0, 2, 5}, {1, 2, 5}, {0, 1, 2, 5}, {0, 3, 5}, {1, 3, 5}, {0, 1, 3, 5}, {2, 3, 5}, {0, 2, 3, 5}, {1, 2, 3, 5}, {0, 1, 2, 3, 5}, {0, 4, 5}, {1, 4, 5}, {0, 1, 4, 5}, {2, 4, 5}, {0, 2, 4, 5}, {1, 2, 4, 5}, {0, 1, 2, 4, 5}, {0, 2, 6}, {1, 2, 6}, {0, 1, 2, 6}, {0, 5, 6}, {1, 5, 6}, {0, 1, 5, 6}, {2, 5, 6}, {0, 2, 5, 6}, {1, 2, 5, 6}, {0, 1, 2, 5, 6}}def op1370_twoblock_asym_b : Finset (Finset (Fin 7)) := {{3, 4}, {0, 3, 4}, {1, 3, 4}, {0, 1, 3, 4}, {2, 3, 4}, {3, 4, 5}, {3, 6}, {0, 3, 6}, {1, 3, 6}, {0, 1, 3, 6}, {2, 3, 6}, {4, 6}, {0, 4, 6}, {1, 4, 6}, {0, 1, 4, 6}, {2, 4, 6}, {3, 4, 6}, {0, 3, 4, 6}, {1, 3, 4, 6}, {0, 1, 3, 4, 6}, {2, 3, 4, 6}, {3, 5, 6}, {4, 5, 6}, {3, 4, 5, 6}}def op1370_twoblock_asym_f : Fin 2 → Finset (Finset (Fin 7)) := ![op1370_twoblock_asym_a, op1370_twoblock_asym_b]lemma op1370_twoblock_asym_a_uncomp : is_uncomplemented op1370_twoblock_asym_a := by unfold is_uncomplemented; decide +kernellemma op1370_twoblock_asym_b_uncomp : is_uncomplemented op1370_twoblock_asym_b := by unfold is_uncomplemented; decide +kernellemma op1370_twoblock_asym_f_uncomp : ∀ i, is_uncomplemented (op1370_twoblock_asym_f i) := by  intro i; fin_cases i <;> simp [op1370_twoblock_asym_f, op1370_twoblock_asym_a_uncomp, op1370_twoblock_asym_b_uncomp]lemma op1370_twoblock_asym_f_incomp : strongly_incomparable op1370_twoblock_asym_f := by  unfold strongly_incomparable  decide +kernellemma op1370_twoblock_asym_f_vary : ∀ i : Fin 2, ∀ x : Fin 7, (∃ S ∈ op1370_twoblock_asym_f i, x ∈ S) ∧ (∃ T ∈ op1370_twoblock_asym_f i, x ∉ T) := by  decide +kernellemma op1370_twoblock_asym_f_card : (∑ i, (op1370_twoblock_asym_f i).card) = 2^6 ∧ (op1370_twoblock_asym_f 0).card = 40 ∧ (op1370_twoblock_asym_f 1).card = 24 := by decide +kerneltheorem op_1370_twoblock_asymmetric_equality_counterexample : ∃ 𝒜 : Fin 2 → Finset (Finset (Fin 7)),      (∀ i, is_uncomplemented (𝒜 i)) ∧ strongly_incomparable 𝒜 ∧      (∀ i, ∀ x, (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 i, x ∉ T)) ∧      (∑ i, (𝒜 i).card = 2^6) ∧ (𝒜 0).card = 40 ∧ (𝒜 1).card = 24 := by  exact ⟨op1370_twoblock_asym_f, op1370_twoblock_asym_f_uncomp, op1370_twoblock_asym_f_incomp, op1370_twoblock_asym_f_vary, op1370_twoblock_asym_f_card⟩
See it in the graphDiscuss this resultChallenge it