Definability in Rationals with Real Order in the Background

  • Yuri Gurevich ,
  • Alexander Rabinovich

Journal of Logic and Computation | , Vol 12: pp. 1-11

The paper deals with logically definable families of 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 formula φ, the family F can be defined by means of a formula ψ(Y) interpreted over the rational order. We answer the question negatively. The answer remains negative if the first-order logic is strengthen 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.