Peano Arithmetic
Formalizing natural numbers and proving 2+2=4
Overview
This example shows how to formalize Peano arithmetic in Formall — defining natural numbers, equality, addition, and proving 2+2=4.
Complete Proof
Full 2+2=4 Proof
Complete working proof that can be executed in the interpreter.
Step-by-Step Explanation
1. Equality Setup
We establish reflexivity (x = x), substitution (if x = y, we can replace x with y), and symmetry (if x = y then y = x) — all inside a lock scope so they work as reusable axioms.
2. Number Definitions
Each number is defined as the successor of the previous: 2 = S(1), 3 = S(2), 4 = S(3).
3. Addition Axioms
A➕1: adding 1 is successor (x + 1 = S(x)). A➕2: recursive step (x + S(y) = S(x + y)).
4. The Calculation
2 + 2 = 2 + S(1) // by definition of 2 = S(2 + 1) // by A➕2 = S(S(2)) // by A➕1 = S(3) // by definition of 3 = 4 // by definition of 4
Key Techniques Used
T=S[a, b]— Apply symmetry: if=(a,b)proven, get=(b,a)A=I[a, b]— Apply substitution: if=(a,b)proven, enablea -> breplacementA➕1[2]— Instantiate addition axiom with specific value<...>— Chain substitutions together
This proof uses lock() with axiom to create reusable equality theorems. The lock ensures axioms are verified when applied via do.