⁇Incompleteness and Undecidability Unit 4 – Peano Arithmetic & Recursive Functions

Key Concepts and Definitions

• Peano arithmetic formalizes the natural numbers and their properties using a set of axioms
• Recursive functions defined in terms of themselves, enabling computation over natural numbers
• Primitive recursive functions form a subset of total recursive functions, built using specific rules
• $\mu$-recursive functions extend primitive recursive functions by allowing unbounded search
• Ackermann function serves as an example of a total recursive function that is not primitive recursive
• Church-Turing thesis states that any effectively calculable function is recursive
• Gödel numbering assigns unique natural numbers to mathematical objects, enabling meta-mathematics
• Decidability refers to the existence of an effective method to determine membership in a set

Peano Axioms Explained

• Peano axioms consist of nine axioms that define the natural numbers and their properties
• First axiom asserts the existence of a natural number 0
• Second axiom defines the successor function $S(n)$, which returns the next natural number
• Third axiom states that 0 is not the successor of any natural number
• Fourth axiom asserts that if $S(a) = S(b)$, then $a = b$ (injectivity of the successor function)
• Fifth through eighth axioms define the properties of addition and multiplication
• Ninth axiom is the induction axiom, enabling proofs by mathematical induction
  • Induction axiom: If a property holds for 0 and, whenever it holds for a natural number $n$, it also holds for $S(n)$, then the property holds for all natural numbers

Building Natural Numbers

• Natural numbers are constructed using the Peano axioms, starting with 0 and the successor function
• 0 is the first natural number, defined by the first axiom
• Successive natural numbers are obtained by repeatedly applying the successor function: $S(0), S(S(0)), S(S(S(0))), \ldots$
• The natural number 1 is defined as $S(0)$, 2 as $S(S(0))$, 3 as $S(S(S(0)))$, and so on
• Addition of natural numbers is defined recursively using the successor function
  • $a + 0 = a$
  • $a + S(b) = S(a + b)$
• Multiplication of natural numbers is also defined recursively using addition
  • $a \cdot 0 = 0$
  • $a \cdot S(b) = a + (a \cdot b)$

Introduction to Recursive Functions

• Recursive functions are defined in terms of themselves, enabling computation over natural numbers
• Recursive definitions consist of one or more base cases and one or more recursive cases
• Base cases specify the function's value for certain inputs without recursion
• Recursive cases define the function's value in terms of the function itself applied to smaller inputs
• Recursive functions can be unary (one argument), binary (two arguments), or n-ary (n arguments)
• Examples of recursive functions include addition, multiplication, exponentiation, and factorial
  • Factorial function: $0! = 1$ (base case), $n! = n \cdot (n-1)!$ for $n > 0$ (recursive case)

Primitive Recursive Functions

• Primitive recursive functions are a subset of total recursive functions built using specific rules
• Basic primitive recursive functions include the zero function, successor function, and projection functions
• More complex primitive recursive functions are built using composition and primitive recursion
• Composition combines existing primitive recursive functions to create new ones
  • If $f$ and $g$ are primitive recursive, then $h(x_1, \ldots, x_n) = f(g(x_1, \ldots, x_n))$ is also primitive recursive
• Primitive recursion defines a function using recursion and previously defined primitive recursive functions
  • If $f$ and $g$ are primitive recursive, then $h$ defined by $h(0, \vec{x}) = f(\vec{x})$ and $h(S(y), \vec{x}) = g(y, h(y, \vec{x}), \vec{x})$ is also primitive recursive
• Examples of primitive recursive functions include addition, multiplication, exponentiation, and factorial

General Recursive Functions

• General recursive functions, also known as $\mu$-recursive functions, extend primitive recursive functions
• $\mu$-recursion allows the definition of functions using unbounded search (minimization)
• The $\mu$ operator finds the least natural number satisfying a given condition
  • $\mu y . f(x_1, \ldots, x_n, y) = 0$ denotes the least $y$ such that $f(x_1, \ldots, x_n, y) = 0$
• Ackermann function is an example of a total recursive function that is not primitive recursive
  • $A(0, n) = n + 1$
  • $A(m + 1, 0) = A(m, 1)$
  • $A(m + 1, n + 1) = A(m, A(m + 1, n))$
• General recursive functions are equivalent to the functions computable by Turing machines (Church-Turing thesis)

Applications and Examples

• Recursive functions have numerous applications in mathematics, computer science, and logic
• In number theory, recursive functions define arithmetic operations and number-theoretic functions
  • Fibonacci sequence: $F(0) = 0$, $F(1) = 1$, $F(n) = F(n-1) + F(n-2)$ for $n > 1$
• In computer science, recursive functions are used to implement algorithms and data structures
  • Merge sort: Recursively divide the list into halves, sort each half, and merge the sorted halves
• Recursive functions are essential for defining and studying formal systems and their properties
  • Gödel numbering assigns unique natural numbers to formulas and proofs, enabling meta-mathematics
• Recursive functions can model and analyze the behavior of complex systems and processes
  • Population growth models: $P(0) = P_0$ (initial population), $P(t+1) = r \cdot P(t)$ (growth rate $r$)

Limitations and Extensions

• Not all total functions on natural numbers are primitive recursive (e.g., Ackermann function)
• $\mu$-recursive functions extend primitive recursive functions but may not always terminate
• Some functions, like the busy beaver function, are not computable by any recursive function
• Higher-order recursive functions allow recursion on functions themselves, not just natural numbers
• Recursive functionals are higher-order functions that take recursive functions as arguments
• Transfinite recursion extends recursive definitions to ordinals beyond the natural numbers
• Recursion theory studies the properties and limitations of recursive functions and related concepts
  • Recursively enumerable sets are the domains of partial recursive functions
  • Recursive sets are both recursively enumerable and have recursively enumerable complements