Доказать отсутствие биекции

@NEvOl · Регистрация: 13.08.2012

Author24 — интернет-сервис помощи студентам

Как доказывают отсутствие биекции между двумя бесконечными множествами ?
Знаю что для конечных множеств есть теорема о том что мощности множеств совпадают тогда и только тогда, когда существует биективное отображение между ними. Но вот с бесконечными множествами не знаю подобной теоремы.
Например доказать что не существует биекции между $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{N}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(\mathbb{N})$ .
Можно сыграть как-то на том что множества неравномощны, рассматривая $https://www.cyberforum.ru/cgi-bin/latex.cgi?M \subset P(\mathbb{N})$ где $https://www.cyberforum.ru/cgi-bin/latex.cgi?M = \left{ \{1\}, \{2\}, ..., \{n\} \right}$ . Между $https://www.cyberforum.ru/cgi-bin/latex.cgi?M$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{N}$ существует очевидная биекция и получаем что $https://www.cyberforum.ru/cgi-bin/latex.cgi?M$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{N}$ равномощны, вто время как в $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(\mathbb{N})$ больше элементов чем в $https://www.cyberforum.ru/cgi-bin/latex.cgi?M$ (т.к. $https://www.cyberforum.ru/cgi-bin/latex.cgi?M$ собственное подмножество $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(\mathbb{N})$ ), то можно сделать вывод что несуществует биекции между $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{N}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(\mathbb{N})$ т.к. они неравномощны. Подскажите пожалуйста, как это правильно сделать ?

@3D Homer · 24.04.2017, 22:36

Сообщение от NEvOl

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

Для бесконечных множеств это определение мощности.

Сообщение от NEvOl

Например доказать что не существует биекции между $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{N}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(\mathbb{N})$ .

Это теорема Кантора.

@NEvOl · 25.04.2017, 08:42 **[ТС]**

3D Homer, а без теоремы Кантора это можно как-то сделать (не ссылаясь на нее и не передоказывая) ? а то в лекциях она не упомяналась.

@3D Homer · 25.04.2017, 09:08

а без теоремы Кантора это можно как-то сделать (не ссылаясь на нее и не передоказывая) ?

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

Байт · 26.04.2017, 12:14

Сообщение от NEvOl

а без теоремы Кантора это можно как-то сделать (не ссылаясь на нее и не передоказывая)

Если вам удастся доказать это утверждение существенно другим путем, благодарное человечество поставим вам памятник неподалеку от канторовского.
Правда, я не вижу особого смысла в поиске такого доказательство, ибо приведенное уважаемым 3D Homer в параллельном топике занимает ровно одну строчку.

Сообщение от 3D Homer

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

Предположение о счетности множества в самом деле нигде не используется

@eropegov · 29.04.2017, 23:05

...т.к. $https://www.cyberforum.ru/cgi-bin/latex.cgi?M$ собственное подмножество $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(\mathbb{N}))$ , то можно сделать вывод что не существует биекции между $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{N}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi? P(\mathbb{N})$ т. к. они неравномощны

Вообще-то нельзя сделать такого вывода. Собственное подмножество очень просто может быть равномощно всему множеству.

@NEvOl 20 / 19 / 1 Регистрация: 13.08.2012 Сообщений: 779
		1
	Доказать отсутствие биекции 24.04.2017, 17:34. Показов 2317. Ответов 5 Метки нет (Все метки) Как доказывают отсутствие биекции между двумя бесконечными множествами ? Знаю что для конечных множеств есть теорема о том что мощности множеств совпадают тогда и только тогда, когда существует биективное отображение между ними. Но вот с бесконечными множествами не знаю подобной теоремы. Например доказать что не существует биекции между $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{N}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(\mathbb{N})$ . Можно сыграть как-то на том что множества неравномощны, рассматривая $https://www.cyberforum.ru/cgi-bin/latex.cgi?M \subset P(\mathbb{N})$ где $https://www.cyberforum.ru/cgi-bin/latex.cgi?M = \left{ \{1\}, \{2\}, ..., \{n\} \right}$ . Между $https://www.cyberforum.ru/cgi-bin/latex.cgi?M$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{N}$ существует очевидная биекция и получаем что $https://www.cyberforum.ru/cgi-bin/latex.cgi?M$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{N}$ равномощны, вто время как в $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(\mathbb{N})$ больше элементов чем в $https://www.cyberforum.ru/cgi-bin/latex.cgi?M$ (т.к. $https://www.cyberforum.ru/cgi-bin/latex.cgi?M$ собственное подмножество $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(\mathbb{N})$ ), то можно сделать вывод что несуществует биекции между $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{N}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(\mathbb{N})$ т.к. они неравномощны. Подскажите пожалуйста, как это правильно сделать ? 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,660
	24.04.2017, 22:36	2
	Сообщение от NEvOl Знаю что для конечных множеств есть теорема о том что мощности множеств совпадают тогда и только тогда, когда существует биективное отображение между ними. Но вот с бесконечными множествами не знаю подобной теоремы. Для бесконечных множеств это определение мощности. Сообщение от NEvOl Например доказать что не существует биекции между $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{N}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(\mathbb{N})$ . Это теорема Кантора. 0

@NEvOl 20 / 19 / 1 Регистрация: 13.08.2012 Сообщений: 779
	25.04.2017, 08:42 [ТС]	3
	3D Homer, а без теоремы Кантора это можно как-то сделать (не ссылаясь на нее и не передоказывая) ? а то в лекциях она не упомяналась. 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,660
	25.04.2017, 09:08	4
	а без теоремы Кантора это можно как-то сделать (не ссылаясь на нее и не передоказывая) ? Вы не можете доказать утверждение, не доказывая его. Можно, правда, доказать его не для произвольного множества, а для натуральных чисел. Обычно это доказывается диагональным рассуждением. Либо его не было у вас на лекции, либо вы его пропустии. 1

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	26.04.2017, 12:14	5
	Сообщение от NEvOl а без теоремы Кантора это можно как-то сделать (не ссылаясь на нее и не передоказывая) Если вам удастся доказать это утверждение существенно другим путем, благодарное человечество поставим вам памятник неподалеку от канторовского. Правда, я не вижу особого смысла в поиске такого доказательство, ибо приведенное уважаемым 3D Homer в параллельном топике занимает ровно одну строчку. Сообщение от 3D Homer его не для произвольного множества, а для натуральных чисел. Предположение о счетности множества в самом деле нигде не используется 0

@eropegov $Эксперт по математике/физике$ 505 / 465 / 100 Регистрация: 30.01.2017 Сообщений: 1,371
	29.04.2017, 23:05	6
	...т.к. $https://www.cyberforum.ru/cgi-bin/latex.cgi?M$ собственное подмножество $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(\mathbb{N}))$ , то можно сделать вывод что не существует биекции между $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{N}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi? P(\mathbb{N})$ т. к. они неравномощны Вообще-то нельзя сделать такого вывода. Собственное подмножество очень просто может быть равномощно всему множеству. 1