Back-and-forth method

<h2 id="application-to-densely-ordered-sets">Application to densely ordered sets</h2>
As an example, the back-and-forth method can be used to prove <a href="/facts/Cantor%2527s_isomorphism_theorem/FGxF46Dp">Cantor's isomorphism theorem</a>, although this was not <a href="/facts/Georg_Cantor/k5v1DvW4">Georg Cantor</a>'s original proof. This <a href="/facts/Theorem/f2Pe1FMD">theorem</a> states that two unbounded countable <a href="/facts/Dense_order/EVVQI3V6">dense linear orders</a> are isomorphic.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>
Suppose that

<ul><li>(A, ≤A) and (B, ≤B) are linearly ordered sets;</li>
<li>They are both unbounded, in other words neither A nor B has either a maximum or a minimum;</li>
<li>They are densely ordered, i.e. between any two members there is another;</li>
<li>They are countably infinite.</li></ul>
Fix enumerations (without repetition) of the underlying sets:

A = { a1, a2, a3, ... },
B = { b1, b2, b3, ... }.
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 some 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 some 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.

<h2 id="history">History</h2>
According to Hodges (1993):

Back-and-forth methods are often ascribed to <a href="/facts/Georg_Cantor/k5v1DvW4">Cantor</a>, <a href="/facts/Bertrand_Russell/SRpwNX2U">Bertrand Russell</a> and <a href="/facts/Cooper_Harold_Langford/jkEkc5z3">C. H. Langford</a> [...], but there is no evidence to support any of these attributions.
While the theorem on countable densely ordered sets is due to Cantor (1895), the back-and-forth method with which it is now proved was developed by <a href="/facts/Edward_Vermilye_Huntington/FRagB52P">Edward Vermilye Huntington</a> (1904) and <a href="/facts/Felix_Hausdorff/Rn6DuY2x">Felix Hausdorff</a> (1914). Later it was applied in other situations, most notably by <a href="/facts/Roland_Fra%25C3%25AFss%25C3%25A9/4Kc6D8wj">Roland Fraïssé</a> in <a href="/facts/Model_theory/vLWVV8sQ">model theory</a>.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Ehrenfeucht%25E2%2580%2593Fra%25C3%25AFss%25C3%25A9_game/MJonU8Cb">Ehrenfeucht–Fraïssé game</a></li></ul>

<ul><li><a href="/facts/Felix_Hausdorff/Rn6DuY2x">Hausdorff, F.</a> (1914), Grundzüge der Mengenlehre</li>
<li><a href="/facts/Wilfrid_Hodges/dgBdylPu">Hodges, Wilfrid</a> (1993), <a href="https://archive.org/details/modeltheory0000hodg">Model theory</a>, <a href="/facts/Cambridge_University_Press/fgEBSSRq">Cambridge University Press</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-30442-9</li>
<li><a href="/facts/Edward_Vermilye_Huntington/FRagB52P">Huntington, E. V.</a> (1904), The continuum and other types of serial order, with an introduction to Cantor's transfinite numbers, <a href="/facts/Harvard_University_Press/YluAnq74">Harvard University Press</a></li>
<li>Marker, David (2002), Model Theory: An Introduction, <a href="/facts/Graduate_Texts_in_Mathematics/VTIfY29j">Graduate Texts in Mathematics</a>, Berlin, New York: <a href="/facts/Springer-Verlag/nAesf6nT">Springer-Verlag</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-387-98760-6</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Silver, Charles L. (1994), "Who invented Cantor's back-and-forth argument?", Modern Logic, 4 (1): 74–78, MR 1253680 <a href="https://projecteuclid.org/euclid.rml/1204835164" target="_blank">https://projecteuclid.org/euclid.rml/1204835164</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
</ol>

Back-and-forth method open-in-new

Back-and-forth method