Множества и отображения

11. Понятие множества

Любое понятие дискретной математики можно определить с помощью понятия множества. Под множеством понимают объединение в одно общее объектов, хорошо различаемых нашей интуицией или нашей мыслью. Таково интуитивное определение понятия множества, данное основателем теории множеств Георгом Кантором. Это понятие в математике является первичным и, следовательно, не имеет строгого определения. Объекты, составляющие множество, будем называть его элементами. Множества будем обозначать прописными буквами латинского алфавита: А,В, С,, а элементы множеств — строчными буквами а,Ъ,с,.... Основное отношение между элементом а и содержащим его множеством А, обозначается так: а е А (а принадлежит А). Если а не является элементом множества А, то пишут а ^ А (а не принадлежит А). Некоторые множества имеют общепринятые обозначения: N — множество натуральных чисел; R — множество действительных чисел; Z — множество целых чисел.

12. Способы задания множеств

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

Первый способ мы назовем описанием множества, а второй способ — перечислением множества. Например, обозначение {х € U : а(х)} читается: «элементы множества U, обладающие свойством а» — это описание множества. Элементы перечисляемого множества принято заключать в скобки: {1,2,3,...} — множество натуральных чисел; {2,4, 6, } — множество четных чисел. Под многоточием в первом случае подразумеваются все последующие натуральные числа, а во втором — четные.

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

13. Подмножества

Множество, состоящее из некоторых элементов другого множества, называется подмножеством этого последнего множества. С целью изуче­ния всех подмножеств данного множества введем следующую терминоло­гию. Исходное множество будем называть универсальным множеством; подмножества, содержащие один элемент, будем называть единичными множествами; множество, вовсе не содержащее никаких элементов, бу­дем называть пустым множеством и обозначать 0.

В качестве примера возьмем универсальное множество U, состоящее из трех элементов {а,Ь,с}. Собственные подмножества U — это множе­ства, которые содержат некоторые, но не все элементы U. Этими подмно­жествами являются три множества из двух элементов {а, Ь), {а, с}, {Ъ, с} и три единичных множества {а}, {6}, {с\.

Будем считать подмножеством множества U и пустое множество 0, не содержащее элементов U.

Другими словами, множество А называется подмножеством множе­ства В (обозначаем А С В), если все элементы множества А принадле­жат Б. Это означает справедливость следующего утверждения: для любо­го элемента а, если а £ А, то а £ Б при условии А с Б. Будем говорить также, что множество А содержится в Б или имеется включение множе­ства А в Б. Множества А и Б называются равными или совпадающими (обозначается А = Б), если они состоят из одних и тех же элементов, т. е. если А С Б и Б С А. Таким образом, чтобы доказать равенство множеств, требуется установить два включения.