Oxford Journals
tools journals homepage advanced search contact help
Journal of Logic and Computation: Current Issue

OUP > Journals > Computing/Engineer. & Mathematics/Stats. > Journal of Logic and Computation

Journal of Logic and Computation

Volume 12, Issue 1, February 2002: pp. 1-11

Definability in Rationals with Real Order in the Background

Yuri Gurevich1 and Alexander Rabinovich2

1Microsoft Research and Dept EECS, University of Michigan, One Microsoft Way, Redmond, WA 98052, USA. E-mail: gurevich@microsoft.com
2Department of Computer Science, Beverly Sackler School of Exact Sciences, Tel Aviv University, Israel 69978. E-mail: rabino@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 [phgr](X, Y) and [psgr](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 [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 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

Table of Contents   Full-Text PDF (143 KB)

Oxford University Press
Published by Oxford University Press
Copyright ©Oxford University Press 2003
Print ISSN: 0955-792X  Online ISSN: 1465-363X.
Oxford University Press Privacy Policy and Legal Statement