2

In the proof, we start with a numbering of all formulas with one free variable $v$.

The formula $sub(x,x,y)$ used in the diagonal lemma says:

$y$ is the godel number of the formula obtained when the free variable $v$ in the formula whose number is $x$ is replaced by the numeral for $x$.

$sub(x,x,y)$ is a formula with the variable $x$ free and if $y$ is within the scope of a quantifier, it is the only variable free.

I am not clear about the following questions.

If $x$ is a free variable, what is the numeral for $x$? Do we take it as $S(S(S...S(0)...))$ (where the $S$'s are repeated $x$ times)?

If $y$ is the godel number of a formula ( formula $\phi(x)$ obtained by replacing the variable $v$ by the numeral for $x$ in the formula whose number is $x$) , then is $y$ a number or a function of $x$?

Mauro ALLEGRANZA
  • 94,169
Sudhir
  • 115

1 Answers1

3

Referring H.Enderton, A Mathematical Introduction to Logic (2nd ed - 2001), we must start with the general definition of the function $Sb(v_1,v_2,v_3)$ [pag.228].

The definition is :

let $T$ a system for arithmetic [e.g.first-order Peano Arithmetic or Robinson Arithmetic : they must contain the symbols $0$ (individual constant denoting the number zero) and $S$ (1-ary functional constant denoting the successor function)];

let $n$ the Godel-number of a (term or a) formula $\alpha$;

let $m$ the G-number of a variable $x_i$;

let $k$ the G-number of a term $t$;

then $Sb(n,m,k)$ is the G-number of the resulting expression obtained replacing with the term $t$ all the free occurences of $x_i$ into $\alpha$ (i.e.$\alpha(t/x_i)$).

Question 1) : If x is a free variable, what is the numeral for x?

You must start with the coding of all symbols of the language; then you encode all terms, starting with xariables : for example, the G-number of $x_i$ will be : $g(x_i) = 9+2i$.

Remember ! in the formal treatment the variables are ordered; you are using $x$, $y$, $z$ as meta-language variables standing for the variables of the object-language, that are : $x_1$, $x_2$, $x_3$, ...

Applying the definition, we can compute the G-number for $x_1$; it is $11$.

Same for the terms ; terms are expressions like : $S(S(S(0))$ or $S(x+S(0))$, and following the "build-up" of the term the encoding rules will produce univocally a G-number. Numerals are terms : 11 is a term (it is $S(S...S(0)...)$ i.e. $S$ 11-times $0$) and it is the name in formal arithmetic of the number $11$.

So , in the encoding of a (formal) expression, it is perfectly known which variable you are replacing with a (perfectly known) term.

Question 2) : If $y$ is the G-number of a formula, then is $y$ a number or a function of $v$ (where $v$ is the G-number of a variable $x_i$) ?

$v$ is a number; when you replace the (free occurrences of the) variable $x_i$ into formula $\alpha$ with a term $t$ you get a new expression : $\alpha(t/x_i)$. You must replace $x_i$ in $\alpha$ with the numeral "naming" the G-number of $t$, and you will get a new formula.

Applying again the encoding rules to the resulting expression, you will compute a new G-number : the value of $Sb(y,v,u)$.

Another basic concept is "representability" (seee pag.205-on) :

The formula $\rho$ (with one free variable) represents in T a 1-ary relation $R$ on $\mathbb N$ iff for every $a$ in $\mathbb N$ :

$a \in R \Rightarrow \vdash _T \rho(S^a(0))$, i.e. the (closed) formula obtained from $\rho(x)$ substituing in place of $x$ the numeral "naming" the number $a$ is provable in $T$, and

$a \notin R \Rightarrow \vdash_T \lnot \rho(S^a(0))$.

A very simple example of relation representable in $T$ is the equality relation in $\mathbb N$ (pag.206) : use the formula $x_1 = x_2$.

You can extend this notion also to functions (see pag.212), saying that a formula $\phi$ (with $m+1$ free variables) functionally represent a function $f$ (with $m$ arguments). The basic result is (pag.214-on) that a lot of useful functions and relations are representable in $T$.

All this result converges in the arithmetization of syntax (pag.224-on), where you can prove that the functions and relations involved with G-numbers are representable in the formal system $T$.

At page.228, item 5, you have that $Sb(y,u,v)$ is representable.

The "trick" of Fixed-Point Lemma (pag.235) is to exploit the above facts.

$\theta$ is a formula of the system $T$ : it does not represents $Sb$, but it is very "tightly" linked to $Sb$.

The formula $\theta(v_1,v_2,v_3)$ functionally represents the function that, given as arguments the G-number of a formula (with only the free variable $x$) $\alpha$ and the number $n$ (they are both numbers !), returns as ouput the G-number of $\alpha(x/S^n(0))$ (i.e. the closed formula obtaind replacing $x$ with the numeral "naming" $n$).

Call it $Sb_1$ : it is like $Sb$ but without the reference to the free variable (there is only one). The formula $\theta$ is defined as :

$\theta(x,y,z)$ is true iff $Sb_1(x,y)=z$.

In the prof of the Lemma we will use the formula $\theta$ that "speaks of" formulae of the system itself through their G-numbers.

Added Dec,23

Question 3) : The formula with godel number $v_1$ is a formula with 2 free variables, namely $x$ and $v_1$? And once we substitute (the numeral for) $v_1$ for $x$, we are left with a formula with $v_1$ as free variable and take the godel number of this formula? Or we first substitute a number for $v_1$ in $\theta$ , find the corresponding formula and substitute?

First, in order to avoid confusion, we will use only $v_1, v_2, ...$ as free variables in formulae. We will use $n, m, k, ...$ as numbers and $S^n(0), ...$ as numerals (i.e.closed term "naming" numbers).

At pag.235, you have the formula (1) : $\forall v_3 [\theta (v_1,v_1,v_3) \rightarrow \beta(v_3)]$.

This is a formula with only one free variable : $v_1$. It is a formula of the language; so you can compute its own G-number : say $q$ (if you review the encoding rules, you can check that G-numbers for variables cannot be equal to G-numbers for formulae).

Then put the numeral $S^q(0)$ in place of the free variable $v_1$ into (1) and you will get a closed formula : $\sigma$.

This new formula has a new G-number, different from $q$.

Community
  • 1
Mauro ALLEGRANZA
  • 94,169
  • I am not sure if we are using sub in the same sense. I was using it in the sense given in Enderton where sub(x,x,y)is a formula. The way you are using it, sub would be a number.in the sense I used, the desired self referential sentence is ∀y{sub(u,u,y)->psi y}, where u is the godel number for ∀y{sub(x,x,y)->psi y} – Sudhir Dec 21 '13 at 18:27
  • Ok, thanks. I'll re-edit the answer using Enderton. – Mauro ALLEGRANZA Dec 21 '13 at 19:52
  • Please, can you give me the page where the $sub(x,y,z)$ formula is used ? – Mauro ALLEGRANZA Dec 21 '13 at 20:10
  • Take in account that in the proof of Godel's Th using arithmetization of syntax you need the feature of PA (or Robinson Arithmetic) that they are capable of "representing" primitive recursive functions (like Sb), i.e. for a p.r. function $f$ you can find a formula $F$ such that : if $f(m)=n$ then $PA \vdash F(m,n)$ and if not $f(m)=n$ then not $PA \vdash F(m,n)$. – Mauro ALLEGRANZA Dec 21 '13 at 21:06
  • My apologies for the delay in responding. Actually, the formula I was referring to is Equation (1) onpage 235, in the proof of fixed point lemma. My use of sub was inaccurate ( possibly from Kozen' s book on Automata);the formula in Enderton is theta( v1,v2,v3). – Sudhir Dec 22 '13 at 04:38
  • I will try to expand again the answer. – Mauro ALLEGRANZA Dec 22 '13 at 08:20
  • I understand that theta(17,17,z) means that z is the number of the formula obtained when in the formu – Sudhir Dec 22 '13 at 17:49
  • There are two possible ways of interpreting theta(v1,v1,z).One is I take it that z is represented in closed form z=godelnumber of f(v1).For example, we can say z is godel number of v1+SS0, in which case it makes no sense to speak of z as a function of variable v. The other view is to take theta(v1,v1,z) as a mere shorthand for the many formulae theta(1,1,z),theta(2,2,z) and so on.In that case to say that theta( v1,v1,z) is a single formula that kind of encompasses all these many formulae seems to kind of mix these two views. – Sudhir Dec 22 '13 at 18:24
  • Please ignore the last but one comment. Could not edit it ine time. If we have a formula z = v+S0, then v is free in it. But if we say z=godel number of v+S0, then v is no longer free.The formula simply reduces to z= some constant. So in theta(v1,v1,z) which is equivalent to "z is the godel number of formula obtained by substituting numeral for v1 in formula whose number is v1" is v1 free ?or the formula theta is simply equivalent to z= some constant? – Sudhir Dec 22 '13 at 18:55
  • I think you are mixing two things. Start with a formula with a free variable; start with a very simple one : $x_1=S(0)$. Call it $\alpha(x_1)$. Do the exercise of computing (using the coding of Enderton's textbook) his G-number : call it $w$. Suppose that $w$ is $5$ (it surely will be greater !). Then you must substitute the numeral 5 (i.e. $S(S(S(S(S(0)))))$ in $\alpha$ in place of $x_1$ : you will obtain a new (closed) formula : $S(S(S(S(S(0)))))=S(0)$. Then compute the new G-number : say $z$. The formula $\theta(w,5,z)$ is true. – Mauro ALLEGRANZA Dec 22 '13 at 20:00
  • w is 5, so are we saying theta(5,5,z) is true ? If not ,what is theta(w,5,z)? – Sudhir Dec 22 '13 at 20:20
  • $\theta$ is NOT a function; is a formula with three argument places. So, if <5,5,z> satisfy it, we have that $\theta(5,5,z)$ is true; otherwise it is false. Think to a formula $\alpha(x_1,x_2)$ (say : $x_1=x_2$) as a relation between numbers : for some couples of numbers (<0,0>, <1,1>, ...) it is true; for others (<0,1>, <1,0>, ...) it is false. – Mauro ALLEGRANZA Dec 22 '13 at 20:35
  • There is some point that I am missing altogether. If G number of x1=S0 is 5,then theta (5,5,z) is true. theta (x1,x1,z) is true is equivalent to " z = Godel number of some function of x1".Godel number of any function of x1 is just some number,so theta(x1,x1,z) is equivalent to "z=some number".There is no x1 free in it and so in theta(x1,x1,z).So theta (3,3,z) is Not obtained by simply substituting 3 for x1 in theta (x1,x1,z).i hope the above explains the point which is confusing me and for which I will appreciate a clarification. – Sudhir Dec 23 '13 at 04:07
  • maybe it will be more precise to say that theta(x1,x1,z) is equivalent to " z = godel number of some term containing x1".But godel number of any term containing x1 is just some number. – Sudhir Dec 23 '13 at 04:24
  • At pag.235, you have the formula (1) : $\forall v_3 [\theta(v_1,v_1,v_3) \rightarrow \beta(v_3)]$. This is a formula with only one free variable : $v_1$. It is a formula of the language; so you can compute its own G-Number : say $q$. Then put the numeral $S^q(0)$ in place of the free variable $v_1$ into (1) and you will get a closed formula : $\sigma$. – Mauro ALLEGRANZA Dec 23 '13 at 08:01
  • Theta(v1,v1,v3)<-> v3 = godel number of 'formula containing variable v1'. but godel number of 'formula containing variable v1' is just some number, say 100. So, theta(v1,v1,v3)<->v3=100.in the L.H.S of the equivalence, v1 is free, but not in the R.H.S.I am looking for a clarification on this;where is the mistake in the above? – Sudhir Dec 23 '13 at 08:54
  • No. Do not mix the free variables used as argument places in the definition of $\theta(v_1,v_1,v_3)$ with the free variable (say : $x$) in $\alpha$. $\theta(v_1,v_1,v_3)$ is true iff $v_3$ is the new G-number of the result of replacing into a formula $\alpha$ (with a free variable $x$), having G-number $n$, the numeral $S^n(0)$ in place of $x$. – Mauro ALLEGRANZA Dec 23 '13 at 09:13
  • "Formula with godel number v1" - is it a formula with 2 free variables namely x and v1? And once we substitute (the numeral for) v1 for x, we are left with a formula with v1 as free variable and take the godel number of this formula? Or we first substitute a number for v1 in theta ,find the corresponding formula and substitute? – Sudhir Dec 23 '13 at 15:28
  • For example, consider a numbering as below: Formula 1----x+1=0; formula 2---x+2=0 ; formula 3. ----x+3=0 and so on.Then the formula with code v1 is x+v1=0.Now we substitute the numeral for v1 in x+v1=0 to get a formula in which v1 is free.then we take the code of this formula. – Sudhir Dec 23 '13 at 15:42
  • It is hard, using only comments, to write down the formulae correctly. If $v_1$ is a variable in the formula $\alpha$ it is NOT a number: a variable is a syntactic object, while a number is ... a number. Only computing the G-number of $\alpha$ you will get a number $n$ (please, don't call it as a variable) and then you will substitute the numeral $S^n(0)$ (that is a term, i.e.another syntactic objcet) into the formula. You must be careful in distinguishing between numbers (when you in the meta-theory compute the G-numbers) and numerals (when you use them in formulae of the formal theory). – Mauro ALLEGRANZA Dec 23 '13 at 16:10
  • So there is nothing like a formula {psi(x,v)with two free variables}with godel number v? "A formula with godel number v" is non denoting?but theta(v,v,v3) is equivalent to " v3 is the godel number when ' In the formula with godel number v' , the free variable etc etc". – Sudhir Dec 23 '13 at 16:40
  • I have used too many comments already, but this is one I cannot resist the temptation.Using Enderton's notation, Godel number G of v1= 11. Writing this as G(v1)=11, we see that v1 is not a free variable in the L.H.S.So,if a variable is within the scope of the godel numbering function, it is not free.In theta(v1,v1,v3), v1 is within the scope of a godel numbering function.So, can we take it as a free variable? – Sudhir Dec 24 '13 at 03:41
  • $\theta$ is NOT a "Godel numbering" function ! In general, it is a formula in formal number theory that express a relation between numbers. When its arguments are instantiated with values that are suitably chosen (i.e. Godel numbers of ...) it is true. Merry Christmas ! – Mauro ALLEGRANZA Dec 24 '13 at 10:07
  • Not theta,yes. But theta(v1,,v1,,v3)<->v3 = godel number of " the formula obtained by substituting for the free variable the numeral for v1 in the formula whose number is v1".So v1 within the argument of a godel numbering function in theR.H.S. Merry Christmas to you all too! – Sudhir Dec 24 '13 at 13:09
  • I think you are making again the same mistake. You are using $v_1$ both as a variable [i.e. a "placeholder" in a formula to be filled with a term (i.e. a "name" for an object: in number theory a numeral "naming" a number)] and as a number. If $n$ is the G-number of a formula, when you "fill" with the corresponding numeral (i.e.$S^n(0)$) the argument-place in $\theta$, you will have nor more the "placeholder" $v_1$. – Mauro ALLEGRANZA Dec 24 '13 at 14:00
  • The issue is clearer to me and I am perhaps a lot less confused. Thanks! – Sudhir Dec 24 '13 at 17:52
  • @Sudhir -- If you have still some doubts, please read carefully pag.185 of Enderton. There you can find the passages from a formula $\rho(v_1,v_2,v_3)$ with three argument-places, to a formula with two arg-places: $\forall v_3 \rho(v_1,v_2,v_3)$, and last to a formula with only one arg-places : $\forall v_3 \rho(v_1,v_1,v_3)$. This last passage is the same as in number theory, changing from $x+y=4$, i.e.an eqaution where you can choose $x$ and $y$ independently, to $x+x=4$. – Mauro ALLEGRANZA Jan 02 '14 at 17:08