I'm reading a set of lecture notes in which $Proof(u,v)$ is taken to represent the relation on natural numbers $u,v$ that $u$ is the encoding of a proof terminating in the sentence with godel number $v$. I.e. if this relation holds for numbers $m,n$ which have numerals in the language $\underline{m}, \underline{n}$, and we call the theory $T$, then $T\vdash Proof(\underline{m},\underline{n})$, and if the relation does not hold for these numbers then $T\vdash \neg Proof(\underline{m}, \underline{n})$.

We define $Proof^*(y,x)=Proof(y,x)\land \forall z<y[\neg Proof(z,neg(x))]$ where $neg(x)$ is the godel number of the negation of the sentence with number $x$. The author then writes

Note that if $T$ is consistent and $Proof(y,x)$ represents in $T$ the proof-in-$T$ relation (which is our background assumption), then $Proof^*(y,x)$ represents in $T$ the proof relation of $T$. That is:

$$n \text{ is a proof of } \sigma \Rightarrow T\vdash Proof^*(\underline{n},\ulcorner \sigma\urcorner) \\ n \text{ is not a proof of } \sigma \Rightarrow T\vdash \neg Proof^*(\underline{n}, \ulcorner\sigma\urcorner) $$

I can see that $Proof^*(y,x)$ claims that $y$ is a proof of $x$ and there is no shorter proof of $x$'s negation. However, I don't understand the author's characterization of this. I'm not seeing what the distinction is between a proof-in-$T$ relation and a proof relation of $T$. Can anyone explain?

up vote 1 down vote accepted

The relation $Proof(u,v)$ is a binary relation on natural numbers, whereas the probability relation for $T$ is a relation on formulae.

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.