Back-and-forth method

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.

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 a_i is not yet paired with any member of B. Let j be the smallest index such that b_j is not yet paired with any member of A and a_i can be paired with b_j consistently with the requirement that the pairing be strictly increasing. Pair a_i with b_j.

(2) Let j be the smallest index such that b_j is not yet paired with any member of A. Let i be the smallest index such that a_i is not yet paired with any member of B and b_j can be paired with a_i consistently with the requirement that the pairing be strictly increasing. Pair b_j with a_i.

(3) Go back to step (1).

[Could someone add a reference to the original paper here?]