imported>PagePerfecter: Just added the link in the content.

2025-01-24T11:16:01Z

Just added the link in the content.

New page

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

* any two [[countably infinite]] [[dense order|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 order]]s is simply a strictly increasing [[bijection]]. This result implies, for example, that there exists a strictly increasing bijection between the set of all [[rational number]]s and the set of all [[real number|real]] [[algebraic number]]s.
* any two countably infinite atomless [[Boolean algebra (structure)|Boolean algebras]] are isomorphic to each other.
* any two equivalent countable [[atomic model (mathematical logic)|atomic models]] of a theory are isomorphic.
* the [[Erdős–Rényi model]] of [[random graph]]s, when applied to countably infinite graphs, [[almost surely]] produces a unique graph, the [[Rado graph]].
* any two [[many-one reduction|many-complete]] [[recursively enumerable]] sets are [[computable function|recursively]] isomorphic.

== Application to densely ordered sets ==
As an example, the back-and-forth method can be used to prove [[Cantor's isomorphism theorem]], although this was not [[Georg Cantor]]'s original proof. This [[theorem]] states that two unbounded countable [[dense order|dense linear order]]s are isomorphic.<ref>{{citation
| last = Silver | first = Charles L.
| issue = 1
| journal = Modern Logic
| mr = 1253680
| pages = 74–78
| title = Who invented Cantor's back-and-forth argument?
| url = https://projecteuclid.org/euclid.rml/1204835164
| volume = 4
| year = 1994}}</ref>

Suppose that

* (''A'', ≤''A'') and (''B'', ≤''B'') are linearly ordered sets;
* They are both unbounded, in other words 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:

:''A'' = { ''a''1, ''a''2, ''a''3, ... },
:''B'' = { ''b''1, ''b''2, ''b''3, ... }.

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 some 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 some 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)'''.

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 ''a''''p'' and ''a''''q'' in ''A'' corresponding to ''b''''p'' and ''b''''q'' in ''B'' respectively such that ''a''''p'' < ''a''''i'' < ''a''''q'' and ''b''''p'' < ''b''''q'', we choose ''b''''j'' in between ''b''''p'' and ''b''''q'' 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.

== History ==
According to Hodges (1993):
:''Back-and-forth methods are often ascribed to [[Georg Cantor|Cantor]], [[Bertrand Russell]] and [[Cooper Harold Langford|C. H. Langford]] [...], 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 [[Edward Vermilye Huntington]] (1904) and [[Felix Hausdorff]] (1914). Later it was applied in other situations, most notably by [[Roland Fraïssé]] in [[model theory]].

== See also ==
* [[Ehrenfeucht–Fraïssé game]]

==References==
{{reflist}}
* {{Citation | last1=Hausdorff | first1=F. | author1-link=Felix Hausdorff | title=Grundzüge der Mengenlehre | year=1914}}
* {{Citation | last1=Hodges | first1=Wilfrid | author1-link=Wilfrid Hodges | title=Model theory | publisher=[[Cambridge University Press]] | isbn=978-0-521-30442-9 | year=1993 | url-access=registration | url=https://archive.org/details/modeltheory0000hodg }}
* {{Citation | last1=Huntington | first1=E. V. | authorlink=Edward Vermilye Huntington | title=The continuum and other types of serial order, with an introduction to Cantor's transfinite numbers | publisher=[[Harvard University Press]] | year=1904}}
* {{Citation | last1=Marker | first1=David | title=Model Theory: An Introduction | publisher=[[Springer-Verlag]] | location=Berlin, New York | series=[[Graduate Texts in Mathematics]] | isbn=978-0-387-98760-6 | year=2002}}

{{Mathematical logic}}

[[Category:Articles containing proofs]]
[[Category:Mathematical proofs]]
[[Category:Model theory]]

Back-and-forth method - Revision history

imported>PagePerfecter: Just added the link in the content.