cyclic_cubic_family_card
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.
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).
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
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.
uses
cyclic_cubic_family_card_e6,Finset.image_insert,Finset.image_singleton,Finset.card_image_of_injective,Finset.image_injectivehave 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
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).
uses
Finset.mem_insert,Finset.mem_singleton,Finset.ext_iff.mphave 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
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.
uses
Finset.mem_biUnion,Finset.mem_Iic,Finset.mem_insert,Finset.mem_singleton,Finset.card_insert_of_notMem,Nat.card_Ico,Finset.mem_Icohave 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⟩
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).
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_singletonhave 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
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.
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.mprhave 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)
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.
uses
Finset.mem_union,Finset.mem_insert,Finset.mem_singleton,Finset.mem_Ico,Finset.mem_Iiohave 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
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.
uses
Finset.disjoint_left,le_antisymm,Finset.mem_Ico,Finset.disjoint_union_left.mprhave 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⟩
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.
uses
Finset.card_image_of_injOn,Finset.card_union_of_disjointrw [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
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.
/-- 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