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

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

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

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

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

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

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

А = { а₁, а₂, а₃, … },

B = { б₁, б₂, б₃, … }.

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

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

(2) Позволять j наименьший индекс такой, что б_j еще не связан ни с одним членом А. Позволять я - некоторый индекс такой, что а_я еще не связан ни с одним членом B и б_j может быть в паре с а_я в соответствии с требованием, чтобы спаривание было строго возрастающим. Пара б_j с участием а_я.

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

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

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

История

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

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

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

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

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

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

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