Данная тема содержит немало терминологии, поэтому я добавлю содержание темы, которое позволит легче ориентироваться в материале.
Начнём с того, что же, собственно, понимать под словом "множество". На интуитивном уровне под множеством понимают некую совокупность объектов, именуемых элементами множества. Например, можно говорить о множестве груш на столе, множестве букв в слове "множество" и так далее. Георг Кантор (немецкий математик, основатель современной теории множеств) писал, что под "множеством я понимаю вообще всё то многое, которое возможно мыслить как единое, т.е. такую совокупность определённых элементов, которая посредством одного закона может быть соединена в одно целое". Некоторое время понятие множества, введённое Кантором, полагалось довольно очевидным и не требующим дополнительных пояснений. Казалось, что появление работ Больцано, а затем и Кантора в конце 19 - начале 20 века, положит конец многим вопросам (например, окончательно разрешит апории Зенона, разрешит проблему бесконечности и т.д.) и станет началом новой математики. Гениальный немецкий математик Давид Гильберт отмечал, что "Никто не изгонит нас из рая, созданного Кантором".
Однако появление парадоксов (Рассел, Бурали-Форти) положило конец "канторовскому раю". Одна из формулировок парадокса Рассела, известная под названием "парадокс брадобрея" звучит так: в некотором селе брадобрей бреет тех и только тех жителей села, которые не бреются сами. Кто же тогда бреет самого брадобрея? Допустим, он бреет себя самостоятельно. Т.е. он принадлежит к тем жителям села, которые бреются сами, – а ведь согласно условию этих жителей брадобрей не имеет права брить. Следовательно, допущение о том, что брадобрей бреется сам, приводит к противоречию. Попробуем иначе: пусть брадобрей не бреется сам. Если он сам не бреется, то согласно условию его обязан брить брадобрей – вновь противоречие! Были предприняты попытки разрешить противоречия теории множеств, предложенной Кантором. Саму канторовскую теорию множеств математики назвали "наивной". Целью многих математических трудов стало построение такой системы аксиом, в которой подобные парадоксы были бы невозможны. Но задача оказалась не столь уж проста. На данный момент, насколько мне известно, единой аксиоматики теории множеств нет. Наиболее распространенной считается система аксиом Цермело-Френкеля (ZFC), в которой особняком стоит так называемая "аксиома выбора". Есть и вариации этой системы: например, автор B-метода Жан-Раймонд Абриал предложил типизированную теорию множеств, на основании которой создал формальный метод разработки программ.
Обозначение множеств. Принадлежность элемента множеству. Пустое множество.
Обычно множества записываются в фигурных скобках. Например, множество всех гласных букв русского алфавита будет записано так:
\[\{а, е, ё, и, о, у, ы, э, ю, я \} \]
А множество всех целых целых чисел, больших 8, но меньших 15, будет таким:
\[\{9,10,11,12,13,14 \} \]
Множество может вообще не содержать ни одного элемента. В этом случае его именуют пустым множеством и обозначают как \(\displaystyle{\varnothing}\).
Чаще всего в математической литературе множества обозначаются с помощью больших букв латинского алфавита. Например:
\[A=\{0, 5, 6, -9 \},\; B=\{\Delta, +, -5, 0\}.\]
Есть и устоявшиеся обозначения определённых множеств. Например, множество натуральных чисел принято обозначать буквой \(\displaystyle{N}\); множество целых чисел – буквой \(\displaystyle{Z}\); множество рациональных чисел – буквой \(\displaystyle{Q}\); множество всех действительных чисел – буквой \(\displaystyle{R}\). Есть и иные устоявшиеся обозначения, но к ним мы станем обращаться по мере необходимости.
Множество, которое содержит конечное количество элементов, именуют конечным множеством. Если множество содержит бесконечное количество элементов, его называют бесконечным.
Например, указанное выше множество \(\displaystyle{A=\{0, 5, 6, -9 \}}\) – конечное множество, ибо содержит 4 элемента (т.е. конечное число элементов). Множество натуральных чисел \(\displaystyle{N}\) является бесконечным. Вообще говоря, мы не всегда можем сразу с уверенностью сказать, бесконечно некое множество или нет. Например, пусть \(\displaystyle{F}\) – множество простых чисел.
Что такое простое число?
Простыми числами именуют такие натуральные числа большие 1, которые делятся лишь на 1 или на самое себя. Например, 2, 3, 5, 7 и так далее. Для сравнения: число 12 не является простым числом, так как оно делится не только на 12 и 1, а ещё и на иные числа (например, на 3). Число 12 является составным.
Возникает вопрос: бесконечно множество \(\displaystyle{F}\) или нет? Существует ли наибольшее простое число? Для ответа на этот вопрос понадобилась целая теорема, доказанная Эвклидом, о том, что множество простых чисел – бесконечно.
Под мощностью множества для конечных множеств понимают количество элементов данного множества. Мощность множества \(\displaystyle{A}\) обозначается как \(\displaystyle{|A|}\).
Например, так как конечное множество \(\displaystyle{A=\{0, 5, 6, -9 \}}\) содержит 4 элемента, то мощность множества \(\displaystyle{A}\) равна 4, т.е. \(\displaystyle{|A|=4}\).
Если нам известно, что некий объект \(\displaystyle{a}\) принадлежит множеству \(\displaystyle{A}\), то записывают это так: \(\displaystyle{a\in A}\). Например, для вышеуказанного множества \(\displaystyle{A}\) можно записать, что \(\displaystyle{5\in A}\),\(\displaystyle{-9\in A}\). Если же объект \(\displaystyle{a}\) не принадлежит множеству \(\displaystyle{A}\), то обозначается это следующим образом: \(\displaystyle{a\notin A}\). Например, \(\displaystyle{19\notin A}\). Кстати, сказать, элементами множеств могут быть и иные множества, например:
\[
M=\{-9,1,0, \{ a, g\}, \varnothing \}
\]
Элементами множества \(\displaystyle{M}\) являются числа -9, 1, 0, а также множество \(\displaystyle{ \{ a,\; g\}}\) и пустое множество \(\displaystyle{\varnothing}\). Вообще, для упрощения восприятия множество можно представлять как портфель. Пустое множество – пустой портфель. Эта аналогия пригодится чуть далее.
Множество \(\displaystyle{A}\) называют подмножеством множества \(\displaystyle{B}\), если все элементы множества \(\displaystyle{A}\) являются также элементами множества \(\displaystyle{B}\). Обозначение: \(\displaystyle{A\subseteq B}\).
Например, рассмотрим множества \(\displaystyle{K=\{ -9,5\}}\) и \(\displaystyle{T=\{8,-9,0,5,p, -11\}}\). Каждый элемент множества \(\displaystyle{K}\) (т.е. -9 и 5) является также элементом множества \(\displaystyle{T}\). Следовательно, множество \(\displaystyle{K}\) есть подмножество множества \(\displaystyle{T}\), т.е. \(\displaystyle{K\subseteq T}\).
Так как все элементы любого множества \(\displaystyle{A}\) принадлежат самому множеству \(\displaystyle{A}\), то множество \(\displaystyle{A}\) является подмножеством самого множества \(\displaystyle{A}\). Пустое множество \(\displaystyle{\varnothing}\) является подможеством любого множества. Т.е. для произвольного множества \(\displaystyle{A}\) верно следующее:
\[A\subseteq A; \; \varnothing\subseteq A.\]
Введём ещё одно определение – универсальное множество.
Универсальное множество (универсум) \(\displaystyle{U}\) обладает тем свойством, что все иные множества, рассматриваемые в данной задаче, являются его подмножествами.
Иными словами, универсум содержит в себе элементы всех множеств, которые рассматриваются в рамках некоей задачи. Например, рассмотрим такую задачу: проводится опрос студентов некоей академгруппы. Каждому студенту предлагается указать мобильных операторов РФ, сим-карты которых он использует. Данные этого опроса можно представить в виде множеств. Например, если студент Василий использует сим-карты от МТС и Life, то можно записать следующее:
\[
Vasilij=\{MTC, Life \}
\]
Подобные множества можно составить для каждого студента. Универсумом в этой модели будет множество, в котором перечислены все операторы России. В принципе, в качестве универсума можно взять также множество, в котором перечислены все операторы СНГ, а также множество всех мобильных операторов мира. И это не будет противоречием, ибо любой оператор России входит в множество операторов как СНГ, так и всего мира. Итак, универсум определяется только в рамках некоей конкретной задачи, при этом зачастую можно рассмотреть несколько универсальных множеств.
Множества \(\displaystyle{A}\) и \(\displaystyle{B}\) называются равными, если они состоят из одних и тех же элементов. Иными словами, если каждый элемент множества \(\displaystyle{A}\) является также элементом множества \(\displaystyle{B}\), и каждый элемент множества \(\displaystyle{B}\) является также элементом множества \(\displaystyle{A}\), то \(\displaystyle{A=B}\).
Определение равенства множеств можно записать и по-иному: если \(\displaystyle{A\subseteq B}\) и \(\displaystyle{B\subseteq A}\), то \(\displaystyle{A=B}\).
Рассмотрим пару множеств: первое будет \(\displaystyle{\{\Delta, k \}}\), а второе – \(\displaystyle{\{k, \Delta\}}\). Каждый элемент первого множества (т.е. \(\displaystyle{\Delta}\) и \(\displaystyle{k}\)) является также элементом второго множества. Каждый элемент второго множества (т.е. \(\displaystyle{k}\) и \(\displaystyle{\Delta}\)) является также элементом второго множества. Вывод: \(\displaystyle{\{\Delta, k \}=\{k, \Delta\}}\). Как видите, порядок записи элементов в множестве роли не играет.
Рассмотрим ещё пару множеств: \(\displaystyle{X=\{k, \Delta, k, k,k \}}\) и \(\displaystyle{Y=\{\Delta, k \}}\). Каждый элемент множества \(\displaystyle{X}\) является также элементом множества \(\displaystyle{Y}\); каждый элемент множества \(\displaystyle{Y}\) является также элементом множества \(\displaystyle{X}\). Следовательно, \(\displaystyle{\{k, \Delta, k, k, k \}=\{\Delta, k \}}\). С учётом подобных равенств в теории множеств принято одинаковые элементы не повторять в записи дважды. Например, множество цифр числа 1111111555559999 будет таким: \(\displaystyle{\{1,5,9\}}\). Есть, конечно, исключения: так называемые мультимножества. В записи мультимножеств элементы могут повторяться, однако в классической теории множеств повторения элементов не допускаются.
Используя понятие равенства множеств, можно классифицировать подмножества.
Если \(\displaystyle{A\subseteq B}\), при этом \(\displaystyle{A\neq B}\), то множество \(\displaystyle{A}\) называют собственным (строгим) подмножеством множества \(\displaystyle{B}\). Также говорят, что множество \(\displaystyle{A}\) строго включено в множество \(\displaystyle{B}\). Записывают это так: \(\displaystyle{A \subset B}\).
Если же некое подмножество множества \(\displaystyle{A}\) совпадает с самим множеством \(\displaystyle{A}\), то это подмножество называют несобственным. Иными словами, множество \(\displaystyle{A}\) является несобственным подмножеством самого множества \(\displaystyle{A}\).
Например, для рассмотренных выше множеств \(\displaystyle{K=\{ -9,5\}}\) и \(\displaystyle{T=\{8,-9,0,5,p, -11\}}\) имеем: \(\displaystyle{K\subseteq T}\), при этом \(\displaystyle{K\neq T}\). Следовательно, множество \(\displaystyle{K}\) является собственным подмножеством множества \(\displaystyle{T}\), что записывается как \(\displaystyle{K\subset T}\). Можно сказать и так: множество \(\displaystyle{K}\) строго включено в множество \(\displaystyle{T}\). Запись \(\displaystyle{K\subset T}\) более конкретна, нежели \(\displaystyle{K\subseteq T}\). Дело в том, что записывая \(\displaystyle{K\subset T}\) мы гарантируем, что \(\displaystyle{K\neq T}\). В то время как запись \(\displaystyle{K\subseteq T}\) не исключает случая равенства \(\displaystyle{K=T}\).
Примечание относительно терминологии
Вообще говоря, тут есть некая путаница в терминологии. Приведённое выше определение несобственных множеств принято в американской и части отечественной литературы. Однако в другой части отечественной литературы есть несколько иная трактовка понятия несобственных множеств.
Если \(\displaystyle{A\subseteq B}\), при этом \(\displaystyle{A\neq B}\) и \(\displaystyle{A\neq \varnothing}\), то множество \(\displaystyle{A}\) называют собственным (строгим) подмножеством множества \(\displaystyle{B}\). Также говорят, что множество \(\displaystyle{A}\) строго включено в множество \(\displaystyle{B}\). Записывают это так: \(\displaystyle{A \subset B}\). Множества \(\displaystyle{B}\) и \(\displaystyle{\varnothing}\) именуются несобственными подмножествами множества \(\displaystyle{B}\).
Иными словами, пустое множество в такой трактовке исключается из собственных подмножеств и переходит в разряд несобственных. Выбор терминологии – дело вкуса.
Множество всех подмножеств некоего множества \(\displaystyle{A}\) называют булеаном или степенью множества \(\displaystyle{A}\). Обозначается булеан как \(\displaystyle{P(A)}\) или \(\displaystyle{2^A}\).
Пусть множество \(\displaystyle{A}\) содержит \(\displaystyle{n}\) элементов. Булеан множества \(\displaystyle{A}\) содержит \(\displaystyle{2^n}\) элементов, т.е.
\[
\left| P(A) \right|=2^{n},\;\; n=|A|.
\]
Рассмотрим пару задач на использование введённых выше понятий.
Задача №1
Условие
Из предложенного списка выберите те утверждения, которые являются верными. Ответ аргументируйте.
Нам заданы два множества: \(\displaystyle{\{-3,5, 9 \}}\) и \(\displaystyle{\{-3, 9, 8, 5, 4, 6 \}}\). Каждый элемент первого множества является также элементом второго множества. Следовательно, первое множество есть подмножество второго, т.е. \(\displaystyle{\{-3,5, 9 \}\subseteq \{-3, 9, 8, 5, 4, 6 \}}\). Утверждение первого пункта – верное.
В первом пункте мы выяснили, что \(\displaystyle{\{-3,5, 9 \}\subseteq \{-3, 9, 8, 5, 4, 6 \}}\). При этом данные множества не равны между собой, т.е. \(\displaystyle{\{-3,5, 9 \}\neq \{-3, 9, 8, 5, 4, 6 \}}\). Значит, множество \(\displaystyle{\{-3,5, 9 \}}\) является собственным (в иной терминологии строгим) подмножеством множества \(\displaystyle{\{-3, 9, 8, 5, 4, 6 \}}\). Этот факт записывается как \(\displaystyle{\{-3,5, 9 \}\subset \{-3, 9, 8, 5, 4, 6 \} }\). Итак, утверждение второго пункта истинно.
Множество \(\displaystyle{\{-3,5, 9 \}}\) не является элементом множества \(\displaystyle{\{-3, 9, 8, 5, 4, 6 \}}\). Утверждение третьего пункта ложно. Для сравнения: утверждение \(\displaystyle{\{-3,5, 9 \}\in \{9, 8, 5, 4, \{-3,5,9\}, 6 \}}\) истинно.
Пустое множество является подможеством любого множества. Поэтому утверждение \(\displaystyle{\varnothing \subseteq \varnothing}\) истинно.
Утверждение ложно. Множество \(\displaystyle{\varnothing}\) не содержит элементов, а множество \(\displaystyle{\{\varnothing \}}\) содержит один элемент, посему равенство \(\displaystyle{\varnothing=\{\varnothing \}}\) неверно. Чтобы это было нагляднее, можно обратиться к той аналогии, что я описал выше. Множество – это портфель. Пустое множество \(\displaystyle{\varnothing}\) – пустой портфель. Множество \(\displaystyle{\{\varnothing \}}\) – портфель, внутри которого лежит пустой портфель. Естественно, что пустой портфель и непустой портфель, внутри которого нечто есть – разные портфели :)
Пустое множество не содержит элементов. Ни единого. Поэтому утверждение \(\displaystyle{\varnothing \in \varnothing}\) ложно. Для сравнения: утверждение \(\displaystyle{\varnothing\in\{\varnothing \}}\) истинно.
Множество \(\displaystyle{A}\) содержит 4 элемента, а именно: 9, -5, 8 и \(\displaystyle{\{7, 6 \}}\). Поэтому мощность множества \(\displaystyle{A}\) равна 4, т.е. \(\displaystyle{|A|=4}\). Следовательно, утверждение о том, что \(\displaystyle{|A|=5}\) – ложно.
Ответ:
Утверждения в пунктах №1, №2, №4 – истинны.
Задача №2
Условие
Записать булеан множества \(\displaystyle{A=\{-5,10,9\}}\).
Решение
Множество \(\displaystyle{A}\) содержит 3 элемента. Иными словами: мощность множества \(\displaystyle{A}\) равна 3, \(\displaystyle{|A|=3}\). Следовательно, множество \(\displaystyle{A}\) имеет \(\displaystyle{2^3=8}\) подмножеств, т.е. булеан множества \(\displaystyle{A}\) будет состоять из восьми элементов. Перечислим все подмножества множества \(\displaystyle{A}\). Напомню, что пустое множество \(\displaystyle{\varnothing}\) является подмножеством любого множества. Итак, подмножества таковы:
Напомню, что подмножество \(\displaystyle{\{-5, 10, 9 \}}\) является несобственным, так как совпадает с множеством \(\displaystyle{A}\). Все остальные подмножества – собственные. Все записанные выше подмножества являются элементами булеана множества \(\displaystyle{A}\). Итак:
Первый способ – это простое перечисление элементов множества. Естественно, такой способ подходит лишь для конечных множеств. Например, с помощью данного способа множество первых трёх натуральных чисел будет записано так:
\[
\{1,2,3\}
\]
Часто в литературе можно встретить обозначения такого характера: \(\displaystyle{T=\{0,2,4,6,8, 10, \ldots \}}\). Здесь множество задаётся не перечислением элементов, как кажется на первый взгляд. Перечислить все чётные неотрицательные числа, которые и составляют множество \(\displaystyle{T}\), невозможно, ибо этих чисел бесконечно много. Запись вида \(\displaystyle{T=\{0,2,4,6,8, 10, \ldots \}}\) допускается только тогда, когда не вызывает разночтений.
Второй способ – задать множество с помощью так называемого характеристического условия (характеристического предиката) \(\displaystyle{P(x)}\). В этом случае множество записывается в таком виде:
\[\{x| P(x)\}\]
Запись \(\displaystyle{\{x| P(x)\}}\) читается так: "множество всех элементов \(\displaystyle{x}\), для которых высказывание \(\displaystyle{P(x)}\) истинно". Что именно значит словосочетание "характеристическое условие" проще пояснить на примере. Рассмотрим такое высказывание:
\[P(x)="x\; – \;натуральное\; число,\; последняя\; цифра\; которого \;равна\; 7"\]
Подставим в это высказывание вместо \(\displaystyle{x}\) число 27. Мы получим:
\[P(27)="27\; – \;натуральное\; число,\; последняя\; цифра\; которого \;равна\; 7"\]
Это истинное высказывание, так как 27 действительно является натуральным числом, последняя цифра которого равна 7. Подставим в это высказывание число \(\displaystyle{\frac{2}{5}}\):
\[P\left(\frac{2}{5}\right)="\frac{2}{5}\; – \;натуральное\; число,\; последняя\; цифра\; которого \;равна\; 7"\]
Это высказывание ложно, так как \(\displaystyle{\frac{2}{5}}\) не является натуральным числом. Итак, для некоторых объектов \(\displaystyle{x}\) высказывание \(\displaystyle{P(x)}\) может быть ложно, для некоторых – истинно (а для некоторых вообще не определено). Нас будут интересовать лишь те объекты, для которых высказывание \(\displaystyle{P(x)}\) будет истинно. Именно эти объекты и образуют множество, заданное с помощью характеристического условия \(\displaystyle{P(x)}\) (см. задачу №3).
Третий способ – задать множество с помощью так называемой порождающей процедуры. Порождающая процедура описывает, как получить элементы множества из уже известных элементов или неких иных объектов (см. задачу №4).
Задача №3
Условие
Записать множество \(\displaystyle{A=\{x| x\in Z \wedge x^2 \lt 10\}}\) перечислением элементов.
Решение
Множество \(\displaystyle{A}\) задано с помощью характеристического условия. Характеристическое условие в данном случае выражено записью "\(\displaystyle{x\in Z \wedge x^2 \lt 10}\)" (знак "\(\displaystyle{\wedge}\)" означает "и"). Расшифровывается эта запись так: "\(\displaystyle{x}\) – целое число, и \(\displaystyle{x^2 \lt 10}\)". Иными словами, в множество \(\displaystyle{A}\) должны входить лишь целые числа, квадрат которых меньше 10. Таких чисел всего 7, т.е.
\[
A=\{0,-1,1,-2,2,-3,3\}
\]
Множество \(\displaystyle{A}\) теперь задано с помощью перечисления элементов.
Ответ:
\(\displaystyle{A=\{0,-1,1,-2,2,-3,3\}}\).
Задача №4
Условие
Описать элементы множества \(\displaystyle{M}\), которое задано такой порождающей процедурой:
\(\displaystyle{3\in M}\);
Если элемент \(\displaystyle{x\in M}\), то \(\displaystyle{3x\in M}\).
Множество \(\displaystyle{M}\) – является подмножеством любого множества \(\displaystyle{A}\), удовлетворяющего условиям №1 и №2.
Решение
Давайте пока оставим в покое условие №3 и посмотрим, какие элементы входят в множество \(\displaystyle{M}\). Число 3 туда входит согласно первому пункту. Так как \(\displaystyle{3\in M}\), то согласно пункту №2 имеем: \(\displaystyle{3\cdot 3\in M}\), т.е. \(\displaystyle{9\in M}\). Так как \(\displaystyle{9\in M}\), то согласно пункту №2 получим: \(\displaystyle{3\cdot 9\in M}\), т.е. \(\displaystyle{27\in M}\). Так как \(\displaystyle{27\in M}\), то по тому же пункту №2 имеем: \(\displaystyle{81\in M}\). Короче говоря, построенное множество 3, 9, 27, 81 и так далее – это натуральные степени числа 3.
Итак, кажется, что искомое множество задано. И выглядит оно так: \(\displaystyle{\{3,9,27,81,\ldots \}}\). Однако действительно ли условия №1 и №2 определяют только это множество?
Рассмотрим множество всех натуральных чисел, т.е. \(\displaystyle{N}\). Число 3 – натуральное, посему \(\displaystyle{3\in N}\). Вывод: множество \(\displaystyle{N}\) удовлетворяет пункту №1. Далее, для любого натурального числа \(\displaystyle{x}\) множество \(\displaystyle{N}\) содержит также и число \(\displaystyle{3x}\). Например, 5 и 15, 7 и 21, 13 и 39 и так далее. Значит, множество \(\displaystyle{N}\) удовлетворяет условию №2. И, кстати сказать, не только множество \(\displaystyle{N}\) удовлетворяет условиям №1 и №2. Например, множество всех нечётных натуральных чисел \(\displaystyle{N_1=\{1,3,5,7,9,11, \ldots\}}\) тоже подходит под условия пунктов №1 и №2. Как же указать, что нам нужно именно множество \(\displaystyle{\{3,9,27,81,\ldots \}}\)?
Вот тут на помощь приходит пункт №3. Говоря огрублённо, он означает, что множество \(\displaystyle{M}\) – наименьшее из всех возможных множеств. Так как множества \(\displaystyle{N}\) и \(\displaystyle{\{3,9,27,81,\ldots \}}\) удовлетворяют пунктам №1 и №2, но \(\displaystyle{N\nsubseteq \{3,9,27,81,\ldots \}}\), то множество \(\displaystyle{N}\) не удовлетворяет третьему пункту. Аналогично, так как \(\displaystyle{N_1\nsubseteq \{3,9,27,81,\ldots \}}\), то множество \(\displaystyle{N_1}\) также не удовлетворяет пункту №3. Можно показать (если это необходимо, отпишите мне на почту, я распишу подробнее), что всем трём пунктам удовлетворяет лишь множество \(\displaystyle{\{3,9,27,81,\ldots \}}\), т.е.
\[M=\{3,9,27,81,\ldots \}.\]
Обычно при задании множества с помощью таких правил (которые часто называют рекурсивными или индуктивными) третий пункт подразумевается, но не оговаривается явно. Но нужно иметь его в виду.