- C 62.2%
- C++ 23.8%
- Python 11.6%
- NASL 0.9%
- Makefile 0.9%
- Other 0.4%
| Filename | Latest commit message | Latest commit date |
|---|---|---|
| definitions | ||
| experiments/lrat-sharing/inputs | ||
| images | ||
| implementations | ||
| prover | ||
| sat | ||
| smt | ||
| tests | ||
| tptp | ||
| .gitignore | ||
| axiom-declarations.c | ||
| axiom-declarations.h | ||
| axioms.c | ||
| axioms.h | ||
| build-axioms.c | ||
| check-solution.c | ||
| cli-file.h | ||
| definitions.h | ||
| Formats.md | ||
| kernel.c | ||
| kernel.h | ||
| Makefile | ||
| Mathematics.md | ||
| print-context.c | ||
| print-dump.c | ||
| print-dump.h | ||
| print-internal.h | ||
| print-numerals.c | ||
| proof-file.c | ||
| proof-file.h | ||
| proof-slots.c | ||
| proof-stream.c | ||
| proof-stream.h | ||
| README.md | ||
| snapshot.c | ||
| snapshot.h | ||
| symbols.h | ||
| theorem-dump.c | ||
| theorem-dump.h | ||
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.