<p>The formula $A$ is provable, this is almost exactly the content of <a href="http://en.wikipedia.org/wiki/L%C3%B6b%27s_theorem" rel="nofollow">Löb's Theorem</a>.</p>

<p>The proof (which can be found on the Wikipedia page) is a bit contorted, as it requires an additional application of diagonalization to build and analyze the formula:</p>

<p>$$ \Psi \equiv Pr(\lceil\Psi\rceil)\rightarrow A $$</p>

CC BY-SA 3.0
2013-06-05T18:55:48.267Z
2013-06-05T18:55:48.267Z
cody
<p>I am wondering whether this is the right site to ask this question, but since it involves proof and diagonalisation, hopefully it is the right place.</p>

<p>I am curious and trying to reason about what consequences we get if we use the predicate in the diagonalisation lemma as the provability predicate. I don't think I succeeded, I would appreciate if anyone could lend some help.</p>

<p>So here it is:  </p>

<blockquote>
  <p>Suppose Pr is a provability predicate for a deductively defined theory T, where T is a theory satisfying the diagonalisation lemma. Suppose A is a FIXED POINT for Pr in T, that is, that $T\vdash Pr(\ulcorner A\urcorner)\equiv A$. </p>
</blockquote>

<p><strong>My question is: What can we say about the formula A? Is it provable in the theory T? Is it refutable in the theory T? (That is, is its negation provable in T?) Could it be either provable or refutable?</strong></p>

<p>I tried to reason as follow: (To be honest I have not yet got the hang of it, I find this topic a bit confusing, so there should be many flaws in my reasoning, please kindly correct my mistakes)</p>

<p>Since $T\vdash Pr(\ulcorner A\urcorner)\equiv A$ so $T\vdash A$. In words, since T can show that $\ulcorner A\urcorner$ is provable iff $A$, so T can show A. So A is provable in T. I don't think it sounds correct, but I have no idea how to fix it.</p>

<p><strong>To grasp the concept better, I think it is easier for me to think of an example, but I am still struggling to find one. I am trying to find examples of formulas which are fixed points for Pr in the theory of Peano Arithmetic.</strong> </p>

<p>What I can think of about properties of numbers are like eveness, primeness. So suppose Pr represents there is a proof that $\ulcorner A\urcorner$ is even, and A is "I am even". Is my example correct? Again, I am really doubtful about my own example.</p>

<p>Also, if anyone has any better way to understand the topic, I would be more than happy to learn.</p>

<p>Many many thanks in advance, I really appreciate any helps.</p>

CC BY-SA 3.0
2013-06-05T15:52:31.060Z
I think this is more suitable for [math.se].
Kaveh
<lo.logic><proofs>
What can we say about a fixed point for a provability predicate in deductively defined theory that satisfies diagonalisation lemma
user71346
# What can we say about a fixed point for a provability predicate in deductively defined theory that satisfies diagonalisation lemma

(Asked by: username_0 on 2013-06-05)

I am wondering whether this is the right site to ask this question, but since it involves proof and diagonalisation, hopefully it is the right place.

I am curious and trying to reason about what consequences we get if we use the predicate in the diagonalisation lemma as the provability predicate. I don't think I succeeded, I would appreciate if anyone could lend some help.

So here it is:

> Suppose Pr is a provability predicate for a deductively defined theory T, where T is a theory satisfying the diagonalisation lemma. Suppose A is a FIXED POINT for Pr in T, that is, that $T\vdash Pr(\ulcorner A\urcorner)\equiv A$.

**My question is: What can we say about the formula A? Is it provable in the theory T? Is it refutable in the theory T? (That is, is its negation provable in T?) Could it be either provable or refutable?**

I tried to reason as follow: (To be honest I have not yet got the hang of it, I find this topic a bit confusing, so there should be many flaws in my reasoning, please kindly correct my mistakes)

Since $T\vdash Pr(\ulcorner A\urcorner)\equiv A$ so $T\vdash A$. In words, since T can show that $\ulcorner A\urcorner$ is provable iff $A$, so T can show A. So A is provable in T. I don't think it sounds correct, but I have no idea how to fix it.

**To grasp the concept better, I think it is easier for me to think of an example, but I am still struggling to find one. I am trying to find examples of formulas which are fixed points for Pr in the theory of Peano Arithmetic.**

What I can think of about properties of numbers are like eveness, primeness. So suppose Pr represents there is a proof that $\ulcorner A\urcorner$ is even, and A is "I am even". Is my example correct? Again, I am really doubtful about my own example.

Also, if anyone has any better way to understand the topic, I would be more than happy to learn.

Many many thanks in advance, I really appreciate any helps.

**Tags:** lo.logic, proofs
> **Comments:**
> **username_1**: I think this is more suitable for [math.se].  

---

## 1 answers

### Answer by username_2 on 2013-06-05. Score: 2

The formula $A$ is provable, this is almost exactly the content of [Löb's Theorem](http://en.wikipedia.org/wiki/L%C3%B6b%27s_theorem).

The proof (which can be found on the Wikipedia page) is a bit contorted, as it requires an additional application of diagonalization to build and analyze the formula:

$$ \Psi \equiv Pr(\lceil\Psi\rceil)\rightarrow A $$


---

