Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Model Theory

7 missions · 6 completed

Missions

Open1Completed6All7
🏆Completed
Mathematical Logic·Captain: Lucas

Continuum Hypothesis: Independence from ZFCTextbook

Motivation

The continuum hypothesis (CH) asks how large the set of real numbers is. Cantor proved that ∣Z∣=∣Q∣<∣R∣|\mathbb Z|=|\mathbb Q|<|\mathbb R|∣Z∣=∣Q∣<∣R∣, and in 1878 he conjectured that no set has cardinality strictly between that of the integers and that of the reals. Settling CH was the first of Hilbert's problems at the 1900 International Congress of Mathematicians. The question was answered by showing that it cannot be answered from the standard axioms: CH is independent of Zermelo–Fraenkel set theory with choice (ZFC).

Timeline (as recorded in the source):

  • 1878 — Cantor formulates the (weak) continuum hypothesis; in 1882 he states CH in its modern form.
  • 1900 — Hilbert lists CH as the first of his problems.
  • 1906 — Kőnig proves a theorem that, combined with Hausdorff's notion of cofinality (1908), shows 2ℵ0≠ℵα2^{\aleph_0}\neq\aleph_\alpha2ℵ0​=ℵα​ whenever α\alphaα has cofinality ω\omegaω.
  • 1930 — Patai: if 2κ2^\kappa2κ is the γ\gammaγ-th successor of κ\kappaκ for every infinite κ\kappaκ, then γ\gammaγ is finite.
  • 1938/1940 — Gödel proves that AC and GCH hold in the constructible universe LLL, so Con(ZF)⇒Con(ZFC+GCH)\mathrm{Con}(\mathrm{ZF})\Rightarrow\mathrm{Con}(\mathrm{ZFC}+\mathrm{GCH})Con(ZF)⇒Con(ZFC+GCH).
  • 1947 — Sierpiński proves that ZF + GCH implies AC.
  • 1963 — Cohen invents forcing and proves Con(ZFC)⇒Con(ZFC+¬CH)\mathrm{Con}(\mathrm{ZFC})\Rightarrow\mathrm{Con}(\mathrm{ZFC}+\neg\mathrm{CH})Con(ZFC)⇒Con(ZFC+¬CH).
  • 1986 — Freiling shows that ¬\neg¬CH is equivalent to his axiom of symmetry.

Setting

A cardinal measures the size of a set; ∣A∣≤∣B∣|A|\le|B|∣A∣≤∣B∣ means there is an injection A→BA\to BA→B, and ∣A∣=∣B∣|A|=|B|∣A∣=∣B∣ a bijection. ℵ0=∣N∣\aleph_0=|\mathbb N|ℵ0​=∣N∣, 2κ=∣P(X)∣2^\kappa=|\mathcal P(X)|2κ=∣P(X)∣ for ∣X∣=κ|X|=\kappa∣X∣=κ, so ∣R∣=2ℵ0|\mathbb R|=2^{\aleph_0}∣R∣=2ℵ0​. ℵα\aleph_\alphaℵα​ is the α\alphaα-th infinite cardinal, ℶα\beth_\alphaℶα​ is defined by ℶ0=ℵ0\beth_0=\aleph_0ℶ0​=ℵ0​, ℶα+1=2ℶα\beth_{\alpha+1}=2^{\beth_\alpha}ℶα+1​=2ℶα​ and suprema at limits, and cf\mathrm{cf}cf denotes cofinality.

  • CH: there is no S⊆RS\subseteq\mathbb RS⊆R with ℵ0<∣S∣<2ℵ0\aleph_0<|S|<2^{\aleph_0}ℵ0​<∣S∣<2ℵ0​ (CH).
  • GCH: for every infinite cardinal κ\kappaκ there is no cardinal strictly between κ\kappaκ and 2κ2^\kappa2κ (GCH).

Independence is a statement about a first-order theory. The language of set theory has one binary relation symbol ∈\in∈ (setLang). ZF (ZF) consists of extensionality, foundation, pairing, union, power set, infinity, and all instances of the separation and replacement schemas; ZFC (ZFC) adds the axiom of choice (acSentence). CH and GCH are also written as first-order sentences (chSentence, gchSentence): CH says that every subset of P(ω)\mathcal P(\omega)P(ω) injects into ω\omegaω or receives an injection from P(ω)\mathcal P(\omega)P(ω). A theory is consistent if it has a model, and T⊨σT\models\sigmaT⊨σ means σ\sigmaσ holds in every model of TTT; by Gödel's completeness theorem these coincide with the proof-theoretic notions.

Formalization targets

Goal: independence of CH from ZFC

Con(ZFC) ⟹ ZFC⊭CH  and  ZFC⊭¬CH.\mathrm{Con}(\mathrm{ZFC})\ \Longrightarrow\ \mathrm{ZFC}\not\models\mathrm{CH}\ \text{ and }\ \mathrm{ZFC}\not\models\neg\mathrm{CH}.Con(ZFC) ⟹ ZFC⊨CH  and  ZFC⊨¬CH.

Milestones

  1. ∣Z∣=∣Q∣<∣R∣|\mathbb Z|=|\mathbb Q|<|\mathbb R|∣Z∣=∣Q∣<∣R∣.
  2. CH  ⟺  2ℵ0=ℵ1\mathrm{CH}\iff 2^{\aleph_0}=\aleph_1CH⟺2ℵ0​=ℵ1​.
  3. (Gödel) Con(ZF)⇒Con(ZFC+GCH)\mathrm{Con}(\mathrm{ZF})\Rightarrow\mathrm{Con}(\mathrm{ZFC}+\mathrm{GCH})Con(ZF)⇒Con(ZFC+GCH).
  4. ZFC+GCH⊨CH\mathrm{ZFC}+\mathrm{GCH}\models\mathrm{CH}ZFC+GCH⊨CH.
  5. (Cohen) Con(ZFC)⇒Con(ZFC+¬CH)\mathrm{Con}(\mathrm{ZFC})\Rightarrow\mathrm{Con}(\mathrm{ZFC}+\neg\mathrm{CH})Con(ZFC)⇒Con(ZFC+¬CH).
  6. (Kőnig) 2ℵ0≠ℵα2^{\aleph_0}\neq\aleph_\alpha2ℵ0​=ℵα​ when cf(α)=ω\mathrm{cf}(\alpha)=\omegacf(α)=ω; and cf(2ℵ0)>ℵ0\mathrm{cf}(2^{\aleph_0})>\aleph_0cf(2ℵ0​)>ℵ0​.
  7. (Sierpiński) ZF+GCH⊨AC\mathrm{ZF}+\mathrm{GCH}\models\mathrm{AC}ZF+GCH⊨AC.
  8. GCH  ⟺  ∀α, 2ℵα=ℵα+1  ⟺  ∀α, ℵα=ℶα\mathrm{GCH}\iff\forall\alpha,\ 2^{\aleph_\alpha}=\aleph_{\alpha+1}\iff\forall\alpha,\ \aleph_\alpha=\beth_\alphaGCH⟺∀α, 2ℵα​=ℵα+1​⟺∀α, ℵα​=ℶα​.
  9. Under GCH: A<B⇒2A<2BA<B\Rightarrow 2^A<2^BA<B⇒2A<2B for infinite AAA, and the three-case formula for ℵαℵβ\aleph_\alpha^{\aleph_\beta}ℵαℵβ​​.
  10. (Patai) ∀α, 2ℵα=ℵα+γ\forall\alpha,\ 2^{\aleph_\alpha}=\aleph_{\alpha+\gamma}∀α, 2ℵα​=ℵα+γ​ implies γ<ω\gamma<\omegaγ<ω.
  11. (Freiling) the axiom of symmetry is equivalent to ¬\neg¬CH.

Significance

The independence theorem shows that the ZFC axioms do not determine the size of the continuum, and it was among the first independence results for a mathematical statement. Its two halves introduced the two main tools of modern set theory: inner models (Gödel's LLL) and forcing (Cohen). Many statements in analysis, topology and measure theory were subsequently shown to be independent by the same methods.

For formalization, the goal requires a model theory of ZF inside Lean: interpreting the first-order theory, building LLL inside an arbitrary model of ZF, and building forcing extensions of an arbitrary model of ZFC. The independence of CH was formalized in Lean 3 by the Flypitch project (Han and van Doorn, 2019–2020); no Lean 4 / Mathlib formalization is known to this mission. The cardinal-arithmetic milestones (2, 6, 8–11) are theorems of ZFC that can be proved directly in Lean's cardinal library.

Difficulty

Neither half follows from cardinal arithmetic in Lean: Lean's foundations prove that models of ZFC exist, but (assuming they are consistent) they prove neither CH nor its negation about Lean's own Cardinal, so an argument inside Lean's cardinal arithmetic alone cannot produce the required models. Gödel's half needs relativization of formulas to a definable inner class and absoluteness of the construction of LLL; Cohen's half needs a generic extension in which a new family of ℵ2\aleph_2ℵ2​ reals is added while cardinals are preserved (the countable chain condition). Both require a theory of definability inside arbitrary, possibly non-well-founded, models of a first-order theory.

Formalization scope

  • Syntax and semantics are Mathlib's first-order logic (FirstOrder.Language, Theory.IsSatisfiable, Theory.ModelsBoundedFormula written ⊨ᵇ). Formulas name their variables by natural numbers; close φ is the universal closure. Equality is the built-in equality of first-order logic.
  • Consistency is satisfiability and provability is semantic consequence over models with universe in Type. By the completeness theorem these agree with the syntactic notions.
  • The first-order CH uses P(ω)\mathcal P(\omega)P(ω) in place of R\mathbb RR (they are equinumerous in ZF). The first-order GCH is the choice-free form "∣S∣≤∣T∣≤∣P(S)∣⇒∣T∣=∣S∣|S|\le|T|\le|\mathcal P(S)|\Rightarrow|T|=|S|∣S∣≤∣T∣≤∣P(S)∣⇒∣T∣=∣S∣ or ∣T∣=∣P(S)∣|T|=|\mathcal P(S)|∣T∣=∣P(S)∣, for SSS infinite".
  • The consistency results carry their hypotheses Con(ZF)\mathrm{Con}(\mathrm{ZF})Con(ZF) or Con(ZFC)\mathrm{Con}(\mathrm{ZFC})Con(ZFC) explicitly, even though these are provable in Lean. A solution may not replace a model of ZF by Lean's own universe in a way that assumes CH or its negation.
  • Results that need large-cardinal hypotheses or class forcing (Easton, Solovay, Foreman–Woodin, Merimovich) are not part of this mission.

Reusable infrastructure: the language of set theory with standard abbreviations (pairs, functions, ω\omegaω, power set), satisfaction lemmas for the abbreviations, relativization, absoluteness, the constructible hierarchy, and forcing over models of ZFC.

Selected references

  • G. Cantor, Ein Beitrag zur Mannigfaltigkeitslehre, J. Reine Angew. Math. 84 (1878) 242–258. https://doi.org/10.1515/crll.1878.84.242
  • K. Gödel, The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis, PNAS 24 (1938) 556–557. https://doi.org/10.1073/pnas.24.12.556
  • K. Gödel, The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis with the Axioms of Set Theory, Annals of Math. Studies 3, Princeton, 1940.
  • P. J. Cohen, The independence of the Continuum Hypothesis I, II, PNAS 50 (1963) 1143–1148; 51 (1964) 105–110. https://doi.org/10.1073/pnas.50.6.1143, https://doi.org/10.1073/pnas.51.1.105
  • C. Freiling, Axioms of symmetry: throwing darts at the real number line, J. Symbolic Logic 51 (1986) 190–200. https://doi.org/10.2307/2273955
  • L. Gillman, Two classical surprises concerning the Axiom of Choice and the Continuum Hypothesis, Amer. Math. Monthly 109 (2002) 544–553. https://doi.org/10.2307/2695444
  • K. Kunen, Set Theory: An Introduction to Independence Proofs, North-Holland, 1980.
  • Wikipedia, Continuum hypothesis (revision 1376315189). https://en.wikipedia.org/w/index.php?title=Continuum_hypothesis&oldid=1376315189
33 thms3 active usersReviewed
🏆Completed
Mathematical Logic·Captain: wurtle

A CH obstruction to a prescribed categoricity thresholdResearch Paper

Motivation: categoricity transfer beyond first-order logic

A class of structures is categorical in a cardinal λ\lambdaλ if it has exactly one model of size λ\lambdaλ up to isomorphism. Morley's theorem (1965) says that a complete first-order theory in a countable language categorical in one uncountable cardinal is categorical in all of them. Abstract elementary classes (AECs), introduced by Shelah in the 1970s, axiomatize classes of structures with a well-behaved notion of strong substructure (closure under isomorphism, coherence, unions of chains, a Löwenheim–Skolem number) without requiring first-order axiomatizability; they cover classes defined in infinitary logics and many classes of modules. Shelah's categoricity conjecture for AECs, in its eventual form, asks whether categoricity in one sufficiently large cardinal transfers to all sufficiently large cardinals. A sharper, prescribed-threshold form names the threshold explicitly: with H(K)=ℶ(2LS(K))+H(K)=\beth_{(2^{\mathrm{LS}(K)})^+}H(K)=ℶ(2LS(K))+​ (the Hanf number for existence of arbitrarily large models), categoricity in some λ≥H(K)\lambda\ge H(K)λ≥H(K) should imply categoricity in every μ≥H(K)\mu\ge H(K)μ≥H(K). Deciding which form holds is a central question in non-elementary model theory.

Timeline

  • 1965 — Morley proves the categoricity theorem for countable first-order theories (Trans. AMS 1965).
  • 1970s — Shelah introduces abstract elementary classes (see the survey of Boney–Vasey 2017, §2).
  • 1990 — Hart and Shelah show categoricity in Lω1,ωL_{\omega_1,\omega}Lω1​,ω​ can stop at ℵk\aleph_kℵk​ while holding for ℵ0,…,ℵk−1\aleph_0,\dots,\aleph_{k-1}ℵ0​,…,ℵk−1​, using finite-support group constructions (Israel J. Math. 1990).
  • 1999 — Shelah proves categoricity transfer for AECs with amalgamation and records H(K)H(K)H(K) as the existence bound (APAL 1999).
  • 2016 — Kolesnikov and Lambie-Hanson study Hanf numbers for amalgamation of coloring classes (JSL 2016).
  • 2017 — Vasey proves downward transfer from a successor cardinal ≥H(K)\ge H(K)≥H(K) under amalgamation and tameness (APAL 2017).
  • 2021 — Grossberg distinguishes the prescribed-bound and eventual forms of the conjecture (A Course in Model Theory I, draft, Ch. 2 §4).
  • 2022–2023 — Espíndola announces a proof of eventual categoricity and, for arbitrary AECs, a transfer at the prescribed bound via accessible categories (arXiv:1906.09169, arXiv:2301.13167).
  • 2024 — Šaroch and Trlifaj state the prescribed-threshold formulation with both endpoints included (Bull. LMS 2024, §2.3).
  • 2026 — An OpenAI preprint, A CH obstruction to a prescribed categoricity threshold (OpenAI Math Release, September 24, 2026), claims that under CH there is an AEC with LS(K)=ℵ0\mathrm{LS}(K)=\aleph_0LS(K)=ℵ0​, categorical on a tail but with two nonisomorphic models at H(K)=ℶω2H(K)=\beth_{\omega_2}H(K)=ℶω2​​; this conflicts with the transfer claimed in Espíndola 2023 (Theorem 4.1). The preprint has not been peer reviewed and its theorem is not formally verified.

Setting

Work with relational structures in a finitary relational language LLL (a set of relation symbols, each with a finite arity). An abstract elementary class is a class KKK of LLL-structures with a relation M⪯KNM\preceq_K NM⪯K​N ("strong substructure") such that: ⪯K\preceq_K⪯K​ is a partial order on KKK refining substructure; KKK and ⪯K\preceq_K⪯K​ are closed under isomorphism; coherence holds (M0⊆M1M_0\subseteq M_1M0​⊆M1​, M0⪯KM2M_0\preceq_K M_2M0​⪯K​M2​, M1⪯KM2M_1\preceq_K M_2M1​⪯K​M2​ imply M0⪯KM1M_0\preceq_K M_1M0​⪯K​M1​); unions of ⪯K\preceq_K⪯K​-chains are in KKK, are ⪯K\preceq_K⪯K​-extensions of each member, and are ⪯K\preceq_K⪯K​-below any common strong extension (Tarski–Vaught chain axioms); and there is a Löwenheim–Skolem number LS(K)≥ℵ0+∣L∣\mathrm{LS}(K)\ge\aleph_0+|L|LS(K)≥ℵ0​+∣L∣, the least θ\thetaθ such that every subset AAA of a model MMM lies in some N⪯KMN\preceq_K MN⪯K​M with ∣N∣≤∣A∣+θ|N|\le|A|+\theta∣N∣≤∣A∣+θ.

KKK is categorical in μ\muμ if it has a model of size μ\muμ and any two models of size μ\muμ are isomorphic. The beth numbers are ℶ0=ℵ0\beth_0=\aleph_0ℶ0​=ℵ0​, ℶα+1=2ℶα\beth_{\alpha+1}=2^{\beth_\alpha}ℶα+1​=2ℶα​ and suprema at limits. CH is 2ℵ0=ℵ12^{\aleph_0}=\aleph_12ℵ0​=ℵ1​.

Formalization targets

Goal: the CH counterexample (Theorem 1.1)

Assume CH. There is a countable finitary relational language LLL and an AEC KKK in LLL such that

LS(K)=ℵ0,ℶω2=H(K)=ℶ(2ℵ0)+,\mathrm{LS}(K)=\aleph_0,\qquad \beth_{\omega_2}=H(K)=\beth_{(2^{\aleph_0})^+},LS(K)=ℵ0​,ℶω2​​=H(K)=ℶ(2ℵ0​)+​,

KKK has two nonisomorphic models of cardinality ℶω2\beth_{\omega_2}ℶω2​​, and, with Λ=ℶ(2ℵ1)+\Lambda=\beth_{(2^{\aleph_1})^+}Λ=ℶ(2ℵ1​)+​,

K is categorical in every cardinal μ≥Λ.K\ \text{is categorical in every cardinal } \mu\ge\Lambda .K is categorical in every cardinal μ≥Λ.

Hence Λ+>H(K)\Lambda^+>H(K)Λ+>H(K) is a categoricity cardinal from which downward transfer to H(K)H(K)H(K) fails, while eventual categoricity holds for this KKK. The goal statement is published on the platform with status Open: no machine-checked proof exists yet.

Significance

The result itself. Combined with Gödel's relative consistency of CH, the theorem shows that, if ZFC is consistent, the prescribed-threshold form of Shelah's categoricity conjecture is not provable in ZFC (Corollary 6.1 of the source). The example has no amalgamation or joint embedding, which explains why transfer theorems that assume these properties are unaffected, and it is compatible with qualitative eventual categoricity. It also bears directly on a published claim of transfer at the prescribed bound for arbitrary AECs.

Formalizing it. Because the result contradicts a claimed theorem in the literature, an independent machine check is especially valuable. The formal statement verifies every AEC axiom explicitly, not just the two cardinal-arithmetic conclusions. Mathlib has cardinal and ordinal arithmetic, beth numbers and ZFC sets; the AEC framework built here would be reusable for further formal work in non-elementary model theory.

Difficulty

Most known non-transfer examples (Hart–Shelah) fail categoricity at small cardinals; here the failure must happen exactly at the Hanf-type bound ℶω2\beth_{\omega_2}ℶω2​​ while categoricity holds on a tail, with LS(K)=ℵ0\mathrm{LS}(K)=\aleph_0LS(K)=ℵ0​. One must build two nonisomorphic models at ℶω2\beth_{\omega_2}ℶω2​​ and simultaneously rule out any two nonisomorphic models above Λ\LambdaΛ, without appealing to a general eventual-categoricity theorem. All AEC axioms — in particular coherence and smoothness of unions of arbitrary directed chains — must survive the exceptional sets used to separate models, which is where naive constructions break.

Formalization scope

  • Structures are RelModel L with carrier a ZFSet (so cardinalities are cardinals of genuine sets in universe u) and relations indexed by arity; L:N→L:\mathbb N\toL:N→ Type with ΣnLn\Sigma_n L_nΣn​Ln​ countable.
  • ClassData packages a predicate of objects and a strong-substructure relation; IsAEC lists the axioms above, including invariance under isomorphisms compatible with inclusion, coherence, and the union axioms for chains indexed by any nonzero ordinal.
  • HasLSNumber ℵ₀ asserts both that ℵ0\aleph_0ℵ0​ is a Löwenheim–Skolem bound and that it is the least one.
  • hanf κ = beth (succ (2^κ)).ord, endpoint = beth (ω_2), tailThreshold = beth (succ (2^{ℵ₁})).ord. The equality endpoint = hanf ℵ₀ is part of the goal (it follows from CH).
  • Categorical μ includes existence of a model of size μ\muμ; TwoModels asks for two nonisomorphic models of the given size.
  • CH is a hypothesis of the theorem, in the same universe; the consistency corollary is not part of the goal.

Selected references

  • M. Morley, Categoricity in power, Trans. Amer. Math. Soc. (1965). https://doi.org/10.1090/S0002-9947-1965-0175782-0
  • K. Gödel, The consistency of the axiom of choice and of the generalized continuum-hypothesis, Proc. Nat. Acad. Sci. USA (1938). https://doi.org/10.1073/pnas.24.12.556
  • B. Hart and S. Shelah, Categoricity over P for first order T or categoricity for φ∈L_{ω1ω} can stop at ℵ_k while holding for ℵ_0,…,ℵ_{k−1}, Israel J. Math. (1990). https://doi.org/10.1007/BF02807869
  • S. Shelah, Categoricity for abstract classes with amalgamation, Ann. Pure Appl. Logic (1999). https://doi.org/10.1016/S0168-0072(98)00016-5
  • S. Vasey, Downward categoricity from a successor inside a good frame, Ann. Pure Appl. Logic (2017). https://doi.org/10.1016/j.apal.2016.10.003
  • W. Boney and S. Vasey, A survey on tame abstract elementary classes, 2017. https://arxiv.org/abs/1512.00060
  • A. Kolesnikov and C. Lambie-Hanson, The Hanf number for amalgamation of coloring classes, J. Symb. Logic (2016). https://doi.org/10.1017/jsl.2015.48
  • J. Šaroch and J. Trlifaj, Deconstructible abstract elementary classes of modules and categoricity, Bull. London Math. Soc. (2024). https://doi.org/10.1112/blms.13172
  • C. Espíndola, A complete classification of categoricity spectra of accessible categories with directed colimits, preprint, 2023. https://arxiv.org/abs/2301.13167
  • OpenAI, A CH obstruction to a prescribed categoricity threshold, OpenAI Math Release preprint, September 24, 2026 (source of the goal; Theorem 1.1, p. 2). https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold-September-24-2026/paper.pdf
26 thms3 active usersReviewed
🏆Completed
AlgebraMathematical LogicPure Mathematics·Captain: Alien60

Barto-Kozik: Absorbing Subalgebras and Cyclic TermsResearch Paper

Motivation

A constraint satisfaction problem CSP(A)\mathrm{CSP}(\mathbb A)CSP(A) asks whether a given conjunction of constraints, each a relation of a fixed finite structure A\mathbb AA, has a solution. The algebraic approach to its complexity studies the polymorphisms of A\mathbb AA, the operations preserving all of its relations. Bulatov, Jeavons and Krokhin (SIAM J. Comput. 2005) showed that CSP(A)\mathrm{CSP}(\mathbb A)CSP(A) is NP-complete unless the idempotent polymorphisms generate a Taylor variety, and conjectured that it is solvable in polynomial time in the Taylor case. Proving the hardness side and attacking the tractable side both need structural theorems about finite algebras in Taylor varieties. Timeline:

  • Taylor (Canad. J. Math. 1977) characterized Taylor varieties by the absence of a two-element algebra whose operations are all projections.
  • Hell and Nešetřil (J. Combin. Theory Ser. B 1990) proved the dichotomy for undirected graphs, and Barto, Kozik and Niven (SIAM J. Comput. 2009) proved it for digraphs with no sources and no sinks (the loop lemma), using the weak near-unanimity terms of Maróti and McKenzie (Algebra Universalis 2008).
  • Barto, Kozik, Maróti, McKenzie and Niven (Algebra Universalis 2009) obtained cyclic terms for finite congruence modular algebras.
  • Barto and Kozik (LMCS 8(1:07) 2012, arXiv:1201.0557) introduced absorbing subalgebras, proved the Absorption Theorem, gave a new proof of the loop lemma, and proved that every finite algebra in a Taylor variety has a cyclic term of every prime arity p>∣A∣p>|A|p>∣A∣.
  • Absorption is a central tool of the later proofs of the CSP dichotomy by Bulatov (arXiv:1703.03021) and Zhuk (arXiv:1704.01914).

This mission formalizes the absorption theory and the cyclic-term theorem of Barto–Kozik 2012.

Setting

An algebra is a set AAA with finitary basic operations of a fixed signature LLL; a term operation is an operation a↦t(a)a\mapsto t(a)a↦t(a) given by a term ttt in variables x0,…,xn−1x_0,\dots,x_{n-1}x0​,…,xn−1​. A subuniverse is a subset closed under all basic operations. Products A×BA\times BA×B and powers AkA^kAk carry the coordinatewise operations, so a subuniverse RRR of A×BA\times BA×B is itself an algebra. R⊆A×BR\subseteq A\times BR⊆A×B is subdirect (R≤SA×BR\le_S A\times BR≤S​A×B) if both projections are onto, and linked if any two elements a,a′a,a'a,a′ of its first projection are connected by a chain a=c0,c2,…,c2n=a′a=c_0,c_2,\dots,c_{2n}=a'a=c0​,c2​,…,c2n​=a′ where consecutive elements have a common RRR-neighbour c2i+1∈Bc_{2i+1}\in Bc2i+1​∈B.

An algebra is idempotent if every basic operation satisfies f(a,…,a)=af(a,\dots,a)=af(a,…,a)=a. A kkk-ary term ttt is a Taylor term if for every j<kj<kj<k an identity t(□0,…,□k−1)≈t(△0,…,△k−1)t(\square_0,\dots,\square_{k-1})\approx t(\triangle_0,\dots,\triangle_{k-1})t(□0​,…,□k−1​)≈t(△0​,…,△k−1​) holds with all □i,△i∈{x,y}\square_i,\triangle_i\in\{x,y\}□i​,△i​∈{x,y}, □j=x\square_j=x□j​=x and △j=y\triangle_j=y△j​=y. A Taylor variety is an idempotent variety with a Taylor term.

A subuniverse B⊆AB\subseteq AB⊆A absorbs AAA, written B⊴AB\trianglelefteq AB⊴A, if some term operation ttt satisfies t(a0,…,an−1)∈Bt(a_0,\dots,a_{n-1})\in Bt(a0​,…,an−1​)∈B whenever all aia_iai​ but at most one lie in BBB. It is proper if ∅≠B≠A\emptyset\ne B\ne A∅=B=A, and a minimal absorbing subuniverse, B⊴ ⁣ ⁣⊴AB\trianglelefteq\!\!\trianglelefteq AB⊴⊴A, if B≠∅B\neq\emptysetB=∅, B⊴AB\trianglelefteq AB⊴A and no proper subalgebra of BBB absorbs AAA. A digraph (A,E)(A,E)(A,E) is smooth if every vertex has an incoming and an outgoing edge. An oriented path has algebraic length equal to its number of forward edges minus its number of backward edges, and (A,E)(A,E)(A,E) has algebraic length 111 if some vertex is joined to itself by an oriented path of algebraic length 111. A kkk-ary term ttt (k≥2k\ge2k≥2) is cyclic if it is idempotent and t(x0,x1,…,xk−1)≈t(x1,…,xk−1,x0)t(x_0,x_1,\dots,x_{k-1})\approx t(x_1,\dots,x_{k-1},x_0)t(x0​,x1​,…,xk−1​)≈t(x1​,…,xk−1​,x0​); a relation R⊆AkR\subseteq A^kR⊆Ak is cyclic if it is closed under this rotation of tuples.

Formalization targets

Goal: Taylor varieties via cyclic terms (Barto–Kozik, Thm 4.1)

Let AAA be a finite idempotent algebra and V(A)V(A)V(A) the variety it generates. Then the following are equivalent:

V(A) is Taylor  ⟺  A has a cyclic term  ⟺  A has a p-ary cyclic term for every prime p>∣A∣.V(A)\text{ is Taylor}\iff A\text{ has a cyclic term}\iff A\text{ has a }p\text{-ary cyclic term for every prime }p>|A|.V(A) is Taylor⟺A has a cyclic term⟺A has a p-ary cyclic term for every prime p>∣A∣.

This characterizes finitely generated Taylor varieties by a single identity, t(x0,…,xp−1)≈t(x1,…,xp−1,x0)t(x_0,\dots,x_{p-1})\approx t(x_1,\dots,x_{p-1},x_0)t(x0​,…,xp−1​)≈t(x1​,…,xp−1​,x0​). The substantial implication is Thm 4.2 (a milestone); the others hold because a cyclic term is a Taylor term.

Milestones

  • Prop 2.7: if AAA (finite, in a Taylor variety) has no proper absorbing subuniverse, there is a term operation vvv such that for all b,c∈Ab,c\in Ab,c∈A and every coordinate iii, some tuple with bbb in position iii is mapped by vvv to ccc.
  • Thm 2.11 (Absorption Theorem): if A,BA,BA,B are finite algebras in a Taylor variety and R≤SA×BR\le_S A\times BR≤S​A×B is linked and R≠A×BR\neq A\times BR=A×B, then AAA or BBB has a proper absorbing subuniverse.
  • Prop 2.15: five properties (i)–(v) of minimal absorbing subuniverses with respect to a subdirect R≤SA×BR\le_S A\times BR≤S​A×B; for example, (iii): if RRR is linked, C⊴ ⁣ ⁣⊴AC\trianglelefteq\!\!\trianglelefteq AC⊴⊴A, D⊴ ⁣ ⁣⊴BD\trianglelefteq\!\!\trianglelefteq BD⊴⊴B and (C×D)∩R≠∅(C\times D)\cap R\neq\emptyset(C×D)∩R=∅, then C×D⊴ ⁣ ⁣⊴RC\times D\trianglelefteq\!\!\trianglelefteq RC×D⊴⊴R.
  • Thm 3.6 (Loop Lemma): a smooth digraph (A,E)(A,E)(A,E) of algebraic length 111 with EEE a subuniverse of A2A^2A2, AAA finite in a Taylor variety, has a loop; if a nonempty absorbing subuniverse lies in a weak component of algebraic length 111, there is a loop inside some J⊴ ⁣ ⁣⊴AJ\trianglelefteq\!\!\trianglelefteq AJ⊴⊴A.
  • Lemma 4.4: a finite idempotent algebra has a kkk-ary cyclic term operation iff every nonempty cyclic subuniverse of AkA^kAk contains a constant tuple.
  • Thm 4.2: a finite algebra in a Taylor variety has a ppp-ary cyclic term operation for every prime p>∣A∣p>|A|p>∣A∣.

Significance

The result itself. Thm 4.1 gives the identity form of the Bulatov–Jeavons–Krokhin conjecture, which is now the theorem of Bulatov and Zhuk: a finite structure has a tractable CSP iff it has a cyclic polymorphism. In Barto–Kozik it also yields short proofs of the Hell–Nešetřil theorem and of the Maróti–McKenzie weak near-unanimity theorem. The Absorption Theorem and the properties of minimal absorbing subuniverses are the basic tools of later work on absorption, including Zhuk's dichotomy proof.

Formalizing it. The results are proved. To our knowledge none of them has a machine-checked proof; the Prove2Me library has no absorption or Taylor-term development. This mission builds a reusable Lean library on Mathlib's model theory: absorption, linkedness, minimal absorbing subuniverses, the loop lemma, and cyclic relations.

Difficulty

The obvious attempt at Thm 4.2, the substantial direction of the goal, composes a Taylor term with itself until it becomes cyclic, and it fails because Taylor identities do not determine the term on most tuples. Barto–Kozik instead reduce to cyclic relations (Lemma 4.4) and pick a minimal counterexample. That needs every milestone for arbitrary finite algebras of the variety, including subalgebras of powers AnA^nAn and quotients. The Absorption Theorem is an induction over sets of common neighbours driven by the term of Prop 2.7. The Loop Lemma is an induction on ∣A∣|A|∣A∣ that juggles smooth parts, weak components, algebraic lengths and absorption at once. Bookkeeping for terms over products and powers, and for oriented paths, is heavy in Lean.

Formalization scope

  • Signature: L : FirstOrder.Language with [L.IsAlgebraic]; algebras are L.Structures on types with [Finite _]. The paper's signatures are finite; the Lean statements allow any signature, since they involve only term operations.
  • Taylor variety. A TaylorDatum L is a term t : L.Term (Fin k) with patterns σ j, τ j : Fin k → Bool (false =x=x=x, true =y=y=y, σ j j = false, τ j j = true). IsTaylorAlg T A says that AAA is idempotent and satisfies the identities t(σ j) ≈ t(τ j). These algebras form the Taylor variety axiomatized by those identities, and every algebra of a Taylor variety satisfies such a datum. "Finite algebras in a Taylor variety" means finite algebras satisfying one common datum T. Idempotency is imposed on basic operations, so a nullary symbol forces ∣A∣≤1|A|\le1∣A∣≤1. Degenerate data are harmless: a Taylor term of arity 000 or 111, combined with idempotency, also forces ∣A∣≤1|A|\le1∣A∣≤1.
  • A × B carries the coordinatewise structure prodStructure. Subuniverses of A×BA\times BA×B and A2A^2A2 are L.Substructures, and the algebra RRR is ↥R with Mathlib's induced structure. Subuniverses of AkA^kAk are sets of Fin k → A closed coordinatewise (IsSubpower). The rotation is x ∘ finRotate k, i.e. (x1,…,xk−1,x0)(x_1,\dots,x_{k-1},x_0)(x1​,…,xk−1​,x0​).
  • IsAbsorbing L B includes closure of BBB; MinAbsorbing requires nonemptiness. In Prop 2.7 the term has positive arity, which rules out a vacuous nullary witness. In Thm 3.6 the absorbing III is nonempty, as in the paper's use. Algebraic length is the inductive relation Walk E a b z.
  • Out of scope: (a) the converse half of the two-way Absorption Theorem 2.3 (for locally finite idempotent varieties); the paper derives it from Taylor's theorem in a few lines, and Thm 2.11 is the half it proves. (b) The CSP consequences (Smooth Theorem 3.1, Thm 4.15, the Hell–Nešetřil Cor 4.16); these combine the algebraic results with the external hardness theorem of Bulatov–Jeavons–Krokhin and need a theory of NP-completeness. (c) Cor 4.17, the paper's reproof of the Maróti–McKenzie theorem for locally finite varieties via free algebras. (d) Section 4.4 on arities: Prop 4.18 is cited from Barto–Kozik–Maróti–McKenzie–Niven, and Lemma 4.19 and Cor 4.20 are remarks stated without proof. All of these are natural follow-up missions.
  • In the goal, V(A)V(A)V(A) is Taylor is encoded as ∃ T, IsTaylorAlg T A, since V(A)V(A)V(A) is idempotent and satisfies exactly the identities of AAA.
  • Welcome contributions: reusable lemmas on term operations in products and powers, transitivity and intersection of absorption (Prop 2.4), absorbing neighbourhoods (Lemma 2.5), smooth parts (Lemma 3.3), and the claims inside the proof of Thm 4.2.

Selected references

  • L. Barto, M. Kozik, Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem, Logical Methods in Computer Science 8(1:07), 2012. doi:10.2168/LMCS-8(1:7)2012, arXiv:1201.0557
  • L. Barto, M. Kozik, M. Maróti, R. McKenzie, T. Niven, Congruence modularity implies cyclic terms for finite algebras, Algebra Universalis 61(3), 365–380, 2009. doi:10.1007/s00012-009-0025-z
  • L. Barto, M. Kozik, T. Niven, The CSP dichotomy holds for digraphs with no sources and no sinks, SIAM J. Comput. 38(5), 1782–1802, 2009. doi:10.1137/070708093
  • A. Bulatov, P. Jeavons, A. Krokhin, Classifying the complexity of constraints using finite algebras, SIAM J. Comput. 34(3), 720–742, 2005. doi:10.1137/S0097539700376676
  • P. Hell, J. Nešetřil, On the complexity of H-coloring, J. Combin. Theory Ser. B 48(1), 92–110, 1990. doi:10.1016/0095-8956(90)90132-J
  • M. Maróti, R. McKenzie, Existence theorems for weakly symmetric operations, Algebra Universalis 59(3–4), 463–489, 2008. doi:10.1007/s00012-008-2122-9
  • W. Taylor, Varieties obeying homotopy laws, Canad. J. Math. 29(3), 498–527, 1977. doi:10.4153/CJM-1977-054-9
  • A. Bulatov, A dichotomy theorem for nonuniform CSPs, arXiv:1703.03021; D. Zhuk, A proof of the CSP dichotomy conjecture, arXiv:1704.01914
13 thms1 active userReviewed
🏆Completed
AlgebraMathematical LogicPure Mathematics·Captain: Alien60

Higher Commutator Theory for Congruence Modular VarietiesResearch Paper

Motivation

Commutator theory gives general algebras the notions that group theory builds from the commutator subgroup [M,N][M,N][M,N]: abelian, central, solvable and nilpotent congruences. For congruence modular varieties, which include groups, rings, modules, quasigroups and lattices, the binary commutator was developed by Smith, Hagemann–Herrmann, Gumm and Freese–McKenzie, and has the expected properties: it is symmetric, additive in each argument, and compatible with homomorphisms (Freese–McKenzie 1987).

Many questions need commutators of more than two congruences. The best known is supernilpotence: an algebra is kkk-supernilpotent when its (k+1)(k+1)(k+1)-ary commutator [1,…,1][1,\dots,1][1,…,1] vanishes. Timeline:

  • Bulatov (2001) introduced higher commutators for Mal'cev algebras to count finite Mal'cev algebras of bounded size.
  • Aichinger and Mudrinski (2010) proved symmetry, additivity and the homomorphism property of higher commutators for algebras with a Mal'cev term.
  • Moorhead (arXiv:1610.07087; J. Algebra 513 (2018) 133–158) extended these properties to every congruence modular variety, using Day terms in place of a Mal'cev term.
  • Later work on supernilpotence uses these higher commutators. Moore and Moorhead constructed a supernilpotent algebra that is not solvable, so supernilpotence does not imply nilpotence in general (arXiv:1808.04858). Kearnes and Szendrei proved that it does for finite algebras (arXiv:1907.03216).

This mission formalizes Moorhead's paper.

Setting

An algebra is a set MMM with finitary basic operations. A congruence is an equivalence relation on MMM that is compatible with every basic operation. Congruences are ordered by inclusion and form a complete lattice Con(M)\mathrm{Con}(M)Con(M), with join ⋁iγi\bigvee_i\gamma_i⋁i​γi​ the smallest congruence that contains every γi\gamma_iγi​. A polynomial is a term operation in which elements of MMM may appear as constants.

Fix congruences T=(θ0,…,θk−1)T=(\theta_0,\dots,\theta_{k-1})T=(θ0​,…,θk−1​). Take a polynomial t(z0,…,zk−1)t(\mathbf z_0,\dots,\mathbf z_{k-1})t(z0​,…,zk−1​) whose iii-th block zi\mathbf z_izi​ is a tuple of variables, and pairs of tuples ai≡θibi\mathbf a_i\equiv_{\theta_i}\mathbf b_iai​≡θi​​bi​ (componentwise). For a vertex f∈{0,1}kf\in\{0,1\}^kf∈{0,1}k of the cube, evaluate ttt with ai\mathbf a_iai​ in block iii if f(i)=0f(i)=0f(i)=0 and bi\mathbf b_ibi​ if f(i)=1f(i)=1f(i)=1. The resulting map 2k→M2^k\to M2k→M is a TTT-matrix. A (j)(j)(j)-line of a TTT-matrix is a pair of vertices that differ only in coordinate jjj. The pivot (j)(j)(j)-line is the one at which all other coordinates equal 111, and the other (j)(j)(j)-lines are supporting. The term condition C(T;j;δ)C(T;j;\delta)C(T;j;δ) says that in every TTT-matrix, if every supporting (j)(j)(j)-line is a δ\deltaδ-pair, then so is the pivot (j)(j)(j)-line. The higher commutator is

[θ0,…,θk−1]  =  ⋀{δ∈Con(M):C(T;k−1;δ)},[\theta_0,\dots,\theta_{k-1}] \;=\; \bigwedge\{\delta\in\mathrm{Con}(M) : C(T;k-1;\delta)\},[θ0​,…,θk−1​]=⋀{δ∈Con(M):C(T;k−1;δ)},

and for k=2k=2k=2 it is the usual term-condition commutator. Day terms are 4-ary terms m0,…,mnm_0,\dots,m_nm0​,…,mn​ satisfying me(x,y,y,x)=xm_e(x,y,y,x)=xme​(x,y,y,x)=x, m0=xm_0=xm0​=x, mn=um_n=umn​=u, me(x,x,u,u)=me+1(x,x,u,u)m_e(x,x,u,u)=m_{e+1}(x,x,u,u)me​(x,x,u,u)=me+1​(x,x,u,u) for even eee, and me(x,y,y,u)=me+1(x,y,y,u)m_e(x,y,y,u)=m_{e+1}(x,y,y,u)me​(x,y,y,u)=me+1​(x,y,y,u) for odd eee. By Day's theorem (Day 1969), a variety has Day terms iff it is congruence modular.

Formalization targets

Goal: additivity (Moorhead, Prop 5.1)

If MMM has Day terms, then for congruences θ0,…,θk\theta_0,\dots,\theta_kθ0​,…,θk​ and any family (γi)i∈I(\gamma_i)_{i\in I}(γi​)i∈I​,

[θ0,…,θk,⋁i∈Iγi]  =  ⋁i∈I [θ0,…,θk,γi].[\theta_0,\dots,\theta_k,\textstyle\bigvee_{i\in I}\gamma_i] \;=\; \bigvee_{i\in I}\,[\theta_0,\dots,\theta_k,\gamma_i].[θ0​,…,θk​,⋁i∈I​γi​]=⋁i∈I​[θ0​,…,θk​,γi​].

Together with symmetry, this makes the commutator a completely join-preserving operation in each argument, which is the property most later uses rely on. The index set III is arbitrary, including empty and infinite.

Milestones

  • Lemma 3.1 (shift rotation): for j≠lj\neq lj=l and each e≤ne\le ne≤n, a map on TTT-matrices that rewrites every (j,l)(j,l)(j,l)-cross-section square [rsuv]\begin{bmatrix}r&s\\u&v\end{bmatrix}[ru​sv​] as [ssme(s,r,u,v)me(s,s,v,v)]\begin{bmatrix}s&s\\m_e(s,r,u,v)&m_e(s,s,v,v)\end{bmatrix}[sme​(s,r,u,v)​sme​(s,s,v,v)​]. It turns δ\deltaδ-supporting (j)(j)(j)-lines into δ\deltaδ-supporting (l)(l)(l)-lines and transfers the pivot condition.
  • Prop 3.2: C(T;l;δ)C(T;l;\delta)C(T;l;δ) for one coordinate lll implies C(T;i;δ)C(T;i;\delta)C(T;i;δ) for every iii.
  • Thm 3.3 (symmetry): [θσ(0),…,θσ(k)]=[θ0,…,θk][\theta_{\sigma(0)},\dots,\theta_{\sigma(k)}]=[\theta_0,\dots,\theta_k][θσ(0)​,…,θσ(k)​]=[θ0​,…,θk​] for k≥1k\ge1k≥1 and every permutation σ\sigmaσ.
  • Thm 4.4(2): C(T;δ)C(T;\delta)C(T;δ) holds iff [T]≤δ[T]\le\delta[T]≤δ.
  • Prop 5.2 (homomorphism property): for a surjective homomorphism fff with kernel π\piπ, [T]∨π=f−1([f(θ0∨π),…,f(θk∨π)])[T]\vee\pi=f^{-1}\big([f(\theta_0\vee\pi),\dots,f(\theta_k\vee\pi)]\big)[T]∨π=f−1([f(θ0​∨π),…,f(θk​∨π)]) for T=(θ0,…,θk)T=(\theta_0,\dots,\theta_k)T=(θ0​,…,θk​), k≥1k\ge1k≥1.
  • Prop 6.4 (two-term condition): C(T;δ)C(T;\delta)C(T;δ) iff Ctt(T;δ)C_{tt}(T;\delta)Ctt​(T;δ). Here Ctt(T;δ)C_{tt}(T;\delta)Ctt​(T;δ) says that two TTT-matrices which are δ\deltaδ-related at every vertex except the all-ones vertex are also δ\deltaδ-related there.

Significance

The result. Symmetry, additivity and the homomorphism property are the axioms that make the higher commutator usable. They underlie the definition of supernilpotence in congruence modular varieties and the later results on it cited above. The two-term characterization gives an equivalent condition that compares two matrices vertex by vertex, which extends Kiss's binary result to all arities. Without these properties, [θ0,…,θk−1][\theta_0,\dots,\theta_{k-1}][θ0​,…,θk−1​] is only an operation that favours its last argument.

Formalizing it. The results are proved; none is formalized. Mathlib has general first-order structures (FirstOrder.Language) but no congruence lattice of a general algebra, no polynomials, no Day terms and no commutator theory, and Prove2Me has no commutator-theory missions. The mission produces the first machine-checked higher commutator theory for congruence modular algebras, on a setting shaped like the universal-algebra mission on Birkhoff's HSP theorem (namespace UAVariety).

Difficulty

The definition privileges the last coordinate, so neither symmetry nor upward closure of C(T;δ)C(T;\delta)C(T;δ) in δ\deltaδ is formal. Both fail without congruence modularity: already a three-element groupoid has [α,β]≠[β,α][\alpha,\beta]\neq[\beta,\alpha][α,β]=[β,α]. Closure of C(T;δ)C(T;\delta)C(T;δ) under meets is immediate, but closure under joins in the last argument is not. Joining γi\gamma_iγi​ creates chains a=c0 γi0 c1⋯cq=b\mathbf a=\mathbf c_0\,\gamma_{i_0}\,\mathbf c_1\cdots\mathbf c_q=\mathbf ba=c0​γi0​​c1​⋯cq​=b, and the term condition gives no way to compose information along such a chain. The paper resolves this with combinatorics of 2k2^k2k-cubes driven by the Day identities. The formal difficulty is the bookkeeping: cross-section squares and lines of cubes indexed by {0,1}k\{0,1\}^k{0,1}k, polynomials in blocks of variables of arbitrary arity, and induction over trees of iterated shift rotations.

Formalization scope

  • Algebras. L : FirstOrder.Language, [L.Structure M]. Theorems assume [L.IsAlgebraic] (no relation symbols). Congruence M is a Setoid compatible with all operations, and φ ≤ ψ is inclusion. Congruence.iSup is the join, defined as the intersection of all upper bounds. Congruence.sup, ker, comap, map are binary join, kernel, preimage, and the congruence generated by the image.
  • Polynomials are L.Term ((Σ i : Fin k, Fin (r i)) ⊕ M): block i has any arity r i (zero allowed), and Sum.inr c is the constant c. Constants are essential, since terms without constants give a different condition.
  • Cubes. Vertices are f : Fin k → Bool. The (j)(j)(j)-line at f ignores f j. CentralAt T j δ is C(T;j;δ)C(T;j;\delta)C(T;j;δ), and higherComm T for T : Fin (k+2) → Congruence M is [T][T][T] with the last coordinate centralized (paper Def 2.2). As in the paper, every commutator and every theorem involves at least two congruences.
  • Day terms at the algebra level. IsDayTerms M m requires Day's identities to hold for all elements of M, not in a whole variety. This hypothesis is weaker than membership in a congruence modular variety, so the theorems are stronger, and the paper's proofs use congruence modularity only through these identities.
  • Ruling out trivialization. nnn is arbitrary, and constants are allowed in polynomials. Lemma 3.1 fixes the rotated squares explicitly, so its existential is not vacuous.
  • Reusable infrastructure, welcome as contributions: a CompleteLattice instance on Congruence M; Lemma 2.10 (the TTT-matrices form the subalgebra of M2kM^{2^k}M2k generated by matrices depending on one coordinate); the generator description [T]=Cg(X(T))[T]=\mathrm{Cg}(X(T))[T]=Cg(X(T)) (Thm 4.4(1)); Remark 2.14 (reindexing polynomials under permutations). These serve later Mal'cev, Jónsson and supernilpotence missions.

Selected references

  • A. Moorhead, Higher commutator theory for congruence modular varieties, J. Algebra 513 (2018) 133–158. https://doi.org/10.1016/j.jalgebra.2018.07.026 ; arXiv:1610.07087, https://arxiv.org/abs/1610.07087
  • R. Freese, R. McKenzie, Commutator Theory for Congruence Modular Varieties, LMS Lecture Note Series 125, Cambridge University Press, 1987. https://math.hawaii.edu/~ralph/Commutator/
  • A. Day, A characterization of modularity for congruence lattices of algebras, Canad. Math. Bull. 12 (1969) 167–173. https://doi.org/10.4153/CMB-1969-016-6
  • E. Aichinger, N. Mudrinski, Some applications of higher commutators in Mal'cev algebras, Algebra Universalis 63 (2010) 367–403. https://doi.org/10.1007/s00012-010-0084-1
  • M. Moore, A. Moorhead, Supernilpotence need not imply nilpotence, arXiv:1808.04858. https://arxiv.org/abs/1808.04858
  • K. A. Kearnes, Á. Szendrei, Is supernilpotence super nilpotence?, arXiv:1907.03216. https://arxiv.org/abs/1907.03216
8 thms1 active userReviewed
🏆Completed
Mathematical Logic·Captain: username

Friedman Stanley cofinality without Borel completenessOpen Problem

Motivation and historical context

Classification of countable structures asks whether objects have the same structure and whether one problem can supply definable invariants for another. Borel reducibility makes this comparison precise: a Borel map must preserve and reflect isomorphism. A class is Borel complete when every countable-structure isomorphism problem reduces to it. Friedman and Stanley introduced a hierarchy of bounded-rank tree problems and asked whether receiving every countable level already forces completeness. The question is stated in their original paper, page 899. Friedman–Stanley, 1989.

The relevant chronology distinguishes that general question from particular examples:

  • 1989: Friedman and Stanley develop Borel comparison of countable structures, establish their tree hierarchy, and ask whether completeness for all countable ranks implies Borel completeness. Original article, pages 899–902.
  • 2019: Shelah and Ulrich restate the question for infinitary sentences. Their Theorem 1.2 recalls Hjorth's result that every countable Friedman–Stanley level reduces to torsion-free abelian group isomorphism. Shelah–Ulrich, page 276.
  • 2024: Paolini and Shelah prove torsion-free abelian groups Borel complete. This settles that particular group example, while the general implication concerns arbitrary invariant Borel classes. Annals of Mathematics.
  • 2024: Shani studies the finite and omega Friedman–Stanley jumps through Borel homomorphism dichotomies. The supplied manuscript distinguishes these published levels from its proposed construction at arbitrary countable ordinals. arXiv:2405.18360.
  • 2 November 2026: the supplied research draft proposes a counterexample to the general implication. It reports internal checking only, with no claim of independent mathematical verification.

Setting

A countable relational language has at most countably many symbols, each with finite arity. A structure on the natural numbers assigns a truth value to each symbol and each tuple of the appropriate length. Nullary symbols are allowed. The resulting countable product of two-point spaces has its canonical Borel sigma algebra. Two structures are isomorphic when a single permutation of the natural numbers preserves all relation values.

An invariant Borel class is a Borel subset of that structure space closed under isomorphism. Borelness of the class does not assert Borelness of its isomorphism relation. Graphs are simple undirected graphs on the fixed vertex set of natural numbers.

For relations EEE and FFF, the notation E≤BFE\leq_B FE≤B​F means that some measurable map between their specified Borel code spaces satisfies

E(x,y)⟺F(f(x),f(y))E(x,y)\quad\Longleftrightarrow\quad F(f(x),f(y))E(x,y)⟺F(f(x),f(y))

for every pair of source points. Neither relation is assumed Borel merely by writing this comparison.

The benchmark J0\mathsf J_0J0​ is equality on Cantor space 2N2^{\mathbb N}2N. At successors, Jα+1\mathsf J_{\alpha+1}Jα+1​ compares enumerated countable sets of Jα\mathsf J_\alphaJα​ classes, with a distinct empty-set code; order and repetitions are ignored. At nonzero countable limits, the benchmark is a coordinatewise product along a fixed increasing cofinal sequence of smaller ordinals. Codes remain actual measurable sequence spaces, rather than quotient spaces of invariants.

Formalization targets

The goal is Theorem 1.2 of the supplied manuscript, not Question 1.1, which shares its numbering counter. There should be one fixed countable language LLL and one invariant Borel class K⊆Str⁡L(N)\mathcal K\subseteq\operatorname{Str}_L(\mathbb N)K⊆StrL​(N) such that

∀α<ω1,Jα≤B≅K,≅Graph̸≤B≅K,\forall\alpha<\omega_1,\qquad \mathsf J_\alpha\leq_B\cong_{\mathcal K}, \qquad \cong_{\mathrm{Graph}}\not\leq_B\cong_{\mathcal K},∀α<ω1​,Jα​≤B​≅K​,≅Graph​≤B​≅K​,

and, including the theorem's additional conclusion,

∀ 0<α<ω1,≅Tα≤B≅K.\forall\,0<\alpha<\omega_1,\qquad \cong_{\mathfrak T_\alpha}\leq_B\cong_{\mathcal K}.∀0<α<ω1​,≅Tα​​≤B​≅K​.

Here Tα\mathfrak T_\alphaTα​ denotes bounded-rank rooted well-founded tree codes, including finite and empty trees. The manuscript compares its product-limit benchmarks with the usual hierarchy conventions in Proposition 4.13 and with the original tree hierarchy in Proposition 4.15. No identification of ordinal indices between different presentations is asserted.

The milestones retain the source's attack path: the classical Borelness of bounded-rank tree isomorphism from Friedman–Stanley Section 1.2.1; Proposition 3.6 on invariant real-valued graph parameters; Theorem 4.1 on cofinality of Polishable subgroup coset relations; and Proposition 4.15 comparing the original tree hierarchy with the product-limit tower. The first is published background; the other three are targets from the proposed research draft.

Significance and current status

The target distinguishes being above every countable benchmark from being universal for all countable-structure classification problems. In the source's sentence formulation, it would give a negative answer to the question restated by Shelah and Ulrich. The structure-class formulation is the goal here; the infinitary-sentence corollary and the appendix's forcing and thickness claims are outside this mission.

The requested formalization is open. Local compilation validates the definitions and theorem interfaces, with explicit open-target placeholders; it does not verify the proposed mathematical proof. A completed development would provide reusable code-space constructions, ordinal-indexed comparison relations, bounded-tree interfaces, and permutation-group coset machinery.

Central difficulty

The quantifier ranges over every countable ordinal, while the language and target class must remain fixed. Results restricted to finitely many jumps, or even to the omega level, do not settle this claim. The distinction between countable sets and countable multisets is also substantive: the original tree codes retain multiplicities, while the set jump forgets them. Friedman–Stanley, Section 1.2.

The class of structures must itself be Borel and invariant. Replacing that requirement by Borelness of its isomorphism graph changes the problem. Individual reductions may depend on the ordinal; the theorem does not require a single Borel selection of reductions over all codes for countable well-orders.

Formalization scope

The Lean language bundle represents actual relational structures on N\mathbb NN by Boolean truth tables. The source allows functions and constants to be represented by relations; no structural axioms are imposed on the ambient space. A proposed target class must supply its own Borelness and invariance. Empty languages and empty classes are admitted by the interfaces, and no nontriviality is hidden in those definitions.

The tower uses native ordinal recursion below ω1\omega_1ω1​, equality on Cantor space, option-valued sequence codes for the set jump, and dependent countable products at limits. Fundamental sequences are fixed once; their strict increase and cofinality in the countable range are proved in the definition layer. This commits to the manuscript's product-limit presentation.

Tree codes are prefix-closed subsets of finite natural-number sequences. Isomorphisms are actual node bijections preserving and reflecting immediate parenthood. A global bound is expressed by an ordinal ranking into the bound, strictly decreasing along children; the empty tree has height zero and a single vertex height one. This specifies reverse-tree height explicitly and does not conflate the original convention with the separate leaf-zero padding convention. Finite and infinite branch multiplicities are retained.

The coset interface uses the actual group of permutations of N\mathbb NN with its standard Polish topology and the source convention pEHq  ⟺  q−1p∈HpE_Hq\iff q^{-1}p\in HpEH​q⟺q−1p∈H. No normality or closedness of the image subgroup is assumed. Contributions developing the ordinal, measurable-space, tree, and topological-group prerequisites are welcome.

Selected references

  • Friedman–Stanley cofinality and Borel completeness: A proposed negative answer to the Friedman–Stanley question, supplied research draft dated 2 November 2026, FriedmanStanleyQuestion.tex, Theorem 1.2; Proposition 3.6; Theorem 4.1; Propositions 4.13 and 4.15. Author field empty; no public manuscript URL supplied.
  • H. Friedman and L. Stanley, A Borel reducibility theory for classes of countable structures, Journal of Symbolic Logic 54 (1989), 894–914. DOI.
  • S. Shelah and D. Ulrich, Torsion-free abelian groups are consistently aΔ21\mathrm a\Delta^1_2aΔ21​-complete, Fundamenta Mathematicae 247 (2019), 275–297. Author-hosted paper.
  • G. Paolini and S. Shelah, Torsion-free abelian groups are Borel complete, Annals of Mathematics 199 (2024), 1177–1224. DOI.
  • A. Shani, The finite Friedman–Stanley jumps: generic dichotomies for Borel homomorphisms, 2024. arXiv:2405.18360.
9 thms1 active userReviewed
🏆Completed
Category TheoryFormal VerificationLogic+3·Captain: Alien60

Barrett–Halvorson 2016: Morita Equivalence Implies Categorical EquivalenceResearch Paper

Motivation

When are two scientific theories "the same theory in different words"? Philosophers of science have used two formal criteria. Definitional equivalence (Glymour) is strict: it requires a common definitional extension and therefore cannot relate theories with different numbers of sorts. Categorical equivalence (Halvorson, Weatherall) is liberal: it asks only that the categories of models be equivalent. It has been applied to classical mechanics, electromagnetism and Newtonian gravitation (Weatherall 2016; survey in Weatherall 2019).

Barrett and Halvorson (2016) proposed Morita equivalence as a syntactic criterion between these two. It allows definitions of new sorts (products, coproducts, subsorts, quotients) in addition to the usual definitions of new predicates and function symbols. Their main results place the new criterion strictly between the other two:

  • Morita equivalence implies categorical equivalence (their Theorem 5.1).
  • The converse fails (their Theorem 5.2).

This mission formalizes that comparison: the semantic core of Morita extensions, the implication, the separating example, and the paper's motivating "two kinds of things" example.

Setting

A signature Σ\SigmaΣ (Sig) consists of a type of sorts, function symbols f:σ1×⋯×σm→σf : \sigma_1\times\dots\times\sigma_m\to\sigmaf:σ1​×⋯×σm​→σ and predicate symbols p⊆σ1×⋯×σmp\subseteq\sigma_1\times\dots\times\sigma_mp⊆σ1​×⋯×σm​. Formulas (Formula L Γ) are built in a typed context Γ\GammaΓ from ⊥\bot⊥, ===, predicates, →\to→ and ∀\forall∀. A structure (Str) assigns a nonempty set to each sort and interprets the symbols. A theory TTT is a set of formulas in context, each read as its universal closure; a model of TTT is a structure satisfying them all.

The category Mod(T)\mathrm{Mod}(T)Mod(T) (Model T) has the models of TTT as objects and elementary embeddings as arrows: maps on every sort that preserve and reflect every formula. Theories T1,T2T_1,T_2T1​,T2​ are categorically equivalent (CategoricallyEquivalent) if Mod(T1)≃Mod(T2)\mathrm{Mod}(T_1)\simeq\mathrm{Mod}(T_2)Mod(T1​)≃Mod(T2​).

A Morita extension of a Σ\SigmaΣ-theory TTT (MoritaData L T) adds to Σ\SigmaΣ:

  • new sorts, each with its defining symbols:
    • a product σ\sigmaσ of σ1,σ2\sigma_1,\sigma_2σ1​,σ2​, with projections π1,π2\pi_1,\pi_2π1​,π2​;
    • a coproduct, with injections ρ1,ρ2\rho_1,\rho_2ρ1​,ρ2​;
    • a subsort cut out by a Σ\SigmaΣ-formula φ(x)\varphi(x)φ(x), with an injection iii;
    • a quotient by a Σ\SigmaΣ-formula φ(x1,x2)\varphi(x_1,x_2)φ(x1​,x2​), with a projection ε\varepsilonε;
  • new predicates and function symbols, each explicitly defined by a Σ\SigmaΣ-formula.

Each new symbol gets one defining axiom, and the symbols of one new sort share a single axiom. The extension T+T^+T+ (D.ext) is TTT together with these axioms. Each definition must satisfy its admissibility condition in every model of TTT:

DefinitionCondition
subsort∃x φ(x)\exists x\,\varphi(x)∃xφ(x)
quotientφ\varphiφ is an equivalence relation
function symbol∀x ∃!y φ(x,y)\forall x\,\exists!y\,\varphi(x,y)∀x∃!yφ(x,y)

The reduct gives a functor Π:Mod(T+)→Mod(T)\Pi:\mathrm{Mod}(T^+)\to\mathrm{Mod}(T)Π:Mod(T+)→Mod(T) (D.proj).

T1T_1T1​ and T2T_2T2​ are Morita equivalent (MoritaEquivalent) if two finite chains of Morita extensions T1⇝T1′T_1\rightsquigarrow T_1'T1​⇝T1′​ and T2⇝T2′T_2\rightsquigarrow T_2'T2​⇝T2′​ (MoritaReach) end in logically equivalent theories, that is, theories with the same models, over a common signature.

Formalization targets

Goal: Morita equivalence implies categorical equivalence

T1 Morita equivalent to T2  ⟹  Mod(T1)≃Mod(T2).T_1 \text{ Morita equivalent to } T_2 \;\Longrightarrow\; \mathrm{Mod}(T_1)\simeq\mathrm{Mod}(T_2).T1​ Morita equivalent to T2​⟹Mod(T1​)≃Mod(T2​).

Milestones

  1. Unique expansion. Every model MMM of TTT has an expansion N⊨T+N\models T^+N⊨T+ with ΠN≅M\Pi N\cong MΠN≅M, and any two such expansions are isomorphic.
  2. Π\PiΠ is faithful.
  3. Π\PiΠ is full.
  4. Conservativity. For every Σ\SigmaΣ-formula α\alphaα: T⊨αT\models\alphaT⊨α iff T+⊨αT^+\models\alphaT+⊨α.
  5. Translation. Every Σ+\Sigma^+Σ+-formula whose free variables all have old sorts is T+T^+T+-equivalent to a Σ\SigmaΣ-formula.
  6. Two kinds of things. T1={∃x p(x), ∃x q(x), ∀x (p(x)∨q(x)), ∀x ¬(p(x)∧q(x))}T_1=\{\exists x\,p(x),\ \exists x\,q(x),\ \forall x\,(p(x)\vee q(x)),\ \forall x\,\neg(p(x)\wedge q(x))\}T1​={∃xp(x), ∃xq(x), ∀x(p(x)∨q(x)), ∀x¬(p(x)∧q(x))} over one sort is Morita equivalent to the empty theory over two sorts.
  7. Separating example, first half. T1={∃=1x (x=x)}T_1=\{\exists^{=1}x\,(x=x)\}T1​={∃=1x(x=x)} and T2=T1∪{∀y (p0(y)→pi(y)):i∈N}T_2=T_1\cup\{\forall y\,(p_0(y)\to p_i(y)) : i\in\mathbb N\}T2​=T1​∪{∀y(p0​(y)→pi​(y)):i∈N}, over one sort and countably many unary predicates, are categorically equivalent.
  8. Separating example, second half. These two theories are not Morita equivalent.

Milestones 1–3 together say that Π\PiΠ is an equivalence of categories. Milestones 6–8 are not needed for the goal; they record the paper's examples, which show that Morita equivalence relates theories with different numbers of sorts and is strictly stronger than categorical equivalence.

Significance

The result itself. The goal makes Morita equivalence a syntactic sufficient condition for categorical equivalence: an explicit dictionary of definitions yields an equivalence of model categories. Milestone 8 shows the converse fails, so categorical equivalence is strictly weaker. Milestone 6 shows that Morita equivalence, unlike definitional equivalence, can relate theories with different numbers of sorts. Together these locate the criterion that later philosophy-of-physics work uses to compare formulations with different ontologies, such as different numbers of kinds of objects.

Formalizing it. The results are proved on paper and, as far as is known, have no machine-checked proofs. Mathlib's ModelTheory library is single-sorted, so none of this is available there. The mission produces a reusable many-sorted first-order logic with:

  • syntax, semantics and signature maps;
  • elementary embeddings and the category of models;
  • Morita extensions with their reduct functors.

The paper's arguments for conservativity and translation are informal in places; for example, the translation in the appendix uses coding of new-sorted variables. A formal proof fixes these details.

Difficulty

The obvious route to the goal composes the reduct functors along the chains. The work lies in showing that each reduct is an equivalence when the arrows are elementary embeddings.

  • Fullness. An elementary embedding of reducts extends uniquely to the new sorts. Showing that the extension is again elementary requires the translation of Milestone 5: every Σ+\Sigma^+Σ+-formula has to be pulled back to a Σ\SigmaΣ-formula, including formulas that quantify over the new sorts.
  • Coproduct and quotient sorts. Quantifiers over these sorts must be eliminated in favour of quantifiers over the old sorts.

For Milestone 8 the difficulty is reversed. One must rule out every pair of chains, including chains that introduce arbitrary new sorts. The paper's proof argues with a single common Morita extension. The definition, however, allows chains, and the paper notes that a chain need not collapse to a single extension. The argument must therefore be run through conservativity and translation along each chain.

Formalization scope

  • Self-contained logic. Signatures have dependent arities (Fin m → Srt). Terms and formulas use de Bruijn variables in typed contexts Γ : Fin n → Srt; Formula.all binds variable 0.
  • Theories. A theory is a Set (Axiom L), each axiom being a formula in context read as its universal closure. Because sorts are nonempty, this agrees with the sentence version.
  • Nonempty sorts. Every structure has nonempty carriers. This is the paper's convention, and without it Milestone 6 is false: the empty theory over two sorts would have models with an empty sort.
  • Morita extensions are built, not recognized. MoritaData L T lists the new sorts and symbols and their defining Σ\SigmaΣ-formulas. The signature Σ+\Sigma^+Σ+ (D.sig) and the axioms are generated from it, and admissibility is stated semantically, over all models of TTT. Any Morita extension in the paper's sense is of this form up to renaming of the new symbols.
  • A common signature up to renaming. MoritaEquivalent asks for a bijective signature map F between the two chain ends such that a structure is a model of T2′T_2'T2′​ iff its F-reduct is a model of T1′T_1'T1′​.
  • Universes. Models live in Type.
  • Separating example. The paper writes T2T_2T2​ with fresh symbols qiq_iqi​; here T1T_1T1​ and T2T_2T2​ share the signature with predicates pip_ipi​, which only renames symbols.
  • No trivialization. None of the targets holds vacuously: Morita extensions require genuine admissibility proofs, and the arrows are elementary embeddings, not arbitrary maps. Milestone 6 needs explicit chains and an explicit renaming, with arity casts.

A complete development will need:

  • the substitution and weakening lemmas for de Bruijn formulas;
  • the realization of signature maps;
  • the construction of expansions;
  • a translation function from Σ+\Sigma^+Σ+-formulas to Σ\SigmaΣ-formulas.

These pieces are reusable for any later work on interpretations or theoretical equivalence. Alternative proofs of Milestone 8, for example by counting finitely axiomatized subtheories, are welcome.

Selected references

  • T. W. Barrett, H. Halvorson, Morita Equivalence, Rev. Symb. Logic 9 (2016) 556–582. arXiv:1506.04675. Source of all targets: §3–§5 and the appendix; Example 4 and Theorems 4.1–4.3, 5.1, 5.2.
  • J. O. Weatherall, Are Newtonian Gravitation and Geometrized Newtonian Gravitation Theoretically Equivalent?, Erkenntnis 81 (2016) 1073–1091. arXiv:1411.5757.
  • J. O. Weatherall, Theoretical Equivalence in Physics, Philos. Compass 14 (2019). arXiv:1810.08192.
  • H. Halvorson, The Logic in Philosophy of Science, Cambridge University Press, 2019. doi:10.1017/9781316275603.
20 thms1 active userReviewed

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me