Search Results

CC/GS: Partial Fulfillment of Science Requirement

The course covers Godel's two theorems: (1) In any formal deductive system, which is adequate for doing a minimum of basic mathematics, there are statements that are neither provable nor disprovable.  (2) The consistency of any minimally adequate system is not provable within the system itself.  Those theorems are often regarded as the most philosophically significant results in mathematics, giving rise to foundational questions about human cognition.  Besides their philosophical significance, Godel's technique involved basic notions of computability, leading to the standard impossibility results in theoretical computer science, and to counterparts in complexity theory. The course aims at presenting Godel's proof in a transparent intuitive way, while adhering to the usual standards of rigor.  It also covers the basic notions of computable (or recursive) functions, and computably enumerable sets.  The plan is to discuss some philosophical questions that emerge from the results.  Also planned are undecidability results for some well-known systems - that is, the impossibility of deciding, by means of a computer algorithm whether a given sentence is a theorem. The course relies on detailed couse notes developed over the years.  It requires acquaintance with first-order logic, but will be technically self-contained; the required knowledge is provided as a chapter in the course notes.  Students who are good at it can get it by themselves, but should consult the instructor and get the required approval.