2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему
 
 Теорема Кантора о мощностях и аксиома выбора
Сообщение25.05.2015, 08:32 


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

 Профиль  
                  
 
 Re: Теорема Кантора о мощностях и аксиома выбора
Сообщение25.05.2015, 12:11 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
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 писал(а):
При использовании логического прувера эту теорему удалось доказать с использованием аксиомы выбора в мультипликативной форме.
Без использования аксиомы выбора за обозримое время это сделать не удалось.
Этот вопрос, видимо, надо задавать программистам, писавшим "логический прувер". На что они, скорее всего, ответят, что поиск доказательства может занять неопределённо длительное время. Вспомните так называемую "великую теорему Ферма".

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

 Профиль  
                  
 
 Re: Теорема Кантора о мощностях и аксиома выбора
Сообщение25.05.2015, 13:49 


08/03/11
273
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 $"
в статье из википедии можно получить, используя аксиому выбора.

 Профиль  
                  
 
 Re: Теорема Кантора о мощностях и аксиома выбора
Сообщение25.05.2015, 13:57 
Заслуженный участник


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

 Профиль  
                  
 
 Posted automatically
Сообщение25.05.2015, 14:10 
Супермодератор
Аватара пользователя


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

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

 Профиль  
                  
 
 Posted automatically
Сообщение29.05.2015, 19:59 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group