What kind of relation is Godel talking about in Proposition V of his Incompleteness theorem?

144 Views Asked by At

Proposition V in Gödel's 1931 Incompleteness theorem is stated as follows:

For every recursive relation $ R(x_{1},...,x_{n})$ there is an n-ary "predicate" $r$ (with "free variables" $u_1,...,u_n$) such that, for all n-tuples of numbers $(x_1,...,x_n)$, we have:

$$R(x_1,...,x_n)\Longrightarrow Bew[Sb(r~_{Z(x_1)}^{u_1}\cdot\cdot\cdot~_{Z(x_n)}^{u_n})] $$

$$\overline{R}(x_1,...x_n)\Longrightarrow Bew[Neg~Sb(r~_{Z(x_1)}^{u_1}\cdot\cdot\cdot~_{Z(x_n)}^{u_n})]$$

My question is this: what are some examples of $R$ (in 1 variable)?

Could it be something as simple as...$$R(x) \Rightarrow(x = 5)$$ or $$R(x) \Rightarrow 2x$$? Or does $R$ represent something more complicated?

1

There are 1 best solutions below

0
On

It is a bit unclear as to what you mean by your $\Rightarrow$ in your examples.
If $x=5$ / $2x$ is supposed to correspond to the right-hand side of the implication in the proposition for two concrete examples, then you misunderstood what the proposition says; I will clarify this in the first half of my answer.
If your question is not what $\ldots \Longrightarrow Bew[\ldots]$ means and by the arrow notation you intend a definition of $R$ for possible examples of $R$, then see the second half of my post.


Meaning of the proposition

$R$ is a recursive relation, so if it is 1-place, it will be a property of a number. An example would be "$x$ is prime": $Prime(x)$.
$r$ is a symbol of the formal language that expresses the relation $R$: $prime(u)$.

Let's choose $x := 5$.

Then the proposition $$Prime(5)\Longrightarrow Bew[Sb(prime~_{Z(5)}^{u})] $$ states that if $5$ is prime ("$Prime(5)$"), then the formula with predicate symbol $prime$, and with the free variable $u$ substituted ("$Sb$") by the encoding ($Z$) of the number $5$ ("$x$"), is provable ("$Bew"$) in the formal system $P$.
The second half of the proposition states that if $5$ is not prime, then the negation of the formula is provable.

Note that $Bew$ is itself a predicate that expresses this provability; and the part inside the [$\ldots$] is an encoding of the desired formula (hence the cumbersome notation with $Z, Sb, Neg$).

So if your $x=5$ and $2x$ meant to refer to the right-hand side of the implication, then your interpretation of what $V$ does is not correct: It is not about assigning a concrete value to some free variable, or defining a function that performs some operation on the variable. What the theorem states is that if some relation holds, then it is provable for an adequate formula representation of the relation. The substitution merely says to replace the free variables $u_i$ of the formula by the encoding of the variables $x_i$ of the relation. The recursive definition of the relation $R$, as well as the values for the $x_i$, are already given. $V$ is about the formal representatibility of this relation.

In short, proposition $V$ states that every recursive relation is definable within the system.

Note that while, as per your request, the example here is of a 1-place relation, the proposition is proved for relations which represent recursive functions (see also below for the distinction).


Your two examples of R

1: Being equal to $5$ would indeed be a property of a number and thus a possible 1-place relation; in this case, $R$ has only one member, namely $5$: $R = \{5\}$; so $R(x)$ iff $x = 5$.
Proposition $V$ now states that for any number $x$, if $R(x)$, i.e. by your definition if $x=5$, then $P$ can prove a formula that expresses the fact that $x$ has property $R$; and if $\overline{R}(x)$, i.e. if $x \neq 5$, then $P$ can prove the negation of such a formula.

2: But your second example, "$R(x) \Rightarrow 2x$" does not work: Here you mean not a property of a number, but a function from numbers into numbers.

Remember that an $n$-place function is an $n+1$-place relation: $f(x_2, \ldots, x_n) = x_1$ can be expressed as $R(x_1, \ldots, x_n)$. This is what is exploited in Gödel's definitions.

An example from Peano arithmetic is the 1-place successor function $s$: $s(0) = 1, s(1) = 2, s(2) = 3, ...$. This can be expressed as a two-place relation $S$: $S = \{\langle 1, 0 \rangle, \langle 2, 1 \rangle, \langle 3, 2 \rangle, \ldots\}$. What proposition $V$ states is that if $S(x) = y$, i.e. if $S(y,x)$, then the formal system can prove a formula which expresses that $S(y,x)$, and otherwise its negation.

Your 1-place funtction $R(x) = 2x$ can be expressed as a 2-place relation $R = \{\langle 0, 0 \rangle, \langle 2, 1 \rangle, \langle 4, 2 \rangle, \ldots \}$.
Given that $R(2) = 2 \cdot 2 = 4$, then according to $V$, the formal system can prove some formula $r(4, 2)$, where $r$ is a predicate expressing $R$ and $4$ and $2$ are symbols of the language representing the respective numbers.
And with $R(2) \neq 3$, the correspondng formula to prove is $\neg r(3, 2)$. Again, $3$ and $2$ here are just symbols of the language which stand for the actual numbers.

Note that $Bew$ is itself a predicate that expresses this provability; and the part inside the [$\ldots$] is an encoding of the desired formula (hence the cumbersome notation with $Z, Sb, Neg$).