CSci 301 Lecture Notes

Week Nine, Thursday: Decidability of Logical Theories

Mathematical Logic. Godel's incompletness theorem.

A Decidable Theory

Theorem 6.10: decidability of numbers with addition.

An Undecidable Theory

Theorem 6.11: undecidability of numbers with addition and multiplication.

Incompleteness theorem: some true statements are not provable.

Homework Assignment

Assigned Thursday, November 5, due Thursday, November 12:

Chapter 6: exercise 6.4, problem 6.5.


Email: Richard dot J dot Wagner at gmail dot com

notes09b.htm, this hand crafted HTML file created August 31, 1998.
Last updated May 14, 2011, by Rick Wagner. Copyright © 1998-2011, all rights reserved.