Computer Science Logic and 8th Kurt Gödel Colloquium
Margarita Korovina: Computational Aspects of $\Sigma$-definability over the Real Numbers without the Equality Test
Welcome and News
Host Institutions
Calls and Deadlines
Social Program
Location and Venue
Colocated Events
Authors' instructions
Print current pagePrint this page
In this paper we study the expressive power and algorithmic properties of the language of $\Sigma$-formulas intended to represent computability on the real numbers. In order to adequately represent computability we extend the reals by the structure of hereditarily finite sets. In this setting it is crucial to consider the real numbers without equality since the equality test is undecidable over the reals. We prove Engeler's Lemma for $\Sigma$-definability over the reals without the equality test which relates $\Sigma$-definability with definability in the constructive infinitary language $L_{\omega_1\omega}$. Thus, a relation over the real numbers is $\Sigma$-definable if and only if it is definable by a disjunction of a recursively enumerable set of quantifier free formulas. This result reveals computational aspects of $\Sigma$-definability and also gives topological characterisation of $\Sigma$-definable relations over the reals without the equality test.
© 2002-2003 Kurt Gödel Society, Norbert Preining. 2003-06-04 Valid HTML 4.01! Valid CSS! Debian