Graduate Student Seminar, 4:00 pm April 16, 2007; HH229


Josh Cole



Decidable and Undecidable Theories



We say that the theory of a class of mathematical structures is "decidable" if there is an algorithm for determining which first-order sentences are true of all structures in the class. I will make this definition more precise and give examples of both decidable and undecidable theories of familiar classes of mathematical structures. The class of groups will be given special attention; I will show how the existence of a finitely presented group with an unsolvable word problem implies that the theory of the class of groups is undecidable.


To volunteer to give a talk, or for any other questions regarding this schedule, contact Sara Miller