Теорема Кантора об изоморфизме - Cantor's isomorphism theorem

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

Примеры

Функция вопросительного знака Минковского обеспечивает конкретный изоморфизм рациональных чисел в диадические рациональные числа.

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

Общий порядок или линейный порядок является плотным , когда каждые два элемента для того , есть еще один элемент между ними. Неограниченность означает, что порядок не имеет минимального или максимального элемента. Как для рациональных чисел, так и для диадических рациональных чисел не существует минимума или максимума, и элемент может быть найден между любыми двумя элементами, взяв их среднее значение . Оба эти множества счетны; счетность рациональных чисел также наблюдалась Кантором, а счетность диадических рациональных чисел следует из того факта, что они являются подмножеством рациональных чисел. Следовательно, они изоморфны друг другу и всем остальным счетным плотным линейным порядкам без концов.

Эти числа являются счетны и не имеют конечных точек, но не плотно: нет целого числа от 0 до 1. действительных чисел плотны и не имеют конечных точек, но не счетны. Следовательно, теорема Кантора неприменима к этим порядкам.

Доказательства

Одно доказательство теоремы Кантора об изоморфизме, в некоторых источниках называемое «стандартным доказательством», использует метод возвратно-поступательного движения . Это доказательство строит изоморфизм между любыми двумя заданными порядками, используя жадный алгоритм , в порядке, заданном счетным перечислением двух порядков. Более подробно, доказательство поддерживает два изоморфных по порядку конечных подмножества и двух данных порядков, изначально пустых. Он многократно увеличивает размеры и путем добавления нового элемента из одного порядка, первого отсутствующего элемента в его перечисление, и сопоставления его с эквивалентным порядку элементом другого порядка, существование которого доказано с использованием плотности и отсутствия конечных точек порядок. Он чередуется между двумя порядками, для которых он ищет первый отсутствующий элемент, и какой он использует для поиска совпадающего элемента. Каждый элемент каждого порядка в конечном итоге сопоставляется с эквивалентным порядку элементом другого порядка, поэтому два порядка изоморфны. ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$

Хотя метод возвратно-поступательного движения также был приписан Кантору, в первоначальной публикации Кантором этой теоремы в 1895–1897 годах использовалось другое доказательство. В исследовании истории этой теоремы логиком Чарльзом Л. Силвером самый ранний пример обратного доказательства, найденного Сильвером, был в учебнике 1914 года Феликса Хаусдорфа .

Вместо того, чтобы создавать подмножества, изоморфные по порядку, и переходить «туда-сюда» между перечислением для первого порядка и перечислением для второго порядка, в исходном доказательстве Кантора используется только «идущая вперед» половина метода возвратно-поступательного движения. . Многократно усиливает два конечных множества и путем добавления к раннему недостающему элементу перечисления первого порядка, и добавлению к заказу-эквивалентного элементу , который является ранним в перечислении второго заказа. Это, естественно, обнаруживает эквивалентность между первым порядком и подмножеством второго порядка, и Кантор затем утверждает, что включен весь второй порядок. ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$

Теория моделей

Теорема Кантора об изоморфизме может быть выражена на языке теории моделей , сказав, что теория первого порядка неограниченных плотных линейных порядков счетно категорична . Рациональные числа представляют собой насыщенную модель этой теории. Однако эта теория не является категоричной для высших мощностей .

Связанные результаты

Тот же метод, который использовался для доказательства теоремы Кантора об изоморфизме, также доказывает, что любые два набора точек в неограниченном плотном счетном линейном порядке могут быть отображены друг в друга с помощью порядкового автоморфизма . Это также можно доказать непосредственно для упорядочения рациональных чисел, построив кусочно-линейный автоморфизм порядка с точками излома в заданных точках. В этом смысле группа симметрий такого порядка называется «очень однородной», даже если она не является 2-транзитивной группой (пары точек не могут быть заменены друг на друга с помощью симметрии, потому что это изменило бы их заказ). ${\ displaystyle k}$${\ displaystyle k}$

Теорема об изоморфизме может быть распространена на системы любого конечного или счетного числа линейно упорядоченных неограниченных множеств, каждое из которых плотно друг в друге. Все такие системы с одинаковым числом наборов изоморфны по порядку при любой перестановке их наборов. Bhattacharjee et al. (1997) приводят в качестве примера разделение рациональных чисел на диадические рациональные числа и их дополнение; эти два множества плотны друг в друге, и их объединение имеет порядковый изоморфизм любой другой паре неограниченных линейных порядков, счетных и плотных друг в друге. В отличие от теоремы Кантора об изоморфизме, для доказательства нужен полный аргумент туда и обратно, а не только аргумент «вперед».

Кантор использовал теорему об изоморфизме, чтобы доказать, что любой полный по Дедекинду линейный порядок, содержащий плотное подмножество, изоморфное рациональным числам, должен быть изоморфен действительным числам . Проблема Суслина спрашивает, должны ли порядки, обладающие некоторыми другими свойствами порядка действительных чисел, включая неограниченность, плотность и мощность континуума, быть порядково-изоморфными действительным числам; его правда не зависит от ZFC .

Другое следствие доказательства Кантора состоит в том, что любой конечный или счетный линейный порядок может быть вложен в рациональные числа или в любой неограниченный плотный порядок. Назвав это «хорошо известным» результатом Кантора, Вацлав Серпинский доказал аналогичный результат для более высокой мощности: предполагая гипотезу континуума , существует линейное упорядочение мощности, в которое могут быть вложены все другие линейные упорядочения мощности . Аксиома Баумгартнера касается плотных множеств действительных чисел, неограниченных множеств с тем свойством, что каждые два элемента разделяются точно другими элементами. Он утверждает, что каждые два таких множества изоморфны по порядку, обеспечивая таким образом другой аналог более высокой мощности теоремы об изоморфизме Кантора. Это согласуется с ZFC и отрицанием гипотезы континуума и подразумевается соответствующей аксиомой принуждения , но не зависит от аксиомы Мартина . ${\ displaystyle \ aleph _ {1}}$${\ displaystyle \ aleph _ {1}}$${\ displaystyle \ aleph _ {1}}$${\ displaystyle \ aleph _ {1}}$

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