Множество всех подмножеств имеет мощность большую чем мощность множества
Научный форум dxdy
Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Правила форума
Доказательство теоремы о мощности множества подмножеств
 |
|
 |
|
| Заслуженный участник |
 |
Так можно «доказать» и что мощность множества целых чисел больше множества натуральных: ведь множество целых чисел содержит все натуральные, да ещё и отрицательные. Но на самом деле эти мощности равны. Поэтому надо аккуратно делать все рассуждения.
| Заслуженный участник |
 |
Это какое-то странное и очень распространённое заблуждение. Это предположение никак в известных мне доказательствах не используется, поэтому доказательства «от противного» нет.
Я всегда пользовался обозначением 
для мощности множества, поэтому так и буду писать вместо вашего 
(кстати, гораздо лучше выглядит 
).
Но хотелось бы видеть точные определения следующих понятий:
1) множества 
и 
равномощны, то есть, 
;
2) множество имеет мощность не большую, чем множество , то есть, 
;
3) множество имеет мощность меньшую, чем множество , то есть, 
.
Боюсь, без этих определений (и, возможно, ещё некоторых) мы будем долго блуждать в трёх соснах.
|
Последний раз редактировалось korablique 03.01.2021, 12:05, всего редактировалось 1 раз.
| Заслуженный участник |
|
|
|
Последний раз редактировалось Odysseus 03.01.2021, 17:59, всего редактировалось 3 раз(а).
Кажется, вы наугад говорите.
1) Неправильно. Инъекция-то существует, но ее недостаточно, т.е. правильного определения у вас нет.
2) Неправильно. Данная сюръекция может и существовать в каких-то случаях при (в каких?), но к нужному определению это отношения не имеет.
3) Правильно только частично (а значит, тоже неправильно, поскольку, строго говоря, «частично правильного» в математике нет). Во-первых, нужно было указать откуда и куда ведет инъекция. Во-вторых, что значит «нет биекции»? Может просто у вас ее нет (не придумали), а у кого-то другого есть. Правильнее говорить «не существует».
Не нужно срезать углы и опускать подробности, особенно при самом первом ознакомлении с чем-то. Рекомендую
— Вспомнить и привести подробные определения произвольного отображения между множествами, инъекции, сюръекции, биекции.
— Проиллюстрировать их на каких-то конкретных отображениях, сначала между конкретными конечными множествами, потом между бесконечными.
— Дать определение и примеры счетного множества, несчетного множества.
— Привести характерные свойства счетных множеств, несчетных множеств, бесконечных множеств в целом.
И кстати, по какому учебнику вы учите теорию множеств? Для первого ознакомления рекомендую первую главу Александрова «Введение в теорию множеств и общую топологию» и первую главу Калужнина «Введение в общую алгебру».
Потому что в доказательстве на которое вы ссылаетесь нет никакой необходимости предполагать, что биекция есть. Суть доказательства в том, что берется произвольное отображение 
и явно строится подмножество 
, т.е. элемент 
, в которое не может переходить никакой элемент из при данном отображении 
. Из этого следует, что это не сюръекция. А с учетом произвольности взятых множества и отображения (конкретный вид и в доказательстве не используется, т.е. они могут быть любыми) из этого следует, что сюръекции между и не может существовать вообще. А поскольку инъекция существует, то 
.
Предварять все это словами «предположим, что существует множество, равномощное множеству его подмножеств, т.е. существует биекция » не добавляет к доказательству ничего полезного, а может только запутывать. Это все равно, как при доказательства теоремы Пифагора предположить, что она неверна, потом ее явно доказать, а потом сказать, что предположение было неверным, и значит мы «доказали это от противного».
Подобное явное построение элемента второго множества в который не может перейти никакой элемент из первого это главная идея т.н. диагонального метода Кантора. Так доказывается, например, также то, что мощность множества вещественных чисел больше мощности множества натуральных чисел. Но в доказательстве неравномощности множества и множества его подмножеств на которое ссылаетесь вы, этот диагональный метод используется несколько иначе, и поэтому кому-то может казаться не таким ясным и «конструктивным». Рекомендую разобрать еще один способ этого доказательства, который есть в Александрове «Введение в теорию множеств и общую топологию», глава 1, § 6, теоремы 15 и 16. Это более «прямой» способ, и при этом выстраиваемая структура и логика рассуждений практически идентичны диагональному методу доказательства неравномощности множеств натуральных и вещественных чисел. После этого постарайтесь понять в чем эти два способа доказательства близки, и как первый способ можно немного переформулировать на языке близком ко второму.
|
Последний раз редактировалось korablique 03.01.2021, 18:11, всего редактировалось 2 раз(а).
Да, извиняюсь, у меня тут в тетради похожий вопрос написан, и я ответила на него, а не на тот, что мне задали 
1) существует биекция 
2) существует инъекция
3) существует инъекция , но не существует биекции
Odysseus
За рекомендации спасибо
| Заслуженный участник |
|
|
С этим я больше согласен, чем нет. Хотя, например, теорема Кантора-Бернштейна намного понятнее доказана у Верещагина и Шеня. И про кардинальные числа и их арифметику может быть полезно где-то почитать. Ну и явно полезно задачки порешать.
Мой пойнт был несколько в другом. Есть много учебников по теории множеств, но эта глава из Александрова, как и первая глава из Калужнина, это ИМХО самые удачные введения в предмет с точки зрения сочетания простоты/понятности и хорошей подборки материала. Далее, при желании, можно углубляться и дальше, но обычно только если что-то дополнительное явно понадобится.
| Заслуженный участник |
|
Это, естественно, не более чем вопрос стилистики. Утверждения «никакая инъекция не может быть биекцией» и «существование биекции внутренне противоречиво» означают ровно одно и тоже, лишь словесное оформление различно. Ну разве что первый вариант рассуждения по своей логической структуре выглядит несколько сложнее.
| Заслуженный участник |
|
Последний раз редактировалось Someone 06.01.2021, 21:55, всего редактировалось 1 раз.
Вот я и говорю: странное, но широко распространённое заблуждение. Доказательства от противного нет, потому что предположение о существовании биекции никаким способом в доказательстве не используется. Точно так же можно это предположение сформулировать не в начале доказательства, а в конце, и объявить, что получилось противоречие.
Фактически доказательство неравенства 
состоит из двух частей:
1) доказывается неравенство 
(демонстрируется инъекция 
);
2) доказывается неравенство 
(демонстрируется, что никакое отображение не является сюръекцией и, следовательно, не является биекцией).
Во втором пункте мы, разумеется, можем в начале наших рассуждений предположить, что рассматриваемое отображение является биекцией, но это никак не повлияет на наши построения. Поэтому такое предположение является лишним.
Таким способом можно любое доказательство превратить в доказательство от противного: в начале доказательства сделаем предположение, что доказываемое утверждение неверно, потом докажем его любым способом и получим противоречие с предположением.
06. Теоремы о счетных множествах. Множества мощности континуум
Если рассмотреть любое конечное множество и любое его собственное (непустое и не совпадающее с ним самим) подмножество, то элементов в подмножестве меньше, чем в сам множестве, т. е. часть меньше целого.
Обладают ли бесконечные множества таким свойством? И может ли иметь смысл утверждение, что в одном бесконечном множестве «меньше» элементов, чем в другом, тоже бесконечном? Ведь про два бесконечных множества мы можем пока только сказать, эквивалентны они или нет. А существуют ли вообще неэквивалентные бесконечные множества?
Приведём забавную фантастическую историю из книги Н. Я. Виленкина «Рассказы о множествах». Действие происходит в далёком будущем, когда жители разных галактик могут встречаться друг с другом. Поэтому для всех путешествующих по космосу построена огромная гостиница, протянувшаяся через несколько галактик.
В этой гостинице бесконечно много номеров (комнат), но, как и положено, все комнаты пронумерованы, и для любого Натурального числа n есть комната с этим номером.
Однажды в этой гостинице проходил съезд космозоологов, в котором участвовали представители всех галактик. Так как галактик тоже бесконечное множество, все места в гостинице оказались занятыми. Но в это время к директору гостиницы приехал его друг и попросил поселить его в эту гостиницу.
«После некоторых размышлений директор обратился к администратору и сказал:
– Куда же я дену жильца этого номера? – удивлённо спросил администратор.
– А его переселите в № 2. Жильца же из № 2 отправьте в № 3, из № 3 – в № 4 и т. д.»
Вообще, пусть постоялец, живущий в номере K, переедет в номер K+1, как это показано на следующем рисунке:
Тогда у каждого снова будет свой номер, а № 1 освободится.
Таким образом, нового гостя удалось поселить – именно потому, что номеров в гостинице бесконечно много.
Первоначально участники съезда занимали все номера гостиницы, следовательно, между множеством космозоологов и множеством N Было установлено взаимно однозначное соответствие: каждому космозоологу дали по номеру, на двери которого написано соответствующее ему натуральное число. Естественно считать, что делегатов было «столько же», сколько имеется натуральных чисел. Но приехал ещё один человек, его тоже поселили, и количество проживающих увеличилось на 1. Но их снова осталось «столько же», сколько и натуральных чисел: ведь все поместились в гостиницу!
Мы пришли к удивительному выводу: если к множеству, которое равномощно N, добавить ещё один элемент, получится множество, которое снова равномощно N. Но ведь совершенно ясно, что делегаты-космозоологи представляют собой часть того множества людей, которые разместились в гостинице после приезда нового гостя. Значит, в этом случае часть не «меньше» целого, а «равна» целому!
Итак, из определения эквивалентности (которое не приводит ни к каким странностям в случае конечных множеств) следует, что часть бесконечного множества может быть эквивалентна всему множеству.
Новый постоялец не удивился, когда на другое утро ему предложили переселиться в № 1000000. Просто в гостиницу прибыли запоздавшие космозоологи из галактики ВСК-3472, и надо было разместить ещё 999999 жильцов.
Эта задача оказалась весьма сложной. Но и в этом случае нашёлся выход.
«В первую очередь администратор приказал переселить жильца из № 1 в № 2.
– А жильца из № 2 переселите в № 4, из № 3 – в № 6, вообще, из номера N – в номер 2n.
Определение. Множество А, равномощное множеству натуральных чисел N, называется Счетным множеством (имеет мощность счетного множества). Если множество В является бесконечным и не равномощно множеству N, то его называют несчетным.
Множество, которое является конечным или счетным, еще называют не более чем счетным .
Пусть множество А является счетным. По определению, тогда существует биекция А на N, т. е. каждому аÎА соответствует единственный номер nÎN и множество А обращается в некоторую последовательность <аn>.
Теорема 1. Любое подмножество счетного множества не более чем счетно.
Доказательство. Пусть А = 
. Тогда необходимая нам биекция, показывающая, что В является счетным множеством, задается в виде: 
® k.
Теорема 2. Объединение конечного или счетного числа счетных множеств является счетным множеством.
Теорема 3. Любое бесконечное множество содержит счетное подмножество.
Доказательство. Выберем в заданном множестве А какой-либо элемент, придав ему единичный индекс: а1. Среди всех оставшихся элементов множества А найдется не равный а1 элемент (в силу бесконечности А). Его мы обозначим через а2. Продолжая этот процесс до бесконечности мы получим необходимое нам счетное множество
Доказательство. Пусть множество М – А не более чем счетно. Тогда множество М = АÈ(М – А) по теореме 2 не более чем счетно. Это противоречит тому, что множество М несчетно и, следовательно, наше исходное предположение не верно. Таким образом, множество М – А несчетно. Последнее еще не означает равномощности множеств М и М – А. Докажем ее. Выделим из М – А счетное множество В. Обозначим через С множество С = (М – А) – В. Справедливы равенства М = АÈВÈС и М – А = ВÈС. Множество АÈВ счетно (теорема 2). Следовательно, существует биекция f из АÈВ на А. Теперь можно построить биекцию g из М на М – А по правилу:
Теорема 5. Если множество С бесконечно, а В не более чем счетно, то множество ВÈС равномощно множеству С.
Доказательство. Если множество С счетно, то множество ВÈС также счетно и следовательно они равномощны. Если же множество С не счетно, то мы можем воспользоваться теоремой 4, положив в ней А = СÇВ, а М = С.
Теорема 6. Если множество С является бесконечным, то существует его подмножество В такое, что В¹С и В равномощно с С.
Доказательство. По теореме 3 мы можем выделить из множества С его счетное подмножество А. Если множество С счетно, то в качестве В из утверждения теоремы можно взять В=А. Если же С не счетно, то можно положить В=С-А и утверждаемое вытекает из теоремы 4.
Теорема 7. Множество рациональных чисел Q является счетным.
Доказательство. Обозначим через Р множество всех пар натуральных чисел (p, q), таких что p и q не имеют общих целых делителей, кроме единицы. Для пары натуральных чисел (p, q) введем ее высоту m = p + q. Обозначим Рn множество пар натуральных чисел высоты n. Нетрудно проверить, что каждое множество Рn является конечным и содержит не более, чем n-1 член. Так как Р = Èn Рn, то множество Р счетно в силу теоремы 2.
Теорема 8. Множество точек интервала (0,1) является несчетным.
Доказательство (Диагональный метод Кантора). Доказательство проведем от противного, предположив, что множество точек интервала (0,1) является счетным. Тогда все точки можно записать в виде последовательности:
Множества, равномощные множеству точек интервала (0, 1), называются множествами мощности Континуум .
Задачи.
1. Показать, что если множества А и В являются счетными, то и их произведение А´В является счетным.
2. Установить биекцию между множеством N всех натуральных чисел и множеством Q всех четных положительных чисел.
3. Установить биекцию между множеством N всех натуральных чисел и множеством Р всех четных чисел.
Парадокс Кантора- мощность множества всех множеств
Всё течёт, всё меняется.
Нельзя дважды войти в одну и ту же реку.
(Энциклопедический словарь
крылатых слов и выражений
http://www.bibliotekar.ru/encSlov/3/206.htm)
В теории множеств теорема Кантора гласит, что
Любое множество менее мощно, чем множество всех его подмножеств.»
(Википедия, Теорема Кантора)
Парадокс Кантора — парадокс теории множеств, который демонстрирует, что предположение о существовании множества всех множеств ведёт к противоречиям и, следовательно, противоречивой является теория, в которой построение такого множества возможно.
Не существует максимального кардинального числа. В самом деле: пусть оно существует и равно М. Тогда по теореме Кантора 2м > М.
Этот парадокс, открытый Кантором около 1899 года, обнаружил необходимость пересмотра «наивной теории множеств» (парадокс Рассела был открыт несколько позднее, около 1901 года) и стимулировал разработку строгой аксиоматики теории множеств. Схема аксиом отвергнута как противоречивая, вместо этого была разработана система ограничений на вид условия, задаваемого формулой A.
(Википедия, Парадокс Кантора)
«Универсальное множество — в математике множество, содержащее все мыслимые объекты. Универсальное множество единственно»
(Википедия, универсальное множество)
В этом рассуждении нет парадокса. Кантор описал ситуацию изменения знания (его объёма и качества), то есть процесс познания.
Одним из следствий сущностной глобальной черты мира, в котором мы существуем – его изменчивости – является то, что знание относительно («Логические парадоксы. Пути решения», «О принципах решения парадоксов», пункт 2, http://proza.ru/2009/04/27/370). Из этого следует:
1. на конкретный момент времени Т(x) существует универсум N(x), имеющий максимально возможную мощность M[N(x)]. Это множество множеств, отражающее максимальный, кардинальный предел объёма всего нашего знания на конкретный момент времени;
2. новое знание, появляющееся в процессе познания мира, а также в процессе изменения самого мира, приводит к новому универсуму N(y), имеющему по сравнению с предыдущим большую мощность M[N(y)] на новый момент времени T(y).
Таким образом, противоречие кроется лишь в точном разделении моментов времени.
В ОДНО И ТО ЖЕ ВРЕМЯ НЕ СУЩЕСТВУЕТ ДВУХ УНИВЕРСУМОВ.
Универсум всегда один. Но мощность его меняется с включением новых элементов в новый момент времени. Поэтому в изменении мощности универсума нет противоречия, так как знание относительно. Ведь мир изменяется качественно и количественно, а значит, и знание о нём тоже. И в наличии на конкретный момент времени лишь одного самого мощного множества тоже нет противоречия по тому же принципу.
Приведённое рассуждение – это прямое описание «принципа относительности знания», то есть его бесконечности, бесконечного обновления и развития в сторону движения к Абсолютной истине.
Другое дело, если принимать иную «точку опоры выводов»: в виде дефиниции «кардинального множества» в качестве Абсолютной истины. То есть считать, что может в принципе существовать только одно самое мощное множество. Потому что его наличие означает конечность знания, то есть существование множества максимальной, конечной мощности M[N(limX)], даже, возможно, и не достижимого для человека в принципе. В такой интерпретации тезис Кантора выглядит ошибочно сформулированным. Ошибка заключается в «ложном выводе». Если, согласно цитате, Кантор взял в качестве посылки мысль о том, что «для любого сколь угодно мощного множества можно указать ещё более мощное», и сделал на этом основании вывод, что «не существует самого мощного множества», то такая позиция исключает в принципе существование конечной Абсолютной истины, констатируя бесконечность процесса познания, развития. В противовес позиции Кантора во второй части сформулированного парадокса констатируется, что, всё-таки Абсолютная истина в виде множества кардинальной мощности существует или должна существовать. Основанием такого утверждения приводится интуитивное понимание. Такая позиция может иметь право на существование, как и позиция Кантора, хотя она и менее устойчива логически. Потому что интуитивная очевидность не есть логический аргумент, в отличие от приведённого Кантором факта постоянного изменения знания, как следствия сущностной черты мироздания. Более того, предположение о существовании конечного множества в виде Абсолютной истины прямо противоречит фактической действительности – изменчивости мира, в том числе и знания, включая мощность множества.
В самом деле, если мы, к примеру, пересчитали всех цыплят в хозяйстве и тем самым установили мощность множества «все цыплята» (о которых мы можем знать в данный момент времени), то, придя к соседу, увидели ещё цыплят. Мощность нашего множества оказалось под вопросом. Поставив безумную цель сосчитать всех цыплят в мире, через несколько лет мы путём организации получения такой информации в виде передвижений личных и сторонников плюс получение полной информации из всех хозяйств от самых мелких личных хозяйств до крупных птицеводческих ферм, транснациональных сельскохозяйственных птицеводческих корпораций, государств и их объединений в данной сфере, будем иметь громадный массив данных обо всех существующих цыплятах в мире на конкретный момент времени. Задача выполнена? Найдена ли максимальная мощность множества «все цыплята»? Конечно же, нет. Потому что только теперь мы в полной мере можем оценить изменчивость мира – мы увидим, что ежесекундно в мире на свет появляются миллионы новых цыплят, как и исчезают. Поэтому говорить о стабильности и точности нашего знания не приходится теперь ещё в большей степени, несмотря на все усилия и наличие огромной базы данных. Как говорится, «цыплят по осени считают» не зря.
Фиксация объёма «множества множеств» представляется ещё более сложной задачей, чем определение мощности «множества цыплят». И как бы близко мы ни подбирались к определению мощности множества всех множеств, в следующий момент времени наш результат может оказаться уже не соответствующим действительности. «Истина всегда где-то рядом».
Это рассуждение иллюстрирует невозможность получения истинного непротиворечивого логического вывода на основе зыбких, ошибочных, ложных основаниях, посылках. Всё дело в том, что изначально был нарушен принцип «полного и точного понимания проблемы» («Логические парадоксы. Пути решения», «О принципах решения парадоксов», пункт 1, http://proza.ru/2009/04/27/370). Согласно нему, перед нахождением решения и даже перед постановкой вопроса нужно было «расставить все точки над i». Тогда, возможно и не пришлось бы задумываться над этой задачей вообще. Как уже упоминалось мной в решении парадокса «О множестве обычных множеств» (http://www.proza.ru/2009/04/20/768), введённое Кантором понятие «множества» является нечётким, неоднозначно определённым. Оно не учитывает изменчивость мироздания, а, следовательно, неверно. Для приведения к однозначному пониманию «множества» нужно было бы выбрать одно из двух:
«множество» – это обобщение всех существующих элементов по указанным признакам:
1) на ОДИН конкретный момент времени
2) всех таких элементов, возможных в принципе, то есть – на БЕСКОНЕЧНЫЙ момент времени, включая прошлое и будущее, или, другими словами, без учёта момента времени вообще.
Все известные мне рассуждения, касающиеся множеств, так или иначе, основываются на втором толковании понятия «множества». То есть множество понимается как «универсальное математическое множество», мощность которого составляют все мыслимые объекты. А понимание категории «мыслимые объекты» изначально подразумевает, что они могут даже и не существовать в действительности, а только в уме, потому что они мыслимые, то есть как существующие, так и только возможные в будущем или существовавшие раньше. Поэтому такие рассуждения и приводят к противоречивым выводам и вообще противоречивому пониманию «множеств», как и в данной задаче. Легко показать, что вторая трактовка понятия «множества» ошибочна.
Беря за основу понимания «множества» совокупность всех возможных в принципе элементов по интересующим нас признакам, мы не отграничиваем объём множества, что нам необходимо для точного и чёткого понимания и рассуждения, а наоборот, раздвигаем границу понимания до бесконечного предела. Потому что изменчивость мира приводит к постоянному изменению количества и качества знания, в том числе знания об интересующих нас элементах, в частности. И, основываясь на второй трактовке «множества», мы с одной стороны, должны включать в объём нашего множества все новые элементы, появляющиеся с течением времени, как и существовавшие до нас, а, с другой стороны, мы можем остановиться в таком перечислении только в одном случае – указание общего существующего числа элементов нашего множества на конечный момент времени, то есть на «конец света», фактически. Только в этот момент времени будет существовать «множество» максимально возможной мощности.
Конечно, казалось бы, большое количество множеств можно указать в максимальном объёме и до «конца света». Например, количество монет или банкнот исчезнувшего государства или ушедшей эпохи. После их исчезновения составить «множество валют» с максимальной мощностью вроде бы не столь сложно. Тогда как во время существования государства или соответствующей исторической эпохи невозможно было составить такого множества, хотя можно было предположить с уверенностью, что такой универсум будет существовать, так как любому государству или эпохе отведён свой временной срок. Но и в этом случае такие, как указанное, с валютой исчезнувших государств, или подобные им другие множества, могут изменить свою мощность в любую сторону: как увеличения объёма элементов – нахождение клада, – так и уменьшения объёма элементов – утрата хранящихся экземпляров.
Поэтому трактовка множества с опорой на бесконечную продолжительность времени или его игнорирование, что, по сути, одно и то же, является ошибкой, приводящей к всеобщему массовому заблуждению и ложным логическим следствиям.
Человек не может в принципе иметь полный объём информации по интересующему его вопросу по двум причинам:
1) Практическое отсутствие у конкретного человека возможности располагать всей известной информацией по интересующему его вопросу в данный конкретный момент времени.
Теоретически, конечно, человек может добыть, изучить весь объём интересующей его информации. Но практически это сделать, во-первых, затруднительно, а, во-вторых, он не сможет верно оценить полноту этого объёма информации.
2) Изменение самой информации (объёма и качества) в процессе изучения.
Информация изменяется, потому что мир не стоит на месте в момент изучения, а изменяется вместе со всем, что в нём присутствует. Можно предположить, что информацию о конечных множествах возможно изучить полностью на конкретный момент времени. Но, как описано выше в примере с валютой, даже полная информация о конечном множестве на конкретный момент времени может измениться в следующий момент времени с изменением обстоятельств, то есть с изменением самого этого конечного множества (обнаружение клада или утрата образцов, как в указанном примере).
Из этого рассуждения следует, что верной дефиницией «множества» будет первая его возможная трактовка, которая полностью отражает существующее в действительности положение вещей – изменчивость мироздания, а, следовательно, изменчивость информации о нём. Ведь единственная функция, главная цель любого множества, то, для чего оно и создаётся, – это определение мысленной границы между нашим знанием и незнанием, отделение известного и существующего от неизвестного и несуществующего.
Таким образом, мощность любого «множества», включая и множество кардинальной мощности, то есть «множество всех множеств», зависит от момента времени, в который мы определяем объём этого множества. В этот конкретный момент времени существует только одно множество кардинальной мощности – универсум. Но в следующий момент времени мощность универсума изменяется – уменьшается или возрастает – потому что изменяется само мироздание.