© 2002 by Oxford University Press
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
Original Article |
Definability in Rationals with Real Order in the Background
1 Microsoft Research and Dept EECS, University of Michigan, One Microsoft Way, Redmond, WA 98052, USA. E-mail: gurevich{at}microsoft.com 2 Department of Computer Science, Beverly Sackler School of Exact Sciences, Tel Aviv University, Israel 69978. E-mail: rabino{at}math.tau.ac.il
The paper deals with logically definable families of sets (or point-sets) 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 
(X, Y) and 
(Y) range over formulas in the first-order monadic language of order. Let Q be the set of rationals and F be the family of subsets J of Q such that (Q, J) holds over the real line. The question arises whether, for every , F can be defined by means of an appropriate (Y) interpreted over the rational order. We answer the question negatively. The answer remains negative if the first-order logic is strengthened to weak monadic second-order logic. The answer is positive for the restricted version of monadic second-order logic where set quantifiers range over open sets. The case of full monadic second-order logic remains open.
Keywords: Definability; expressibility; monadic logic of order
Received 17 December 1999.