2021/12/07 by Serafim Batzoglou, Batzoglou, Serafim
Computer Science · Psychology · #03-01 #03D20 #03F40 #Artificial Intelligence (cs.AI) #Computability, Logic, AI Algorithms #F.1.1 #F.4.1 #FOS: Computer and information sciences #FOS: Mathematics #G.2.m #History and Overview (math.HO) #I.2.3 #I.2.4 #Logic (math.LO) #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Philosophy and Theoretical Science
paper · pdf · doi:10.48550/arxiv.2112.06641
openalex publication_date 2021/12/07 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
I present the proof of Goedel's First Incompleteness theorem in an intuitive manner, while covering all technically challenging steps. I present generalizations of Goedel's fixed point lemma to two-sentence and multi-sentence versions, which allow proof of incompleteness through circular versions of the liar's paradox. I discuss the relation of Goedel's First and Second Incompletneness theorems to Goedel's Completeness theorems, and conclude with remarks on implications of these results for mathematics, computation, theory of mind and AI.