Introduction to Incompleteness

Serafim Batzoglou is a computer scientists and geneticist whose work has focused on the application of algorithms and machine learning to the analysis of large-scale biomolecular data. After completing his PhD in Computer Science at MIT, he joined the Stanford AI Laboratory in 2001 where he was professor of Computer Science until 2016, when he transitioned to research leadership positions in industry. He has authored more than 120 peer-reviewed publications primarily in the field of computational biology. In 2003, he was named among the top young technology innovators by Technology Review magazine. He received the inaugural Innovator Award by the International Society of Computational Biology (ISCB) in 2016, and was named an ISCB Fellow in 2020. Serafim is also co-founder of DNAnexus, a precision health data cloud company.

Serafim has been fascinated by logic since his undergraduate years as a math major at MIT. He noticed the dearth of books that cover the topic of incompleteness in an accessible manner. As an educator for 15 years, he had strived to teach technical concepts clearly for a broad audience of engineers and biologists. With this book, he puts his experience to practice in providing a comprehensive and accessible technical exposition of incompleteness for a wide audience.

Part 1: Godel's Theorems.- Formal Axiomatic Systems.- Peano Arithmetic and Recursive Functions.- Godel's Incompleteness Theorems.- Structures, Models, and Satisfaction.- Completeness and Compactness Theorems.- Completeness and Peano Arithmetic.- The Lucas-Penrose Arguments.- Part II: Incompleteness in arithmetic and set theory.- Incompleteness in Finite Combinatorics.- Consistency of PA and E0 Induction.- Set Theory.- Independence of CH--forcing.- Independence of CH--forcing CH and -CH.