0

Given a countable set on which a total ordering is defined, it is not always possible to list the full set in ascending order. The set of rationals is a well-known example.

Show that it is impossible to list the rational numbers in increasing order

But are there conditions under which such a listing is possible? Ideally, the conditions would be both necessary and sufficient conditions, but I suppose weak sufficient conditions will, eh, suffice. For instance, can the support of a discrete random variable on a probability space always be listed in ascending order?

Andrés E. Caicedo
  • 79,201
Marcus Nye
  • 390
  • 4
  • 9
  • 2
    If the ordering is a well-order... – Rushabh Mehta Oct 22 '19 at 22:10
  • 2
    Enumerate the rationals as $q_1,q_2,q_3,\ldots$. Then we can have a discrete random variable where $P(X=q_n)=2^{-n}$, so that's a "no" on your last question (and depending on how you define support, it may even be $\Bbb R$ instead of $\Bbb Q$) – Hagen von Eitzen Oct 22 '19 at 22:16
  • @Don Thousand. I don't think you read my question carefully. I already know (and noted) that the rationals cannot be listed in ascending order. My question is "Which countable sets CAN be listed in ascending order?" – Marcus Nye Oct 22 '19 at 22:38
  • @Hagen von Eitzen. I define support of a discrete random variable to be the set of numbers which have positive probability of being assumed by the variable. I agree your example answers the second question. Thanks. – Marcus Nye Oct 22 '19 at 22:52
  • 1
    Depends on what you mean specifically by “list in ascending order”. Even still, there’s really no non-tautological answer. This is a property of the ordering, and not of the underlying set. For instance if you mean that it can be listed like $a_1,a_2,\ldots$ (i.e. excluding cases where there are limits like in countable ordinals larger than $\omega$) then the answer is “if and only if the ordered set is order isomorphic to the natural numbers (i.e. there is an order-preserving bijection with the naturals)”. – spaceisdarkgreen Oct 22 '19 at 23:26
  • @spaceisdarkgreen. By "list in ascending order" I mean that the elements of the set can in entirety be written $\ldots,a_{-1},a_0,a_1,a_2,a_3,\ldots$ such that $\cdots<a_{-1}<a_0<a_1<a_2<a_3<\cdots$. Certainly this depends on the ordering, but I'm assuming the ordering has already been decided upon. – Marcus Nye Oct 23 '19 at 00:15
  • @MarcNye My point is that this property completely determines the ordered set up to isomorphism. I can rattle off a characterization of this in terms of more basic properties of the ordering (every element has an immediate predecessor and for any two elements, there is an $n$ such that one element is the n-th immediate successor of the other) but it doesn't seem like this is what you are looking for. It seems like you are assuming something external as a background, but haven't specified it (like e.g. that we're talking about subsets of the reals). – spaceisdarkgreen Oct 23 '19 at 01:26

1 Answers1

0

Let S be a countable linear order.
Assume for all x,y in S, (x,y) is not order dense.
That is one requirement.
Another requirement is to prevent intervals of the form
(-1/2, -1/3,.. -1/n,.. ..1/n,.. 1/3, 1/2).

William Elliot
  • 17,598