RSS

Gödelian Logic

TagLast edit: Dec 21, 2021, 8:54 AM 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 MarksSep 29, 2021, 7:03 PM
101 points
23 comments23 min readLW link1 review

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

Eliezer YudkowskyDec 25, 2012, 1:16 AM
80 points
87 comments11 min readLW link

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

Eliezer YudkowskyMar 24, 2013, 4:37 PM
112 points
168 comments3 min readLW link

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

jessicataAug 16, 2023, 6:57 PM
76 points
0 comments17 min readLW link
(unstableontology.com)

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

ojorgensenSep 28, 2022, 2:10 PM
17 points
6 comments18 min readLW link

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

HazardJun 28, 2020, 6:50 PM
44 points
11 comments12 min readLW link

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

jollybardJul 12, 2020, 9:13 AM
9 points
6 comments3 min readLW link

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

Abhimanyu Pallavi SudhirJul 26, 2020, 7:16 AM
6 points
4 comments1 min readLW link

Gödel and Bayes: quick question

hairyfigmentApr 14, 2011, 6:12 AM
2 points
36 comments1 min readLW link

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

XiXiDuJan 6, 2012, 5:23 PM
16 points
40 comments2 min readLW link

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

cousin_itJun 27, 2012, 6:28 PM
52 points
22 comments2 min readLW link

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

lukeprogDec 16, 2011, 5:51 AM
12 points
30 comments4 min readLW link

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

Stuart_ArmstrongJun 29, 2012, 11:24 PM
17 points
4 comments4 min readLW link

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

So8resSep 1, 2013, 5:40 PM
27 points
10 comments3 min readLW link

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

Stuart_ArmstrongOct 5, 2012, 2:46 PM
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_ArmstrongJan 16, 2012, 5:38 PM
79 points
39 comments11 min readLW link

You Prov­ably Can’t Trust Yourself

Eliezer YudkowskyAug 19, 2008, 8:35 PM
48 points
19 comments6 min readLW link

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

Sunny from QADOct 13, 2019, 3:59 AM
23 points
22 comments1 min readLW link

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

paulfchristianoDec 10, 2011, 10:30 PM
33 points
9 comments7 min readLW link

Se­cond-Order Logic: The Controversy

Eliezer YudkowskyJan 4, 2013, 7:51 PM
67 points
192 comments15 min readLW link

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

Rafael HarthApr 6, 2022, 7:31 PM
13 points
1 comment67 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 KingFeb 11, 2023, 7:57 AM
5 points
4 comments5 min readLW link

Pro­gram­ming AGI is impossible

Áron EcsenyiMay 30, 2023, 11:05 PM
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?

Noosphere89Apr 17, 2023, 3:14 PM
−11 points
12 comments1 min readLW link

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

Abhimanyu Pallavi SudhirDec 12, 2022, 4:03 PM
16 points
14 comments14 min readLW link

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

AxiomWriterMar 30, 2024, 7:47 AM
−2 points
0 comments6 min readLW link