Доказательство теоремы о мощности множества подмножеств

[korablique]

Теорема: $cardX < card \rho(X)$, $\rho(X)$ - множество всех подмножеств $X$.
Для пустого множества очевидно. Для непустого $\rho(X)$ содержит все одноэлементные подмножества $X$, поэтому $cardX \leqslant card \rho(X)$. Остаётся доказать, что равенства быть не может.
Доказательство ведётся от противного - предполагается, что существует множество, равномощное множеству его подмножеств. Тогда существует биекция $f:X \to \rho(X)$. Далее рассматривается множество $A = \{x \in X : x \notin f(x)\}$. А зачем его рассматривать, если и так понятно, что множество всех подмножеств как минимум содержит все одноэлементные подмножества $X$ и $\varnothing$, а это уже больше мощности $X$?

[ET]

korablique в сообщении #1498641 писал(а):

А зачем его рассматривать, если и так понятно, что множество всех подмножеств как минимум содержит все одноэлементные подмножества $X$ и $\varnothing$, а это уже больше мощности $X$?

С чего бы это было больше?
Это только для конечных множеств больше, и то , и это доказывать вообще-то надо
А теорема для всех

[Odysseus]

Это "и так понятно" только для конечных множеств, но для бесконечных из того, что $A$ является собственным подмножеством $B$ следует только $cardA \leqslant cardB$, но не $cardA < cardB$. Например, множество целых чисел вложено в множество рациональных, но эти два множества имеют одинаковую мощность.

[ET]

Ладно, давайте так:
Докажите, что Множества натуральных и целых чисел равномощны (ни одно из них НЕ больше другого)

[warlock66613]

korablique в сообщении #1498641 писал(а):

и так понятно, что множество всех подмножеств как минимум содержит все одноэлементные подмножества $X$ и $\varnothing$, а это уже больше мощности $X$?

Так можно "доказать" и что мощность множества целых чисел больше множества натуральных: ведь множество целых чисел содержит все натуральные, да ещё и отрицательные. Но на самом деле эти мощности равны. Поэтому надо аккуратно делать все рассуждения.

Вот кстати,

korablique в сообщении #1498641 писал(а):

Для непустого $\rho(X)$ содержит все одноэлементные подмножества $X$, поэтому $cardX \leqslant card \rho(X)$.

А вы понимаете, что здесь подразумевается под "поэтому"?

[Someone]

korablique в сообщении #1498641 писал(а):

Доказательство ведётся от противного - предполагается, что существует множество, равномощное множеству его подмножеств.

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

Я всегда пользовался обозначением $\lvert A\rvert$ для мощности множества, поэтому так и буду писать вместо вашего $card A$ (кстати, гораздо лучше выглядит $\operatorname{card}A$).

Но хотелось бы видеть точные определения следующих понятий:
1) множества $A$ и $B$ равномощны, то есть, $\lvert A\rvert=\lvert B\rvert$;
2) множество $A$ имеет мощность не большую, чем множество $B$, то есть, $\lvert A\rvert\leqslant\lvert B\rvert$;
3) множество $A$ имеет мощность меньшую, чем множество $B$, то есть, $\lvert A\rvert<\lvert B\rvert$.

Боюсь, без этих определений (и, возможно, ещё некоторых) мы будем долго блуждать в трёх соснах.

[korablique]

warlock66613 в сообщении #1498648 писал(а):

А вы понимаете, что здесь подразумевается под "поэтому"?

Что?

-- 03.01.2021, 16:05 --

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

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

А почему оно не от противного? Нужно же доказать, что биекции нет, и предполагаем, что она есть. Разве не от противного?

[warlock66613]

korablique в сообщении #1498735 писал(а):

Что?

То есть не понимаете? Тогда начните с ответа на вопросы Someone.

[korablique]

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

1) множества $A$ и $B$ равномощны, то есть, $\lvert A\rvert=\lvert B\rvert$;
2) множество $A$ имеет мощность не большую, чем множество $B$, то есть, $\lvert A\rvert\leqslant\lvert B\rvert$;
3) множество $A$ имеет мощность меньшую, чем множество $B$, то есть, $\lvert A\rvert<\lvert B\rvert$.

1) существует инъекция $f:A \to B$
2) существует сюръекция $f:A \to B$
3) существует инъекция, но нет биекции

[Odysseus]

Кажется, вы наугад говорите.
1) Неправильно. Инъекция-то существует, но ее недостаточно, т.е. правильного определения у вас нет.
2) Неправильно. Данная сюръекция может и существовать в каких-то случаях при $\lvert A\rvert\leqslant\lvert B\rvert$ (в каких?), но к нужному определению это отношения не имеет.
3) Правильно только частично (а значит, тоже неправильно, поскольку, строго говоря, "частично правильного" в математике нет). Во-первых, нужно было указать откуда и куда ведет инъекция. Во-вторых, что значит "нет биекции"? Может просто у вас ее нет (не придумали), а у кого-то другого есть. Правильнее говорить "не существует".

Не нужно срезать углы и опускать подробности, особенно при самом первом ознакомлении с чем-то. Рекомендую
- Вспомнить и привести подробные определения произвольного отображения между множествами, инъекции, сюръекции, биекции.
- Проиллюстрировать их на каких-то конкретных отображениях, сначала между конкретными конечными множествами, потом между бесконечными.
- Дать определение и примеры счетного множества, несчетного множества.
- Привести характерные свойства счетных множеств, несчетных множеств, бесконечных множеств в целом.

И кстати, по какому учебнику вы учите теорию множеств? Для первого ознакомления рекомендую первую главу Александрова "Введение в теорию множеств и общую топологию" и первую главу Калужнина "Введение в общую алгебру".

-- 03.01.2021, 06:55 --

korablique в сообщении #1498735 писал(а):

А почему оно не от противного? Нужно же доказать, что биекции нет, и предполагаем, что она есть. Разве не от противного?

Потому что в доказательстве на которое вы ссылаетесь нет никакой необходимости предполагать, что биекция есть. Суть доказательства в том, что берется произвольное отображение $f:X \to \rho(X)$ и явно строится подмножество $X$, т.е. элемент $\rho(X)$, в которое не может переходить никакой элемент из $X$ при данном отображении $f$. Из этого следует, что $f$ это не сюръекция. А с учетом произвольности взятых множества $X$ и отображения $f$ (конкретный вид $X$ и $f$ в доказательстве не используется, т.е. они могут быть любыми) из этого следует, что сюръекции между $X$ и $\rho(X)$ не может существовать вообще. А поскольку инъекция существует, то $\lvert X\rvert<\lvert \rho(X)\rvert$.

Предварять все это словами "предположим, что существует множество, равномощное множеству его подмножеств, т.е. существует биекция $f:X \to \rho(X)$" не добавляет к доказательству ничего полезного, а может только запутывать. Это все равно, как при доказательства теоремы Пифагора предположить, что она неверна, потом ее явно доказать, а потом сказать, что предположение было неверным, и значит мы "доказали это от противного".

Подобное явное построение элемента второго множества в который не может перейти никакой элемент из первого это главная идея т.н. диагонального метода Кантора. Так доказывается, например, также то, что мощность множества вещественных чисел больше мощности множества натуральных чисел. Но в доказательстве неравномощности множества и множества его подмножеств на которое ссылаетесь вы, этот диагональный метод используется несколько иначе, и поэтому кому-то может казаться не таким ясным и "конструктивным". Рекомендую разобрать еще один способ этого доказательства, который есть в Александрове "Введение в теорию множеств и общую топологию", глава 1, § 6, теоремы 15 и 16. Это более "прямой" способ, и при этом выстраиваемая структура и логика рассуждений практически идентичны диагональному методу доказательства неравномощности множеств натуральных и вещественных чисел. После этого постарайтесь понять в чем эти два способа доказательства близки, и как первый способ можно немного переформулировать на языке близком ко второму.

[korablique]

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

Кажется, вы наугад говорите.

Да, извиняюсь, у меня тут в тетради похожий вопрос написан, и я ответила на него, а не на тот, что мне задали
1) существует биекция $f: A \to B$
2) существует инъекция $f: A \to B$
3) существует инъекция $f: A \to B$, но не существует биекции

-- 03.01.2021, 22:11 --

Odysseus
За рекомендации спасибо

[Padawan]

(Оффтоп)

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

Для первого ознакомления рекомендую первую главу Александрова "Введение в теорию множеств и общую топологию"

Её и не для первого ознакомления позаглаза хватит (если понять всё, что там написано)

[Odysseus]

(Оффтоп)

Padawan в сообщении #1498851 писал(а):

Её и не для первого ознакомления позаглаза хватит (если понять всё, что там написано)

С этим я больше согласен, чем нет. Хотя, например, теорема Кантора-Бернштейна намного понятнее доказана у Верещагина и Шеня. И про кардинальные числа и их арифметику может быть полезно где-то почитать. Ну и явно полезно задачки порешать.

Мой пойнт был несколько в другом. Есть много учебников по теории множеств, но эта глава из Александрова, как и первая глава из Калужнина, это ИМХО самые удачные введения в предмет с точки зрения сочетания простоты/понятности и хорошей подборки материала. Далее, при желании, можно углубляться и дальше, но обычно только если что-то дополнительное явно понадобится.

[ewert]

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

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

Но, между прочим, стандартно доказательства несчётности вещественных чисел принято оформлять именно от противного: предположим, что биекция существует -- и диагональным методом придём к противоречию.

Это, естественно, не более чем вопрос стилистики. Утверждения "никакая инъекция не может быть биекцией" и "существование биекции внутренне противоречиво" означают ровно одно и тоже, лишь словесное оформление различно. Ну разве что первый вариант рассуждения по своей логической структуре выглядит несколько сложнее.

[Someone]

ewert в сообщении #1499395 писал(а):

Но, между прочим, стандартно доказательства несчётности вещественных чисел принято оформлять именно от противного: предположим, что биекция существует -- и диагональным методом придём к противоречию.

Вот я и говорю: странное, но широко распространённое заблуждение. Доказательства от противного нет, потому что предположение о существовании биекции никаким способом в доказательстве не используется. Точно так же можно это предположение сформулировать не в начале доказательства, а в конце, и объявить, что получилось противоречие.

Фактически доказательство неравенства $\lvert A\rvert<\lvert 2^A\rvert$ состоит из двух частей:
1) доказывается неравенство $\lvert A\rvert\leqslant\lvert 2^A\rvert$ (демонстрируется инъекция $A\to 2^A$);
2) доказывается неравенство $\lvert A\rvert\neq\lvert 2^A\rvert$ (демонстрируется, что никакое отображение $A\to 2^A$ не является сюръекцией и, следовательно, не является биекцией).

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

-- Ср янв 06, 2021 21:55:42 --

ewert в сообщении #1499395 писал(а):

Утверждения "никакая инъекция не может быть биекцией" и "существование биекции внутренне противоречиво" означают ровно одно и тоже, лишь словесное оформление различно.

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

P.S. У самого Кантора никакого доказательства от противного не было.