Теорема Кантора о мощностях и аксиома выбора

[alex_dorin]

Теорема Кантора о мощностях :
"любое множество менее мощно, чем множество всех его подмножеств"
обычно доказывается методом от противного с использованием аксиомы выделения, например,
https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 1%80%D0%B0
При использовании логического прувера эту теорему удалось доказать с использованием аксиомы выбора в мультипликативной форме.
Без использования аксиомы выбора за обозримое время это сделать не удалось.
Не используется ли аксиома выбора для доказательства этой теоремы неявно ?

[Someone]

alex_dorin в сообщении #1019287 писал(а):

Не используется ли аксиома выбора для доказательства этой теоремы неявно ?

В доказательстве этой теоремы не используется ни аксиома выбора, ни метод "от противного".
Что касается аксиомы выбора, то попробуйте указать место, где она используется. Где используется аксиома выделения, сразу видно.

По поводу метода "от противного". Да, сплошь и рядом это доказательство излагают так, будто бы этот метод используется. Однако сделанное "противное" предположение в доказательстве нигде не используется. Описанное в доказательстве рассуждение благополучно проходит для произвольного отображения $f\colon A\to 2^A$ и доказывает, что это отображение не является сюръекцией, то есть, что $fA\neq 2^A$. Отсюда уже следует, что произвольное отображение $f\colon A\to 2^A$ тем более не является взаимно однозначным, то есть, $\lvert A\rvert\neq\lvert 2^A\rvert$. Поскольку неравенство $\lvert A\rvert\leqslant\lvert 2^A\rvert$ очевидно (инъективное отображение $f\colon A\to 2^A$ можно определить равенством $fx=\{x\}$ для $x\in A$), то $\lvert A\rvert<\lvert 2^A\rvert$. Суть доказательства состоит в непосредственном предъявлении элемента $B\in 2^A\setminus fA$. Вот в доказательстве последней формулы можно усмотреть рассуждение "от противного".

alex_dorin в сообщении #1019287 писал(а):

При использовании логического прувера эту теорему удалось доказать с использованием аксиомы выбора в мультипликативной форме.
Без использования аксиомы выбора за обозримое время это сделать не удалось.

Этот вопрос, видимо, надо задавать программистам, писавшим "логический прувер". На что они, скорее всего, ответят, что поиск доказательства может занять неопределённо длительное время. Вспомните так называемую "великую теорему Ферма".

Где-то в интернете есть ресурс, содержащий формальные доказательства теорем теории множеств. Наверное, там и теорема Кантора есть.

[alex_dorin]

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

Что касается аксиомы выбора, то попробуйте указать место, где она используется

в указаной статье википедии :

в [url=https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D0%B0%D0%BD%D1%82%D0%BE%D1%80%D0%B0 [/url] писал(а):

Заметим, что $ 2^{A} $ содержит подмножество, равномощное $ A $
(например, множество всех одноэлементных подмножеств $ A $), а тогда из только
что доказанного следует $ \textbar 2^{A}\textbar \textgreater \textbar A\textbar $

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

[NSKuber]

alex_dorin
И где же здесь используется аксиома выбора? Где семейство множеств, где функция, которая каждому множеству семейства сопоставляет какой-то его элемент?
Для построения множества одноэлементных подмножеств $A$ аксиома выбора не требуется. Как и не нужна она, чтобы, имея бесконечное число пар обуви, из каждой пары выбрать правый ботинок.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом, цитата не оформлена правильно

alex_dorin
Оформите правильно цитату.
Наберите все формулы и термы $\TeX$ом.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
См. также тему Что такое карантин, и что нужно делать, чтобы там оказаться.
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[Deggial]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Возвращено