Tarski's undefinability theorem

Tarski's undefinability theorem

Tarski's undefinability theorem was proven by Alfred Tarski in 1933. It is an important idea in mathematical logic, the foundations of mathematics, and formal semantics.

The theorem tells us that some truths in arithmetic cannot be fully described using the rules of arithmetic itself.

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

The theorem is important because it shows deep links between logic, mathematics, and meaning. It influences many areas of modern mathematics and philosophy, helping us know which questions can and cannot be answered within a certain system.

History

In 1931, Kurt Gödel published the incompleteness theorems. He showed how to use numbers to represent the rules of logic in first-order arithmetic. This idea is called Gödel numbering.

Later, Alfred Tarski proved that math cannot fully describe what is true within math itself. This is known as Tarski's undefinability theorem. Tarski gave the formal proof for this in 1933.

Simplified statement

Alfred Tarski discovered an important idea in math in 1933. He showed that in the basic system of numbers and their addition and multiplication, you cannot make 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 might end up with a statement that says “this statement is false.” This creates a problem with logic. Because of this, the full idea of “truth” for these statements can’t be described 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 its own statements, you cannot define what "truth" means inside that same system. This is because if you could define truth, you would have a problem like the "liar" paradox: a statement that says "I am false." If this statement were true, it would be false. If it were false, it would be true. This is 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." This means assuming the opposite of what you want to prove and showing that this leads to a contradiction. Assuming you can define truth inside the system leads to an impossible situation, proving that it cannot be done.

Discussion

Tarski's undefinability theorem is simpler to understand and prove than Gödel's incompleteness theorems, but it is just as important. While Gödel's theorems focus on mathematics, Tarski's theorem talks about the limits of any language that can express complex ideas. It shows that such a language cannot fully explain its own meaning.

The theorem does not prevent 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 learn about the limits of what we can express in formal languages.

Main article: Gödel's incompleteness theorems