TITLE: Is the set of rational numbers recursive?
QUESTION [4 upvotes]: My question is expressed by means of Quine's definition of rational numbers in Set Theory and its Logic,  chapters 17 and 18. 
Let pairing of natural numbers be represented as by his definition 17.1 $x;y=_{def}x+(x+y)^2$, let as by 18.1 $x/y=_{def}  \{z;w|z,w\in\mathbf{N}\wedge x\cdot w > y\cdot z \}$ and as in 18.10 let $\mathbf{Q}=_{def}\{x/y|x, y\in\mathbf{N}\wedge y\neq 0 \}$. Is $\mathbf{Q}$ $\Delta_1$, or just $\Sigma_1$?

REPLY [5 votes]: With this definition, each rational number is a set of natural numbers, so you're asking about the status of a set of sets of natural numbers. Every $\Sigma_1^0$ subset of $\mathcal P(\mathbb N)$ is open in the usual topology (the product topology on $2^{\mathcal N}$), but this version of $\mathbb Q$ is not open.  Given any rational $x/y$ and given any finite subset $F\subseteq\mathbb N$, it's easy to find a set $S$ of natural numbers that is not a rational number yet has $S\cap F=(x/y)\cap F$.  So this version of $\mathbb Q$ is not even $\Sigma_1^0$.
{"set_name": "stack_exchange", "score": 4, "question_id": 264983}