Gödel Numbering

Mathematical Logic · Axiom Academy

Unit 5: Gödel's Theorems - Encoding Syntax as Numbers 1. The Key Idea: Syntax as Numbers Gödel numbering is a systematic way to assign a unique natural number to every syntactic object in our formal system. We can use number theory to reason about logic itself Formulas become numbers, so formulas can refer to other formulas Ultimately, a formula can refer to itself Systematic: Every symbol gets a unique number Computable: We can calculate the Gödel number Decodable: We can recover the original syntax from the number 2. Assigning Numbers to Symbols We start by assigning a unique number to each basic symbol in our logical language. These assignments are arbitrary - what matters is that each symbol has a unique code. 3. Encoding Sequences Using Prime Factorization To encode a sequence of symbols (like a formula), we use the fundamental theorem of arithmetic : every number has a unique prime factorization. Example: Consider the sequence (7, 5, 7) Now we can encode entire formulas as numbers! Break the formula into its constituent symbols Replace each symbol with its Gödel number Use prime factorization to encode the sequence Example: Let's encode the formula A proof is just a sequence of formulas , so we can encode proofs too! Key observation: Properties of proofs become arithmetic properties! " P is a proof" becomes an arithmetic statement about the number encoding P " P proves φ " relates two numbers " φ is provable" becomes "there exists a number that encodes a proof of φ "

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