FormalConjectures/Wikipedia/DedekindNumber.lean

GitHub source file

Explanation legend Lean4 Domain Explanation Language (L4DEL)

L4DEL explanations are a separate layer. They do not change the Lean source. Intuition is explanatory prose; numbered items are a reading path; sources link the wording back to evidence.

L4DEL
Lean4 Domain Explanation Language

Credit: The upstream authors and contributors retain credit for the project and mathematics. lean4-explainer only renders their pinned source and adds the separately disclosed explanation layer.

Project sources: Pinned project documentation, Formal Conjectures paper, arXiv v1

36 declarations, 3 contain sorry, 0 declared as axioms

Dedekind Numbers

A Dedekind number M(n) counts the number of monotone Boolean functions on n variables, or equivalently, the number of antichains (Sperner families) in the Boolean lattice 2^[n].

For example, $$M ( 0 ) = 2 , M ( 1 ) = 3 , M ( 2 ) = 6 , and M ( 3 ) = 20 .$$ The first few values grew slowly: $$M ( 4 ) = 168 , M ( 5 ) = 7581$$, but then rapidly: $$M ( 6 ) = 7828354 , M ( 7 ) = 2414682040998 , M ( 8 ) = 56130437228687557907788$$, and $$M ( 9 ) = 286386577668298411128469151667598498812366$$ (computed in 2023).

We formalize two definitions:

We prove their values for small n and show that the two definitions agree for all n.

The problem is to determine the exact values of $M(n)$ for $n ≥ 10$. In particular, the value of $M(10)$ is currently unknown.

References:

Imports (1)
Imported by 1 file
  1. instance DedekindNumber.piFinBoolDecidableLE line 56 source

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, DecidableRel, Fin, Bool, LE.le

    Proof uses: Decidable, Eq.mpr

    8 instances, coercions and auxiliary constants left out.

    Tactic trace: 2 steps

    Open to load the checked before-and-after goal states.

  2. def DedekindNumber.M $M(n)$ is the number of monotone Boolean functions on $n$ variables line 63 source

    Source documentation

    $M(n)$ is the number of monotone Boolean functions on $n$ variables.

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat

    Proof uses: Fintype.card, Subtype, Fin, Bool, Monotone, LE.le

    16 instances, coercions and auxiliary constants left out.

    def M (n : ℕ) : ℕ :=
    …
  3. def DedekindNumber.IsSperner A Sperner family (antichain) of subsets of Fin n: a family of sets such that no member is a subset of another line 68 source

    Source documentation

    A Sperner family (antichain) of subsets of Fin n: a family of sets such that no member is a subset of another.

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Finset, Fin

    Proof uses: IsAntichain, LE.le

    5 instances, coercions and auxiliary constants left out.

    def IsSperner {n : ℕ} (A : Finset (Finset (Fin n))) : Prop :=
    …
  4. instance DedekindNumber.isSpernerDecidable line 71 source

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, DecidablePred, Finset, Fin, DedekindNumber.IsSperner

    Proof uses: id, Decidable, IsAntichain, LE.le, Set.Pairwise, Compl.compl, Eq.mpr, Membership.mem, Set, Ne, Not, inferInstance, Eq

    19 instances, coercions and auxiliary constants left out.

    Tactic trace: 3 steps

    Open to load the checked before-and-after goal states.

  5. def DedekindNumber.M' $M'(n)$ is the number of antichains (Sperner families) of subsets of Fin n line 79 source

    Source documentation

    $M'(n)$ is the number of antichains (Sperner families) of subsets of Fin n.

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat

    Proof uses: Fintype.card, Subtype, Finset, Fin, DedekindNumber.IsSperner

    4 instances, coercions and auxiliary constants left out.

    def M' (n : ℕ) : ℕ :=
    …
  6. theorem DedekindNumber.M_zero Values for small n line 84 source

    Source documentation

    Values for small n

    extra axioms: _private.0.DedekindNumber.M_zero._native.native_decide.ax_1 what this means

    Statement uses: Eq, Nat, DedekindNumber.M, OfNat.ofNat

    Proof uses: of_decide_eq_true

    4 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

    theorem M_zero : M 0 = 2 := by native_decide
    …

    Mentions: DedekindNumber.M

  7. theorem DedekindNumber.M_one line 87 source

    extra axioms: _private.0.DedekindNumber.M_one._native.native_decide.ax_1 what this means

    Statement uses: Eq, Nat, DedekindNumber.M, OfNat.ofNat

    Proof uses: of_decide_eq_true

    4 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

  8. theorem DedekindNumber.M_two line 90 source

    extra axioms: _private.0.DedekindNumber.M_two._native.native_decide.ax_1 what this means

    Statement uses: Eq, Nat, DedekindNumber.M, OfNat.ofNat

    Proof uses: of_decide_eq_true

    4 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

  9. theorem DedekindNumber.M_three line 93 source

    extra axioms: _private.0.DedekindNumber.M_three._native.native_decide.ax_1 what this means

    Statement uses: Eq, Nat, DedekindNumber.M, OfNat.ofNat

    Proof uses: of_decide_eq_true

    4 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

  10. theorem DedekindNumber.M'_zero line 96 source

    extra axioms: _private.0.DedekindNumber.M'_zero._native.native_decide.ax_1 what this means

    Statement uses: Eq, Nat, DedekindNumber.M', OfNat.ofNat

    Proof uses: of_decide_eq_true

    4 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

  11. theorem DedekindNumber.M'_one line 99 source

    extra axioms: _private.0.DedekindNumber.M'_one._native.native_decide.ax_1 what this means

    Statement uses: Eq, Nat, DedekindNumber.M', OfNat.ofNat

    Proof uses: of_decide_eq_true

    4 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

  12. theorem DedekindNumber.M'_two line 102 source

    extra axioms: _private.0.DedekindNumber.M'_two._native.native_decide.ax_1 what this means

    Statement uses: Eq, Nat, DedekindNumber.M', OfNat.ofNat

    Proof uses: of_decide_eq_true

    4 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

  13. theorem DedekindNumber.M'_three line 105 source

    extra axioms: _private.0.DedekindNumber.M'_three._native.native_decide.ax_1 what this means

    Statement uses: Eq, Nat, DedekindNumber.M', OfNat.ofNat

    Proof uses: of_decide_eq_true

    4 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

  14. def DedekindNumber.χ The indicator function of a finset: χ s i = true ↔ i ∈ s line 111 source

    Source documentation

    The indicator function of a finset: χ s i = true ↔ i ∈ s.

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Finset, Fin, Bool

    Proof uses: Decidable.decide, Membership.mem

    4 instances, coercions and auxiliary constants left out.

    def χ {n : ℕ} (s : Finset (Fin n)) : Fin n → Bool :=
    …
  15. def DedekindNumber.supp The support of a Boolean-valued function: supp v = {i | v i = true} line 115 source

    Source documentation

    The support of a Boolean-valued function: supp v = {i | v i = true}.

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Fin, Bool, Finset

    Proof uses: Finset.filter, Eq, Bool.true, Finset.univ

    2 instances, coercions and auxiliary constants left out.

    def supp {n : ℕ} (v : Fin n → Bool) : Finset (Fin n) :=
    …
  16. def DedekindNumber.toSperner Forward map: monotone function → Sperner family (the minimal true sets) line 119 source

    Source documentation

    Forward map: monotone function → Sperner family (the minimal true sets).

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Fin, Bool, Finset

    Proof uses: Finset.filter, And, Eq, DedekindNumber.χ, Bool.true, LE.le, Finset.univ

    11 instances, coercions and auxiliary constants left out.

    def toSperner {n : ℕ} (f : (Fin n → Bool) → Bool) : Finset (Finset (Fin n)) :=
    …
  17. def DedekindNumber.fromSperner Backward map: Sperner family → monotone Boolean function line 124 source

    Source documentation

    Backward map: Sperner family → monotone Boolean function.

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Finset, Fin, Bool

    Proof uses: Decidable.decide, Exists, And, Membership.mem, Eq, Bool.true

    8 instances, coercions and auxiliary constants left out.

    def fromSperner {n : ℕ} (A : Finset (Finset (Fin n))) (v : Fin n → Bool) : Bool :=
    …
  18. lemma DedekindNumber.χ_supp line 130 source

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Fin, Bool, Eq, DedekindNumber.χ, DedekindNumber.supp

    Proof uses: funext, of_eq_true, Eq.trans, True, congrFun', congrArg, Decidable.decide, Membership.mem, Finset, Bool.true, Decidable.decide.congr_simp, Finset.filter, Finset.univ, And, true_and, Bool.decide_eq_true, eq_self

    8 instances, coercions and auxiliary constants left out.

    Tactic trace: 2 steps

    Open to load the checked before-and-after goal states.

  19. lemma DedekindNumber.supp_χ line 134 source

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Finset, Fin, Eq, DedekindNumber.supp, DedekindNumber.χ

    Proof uses: Finset.ext, of_eq_true, Iff, Membership.mem, Eq.trans, True, congrFun', congrArg, Finset.filter, Bool, Bool.true, Finset.univ, Finset.filter.congr_simp, funext, Decidable.decide, decide_eq_true_eq, Eq.refl, Finset.filter_mem_eq_of_subset, LE.le, iff_self

    10 instances, coercions and auxiliary constants left out.

    Tactic trace: 2 steps

    Open to load the checked before-and-after goal states.

  20. lemma DedekindNumber.χ_le_iff line 139 source

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Finset, Fin, Iff, LE.le, Bool, DedekindNumber.χ

    Proof uses: of_eq_true, Eq.trans, Membership.mem, True, congr, congrArg, forall_congr, Decidable.decide, Eq, Bool.true, implies_congr, decide_eq_true_eq, iff_self

    17 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

  21. lemma DedekindNumber.mem_supp_iff line 143 source

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Fin, Bool, Iff, Membership.mem, Finset, DedekindNumber.supp, Eq, Bool.true

    Proof uses: of_eq_true, Eq.trans, True, congrFun', congrArg, Finset.filter, Finset.univ, And, true_and, iff_self

    8 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

  22. lemma DedekindNumber.toSperner_isSperner line 147 source

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Fin, Bool, Monotone, DedekindNumber.IsSperner, DedekindNumber.toSperner

    Proof uses: Finset, Membership.mem, Set, Ne, Eq.mpr, Compl.compl, LE.le, Not, id, Eq, Mathlib.Tactic.Contrapose.contrapose₃, Exists, Iff, implies_congr, Eq.refl, Eq.trans, binderNameHint, forall_congr, DedekindNumber.χ, Bool.true and 11 more

    31 instances, coercions and auxiliary constants left out.

    Tactic trace: 5 steps

    Open to load the checked before-and-after goal states.

  23. lemma DedekindNumber.fromSperner_monotone line 153 source

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Finset, Fin, DedekindNumber.IsSperner, Monotone, Bool, DedekindNumber.fromSperner

    Proof uses: LE.le, Eq, Bool.true, And, Membership.mem, DedekindNumber.supp, Exists, of_eq_true, Eq.trans, True, congrArg, funext, forall_congr, implies_congr_ctx, Eq.refl, eq_true, id, Eq.mp, Decidable.decide, decide_eq_true_eq and 11 more

    21 instances, coercions and auxiliary constants left out.

    Tactic trace: 11 steps

    Open to load the checked before-and-after goal states.

  24. lemma DedekindNumber.exists_minimal_true_subset Every true set of a monotone Boolean function contains a minimal true set line 168 source

    Source documentation

    Every true set of a monotone Boolean function contains a minimal true set.

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Fin, Bool, Monotone, Finset, Eq, DedekindNumber.χ, Bool.true, Exists, And, LE.le

    Proof uses: Membership.mem, Set, Set.ofPred, Finset.card, Set.exists_min_image, Iff.mpr, Set.Finite, BddAbove, Set.finite_iff_bddAbove, Exists.intro, upperBounds, And.left, And.intro, Finset.Subset.refl, And.right, Iff.mp, Not, Classical.not_not, not_lt_of_ge, LE.le.trans and 14 more

    27 instances, coercions and auxiliary constants left out.

    Tactic trace: 9 steps

    Open to load the checked before-and-after goal states.

    lemma exists_minimal_true_subset {n : ℕ} {f : (Fin n → Bool) → Bool} (_ : Monotone f)
        {s : Finset (Fin n)} (hs : f (χ s) = true) :
        ∃ t, t ⊆ s ∧ f (χ t) = true ∧ ∀ u, u ⊆ t → f (χ u) = true → t ⊆ u := by
    …

    Mentions: DedekindNumber.χ

  25. lemma DedekindNumber.fromSperner_toSperner Converting a monotone function to a Sperner family and back yields the same function line 184 source

    Source documentation

    Converting a monotone function to a Sperner family and back yields the same function.

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Fin, Bool, Monotone, Eq, DedekindNumber.fromSperner, DedekindNumber.toSperner

    Proof uses: funext, dite, Bool.true, Eq.mpr, Exists, Finset, And, Membership.mem, id, Eq.trans, Decidable.decide, congrArg, decide_eq_true_eq, LE.le, Finset.filter, Finset.univ, DedekindNumber.χ, DedekindNumber.exists_minimal_true_subset, eq_of_heq, HEq and 36 more

    38 instances, coercions and auxiliary constants left out.

    Tactic trace: 19 steps

    Open to load the checked before-and-after goal states.

    lemma fromSperner_toSperner {n : ℕ} (f : (Fin n → Bool) → Bool) (hf : Monotone f) :
        fromSperner (toSperner f) = f := by
    …

    Mentions: DedekindNumber.fromSperner, DedekindNumber.toSperner

  26. lemma DedekindNumber.toSperner_fromSperner Converting a Sperner family to a monotone function and back yields the same family line 203 source

    Source documentation

    Converting a Sperner family to a monotone function and back yields the same family.

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Finset, Fin, DedekindNumber.IsSperner, Eq, DedekindNumber.toSperner, DedekindNumber.fromSperner

    Proof uses: Finset.ext, Eq.mpr, Iff, Membership.mem, And, Exists, Bool, DedekindNumber.χ, Bool.true, LE.le, id, congrFun', congrArg, Eq.trans, Finset.univ, Finset.filter, Finset.filter_congr, Iff.of_eq, congr, decide_eq_true_eq and 32 more

    36 instances, coercions and auxiliary constants left out.

    Tactic trace: 27 steps

    Open to load the checked before-and-after goal states.

    lemma toSperner_fromSperner {n : ℕ} (A : Finset (Finset (Fin n))) (hA : IsSperner A) :
        toSperner (fromSperner A) = A := by
    …

    Mentions: DedekindNumber.IsSperner, DedekindNumber.toSperner, DedekindNumber.fromSperner

  27. def DedekindNumber.equivMonotoneSperner The set of monotone Boolean functions on n variables is in bijection with the set of Sperner families of subsets of Fin n line 219 source

    Source documentation

    The set of monotone Boolean functions on n variables is in bijection with the set of Sperner families of subsets of Fin n.

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Equiv, Subtype, Fin, Bool, Monotone, Finset, DedekindNumber.IsSperner

    Proof uses: Equiv.mk, DedekindNumber.equivMonotoneSperner.match_1, Subtype.mk, DedekindNumber.toSperner, DedekindNumber.toSperner_isSperner, DedekindNumber.equivMonotoneSperner.match_2, DedekindNumber.fromSperner, DedekindNumber.fromSperner_monotone

    8 instances, coercions and auxiliary constants left out.

    def equivMonotoneSperner (n : ℕ) :
        {f : (Fin n → Bool) → Bool // Monotone f} ≃
        {A : Finset (Finset (Fin n)) // IsSperner A} where
    …

    Mentions: DedekindNumber.IsSperner

  28. theorem DedekindNumber.M_eq_M' line 228 source

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Eq, Nat, DedekindNumber.M, DedekindNumber.M'

    Proof uses: funext, Fintype.card_congr, Subtype, Fin, Bool, Monotone, Finset, DedekindNumber.IsSperner, LE.le, DedekindNumber.equivMonotoneSperner

    18 instances, coercions and auxiliary constants left out.

    Tactic trace: 2 steps

    Open to load the checked before-and-after goal states.

  29. def DedekindNumber.kisielewiczFormula A closed formula for the Dedekind numbers as found by Kisielewicz (1998) line 238 source

    Source documentation

    A closed formula for the Dedekind numbers as found by Kisielewicz (1998): $$ M(n) = \sum_{k=0}^{2^{2^n}}\prod_{j = 1}^{2 ^ n - 1}\prod_{i = 0}^{j - 1} \left( 1 - b_i^kb_j^k \prod_{m = 0}^{\log_2 i} (1 - b_m^i + b_m^ib_m^j)\right), $$, where $b_i^k$ is the $i$-th bit of $k$.

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat

    Proof uses: Finset.sum, Finset.range, HPow.hPow, OfNat.ofNat, Finset.prod, Finset.Icc, HSub.hSub, HMul.hMul, Bool.toNat, Nat.testBit, HAdd.hAdd, Nat.log2

    15 instances, coercions and auxiliary constants left out.

    def kisielewiczFormula (n : ℕ) : ℕ :=
    …
  30. theorem DedekindNumber.kisielewiczFormula_zero line 243 source

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Eq, Nat, DedekindNumber.kisielewiczFormula, OfNat.ofNat

    Proof uses: of_decide_eq_true, id, Bool, Decidable.decide, Bool.true, Eq.refl

    3 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

  31. theorem DedekindNumber.kisielewiczFormula_one line 244 source

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Eq, Nat, DedekindNumber.kisielewiczFormula, OfNat.ofNat

    Proof uses: of_decide_eq_true, id, Bool, Decidable.decide, Bool.true, Eq.refl

    3 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

  32. theorem DedekindNumber.kisielewiczFormula_two line 245 source

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Eq, Nat, DedekindNumber.kisielewiczFormula, OfNat.ofNat

    Proof uses: of_decide_eq_true, id, Bool, Decidable.decide, Bool.true, Eq.refl

    3 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

  33. theorem DedekindNumber.kisielewiczFormula_three line 246 source

    extra axioms: _private.0.DedekindNumber.kisielewiczFormula_three._native.native_decide.ax_1 what this means

    Statement uses: Eq, Nat, DedekindNumber.kisielewiczFormula, OfNat.ofNat

    Proof uses: of_decide_eq_true

    4 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

  34. theorem DedekindNumber.M_eq_kisielewiczFormula Kisielewicz (1988) proved the following arithmetic formula for the Dedekind numbers sorry line 259 source

    Source documentation

    Kisielewicz (1988) proved the following arithmetic formula for the Dedekind numbers: $$ M(n) = \sum_{k=0}^{2^{2^n}}\prod_{j = 1}^{2 ^ n - 1}\prod_{i = 0}^{j - 1} \left( 1 - b_i^kb_j^k \prod_{m = 0}^{\log_2 i} (1 - b_m^i + b_m^ib_m^j)\right), $$ where $b_i^k$ is the $i$-th bit of $k$. However, this formula is not computationally efficient for large $n$.

    depends on sorry what this means

    Statement uses: Eq, Nat, DedekindNumber.M, DedekindNumber.kisielewiczFormula

    Proof uses: sorryAx, Lean.Name, Bool.false, Lean.Name.num, Lean.Name.str, Lean.Name.anonymous, OfNat.ofNat

    1 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

    theorem M_eq_kisielewiczFormula : M = kisielewiczFormula := by
    …

    Mentions: DedekindNumber.M, DedekindNumber.kisielewiczFormula

  35. theorem DedekindNumber.M_eq No closed-form expression that allows efficient computation of Dedekind numbers is currently known sorry line 267 source

    Source documentation

    No closed-form expression that allows efficient computation of Dedekind numbers is currently known.

    depends on sorry what this means

    Statement uses: Eq, Nat, DedekindNumber.M, sorryAx, Lean.Name, Bool.false, Lean.Name.num, Lean.Name.str, Lean.Name.anonymous, OfNat.ofNat

    2 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

    theorem M_eq : M = answer(sorry) := by
    …

    Mentions: DedekindNumber.M

  36. theorem DedekindNumber.Dedekind_10 In particular, the Dedekind number for n = 10 is currently unknown sorry line 274 source

    Source documentation

    In particular, the Dedekind number for n = 10 is currently unknown.

    depends on sorry what this means

    Statement uses: Eq, Nat, DedekindNumber.M, OfNat.ofNat, sorryAx, Lean.Name, Bool.false, Lean.Name.num, Lean.Name.str, Lean.Name.anonymous

    2 instances, coercions and auxiliary constants left out.

    Tactic trace: 1 steps

    Open to load the checked before-and-after goal states.

    theorem Dedekind_10 : M 10 = answer(sorry) := by sorry
    …

    Mentions: DedekindNumber.M