FormalConjectures/Wikipedia/DedekindNumber.lean
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:
M n: the number of monotone Boolean functions(Fin n → Bool) → BoolM' n: the number of antichains (Sperner families) ofFinset (Fin n)
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
- instance
DedekindNumber.piFinBoolDecidableLEline 56 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,DecidableRel,Fin,Bool,LE.leProof uses:
Decidable,Eq.mpr8 instances, coercions and auxiliary constants left out.
Tactic trace: 2 steps
Open to load the checked before-and-after goal states.
- def
DedekindNumber.M$M(n)$ is the number of monotone Boolean functions on $n$ variables line 63 sourceSource 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:
NatProof uses:
Fintype.card,Subtype,Fin,Bool,Monotone,LE.le16 instances, coercions and auxiliary constants left out.
def M (n : ℕ) : ℕ := …
- def
DedekindNumber.IsSpernerA Sperner family (antichain) of subsets ofFin n: a family of sets such that no member is a subset of another line 68 sourceSource 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,FinProof uses:
IsAntichain,LE.le5 instances, coercions and auxiliary constants left out.
def IsSperner {n : ℕ} (A : Finset (Finset (Fin n))) : Prop := … - instance
DedekindNumber.isSpernerDecidableline 71 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,DecidablePred,Finset,Fin, DedekindNumber.IsSpernerProof uses:
id,Decidable,IsAntichain,LE.le,Set.Pairwise,Compl.compl,Eq.mpr,Membership.mem,Set,Ne,Not,inferInstance,Eq19 instances, coercions and auxiliary constants left out.
Tactic trace: 3 steps
Open to load the checked before-and-after goal states.
- def
DedekindNumber.M'$M'(n)$ is the number of antichains (Sperner families) of subsets ofFin nline 79 sourceSource 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:
NatProof uses:
Fintype.card,Subtype,Finset,Fin, DedekindNumber.IsSperner4 instances, coercions and auxiliary constants left out.
def M' (n : ℕ) : ℕ := …
- theorem
DedekindNumber.M_zeroValues for small n line 84 sourceSource 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.ofNatProof uses:
of_decide_eq_true4 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
- theorem
DedekindNumber.M_oneline 87 sourceextra axioms: _private.0.DedekindNumber.M_one._native.native_decide.ax_1 what this means
Statement uses:
Eq,Nat, DedekindNumber.M,OfNat.ofNatProof uses:
of_decide_eq_true4 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- theorem
DedekindNumber.M_twoline 90 sourceextra axioms: _private.0.DedekindNumber.M_two._native.native_decide.ax_1 what this means
Statement uses:
Eq,Nat, DedekindNumber.M,OfNat.ofNatProof uses:
of_decide_eq_true4 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- theorem
DedekindNumber.M_threeline 93 sourceextra axioms: _private.0.DedekindNumber.M_three._native.native_decide.ax_1 what this means
Statement uses:
Eq,Nat, DedekindNumber.M,OfNat.ofNatProof uses:
of_decide_eq_true4 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- theorem
DedekindNumber.M'_zeroline 96 sourceextra axioms: _private.0.DedekindNumber.M'_zero._native.native_decide.ax_1 what this means
Statement uses:
Eq,Nat, DedekindNumber.M',OfNat.ofNatProof uses:
of_decide_eq_true4 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- theorem
DedekindNumber.M'_oneline 99 sourceextra axioms: _private.0.DedekindNumber.M'_one._native.native_decide.ax_1 what this means
Statement uses:
Eq,Nat, DedekindNumber.M',OfNat.ofNatProof uses:
of_decide_eq_true4 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- theorem
DedekindNumber.M'_twoline 102 sourceextra axioms: _private.0.DedekindNumber.M'_two._native.native_decide.ax_1 what this means
Statement uses:
Eq,Nat, DedekindNumber.M',OfNat.ofNatProof uses:
of_decide_eq_true4 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- theorem
DedekindNumber.M'_threeline 105 sourceextra axioms: _private.0.DedekindNumber.M'_three._native.native_decide.ax_1 what this means
Statement uses:
Eq,Nat, DedekindNumber.M',OfNat.ofNatProof uses:
of_decide_eq_true4 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- def
DedekindNumber.χThe indicator function of a finset:χ s i = true ↔ i ∈ sline 111 sourceSource 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,BoolProof uses:
Decidable.decide,Membership.mem4 instances, coercions and auxiliary constants left out.
def χ {n : ℕ} (s : Finset (Fin n)) : Fin n → Bool := … - def
DedekindNumber.suppThe support of a Boolean-valued function:supp v = {i | v i = true}line 115 sourceSource 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,FinsetProof uses:
Finset.filter,Eq,Bool.true,Finset.univ2 instances, coercions and auxiliary constants left out.
def supp {n : ℕ} (v : Fin n → Bool) : Finset (Fin n) := … - def
DedekindNumber.toSpernerForward map: monotone function → Sperner family (the minimal true sets) line 119 sourceSource 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,FinsetProof uses:
Finset.filter,And,Eq, DedekindNumber.χ,Bool.true,LE.le,Finset.univ11 instances, coercions and auxiliary constants left out.
def toSperner {n : ℕ} (f : (Fin n → Bool) → Bool) : Finset (Finset (Fin n)) := … - def
DedekindNumber.fromSpernerBackward map: Sperner family → monotone Boolean function line 124 sourceSource documentation
Backward map: Sperner family → monotone Boolean function.
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,Finset,Fin,BoolProof uses:
Decidable.decide,Exists,And,Membership.mem,Eq,Bool.true8 instances, coercions and auxiliary constants left out.
def fromSperner {n : ℕ} (A : Finset (Finset (Fin n))) (v : Fin n → Bool) : Bool := … - lemma
DedekindNumber.χ_suppline 130 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,Fin,Bool,Eq, DedekindNumber.χ, DedekindNumber.suppProof 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_self8 instances, coercions and auxiliary constants left out.
Tactic trace: 2 steps
Open to load the checked before-and-after goal states.
- lemma
DedekindNumber.supp_χline 134 sourcestandard 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_self10 instances, coercions and auxiliary constants left out.
Tactic trace: 2 steps
Open to load the checked before-and-after goal states.
- lemma
DedekindNumber.χ_le_iffline 139 sourcestandard 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_self17 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- lemma
DedekindNumber.mem_supp_iffline 143 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,Fin,Bool,Iff,Membership.mem,Finset, DedekindNumber.supp,Eq,Bool.trueProof uses:
of_eq_true,Eq.trans,True,congrFun',congrArg,Finset.filter,Finset.univ,And,true_and,iff_self8 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- lemma
DedekindNumber.toSperner_isSpernerline 147 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,Fin,Bool,Monotone, DedekindNumber.IsSperner, DedekindNumber.toSpernerProof 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.trueand 11 more31 instances, coercions and auxiliary constants left out.
Tactic trace: 5 steps
Open to load the checked before-and-after goal states.
- lemma
DedekindNumber.fromSperner_monotoneline 153 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,Finset,Fin, DedekindNumber.IsSperner,Monotone,Bool, DedekindNumber.fromSpernerProof 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_eqand 11 more21 instances, coercions and auxiliary constants left out.
Tactic trace: 11 steps
Open to load the checked before-and-after goal states.
- lemma
DedekindNumber.exists_minimal_true_subsetEvery true set of a monotone Boolean function contains a minimal true set line 168 sourceSource 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.leProof 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.transand 14 more27 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.χ
- lemma
DedekindNumber.fromSperner_toSpernerConverting a monotone function to a Sperner family and back yields the same function line 184 sourceSource 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.toSpernerProof 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,HEqand 36 more38 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
- lemma
DedekindNumber.toSperner_fromSpernerConverting a Sperner family to a monotone function and back yields the same family line 203 sourceSource 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.fromSpernerProof 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_eqand 32 more36 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
- def
DedekindNumber.equivMonotoneSpernerThe set of monotone Boolean functions onnvariables is in bijection with the set of Sperner families of subsets ofFin nline 219 sourceSource documentation
The set of monotone Boolean functions on
nvariables is in bijection with the set of Sperner families of subsets ofFin n.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,Equiv,Subtype,Fin,Bool,Monotone,Finset, DedekindNumber.IsSpernerProof uses:
Equiv.mk,DedekindNumber.equivMonotoneSperner.match_1,Subtype.mk, DedekindNumber.toSperner, DedekindNumber.toSperner_isSperner,DedekindNumber.equivMonotoneSperner.match_2, DedekindNumber.fromSperner, DedekindNumber.fromSperner_monotone8 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
- theorem
DedekindNumber.M_eq_M'line 228 sourcestandard 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.equivMonotoneSperner18 instances, coercions and auxiliary constants left out.
Tactic trace: 2 steps
Open to load the checked before-and-after goal states.
- def
DedekindNumber.kisielewiczFormulaA closed formula for the Dedekind numbers as found by Kisielewicz (1998) line 238 sourceSource 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:
NatProof uses:
Finset.sum,Finset.range,HPow.hPow,OfNat.ofNat,Finset.prod,Finset.Icc,HSub.hSub,HMul.hMul,Bool.toNat,Nat.testBit,HAdd.hAdd,Nat.log215 instances, coercions and auxiliary constants left out.
def kisielewiczFormula (n : ℕ) : ℕ := …
- theorem
DedekindNumber.kisielewiczFormula_zeroline 243 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Eq,Nat, DedekindNumber.kisielewiczFormula,OfNat.ofNatProof uses:
of_decide_eq_true,id,Bool,Decidable.decide,Bool.true,Eq.refl3 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- theorem
DedekindNumber.kisielewiczFormula_oneline 244 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Eq,Nat, DedekindNumber.kisielewiczFormula,OfNat.ofNatProof uses:
of_decide_eq_true,id,Bool,Decidable.decide,Bool.true,Eq.refl3 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- theorem
DedekindNumber.kisielewiczFormula_twoline 245 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Eq,Nat, DedekindNumber.kisielewiczFormula,OfNat.ofNatProof uses:
of_decide_eq_true,id,Bool,Decidable.decide,Bool.true,Eq.refl3 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- theorem
DedekindNumber.kisielewiczFormula_threeline 246 sourceextra axioms: _private.0.DedekindNumber.kisielewiczFormula_three._native.native_decide.ax_1 what this means
Statement uses:
Eq,Nat, DedekindNumber.kisielewiczFormula,OfNat.ofNatProof uses:
of_decide_eq_true4 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- theorem
DedekindNumber.M_eq_kisielewiczFormulaKisielewicz (1988) proved the following arithmetic formula for the Dedekind numbers sorry line 259 sourceSource 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.kisielewiczFormulaProof uses:
sorryAx,Lean.Name,Bool.false,Lean.Name.num,Lean.Name.str,Lean.Name.anonymous,OfNat.ofNat1 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
- theorem
DedekindNumber.M_eqNo closed-form expression that allows efficient computation of Dedekind numbers is currently known sorry line 267 sourceSource 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.ofNat2 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
- theorem
DedekindNumber.Dedekind_10In particular, the Dedekind number forn = 10is currently unknown sorry line 274 sourceSource documentation
In particular, the Dedekind number for
n = 10is 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.anonymous2 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