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.