Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Are there differences between 'counting' and 'ordering'? As such, the whole of rational number is countable, or they order-able too? In what cases counting and ordering are same or not?

share|improve this question
add comment

2 Answers

up vote 8 down vote accepted

"Counting" means finding the cardinality; "ordering" means establishing an order. Certainly, there is a difference: for a simple example, while there is only one possible answer to "How many elements does the set $\{x,y\}$, with $x\neq y$, have?" (namely, "2"), there are at least two different answers to "What is an ordering of the set $\{x,y\}$, with $x\neq y$?" ( either "$x$ smaller than $y$" or "$y$ smaller than $x$"; if you admit partial orders, then there is even a third possible answer, "$x$ and $y$ incomparable").

Now, the rational numbers are already ordered, in their "usual ordering" as a subset of the reals. But that is not what you really mean, I think. Rather, you want to think about a specific "counting" of the rationals (that is, a bijection to the nonnegative integers) as providing a way to "order" the rationals (or any other set that is "countable"; i.e., bijectable with $\mathbb{N}$).

Yes: if you have a set $X$, and you know that $X$ is countable (there exists a bijection $f\colon X\to\mathbb{N}$), then you can use the bijection to endow $X$ with a "total ordering" (in fact, a well ordering): first, pick a bijection $f\colon X\to\mathbb{N}$; then, given $x$ and $y$ in $X$, define $x\preceq y$ if and only if $f(x)\leq f(y)$ (the latter being the "usual" ordering of the natural numbers). But this ordering is "non-canonical": if you choose a different bijection $f$ (and there are many, many bijections if there is at least one) you get a different order.

share|improve this answer
    
I had to loan you some $ ;-) –  Asaf Karagila Mar 20 '11 at 22:19
1  
Guru, you have well-ordered them by omega^2, which is a countable ordinal. –  Dan Brumleve Mar 20 '11 at 22:26
1  
Guru, it is an infinite succession of infinite lists. So we have omega omegas and that's omega^2. –  Dan Brumleve Mar 20 '11 at 22:45
1  
@Dan, @Guru: To be a bit more precise: it is a countable list of countable lists, each list ordered as the naturals, the list of lists ordered as the naturals. –  Arturo Magidin Mar 20 '11 at 22:46
3  
There is an underknown bijection between the naturals and the non-negative rationals using the binary representation on one hand and the Stern-Brocot tree of mediants (of rationals) on the other. See Graham,Knuth, Patashnik, Concrete Mathematics or Wilf and Calkin, Recounting the Rationals. –  Mitch Mar 20 '11 at 22:57
show 6 more comments

All infinite countable sets have cardinality $\aleph_0$ (which "counts" them) and can be put into one-to-one correspondence with any countable infinite ordinal, the smallest being $\omega$ (which "orders" them), so there is no difference in this case. If you assume the Axiom of Choice, a more general property is true for all sets: the Well-ordering principle. The rational numbers are countable and can be well-ordered by $\omega$: imagine laying them out in a table (according to each numerator and denominator), and then zig-zagging diagonally starting at the corner.

Cantor's diagonal argument explains why the reals are uncountable. The Well-ordering principle says we can well-order the reals by some uncountable ordinal, but it doesn't say which one. If you assume the Continuum Hypothesis, then we can use the first uncountable ordinal to order them. But even with all of these assumptions, it is impossible to visualize the correspondence in the same way as the case of countable ordinals. Some countable ordinals can be difficult to visualize too, such as $\epsilon_0$.

share|improve this answer
    
+1. thanks for answer. I got confused with orderable and countable. For the fact, can you explain how real numbers are orderable / uncountable? (not in comments please, in above answer) –  Guru Mar 20 '11 at 22:27
    
Most ordinals are very complicated to imagine, in the case of $\epsilon_0$ or well-ordering of the reals it all the same after you get used to the idea of well orders. Also there are (strictly) weaker principles such that "every set can be linearly ordered" and "every set can be densely linearly ordered". These are orderings as well, in spite not necessarily being well-founded. Not to mention partial orders. –  Asaf Karagila Mar 20 '11 at 23:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.