2
$\begingroup$

Let $X$ be a countable ordered set. My question is very simple - Can we sort $X$ in countable number of steps?

When $X$ is finite, the answer is obviously yes. But what is the answer when $X$ is infinite?

Thanks in advance!

$\endgroup$
8
  • $\begingroup$ Sure. Do bubble sort on the first n elements, and then increment n. Gerhard "Don't Ask Me About Supertasks" Paseman, 2013.09.28 $\endgroup$ – Gerhard Paseman Sep 28 '13 at 20:50
  • 1
    $\begingroup$ Welcome back, @GerhardPaseman! :) $\endgroup$ – Joel Reyes Noche Sep 28 '13 at 23:57
  • 3
    $\begingroup$ Well, it's less simple than that - iterated bubble sort only works if $X$ has order type $\omega$. But we could ask this same question if $X$ is any order type, and if $X$ is well-ordered we could make sense of "a computational procedure of length $X$" (and maybe even if $X$ is not well-ordered; I vaguely remember a paper doing this, but I can't find it - it is still conceivable). In any case, I think the full answer might be less simple, and I'm not sure this question should have been closed (although it certainly needs more explanation, and a clarification of what's being asked). $\endgroup$ – Noah Schweber Sep 29 '13 at 4:00
  • 2
    $\begingroup$ I think the article I was vaguely remembering is liafa.univ-paris-diderot.fr/~carton/Publications/Linear/Kleene/… (and I should also note that "sort" is ambiguous if $X$ is not well-ordered - for example, if $X$ is $\mathbb{Z}$ with the usual order, then there $\omega$-many ways to 'list $X$ in order' if we take that to mean 'exhibit a map from $X$ to $\mathbb{Z}$ which is order-preserving). I strongly encourage the OP to rewrite this question, with motivation and clear definitions; I think it could be extremely interesting. $\endgroup$ – Noah Schweber Sep 29 '13 at 4:05
  • 1
    $\begingroup$ @Joel, Thank You! It does feel quite nice to be welcomed. Noah, it depends on what is truly wanted, and what resources are at hand. Clearly any finite fragment of X can be ordered with e.g. bubblesort; all that is needed is some surjection of $\omega$ onto X. If the idea is to discover the order type of X, I agree that requires a bit more. Gerhard "May Come Here More Often" Paseman, 2013.09.30 $\endgroup$ – Gerhard Paseman Oct 1 '13 at 3:25