Mathematical Logic and Gödel's Incompleteness Theorems

Mathematics prides itself on certainty: once a theorem is proved, it stays proved forever. Early in the twentieth century, many mathematicians hoped to go further and show that every true mathematical statement could, in principle, be proved by mechanical rules. In 1931 a logician in Vienna, still only in his mid-twenties, showed that this dream was impossible. To understand what Kurt Gödel discovered, we first need the basic tools of mathematical logic.

Propositions and Connectives

A proposition is a statement that is either true or false, such as "7 is prime" (true) or "\( 2 + 2 = 5 \)" (false). Logic builds complex statements from simple ones using connectives:

• Negation \( \neg p \): "not \( p \)"
• Conjunction \( p \land q \): "\( p \) and \( q \)"
• Disjunction \( p \lor q \): "\( p \) or \( q \)" (or both)
• Implication \( p \to q \): "if \( p \) then \( q \)"
• Biconditional \( p \leftrightarrow q \): "\( p \) if and only if \( q \)"

The implication causes the most confusion. The statement \( p \to q \) is false only when \( p \) is true and \( q \) is false. "If it rains, the ground is wet" is not broken by a dry, sunny day; it is broken only by rain falling on dry ground.

Worked Example 1: The Contrapositive

Show that \( p \to q \) is logically equivalent to its contrapositive \( \neg q \to \neg p \).

We check every combination of truth values. T means true, F means false.

Row by row: in row 2, \( p \) is true and \( q \) is false, so \( p \to q \) is false. For the contrapositive, \( \neg q \) is true and \( \neg p \) is false, so \( \neg q \to \neg p \) is also false. In every other row, both implications have a false hypothesis or a true conclusion, so both are true.

The two columns match in all four rows, so the statements are equivalent. This is why proof by contrapositive works: to prove "if \( n^2 \) is even then \( n \) is even", it is enough to prove "if \( n \) is odd then \( n^2 \) is odd", which is easy since \( (2k+1)^2 = 2(2k^2 + 2k) + 1 \).

Note that the converse \( q \to p \) is not equivalent: "if it is a square, it is a rectangle" is true, but "if it is a rectangle, it is a square" is false.

Formal Systems and Hilbert's Programme

A formal system consists of a precise symbolic language, a set of axioms, and rules of inference (such as modus ponens: from \( p \) and \( p \to q \), deduce \( q \)). A proof is a finite chain of statements, each an axiom or obtained from earlier lines by a rule. Checking a proof requires no insight, just careful symbol matching, so in principle a machine could do it.

In the 1920s the great German mathematician David Hilbert proposed a programme: find a formal system for all of mathematics that is

• consistent, never proving both a statement and its negation, and
• complete, able to prove or disprove every statement in its language,

and prove its consistency using only simple, finite reasoning. Hilbert famously declared, "We must know, we will know."

Gödel's Bombshell

Kurt Gödel was born in 1906 in Brünn (now Brno, Czech Republic) and studied at the University of Vienna. In 1931 he published a paper showing that Hilbert's goals could not all be met.

First Incompleteness Theorem: any consistent formal system powerful enough to express basic arithmetic contains statements that are true but cannot be proved within the system.

Second Incompleteness Theorem: such a system cannot prove its own consistency.

The key idea is a sentence \( G \) that effectively says, "This statement cannot be proved in this system." If the system proved \( G \), it would prove something false, contradicting consistency. So \( G \) is unprovable, which is exactly what \( G \) asserts, so \( G \) is true. Gödel had found a true but unprovable statement.

Worked Example 2: Gödel Numbering

How can a statement about arithmetic talk about proofs? Gödel's trick was to turn every formula into a single natural number, so statements about formulas become statements about numbers.

Give each symbol a code. Using codes similar to standard textbook presentations, let the symbol "0" have code 6 and "=" have code 5. To encode a string of symbols, raise successive primes 2, 3, 5, 7, ... to the power of each symbol's code and multiply.

Encode the formula "0 = 0":

• First symbol "0" (code 6) gives \( 2^6 \).
• Second symbol "=" (code 5) gives \( 3^5 \).
• Third symbol "0" (code 6) gives \( 5^6 \).

$$ 2^6 \times 3^5 \times 5^6 = 64 \times 243 \times 15625 $$

Calculate step by step: \( 64 \times 243 = 15552 \), then \( 15552 \times 15625 = 243\,000\,000 \).

So the Gödel number of "0 = 0" is 243,000,000.

Decoding: because prime factorisation is unique (the Fundamental Theorem of Arithmetic), we can recover the formula. Factorising 243,000,000 gives \( 2^6 \cdot 3^5 \cdot 5^6 \), and the exponents 6, 5, 6 spell out "0 = 0" again.

A whole proof, being a sequence of formulas, can be encoded the same way. "Formula \( x \) is provable" then becomes an arithmetic property of the number \( x \), and Gödel could construct a formula that refers to its own number.

What Incompleteness Does and Does Not Mean

Incompleteness does not say mathematics is broken or that "anything goes". It says no single fixed set of axioms can capture every arithmetic truth. Adding \( G \) as a new axiom simply produces a new system with its own unprovable sentence.

Concrete examples followed. In 1977 Jeff Paris and Leo Harrington found a natural combinatorial statement, true but unprovable in standard Peano arithmetic, and Goodstein's theorem (1944) was later shown to be another. In set theory, the continuum hypothesis is independent of ZFC.

Gödel's ideas also influenced computer science. In 1936 Alan Turing proved that no algorithm can decide whether every program will halt, a close cousin of incompleteness.

Did You Know?

• Gödel later worked at the Institute for Advanced Study in Princeton, where he became close friends with Albert Einstein; the two often walked home together.
• John von Neumann, on hearing Gödel's first theorem in 1930, independently realised the second theorem, but Gödel had already proved it.
• Gödel also found solutions to Einstein's equations of general relativity that allow paths looping back in time.

Key Takeaways

• Logic studies propositions joined by connectives; truth tables test equivalence, such as an implication and its contrapositive.
• A formal system has axioms and rules of inference, and proofs can be checked mechanically.
• Gödel's first theorem: consistent systems containing arithmetic have true but unprovable statements.
• Gödel's second theorem: such systems cannot prove their own consistency.
• Gödel numbering turns formulas into numbers using unique prime factorisation.

Need help with logic, proofs or discrete mathematics assignments? Amathify's experts and PhD scholars provide step-by-step solutions via WhatsApp or the Ask a Question form.