Back-and-forth method


In mathematical logic, especially set theory and model theory, the back-and-forth method is a method for showing isomorphism between countably infinite structures satisfying specified conditions. In particular it can be used to prove that
Suppose that
Fix enumerations of the underlying sets:
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.
It still has to be checked that the choice required in step ' and ' can actually be made in accordance to the requirements. Using step ' 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 ' 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.

History

According to Hodges :
While the theorem on countable densely ordered sets is due to Cantor, the back-and-forth method with which it is now proved was developed by Huntington and Hausdorff. Later it was applied in other situations, most notably by Roland Fraïssé in model theory.