Are all countable sortable sets homeomorphic to $\mathbb{N}$?

Question

In any ordered metric space, let a set $S$ be sortable if it can be placed into 1-1 correspondence with $\mathbb{N}$ such that $x > y \iff n(x) > n(y)$ for all $x,y \in S$. I conjecture the following about sortable sets, and request help proving (or disproving!) them.

Conjecture 1: A set is sortable if and only if it is homeomorphic to $\mathbb{N}$. I conjecture this because the sortable sets I encountered, such as subsets of $\mathbb{N}, \{kn\}, \{n+k\},$ and $\{1/n\}$ are all homeomorphic to $\mathbb{N}$, whereas the unsortable sets, such as $\mathbb{Z}, \mathbb{Q},$ and $\{1/n\}\cup\{0\}$, are not.

Conjecture 2: If a set is countable but not sortable, is it somehow composed of sortable sets? $\mathbb{Z}$ is the union of two sortable sets, and while $\mathbb{Q}$ is not the union of any collection of sortable sets, it is the product of two sortable sets [*]. Is every countable set a union or product of a finite collection of sortable sets?

Proposition 3: An infinite sortable set is not compact. Proof: Consider the collection $O$ of open balls around each $s \in S$, each of radius less than $\min(d(n^{-1}(n(s)+1), s), d(n^{-1}(n(s)-1), s)$. Each $s \in S$ is in precisely one $o \in O$. Thus, $O$ is an open cover of $S$ with no finite subcover.

Besides the above, are there other noteworthy properties of sortable sets? Is there any discussion of sortable sets, or a similar concept, in the literature?

---

[*] By "$\mathbb{Q}$ is the product of two sortable sets," I mean that any rational number corresponds to two independently chosen natural numbers, the numerator and the denominator. However, I see now that this is not an injection, because, for example $\frac 1 2 = \frac 2 4$, whereas $(1,2) \neq (3,4).$ Perhaps I need to refine my statement: Can $\mathbb{Q}$ be somehow composed from finite sortable sets?

Answer 1

I assume you use the canonical topology of the metric space $E$ and the subspace topology for $S$. I also assume that you use the discrete topology for $\mathbb{N}$.

Conjecture 1 is false. You don't have $S$ homeomorphic to $\mathbb{N}$ $\Rightarrow$ $S$ sortable. $\mathbb{Z}$ and $\mathbb{N}$ with the discrete topology are homeomorphic. Any function from a space with the discrete topology to any other topological space is continuous. Hence for two spaces with discrete topology to be homeomorphic, they just need to be in bijection. Any time you have a set $S$ for which $\inf(\lbrace d(x, y), (x, y) \in E^2 \rbrace) \gt 0$, the subspace topology for $S$ is exactly the discrete topology on $S$.

As a counter-example, take $\mathbb{R}$ as your ordered metric space, $\mathbb{Z}$ as $S$. $\mathbb{Z}$ is homeomorphic to $\mathbb{N}$ but not sortable.

For conjecture 2, the problem is defining "composed of". First, I suggest broadening the definition of sortable by authorizing monotone functions, not just increasing functions. If not, you can't split $\mathbb{Z}$ into two sortable sets because you need to have a minimum element in your definition of a sortable set.

The problem of defining a set as the product of other sets, in general, is that it tends to involve bijection somehow. But here, defining the object "up to a bijection" is equivalent to saying that the set is countable. Suppose you want somehow to keep the order in the definition. In that case, you must define how the order interacts with the product in general, and it tends to give an order that looks like alphabetical order, which is kind of limited. For $\mathbb{Q}$, you have a "natural" representation as the product $\mathbb{Z} \times \mathbb{Z}$ modulo an equivalency relation, but in general, it is difficult to define what is a "natural" representation without resorting to bijections. You need to precisely define "composed of" to avoid a trivial conjecture that just involves "being in bijection".

If the conjecture is "For a countable set, can it be partitioned as a finite set of sortable sets" the answer is also no. $\mathbb{Q}$ is a counter-example. It is easy to show that any sortable subsets of $\mathbb{Q}$ contain at most one accumulation point. If the conjecture were true, it would imply that $\mathbb{Q}$ has a finite number of accumulation points which is untrue.

In proposition 3, your proof assumes that the metric and order structure fits nicely together and that looking at the distance to the elements element "before" and "after" is sufficient to ensure that the balls are disjoint, which is not true in general. Take the set of $\mathbb{R}$, $K = \lbrace 0 \rbrace \cup \lbrace 2^{-n}, n \in \mathbb{N} \rbrace$. $K$ is compact since it is closed and bounded. We can now construct a pathological order on $\mathbb{R}$ that will provide a counter-example. $K$ is countable, so there is a bijection $f: K \rightarrow \mathbb{N}$. Now build the order $\lt'$ on $\mathbb{R}$ such that for all $x \in K$ and $y \in \mathbb{R} / K$, $x \lt' y$. If $x$ and $y$ are in $\mathbb{R} / K$ the natural order of $\mathbb{R}$ applies, if $x$ and $y$ are in $K$, then the order is inherited from $f$. With this new order, $K$ is sortable by construction, but $K$ is also compact.

The problem is that your order and metric structure aren't nicely connected in your definition.

I am unfamiliar with the existence of a field in mathematics studying this particular object or a similar concept. I would tend to think that this subject isn't very studied because, indeed, metric space doesn't tend to have natural order that plays well with the topological or metric structure of the space.

Answer 2

@SRobertJames, I add another answer because the explication is too long for the comments.

When you say "goes to infinity in two different ways," it can mean two things, neither of which is a topological property.

First, it can mean that if I take an $x \in \mathbb{Z}$, there is an infinite number of numbers higher than $x$ and an infinite number of numbers lower than $x$. This notion arises from your order and has nothing to do with the discrete topology of $\mathbb{Z}$.

For example, let's build another order $<'$ on $Z$ for which $\mathbb{Z}$ doesn't go to infinity. Take the set $X = [0, 1] \cap \mathbb{Q}$. $X$ is countable so you can define a function $f$ from $\mathbb{Z}$ to $X$. Now for any $x, y \in \mathbb{Z}$ define $x <' y \Leftrightarrow f(x) < f(y)$. Here the ordered set $(\mathbb{Z}, <')$ has a maximum and a minimum element, respectively $f^{-1}(0)$ and $f^{-1}(1)$, so there is no "going to infinity" with this order. So this is a property of $\mathbb{Z}$ seen as an ordered set with the canonical order, not as a topological space.

Similarly, if "goes to infinity in two different ways" is interpreted as "The two sequences $u_n = n$ and $v_n = -n$ are such that $d(0, u_n)$ and $d(0, v_n)$ diverges when $n$ goes to infinity", then this notion arises from the structure of $\mathbb{Z}$ as a metric space, not as a topological one. You need to have a distance to define your statement. If you take the discrete distance (i.e. the distance $d'$ such that $d'(x,y)$ is $0$ if $x=y$ and is $1$ otherwise) on $\mathbb{Z}$, then $\mathbb{Z}$ has a diameter of $1$ and nothing "goes to infinity" anymore. Once again, the "goes to infinity" parts here arises from the canonical metric structure of $\mathbb{Z}$, not from $\mathbb{Z}$ itself or its discrete topology.

Topology is interested in continuity, in how points are connected; there is no notion of how points are ordered or how far they are. And so, for topology, as long as your points aren't connected, it is precisely as if they live in totally different spaces. They are not topologically relatable to one another. This is why you don't have this notion of "goes to infinity" when dealing with isolated points. $\mathbb{Z}$ (with the discrete topology) is topologically equivalent to a collection of isolated points indexed by $\mathbb{Z}$, i.e. $\bigsqcup_{\mathbb{Z}} \star$ where $\star$ designate a singleton. When you write it that way, you see that you lost your metric and your order. And "pairing" isolated points equivoquely between two spaces exactly describes a bijection. This is how you can intuitively understand why when you have two spaces with the discrete topology, having them homeomorph and having them in bijection is exactly the same. Because for the discrete topology, spaces are literally seen as clouds of isolated points indexed by your original set.

I suspect that the notion you are interested in is not the one of homeomorphism but of monotonic homeomorphism. Here, you try in some sense to merge the topological structure of your space and the order structure of your space. In doing so, the natural "isomorphism" you seem to have in mind are the isomorphisms that preserve both the topological structure (homeomorphism) and ordered structure (monotonic function) of your space. And on this point, you are absolutely right; there exists no monotonic homeomorphism between $\mathbb{Z}$ and $\mathbb{N}$ because there exists no monotonic function between $\mathbb{Z}$ and $\mathbb{N}$. You can formally state this in category theory by saying that $\mathbb{Z}$ and $\mathbb{N}$ with the discrete topology are isomorphic in the category of topological spaces $\mathbf{Top}$, but that $\mathbb{Z}$ and $\mathbb{N}$ with their canonical order are not isomorphic in the category of ordered set $\mathbf{OrdSet}$. If you are interested in merging different structures on spaces, I highly suggest looking at category theory. It is a very powerful framework to think about those things.