OUP > Journals > Computing/Engineer. & Mathematics/Stats. > Journal of Logic and Computation
Journal of Logic and Computation
Volume 12, Issue 1, February 2002: pp. 111
Definability in Rationals with Real Order in the Background
Yuri Gurevich^{1} and Alexander Rabinovich^{2}
^{1}Microsoft Research and Dept EECS, University of Michigan, One Microsoft Way, Redmond, WA 98052, USA. Email: gurevich@microsoft.com
^{2}Department of Computer Science, Beverly Sackler School of Exact Sciences, Tel Aviv University, Israel 69978. Email: rabino@math.tau.ac.il
The paper deals with logically definable families of sets (or pointsets) of rational numbers. In particular we are interested whether the families definable over the real line with a unary predicate for the rationals are definable over the rational order alone. Let [phgr](X, Y) and [psgr](Y) range over formulas in the firstorder monadic language of order. Let Q be the set of rationals and F be the family of subsets J of Q such that [phgr](Q, J) holds over the real line. The question arises whether, for every [phgr], F can be defined by means of an appropriate [psgr](Y) interpreted over the rational order. We answer the question negatively. The answer remains negative if the firstorder logic is strengthened to weak monadic secondorder logic. The answer is positive for the restricted version of monadic secondorder logic where set quantifiers range over open sets. The case of full monadic secondorder logic remains open.
Keywords: Definability; expressibility; monadic logic of order
Table of Contents
FullText PDF (143 KB)
