Vtyjkyuk

In Reverse Mathematics, Stillwell states the following:

Realizing a $Sigma_0^0$ condition by a function. For any $Sigma_0^0$ condition $exists mvarphi(m, n)$, there is a function $g:mathbbN rightarrow mathbbN$ such that $exists m [g(m) = n] iff exists m varphi(m, n)$.

Proof. ...

Remember that when RCA$_0$ proves existence of a function $g$ this means that the set of ordered pairs $leftlangle n, g(n)rightrangle$ is computable. We have not proved in RCA$_0$ that the set $leftlbrace n:exists m varphi(m,n)rightrbrace$, the range of $g$, exists. Indeed, we cannot do this in RCA$_0$ when $leftlbrace n: exists m varphi(m,n)rightrbrace$ is computably enumerable but not computable.

To claim the existence of the set $leftlbrace n: exists m varphi(m,n)rightrbrace$ we would need more than recursive comprehension; we would need $Sigma_1^0$ comprehension....

But I don't understand why this should be the case. Doesn't the generation of pairs $leftlangle n, g(n) rightrangle$ itself constitute a constructive proof of the existence of $leftlbrace n : exists m varphi(m,n)rightrbrace$?

-- Or, like, what precisely does it mean for a constructed set to "exist", that we would need to prove it? In cases where we say "Consider a set with the following properties", then the set exists iff our properties are not self-contradicting -- but rather than starting from a high-level property and trying to find a set that satisfies it, at this point after the proof we have some (possibly infinite) list of members and we're just wrapping a pair of curly braces around them and calling it a set, aren't we?

The use of the word "exists" in reverse mathematics has a specific meaning, but it can be confusing at first.

In many other contexts, we can define a set with almost any definition, but we may not have an algorithm to tell which elements are in the set. Even if the set only contains natural numbers, we may not have any particular way to tell which elements are in the set.

In $mathsfRCA_0$, there is only one axiom scheme that we can use to construct sets, and that axiom scheme requires us, in a precise sense, to have an algorithm to decide membership in the set. The precise sense is: to prove that a set exists, we need to have a $Sigma^0_1$ definition of the set (so the set is recursively enumerable, essentially) and a $Sigma^0_1$ definition of the complement of the set (so the complement of the set is also r.e.). These definitions of the set and its complement are allowed to refer to other sets that we already have at hand. The overall axiom scheme is called $Delta^0_1$ comprehension.

When we say $mathsfRCA_0$ proves that a set "exists", we mean that we have that kind of definition of the set. This is much stronger than just saying that the set exists in the general mathematical sense.

This is a common confusion faced when learning reverse mathematics. There are three different objects to consider here:

• The function $g$.




• The graph of $g$, $langle n,g(n)rangle: ninmathbbN$.




• The range of $g$, $m: exists n(g(n)=m)$.

The first two are really the same thing in reverse mathematics: in (classical) reverse mathematics, we only have numbers and sets of numbers, so a "function of numbers" is really just a set with certain properties (namely, for each $n$ there is exactly one $k$ with $langle n,krangle$ in the set).

The first two are also essentially the same in computability theory, in the sense that $g$ is computable iff its graph is (more generally, any function is of the same Turing degree as its graph).

The third, however, is a very different object (and in particular your claim "My question could be restated: "How can $langle n,g(n)rangle:ninmathbbN$ be computable if $g(n)$ itself isn't?"" is incorrect, since $langle n,g(n)rangle:ninmathbbN$ is very much not $m: exists n(g(n)=m)$):

Let me first give an intuitive argument that the range of a computable function need not be computable, and then talk about what's going on in RCA$_0$.

Suppose you had a "black box" representing a function $g$, where you feed in natural numbers and it spits out natural numbers. Now you ask whether $3$ is in the range of (the function computed by) this black box. So you check:

• Is $g(0)=3$? No - when you feed $0$ into the box, it spits out $2$, and $2not=3$.




• Is $g(1)=3$? No - when you feed $1$ into the box, it spits out $4$, and $4not=3$.




• Is $g(2)=3$? No - when you feed $2$ into the box, it spits out $17$, and $17not=3$.




• Is $g(3)=3$? No - when you feed $3$ into the box, it spits out $0$, and $0not=3$.




• ...

However, at no point in this process can you confidently conclude that $3$ is not in the range of $g$! It could be that you just haven't tested the right value.

• Exercise: come up with a specific computable function whose range isn't computable. HINT: think about the halting problem ...
  

So even though you may think of the range of a function as having "less information" than the whole function itself - after all, which numbers go where is forgotten when we look at the range alone - this is actually horribly misleading in the context of computability theory and reverse math: extracting the range of a function from the function itself takes in general nontrivial power.

OK, so now let's think about RCA$_0$. You write:

Or, like, what precisely does it mean for a constructed set to "exist", that we would need to prove it? In cases where we say "Consider a set with the following properties", then the set exists iff our properties are not self-contradicting -- but rather than starting from a high-level property and trying to find a set that satisfies it, at this point after the proof we have some (possibly infinite) list of members and we're just wrapping a pair of curly braces around them and calling it a set, aren't we?

This is not correct, and is also too vague; especially at first, you need to argue very precisely when trying to show that RCA$_0$ proves (or doesn't prove) something. RCA$_0$ has a very limited amount of comprehension (= set existence) power. In order to prove in RCA$_0$ that a set with a certain property exists, you basically need to show that that property can be expressed in a "simple" way - namely, in a $Delta^0_1$ way. The obvious definition of the range of a function $g$ is $Sigma^0_1$ with a parameter for $g$, so even if $g$ is computable we can't immediately argue that its range exists: we would need to also find a $Pi^0_1$ definition for its range. And the point of the above section is that in general, we can't do better than $Sigma^0_1$.

Now you might argue that in some informal sense, we can "construct" the range of a function from the function itself. That's reasonable, but then the way you're using the word "construct" is quite different from the way RCA$_0$ works, and the corresponding intuition will in fact be completely misleading in reverse mathematics.