Теорема о неравномощности множеств

[Mikhail_K]

gogoshik в сообщении #1212316 писал(а):

"его" - это чей, подмножества $B$?

Да, но рассматриваемого не как подмножество, а как элемент множества $2^A$. Может, проблема в понимании у Вас связана с этим?

[Odysseus]

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

Главный прием, и главная психологическая сложность в этой теореме, это постулирование множества $B = \{x \in A \mid x \notin f(x)\}$. После этого все сводится к противоречию очень быстро, но само множество $B$ в самом деле выглядит немного странно. Интуитивно может быть не очень понятно что это зверь и почему он должен существовать, даже если вы знаете про аксиому выделения.

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

И такая абстрактная конструкция для $B$, в силу своей общности, вполне может оказаться и просто пустым множеством, т.е. биекция от $A$ в $2^A$ не состоится по одной, казалось бы, "очень маленькой причине": просто не будет элемента из $A$, который будет соответствовать пустому множеству из $2^A$. В каких случаях так может быть? А вот как раз в случаях самых маленьких множеств для которых мы применяем эту теорему, для $A$ - пустого множества и для $A$ - состоящего из одного элемента. В первом случае, $2^A$ будет состоять из одного элемента - пустого множества, но для него не будет элемента из $A$, который можно было бы туда отобразить, просто потому что в $A$ нет ни одного элемента вообще. (Здесь важно понимать, что в $A$ есть одно подмножество - пустое множество, но это не элемент $A$! А когда мы рассматриваем все его подмножества $2^A$, то там пустое множество будет уже элементом $2^A$!). В принципе, уже этого случая достаточно, но можно посмотреть и на второй. Во втором случае, $2^A$ будет состоять из двух элементов: всего множества $A$ и пустого множества, т.е. одного элемента $A$ на них двух тоже не хватит. Допустим, мы отобразим элемент из $A$ на все множество $A$, но тогда пустое множество (второй элемент в $2^A$) останется без партнера.

Видите что получается? Мы доказываем теорему для любых множеств, от конечных (включая пустое множество) до бесконечных любой мощности, но из-за подобной общности она не может быть "сильнее", чем самые простые случаи, которые она покрывает, т.е. $B$ вполне может быть пустым множеством. Если это понять, то психологических сложностей с ней больше не должно быть.

[gogoshik]

Mikhail_K в сообщении #1212321 писал(а):

Да, но рассматриваемого не как подмножество, а как элемент множества $2^A$. Может, проблема в понимании у Вас связана с этим?

Хм ... Странные вещи получаются. Это я вполне понял. Спасибо всем кто объяснял.

И как сказал Odysseus, действительно трудно представить себе множество $B$ c таким условием, которое не отвечает биективности. Если мы раньше сказали, что существует взаимно однозначное отображение между $A$ и $2^A$, то логично ожидать, что для любого элемента $x \in A$ можно указать его образ $f(x)$ в $2^A$.

[Mikhail_K]

gogoshik в сообщении #1212329 писал(а):

действительно трудно представить себе множество $B$ c таким условием, которое не отвечает биективности. Если мы раньше сказали, что существует взаимно однозначное отображение между $A$ и $2^A$, то логично ожидать, что для любого элемента $x \in A$ можно указать его образ $f(x)$ в $2^A$

Почему это "не отвечает биективности"? Действительно, если мы сказали, что взаимно однозначное отображение $f$ существует, то для любого элемента $x\in A$ существует образ $f(x)\in 2^A$ (или, что то же самое, $f(x)\subset A$). Но это ничего не говорит о том, будет ли $x$ лежать внутри этого множества $f(x)\subset A$ или вне его. А вот определяя $B$, мы обращаем на это внимание.

[mihaild]

Тут кажется тоже достаточно стандартное непонимание, вызванное доказательством от противного. ИМХО оно ("от противного") тут не нужно. Можно так: возьмем какое-нибудь отображение $f : A \to 2^A$. По нему строится $B_f = \{x | x \in A, x \notin f(x)\}$. Методом пристального взгляда доказываем, что ни для какого $y \in A$ не получится $f(y) = B$. Значит, $B$ не лежит в образе $f$, и, следовательно, $f$ - не биекция.
Т.к. $f$ было произвольным отображением, то биекций (и даже сюръекций) $A \to 2^A$ не бывает.

[Odysseus]

gogoshik в сообщении #1212329 писал(а):

И как сказал Odysseus, действительно трудно представить себе множество $B$ c таким условием, которое не отвечает биективности.

Я не говорил, что определение $B$ не отвечает биективности :) В его определении же стоит $B = \{x \in A \mid x \notin f(x)\}$, а не что-то типа $B = \{x \in A \mid x \not\rightarrow f(x)\}$ или $B = \{x \in A \mid x \not\rightarrow B\}$.

Как раз напротив. Поскольку $B$ это одно из подмножеств $A$, просто по определению понятия "подмножество", а значит и элемент $2^A$, то в случае наличия биективного отображения из $A$ в $2^A$ должен найтись $y \in A$ такой, что $y \rightarrow B$. И вот с последним как раз вдруг оказываются проблемы. Заранее таких проблем в определении $B$ мы вовсе не постулируем. Просто множество $B$ оказалось таким "кривым", что никакое $y \in A$ перейти в него просто не может.

И я также не говорил, что $B$ трудно представить. Нет совершенно никаких проблем в том, чтобы представить множество $B$, которое удовлетворяет условию $B = \{x \in A \mid x \notin f(x)\}$. Допустим, у вас $A=\{1, 2\}$, тогда $2^A=\{\{\varnothing\}, \{1\}, \{2\}, \{1, 2\}\}$ Какие проблемы представить отображение из $A$ в $2^A$, которое переводит $1$ в $\{2\}$? В данном случае $1$ как раз и будет элементом $B = \{x \in A \mid x \notin f(x)\}$.

Я говорил, что интуитивно может быть не очень понятно почему такое множество $B$ должно существовать для любых отображений из $A$ в $B$. Но тут уж ничего не поделаешь, оно существовать просто обязано по аксиоме выделения. В крайнем случае, $B$ будет просто пустым множеством, что тоже представить легко (например в случаях, когда $A$ это "маленькое" множество: или пустое, или из одного элемента), и что как я показал на примерах "маленьких множеств" будет противоречить биективности отображения ровно в такой же степени, как если бы $B$ было непустым.

[gogoshik]

mihaild в сообщении #1212331 писал(а):

Почему это "не отвечает биективности"? ...

Odysseus в сообщении #1212338 писал(а):

Я не говорил, что определение $B$ не отвечает биективности :) ...

Вы правы. Это я тут неправильно понял.

mihaild в сообщении #1212331 писал(а):

Методом пристального взгляда доказываем

Что это за метод такой

Odysseus в сообщении #1212338 писал(а):

просто множество $B$ оказалось таким "кривым", что никакое $y \in A$ перейти в него просто не может

В силу биективности оно разве не может?

[Odysseus]

gogoshik в сообщении #1212342 писал(а):

mihaild в сообщении #1212331 писал(а):

Методом пристального взгляда доказываем

Что это за метод такой

Вы шутите или никогда не встречали такое выражение? Это просто жаргон, означающий что доказательство очевидно. Ну или посмотрите пристально на предложения 3-5 из ссылки на доказательство, которое вы привели ранее.

gogoshik в сообщении #1212342 писал(а):

Odysseus в сообщении #1212338 писал(а):

просто множество $B$ оказалось таким "кривым", что никакое $y \in A$ перейти в него просто не может

В силу биективности оно разве не может?

Мы не знаем заранее "может или нет". Мы знаем только, что для биективного отображения из $A$ в $2^A$ такое $y$ обязано найтись. Но оказывается, что его быть никак не может. Значит отображение не биективно. ЧТД.

[gogoshik]

Odysseus в сообщении #1212338 писал(а):

Допустим, у вас $A=\{1, 2\}$, тогда $2^A=\{\{\varnothing\}, \{1\}, \{2\}, \{1, 2\}\}$ Какие проблемы представить отображение из $A$ в $2^A$, которое переводит $1$ в $\{2\}$? В данном случае $1$ как раз и будет элементом $B = \{x \in A \mid x \notin f(x)\}$.

Это хороший пример! Спасибо.
А как Вы в таком случае запишите биекцию между $A$ и $2^A$?

[Odysseus]

gogoshik в сообщении #1212350 писал(а):

А как Вы в таком случае запишите биекцию между $A$ и $2^A$?

Никак :) Догадываетесь почему? Подсказка: ее нет и быть не может.

Теорема Кантора доказывает это в общем случае для любых множеств через конструирование множества $B$ (которое есть элемент $2^A$), в который не может перейти ни один из элементов множества $A$. А в данном частном случае исходного множества $A$ из $2$ элементов это можно элементарно доказать и непосредственно. Не может же быть биекции между конечными множествами состоящими из разного количества элементов, а у нас $2$ элемента в множестве $A$ и $4$ элемента в множестве $2^A$.

[gogoshik]

Odysseus в сообщении #1212352 писал(а):

Никак :) Догадываетесь почему? Подсказка: ее нет и быть не может.

Действительно получается очень даже прикольно :) Ведь мы в самом начале предполагаем что биекция существует. Получается, что в общем случае такую биекцию и представить то немыслимо. Всем интуитивно понятно что мощность $2^A$ больше $A$ из простых арифметических соображений.

[mihaild]

gogoshik в сообщении #1212354 писал(а):

Ведь мы в самом начале предполагаем что биекция существует.

Вы знаете, что такое "доказательство от противного"? Это доказательство вида "Пусть $X$, тогда $<\ldots>$, получили противоречие. Следовательно, $X$ неверно".

[gogoshik]

Знаю. Мы хотим доказать что взаимно однозначное соответствие не существует. Предполагаем что оно существует. И получается что сделав такое предположение мы приходим логически последовательно к противоречию. Доказательство, которое написано в линке на wiki, я теперь понимаю.
Спасибо!
Просто некоторые шаги логической последовательности были не очень понятны. Если абстрагироваться (не требуя конкретных примеров) то вполне прокатит.

[Someone]

Odysseus в сообщении #1212338 писал(а):

а не что-то типа $B = \{x \in A \mid x \not\rightarrow f(x)\}$ или $B = \{x \in A \mid x \not\rightarrow B\}$.

Что-то невнятное, на мой взгляд. Что это должно означать?

mihaild в сообщении #1212331 писал(а):

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

Ага.

mihaild в сообщении #1212331 писал(а):

Значит, $B$ не лежит в образе $f$, и, следовательно, $f$ - не биекция.

Не сюръекция. Биективность или инъективность тут только мешаются. Но если мы доказали, что нет сюръекции, то, разумеется, биекции тоже нет.

gogoshik в сообщении #1212354 писал(а):

Ведь мы в самом начале предполагаем что биекция существует.

Вслед за mihaild, категорически рекомендую не делать такого предположения и вообще не использовать метод "от противного". Это только заморачивает мозги. Прямо доказываем, что произвольно взятое отображение $f\colon A\to 2^A$ не является сюръекцией.

[Odysseus]

gogoshik в сообщении #1212354 писал(а):

Получается, что в общем случае такую биекцию и представить то немыслимо. Всем интуитивно понятно что мощность $2^A$ больше $A$ из простых арифметических соображений.

А вот такого не надо. $2^A$ это просто обозначение, которое соответствует реальной степени лишь для конечных множеств (если $a$ это число элементов в конечном множестве $A$, то в множестве всех его подмножеств, обозначаемом $2^A$, будет $2^a$ элементов).

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

Так уж сложилось, что мы конечные, поэтому нам сложно представить все бесконечное (а еще, например, мы трехмерные, поэтому нам сложно представить четырехмерное, пятимерное и т.д.). Слишком слабая у человека интуиция, чтобы применять ее для бесконечных множеств не рассмотрев до этого 100500 примеров и теорем. Только после этого плиз.

-- 24.04.2017, 11:37 --

Someone в сообщении #1212364 писал(а):

Odysseus в сообщении #1212338 писал(а):

а не что-то типа $B = \{x \in A \mid x \not\rightarrow f(x)\}$ или $B = \{x \in A \mid x \not\rightarrow B\}$.

Что-то невнятное, на мой взгляд. Что это должно означать?

gogoshik считал, что исходное определение множества $B = \{x \in A \mid x \notin f(x)\}$ сразу означает, что в множество $B$ не переходит никакой элемент $x$ из $A$. Я в ответ подчеркивал, что это значит только то, что $x \notin f(x)\, но заранее еще не значит, что $x \not\rightarrow B\ (т.е. заранее не значит, что $ f(x) \ne B}$).