Representability

Mathematical Logic · Axiom Academy

The bridge between computation and formal logic Mathematical Logic • Unit 5 - Gödel's Theorems Representability is a fundamental concept linking computability and formal systems. It asks: Can we express computational functions using formulas in Peano Arithmetic? A function is representable in PA if we can write a formula that "captures" the function's behavior. The formula should: Express the input-output relationship Be provable in PA for actual values Uniquely determine outputs from inputs Formal Definition of Representability Let's make this precise. A function needs both existence and uniqueness to be representable. Definition: Representable Function A function is representable in PA if there exists a formula such that for all natural numbers : is the numeral representing number Example: The Successor Function Let's see representability in action with the simplest function: the successor function . This function adds 1 to its input. In PA, we can use the built-in successor! For any , we have , and PA proves: The successor function is representable! Primitive Recursive Functions are Representable A remarkable theorem: Every primitive recursive function can be represented in PA. This includes addition, multiplication, and much more! Built from basic functions using: Composition: Combining functions Primitive Recursion: Defining by cases Examples of Representable Functions Multiplication: represented by Exponentiation: represented by formula in PA

This is the written version of the interactive lesson above. See the full Mathematical Logic course.