Cantor's back-and-forth method

From Wikipedia, the free encyclopedia

You have new messages (last change).

In mathematical logic, especially set theory and model theory, Cantor's back-and-forth method, named after Georg Cantor, is a method for showing isomorphism between countably infinite structures satisfying specified conditions. In particular:

  • Cantor used it to prove that any two countably infinite densely ordered sets (i.e., linearly ordered in such a way that between any two members there is another) without endpoints are isomorphic. An isomorphism between linear orders is simply a strictly increasing bijection. This means, for example, that there exists a strictly increasing bijection between the set of all rational numbers and the set of all real algebraic numbers.
  • It can be used to prove that any two countably infinite atomless Boolean algebras are isomorphic to each other.

[edit] Application to densely ordered sets

Suppose that

  • (A, ≤A) and (B, ≤B) are linearly ordered sets;
  • Neither A nor B has either a maximum or a minimum;
  • They are densely ordered, i.e. between any two members there is another;
  • They are countably infinite.

Fix enumerations (without repetition) of the underlying sets:

\begin{matrix} A & = & \{\, a_1, a_2, a_3, \dots \,\}, \\ \\ B & = & \{\, b_1, b_2, b_3, \dots \,\}. \end{matrix}

Now we construct a one-to-one correspondence between A and B that is strictly increasing. Initially no member of A is paired with any member of B.

(1) Let i be the smallest index such that ai is not yet paired with any member of B. Let j be the smallest index such that bj is not yet paired with any member of A and ai can be paired with bj consistently with the requirement that the pairing be strictly increasing. Pair ai with bj.
(2) Let j be the smallest index such that bj is not yet paired with any member of A. Let i be the smallest index such that ai is not yet paired with any member of B and bj can be paired with ai consistently with the requirement that the pairing be strictly increasing. Pair bj with ai.
(3) Go back to step (1).

It still has to be checked that the choice required in step (1) and (2) can actually be made in accordance to the requirements. Using step (1) as an example:

If there are already ap and aq in A corresponding to bp and bq in B respectively such that ap < ai < aq and bp < bq, we choose bj in between bp and bq using density. Otherwise, we choose a suitable large or small element of B using the fact that B has neither a maximum nor a minimum. Choices made in step (2) are dually possible. Finally, the construction ends after countably many steps because A and B are countably infinite. Note that we had to use all the prerequisites.

Note that if we iterated only step (1), rather than going back and forth, then the resulting pairing would fail to be bijective.

[edit] Reference

Retrieved from "http://en.wikipedia.org../../../c/a/n/Cantor%27s_back-and-forth_method.html"