Series: Penn State Logic Seminar

Date: Tuesday, October 3, 2000

Time: 2:30 - 3:20 PM

Place: 307 Boucke Building

Speaker: Stephen G. Simpson, Department of Mathematics, Penn State

Title: Undecidable Algebraic Theories, Part 2

Abstract: 

We present an analysis of Turing computability in terms of
hereditarily finite sets.  We use this to prove that the theory of one
finite binary relation is hereditarily undecidable.  This is closely
related to the Trakhtenbrot-Vaught theorem.  From this we deduce that
the theories of finite graphs and finite distributive lattices are
hereditarily undecidable.  Later in this series, we shall go on to
show that the theories of finite commutative rings and finite groups
are hereditarily undecidable.