1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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