Сергей Холодилов (fat_crocodile) wrote,
Сергей Холодилов
fat_crocodile

Categories:

Где спрятать лист

Писал когда-то про диагональную конструкцию Кантора, там от простого примера к более абстрактному один и тот же прием прослеживается. Внезапно ещё одна теорема из теории множеств проясняется похожим методом -- теорема Кантора-Бернштейна-Шредера.

Мощность
Мощность множества это обобщение понятия "количество элементов". Когда элементов становится бесконечно много, говорить о "количестве" уже не очень получается и нужно что-то придумывать. Вот, в частности придумали, как сказать, что у двух бесконечных множеств "равное количество" элементов:

Два множества называются равномощными, если существует взаимно однозначное отображение (биекция) между ними.

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

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

Например, понятно, что множество натуральных чисел {1,2,3,4,5,...} равномощно множеству квадратов натуральных чисел {1,4,9,16,25,...} . Биекция очевидная: число однозначно соответствует своему квадрату. Всё честно, определению удовлетворяет.

Но при этом же понятно, что квадратов "меньше" чем просто чисел, так как вон сколько мы пропустили: 2, 3, 5, 6 -- бесконечно много чисел пропустили, как же так. Осталось много голубей. С другой стороны, можно сделать так, что останется много клеток: сопоставить число и его квадрат, умноженный на 4. Все числа рассадим по клеткам и при этом ещё и половина клеток пустая окажется.

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


Простой пример
Множество N = {1,2,3,4, ...} и множество N' = {2,3,4,5, ...}. В множестве N одна лишняя точка, но это не проблема, биекцию можно сразу же предъявить: f: n --> n+1.

Тривиально, не стоило даже и писать, правда?

Пример посложнее
Полуинтервал (0, 1] и интервал (0, 1). Множества почти идентичны, вроде бы и делать ничего не надо, но в полуинтервале одна лишняя точка. Предыдущий пример подсказывает, как с ней можно поступить -- засунуть в начало бесконечной последовательности. Например так:

1 --> 1/2
1/2 --> 1/4
1/4 --> 1/8
...
1/2n --> 1/2n+1
...

т.е. мы вставили одну точку, "сдвинув" при этом все точки вида 1/2n "на один шаг", все остальные точки остались незатронутыми и их можно отобразить сами на себя.

Понятно, что делать если у нас две лишние точки, например если множества [0, 1] и (0, 1)? Если 10?
Понятно, что выбранная последовательность ничем не волшебная, можно было бы взять 1/n или 1/3n? Можно было и не монотонную, тут главное чтобы без повторов.


Пример на плоскости
Круг с радиусом 1, включающий границу и такой же круг, но уже без границы. Теперь у нас одна лишняя окружность. Куда её? Правильно, в бесконечную последовательность окружностей. То есть:

окружность радиусом 1 --> окружность радиусом 1/2
окружность радиусом 1/2 --> окружность радиусом 1/4
окружность радиусом 1/4 --> окружность радиусом 1/8
...
окружность радиусом 1/2n --> окружность радиусом 1/2n+1
...

Две окружности разных радиусов друг другу очевидно равномощны, надеюсь, это не надо пояснять.

То есть, опять, точки, лежащие на окружностях радиуса 1/2n, "сдвигаются на шаг". Остальные точки отображаются сами на себя, биекция готова.

Теорема Кантора-Бернштейна-Шредера - 1
Для начала нужно ещё одно определение: говорят, что мощность множества X не больше, чем мощность множества Y, если X равномощно подмножеству Y.

Довольно логично -- равномощно подмножеству, значит элементов по крайней мере не больше. Проблема в том, что делать, если X равномощно подмножеству Y, а Y при этом равномощно подмножеству X. Множества бесконечные, речь уже не идет о числах, нельзя просто сказать "тогда значит равны" -- надо доказать. Именно это и называется теоремой.

Не совсем она, но эквивалентная формулировка звучит так: если Z ⊂ Y ⊂ X и при этом X равномощно Z, то X равномощно Y.

Выглядит это как-то так:


Надо построить биекцию X --> Y. И тут в множестве X ... один лишний "слой". Как у луковицы. Но уже понятно, что с ним делать -- конечно поставить в бесконечную последовательность таких же слоев.

Ну то есть, примерно так: нам дано, что X равномощно Z, значит существует биекция f: X --> Z. Теперь, рассмотрим множество L = X \ Y (это тот самый лишний слой, от слова layer). Предлагается следующее отображение:

L --> f(L)
f(L) --> f(f(L))
...
fn(L) --> fn+1(L)
...

а остальные элементы X отображаются сами на себя. То же самое, немного более строго:

если x ∈ U(fn(L)), где n ∈ {1,2, ...}, то x --> f(x)
иначе x --> x

т.е. если x лежит в каком-то из "слоев", то перейти в следующий "слой", иначе ничего не делать.

Теорема Кантора-Бернштейна-Шредера - 2
Ну и последний шаг, раз уж начали: почему из доказанного собственно следует искомая теорема.

X равномощно некоторому X' ⊂ Y, значит есть биекция f: X --> X'
Y равномощно некоторому Y' ⊂ X, значит есть биекция g: Y --> Y'

g(X') = X'' ⊂ Y' ⊂ X
И композиция f и g функция gf: X --> X'' это биекция

То есть пришли к начальным условиям доказанной выше теоремы: X'' ⊂ Y' ⊂ X и X равномощно X''. Отсюда, по доказанному, X равномощно Y', а значит и Y тоже. Что и требовалось доказать.

Теперь можно посмотреть доказательство в википедии и плакать, плакать от того, что всё равно ничерта не понятно может быть, зная суть, удастся что-то разобрать в этой последовательности значков.
Tags: математика
Subscribe

  • (no subject)

    Очень простую штуку объяснили, как-то мимо проходила. В книжках про ассемблер и прочее такое пишут про "представление отрицательных чисел в…

  • (no subject)

    Наконец вроде осознал, когда и зачем аксиома выбора нужна, а когда она не нужна. Если у нас есть одно непустое множество X и нам нужно взять…

  • CRC-3: как его обойти

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

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 11 comments

  • (no subject)

    Очень простую штуку объяснили, как-то мимо проходила. В книжках про ассемблер и прочее такое пишут про "представление отрицательных чисел в…

  • (no subject)

    Наконец вроде осознал, когда и зачем аксиома выбора нужна, а когда она не нужна. Если у нас есть одно непустое множество X и нам нужно взять…

  • CRC-3: как его обойти

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