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

Category:

Диагональная конструкция Кантора

Простая очень вещь, но что-то я только сейчас сообразил, что это всё один и тот же приём, применяемый к разным данным.

Несчётность множества бесконечных последовательностей 0 и 1
Обозначим множество бесконечных последовательностей 0 и 1 как {0,1}.

Классическое доказательство. Пусть это множество счётно, тогда, по определению, существует биекция f: N --> {0,1}. Нарисуем табличку из двух столбцов, в первом натуральное число, во втором -- соответствующая ему последовательность 0,1. Как-то так (что выделено красным -- ниже):

1 --> 000100010111...
2 --> 010101110001...
3 --> 10001111100100...
4 --> 00010100111
...
n --> 10111100000111...00110...
...

По предположению, все элементы {0,1} вошли в эту (конечно, бесконечную) таблицу. А теперь построим последовательность, которой в ней нет. Очень просто. От первой строки она будет отличаться в первой цифре, от второй -- во второй, от третьей -- в третьей и т.п.
Для приведённого примера нужно инвертировать красные цифры, получим

1010 ... 0 ...

Получили противоречие, значит предположение неверно, значит множество несчётно. Использованный приём называется диагональной конструкцией.

Отсюда обычно получают несчётность R, сопоставляя его и рассмотренное множество последовательностей, но сейчас это немного в стороне от моей мысли.

Несчётность множества подмножеств N
Множество подмножеств N и {0,1} это почти одно и то же. Биекция задаётся следующим образом:

если число n принадлежит подмножеству X, то в соответствующей X последовательности n-й разряд это 1, иначе 0.

Так что на этом можно было бы доказательство и закончить. Но это не поможет нам дальше, поэтому вместо этого проведём те же рассуждения для этого случая, они менее наглядны, но если держать в голове предыдущий случай, преемственность очевидна. Множество подмножеств N обозначим 2N.

Итак, пусть это множество счётно, тогда, по определению, существует биекция f: N --> 2N. Нарисуем табличку из двух столбцов, в первом натуральное число, во втором -- соответствующее ему подмножество N. Как-то так:

1 --> {4, 8, 10, 11, 12, ...}
2 --> {2, 4, 6, 7, 8, 12, ... }
3 --> {1, 5, 6, 7, 8, 9, 12, ...}
4 --> {4, 6, 9, 10, 11, ...}
...
n --> {1, 2, 3, 4, 5, 12, 13, 14, ..., n-1, n, ...}
...

По предположению, в этой таблице содержатся все подмножества N. Построим подмножество, которого там нет. От каждой строчки таблицы оно будет отличаться наличием/отсутствием соответствующего элемента. То есть, если в первой строчке таблицы в подмножестве 1 есть, её не берём, иначе берём. И т.д. Это записывается так:

А = {x ∈ N | x ∉ f(x)}

Т.е. в A будут только те элементы N, которые отсутствуют в соответствующих себе строчках (а если таких нет? ничего не изменится, пустое множество ни чем не хуже прочих).

Противоречие, доказано.

Теорема Кантора: множество подмножеств X не равномощно X
Ещё менее наглядный случай, но тоже можно проследить преемственность с предыдущим.

Пусть это не так. Тогда, по определению, существует биекция f: X --> 2X. Тогда рассмотрим A ⊂ X:

А = {x ∈ X | x ∉ f(x)}

Если f задана, то определение A корректно -- для каждого x ∈ X мы можем понять, содержится он в A или нет. По предположению, существует a ∈ X: f(a) = A.

Если a ∈ f(a), то, по построению A, a ∉ A
Если a ∉ f(a), то, по построению A, a ∈ A

Так как A = f(a), получили противоречие, утверждение доказано.

Парадокс Рассела
Что предыдущее это более менее одно и то же мне было понятно и раньше. А посетивший меня несложный инсайт состоял в том, что и парадокс Рассела это тоже то же самое.

Рассмотрим множество A, содержащее все множества, такие, что они не содержат себя в качестве элемента

A = {X | X ∉ X}

Содержит ли оно само себя?

Если A ∈ A, то, по построению A, A ∉ A
Если A ∉ A, то, по построению A, A ∈ A

Противоречие. Вывод: нельзя строить множества таким образом. Отсюда есть пошла аксиоматическая теория множеств, объясняющая, как их строить можно.

А мне интересно было поставить парадокс Рассела в ряд аналогичных рассуждений.
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.
  • 15 comments

  • (no subject)

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

  • (no subject)

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

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

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