Series: Penn State Logic Seminar

Date: Tuesday, April 29, 2003

Time: 2:30 - 3:45 PM

Place: 113 McAllister Building

Speaker: Christopher Griffin, Penn State, ARL

Title: Non-Effective Quantifier Elimination

Abstract: 

We present a short note of the same title from Mihai Prunescu.  This
note appeared in Math. Log. Quart. 47(4), 2001. Let T be a theory and
let E be the property that T admits quantifier elimination, EE be the
property that said quantifier elimination is effective and D be the
property that the theory is decidable. We will give examples showing
that E does not imply EE in the absence of D. In particular, we will
use a structure that appears in Math 563 homework to do this. We will
also give examples of theories that are undecidable but that have
effective quantifier elimination.  Background information will be
provided if there are a substantial number of audience members
unfamiliar with quantifier elimination.