AFTD Auto-Formalizing Theoretical Domains

cyclic_cubic_family_card

theoremverified

For any n ≥ 6, the cardinality of cyclic_cubic_family n is 2 * n + 5.

Statement

theorem cyclic_cubic_family_card (n : ℕ) (hn : 6 ≤ n) : (cyclic_cubic_family n).card = 2 * n + 5
Source
step towards cyclic_cubic_t_count_upper_bound
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • cyclic_cubic_familyThe explicit parametric parity family on n qubits consists of 10 boundary parities (Group A), 2(n-4) running parities (Group B), and 3…

The proof, explained

The proof sets n = m + 6 with m ≥ 0 and expresses cyclic_cubic_family (m + 6) as the image under an embedding T of three families of integer subsets: a boundary family A of 10 subsets, a chain family B of 2(m + 2) subsets, and a tail family C of 3 subsets. The cardinalities |A| = 10, |B| = 2(m + 2), and |C| = 3 are established directly, with B partitioned into m + 2 disjoint pairs indexed by k ≤ m + 1. The families A, B, and C are shown to be mutually disjoint using set size bounds and specific element inclusions and exclusions. Since T is injective on their union, the total cardinality is |A| + |B| + |C| = 10 + 2(m + 2) + 3 = 2(m + 6) + 5 = 2n + 5.

  1. Write n = m + 6 and represent cyclic_cubic_family (m + 6) as the image under T of the union of three families of integer subsets A, B, and C.

    Since n ≥ 6, we set m = n - 6, so n = m + 6 with m ≥ 0. Under this shift, the definition of cyclic_cubic_family (m + 6) is the image under T(s) = {i ∈ Fin (m + 6) | i ∈ s} of three families of finite subsets of ℕ: A (a boundary family of 10 subsets), B (a chain family indexed by k ≤ m + 1), and C (a tail family of 3 subsets).

    lines 14–19

      obtain ⟨m, rfl⟩ : ∃ m, n = m + 6 := ⟨n - 6, by omega⟩
      let T : Finset ℕ → Finset (Fin (m + 6)) := fun s => {i | (i : ℕ) ∈ s}
      let A : Finset (Finset ℕ) := {{1}, {0,1}, {m+3}, {0,m+4}, {m+3,m+4}, {1,m+5}, {0,1,m+5}, {m+2,m+5}, {m+2,m+3,m+5}, {0,m+4,m+5}}
      let B : Finset (Finset ℕ) := (Finset.Iic (m+1)).biUnion fun k => ({insert k (Finset.Ico (k+3) (m+6)), insert k (insert (k+1) (Finset.Ico (k+3) (m+6)))} : Finset (Finset ℕ))
      let C : Finset (Finset ℕ) := ({Finset.Ico 2 (m+6), insert 0 (Finset.Ico 2 (m+6)), Finset.Iio (m+6)} : Finset (Finset ℕ))
      have hfam : cyclic_cubic_family (m+6) = (A ∪ B ∪ C).image T := rfl
  2. The family A has cardinality 10.

    We define cyclic_cubic_family_card_e6 m : Fin 6 → ℕ mapping (0, 1, 2, 3, 4, 5) to (0, 1, m+2, m+3, m+4, m+5), and show it is injective by checking all 36 index pairs. We then show that A is the image under this injection of a fixed template family of 10 subsets of Fin 6. Since injective images preserve cardinality and the template family has 10 elements by evaluation, |A| = 10.

    lines 20–28

    uses cyclic_cubic_family_card_e6, Finset.image_insert, Finset.image_singleton, Finset.card_image_of_injective, Finset.image_injective

      have hinj_e : Function.Injective (cyclic_cubic_family_card_e6 m) := by
        intro a b h
        fin_cases a <;> fin_cases b <;> simp only [cyclic_cubic_family_card_e6] at h <;> omega
      have hA_template : A = ({{1}, {0,1}, {3}, {0,4}, {3,4}, {1,5}, {0,1,5}, {2,5}, {2,3,5}, {0,4,5}} : Finset (Finset (Fin 6))).image (fun s => s.image (cyclic_cubic_family_card_e6 m)) := by
        simp only [A, Finset.image_insert, Finset.image_singleton]
        rfl
      have hAcard : A.card = 10 := by
        rw [hA_template, Finset.card_image_of_injective _ (Finset.image_injective hinj_e)]
        decide
  3. Every set in A has at most 3 elements, and none of them equals {m+1, m+4, m+5}.

    Exhausting the 10 explicit subsets in A shows that each has cardinality at most 3. Furthermore, each subset is shown distinct from {m+1, m+4, m+5} by exhibiting an element on which they differ (for example, m+5, m+4, 0, or m+2).

    lines 29–46

    uses Finset.mem_insert, Finset.mem_singleton, Finset.ext_iff.mp

      have hAcardle : ∀ S ∈ A, S.card ≤ 3 := by
        intro S hS
        simp only [A, Finset.mem_insert, Finset.mem_singleton] at hS
        rcases hS with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> simp
      have hAnotB : ∀ S ∈ A, S ≠ ({m+1, m+4, m+5} : Finset ℕ) := by
        intro S hS
        simp only [A, Finset.mem_insert, Finset.mem_singleton] at hS
        rcases hS with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl
        · intro h; have hh := Finset.ext_iff.mp h (m+5); simp at hh
        · intro h; have hh := Finset.ext_iff.mp h (m+5); simp at hh
        · intro h; have hh := Finset.ext_iff.mp h (m+5); simp at hh
        · intro h; have hh := Finset.ext_iff.mp h (m+5); simp at hh
        · intro h; have hh := Finset.ext_iff.mp h (m+5); simp at hh
        · intro h; have hh := Finset.ext_iff.mp h (m+4); simp at hh
        · intro h; have hh := Finset.ext_iff.mp h 0; simp at hh
        · intro h; have hh := Finset.ext_iff.mp h (m+4); simp at hh
        · intro h; have hh := Finset.ext_iff.mp h (m+2); simp at hh
        · intro h; have hh := Finset.ext_iff.mp h 0; simp at hh
  4. Sets in B have size at least 3, their unique 3-element set is {m+1, m+4, m+5}, and each misses some integer k+2 with k ≤ m+1.

    A set S is in B if and only if it equals {k} ∪ [k+3, m+6) or {k, k+1} ∪ [k+3, m+6) for some k ≤ m+1. These have cardinalities m+4-k and m+5-k respectively, which are both ≥ 3 since k ≤ m+1. The cardinality can only be 3 if m+4-k = 3, forcing k = m+1 and yielding {m+1, m+4, m+5}. In both cases, the element k+2 is omitted from S.

    lines 47–81

    uses Finset.mem_biUnion, Finset.mem_Iic, Finset.mem_insert, Finset.mem_singleton, Finset.card_insert_of_notMem, Nat.card_Ico, Finset.mem_Ico

      have hBmem : ∀ S, S ∈ B ↔ ∃ k, k ≤ m + 1 ∧ (S = insert k (Finset.Ico (k+3) (m+6)) ∨ S = insert k (insert (k+1) (Finset.Ico (k+3) (m+6)))) := by
        intro S
        simp only [B, Finset.mem_biUnion, Finset.mem_Iic, Finset.mem_insert, Finset.mem_singleton]
      have hBcard1 : ∀ k, k ≤ m + 1 → (insert k (Finset.Ico (k+3) (m+6)) : Finset ℕ).card = m + 4 - k := by
        intro k hk
        rw [Finset.card_insert_of_notMem (by simp [Finset.mem_Ico]), Nat.card_Ico]
        omega
      have hBcard2 : ∀ k, k ≤ m + 1 → (insert k (insert (k+1) (Finset.Ico (k+3) (m+6))) : Finset ℕ).card = m + 5 - k := by
        intro k hk
        rw [Finset.card_insert_of_notMem (by simp [Finset.mem_Ico]), Finset.card_insert_of_notMem (by simp [Finset.mem_Ico]), Nat.card_Ico]
        omega
      have hBge : ∀ S ∈ B, 3 ≤ S.card := by
        intro S hS
        rw [hBmem S] at hS
        obtain ⟨k, hk, rfl | rfl⟩ := hS
        · rw [hBcard1 k hk]; omega
        · rw [hBcard2 k hk]; omega
      have hBeq3 : ∀ S ∈ B, S.card = 3 → S = ({m+1, m+4, m+5} : Finset ℕ) := by
        intro S hS hc
        rw [hBmem S] at hS
        obtain ⟨k, hk, rfl | rfl⟩ := hS
        · rw [hBcard1 k hk] at hc
          have hk' : k = m + 1 := by omega
          subst hk'
          have hIco : Finset.Ico (m+1+3) (m+6) = ({m+4, m+5} : Finset ℕ) := by
            ext x; simp [Finset.mem_Ico]; omega
          rw [hIco]
        · rw [hBcard2 k hk] at hc
          omega
      have hBmiss : ∀ S ∈ B, ∃ k, k ≤ m + 1 ∧ k + 2 ∉ S := by
        intro S hS
        rw [hBmem S] at hS
        obtain ⟨k, hk, rfl | rfl⟩ := hS
        · exact ⟨k, hk, by intro h; simp only [Finset.mem_insert, Finset.mem_Ico] at h; omega⟩
        · exact ⟨k, hk, by intro h; simp only [Finset.mem_insert, Finset.mem_Ico] at h; omega⟩
  5. The family B has cardinality 2 * (m + 2).

    For each k ≤ m+1, the pair of sets has cardinality 2 because k+1 belongs to the second set but not the first. For distinct indices k and l, the corresponding pairs are disjoint because the minimum element of any set generated by k is k. Summing 2 over all m+2 values of k gives |B| = 2(m + 2).

    lines 82–115

    uses Finset.mem_insert, Finset.mem_Ico, Finset.card_insert_of_notMem, Finset.card_singleton, Finset.card_biUnion, Finset.sum_congr, Finset.sum_const, Nat.card_Iic, smul_eq_mul, Finset.disjoint_left, Finset.mem_singleton

      have hBcard : B.card = 2 * (m + 2) := by
        have hBpaircard : ∀ k, ({insert k (Finset.Ico (k+3) (m+6)), insert k (insert (k+1) (Finset.Ico (k+3) (m+6)))} : Finset (Finset ℕ)).card = 2 := by
          intro k
          have hne : (insert k (Finset.Ico (k+3) (m+6)) : Finset ℕ) ≠ insert k (insert (k+1) (Finset.Ico (k+3) (m+6))) := by
            intro h
            have hmem : k+1 ∈ insert k (insert (k+1) (Finset.Ico (k+3) (m+6))) := by simp
            rw [← h] at hmem
            simp only [Finset.mem_insert, Finset.mem_Ico] at hmem
            omega
          rw [Finset.card_insert_of_notMem (by simpa using hne), Finset.card_singleton]
        simp only [B]
        rw [Finset.card_biUnion]
        · rw [Finset.sum_congr rfl (fun k _ => hBpaircard k)]
          simp only [Finset.sum_const, Nat.card_Iic, smul_eq_mul]
          ring
        · intro k hk l hl hkl
          show Disjoint _ _
          rw [Finset.disjoint_left]
          intro S hS hT
          have hkS : k ∈ S ∧ ∀ x ∈ S, k ≤ x := by
            simp only [Finset.mem_insert, Finset.mem_singleton] at hS
            rcases hS with rfl | rfl
            · exact ⟨by simp, by intro x hx; simp only [Finset.mem_insert, Finset.mem_Ico] at hx; omega⟩
            · exact ⟨by simp, by intro x hx; simp only [Finset.mem_insert, Finset.mem_Ico] at hx; omega⟩
          have hlT : l ∈ S ∧ ∀ x ∈ S, l ≤ x := by
            simp only [Finset.mem_insert, Finset.mem_singleton] at hT
            rcases hT with rfl | rfl
            · exact ⟨by simp, by intro x hx; simp only [Finset.mem_insert, Finset.mem_Ico] at hx; omega⟩
            · exact ⟨by simp, by intro x hx; simp only [Finset.mem_insert, Finset.mem_Ico] at hx; omega⟩
          obtain ⟨h1, h2⟩ := hkS
          obtain ⟨h3, h4⟩ := hlT
          have h1' : k ≤ l := h2 l h3
          have h2' : l ≤ k := h4 k h1
          omega
  6. The family C has cardinality 3, each of its sets has at least 4 elements, and each contains [2, m+6).

    The three defining sets of C are [2, m+6), {0} ∪ [2, m+6), and [0, m+6). They are distinct because 0 and 1 separate them, so |C| = 3. Each set contains [2, m+6) as a subset, and since |[2, m+6)| = m+4 ≥ 4, every set in C has cardinality at least 4.

    lines 116–144

    uses Finset.mem_insert, Finset.mem_singleton, not_or, congrArg, Finset.card_insert_of_notMem, Nat.card_Ico, Nat.card_Iio, Finset.Subset.refl, Finset.mem_insert_of_mem, Finset.mem_Ico, Finset.mem_Iio.mpr

      have hCcard : C.card = 3 := by
        have h1 : Finset.Ico 2 (m+6) ∉ ({insert 0 (Finset.Ico 2 (m+6)), Finset.Iio (m+6)} : Finset (Finset ℕ)) := by
          simp only [Finset.mem_insert, Finset.mem_singleton, not_or]
          constructor
          · intro h; have := congrArg (fun s => (0:ℕ) ∈ s) h; simp at this
          · intro h; have := congrArg (fun s => (1:ℕ) ∈ s) h; simp at this
        have h2 : insert 0 (Finset.Ico 2 (m+6)) ∉ ({Finset.Iio (m+6)} : Finset (Finset ℕ)) := by
          simp only [Finset.mem_singleton]
          intro h; have := congrArg (fun s => (1:ℕ) ∈ s) h; simp at this
        simp only [C]
        rw [Finset.card_insert_of_notMem h1, Finset.card_insert_of_notMem h2]
        rfl
      have hCge : ∀ S ∈ C, 4 ≤ S.card := by
        intro S hS
        simp only [C, Finset.mem_insert, Finset.mem_singleton] at hS
        rcases hS with rfl | rfl | rfl
        · rw [Nat.card_Ico]; omega
        · rw [Finset.card_insert_of_notMem (by simp [Finset.mem_Ico]), Nat.card_Ico]; omega
        · rw [Nat.card_Iio]; omega
      have hCsup : ∀ T ∈ C, Finset.Ico 2 (m+6) ⊆ T := by
        intro U hU
        simp only [C, Finset.mem_insert, Finset.mem_singleton] at hU
        rcases hU with rfl | rfl | rfl
        · exact Finset.Subset.refl _
        · intro x hx
          exact Finset.mem_insert_of_mem hx
        · intro x hx
          simp only [Finset.mem_Ico] at hx
          exact Finset.mem_Iio.mpr (by omega)
  7. Every element of every set in A ∪ B ∪ C is strictly less than m + 6, making T injective on A ∪ B ∪ C.

    Case analysis over the definitions shows all elements in any S ∈ A ∪ B ∪ C are bounded by m+6. Because no elements exceed the domain of Fin (m+6), the mapping T(S) = {i ∈ Fin (m+6) | i ∈ S} preserves the sets faithfully, so T is injective on A ∪ B ∪ C.

    lines 145–171

    uses Finset.mem_union, Finset.mem_insert, Finset.mem_singleton, Finset.mem_Ico, Finset.mem_Iio

      have hbound : ∀ S ∈ A ∪ B ∪ C, ∀ x ∈ S, x < m + 6 := by
        intro S hS x hx
        simp only [Finset.mem_union] at hS
        rcases hS with (hSA | hSB) | hSC
        · simp only [A, Finset.mem_insert, Finset.mem_singleton] at hSA
          rcases hSA with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl <;>
            (simp only [Finset.mem_insert, Finset.mem_singleton] at hx) <;> omega
        · rw [hBmem S] at hSB
          obtain ⟨k, hk, rfl | rfl⟩ := hSB <;>
            (simp only [Finset.mem_insert, Finset.mem_Ico] at hx) <;> omega
        · simp only [C, Finset.mem_insert, Finset.mem_singleton] at hSC
          rcases hSC with rfl | rfl | rfl <;>
            (simp only [Finset.mem_insert, Finset.mem_Ico, Finset.mem_Iio] at hx) <;> omega
      have hinj : Set.InjOn T ↑(A ∪ B ∪ C) := by
        intro S hS S' hS' h
        have h1 := hbound S hS
        have h2 := hbound S' hS'
        ext x
        constructor
        · intro hx
          have hmem : (⟨x, h1 x hx⟩ : Fin (m + 6)) ∈ T S := by simpa [T] using hx
          rw [h] at hmem
          simpa [T] using hmem
        · intro hx
          have hmem : (⟨x, h2 x hx⟩ : Fin (m + 6)) ∈ T S' := by simpa [T] using hx
          rw [← h] at hmem
          simpa [T] using hmem
  8. The families A, B, and C are pairwise disjoint, so (A ∪ B) is disjoint from C.

    A and C are disjoint because sets in A have size ≤ 3 while sets in C have size ≥ 4. A and B are disjoint because any intersection element must have size 3, but the only size-3 element of B is not in A. B and C are disjoint because every set in B omits some element k+2 ∈ [2, m+6), whereas every set in C contains all of [2, m+6). Hence (A ∪ B) is disjoint from C.

    lines 172–190

    uses Finset.disjoint_left, le_antisymm, Finset.mem_Ico, Finset.disjoint_union_left.mpr

      have hAC : Disjoint A C := by
        rw [Finset.disjoint_left]
        intro S hSA hSC
        have h1 := hAcardle S hSA
        have h2 := hCge S hSC
        omega
      have hAB : Disjoint A B := by
        rw [Finset.disjoint_left]
        intro S hSA hSB
        have h1 := hAcardle S hSA
        have h2 := hBge S hSB
        have h3 : S.card = 3 := le_antisymm h1 h2
        exact hAnotB S hSA (hBeq3 S hSB h3)
      have hBC : Disjoint B C := by
        rw [Finset.disjoint_left]
        intro S hSB hSC
        obtain ⟨k, hk, hmiss⟩ := hBmiss S hSB
        exact hmiss (hCsup S hSC (by simp only [Finset.mem_Ico]; omega))
      have hABC : Disjoint (A ∪ B) C := Finset.disjoint_union_left.mpr ⟨hAC, hBC⟩
  9. The cardinality of cyclic_cubic_family n is 2 * n + 5.

    Since T is injective on A ∪ B ∪ C, the cardinality equals |A ∪ B ∪ C|. Because A, B, and C are mutually disjoint, this sum is |A| + |B| + |C| = 10 + 2(m + 2) + 3 = 2m + 17 = 2(m + 6) + 5 = 2n + 5.

    lines 191–193

    uses Finset.card_image_of_injOn, Finset.card_union_of_disjoint

      rw [hfam, Finset.card_image_of_injOn hinj]
      rw [Finset.card_union_of_disjoint hABC, Finset.card_union_of_disjoint hAB, hAcard, hBcard, hCcard]
      omega
cyclic_cubic_family_card_e6
The map sending indices 0 through 5 of Fin 6 to 0, 1, m+2, m+3, m+4, and m+5 respectively.
Finset.image_insert
The image of inserting an element into a finite set is the insertion of its image into the image set.
Finset.image_singleton
The image of a singleton set under a function is the singleton of the function applied to that element.
Finset.card_image_of_injective
An injective function preserves the cardinality of any finite set under taking its image.
Finset.image_injective
If a function between elements is injective, the induced map taking images of finite sets is also injective.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to a singleton set if and only if it equals the single element.
Finset.ext_iff.mp
Equal sets have the exact same elements.
Finset.mem_biUnion
An element belongs to an indexed union of finite sets if and only if it belongs to one of the component sets.
Finset.mem_Iic
An element belongs to the closed interval up to a if and only if it is less than or equal to a.
Finset.card_insert_of_notMem
Inserting an element not already in a finite set increases its cardinality by 1.
Nat.card_Ico
The cardinality of the half-open interval of natural numbers [a, b) is b - a.
Finset.mem_Ico
An element belongs to the half-open interval [a, b) if and only if a ≤ x and x < b.
Finset.card_singleton
A singleton set has cardinality 1.
Finset.card_biUnion
The cardinality of a pairwise disjoint union of finite sets is the sum of their individual cardinalities.
Finset.sum_congr
Sums of pointwise equal functions over equal finite sets are equal.
Finset.sum_const
The sum of a constant value over a finite set equals the cardinality of the set multiplied by that value.
Nat.card_Iic
The cardinality of the closed interval [0, b] of natural numbers is b + 1.
smul_eq_mul
Scalar multiplication of natural numbers is ordinary multiplication.
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
not_or
The negation of a disjunction is the conjunction of the negations.
congrArg
Applying a function to equal arguments yields equal results.
Nat.card_Iio
The cardinality of the open-right interval [0, b) of natural numbers is b.
Finset.Subset.refl
Every finite set is a subset of itself.
Finset.mem_insert_of_mem
If an element belongs to a finite set, it also belongs to that set with any element inserted.
Finset.mem_Iio.mpr
If x < a, then x belongs to the open-right interval [0, a).
Finset.mem_union
An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
Finset.mem_Iio
An element belongs to the open-right interval [0, a) if and only if it is strictly less than a.
le_antisymm
If a ≤ b and b ≤ a in a partial order, then a = b.
Finset.disjoint_union_left.mpr
If two sets are each disjoint from a third set, their union is also disjoint from that third set.
Finset.card_image_of_injOn
If a function is injective on a finite set, the cardinality of its image equals the cardinality of the original set.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.

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

/-- The six-element alphabet `0, 1, m+2, m+3, m+4, m+5` indexing the boundary setsof `cyclic_cubic_family (m+6)`; used to identify the boundary group with a fixedfamily of ten subsets of `Fin 6`. -/def cyclic_cubic_family_card_e6 (m : ℕ) : Fin 6 → ℕ  | ⟨0, _⟩ => 0  | ⟨1, _⟩ => 1  | ⟨2, _⟩ => m + 2  | ⟨3, _⟩ => m + 3  | ⟨4, _⟩ => m + 4  | _ => m + 5/-- The explicit parametric parity family on n qubits has cardinality 2 * n + 5 for all n ≥ 6. -/theorem cyclic_cubic_family_card (n : ℕ) (hn : 6 ≤ n) : (cyclic_cubic_family n).card = 2 * n + 5 := by  obtain ⟨m, rfl⟩ : ∃ m, n = m + 6 := ⟨n - 6, by omega⟩  let T : Finset ℕ → Finset (Fin (m + 6)) := fun s => {i | (i : ℕ) ∈ s}  let A : Finset (Finset ℕ) := {{1}, {0,1}, {m+3}, {0,m+4}, {m+3,m+4}, {1,m+5}, {0,1,m+5}, {m+2,m+5}, {m+2,m+3,m+5}, {0,m+4,m+5}}  let B : Finset (Finset ℕ) := (Finset.Iic (m+1)).biUnion fun k => ({insert k (Finset.Ico (k+3) (m+6)), insert k (insert (k+1) (Finset.Ico (k+3) (m+6)))} : Finset (Finset ℕ))  let C : Finset (Finset ℕ) := ({Finset.Ico 2 (m+6), insert 0 (Finset.Ico 2 (m+6)), Finset.Iio (m+6)} : Finset (Finset ℕ))  have hfam : cyclic_cubic_family (m+6) = (A ∪ B ∪ C).image T := rfl  have hinj_e : Function.Injective (cyclic_cubic_family_card_e6 m) := by    intro a b h    fin_cases a <;> fin_cases b <;> simp only [cyclic_cubic_family_card_e6] at h <;> omega  have hA_template : A = ({{1}, {0,1}, {3}, {0,4}, {3,4}, {1,5}, {0,1,5}, {2,5}, {2,3,5}, {0,4,5}} : Finset (Finset (Fin 6))).image (fun s => s.image (cyclic_cubic_family_card_e6 m)) := by    simp only [A, Finset.image_insert, Finset.image_singleton]    rfl  have hAcard : A.card = 10 := by    rw [hA_template, Finset.card_image_of_injective _ (Finset.image_injective hinj_e)]    decide  have hAcardle : ∀ S ∈ A, S.card ≤ 3 := by    intro S hS    simp only [A, Finset.mem_insert, Finset.mem_singleton] at hS    rcases hS with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> simp  have hAnotB : ∀ S ∈ A, S ≠ ({m+1, m+4, m+5} : Finset ℕ) := by    intro S hS    simp only [A, Finset.mem_insert, Finset.mem_singleton] at hS    rcases hS with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl    · intro h; have hh := Finset.ext_iff.mp h (m+5); simp at hh    · intro h; have hh := Finset.ext_iff.mp h (m+5); simp at hh    · intro h; have hh := Finset.ext_iff.mp h (m+5); simp at hh    · intro h; have hh := Finset.ext_iff.mp h (m+5); simp at hh    · intro h; have hh := Finset.ext_iff.mp h (m+5); simp at hh    · intro h; have hh := Finset.ext_iff.mp h (m+4); simp at hh    · intro h; have hh := Finset.ext_iff.mp h 0; simp at hh    · intro h; have hh := Finset.ext_iff.mp h (m+4); simp at hh    · intro h; have hh := Finset.ext_iff.mp h (m+2); simp at hh    · intro h; have hh := Finset.ext_iff.mp h 0; simp at hh  have hBmem : ∀ S, S ∈ B ↔ ∃ k, k ≤ m + 1 ∧ (S = insert k (Finset.Ico (k+3) (m+6)) ∨ S = insert k (insert (k+1) (Finset.Ico (k+3) (m+6)))) := by    intro S    simp only [B, Finset.mem_biUnion, Finset.mem_Iic, Finset.mem_insert, Finset.mem_singleton]  have hBcard1 : ∀ k, k ≤ m + 1 → (insert k (Finset.Ico (k+3) (m+6)) : Finset ℕ).card = m + 4 - k := by    intro k hk    rw [Finset.card_insert_of_notMem (by simp [Finset.mem_Ico]), Nat.card_Ico]    omega  have hBcard2 : ∀ k, k ≤ m + 1 → (insert k (insert (k+1) (Finset.Ico (k+3) (m+6))) : Finset ℕ).card = m + 5 - k := by    intro k hk    rw [Finset.card_insert_of_notMem (by simp [Finset.mem_Ico]), Finset.card_insert_of_notMem (by simp [Finset.mem_Ico]), Nat.card_Ico]    omega  have hBge : ∀ S ∈ B, 3 ≤ S.card := by    intro S hS    rw [hBmem S] at hS    obtain ⟨k, hk, rfl | rfl⟩ := hS    · rw [hBcard1 k hk]; omega    · rw [hBcard2 k hk]; omega  have hBeq3 : ∀ S ∈ B, S.card = 3 → S = ({m+1, m+4, m+5} : Finset ℕ) := by    intro S hS hc    rw [hBmem S] at hS    obtain ⟨k, hk, rfl | rfl⟩ := hS    · rw [hBcard1 k hk] at hc      have hk' : k = m + 1 := by omega      subst hk'      have hIco : Finset.Ico (m+1+3) (m+6) = ({m+4, m+5} : Finset ℕ) := by        ext x; simp [Finset.mem_Ico]; omega      rw [hIco]    · rw [hBcard2 k hk] at hc      omega  have hBmiss : ∀ S ∈ B, ∃ k, k ≤ m + 1 ∧ k + 2 ∉ S := by    intro S hS    rw [hBmem S] at hS    obtain ⟨k, hk, rfl | rfl⟩ := hS    · exact ⟨k, hk, by intro h; simp only [Finset.mem_insert, Finset.mem_Ico] at h; omega⟩    · exact ⟨k, hk, by intro h; simp only [Finset.mem_insert, Finset.mem_Ico] at h; omega⟩  have hBcard : B.card = 2 * (m + 2) := by    have hBpaircard : ∀ k, ({insert k (Finset.Ico (k+3) (m+6)), insert k (insert (k+1) (Finset.Ico (k+3) (m+6)))} : Finset (Finset ℕ)).card = 2 := by      intro k      have hne : (insert k (Finset.Ico (k+3) (m+6)) : Finset ℕ) ≠ insert k (insert (k+1) (Finset.Ico (k+3) (m+6))) := by        intro h        have hmem : k+1 ∈ insert k (insert (k+1) (Finset.Ico (k+3) (m+6))) := by simp        rw [← h] at hmem        simp only [Finset.mem_insert, Finset.mem_Ico] at hmem        omega      rw [Finset.card_insert_of_notMem (by simpa using hne), Finset.card_singleton]    simp only [B]    rw [Finset.card_biUnion]    · rw [Finset.sum_congr rfl (fun k _ => hBpaircard k)]      simp only [Finset.sum_const, Nat.card_Iic, smul_eq_mul]      ring    · intro k hk l hl hkl      show Disjoint _ _      rw [Finset.disjoint_left]      intro S hS hT      have hkS : k ∈ S ∧ ∀ x ∈ S, k ≤ x := by        simp only [Finset.mem_insert, Finset.mem_singleton] at hS        rcases hS with rfl | rfl        · exact ⟨by simp, by intro x hx; simp only [Finset.mem_insert, Finset.mem_Ico] at hx; omega⟩        · exact ⟨by simp, by intro x hx; simp only [Finset.mem_insert, Finset.mem_Ico] at hx; omega⟩      have hlT : l ∈ S ∧ ∀ x ∈ S, l ≤ x := by        simp only [Finset.mem_insert, Finset.mem_singleton] at hT        rcases hT with rfl | rfl        · exact ⟨by simp, by intro x hx; simp only [Finset.mem_insert, Finset.mem_Ico] at hx; omega⟩        · exact ⟨by simp, by intro x hx; simp only [Finset.mem_insert, Finset.mem_Ico] at hx; omega⟩      obtain ⟨h1, h2⟩ := hkS      obtain ⟨h3, h4⟩ := hlT      have h1' : k ≤ l := h2 l h3      have h2' : l ≤ k := h4 k h1      omega  have hCcard : C.card = 3 := by    have h1 : Finset.Ico 2 (m+6) ∉ ({insert 0 (Finset.Ico 2 (m+6)), Finset.Iio (m+6)} : Finset (Finset ℕ)) := by      simp only [Finset.mem_insert, Finset.mem_singleton, not_or]      constructor      · intro h; have := congrArg (fun s => (0:ℕ) ∈ s) h; simp at this      · intro h; have := congrArg (fun s => (1:ℕ) ∈ s) h; simp at this    have h2 : insert 0 (Finset.Ico 2 (m+6)) ∉ ({Finset.Iio (m+6)} : Finset (Finset ℕ)) := by      simp only [Finset.mem_singleton]      intro h; have := congrArg (fun s => (1:ℕ) ∈ s) h; simp at this    simp only [C]    rw [Finset.card_insert_of_notMem h1, Finset.card_insert_of_notMem h2]    rfl  have hCge : ∀ S ∈ C, 4 ≤ S.card := by    intro S hS    simp only [C, Finset.mem_insert, Finset.mem_singleton] at hS    rcases hS with rfl | rfl | rfl    · rw [Nat.card_Ico]; omega    · rw [Finset.card_insert_of_notMem (by simp [Finset.mem_Ico]), Nat.card_Ico]; omega    · rw [Nat.card_Iio]; omega  have hCsup : ∀ T ∈ C, Finset.Ico 2 (m+6) ⊆ T := by    intro U hU    simp only [C, Finset.mem_insert, Finset.mem_singleton] at hU    rcases hU with rfl | rfl | rfl    · exact Finset.Subset.refl _    · intro x hx      exact Finset.mem_insert_of_mem hx    · intro x hx      simp only [Finset.mem_Ico] at hx      exact Finset.mem_Iio.mpr (by omega)  have hbound : ∀ S ∈ A ∪ B ∪ C, ∀ x ∈ S, x < m + 6 := by    intro S hS x hx    simp only [Finset.mem_union] at hS    rcases hS with (hSA | hSB) | hSC    · simp only [A, Finset.mem_insert, Finset.mem_singleton] at hSA      rcases hSA with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl <;>        (simp only [Finset.mem_insert, Finset.mem_singleton] at hx) <;> omega    · rw [hBmem S] at hSB      obtain ⟨k, hk, rfl | rfl⟩ := hSB <;>        (simp only [Finset.mem_insert, Finset.mem_Ico] at hx) <;> omega    · simp only [C, Finset.mem_insert, Finset.mem_singleton] at hSC      rcases hSC with rfl | rfl | rfl <;>        (simp only [Finset.mem_insert, Finset.mem_Ico, Finset.mem_Iio] at hx) <;> omega  have hinj : Set.InjOn T ↑(A ∪ B ∪ C) := by    intro S hS S' hS' h    have h1 := hbound S hS    have h2 := hbound S' hS'    ext x    constructor    · intro hx      have hmem : (⟨x, h1 x hx⟩ : Fin (m + 6)) ∈ T S := by simpa [T] using hx      rw [h] at hmem      simpa [T] using hmem    · intro hx      have hmem : (⟨x, h2 x hx⟩ : Fin (m + 6)) ∈ T S' := by simpa [T] using hx      rw [← h] at hmem      simpa [T] using hmem  have hAC : Disjoint A C := by    rw [Finset.disjoint_left]    intro S hSA hSC    have h1 := hAcardle S hSA    have h2 := hCge S hSC    omega  have hAB : Disjoint A B := by    rw [Finset.disjoint_left]    intro S hSA hSB    have h1 := hAcardle S hSA    have h2 := hBge S hSB    have h3 : S.card = 3 := le_antisymm h1 h2    exact hAnotB S hSA (hBeq3 S hSB h3)  have hBC : Disjoint B C := by    rw [Finset.disjoint_left]    intro S hSB hSC    obtain ⟨k, hk, hmiss⟩ := hBmiss S hSB    exact hmiss (hCsup S hSC (by simp only [Finset.mem_Ico]; omega))  have hABC : Disjoint (A ∪ B) C := Finset.disjoint_union_left.mpr ⟨hAC, hBC⟩  rw [hfam, Finset.card_image_of_injOn hinj]  rw [Finset.card_union_of_disjoint hABC, Finset.card_union_of_disjoint hAB, hAcard, hBcard, hCcard]  omega
See it in the graphDiscuss this resultChallenge it