Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm interested in Cantor's back-and-forth method so I searched online and surprisingly it was on the Wikipedia.

My question is about the paragraph that starts saying: If we iterated only step (1), rather than going back-and-forth...

For me, it is not clear why we can avoid step 2 in the case of unbounded dense totally ordered sets, why is it posible to choose $j$ "as small as posible"? It is because our sets are well-ordered? or why is it? I hope someone can help me with this :)

share|cite|improve this question
Am inclined to agree. The paragraph you mention is fuzzy. The well-ordering of the two sets is arbitrary, and has nothing to do with the orderings we are proving isomorphic. My feeling is that given any fully specified purely "forth" argument, I could produce a lisitng of the sets that would make surjectivity fail. – André Nicolas Apr 18 '12 at 23:14
Your recomendation is to use the full Back-and-Forth method? – luciana Apr 19 '12 at 3:30
Yes, for proving isomorphism it is a very useful idea. Shows up also in proving that if $A$ has same cardinality as a subset of $B$, and vice-versa, then $A$ and $B$ have the same cardinality. Also useful in Model Theory. – André Nicolas Apr 19 '12 at 3:31
ok I would study this method a little bit more, thanks a lot :) – luciana Apr 19 '12 at 3:36
Depends on your field of work. You may only need it for the one isolated purpose of proving Cantor's Theorem about densely ordered countable sets. – André Nicolas Apr 19 '12 at 3:39
up vote 1 down vote accepted

Let the "only-forth" method be applied by traversing the enumeration of $A$ and pairing each $a_i$ with the $b_j$ that has the least index $j$ of all elements of $B$ compatible with the current set of constraints. This is well-defined since, as the Wikipedia article explains, there is always at least one such element of $B$, and every non-empty set of indices has a least element.

At the $n$-th stage of the construction, after $n$ pairs have been chosen, the unpaired values in $A$ are divided into $n+1$ (countably infinite) sets $A_{nm}$ ($n-1$ between the paired values and $2$ at either end), and $B$ is likewise divided into $n+1$ (countably infinite) sets $B_{nm}$. If an element of $A_{nm}$ is to be paired next, the partner can be arbitrarily chosen from the corresponding set $B_{nm}$.

A given element $b_k$ of $B$ is always in one of these sets $B_{nm}$ until it gets paired. Since there is always a corresponding set $A_{nm}$ of as yet unpaired elements of $A$ and all elements of $A$ eventually get paired, an element $b_k$ that never gets paired would experience infinitely many choices being made from its respective current $B_{nm}$. But this is impossible, since in each case the element of $B_{nm}$ with least index is chosen, and there are only finitely many indices less than $k$.

share|cite|improve this answer

Your Answer


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.