AFTD Auto-Formalizing Theoretical Domains

dedekind_number_zero

lemmaverifiedformalization

The 0-th Dedekind number is 2.

Statement

lemma dedekind_number_zero : dedekind_number 0 = 2
Formalizes
arXiv:2611.13887 Section 2
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • dedekind_numberThe n-th Dedekind number d_n is the number of monotone Boolean functions on n variables, defined as the cardinality of the poset of…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • inst_fintype_orderHomThe type of order-preserving maps between two finite partial orders is finite.

Read back from the Lean

dedekind_number 0 is equal to 2.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

def dedekind_number_zero_orderHom_equiv (α β : Type*) [Unique α] [Preorder α] [Preorder β] :
    (α →o β) ≃ β where
  toFun f := f default
  invFun b := ⟨fun _ => b, fun _ _ _ => le_rfl⟩
  left_inv f := by
    ext x
    have : x = default := Subsingleton.elim x default
    subst this
    rfl
  right_inv b := rfl

/-- The 0-th Dedekind number is 2. -/
lemma dedekind_number_zero : dedekind_number 0 = 2 := by
  change Fintype.card ((Fin 0 → Bool) →o Bool) = 2
  rw [Fintype.card_congr (dedekind_number_zero_orderHom_equiv (Fin 0 → Bool) Bool)]
  exact Fintype.card_bool
See it in the graphDiscuss this resultChallenge it