MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 4 added 10 characters in body; edited body; deleted 10 characters in body

Here is Goldstern's answer, transcribed to constructive mathematics.

In constructive mathematics we do not speak of "recursive" but rather decidable subsets of $\mathbb{N}$. (Recall that a subset $X \subseteq Y$ is decidable if $\forall y \in Y. y \in X \lor y \not\in X$.) Also, your assumption that $A \neq \emptyset$ should be replaced with "$A$ is inhabited", i.e., $\exists n \in A . \top$, or else one is forced to use Markov principle unecessarily.

Let us also observe that an inhabited decidable subset $A \subseteq \mathbb{N}$ has a minimal element. Indeed, given $k \in A$, we may find the least $j \leq k$ such that $j \in A$ by simply checking all of them.

Suppose then that $A$ is a decidable inhabited subset of $\mathbb{N}$. We wish to enumerate the elements of $A$ in a non-decreasing order. Because $A$ is inhabited and decidable it has a minimal element $k \in A$. Now simply define an enumeration $e : \mathbb{N} \to A$ by $$e(n) = \max \lbrace i \in A \mid i \leq \max(n,k) \rbrace.$$ The maximum in the definition of $e$ exists because it is over a finite decidable inhabited subset of $\mathbb{N}$. Clearly, $e(n) \in A$ for all $n$, and $e$ enumerates all of $A$ because $e(m) = m$ when $m \in A$.
show/hide this revision's text 3 added 106 characters in body

Here is Goldstern's answer, transcribed to constructive mathematics.

In constructive mathematics we do not speak of "recursive" but rather decidable subsets of $\mathbb{N}$. (Recall that a subset $X \subseteq Y$ is decidable if $\forall y \in Y. y \in X \lor y \not\in X$.) Also, your assumption that $A \neq \emptyset$ should be replaced with "$A$ is inhabited", i.e., $\exists n \in A . \top$, or else one is forced to use Markov principle unecessarily.

Let us also observe that an inhabited decidable subset $A \subseteq \mathbb{N}$ has a minimal element. Indeed, given $k \in A$, we may find the least $j \leq k$ such that $j \in A$ by simply checking all of them.

Suppose then that $A$ is a decidable inhabited subset of $\mathbb{N}$. We wish to enumerate the elements of $A$ in a non-decreasing order. Because $A$ is inhabited and decidable it has a minimal element $k \in A$. Now simply define an enumeration $e : \mathbb{N} \to A$ by $$e(n) = \max \lbrace i \in A \mid i \leq \max(n,k) \rbrace.$$ The maximum in the definition of $e$ exists because it is over a finite decidable subset of $\mathbb{N}$. Clearly, $e(n) \in A$ for all $n$, and $e$ enumerates all of $A$ because $e(m) = m$ when $m \in A$.
show/hide this revision's text 2 Answered what was actually asked.; added 383 characters in body

I am going to

Here is Goldstern's answertwice, transcribed to constructive mathematics.Once as if your use

In constructive mathematics we do not speak of the word "constructive" meant "computable", and once as if it actually meant "constructive" in the sense recursive" but rather decidable subsets of "constructive mathematics".

First answer: Suppose there were a computable method $c$ of transforming \mathbb{N}$. (codes of) computable enumerations of non-empty sets to non-decreasing computable enumerations of non-empty sets. Then we can solve the Halting oracle as follows. Given any Turing machine $T$, consider the sequence Recall that a subset $e : X \mathbb{N} subseteq Y$ is decidable if $\forall y \to in Y. y \mathbb{N}$ defined by$$e(n) = in X \begin{cases}1 & lor y \text{$T$ does not halt at step not\in X$.) Also, your assumption that $n$} \A \0 & neq \text{$T$ halts at step emptyset$ should be replaced with "$A$ is inhabited", i.e., $n$}\exists n \end{cases}$$The map $e$ enumerates the set ${0,1}$ in A . \top$, or ${1}$, depending on whether $T$ haltselse one is forced to use Markov principle unecessarily.By assumption $c$ transforms

Let us also observe that an inhabited decidable subset $e$ into A \subseteq \mathbb{N}$ has a non-decreasing enumeration $e'$ which enumerates the same set as $e$. If $e'(0) = 0$ then minimal element. Indeed, given $T$ haltsk \in A$, otherwise it does not.

Second answer: In constructive mathematics we can just drop may find the adjetive "computable" from "computable enumeration". Suppose for every enumeration least $e : j \mathbb{N} leq k$ such that $j \in A$ by simply checking all of them.

Suppose then that $A$ is a decidable inhabited subset of $\mathbb{N}$. We wish to \mathbb{N}$ there existed another enumeration which listed enumerate the same elements of $A$ in a non-decreasing order. We can derive from this the non-constructive principle LPO as follows. Consider Because $A$ is inhabited and decidable it has a map minimal element $f k \in A$. Now simply define an enumeration $e : \mathbb{N} \to {0,1}$. We are supposed to decide whether A$ by$\exists n $e(n) = \max \lbrace i \in A \mathbb{N} . f(n) = 0$. By assumption there is a non-decreasing map $e' : mid i \mathbb{N} leq \to max(n,k) \mathbb{N}$ which has the same image as rbrace.$$ Clearly, $f$. We simply look at e(n) \in A$ for all $e'(0)$ to tell whether n$, and $f$ attains e$ enumerates all of $0$.A$ because $e(m) = m$ when $m \in A$.
show/hide this revision's text 1