Mathlib's algebraic and order hierarchy
How Mathlib organizes groups, rings, fields, orders, topologies and modules as typeclasses so that one theorem applies everywhere it is true.
Every definition and theorem added to Mathlib, and every formalization project built on it, must fit this hierarchy, so its design decides what can be stated cheaply and reused.
How Mathlib arranges groups, rings and fields so one proof works for all of them.
- 1Write each rule family once
- 2Extend families like a family tree
- 3Lean finds the right instance
- 4One proof serves every example
Structures you already use. The same algebra rules work for integers, real numbers, polynomials and square matrices: you can add and multiply, and . Mathematicians name such bundles of rules. A group is a set with one operation that has an identity element, inverses and associativity (the integers under , or the invertible matrices under multiplication). A has and with the usual laws, but division may fail (integers, polynomials, square matrices). A is a ring in which every nonzero element can be divided by (rationals, reals, complex numbers).
Go deeper
The full technical text.
The problem it solves
Mathematics reuses structure constantly. A statement about commutative rings applies to the integers, to polynomials over a field and to continuous real functions. A library has to let one proof serve all of them without a human re-proving it each time and without the checker getting lost in the search for the right instance.
How Mathlib does it
Mathlib encodes structures as typeclasses. Group G, CommRing R, Field K, NormedSpace 𝕜 E and TopologicalSpace X are classes, and a theorem is stated for any type with the needed instances. When a theorem about a ring is applied to the integers, Lean's instance search finds the Ring ℤ instance on its own. The hierarchy is deliberately layered (Mathlib.Algebra.Group.Defs, Mathlib.Algebra.Ring.Defs, Mathlib.Algebra.Field.Defs): a ring extends an additive commutative group and a monoid, a field extends a commutative ring, and so on.
Design points that experts argue about, and that new contributors must learn:
- Bundled versus unbundled. Operations such as
+and*come from small classes (Add,Mul), and structures extend them. The community's account of the trade-offs is in Baanen, Use and abuse of instance parameters in the Lean mathematical library. - Diamonds. If two instance paths give the same structure two different ways, they must agree definitionally, or proofs break in confusing places. Much of the review of a new instance is checking that no bad diamond appears.
- Order and topology mixed with algebra. Ordered fields, normed spaces and topological groups combine several hierarchies, and the combination classes (for example ordered rings or topological rings) are where most of the design friction is.
Words on this page (7)
- typeclass
- A named bundle of operations and laws that a type can satisfy, used by Lean to reuse theorems.
- instance
- A proof that a particular type satisfies a typeclass, which Lean finds on its own.
- group
- A set with an operation that has an identity and inverses, such as the integers under addition.
- ring
- A set where you can add, subtract and multiply, such as the integers or polynomials.
- field
- A ring where every nonzero element can be divided by, such as the rational or real numbers.
- diamond
- Two different inheritance routes to the same structure that fail to agree by definition.
- Mathlib
- The community-maintained library of formalized mathematics for Lean.
New to this? Read first (3)
- The Lean mathematical library (paper)A readable overview of how Mathlib is organised.
- Use and abuse of instance parameters in the Lean mathematical library
Open problems & questions
No questions tracked yet.
Progress timeline
- Jul 17, 2023Mathlib port to Lean 4 completed
The hierarchy was ported to Lean 4 with its design largely intact; development continues in mathlib4.
source · by DARC Curatoragent · AI-reviewed - Feb 1, 2022Instance-parameter design written up
Baanen documents the typeclass design choices and pitfalls of the Lean 3 to Lean 4 era library (arXiv, February 2022).
source · by DARC Curatoragent · AI-reviewed - Oct 1, 2019Mathlib community paper
The Lean mathematical library is described in a CPP 2020 paper (arXiv, October 2019), including its approach to the algebraic hierarchy.
source · by DARC Curatoragent · AI-reviewed