Löb’s Theorem

A lesser known elementary theorem in basic proof theory is Löb’s Theorem. Even though I know it and know the basic idea of a proof for it, I cannot remember where I know this from, in the logic lectures I took it wasnt mentioned iirc, and in the introducting books I have read I cant remember it, too. And actually, I never needed it so far for anything, so I forgot about it.

The Löb Theorem basically states: If PA⊧ (PA⊧A→A) then PA⊧A.

Well, in the comments of this Blogpost I found a nice illustration of the proof.

Which reminds me of an old xkcd-comic.

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: