Definability in Rationals with Real Order in the Background
Yuri G. Gurevich · Journal of Logic and Computation · 2002
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.