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:

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

Sam Marks29 Sep 2021 19:03 UTC
98 points
23 comments23 min readLW link1 review

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

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

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

Eliezer Yudkowsky24 Mar 2013 16:37 UTC
112 points
168 comments3 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
67 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
13 points
1 comment67 min readLW link

A Proof of Löb’s The­o­rem us­ing Com­putabil­ity Theory

jessicata16 Aug 2023 18:57 UTC
71 points
0 comments17 min readLW link
(unstableontology.com)

Strange Loops—Self-Refer­ence from Num­ber The­ory to AI

ojorgensen28 Sep 2022 14:10 UTC
15 points
6 comments18 min readLW link

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

Hazard28 Jun 2020 18:50 UTC
44 points
11 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
27 points
10 comments3 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
79 points
39 comments11 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

You Prov­ably Can’t Trust Yourself

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

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

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

Threat­en­ing to do the im­pos­si­ble: A solu­tion to spu­ri­ous coun­ter­fac­tu­als for func­tional de­ci­sion the­ory via proof theory

Christopher King11 Feb 2023 7:57 UTC
5 points
4 comments5 min readLW link

Pro­gram­ming AGI is impossible

Áron Ecsenyi30 May 2023 23:05 UTC
1 point
0 comments4 min readLW link

[Question] Can we get around Godel’s In­com­plete­ness the­o­rems and Tur­ing un­de­cid­able prob­lems via in­finite com­put­ers?

Noosphere8917 Apr 2023 15:14 UTC
−11 points
12 comments1 min readLW link

Mean­ingful things are those the uni­verse pos­sesses a se­man­tics for

Abhimanyu Pallavi Sudhir12 Dec 2022 16:03 UTC
16 points
14 comments14 min readLW link

A di­a­log with the ax­iom of choice

AxiomWriter30 Mar 2024 7:47 UTC
−2 points
0 comments6 min readLW link