Возвратно-поступательный метод - Back-and-forth method

В математической логике , в особенности теории множеств и модели теории , то метод назад и вперед представляет собой способ , показывающий изоморфизм между счетно бесконечных структур , удовлетворяющих заданным условиям. В частности, его можно использовать для доказательства того, что

• любые два счетно бесконечных плотно упорядоченных множества (т. е. линейно упорядоченных таким образом, что между любыми двумя членами есть еще один) без конечных точек изоморфны. Изоморфизм между линейными порядками - это просто строго возрастающая биекция . Этот результат означает, например, что существует строго возрастающая биекция между множеством всех рациональных чисел и множеством всех действительных алгебраических чисел .
• любые две счетно бесконечные безатомные булевы алгебры изоморфны друг другу.
• любые две эквивалентные счетные атомные модели теории изоморфны.
• модель Эрдеш-Рение из случайных графов , при применении к счетно бесконечным графам, всегда получалась уникальный график, график Rado .
• любые две многоместные полные рекурсивно перечислимых множества рекурсивно изоморфны.

Применение к плотно упорядоченным наборам

Например, для доказательства теоремы об изоморфизме Кантора можно использовать метод возвратно-поступательного движения , хотя это не было первоначальным доказательством Георга Кантора . Эта теорема утверждает, что два неограниченных счетных плотных линейных порядка изоморфны.

Предположим, что

• ( A , ≤ _A ) и ( B , ≤ _B ) - линейно упорядоченные множества;
• Оба они неограниченны, другими словами, ни A, ни B не имеют ни максимума, ни минимума;
• Они плотно упорядочены, т.е. между любыми двумя членами находится другой;
• Они счетно бесконечны.

Исправьте перечисления (без повторения) базовых наборов:

A = { a ₁ , a ₂ , a ₃ , ...},

B = { b ₁ , b ₂ , b ₃ , ...}.

Теперь построим взаимно однозначное соответствие между A и B , которое строго возрастает. Изначально ни один член А не спарен с любым членом B .

(1) Пусть я наименьший индекс таким образом, что _я еще не в паре с любым членом B . Пусть j будет некоторым индексом, таким, что b _j еще не спарен с каким-либо членом A, а a _i может быть спарен с b _{j в} соответствии с требованием, чтобы спаривание было строго возрастающим. Соедините a _i с b _j .

(2) Пусть J наименьший индекс таким образом, что б _J еще не в паре с любым членом A . Пусть i - некоторый индекс, такой, что a _i еще не спарен с каким-либо членом B, а b _j может быть спарен с a _{i в} соответствии с требованием, чтобы спаривание было строго возрастающим. Соедините b _j с a _i .

(3) Вернитесь к шагу (1) .

Еще необходимо проверить, что выбор, требуемый на шагах (1) и (2), действительно может быть сделан в соответствии с требованиями. На примере шага (1) :

Если уже есть _p и a _q в A, соответствующие b _p и b _q в B соответственно, такие, что a _p < a _i < a _q и b _p < b _q , мы выбираем b _j между b _p и b _q, используя плотность. В противном случае мы выбираем подходящий большой или маленький элемент B, используя тот факт, что B не имеет ни максимума, ни минимума. Выбор, сделанный на шаге (2) , возможен вдвойне. Наконец, построение заканчивается после счетного числа шагов, поскольку A и B счетно бесконечны. Обратите внимание, что мы должны были использовать все предпосылки.

История

Согласно Ходжесу (1993):

Возвратные методы часто приписываются Кантору , Бертрану Расселу и С. К. Лэнгфорду [...], но нет никаких доказательств, подтверждающих любую из этих атрибуций.

В то время как теорема о счетных плотно упорядоченных множествах принадлежит Кантору (1895 г.), метод возвратно-поступательного движения, с помощью которого она теперь доказывается, был разработан Эдвардом Вермили Хантингтоном (1904 г.) и Феликсом Хаусдорфом (1914 г.). Позже он был применен в других ситуациях, в первую очередь Роландом Фрейссе в теории моделей .

Смотрите также

• Игра Эренфойхта – Фраиссе

использованная литература

• Хантингтон, EV (1904), Континуум и другие типы последовательного порядка, с введением в трансфинитные числа Кантора , Harvard University Press
• Хаусдорф, Ф. (1914), Grundzüge der Mengenlehre
• Ходжес, Уилфрид (1993), теория моделей , Cambridge University Press , ISBN 978-0-521-30442-9
• Маркер, Дэвид (2002), Теория моделей: Введение , Тексты для выпускников по математике , Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-98760-6