Gödel's Incompleteness Theorems proof

215 Views Asked by At

I am trying to understand the proof of Gödel's incompleteness theorems. I am using this document https://mat.iitm.ac.in/home/asingh/public_html/papers/goedel.pdf and finding it quite helpful, but I am a little confused about a particular part of it - on page 2, what is meant by "extend $g$ to proofs of formulas..."? What are $X_1$, $X_2$, etc.?

1

There are 1 best solutions below

0
On

$X$ is a formula, i.e. a string of symbols.

The function $g$ has been defined for "basic" symbols: $g(\top)=1, g(\bot)=2, \ldots$

Then it is extended to formulas in this way; for $X= \sigma_1 \sigma_2 \ldots \sigma_m$:

$g(X)=g(σ_1 σ_2 \ldots σ_m) = 2^{g(σ_1)} \times 3^ {g(σ_2)} \times \ldots \times p_m ^{g(σ_m)}$.

A proof, i.e. a derivation in the calculus, is a sequence of formulas: $X_1, X_2, \ldots X_n$.

Thus, $g$ can be extended again to encode proofs by:

$g(X_1 X_2 \ldots X_n) = 2^{g(X_1)} \times 3^{g(X_2)} \times \ldots \times p_n ^{g(X_m)}$.