Gödel number facts for kids

A Gödel numbering is a special way to give a unique number to every symbol and formula in a formal language, like the symbols and rules used in math. Think of it like assigning a secret code number to every letter, word, and sentence in a book. This number is called a Gödel number.

The idea was first used by a mathematician named Kurt Gödel. He used it to prove his famous incompleteness theorems. These theorems showed some surprising things about what math systems can and cannot prove.

A Gödel numbering helps us turn ideas and statements from a formal language into numbers. This means we can use math to study the properties of the language itself! It's like translating a language into a number code so that computers can understand and work with it.

What is a Gödel Numbering?

A Gödel numbering is a system where each symbol, formula, or even a whole sequence of formulas (like a mathematical proof) gets its own special number. No two different symbols or formulas will ever have the same Gödel number. This makes it a unique way to identify them.

Imagine you have a simple alphabet: A, B, C. You could give them numbers: A=1, B=2, C=3. Then, the "word" CAB could be represented by the sequence of numbers 3, 1, 2. A Gödel numbering does something similar, but for much more complex mathematical symbols and statements.

How Gödel Numbering Works

One simple way to understand how symbols can be turned into numbers is by thinking about how we write numbers. For example, the number "23" is made of the symbols '2' and '3'. We understand that '2' means twenty and '3' means three, making twenty-three. This is a basic form of encoding.

Gödel's Original Encoding Method

Kurt Gödel used a clever method involving prime numbers. Prime numbers are numbers like 2, 3, 5, 7, 11, and so on, that can only be divided by 1 and themselves.

Here's a simplified idea of how Gödel's method worked: 1. First, he assigned a unique number to every basic symbol in his mathematical system (like +, =, x, 0, 1, and so on). 2. Then, for a sequence of these symbols (which formed a "formula"), he would take the first few prime numbers and raise them to the power of the numbers assigned to the symbols.

For example, if you had a sequence of numbers like 1, 2, 3 (representing symbols), the Gödel number might be calculated like this:

• Take the first prime number (2) and raise it to the power of the first number (1): 2¹
• Take the second prime number (3) and raise it to the power of the second number (2): 3²
• Take the third prime number (5) and raise it to the power of the third number (3): 5³

Then, you multiply these results together: 2¹ × 3² × 5³ = 2 × 9 × 125 = 2250.

The amazing thing about this method is that because of the fundamental theorem of arithmetic (which says every number greater than 1 can be uniquely broken down into prime factors), you can always work backward from the Gödel number to find the original sequence of symbols. It's like a perfect, unbreakable code!

Gödel used this system to encode not just single formulas, but also entire sequences of formulas that represented mathematical proofs. This allowed him to translate statements about math into statements about numbers, which was key to his famous theorems.

Why is it Important?

Gödel numbering is a very important idea in mathematical logic and computer science. It shows that formal languages and their rules can be studied using the tools of arithmetic. This means that statements about a mathematical system can, in a way, "talk about themselves" through their Gödel numbers. This concept helped Gödel explore deep questions about what math can prove and what it cannot.

• Gödel, Kurt, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I", Monatsheft für Math. und Physik 38, 1931, pages 173–198.

• Gödel, Escher, Bach: an Eternal Golden Braid, by Douglas Hofstadter. This book defines and uses an alternative Gödel numbering.
• Gödel's Proof by Ernest Nagel and James R. Newman. This book provides a good introduction and summary of the proof, with a large section dedicated to Gödel's numbering.

See also

In Spanish: Numeración de Gödel para niños