Proof theory

Proof theory is a fascinating area of study that belongs to both mathematical logic and theoretical computer science. In proof theory, mathematicians look at proofs — the step-by-step reasons we use to show that something is true — as formal mathematical objects. This means they study proofs using math itself, treating them like numbers or shapes that can be analyzed in detail.

Proofs in this field are often seen as special kinds of structures, like lists or trees, that follow strict rules. These rules come from the basic assumptions, called axioms, and the ways we can build new statements from old ones, known as rules of inference. This way of thinking helps experts understand the deep properties of logical systems.

Proof theory has many different areas of study, such as structural proof theory, ordinal analysis, and automated theorem proving. It also has useful applications in computer science, linguistics, and philosophy, showing how important this way of thinking is across many fields.

History

Proof theory began with the work of mathematicians like Gottlob Frege, Giuseppe Peano, Bertrand Russell, and Richard Dedekind. It became a major field thanks to David Hilbert, who started Hilbert's program to make sure mathematical theories were reliable.

Later, Kurt Gödel showed that some theories could not prove their own reliability. This led to new ideas and research in proof theory, including provability logic and self-verifying theories. During this time, Jan Łukasiewicz, Stanisław Jaśkowski, and Gerhard Gentzen developed new ways to understand how proofs work, like natural deduction and the sequent calculus. These ideas helped make proofs clearer and easier to study.

Structural proof theory

Main article: Structural proof theory

Structural proof theory is a part of proof theory that looks closely at different ways to write down logical proofs, called proof calculi. The three most famous styles are Hilbert calculi, natural deduction calculi, and sequent calculi. These methods can be used to study many kinds of logic, including basic propositional and predicate logic, as well as more complex logics.

Researchers in this area are especially interested in a type of proof called analytic proofs. These proofs have special properties that make them easier to study and understand. For example, in sequent calculus, analytic proofs are those that do not use a certain rule called "cut." This helps show that the logic system is consistent. There are also connections between structural proof theory and type theory, showing how different areas of mathematics and logic relate to each other.

Ordinal analysis

Main article: Ordinal analysis

Ordinal analysis is a special method used to show that certain mathematical systems are consistent, meaning they don’t lead to contradictions. It helps us understand how much “infinity” is needed to prove these systems are reliable. For example, a famous mathematician named Gentzen used this method to show that Peano Arithmetic—a system for basic number facts—is consistent by using a special type of counting called transfinite induction.

This technique has been used to study many different mathematical theories. It can show that some theories are only possible if we assume certain infinite structures are well-organized. It also helps mathematicians classify which functions and structures can be proven within these systems.

Provability logic

Main article: Provability logic

Provability logic is a type of modal logic where the box operator means "it is provable that." It helps us understand how we can talk about proofs in a formal system. One important system is called GL, which matches what can be proven in Peano Arithmetic.

Researchers have found many interesting results using provability logic. For example, GL shows that if a contradiction cannot be proven, then it also cannot be proven that a contradiction cannot be proven. There has also been work on extending provability logic to more complex systems and using it to study how proofs relate to each other.

Reverse mathematics

Main article: Reverse mathematics

Reverse mathematics is a part of mathematical logic that studies which basic rules, or axioms, are needed to prove important math ideas. It was started by Harvey Friedman. Instead of starting with axioms and proving theorems, reverse mathematics works backward — from theorems to the axioms needed to prove them.

In this field, mathematicians begin with a basic set of rules that is too weak to prove many theorems but strong enough to talk about the ideas involved. They then find out which stronger set of rules is needed to prove each theorem. Research in reverse mathematics often uses ideas from another area called recursion theory.

Functional interpretations

Functional interpretations help us understand non-constructive theories by turning them into functional ones. This process happens in two steps. First, a classical theory is changed into an intuitionistic theory, which means finding a way to translate the ideas of the classical theory into a more structured form. Second, the intuitionistic theory is simplified further into a theory without quantifiers, focusing only on functions.

These interpretations support Hilbert's program by showing that classical theories are consistent compared to constructive ones. They also let us pull useful, constructive information from proofs. For example, they can show that certain recursive functions can be represented by simple terms. One famous method, known as the Dialectica interpretation, was developed by Kurt Gödel to connect intuitionistic arithmetic with a theory of functionals.

Formal and informal proof

Main article: Formal proof

Informal proofs are the way mathematicians usually write about their ideas. They are like rough sketches that experts can use to imagine a more detailed proof. Most mathematicians don’t write full formal proofs because they take too much time and are very detailed.

Formal proofs are like step-by-step instructions that computers can help create and check. While checking these formal proofs is easy for a computer, finding them can be very difficult. Checking informal proofs, on the other hand, often takes many weeks of careful review by other mathematicians, and sometimes errors are still found.

Proof-theoretic semantics

Main articles: Proof-theoretic semantics and Logical harmony

In language studies, special ways of thinking from proof theory help explain how we understand words and sentences. This is used in types of grammar like type-logical grammar, categorial grammar, and Montague grammar to give a clear meaning to natural language.