Category: птицы

Category was added automatically. Read all entries about "птицы".

wall

Верхний пост

Всем привет.

Я мало френжу, простите.
У меня есть привычка читать всю ленту и ввязываться в дискуссии, из-за этого приходится держать количество друзей (особенно, активно пишуших друзей) в разумных пределах.

Я не пишу под замок. Сейчас "под глазиком" лежит n штук недописанных постов, под замком один пост с оффлайновыми контактами. И может быть ещё что-то случайное из давней древности.

Если хочется сказать что-то не по теме, это можно сделать тут.
Если что, писать можно на толстый-крокодил@yandex.ru -- как название журнала, но не подчёркивание а дефис.
wall

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

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

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

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

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

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

Например, понятно, что множество натуральных чисел {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). Множества почти идентичны, вроде бы и делать ничего не надо, но в полуинтервале одна лишняя точка. Предыдущий пример подсказывает, как с ней можно поступить Collapse )

Теорема Кантора-Бернштейна-Шредера - 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 тоже. Что и требовалось доказать.

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