Proof theory

Math can be like a puzzle. We use steps to show a truth. We write these steps down. It is like a long list.

These lists help us think. They help us check our work. We can see if it is right. We can even use them in computers.

Some people study how these lists work. They look at the rules for the steps. This helps them find new ways to solve things.

One man named David Hilbert had a big plan. He wanted to make sure all math was solid. Later, Kurt Gödel showed us math is even more complex.

Math is full of wonder. It helps us understand the world.

Math is full of patterns and rules. Proof theory is a special way to study these rules. It treats a proof like a real object. You can look at a proof as a list or a tree. This helps people study how proofs are built.

Long ago, David Hilbert had a big plan. He wanted to prove that math was always solid. He wanted to show that math would never lead to a mistake. But a man named Kurt Gödel changed this idea. He showed that some math truths cannot be proven by their own rules. This means math is even deeper than we thought.

Other experts study how proofs work. Gerhard Gentzen made new ways to write proofs. He used things called natural deduction and sequent calculus. These are sets of steps to find truths. Some people also use math to work backward. This is called reverse mathematics. It asks which rules we need to prove a certain fact. It is like working from the answer back to the start.

Proof theory is a major part of mathematical logic. It is one of four main areas in that field. Other areas include model theory, axiomatic set theory, and recursion theory. In proof theory, we treat a proof as a real mathematical object. We do not just look at the truth of a statement. Instead, we look at the structure of the proof itself. Proofs are often seen as data structures. They can look like lists or trees. These structures follow specific rules and axioms. This way, we can use math to study math.

This field works by looking at the syntax of logic. Syntax is the way symbols and rules are put together. This is different from model theory, which is semantic. Semantic study looks at what the symbols actually mean. Proof theory focuses on the formal steps taken to reach a conclusion. One way to study this is through structural proof theory. This branch looks at different styles of proof calculi. These are sets of rules used to build proofs. Three famous styles are Hilbert calculi, natural deduction, and sequent calculi.

Many famous thinkers helped build this field. David Hilbert started a famous program to find the foundations of math. He wanted to show that math was always consistent. He hoped to prove that math would never lead to a mistake. However, Kurt Gödel changed this idea with his incompleteness theorems. He showed that some math truths cannot be proven by their own rules. This discovery led to new ways of thinking. Researchers like J. Barkley Rosser and Alan Turing also made big contributions. They helped us understand how math systems work and how they talk about themselves.

Other experts created new ways to organize logical steps. In 1926, Jan Łukasiewicz suggested a new way to draw conclusions. Later, Stanisław Jaśkowski and Gerhard Gentzen created systems called natural deduction. Gentzen also created the sequent calculus in 1934. His work introduced the idea of analytic proof. This means the proof uses parts that are already in the statement. Gentzen even used these tools to prove the consistency of Peano arithmetic. This was a very important step for the field.

We can also use math to work in a new direction. This is called reverse mathematics. It was founded by Harvey Friedman. Most math goes from rules to answers. Reverse mathematics goes from the answer back to the rules. It asks which specific axioms are needed to prove a theorem. Scientists start with a base system that is quite weak. They then find the exact strength needed to reach a goal. This helps us see how different mathematical ideas are linked together.

Proof theory is a major branch of mathematical logic. It is one of four primary domains in the field. The other three domains are model theory, axiomatic set theory, and recursion theory. In proof theory, mathematicians treat proofs as formal mathematical objects. This allows researchers to use mathematical techniques to analyze the structure of proofs themselves. Proofs are typically represented as inductively defined data structures. These structures might appear as lists, boxed lists, or trees. They are constructed using the specific axioms and rules of inference of a logical system. Because it focuses on these formal structures, proof theory is considered syntactic in nature. This distinguishes it from model theory, which is semantic in nature.

Structural proof theory is a key subdiscipline that studies different proof calculi. A calculus is a set of rules used to build proofs. There are three well-known styles of proof calculi. These are Hilbert calculi, natural deduction calculi, and sequent calculi. Most logical systems can be represented by one of these styles. Proof theorists often look for calculi that support analytic proofs. An analytic proof is one where the proof relies on the components of the statement itself. Gerhard Gentzen introduced this idea through the sequent calculus. In a sequent calculus, analytic proofs are described as being cut-free. This means every formula in the final result is a subformula of the original premises. This property makes it easier to prove that a system is consistent.

Another important area is ordinal analysis. This technique provides consistency proofs for subsystems of arithmetic, analysis, and set theory. It is used to measure the infinitary content of a theory's consistency. For a consistent theory, one can prove its consistency in finitistic arithmetic if a certain transfinite ordinal is well-founded. This work was pioneered by Gerhard Gentzen. He used transfinite induction up to the ordinal epsilon-zero to prove the consistency of Peano arithmetic. Ordinal analysis has since been extended to many fragments of second-order arithmetic. It remains a powerful tool for understanding the strength of different mathematical systems.

The history of modern proof theory is closely tied to Hilbert's program. David Hilbert initiated this program to find the foundations of mathematics. His goal was to provide finitary proofs of consistency for all formal theories. He believed this would ground mathematics through a metamathematical argument. This would show that all provable sentences are finitarily true. However, the program faced a major challenge from Kurt Gödel. His incompleteness theorems showed that a sufficiently strong theory cannot prove its own consistency. This result changed the direction of the field. Instead of failing, the program evolved into modified versions and new research areas.

Following Gödel, several researchers refined these ideas. J. Barkley Rosser refined Gödel's results by weakening the requirement of omega-consistency to simple consistency. Alan Turing and Solomon Feferman worked on the transfinite iteration of theories. Other scientists discovered self-verifying theories. These are systems strong enough to discuss themselves but too weak to use the diagonal argument used by Gödel. These developments show how the field moved from seeking a single foundation to exploring the complex boundaries of what different systems can prove.

Provability logic is another specialized branch of the field. It is a modal logic where the box operator represents the idea that something is provable. This allows researchers to capture the notion of a proof predicate within a formal theory. The logic GL, or Gödel-Löb, captures provability in Peano arithmetic. Robert Solovay proved that the logic GL is complete with respect to Peano arithmetic. This means that propositional reasoning about provability in that system is both complete and decidable. This branch helps us understand how different theories interact with the concept of provability.

Finally, reverse mathematics offers a unique way to look at mathematical truths. Founded by Harvey Friedman, this program asks which axioms are required to prove specific theorems. While ordinary math moves from axioms to theorems, reverse mathematics goes backward. It starts with a base theory that is too weak to prove most theorems. Researchers then find the exact axiom system needed to reach a specific mathematical goal. To prove a system is necessary, they must perform a reversal. This shows that the theorem itself implies the axiom. This process reveals the deep connections between different mathematical ideas.