Также по теме

МНОЖЕСТВ ТЕОРИЯ

МНОЖЕСТВ ТЕОРИЯ. Под множеством понимается совокупность каких-либо объектов, называемых элементами множества. Теория множеств занимается изучением свойств как произвольных множеств, так и множеств специального вида независимо от природы образующих их элементов. Терминология и многие результаты этой теории широко используются в математике, например в математическом анализе, геометрии и теории вероятностей.

Терминология.

Если каждый элемент множества B является элементом множества A, то множество B называется подмножеством множества A. Например, если множество A состоит из чисел 1, 2 и 3, то у него существует 8 подмножеств (три из них содержат по 1 элементу, три – содержат по 2 элемента, одно подмножество, по определению, есть само множество A и восьмое подмножество – это пустое множество, не содержащее ни одного элемента). Запись x О A означает, что x – элемент множества A, а B М A – что B является подмножеством множества A. Если универсальное множество, из которого мы берем элементы всех множеств, обозначить через I, то элементы, принадлежащие I, но не входящие в A, образуют множество, называемое дополнением множества A и обозначаемое C(A) или Aў. Множество, не содержащее ни одного элемента, называется пустым множеством.

Над множествами можно производить операции, напоминающие операции, производимые в арифметике над числами. Объединением AB множеств A и B называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из множеств A и B (элемент, принадлежащий множествам A и B одновременно засчитывается при включении в AB только один раз). Пересечением AB множеств A и B называется множество, состоящее из всех элементов, принадлежащих как A, так и B. Предположим, например, что множество I состоит из всех букв русского алфавита, A – из всех согласных, а множество B – из букв, встречающихся в слове «энциклопедия». Тогда объединение AB состоит из всех букв алфавита, кроме а, ё, у, ъ, ь, ы, ю, пересечение AB – из букв д, к, л, н, п, ц, а дополнение C(A) – из всех гласных. Раздел теории множеств, который занимается исследованием операций над множествами, называется алгеброй множеств. Пустое множество играет в алгебре множеств роль нуля, и поэтому его часто обозначают символом О; например, AO = A, AO = O.

Булева алгебра.

Алгебра множеств является подразделом булевых алгебр, впервые возникших в трудах Дж.Буля (1815–1864). В аксиомах булевой алгебры отражена аналогия между понятиями «множества», «событие» и «высказывания». Логические высказывания можно записать с помощью множеств и проанализировать с помощью булевой алгебры.

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

-2831. Не бывает котенка, который любит рыбу и которого нельзя научить всяким забавным штукам;

2. Не бывает котенка без хвоста, который будет играть с гориллой;

3. Котята с усами всегда любят рыбу;

4. Не бывает котенка с зелеными глазами, которого можно научить забавным штукам;

5. Не бывает котят с хвостами, но без усов.

Какое заключение можно вывести из этих утверждений?

Рассмотрим следующие множества (универсальное множество I включает в себя всех котят): A – котята, любящие рыбу; B – котята, обучаемые забавным штукам; D – котята с хвостами; E – котята, которые будут играть с гориллой; F – котята с зелеными глазами и G – котята с усами. Первое утверждение гласит, что множество котят, которые любят рыбу, и дополнение множества котят, обучаемых забавным штукам, не имеют общих элементов. Символически это записывается как

-2831. AC(B) = O.

Аналогичным образом остальные утверждения можно записать так:

-2832. C(D)E = O;

3. G М A;

4. BF = O;

5. D М G.

Принимая во внимание теоретико-множественный смысл символов (или воспользовавшись законами булевой алгебры), мы можем переписать утверждения 1, 2 и 4 в виде

1. A М B;

2. E М D;

4. B М C(F).

Таким образом, мы переформулировали исходные утверждения в следующие:

-2831. Котят, которые любят рыбу, можно обучить забавным штукам;

2. У котят, которые будут играть с гориллой, есть хвосты;

4. У котят, которых можно обучить забавным штукам, глаза не зеленые;

Теперь можно расположить символические записи утверждений в таком порядке, чтобы последний символ предыдущего утверждения совпадал с первым символом следующего (этому условию удовлетворяет расположение утверждений в порядке 2, 5, 3, 1, 4). Возникает цепочка включений E М D М G М A М B М C(F), из которой можно сделать вывод, что E М C(F) или «Не бывает котенка с зелеными глазами, который будет играть с гориллой». Такое заключение едва ли очевидно, если рассматривать пять исходных утверждений в их словесной формулировке.

Сравнение множеств.

Если из элементов двух множеств можно составить пары таким образом, чтобы каждому элементу первого множества соответствовал определенный элемент второго множества, а каждому элементу второго множества соответствовал один и только один элемент первого множества, то говорят, что между такими двумя множествами установлено взаимно однозначное соответствие. Чтобы установить взаимно однозначное соответствие, необязательно пересчитывать элементы множеств. Например, мы знаем, что американские штаты находятся во взаимно однозначном соответствии с их столицами, хотя можем оставаться в неведении относительно общего их числа. Мы могли бы утверждать: «Столиц штатов ровно столько, сколько штатов». Между двумя конечными множествами можно установить взаимно однозначное соответствие тогда и только тогда, когда оба множества состоят из одного и того же числа элементов. В теории множеств аналогичные утверждения используются, даже когда множества содержат бесконечно много элементов. Если между двумя множествами можно установить взаимно однозначное соответствие, то говорят, что они имеют одинаковое количество элементов или равномощны. Если же при любом способе образования пар некоторые элементы из первого множества остаются без пары, то говорят, что первое множество содержит больше элементов, чем второе, или, что первое множество имеет большую мощность. С понятием мощности связаны, казалось бы, удивительные результаты. Например, на первый взгляд положительных целых чисел в два раза больше, чем четных положительных чисел, так как четно каждое второе число. Но, согласно теории множеств, четных положительных чисел столько же, сколько всех положительных целых чисел. Действительно, можно образовать пары чисел 2 и 1, 4 и 2, 6 и 3 и, вообще каждому четному числу 2n поставить в соответствие целое число n. Именно это обстоятельство имел в виду Б.Рассел (1872–1970), сформулировав факт, названный им парадоксом Тристрама Шенди. Герой романа Стерна сетовал на то, что ему потребовался целый год, чтобы изложить события первого дня его жизни, еще один год понадобился, чтобы описать второй день, и что при таком темпе он никогда не завершит свое жизнеописание. Рассел возразил, заметив, что если бы Тристрам Шенди жил вечно, то смог бы закончить свое жизнеописание, так как события n-го дня Шенди мог бы описать за n-й год и, таким образом, в летописи его жизни ни один день не остался бы не запечатленным. Иначе говоря, если бы жизнь длилась бесконечно, то она насчитывала бы столько же лет, сколько дней. Эти примеры показывают, что бесконечное множество можно поставить во взаимно однозначное соответствие со своим бесконечным подмножеством. Иногда это свойство принимают за определение бесконечного.

Если можно установить взаимно однозначное соответствие между некоторым множеством и множеством положительных целых чисел, то говорят, что такое множество счетно. Для обозначения количества элементов в счетном множестве часто используют символ А0 (алеф-нуль). Так называемые «трансфинитные» числа, например А0, могут не подчиняться обычным законам арифметики. Например, так как существует А0 четных чисел, А0 нечетных и А0 целых чисел, то приходится признать, что А0 + А0 = А0. Идея сравнения множеств путем установления взаимно однозначного соответствия между ними используется в различных разделах математики. Число всех действительных чисел, как показал основатель научной теории множеств Г.Кантор (1845–1918), больше, чем А0 чисел. Следовательно, если можно показать, что множество действительных чисел, обладающих некоторым особым свойством, является всего лишь счетным множеством, то заведомо должны существовать действительные числа, этим свойством не обладающие. Например, так как множество алгебраических чисел счетно, должны существовать неалгебраические числа. Такие числа называются трансцендентными.

Поразительная и далеко не очевидная теорема, высказанная в качестве гипотезы Кантором и доказанная Э.Шрёдером и Ф.Бернштейном около 1896, утверждает, что если можно установить взаимно однозначное соответствие между множеством A и подмножеством множества B, и между множеством B и подмножеством множества A, то существует взаимно однозначное соответствие между всем множеством A и всем множеством B.