Simple Arithmetic Functions from the Peano Axioms

peano.py

#!/usr/bin/env python3

def S(x): # O(1)
	"""Successor function.

	Simply put, S(x) = x + 1."""
	return x+1
def iS(y): # O(y)
	"""Inverse of the successor function.

	This does not "cheat" by subtracting one, instead
	it brute-forces the set of natural numbers."""
	x = 0
	while S(x) is not y: x += 1
	return x

def add(a, Sb): # O(Sb^2)?
	"""add(a, Sb) = a + Sb"""
	if Sb > a: return add(Sb, a)
	if Sb is 0: return a
	b = iS(Sb)
	return S(add(a, b))
def sub(a, b):
	"""sub(a, b) = a - b"""
	x = 0
	while add(x, b) is not a: x += 1
	return x
def mul(a, Sb): # O(Sb^3)?
	"""mul(a, Sb) = a * Sb"""
	if Sb > a: return mul(Sb, a)
	if Sb is 0: return 0
	b = iS(Sb)
	return add(a, mul(a, b))
def div(a, b):
	"""div(a, b) = a / b"""
	x = 0
	while mul(x, b) is not a: x += 1
	return x

print(add(8, 2))
print(sub(8, 2))
print(mul(8, 2))
print(div(8, 2))