6
$\begingroup$

I am seeking some assistance on a Mathematics/logic problem which I am having trouble with.

My problem is understanding how a number is calculated in a book called Gödel's Proof (about Kurt Gödel's Incompleteness Theorems)...page 97. Basically, the problem is regards to the (G) formula, whose meta-mathematical statement refers to itself as being not 'demonstrable'.

My problem is that I can't work out how Gödel number (g) could be sub (n, 17, n):

(1) ~ (∃x) Dem (x, Sub (y, 17, y)) Gödel number = n

(G) ~ (∃x) Dem (x, Sub (n, 17, n)) Gödel number (g) = sub (n, 17, n)

(G) is derived from (1), due to specialization of the 'y' variable - replacing y with the Gödel number for (1), which is n.

The sub (n, 17, n) function is really a shorthand for a formula of a formal system (which has the Gödel number 'n'), where any instance of the variable which has the Gödel number '17' (say 'y') is replaced by the Gödel number for 'n' itself.....kind of self-swallowing. I assume that a fellow reader of the book could put it all in context, someone with stronger mathematical/logic ability than my own.

The way I interpret the formula (G) is that it states that (1) is not a theorem (although it is as there world be a number x that fits the criteria), and since (G) is a specialization of (1), I can see how it would be a reference to 'itself', however, I cannot workout how (G)'s Gödel number would be sub (n, 17, n).

I would like to understand more clearly how the number sub (n, 17, n) could be the Gödel number for the formula (G). This is the only difficulty I have with the book..just want to understand the nuts and bolts of (G).

I would be immensely grateful for any help with this and thank you for reading my post.

enter image description here

I've drawn up this table to illustrate my interpretation of (G).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

I don't have the book in front of me right now, so the following may not exactly match what it says, but it should be close enough to give you the right idea. The function sub is defined so that, if $a$ is the Gödel number of a formula $\alpha$, if $b$ is the Gödel number of a variable $v$, and if $c$ is any natural number, then $\text{sub}(a,b,c)$ is the Gödel number of the formula obtained by substituting the numeral for $c$ in place of the variable $v$ in the formula $\alpha$. So, in the case at hand, since $n$ is the Gödel number of formula (1) and 17 is the Gödel number of the variable $y$, $\text{sub}(n,17,n)$ is the Gödel number of the formula you get by substituting the numeral for $n$ in place of $y$ in (1). But the result of that substitution is (G), so $\text{sub}(n,17,n)$ is the Gödel number of (G).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for your reply....may I please ask one more quick question? "Was my meta-mathematical interpretation of (G), given above correct? "The way I interpret the formula (G) is that it states that (1) is not a theorem (although it is as there would be a number x that fits the criteria), and since (G) is a specialization of (1), I can see how it would be a reference to 'itself')". $\endgroup$
    – Thomas Farkas
    Commented Sep 19, 2013 at 22:03
  • $\begingroup$ @ThomasFarkas No, the metamathematical interpretation of (G) says simply that (G) itself is not a theorem. $\endgroup$
    – Andreas Blass
    Commented Sep 20, 2013 at 13:01
  • 1
    $\begingroup$ Thank you, again...that chimes with what it says in the book, so I cannot expand on (G)'s meaning, as it refers specifically to itself and does not point to another formula (although it refers to g, its Godel number). I'm very grateful for your time in answering my question, its my first post on this website, and I am definitely encouraged to return. $\endgroup$
    – Thomas Farkas
    Commented Sep 20, 2013 at 13:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .