Truly minimal kernel for mathematical foundations
  • C 62.2%
  • C++ 23.8%
  • Python 11.6%
  • NASL 0.9%
  • Makefile 0.9%
  • Other 0.4%
Find a file
Repository files (latest commit first)
Filename Latest commit message Latest commit date
2026-11-15 15:35:39 +01:00
definitions Make digiCons numerals canonical and optimize arithmetic proofs 2026-11-15 15:35:39 +01:00
experiments/lrat-sharing/inputs SAT replay: UP based on function composition 2026-11-08 12:25:19 +01:00
images have all the rules in intro picture 2026-11-06 00:08:01 +01:00
implementations fix comment 2026-11-12 22:13:36 +01:00
prover Make digiCons numerals canonical and optimize arithmetic proofs 2026-11-15 15:35:39 +01:00
sat Align axiom construction with Python and support theorem slot zero 2026-11-10 18:30:55 +01:00
smt Make digiCons numerals canonical and optimize arithmetic proofs 2026-11-15 15:35:39 +01:00
tests Make digiCons numerals canonical and optimize arithmetic proofs 2026-11-15 15:35:39 +01:00
tptp Align axiom construction with Python and support theorem slot zero 2026-11-10 18:30:55 +01:00
.gitignore theory: universes, reals & complex 2026-11-12 15:07:16 +01:00
axiom-declarations.c Align axiom construction with Python and support theorem slot zero 2026-11-10 18:30:55 +01:00
axiom-declarations.h Align axiom construction with Python and support theorem slot zero 2026-11-10 18:30:55 +01:00
axioms.c Add standalone demo implementations & tweak the axioms / challenge a little to be more systematic 2026-11-12 22:02:30 +01:00
axioms.h Refactor prover and add foundational math library 2026-11-05 17:06:42 +01:00
build-axioms.c Refactor prover and add foundational math library 2026-11-05 17:06:42 +01:00
check-solution.c Refactor prover and add foundational math library 2026-11-05 17:06:42 +01:00
cli-file.h repo init 2026-11-02 00:03:01 +01:00
definitions.h repo init 2026-11-02 00:03:01 +01:00
Formats.md Make digiCons numerals canonical and optimize arithmetic proofs 2026-11-15 15:35:39 +01:00
kernel.c make else explicit 2026-11-06 11:00:11 +01:00
kernel.h better comment 2026-11-05 18:18:12 +01:00
Makefile theory: universes, reals & complex 2026-11-12 15:07:16 +01:00
Mathematics.md Make digiCons numerals canonical and optimize arithmetic proofs 2026-11-15 15:35:39 +01:00
print-context.c more flexible printing 2026-11-07 01:32:14 +01:00
print-dump.c Align axiom construction with Python and support theorem slot zero 2026-11-10 18:30:55 +01:00
print-dump.h more flexible printing 2026-11-07 01:32:14 +01:00
print-internal.h more flexible printing 2026-11-07 01:32:14 +01:00
print-numerals.c Make digiCons numerals canonical and optimize arithmetic proofs 2026-11-15 15:35:39 +01:00
proof-file.c possible to set zstd compression level 2026-11-04 00:05:41 +01:00
proof-file.h possible to set zstd compression level 2026-11-04 00:05:41 +01:00
proof-slots.c checking the theorem slot limit in a proof file 2026-11-03 18:37:25 +01:00
proof-stream.c Align axiom construction with Python and support theorem slot zero 2026-11-10 18:30:55 +01:00
proof-stream.h Align axiom construction with Python and support theorem slot zero 2026-11-10 18:30:55 +01:00
README.md add download command lines 2026-11-14 23:22:42 +01:00
snapshot.c Align axiom construction with Python and support theorem slot zero 2026-11-10 18:30:55 +01:00
snapshot.h Refactor prover and add foundational math library 2026-11-05 17:06:42 +01:00
symbols.h repo init 2026-11-02 00:03:01 +01:00
theorem-dump.c Align axiom construction with Python and support theorem slot zero 2026-11-10 18:30:55 +01:00
theorem-dump.h Improve TPTP / Isinglass coverage & efficiency 2026-11-09 23:52:02 +01:00

Intro Picture

Micromath

Do you think that Lean's kernel is small? That is a lie.

HOL Light, or Metamath Zero are simpler but still far from minimal.

On 100 lines of C code, Micromath's kernel offers nothing more than a calculus for composing binary functions. Yet it already suffices to lay down the foundations for mathematics.

Why is it cool:

  • Truly minimal logical kernel (although compensated by larger axiom base)
  • Kernel operations in constant time: user have full control to optimize the proofs
  • Can do mathematics, for example the proof of Cantor-Bernstein theorem checks below 10ms.
  • Flexible theory strength: simple switch in the axiom generator chooses the number of universes to match the theoretical strength of Peano, ZFC, or stronger systems.

And there can be more to it than it might seem

  • Rewriting by a globaly true equality (e.g. commutativity of AND) inside a huge term is a constant time operation, even under a binder.
  • Merges defined constants with their bodies, at the same time doesn't distinguish definitional / proven equality
  • Verifying SAT proofs (RUP-steps in LRAT)
  • Verifying Vampire proofs (through Isinglass)
  • Verifying some SMT proofs by Primo
  • Clear optimization task for AI's: minimize the number of proof steps.
  • ...

Try it out

# download
git clone https://git.olsak.net/mirek/Micromath.git
cd Micromath

make build-axioms print-dump check-solution  # basic tools
make definitions/build-cantor-bernstein-challenge # challenge generation
make prover/prove-cantor-bernstein   # proof generation

./build-axioms axioms.umd          # store the set theory axioms
./print-dump --math axioms.umd            # print out the generated axioms
# set up the challenge to prove Cantor-Bernstein theorem
./definitions/build-cantor-bernstein-challenge axioms.umd cantor-bernstein.umd
# print out the axioms followed by the challenge specification
./print-dump --math cantor-bernstein.umd
# generate the proof for Cantor-Bernstein theorem
./prover/prove-cantor-bernstein cantor-bernstein.umd cantor-bernstein.ump
# verify the solution of Cantor-Bernstein theorem
./check-solution cantor-bernstein.umd cantor-bernstein.ump

make sat/build-challenge sat/prove-lrat sat/disprove-model  # SAT tools

# SAT proof verification
# translate DIMACS cnf to a micromath umd challenge (assuming axioms are already built)
./sat/build-challenge axioms.umd sat/examples/unsat5.cnf sat/examples/unsat5.umd
./sat/build-challenge axioms.umd sat/examples/sat5.cnf sat/examples/sat5.umd
./print-dump --sat sat/examples/unsat5.umd
./print-dump --sat sat/examples/sat5.umd
# translate LRAT (only RUP steps supported at the moment) to a Micromath proof
./sat/prove-lrat sat/examples/unsat5.umd sat/examples/unsat5.lrat sat/examples/unsat5.ump
./check-solution sat/examples/unsat5.umd sat/examples/unsat5.ump
# translate a model to a disproof
./sat/disprove-model ./sat/examples/sat5.umd ./sat/examples/sat5.model ./sat/examples/sat5.ump
./check-solution ./sat/examples/sat5.umd ./sat/examples/sat5.ump

Both challenge builders accept - for input or output. For example:

./build-axioms - | ./definitions/build-cantor-bernstein-challenge - - | ./print-dump --math -
./build-axioms --boolean - | ./sat/build-challenge - sat/examples/unsat5.cnf - | ./print-dump --sat -

Q & A

Q. What logic is it based on? How does it build mathematics? A. Kernel is just minimal first-order logic. The theory on top of it is set theory with second-order functions modeled with debruijn indices. For more details, check out Mathematics.md

Q. What is the language for proofs, or at least statements? A. Currently, there is no code for parsing the proofs, or statements. Prover's state can be dumped to a straightforward binary format (.umd -- MicroMath Dump), and proofs can be exported into a binary proof format (.ump -- MicroMath Proof) as well. More on the formats in Formats.md. To be able to understand the output of print-dump, read Mathematics.md.

Q. How much of this is Vibe-coded? A. Almost everything (I know that for many people, this is discouraging). Nevertheless, the design is of the system is done by me (human, Mirek Olšák), the small kernel is human-written, as well as Mathematics.md. By the way, the AI coders behave much more competent when they have a logic to rely on ;-).

Q. What source files do I need to check to trust it? A. The official Micromath uses kernel.c, kernel.h for the kernel including its dump / load. A challenge is checked with check-solution.c depending on snapshot.c (loading the kernel and the fixed true, false, and challenge roles, and skipping extended metadata), and on proof-stream.c replaying the proof file through kernel. To trust the axioms & challenge, either you need to check how they are built in axioms.c (called by build-axioms.c, using axiom-declarations.c) & definitions/cantor-bernstein.c (using definitions/functions.c and definitions/definition.c), or how they are printed using print-dump.c (for more advanced prints also print-context.c, and print-numerals.c). You can also check out standalone implementations of the checker & generator for Cantor-Bernstein challenge in C & Python in implementations.

Q. How many axioms are used? A. There are in total 52 = 10 + 10 + 9 + 3 + 11 + 9 axioms in the full setup (not counting auxiliary definitions to state them): 10 axioms about boolean operations & pairing, 10 axioms about context handling, 9 axioms about equality, bool rounding & ite, 3 axioms about quantification & choice, 11 axioms about set theory, and 9 axioms about universe handling.

Q. Are all the axioms necessary? A. Some of it is needed low-level plumbing (e.g. assuming that a symbol is unary). Sometimes they are indeed just convenience, for example assuming true = {0}. On the other hand, some convenience axioms are just stronger versions of otherwise important axiom, for example false = (X ∈ false) says that false is an empty set but also guarantees an empty set to exist. I don't see how to cut down the number of axioms significantly, while offering reasonably usable logic (at least for stating challenges without complex extra layer). If you have better ideas how to set up the axiomatic basis for Micromath, let me know.

Q. How much of the math library is developed? A. So far, we have integer & rational arithmetics, and the set-theoretical foundations needed to get there (transfinite recursion, functions, ...)

Q. I want AI to break this system. What should I instruct it? A. Prove inconsistency from any officially generated axioms. That is get

./build-axioms <arbitrary_legal_options> axioms.umd
./check-solution axioms.umd <arbitrary_malicious_proof_file>

to report

Inconsistency proven!

Building and source layout (by AI)

The build uses GNU make, GCC (or a compatible compiler and linker), and the Linux/POSIX C interfaces used by the file tools. make builds the command-line programs. make check also needs Python 3; zstd is optional for compressed proofs such as solution.ump.zst. Determinism checks compare dump builders at -O0 and -O2, using both GCC and Clang when available. The SMT arithmetic tools and rational proof calculator also require GMP. It plans arithmetic witnesses; the proof kernel does not depend on GMP.

All mathematical axiom fragments are declared in axioms.c; axiom-declarations.c allocates theorem slots and shares definitions by scanning kernel theorems, using the same first-definition convention as the printer (definitions.h). Stable symbol and axiom identifiers are attached at declaration; display names and presentation metadata remain in build-axioms.c. This builder does not link the prover or a definition library. SAT tools require only the named Boolean axioms in their input dump.

definitions/ contains on-demand definitions and challenge builders. definitions/auxiliary.c supplies xor, iff, ctxKeep, select, and intersect2; these are not included in axiom dumps because no axiom needs them. Their prover getters and the derived unary law for ctxKeep live in prover/core/library.c. For example, require_cantor_bernstein requests the definitions of a relation, function, inverse, injectivity, domain and image. Each getter first checks its stable identifier in the current state or loaded dump; only a missing result runs its constructor. Dependencies use the same getters, and cycles are rejected. Terms share a hash table. The standalone library only calls new_node_def in the kernel and does not link any prover code. definitions/build-cantor-bernstein-challenge.c provides the definitions/build-cantor-bernstein-challenge command.

prover/core/load-axioms.c imports axiom identifiers and checks the same axiom descriptions through read-only callbacks, without rebuilding the axioms or requiring their original slot numbers. prover/core/definition-state.c connects the definition getters to the prover's existing shared term table. prover/core/lemma-store.c provides named theorem getters: check memory and the dump, then execute the proof callback if missing, checking its exact statement. require_cantor_bernstein_theorem is an example. Saved shared proof recipes also reuse their formal templates, even when their in-memory cache is full or disabled. Saving newly built lemmas is opt-in, so ordinary SAT/SMT proof export retains its temporary-theorem reclamation.

Small propositional steps can be requested directly through boolean-prover.h. The prover works in the Boolean fragment on arbitrary symbols. It proves schemas up to atom renaming, simplifies branches before further splitting, and memoizes residual formulas. The active proof cache retains anonymous schemas; a saving lemma store also publishes them for later theory development. Atom arguments are opaque, so a large arithmetic or quantified predicate can be one parameter of a small law.

Symbol atoms[] = {a, b};
Symbol conclusion = term(boolean.Impl, term(boolean.And, a, b), a);
Theorem proof = boolean_tautology(conclusion, 2, atoms);
Theorem equation = boolean_equation(
    term(boolean.And, a, term(boolean.Or, a, b)), a, 2, atoms);

boolean_prove and boolean_equal accept explicit work budgets and return separate statuses for success, an abstract non-tautology, unsupported syntax, and budget exhaustion. A non-tautological abstraction can still represent a true concrete statement when its atoms have additional relationships. The budget counts visits during abstraction and search, not kernel instructions; expression/search recursion is also limited to 512. Worst-case search remains exponential. The convenience functions above use a default budget and fail with distinct diagnostics when unsuccessful.

For repeated use, acquire a BooleanLemma with boolean_lemma_acquire or boolean_equation_acquire, then call boolean_lemma_apply with new symbols in the original atom order. Applying a retained handle skips shape traversal and search. Release it with boolean_lemma_release; instances have scratch lifetime. This supports SAT setup lemmas, SMT gate clauses, TPTP guard identities and small theory-building steps through the same Boolean-only interface.

To save the prepared library and proved theorem for later development:

./prover/prove-cantor-bernstein cantor-bernstein.umd cantor-bernstein.ump --save-state theory.umd
./check-solution cantor-bernstein.umd cantor-bernstein.ump
./prover/prove-cantor-bernstein theory.umd resumed.ump --save-state theory-next.umd
./check-solution theory.umd resumed.ump

The second invocation fetches the saved theorem. Checkpoints preserve retained facts, definitions, names and proved normalization laws, clear discarded scratch facts, and restore reusable empty slots on load. The public C API is in prover/core/state.h; other proof modules can use it in the same way. The checkpoint remains a trusted .umd input, while each .ump is checked against the dump it started from. See Formats.md for the checkpoint metadata and lifetime rules.

The set-theory library builds selectable challenges for ordinals, transitive closure, membership minima, induction, and recursion using only the finitary fragment. Use definitions/build-set-theory-challenge --list to list statements and prover/prove-set-theory --list to see proof availability. Membership recursion and both natural-recursion formulas have independently checked proofs.

The integer arithmetic library uses singleton tags for negative numbers and normalizes all arithmetic inputs. definitions/build-arithmetic-challenge --list lists its statements; All 120 arithmetic challenges have independently checked proofs, including ordered-ring, which combines 50 core laws into one certificate. Build it with definitions/build-arithmetic-challenge ordered-ring, and prove it with prover/prove-arithmetic. This also needs only finitary axioms.

The kernel, axiom declarations, dump/printer code and independent checker are at the top level. General definitions and challenges are in definitions/; the untrusted proof-generation implementation is organized under prover/:

Directory Contents
prover/core/ Term sharing, theorem slots, axiom loading, named lemmas, checkpoints, proof recipes, caching, profiling, and export.
prover/logic/ Boolean algebra, context composition, equality, quantifiers, binder extensionality, guarded reasoning, and expression matching.
prover/sets/ Basic set laws, context transport, function graphs, and the ordinal/induction/recursion library.
prover/arithmetic/ Integer normalization, representation, recursion equations, and arithmetic induction.
prover/cantor-bernstein/ The fixed-point and graph construction, optimized preimage proof, alternative function-form proof, and named theorem getter.

The prove-*.c files directly under prover/ are command-line entry points; their executables keep the same paths. Library modules use subject names, without a proving- prefix. Includes use paths from the repository root, such as prover/logic/bool.h, so modules need no additional include search paths. The .inc files contain proof sections included by their owning C modules: sets/recursion.inc extends sets/theorems.c, while cantor-bernstein/fixed-point.inc shares the fixed-point argument between the image and preimage constructions. General graph operations belong in sets/graphs.c; cantor-bernstein/functions.c contains the bridge to that particular theorem's injection and bijection predicates.

SAT translation code and its two input examples are in sat/; the SMT encoder and congruence tools are in smt/. Regression tests are in tests/. Build artifacts go into build/, mirroring the source directories, apart from the public executables at the paths shown above.

The optional sat/cadical/ solver checkout is local and ignored by Git. The included SAT examples already have their LRAT proof or model, so CaDiCaL is not needed to run them. make clean removes build products while preserving user-created .umd/.ump files and the solver checkout.