WikiDer > Возвратно-поступательный метод

Back-and-forth method

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


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

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

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

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

А = { а1, а2, а3, … },
B = { б1, б2, б3, … }.

Теперь построим взаимно однозначное соответствие между А и 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