Decision Problems over the Domain of the Real Numbers

Speaker

Ulrich Loup

Title Decision Problems over the Domain of the Real Numbers
When 29.01.2009
Where Lecture Room Informatik 11
Abstract This work comprises a survey of decidable and undecidable first-order, weak monadic second-order and monadic second-order theories over the domain of the real numbers. The decidability results are presented in a convenient, informal way. In detail the method of interpreting one logical theory in another introduced by Michael O. Rabin is reworked for the mentioned logical systems. It then is used to redesign Saharon Shelah’s proof for the undecidability of the monadic second-order theory of real orderings.
Slides download