Мощность множества всех подмножеств натуральных чисел

Мощность (кардинальное число) множества – такое свойство множества, которое остается после абстрагирования от качества (состава) его элементов (определение мощности по Кантору). Мощность множества А обозначается | А | или gard A.

Любые два множества А и В называются равномощными (эквивалентными), если между их элементами может быть установлено взаимно однозначное соответствие, т.е. существует взаимно однозначная функция f: A → B с областью определения А и множеством (областью) значений В. Таким образом, можно сказать, что мощность – это то общее, что есть у всех эквивалентных множеств. Понятие мощности введено Кантором для количественного сравнения различных множеств. С точки зрения правил сравнения (выявления общего), все множества делятся на конечные и бесконечные. В свою очередь бесконечные множества делятся на счетные и континуальные .

Конечное множество – множество, содержащее конечное число элементов; мощность n-элементного множества А равна числу его элементов, т.е. | А | = n; множество, не содержащее ни одного элемента, называется пустым множеством и обозначается Æ; пустое множество является подмножеством любого множества и имеет нулевую мощность (| Æ | = 0). Из определения конечного множества следует – любые два конечные множества с одинаковым (равным) числом элементов эквивалентны (между ними легко установить взаимно однозначное соответствие – для этого достаточно, например, ввести нумерацию элементов).

Одна из особенностей конечного множества заключается в том, что его всегда можно задать путем перечисления элементов. Ясно, что это не всегда удобно (когда число элементов велико), но довольно часто другие способы просто неприемлемы. Последнее относится, например, к ситуации, когда нужно описать подмножество студентов, объединенных в определенную группу (поток). Очевидно, в этом случае придумать какое-то свойство или порождающую функцию, позволяющие однозначно выделить группу студентов из всего множества студентов вуза (факультета), практически невозможно (да в этом и нет необходимости – достаточно составить список студентов).

Бесконечное множество – всякое множество А, имеющееправильную часть В, равномощную всему ( целому ) множеству А , т. е. В Ì А и |В| = |А|. Так, например, множество М квадратов натуральных чисел является правильной частью всего множества N натуральных чисел (взаимно однозначное соответствие между этими множествами очевидно); следовательно, оба эти множества обладают одинаковой мощностью и подпадают под определение бесконечных множеств. В то же время это определение не подходит к конечным множествам, так как мощность (число элементов) правильной части любого конечного множества всегда меньше мощности полного множества.

Счетное множество – любое бесконечное множество, равномощное множеству N натуральных чисел. Мощность счетного множества принято обозначать (алеф – нуль). Отличительная особенность счетного множества – все его элементы могут быть пронумерованы. И хотя любое конечное множество также обладает этой особенностью, оно, по определению, к счетным множествам не относится. Примеры часто встречающихся счетных множеств: любые бесконечные подмножества множества N натуральных чисел; множества целых и рациональных чисел и их бесконечные подмножества (одним из таких подмножеств является, в частности, множество N );

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

Замечание. С возможностью нумерации элементов счетного множества связан тот факт, что довольно часто такого рода множества описываются посредством перечисления элементов. Это характерно, например, при задании (описании) бесконечных числовых последовательностей и рядов, когда по записанным нескольким первым членам последовательности (ряда) видна закономерность их изменения и, как следствие, запись последующих членов с помощью выявленной закономерности не вызывает затруднений. Простейшей иллюстрацией к вышесказанному могут служить применяемые на практике описания множеств натуральных и целых чисел, а именно:

Континуальное множество – любое бесконечное множество, равномощное множеству R действительных чисел. Говорят, что всякое континуальное множество имеет мощность континуума. Такой мощностью обладают, например:

множество всех подмножеств всякого счетного множества;

множество точек, принадлежащих некоторой прямой или поверхности;

множество всех действительных чисел некоторого интервала ( a,b ) или отрезка [ a,b ] (см. пример1.2).

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

Теорема Кантора. Множество действительных чисел отрезка [0,1] несчетно.

→ Докажем теорему методом от противного. Для этого предположим, что множество счетно, т.е. может быть пронумеровано. Расположим все числа, изображенные бесконечными десятичными дробями, в порядке их нумерации:

Рассмотрим любую бесконечную дробь , у которой . Эта дробь не может войти в указанную последовательность, так как от первого числа она отличается первой цифрой, от второго – второй цифрой и т.д.

Геометрическая интерпретация множеств. Для геометрического (графического) изображения множеств и их свойств (связей между ними) довольно часто используются так называемые диаграммы Эйлера-Венна, представляющие собой в общем случае некоторый прямоугольник на плоскости и вложенные в него круги.

Так, если в рамках конкретно решаемой задачи рассматривается некая система S = <A,B,C,…,G>частных множеств, то кругами (круги Эйлера), находящимися внутри прямоугольника, изображаются любые множества из S, а прямоугольником – некоторое фиксированное универсальное множество (множество-универсум) U, включающее в себя в качестве подмножеств всю систему S частных множеств, т.е.

" МÎ S : M Ì U. При этом каждое множество мыслится как множество точек, принадлежащих изображающему его кругу Эйлера.

Замечание. Ясно, что множество-универсум U должно быть либо задано, либо очевидно из контекста задачи. Так, для S = <A, B, С >, где

в качестве универсального множества можно использовать как весь латинский алфавит, так и множество U = <a,b,c,d,e,f,g>. Круги, иллюстрирующие множества А и В на рисунке, пересекаются, так как эти множества имеют общие элементы.

Читайте также:  Лучшие производители электронных книг

Геометрическая иллюстрация множеств

Не нашли то, что искали? Воспользуйтесь поиском:

Как я понял, биекцию из $%N
ightarrow N$% можно записать как счетное множество, а т.к. множество всех счётных множеств натуральных чисел является континуум, множество всех таких биекций также является континуумом.
Я прав?

задан 5 Ноя ’14 16:03

Leva319
1.7k ● 1 ● 11 ● 53
77&#037 принятых

В принципе да, Вы правы, хотя написано как-то нечетко. Смысл фразы "множество всех счетных множеств натуральных чисел" от меня как-то ускользает.

http://math.hashcode.ru/users/3297/cartesius "множество всех счетных множеств натуральных чисел", а можно ли это как-то понятнее записать?

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

1 ответ

Я не понял смысл приведённого рассуждения. Прежде всего, биекцию $%mathbb N$% на $%mathbb N$% мы записываем не в виде множества, а в виде последовательности. Берутся все натуральные числа и располагаются в определённом порядке: $%a_1$%, $%a_2$%, . , $%a_n$%, . , где каждое число встречается ровно один раз. Множество при этом всегда оно и то же — это само $%mathbb N$%. От перестановки элементов множество не меняется, а вот последовательность меняется, поэтому именно этот термин и должен использоваться.

Далее, я так понял, Вы хотите применить тот факт, что множество всех подмножеств $%mathbb N$% имеет мощность континуума, причём брать можно только бесконечные подмножества, так как конечных подмножеств счётное количество. Это верно, но отсюда пока ещё не получается доказательство, так как подмножества — это одно, а биекции — совсем другое.

Мне кажется, здесь в доказательстве имеет смысл использовать теорему Кантора – Бернштейна, так как требуемую биекцию построить довольно сложно, и легче доказать два факта. Первый, что биекций $%mathbb N$% на $%mathbb N$% не меньше континуума, а второй — что их не больше континуума.

Докажем первое утверждение. Будем опираться на то, что имеется континуум бесконечных двоичных последовательностей типа 01100010. . Это фактически то же самое, что числа промежутка $%[0;1)$%, записанные в двоичной форме с участием запятой в начале. При этом 1 не может возникать в периоде — подобно тому, как 9 не бывает периодом десятичных дробей. И здесь возможна такая интерпретация: каждой последовательности нулей и единиц сопоставляем подмножество в $%mathbb N$% по такому правилу. Если на $%n$%-м месте стоит цифра 0, то считаем, что $%n$% принадлежит нашему подмножеству, а если 1, то не принадлежит. Например, множество нечётных чисел будет закодировано как 010101. множество чётных как 101010. множество простых как 10010101110.. и тому подобное. Это взаимно-однозначное соответствие между двоичными последовательностями и подмножествами $%mathbb N$%. Если 1 получается в периоде, то это в точности означает, что наше подмножество конечно. Такие последовательности можно не рассматривать. И тогда получается биекция между множеством бесконечных подмножеств $%mathbb N$% и множеством вещественных чисел промежутка $%[0;1)$%. Последних имеется континуум, поэтому далее я буду рассматривать множество двоичных последовательностей как "образец" континуума.

Итак, сейчас мы хотим показать, что биекций $%mathbb N$% на $%mathbb N$% не меньше континуума. Для этого по каждой двоичной последовательности типа 011010001. строим свою биекцию по определённому правилу. Я возьму такое правило: все натуральные числа разобью на пары соседних: 1 и 2, 3 и 4, и так далее. В $%n$%-ю пару войдут $%2n-1$% и $%2n$%. Теперь я смотрю на последовательность из нулей и единиц, и начинаю располагать натуральные числа в определённой последовательности. Если я вижу на $%n$%-м месте 0, то числа $%2n-1$% располагаю по порядку. А если вижу 1, то беру эти числа в обратном порядке. По той последовательности, которую я написал чуть выше, у меня получится 1,2,4,3,6,5,7,8,10,9, . и так далее. Это не что иное как биекция $%mathbb N$% на $%mathbb N$%, где 1 переходит в 1, 2 переходит в 2, 3 переходит в 4, 4 переходит в 3, и так далее. Разумеется, не каждая биекция имеет такой вид, но нам здесь важно, что для каждой двоичной последовательности получается биекция, причём своя. Это рассуждение обосновывает тот факт, что биекций $%mathbb N$% на $%mathbb N$% имеется по крайней мере континуум.

Теперь докажем второе утверждение: что биекций не больше континуума. Здесь удобно доказать более сильный факт, что вообще отображений $%mathbb N$% в $%mathbb N$% имеется не больше континуума. Каждое такое отображение есть последовательность натуральных чисел, где числа могут повторяться, могут отсутствовать и так далее.

Пусть у нас в последовательности натуральных чисел встретилось число $%k$%. Тогда мы пишем $%k$% нулей и одну единицу за ними. Скажем, 001000100101. будет кодом последовательности 2,3,2,1. и так далее. Понятно, что каждая последовательность натуральных чисел получает при этом свой двоичный код, по которому её можно восстановить. Это задаёт инъекцию из множества всех отображений ($%mathbb N$% в $%mathbb N$%) в множество двоичных последовательностей, откуда можно сделать вывод, что таких отображений не больше континуума.

ПАРАДОКС КАНТОРА –
Мощность множества всех множеств

Всё течёт, всё меняется.
Нельзя дважды войти в одну и ту же реку.

(Энциклопедический словарь
крылатых слов и выражений
http://www.bibliotekar.ru/encSlov/3/206.htm)

«Согласно одной из теорем Г. Кантора не существует самого мощного множества, то есть множества, обладающего наибольшим кардинальным (количественным) числом. Не существует потому, что для любого сколь угодно мощного множества можно указать ещё более мощное. Это с одной стороны. А с другой, интуитивно очевидно, что множество всех множеств должно быть самым мощным, ведь оно представляет совокупность всех множеств, какие только могут существовать, вообще включает все мыслимые множества» (Сухотин А.К. Парадоксы науки. – Москва: Молодая гвардия, 1980 – с.240, http://nplit.ru/books/item/f00/s00/z0000026/st006.shtml)

Читайте также:  Лучшие музыкальные каналы в телеграмме

В теории множеств теорема Кантора гласит, что
Любое множество менее мощно, чем множество всех его подмножеств.»
(Википедия, Теорема Кантора)

Парадокс Кантора — парадокс теории множеств, который демонстрирует, что предположение о существовании множества всех множеств ведёт к противоречиям и, следовательно, противоречивой является теория, в которой построение такого множества возможно.

Не существует максимального кардинального числа. В самом деле: пусть оно существует и равно М. Тогда по теореме Кантора 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)], даже, возможно, и не достижимого для человека в принципе. В такой интерпретации тезис Кантора выглядит ошибочно сформулированным. Ошибка заключается в «ложном выводе». Если, согласно цитате, Кантор взял в качестве посылки мысль о том, что «для любого сколь угодно мощного множества можно указать ещё более мощное», и сделал на этом основании вывод, что «не существует самого мощного множества», то такая позиция исключает в принципе существование конечной Абсолютной истины, констатируя бесконечность процесса познания, развития. В противовес позиции Кантора во второй части сформулированного парадокса констатируется, что, всё-таки Абсолютная истина в виде множества кардинальной мощности существует или должна существовать. Основанием такого утверждения приводится интуитивное понимание. Такая позиция может иметь право на существование, как и позиция Кантора, хотя она и менее устойчива логически. Потому что интуитивная очевидность не есть логический аргумент, в отличие от приведённого Кантором факта постоянного изменения знания, как следствия сущностной черты мироздания. Более того, предположение о существовании конечного множества в виде Абсолютной истины прямо противоречит фактической действительности – изменчивости мира, в том числе и знания, включая мощность множества.

В самом деле, если мы, к примеру, пересчитали всех цыплят в хозяйстве и тем самым установили мощность множества «все цыплята» (о которых мы можем знать в данный момент времени), то, придя к соседу, увидели ещё цыплят. Мощность нашего множества оказалось под вопросом. Поставив безумную цель сосчитать всех цыплят в мире, через несколько лет мы путём организации получения такой информации в виде передвижений личных и сторонников плюс получение полной информации из всех хозяйств от самых мелких личных хозяйств до крупных птицеводческих ферм, транснациональных сельскохозяйственных птицеводческих корпораций, государств и их объединений в данной сфере, будем иметь громадный массив данных обо всех существующих цыплятах в мире на конкретный момент времени. Задача выполнена? Найдена ли максимальная мощность множества «все цыплята»? Конечно же, нет. Потому что только теперь мы в полной мере можем оценить изменчивость мира – мы увидим, что ежесекундно в мире на свет появляются миллионы новых цыплят, как и исчезают. Поэтому говорить о стабильности и точности нашего знания не приходится теперь ещё в большей степени, несмотря на все усилия и наличие огромной базы данных. Как говорится, «цыплят по осени считают» не зря.

Фиксация объёма "множества множеств" представляется ещё более сложной задачей, чем определение мощности "множества цыплят". И как бы близко мы ни подбирались к определению мощности множества всех множеств, в следующий момент времени наш результат может оказаться уже не соответствующим действительности. "Истина всегда где-то рядом".

Читайте также:  Моноблок dell inspiron 3264 отзывы

Это рассуждение иллюстрирует невозможность получения истинного непротиворечивого логического вывода на основе зыбких, ошибочных, ложных основаниях, посылках. Всё дело в том, что изначально был нарушен принцип «полного и точного понимания проблемы» («Логические парадоксы. Пути решения», «О принципах решения парадоксов», пункт 1, http://proza.ru/2009/04/27/370). Согласно нему, перед нахождением решения и даже перед постановкой вопроса нужно было «расставить все точки над i». Тогда, возможно и не пришлось бы задумываться над этой задачей вообще. Как уже упоминалось мной в решении парадокса «О множестве обычных множеств» (http://www.proza.ru/2009/04/20/768), введённое Кантором понятие «множества» является нечётким, неоднозначно определённым. Оно не учитывает изменчивость мироздания, а, следовательно, неверно. Для приведения к однозначному пониманию «множества» нужно было бы выбрать одно из двух:

«множество» – это обобщение всех существующих элементов по указанным признакам:

1) на ОДИН конкретный момент времени

2) всех таких элементов, возможных в принципе, то есть – на БЕСКОНЕЧНЫЙ момент времени, включая прошлое и будущее, или, другими словами, без учёта момента времени вообще.

Все известные мне рассуждения, касающиеся множеств, так или иначе, основываются на втором толковании понятия «множества». То есть множество понимается как «универсальное математическое множество», мощность которого составляют все мыслимые объекты. А понимание категории «мыслимые объекты» изначально подразумевает, что они могут даже и не существовать в действительности, а только в уме, потому что они мыслимые, то есть как существующие, так и только возможные в будущем или существовавшие раньше. Поэтому такие рассуждения и приводят к противоречивым выводам и вообще противоречивому пониманию «множеств», как и в данной задаче. Легко показать, что вторая трактовка понятия «множества» ошибочна.

Беря за основу понимания «множества» совокупность всех возможных в принципе элементов по интересующим нас признакам, мы не отграничиваем объём множества, что нам необходимо для точного и чёткого понимания и рассуждения, а наоборот, раздвигаем границу понимания до бесконечного предела. Потому что изменчивость мира приводит к постоянному изменению количества и качества знания, в том числе знания об интересующих нас элементах, в частности. И, основываясь на второй трактовке «множества», мы с одной стороны, должны включать в объём нашего множества все новые элементы, появляющиеся с течением времени, как и существовавшие до нас, а, с другой стороны, мы можем остановиться в таком перечислении только в одном случае – указание общего существующего числа элементов нашего множества на конечный момент времени, то есть на «конец света», фактически. Только в этот момент времени будет существовать «множество» максимально возможной мощности.

Конечно, казалось бы, большое количество множеств можно указать в максимальном объёме и до «конца света». Например, количество монет или банкнот исчезнувшего государства или ушедшей эпохи. После их исчезновения составить «множество валют» с максимальной мощностью вроде бы не столь сложно. Тогда как во время существования государства или соответствующей исторической эпохи невозможно было составить такого множества, хотя можно было предположить с уверенностью, что такой универсум будет существовать, так как любому государству или эпохе отведён свой временной срок. Но и в этом случае такие, как указанное, с валютой исчезнувших государств, или подобные им другие множества, могут изменить свою мощность в любую сторону: как увеличения объёма элементов – нахождение клада, – так и уменьшения объёма элементов – утрата хранящихся экземпляров.

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

Человек не может в принципе иметь полный объём информации по интересующему его вопросу по двум причинам:

1) Практическое отсутствие у конкретного человека возможности располагать всей известной информацией по интересующему его вопросу в данный конкретный момент времени.

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

2) Изменение самой информации (объёма и качества) в процессе изучения.

Информация изменяется, потому что мир не стоит на месте в момент изучения, а изменяется вместе со всем, что в нём присутствует. Можно предположить, что информацию о конечных множествах возможно изучить полностью на конкретный момент времени. Но, как описано выше в примере с валютой, даже полная информация о конечном множестве на конкретный момент времени может измениться в следующий момент времени с изменением обстоятельств, то есть с изменением самого этого конечного множества (обнаружение клада или утрата образцов, как в указанном примере).

Из этого рассуждения следует, что верной дефиницией «множества» будет первая его возможная трактовка, которая полностью отражает существующее в действительности положение вещей – изменчивость мироздания, а, следовательно, изменчивость информации о нём. Ведь единственная функция, главная цель любого множества, то, для чего оно и создаётся, – это определение мысленной границы между нашим знанием и незнанием, отделение известного и существующего от неизвестного и несуществующего.

Таким образом, мощность любого «множества», включая и множество кардинальной мощности, то есть «множество всех множеств», зависит от момента времени, в который мы определяем объём этого множества. В этот конкретный момент времени существует только одно множество кардинальной мощности – универсум. Но в следующий момент времени мощность универсума изменяется – уменьшается или возрастает – потому что изменяется само мироздание.

Читайте также:

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock detector