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$?
$\begingroup$
$\endgroup$
asked Mar 18, 2017 at 20:36
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
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$.
answered Mar 18, 2017 at 20:47
-
$\begingroup$ Are there more effective versions of $\mathbf{Q}$ which are $\Delta_1$? $\endgroup$ Commented Mar 18, 2017 at 20:57
-
2$\begingroup$ If I were concerned about complexity, I'd define the (positive) rational numbers simply as (codes for) ordered pairs, like the $x;y$ in the question, such that $y\neq 0$ and such that $x$ and $y$ have no common divisor but 1. In other words, fractions in lowest terms (coded as natural numbers). If (unlike the definition you quoted) I also wanted to include negative rationals, I'd code in a sign along with the numerator and denominator. This coding makes $\mathbb Q$ a recursive set of natural numbers. $\endgroup$ Commented Mar 18, 2017 at 21:57
-
$\begingroup$ Thanks! I will consider this. I am just preparing a follow up question where I attempt to use the $\mu$-function. I link to that in these comments when I post it in a minute. $\endgroup$ Commented Mar 18, 2017 at 22:06
-
3$\begingroup$ There may be a reference, but I don't know one. I considered this obvious. $\endgroup$ Commented Mar 18, 2017 at 22:13
-
1$\begingroup$ @FrodeBjørdal if you want to see a standard development along the lines Andreas suggests, have a look at page 74 of Simpson's Subsystems of Second Order Arithmetic. $\endgroup$ Commented Mar 29, 2017 at 13:32