Tarski's undefinability theorem

Tarski's undefinability theorem, proven by Alfred Tarski in 1933, is a key idea in mathematical logic, the foundations of mathematics, and formal semantics. It tells us that certain truths in arithmetic cannot be fully captured or defined using the rules of arithmetic itself.

This theorem shows that for any strong enough formal system, the concept of truth for that system cannot be defined entirely within the system. This discovery helps us understand the limits of what we can prove or define using mathematical logic.

The theorem is important because it reveals deep connections between logic, mathematics, and meaning. It influences many areas of modern mathematics and philosophy, showing us what questions can and cannot be answered within a given system.

History

In 1931, Kurt Gödel published the incompleteness theorems, showing how to represent the rules of logic using numbers in first-order arithmetic. This idea, called Gödel numbering, helps us understand how math can talk about itself.

Later, Alfred Tarski showed that we cannot use math to fully describe what is true within math itself. This is known as Tarski's undefinability theorem. Even though Gödel had similar ideas earlier, Tarski is credited with formally proving this important result in 1933.

Simplified statement

Alfred Tarski discovered an important idea in math in 1933. He showed that inside the basic system of numbers and their addition and multiplication, you cannot create a rule that tells you which statements are true. This is called Tarski’s undefinability theorem.

Think of it like this: if you could write a rule inside this number system to say what’s true, you could use that rule to make a statement that says “this statement is false.” That creates a problem with logic, like a loop that can’t be solved. Because of this, the full idea of “truth” for these statements can’t be captured inside the same system. To describe truth, you need a bigger, more powerful system.

General form

Alfred Tarski showed that in any system that can talk about numbers and can refer to its own statements, you cannot define what "truth" means inside that same system. This is because if you could define truth, you would run into a problem similar to the famous "liar" paradox: a statement that says "I am false." If this statement were true, then it would be false, and if it were false, then it would be true—a contradiction.

Tarski’s theorem applies to many formal systems, including basic arithmetic and more complex ones like Zermelo-Fraenkel set theory ZFC. The proof uses a method called "reductio ad absurdum," which means assuming the opposite of what you want to prove and showing that this leads to a contradiction. In this case, assuming you can define truth inside the system leads to an impossible situation, thus proving that it cannot be done.

Discussion

Tarski's undefinability theorem is easier to understand and prove than Gödel's incompleteness theorems, even though it is just as important. While Gödel's theorems talk mostly about mathematics, Tarski's theorem is about the limits of any language that can express complicated ideas. It shows that such a language cannot fully describe its own meaning.

The theorem does not stop us from defining truth in one system using a stronger system. For example, we can define what is true in basic arithmetic using a more advanced system. This idea helps us understand the boundaries of what we can express in formal languages.

Main article: Gödel's incompleteness theorems