AFTD Auto-Formalizing Theoretical Domains

not_numerical_semigroup_count_fibonacci_recurrence

theoremverifiedoriginal

The statement numerical_semigroup_count_fibonacci_recurrence is false: The identity is false. Take F = 3, m = 2, g = 2: indeed F + 2 = 5 ≤ 6 = 3*m and m = 2 ≤ 2 = F - 1. LHS: n_{3,2,2} = 1. The complement of such a semigroup is contained in {0,1,2,3} (3 is a gap, everything ≥ 4 is in S), 0 is in S, multiplicity 2 forces 2 ∈ S and 1 ∉ S, and the genus is 2, so the gap set is exactly {1,3}. Hence the unique such semigroup is {0,2} ∪ [4,∞). RHS: n_{1,1,1} + n_{1,1,0} = 0 + 0. A semigroup with Frobenius number 1 has 1 as a gap (1 = sSup of the gap set, and the sSup of a finite nonempty set of naturals is a member of it), while multiplicity 1 forces 1 ∈ S (sInf of the positive elements is a member). Contradiction. So the claimed equation reads 1 = 0. The recurrence fails for every (F, m, g) = (F, F-1, F-1) with F ≥ 3 (the semigroup {0, F-1} ∪ [F+1,∞)); brute-force enumeration up to F = 18 finds no other failures. A probable correction is to add the hypothesis m ≤ F - 2 (equivalently F ≥ m + 2).

Statement

theorem not_numerical_semigroup_count_fibonacci_recurrence : ¬ (∀ (F m g : ℕ) (hlow : F + 2 ≤ 3 * m) (hhigh : m ≤ F - 1), numerical_semigroup_count F m g =
      numerical_semigroup_count (F - 2) (m - 1) (g - 1) +
      numerical_semigroup_count (F - 2) (m - 1) (g - 2))
Related work
refutes `numerical_semigroup_count_fibonacci_recurrence`
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • numerical_semigroup_countThe counting function n_{F,m,g} of numerical semigroups, defined as the number (cardinality) of numerical semigroups with Frobenius number…
  • NumericalSemigroupA numerical semigroup is an additive submonoid of the natural numbers whose complement in ℕ is finite.
  • numerical_semigroup_genusThe genus of a numerical semigroup S is the natural number defined as the cardinality of its complement in ℕ: Set.ncard ((S.toAddSubmonoid…
  • numerical_semigroup_multiplicityThe multiplicity of a numerical semigroup S is the natural number defined as the infimum of its strictly positive elements: sInf {x ∈…
  • numerical_semigroup_frobenius_numberThe Frobenius number of a numerical semigroup S is the natural number defined as the supremum of the complement of S in ℕ: sSup…

The proof, explained

The proof disproves the claimed Fibonacci-type recurrence for counting numerical semigroups by exhibiting a counterexample at parameters (F, m, g) = (3, 2, 2), which satisfy the hypotheses F + 2 ≤ 3m and m ≤ F - 1. At these values, the recurrence asserts that n_{3,2,2} = n_{1,1,1} + n_{1,1,0}. The proof constructs the semigroup S₀ = {0, 2} ∪ [4, ∞) and proves it is the unique numerical semigroup with invariants (3, 2, 2), establishing that the left-hand side is 1. On the right-hand side, no numerical semigroup can have both Frobenius number 1 and multiplicity 1 (since 1 would have to be both in the semigroup and in its gap set), so both terms vanish. This forces 1 = 0, refuting the recurrence.

  1. Assume for contradiction that the Fibonacci recurrence holds for all valid parameters.

    We introduce the universal hypothesis `hcontra`, which asserts that for all natural numbers F, m, g satisfying F + 2 ≤ 3 * m and m ≤ F - 1, the count of numerical semigroups satisfies the Fibonacci-like recurrence. Our goal is to derive False.

    line 4

      intro hcontra
  2. If a numerical semigroup S has multiplicity m > 0, then m ∈ S.

    The multiplicity is defined as the infimum of the set A of positive elements in S. If A were empty, its infimum would be 0 by `Nat.sInf_empty`, contradicting m > 0. Thus A is nonempty, and by `Nat.sInf_mem` its infimum belongs to A, which proves m ∈ S.

    lines 5–17

    uses Set.not_nonempty_iff_eq_empty, Nat.sInf_empty, Nat.sInf_mem

      have mult_mem : ∀ (S : NumericalSemigroup) (m : ℕ), numerical_semigroup_multiplicity S = m →
          0 < m → m ∈ (S.toAddSubmonoid : Set ℕ) := by
        intro S m h hm
        unfold numerical_semigroup_multiplicity at h
        set A : Set ℕ := {x : ℕ | x ∈ (S.toAddSubmonoid : Set ℕ) ∧ 0 < x} with hA
        have hne : A.Nonempty := by
          by_contra hc
          rw [Set.not_nonempty_iff_eq_empty] at hc
          rw [hc, Nat.sInf_empty] at h
          omega
        have hmem := Nat.sInf_mem hne
        rw [h] at hmem
        exact hmem.1
  3. If a numerical semigroup S has multiplicity m, then every positive element x ∈ S satisfies m ≤ x.

    Because m is the infimum of the set of positive elements in S, any positive x ∈ S is at least the infimum by `Nat.sInf_le`.

    lines 18–23

    uses Nat.sInf_le

      have mult_le : ∀ (S : NumericalSemigroup) (m : ℕ), numerical_semigroup_multiplicity S = m →
          ∀ x ∈ (S.toAddSubmonoid : Set ℕ), 0 < x → m ≤ x := by
        intro S m h x hx hx0
        unfold numerical_semigroup_multiplicity at h
        rw [← h]
        exact Nat.sInf_le ⟨hx, hx0⟩
  4. If a numerical semigroup S has Frobenius number F > 0, then F is in the complement of S (F is a gap).

    The Frobenius number is defined as the supremum of the gap set Sᶜ. If Sᶜ were empty, its supremum in ℕ would be 0 by `csSup_empty`, contradicting F > 0. Since Sᶜ is nonempty and finite (thus bounded above), its supremum belongs to Sᶜ by `Nat.sSup_mem`, showing F ∈ Sᶜ.

    lines 24–36

    uses Set.not_nonempty_iff_eq_empty, csSup_empty, Nat.sSup_mem

      have frob_mem_compl : ∀ (S : NumericalSemigroup) (F : ℕ),
          numerical_semigroup_frobenius_number S = F → 0 < F →
          F ∈ (S.toAddSubmonoid : Set ℕ)ᶜ := by
        intro S F h hF
        unfold numerical_semigroup_frobenius_number at h
        have hne : ((S.toAddSubmonoid : Set ℕ)ᶜ).Nonempty := by
          by_contra hc
          rw [Set.not_nonempty_iff_eq_empty] at hc
          rw [hc, csSup_empty] at h
          simp at h
          omega
        have hmem := Nat.sSup_mem hne S.finite_compl.bddAbove
        rwa [h] at hmem
  5. If a numerical semigroup S has Frobenius number F, then every gap x ∈ Sᶜ satisfies x ≤ F.

    Since Sᶜ is finite and thus bounded above, every element x ∈ Sᶜ is bounded above by the supremum of Sᶜ, which is F, by `le_csSup`.

    lines 37–43

    uses le_csSup

      have compl_le_frob : ∀ (S : NumericalSemigroup) (F : ℕ),
          numerical_semigroup_frobenius_number S = F →
          ∀ x ∈ (S.toAddSubmonoid : Set ℕ)ᶜ, x ≤ F := by
        intro S F h x hx
        unfold numerical_semigroup_frobenius_number at h
        calc x ≤ sSup ((S.toAddSubmonoid : Set ℕ)ᶜ) := le_csSup S.finite_compl.bddAbove hx
          _ = F := h
  6. The set S₀ = {0, 2} ∪ [4, ∞) forms a valid numerical semigroup `nsS` whose gap set is {1, 3}.

    We define S₀ = {0, 2} ∪ [4, ∞) and check that 0 ∈ S₀ and that S₀ is closed under addition. Its complement in ℕ is explicitly {1, 3}, which is finite by `Set.toFinite`, yielding a valid numerical semigroup `nsS`.

    lines 44–61

    uses Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici, Set.mem_compl_iff, Set.toFinite

      let nsC : Set ℕ := {0, 2} ∪ Set.Ici 4
      have nsC_add : ∀ a ∈ nsC, ∀ b ∈ nsC, a + b ∈ nsC := by
        intro a ha b hb
        simp only [nsC, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici] at *
        omega
      let nsSub : AddSubmonoid ℕ :=
        { carrier := nsC, zero_mem' := by simp [nsC],
          add_mem' := fun {a b : ℕ} (ha : a ∈ nsC) (hb : b ∈ nsC) => nsC_add a ha b hb }
      have nsSub_carrier : (nsSub : Set ℕ) = nsC := rfl
      have nsSub_compl : (nsC : Set ℕ)ᶜ = {1, 3} := by
        ext n
        simp only [nsC, Set.mem_compl_iff, Set.mem_union, Set.mem_insert_iff,
          Set.mem_singleton_iff, Set.mem_Ici]
        omega
      have hnsF : ((nsSub : Set ℕ)ᶜ).Finite := by
        rw [nsSub_carrier, nsSub_compl]
        exact Set.toFinite _
      let nsS : NumericalSemigroup := { toAddSubmonoid := nsSub, finite_compl := hnsF }
  7. The semigroup S₀ has Frobenius number 3, genus 2, and multiplicity 2.

    The gap set of S₀ is {1, 3}, so its maximum is 3 (Frobenius number 3) and its cardinality is 2 (genus 2). The set of positive elements of S₀ is {2} ∪ [4, ∞), whose minimum is 2, established via `le_antisymm`, `Nat.sInf_le`, and `le_csInf`.

    lines 62–81

    uses le_antisymm, Nat.sInf_le, le_csInf, Set.mem_setOf_eq, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici

      have nsS_carrier : (nsS.toAddSubmonoid : Set ℕ) = nsC := nsSub_carrier
      have nsS_frob : numerical_semigroup_frobenius_number nsS = 3 := by
        unfold numerical_semigroup_frobenius_number
        rw [nsS_carrier, nsSub_compl]
        norm_num
      have nsS_genus : numerical_semigroup_genus nsS = 2 := by
        unfold numerical_semigroup_genus
        rw [nsS_carrier, nsSub_compl]
        simp
      have nsS_mult : numerical_semigroup_multiplicity nsS = 2 := by
        unfold numerical_semigroup_multiplicity
        rw [nsS_carrier]
        have hmem : (2:ℕ) ∈ {x : ℕ | x ∈ nsC ∧ 0 < x} := by simp [nsC]
        apply le_antisymm
        · exact Nat.sInf_le hmem
        · apply le_csInf ⟨2, hmem⟩
          intro b hb
          simp only [Set.mem_setOf_eq, nsC, Set.mem_union, Set.mem_insert_iff,
            Set.mem_singleton_iff, Set.mem_Ici] at hb
          omega
  8. Any numerical semigroup S with Frobenius number 3, multiplicity 2, and genus 2 is equal to S₀.

    Let C = Sᶜ be the gap set of S. Frobenius number 3 implies 3 ∈ C and every gap n satisfies n ≤ 3. Since 0 ∈ S and multiplicity 2 implies 2 ∈ S, we have 0 ∉ C and 2 ∉ C, so C ⊆ {1, 3}. If 1 ∉ C, then C ⊆ {3}, giving |C| ≤ 1 by `Set.ncard_le_ncard` and `Set.ncard_singleton`, contradicting genus |C| = 2. Hence C = {1, 3} by `Set.Subset.antisymm`, which forces the carrier of S to be {0, 2} ∪ [4, ∞) = S₀. Semigroup extensionality (`AddSubmonoid.ext` and `NumericalSemigroup.mk.injEq`) then yields S = S₀.

    lines 82–154

    uses Set.mem_insert_iff, Set.mem_singleton_iff, Set.ncard_le_ncard, Set.toFinite, Set.ncard_singleton, Set.Subset.antisymm, not_or, Set.mem_union, Set.mem_Ici, AddSubmonoid.ext, NumericalSemigroup.mk.injEq

      have uniq : ∀ S : NumericalSemigroup, numerical_semigroup_frobenius_number S = 3 →
          numerical_semigroup_multiplicity S = 2 → numerical_semigroup_genus S = 2 → S = nsS := by
        intro S hfrob hmult hgen
        set C : Set ℕ := (S.toAddSubmonoid : Set ℕ)ᶜ with hC
        have h3C : 3 ∈ C := by
          rw [hC]
          exact frob_mem_compl S 3 hfrob (by norm_num)
        have hupper : ∀ n ∈ C, n ≤ 3 := by
          intro n hn
          rw [hC] at hn
          exact compl_le_frob S 3 hfrob n hn
        have h0S : (0:ℕ) ∈ (S.toAddSubmonoid : Set ℕ) := S.toAddSubmonoid.zero_mem
        have h2S : (2:ℕ) ∈ (S.toAddSubmonoid : Set ℕ) := mult_mem S 2 hmult (by norm_num)
        have hsub : C ⊆ {1, 3} := by
          intro n hn
          have hn3 : n ≤ 3 := hupper n hn
          rw [hC] at hn
          have hn0 : n ≠ 0 := fun h => hn (h ▸ h0S)
          have hn2 : n ≠ 2 := fun h => hn (h ▸ h2S)
          simp only [Set.mem_insert_iff, Set.mem_singleton_iff]
          omega
        have h1C : 1 ∈ C := by
          by_contra h1
          have hsub3 : C ⊆ ({3} : Set ℕ) := by
            intro n hn
            have h := hsub hn
            simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at h ⊢
            rcases h with h | h
            · rw [h] at hn; exact absurd hn h1
            · exact h
          have hle : C.ncard ≤ ({3} : Set ℕ).ncard := Set.ncard_le_ncard hsub3 (Set.toFinite _)
          rw [Set.ncard_singleton] at hle
          have hgen' : C.ncard = 2 := by
            rw [hC]
            exact hgen
          omega
        have hCeq : C = {1, 3} := by
          apply Set.Subset.antisymm hsub
          intro n hn
          simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hn
          rcases hn with rfl | rfl
          · exact h1C
          · exact h3C
        have hcarrier : (S.toAddSubmonoid : Set ℕ) = nsC := by
          ext n
          constructor
          · intro hn
            have hnotC : n ∉ C := by
              rw [hC]
              intro hmem
              exact hmem hn
            rw [hCeq] at hnotC
            simp only [Set.mem_insert_iff, Set.mem_singleton_iff, not_or] at hnotC
            simp only [nsC, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici]
            omega
          · intro hn
            by_contra hns
            have hmem : n ∈ C := by rw [hC]; exact hns
            rw [hCeq] at hmem
            simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hmem
            simp only [nsC, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff,
              Set.mem_Ici] at hn
            omega
        have hsubeq : S.toAddSubmonoid = nsSub := by
          apply AddSubmonoid.ext
          intro n
          change n ∈ (S.toAddSubmonoid : Set ℕ) ↔ n ∈ (nsC : Set ℕ)
          rw [hcarrier]
        have hnsS : nsS = ⟨nsSub, hnsF⟩ := rfl
        rw [hnsS]
        obtain ⟨a, b⟩ := S
        simp only [NumericalSemigroup.mk.injEq]
        exact hsubeq
  9. The count of numerical semigroups with parameters (F, m, g) = (3, 2, 2) is 1.

    The uniqueness result implies that the set of numerical semigroups with parameters (3, 2, 2) is exactly the singleton {S₀}. By `Set.ncard_singleton`, its cardinality is 1, so `numerical_semigroup_count 3 2 2 = 1`.

    lines 155–167

    uses Set.mem_setOf_eq, Set.mem_singleton_iff, Set.ncard_singleton

      have hX : {S : NumericalSemigroup | numerical_semigroup_frobenius_number S = 3 ∧
          numerical_semigroup_multiplicity S = 2 ∧ numerical_semigroup_genus S = 2} = {nsS} := by
        ext S
        simp only [Set.mem_setOf_eq, Set.mem_singleton_iff]
        constructor
        · rintro ⟨a, b, c⟩
          exact uniq S a b c
        · rintro rfl
          exact ⟨nsS_frob, nsS_mult, nsS_genus⟩
      have hcount3 : numerical_semigroup_count 3 2 2 = 1 := by
        unfold numerical_semigroup_count
        rw [hX, Set.ncard_singleton]
      have count_one_zero : ∀ g : ℕ, numerical_semigroup_count 1 1 g = 0 := by
  10. For any genus g, the count of numerical semigroups with Frobenius number 1 and multiplicity 1 is 0.

    Multiplicity 1 requires 1 ∈ S (by `mult_mem`), while Frobenius number 1 requires 1 ∈ Sᶜ (by `frob_mem_compl`). Since 1 cannot simultaneously be in S and in Sᶜ, no such semigroup exists. The set is empty, so its cardinality is 0.

    lines 168–179

    uses Set.not_nonempty_iff_eq_empty

        intro g
        unfold numerical_semigroup_count
        have hempty : {S : NumericalSemigroup | numerical_semigroup_frobenius_number S = 1 ∧
            numerical_semigroup_multiplicity S = 1 ∧ numerical_semigroup_genus S = g} = ∅ := by
          rw [← Set.not_nonempty_iff_eq_empty]
          rintro ⟨S, hfrob, hmult, -⟩
          have h1mem : (1:ℕ) ∈ (S.toAddSubmonoid : Set ℕ) := mult_mem S 1 hmult (by norm_num)
          have h1compl : (1:ℕ) ∈ (S.toAddSubmonoid : Set ℕ)ᶜ :=
            frob_mem_compl S 1 hfrob (by norm_num)
          exact h1compl h1mem
        rw [hempty]
        simp
  11. The recurrence produces the contradiction 1 = 0.

    Specializing the universal recurrence assumption `hcontra` to F = 3, m = 2, g = 2 satisfies the required bounds 3 + 2 ≤ 3 * 2 and 2 ≤ 3 - 1. It equates `numerical_semigroup_count 3 2 2` to `numerical_semigroup_count 1 1 1 + numerical_semigroup_count 1 1 0`. Substituting the known values yields 1 = 0 + 0, which linear arithmetic (`omega`) recognizes as a contradiction.

    lines 180–184

      have h1 := hcontra 3 2 2 (by norm_num) (by norm_num)
      rw [hcount3] at h1
      have h1' : (1:ℕ) = numerical_semigroup_count 1 1 1 + numerical_semigroup_count 1 1 0 := h1
      rw [count_one_zero 1, count_one_zero 0] at h1'
      omega
AddSubmonoid.ext
Two additive submonoids of an additive monoid are equal if and only if they contain the exact same elements.
Nat.sInf_empty
The infimum of the empty set of natural numbers is defined to be 0.
Nat.sInf_le
The infimum of a set of natural numbers is less than or equal to any element in the set.
Nat.sInf_mem
The infimum of a nonempty set of natural numbers belongs to that set (i.e., every nonempty subset of ℕ has a minimum).
Nat.sSup_mem
The supremum of a nonempty, bounded-above set of natural numbers belongs to that set (i.e., it achieves its maximum).
NumericalSemigroup.mk.injEq
Two numerical semigroups constructed with `NumericalSemigroup.mk` are equal if and only if their underlying additive submonoids are equal.
Set.mem_Ici
An element belongs to the closed interval [b, ∞) if and only if b ≤ x.
Set.mem_compl_iff
An element belongs to the complement of a set if and only if it does not belong to the set.
Set.mem_insert_iff
An element belongs to the insertion of an element a into a set s if and only if it equals a or belongs to s.
Set.mem_setOf_eq
Membership of x in the set of elements satisfying a predicate p is equivalent to p(x).
Set.mem_singleton_iff
An element belongs to the singleton set {b} if and only if it equals b.
Set.mem_union
An element belongs to the union of two sets if and only if it belongs to at least one of them.
Set.ncard_le_ncard
If s is a subset of a finite set t, then the cardinality of s is at most the cardinality of t.
Set.ncard_singleton
The cardinality of a singleton set is 1.
Set.not_nonempty_iff_eq_empty
A set is not nonempty if and only if it is the empty set.
Set.Subset.antisymm
If two sets are subsets of each other, they are equal.
Set.toFinite
A set whose subtype is finite is a finite set.
csSup_empty
In a conditionally complete linear order with a bottom element (such as ℕ), the supremum of the empty set is ⊥ (which is 0).
le_antisymm
In a partial order, if a ≤ b and b ≤ a, then a = b.
le_csInf
If an element a is a lower bound for a nonempty set s in a conditionally complete lattice, then a ≤ inf s.
le_csSup
Any element of a bounded-above set in a conditionally complete lattice is less than or equal to the supremum of that set.
not_or
The negation of a disjunction is equivalent to the conjunction of the negations (De Morgan's law).

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

theorem not_numerical_semigroup_count_fibonacci_recurrence : ¬ (∀ (F m g : ℕ) (hlow : F + 2 ≤ 3 * m) (hhigh : m ≤ F - 1), numerical_semigroup_count F m g =      numerical_semigroup_count (F - 2) (m - 1) (g - 1) +      numerical_semigroup_count (F - 2) (m - 1) (g - 2)) := by  intro hcontra  have mult_mem : ∀ (S : NumericalSemigroup) (m : ℕ), numerical_semigroup_multiplicity S = m →      0 < m → m ∈ (S.toAddSubmonoid : Set ℕ) := by    intro S m h hm    unfold numerical_semigroup_multiplicity at h    set A : Set ℕ := {x : ℕ | x ∈ (S.toAddSubmonoid : Set ℕ) ∧ 0 < x} with hA    have hne : A.Nonempty := by      by_contra hc      rw [Set.not_nonempty_iff_eq_empty] at hc      rw [hc, Nat.sInf_empty] at h      omega    have hmem := Nat.sInf_mem hne    rw [h] at hmem    exact hmem.1  have mult_le : ∀ (S : NumericalSemigroup) (m : ℕ), numerical_semigroup_multiplicity S = m →      ∀ x ∈ (S.toAddSubmonoid : Set ℕ), 0 < x → m ≤ x := by    intro S m h x hx hx0    unfold numerical_semigroup_multiplicity at h    rw [← h]    exact Nat.sInf_le ⟨hx, hx0⟩  have frob_mem_compl : ∀ (S : NumericalSemigroup) (F : ℕ),      numerical_semigroup_frobenius_number S = F → 0 < F →      F ∈ (S.toAddSubmonoid : Set ℕ)ᶜ := by    intro S F h hF    unfold numerical_semigroup_frobenius_number at h    have hne : ((S.toAddSubmonoid : Set ℕ)ᶜ).Nonempty := by      by_contra hc      rw [Set.not_nonempty_iff_eq_empty] at hc      rw [hc, csSup_empty] at h      simp at h      omega    have hmem := Nat.sSup_mem hne S.finite_compl.bddAbove    rwa [h] at hmem  have compl_le_frob : ∀ (S : NumericalSemigroup) (F : ℕ),      numerical_semigroup_frobenius_number S = F →      ∀ x ∈ (S.toAddSubmonoid : Set ℕ)ᶜ, x ≤ F := by    intro S F h x hx    unfold numerical_semigroup_frobenius_number at h    calc x ≤ sSup ((S.toAddSubmonoid : Set ℕ)ᶜ) := le_csSup S.finite_compl.bddAbove hx      _ = F := h  let nsC : Set ℕ := {0, 2} ∪ Set.Ici 4  have nsC_add : ∀ a ∈ nsC, ∀ b ∈ nsC, a + b ∈ nsC := by    intro a ha b hb    simp only [nsC, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici] at *    omega  let nsSub : AddSubmonoid ℕ :=    { carrier := nsC, zero_mem' := by simp [nsC],      add_mem' := fun {a b : ℕ} (ha : a ∈ nsC) (hb : b ∈ nsC) => nsC_add a ha b hb }  have nsSub_carrier : (nsSub : Set ℕ) = nsC := rfl  have nsSub_compl : (nsC : Set ℕ)ᶜ = {1, 3} := by    ext n    simp only [nsC, Set.mem_compl_iff, Set.mem_union, Set.mem_insert_iff,      Set.mem_singleton_iff, Set.mem_Ici]    omega  have hnsF : ((nsSub : Set ℕ)ᶜ).Finite := by    rw [nsSub_carrier, nsSub_compl]    exact Set.toFinite _  let nsS : NumericalSemigroup := { toAddSubmonoid := nsSub, finite_compl := hnsF }  have nsS_carrier : (nsS.toAddSubmonoid : Set ℕ) = nsC := nsSub_carrier  have nsS_frob : numerical_semigroup_frobenius_number nsS = 3 := by    unfold numerical_semigroup_frobenius_number    rw [nsS_carrier, nsSub_compl]    norm_num  have nsS_genus : numerical_semigroup_genus nsS = 2 := by    unfold numerical_semigroup_genus    rw [nsS_carrier, nsSub_compl]    simp  have nsS_mult : numerical_semigroup_multiplicity nsS = 2 := by    unfold numerical_semigroup_multiplicity    rw [nsS_carrier]    have hmem : (2:ℕ) ∈ {x : ℕ | x ∈ nsC ∧ 0 < x} := by simp [nsC]    apply le_antisymm    · exact Nat.sInf_le hmem    · apply le_csInf ⟨2, hmem⟩      intro b hb      simp only [Set.mem_setOf_eq, nsC, Set.mem_union, Set.mem_insert_iff,        Set.mem_singleton_iff, Set.mem_Ici] at hb      omega  have uniq : ∀ S : NumericalSemigroup, numerical_semigroup_frobenius_number S = 3 →      numerical_semigroup_multiplicity S = 2 → numerical_semigroup_genus S = 2 → S = nsS := by    intro S hfrob hmult hgen    set C : Set ℕ := (S.toAddSubmonoid : Set ℕ)ᶜ with hC    have h3C : 3 ∈ C := by      rw [hC]      exact frob_mem_compl S 3 hfrob (by norm_num)    have hupper : ∀ n ∈ C, n ≤ 3 := by      intro n hn      rw [hC] at hn      exact compl_le_frob S 3 hfrob n hn    have h0S : (0:ℕ) ∈ (S.toAddSubmonoid : Set ℕ) := S.toAddSubmonoid.zero_mem    have h2S : (2:ℕ) ∈ (S.toAddSubmonoid : Set ℕ) := mult_mem S 2 hmult (by norm_num)    have hsub : C ⊆ {1, 3} := by      intro n hn      have hn3 : n ≤ 3 := hupper n hn      rw [hC] at hn      have hn0 : n ≠ 0 := fun h => hn (h ▸ h0S)      have hn2 : n ≠ 2 := fun h => hn (h ▸ h2S)      simp only [Set.mem_insert_iff, Set.mem_singleton_iff]      omega    have h1C : 1 ∈ C := by      by_contra h1      have hsub3 : C ⊆ ({3} : Set ℕ) := by        intro n hn        have h := hsub hn        simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at h ⊢        rcases h with h | h        · rw [h] at hn; exact absurd hn h1        · exact h      have hle : C.ncard ≤ ({3} : Set ℕ).ncard := Set.ncard_le_ncard hsub3 (Set.toFinite _)      rw [Set.ncard_singleton] at hle      have hgen' : C.ncard = 2 := by        rw [hC]        exact hgen      omega    have hCeq : C = {1, 3} := by      apply Set.Subset.antisymm hsub      intro n hn      simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hn      rcases hn with rfl | rfl      · exact h1C      · exact h3C    have hcarrier : (S.toAddSubmonoid : Set ℕ) = nsC := by      ext n      constructor      · intro hn        have hnotC : n ∉ C := by          rw [hC]          intro hmem          exact hmem hn        rw [hCeq] at hnotC        simp only [Set.mem_insert_iff, Set.mem_singleton_iff, not_or] at hnotC        simp only [nsC, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici]        omega      · intro hn        by_contra hns        have hmem : n ∈ C := by rw [hC]; exact hns        rw [hCeq] at hmem        simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hmem        simp only [nsC, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff,          Set.mem_Ici] at hn        omega    have hsubeq : S.toAddSubmonoid = nsSub := by      apply AddSubmonoid.ext      intro n      change n ∈ (S.toAddSubmonoid : Set ℕ) ↔ n ∈ (nsC : Set ℕ)      rw [hcarrier]    have hnsS : nsS = ⟨nsSub, hnsF⟩ := rfl    rw [hnsS]    obtain ⟨a, b⟩ := S    simp only [NumericalSemigroup.mk.injEq]    exact hsubeq  have hX : {S : NumericalSemigroup | numerical_semigroup_frobenius_number S = 3 ∧      numerical_semigroup_multiplicity S = 2 ∧ numerical_semigroup_genus S = 2} = {nsS} := by    ext S    simp only [Set.mem_setOf_eq, Set.mem_singleton_iff]    constructor    · rintro ⟨a, b, c⟩      exact uniq S a b c    · rintro rfl      exact ⟨nsS_frob, nsS_mult, nsS_genus⟩  have hcount3 : numerical_semigroup_count 3 2 2 = 1 := by    unfold numerical_semigroup_count    rw [hX, Set.ncard_singleton]  have count_one_zero : ∀ g : ℕ, numerical_semigroup_count 1 1 g = 0 := by    intro g    unfold numerical_semigroup_count    have hempty : {S : NumericalSemigroup | numerical_semigroup_frobenius_number S = 1 ∧        numerical_semigroup_multiplicity S = 1 ∧ numerical_semigroup_genus S = g} = ∅ := by      rw [← Set.not_nonempty_iff_eq_empty]      rintro ⟨S, hfrob, hmult, -⟩      have h1mem : (1:ℕ) ∈ (S.toAddSubmonoid : Set ℕ) := mult_mem S 1 hmult (by norm_num)      have h1compl : (1:ℕ) ∈ (S.toAddSubmonoid : Set ℕ)ᶜ :=        frob_mem_compl S 1 hfrob (by norm_num)      exact h1compl h1mem    rw [hempty]    simp  have h1 := hcontra 3 2 2 (by norm_num) (by norm_num)  rw [hcount3] at h1  have h1' : (1:ℕ) = numerical_semigroup_count 1 1 1 + numerical_semigroup_count 1 1 0 := h1  rw [count_one_zero 1, count_one_zero 0] at h1'  omega
See it in the graphDiscuss this resultChallenge it