RSS

Gödelian Logic

TagLast edit: 21 Dec 2021 8:54 UTC by Yoav Ravid

Gödelian Logic refers to logic, math, and arguments in the style of Kurt Gödel. Specifically—his two incompleteness theorems, and one completeness theorem. Due to their tricky and subtle nature, his incompleteness theorems are possibly the most misunderstood theorems of all time.

“All the limitative theorems of metamathematics and the theory of computation suggest that once the ability to represent your own structure has reached a certain critical point, that is the kiss of death: it guarantees that you can never represent yourself totally. Gödel’s Incompleteness Theorem, Church’s Undecidability Theorem, Turing’s Halting Theorem, Tarski’s Truth Theorem — all have the flavour of some ancient fairy tale which warns you that “To seek self-knowledge is to embark on a journey which … will always be incomplete, cannot be charted on any map, will never halt, cannot be described.”—Douglas Hofstadter, Gödel, Escher, Bach

Gödel’s Completeness Theorem

This theorem is less well known than the other two, which came after it, but also less misunderstood.

Gödel’s First Incompleteness Theorem

Gödel’s Second Incompleteness Theorem

Probabilistic Solutions

One way you might think to get around Gödel’s Incompleteness, is to leave behind logical certainty, and instead assign probabilities to logical statements.

External Resources:

Godel’s Com­plete­ness and In­com­plete­ness Theorems

Eliezer Yudkowsky25 Dec 2012 1:16 UTC
60 points
87 comments11 min readLW link

[Book re­view] Gödel, Escher, Bach: an in-depth explainer

Sam Marks29 Sep 2021 19:03 UTC
87 points
20 comments23 min readLW link

Reflec­tion in Prob­a­bil­is­tic Logic

Eliezer Yudkowsky24 Mar 2013 16:37 UTC
108 points
172 comments3 min readLW link

Gödel’s Le­gacy: A game with­out end

Hazard28 Jun 2020 18:50 UTC
39 points
10 comments12 min readLW link

Gödel In­com­plete­ness: For Dummies

jollybard12 Jul 2020 9:13 UTC
9 points
6 comments3 min readLW link

[Question] Godel in sec­ond-or­der logic?

Abhimanyu Pallavi Sudhir26 Jul 2020 7:16 UTC
6 points
4 comments1 min readLW link

Gödel and Bayes: quick question

hairyfigment14 Apr 2011 6:12 UTC
2 points
36 comments1 min readLW link

Ex­plained: Gödel’s the­o­rem and the Banach-Tarski Paradox

XiXiDu6 Jan 2012 17:23 UTC
16 points
40 comments2 min readLW link

Bounded ver­sions of Gödel’s and Löb’s theorems

cousin_it27 Jun 2012 18:28 UTC
52 points
22 comments2 min readLW link

A dis­carded re­view of ‘Godel, Escher Bach: an Eter­nal Golden Braid’

lukeprog16 Dec 2011 5:51 UTC
12 points
30 comments4 min readLW link

For­mal­is­ing cousin_it’s bounded ver­sions of Gödel’s theorem

Stuart_Armstrong29 Jun 2012 23:24 UTC
17 points
4 comments4 min readLW link

MIRI course list book re­views, part 1: Gödel, Escher, Bach

So8res1 Sep 2013 17:40 UTC
26 points
10 comments3 min readLW link

We won’t be able to recog­nise the hu­man Gödel sentence

Stuart_Armstrong5 Oct 2012 14:46 UTC
11 points
33 comments1 min readLW link

Com­plete­ness, in­com­plete­ness, and what it all means: first ver­sus sec­ond or­der logic

Stuart_Armstrong16 Jan 2012 17:38 UTC
78 points
39 comments11 min readLW link

You Prov­ably Can’t Trust Yourself

Eliezer Yudkowsky19 Aug 2008 20:35 UTC
29 points
18 comments6 min readLW link

Clar­ifi­ca­tion of AI Reflec­tion Problem

paulfchristiano10 Dec 2011 22:30 UTC
32 points
9 comments7 min readLW link

[Question] What’s go­ing on with “prov­abil­ity”?

Sunny from QAD13 Oct 2019 3:59 UTC
23 points
22 comments1 min readLW link

Se­cond-Order Logic: The Controversy

Eliezer Yudkowsky4 Jan 2013 19:51 UTC
47 points
192 comments15 min readLW link

Un­der­stand­ing Gödel’s In­com­plete­ness Theorem

Rafael Harth6 Apr 2022 19:31 UTC
12 points
1 comment20 min readLW link