Playground Documentation Challenges Full Docs

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.

▶ Run

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, enable a -> b replacement
  • A➕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.