Множества и операции над множествами

Что такое множества, где и как они применяются

В математике понятие множества является одним из основных, фундаментальным, однако единого определения множества не существует. Одним из наиболее устоявшихся определений множества является следующее: под множеством понимают любое собрание определённых и отличных друг от друга объектов, мыслимых как единое целое. Создатель теории множеств немецкий математик Георг Кантор (1845-1918) говорил так: "Множество есть многое, мыслимое нами как целое".

Ели ли Вы сегодня обед? Сейчас станет известна страшная тайна. Обед является множеством. А именно, множеством блюд, из которых он состоит. В нём (как правило) нет одинаковых блюд, и во множестве все элементы должны быть разными. А, если на обед у Вас был тот же самый салат, что и на завтрак, то этот салат является пересечением множеств "Обед" и "Завтрак".

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

А улица, на которой Вы живёте? Она является собранием многих разных объектов, но обязательно есть множество домов, расположенных на этой улице. Поэтому множество домов является подмножеством множества "Улица".

Итак, мы рассмотрели не только примеры множеств, но и пример операции над множествами - пересечение, а также отношение включения подмножества во множество. Все эти понятия будем рассматривать подробно на этом уроке.

Но пока ещё один пример практического рассмотрения множеств.

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

Пример 0 (Паскаль). Существует набор продуктов, продаваемых в нескольких магазинах города. Определить: какие продукты есть во всех магазинах города; полный набор продуктов в городе.

Решение. Определяем базовый тип данных Food (продукты), он может принимать значения, соответствующие названиями продуктов (например, hleb). Объявляем тип множества, он определяет все подмножества, составленные из комбинаций значений базового типа, то есть Food (продукты). И формируем подмножества: магазины "Солнышко", "Ветерок", "Огонёк", а также производные подмножества: MinFood (продукты, которые есть во всех магазинах), MaxFood (полный набор продуктов в городе). Далее прописываем операции для получения производных подмножеств. Подмножество MinFood получается в результате пересечения подмножеств Solnyshko, Veterok и Ogonyok и включает те и только те элементы этих подмножеств, которые включены в каждое их этих подмножеств (в Паскале операция пересечения множеств обозначается звёздочкой: A * B * C, математическое обозначение пересечения множеств дано далее). Подмножество MaxFood получается в результате объединения тех же подмножеств и включает элементы, которые включены во все подмножества (в Паскале операция объединения множеств обозначается знаком "плюс": A + B + C, математическое обозначение объединения множеств дано далее).

Код PASCAL

Какие бывают множества

Объекты, составляющие множества - объекты нашей интуиции или интеллекта - могут быть самой различной природы. В примере в первом параграфе мы разобрали множества, включающие набор продуктов. Множества могут состоять, например, и из всех букв русского алфавита. В математике изучаются множества чисел, например, состоящие из всех:

- натуральных чисел 0, 1, 2, 3, 4, .

- чётных целых чисел

и т.п. (основные числовые множества рассмотрены в соответствующем параграфе этого материала).

Объекты, составляющие множество, называются его элементами. Можно сказать, что множество - это "мешок с элементами". Очень важно: в множестве не бывает одинаковых элементов.

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

Если M - множество, а a - его элемент, то пишут: a∈M , что означает " a принадлежит множеству M".

Из первого (нулевого) примера на Паскале с продуктами, которые есть в тех или иных магазинах:

что означает: элемент "hleb" принадлежит множеству продуктов, которые есть в магазине "VETEROK".

Существуют два основных способа задания множеств: перечисление и описание.

Множество можно задать, перечислив все его элементы, например:

Перечислением можно задать только конечное множество. Хотя можно сделать это и описанием. Но бесконечные множества можно задать только описанием.

Для описания множеств используется следующий способ. Пусть p(x) - некоторое высказывание, которое описывает свойства переменной x , областью значений которых является множество M . Тогда через M = обозначаентся множество, состоящее из всех тех и только тех элементов, для которых высказывание p(x) истинно. Это выражение читается так: "Множество M , состоящее из всех таких x , что p(x) ".

означает множество корней уравнения x² - 3x + 2 = 0 , т. е. множество . Это конечное множество.

А следующим описанием задаётся множество всех целых чисел больше 5:

это множество является бесконечным.

Описанием предпочтительно задавать и конечные множества, в которых очень много элементов, например, множество всех натуральных чисел от 2 до 22³ :

Множество, не содержащее ни одного элемента, называется пустым и обозначается знаком ∅.

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

Два множества называюся равными, если они состоят из одних и тех же элементов. Например, равны множество равносторонних треугольников и множество равноугольных треугольников, так как это одни и те же треугольники: если в треугольнике все стороны равны, то равны и все его углы. Обратно, из равенства всех трёх углов треугольника вытекает равенство всех трёх его сторон. Равны любые два конечных множетсва, отличающиеся друг от друга только лишь порядком их элементов, например, = .

Пример 1. Равны ли множества

Решение. Так как множества и состоят из одних и тех же элементов, то они равны.

Множества и не равны, так как первое множество двухэлементное, а второе - одноэлементное.

Пример 2. Даны три множества:

Соотношение A∈B верно, так как множество A является первым элементом множества B.

Соотношение B∈C верно, так как множество B является первым элементом множества C.

Соотношение A∉C верно, так как множество A не является элементом множества C. Множество A является элементом множества B, которое является элементом множества C, но множества A и B - это разные множества.

Если А - конечное множество, то через обозначается число его элементов, которое называется мощностью множества.

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

Всякий квадрат является прямоугольником. Из этого следует, что множество квадратов является частью множества прямоугольников, или, как говорят в математике, является подмножеством множества прямоугольников.

Множество А включено в множество В (символическая запись ), если любой элемент множества А принажлежит множеству В . В этом случае множество А является подмножеством множества В .

Если и , то пишут и говорят, что множество А строго включено в множество В или что А есть собственное подмножество В .

Например, если и , то А есть собственное подмножество В .

Верно следующее утверждение: пустое множество есть подмножество любого множества, то есть для любого множества А

Если множество содержит по крайней мере два элемента, то оно имеет всевозможные подмножества, среди которых есть и собственные подмножества.

Например, всевозможные подмножества множества это

из которых и - собственные подмножества множества .

Множество всех подмножеств множества А называется множеством-степенью множества А и обозначается .

Например, если , то

Теорема о мощности множества степени:

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

Пример 3. Сколько элементов содержит множество

Основные числовые множества

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

Числа, которые можно использовать для счёта предметов (то есть положительные целые числа, часто к ним относят и ноль) составляют множество натуральных чисел N :

Натуральные числа, числа противоположные им по знаку (то есть, отрицательные целые числа) и ноль составляют множество целых чисел Z :

Числа, записанные в виде p/q , причём p и q - целые числа и q не равно нулю, составляют множество рациональных чисел Q .

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

Рациональные числа могут быть представлены в виде конечных либо бесконечных периодических дробей, например:

Числа и не являются рациональными числами. Они не могут быть представлены в виде периодических дробей. Но они могут быть представлены в виде непериодических дробей.

Числа, которые можно представить в виде непериодических дробей, составляют множество иррациональных чисел I :

Рациональные и иррациональные числа составляют множество действительных чисел R :

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

Пример 4. Пусть A - множество всех натуральных чётных чисел больше нуля, а B - множество всех натуральных чисел, представимых в виде суммы двух нечётных натуральных чисел. Доказать, что A=B .

Решение. Для доказательства равенства данных множеств покажем, что каждый элемент множества A является элементом и множества B , и наоборот, каждый элемент множества B является и элементом множества A .

Шаг 1. Элемент принадлежит множеству A : x∈A . Докажем, что элемент x принадлежит и множеству B . Если x∈A , то x = 2k , где k ≥ 1 (любое число, умноженное на 2, является чётным числом). Но x = 2k можно представить и в виде (2k - 1) + 1 , что является суммой двух нечётных натуральных чисел. Натуральных, поскольку k ≥ 1 . Следовательно, x∈B .

Шаг 2. Элемент принадлежит множеству B : x∈B . Докажем, что элемент x принадлежит и множеству A . Если x∈B , то x = (2k - 1) + (2m - 1) , где 2k - 1 и 2m - 1 - нечётные натуральные числа, т.е. 2k - 1 ≥ 1 и 2m - 1 ≥ 1 . Следовательно, x = (2k + 2m - 2) = 2(k + m - 1) , где k + m - 1 ≥ 1 , значит, x∈A .

Таким образом, равенство множеств A и B доказано.

Устоявшиеся ныне представления о числовых множествах явились результатом эволюции изучения математиками различных чисел и добавления новых множеств (систем) чисел. Древнегреческие математики считали "настоящими" только натуральные числа, но в практических расчётах за два тысячелетия до н.э. в Древнем Египте и Древнем Вавилоне уже применялись дроби. Следующим важным этапом в развитии понятий о числе было введение отрицательных чисел - это было сделано китайскими математиками за два века до н.э. Отрицательные числа применял в III веке н.э. древнегреческий математик Диофант, знавший уже правила действий над ними. А в VII веке н.э. эти числа подробно изучили индийские математики, которые сравнивали такие числа с долгом. С помощью отрицательных чисел можно было единым образом описывать изменения величин. В результате всех этих занятий и сложилось близкое к современному понятие о множестве целых чисел, а в результате изучения свойств дробей - о множествах рациональных и иррациональных чисел.

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

Операции над множествами: объединение, пересечение, разность, декартово произведение

Объединением множеств А и В называется множество, обозначаемое , состоящее из всех тех и только тех элементов, которые принадлежат или А или В , то есть

Например, если , , , то , , .

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

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

Например, если , , , то , , .

На рисунке ниже - результат пересечения множеств А и В - заштрихованная фигура.

Операция пересечения есть в реляционной алгебре, используемой для манипулирования данными в языках запросов к базам данных, например, SQL.

Разностью множеств А и В называется множество, обозначаемое и состоящее из всех тех и только тех элементов множества А , которые не являются элементами множества В , то есть

Например, если , , , то , , , , .

На рисунке ниже слева - результат разности множеств А и В, а справа - результат разности множеств В и А.

Операция разности есть в реляционной алгебре, используемой для манипулирования данными в языках запросов к базам данных, например, SQL.

Пример 5. Выполните следующие операции над множествами:

Пример 6. Согласно опросу 100 покупателей рынка, купивших цитрусовые, апельсины купили 29 покупателей, лимоны - 30 покупателей, мандарины - 9, только мандарины - 1, апельсины и лимоны - 10, лимоны и мандарины - 4, все три вида фруктов - 3 покупателя. Сколько покупателей не купили ни одного вида перечисленных здесь цитрусовых? Сколько покупателей купили только лимоны?

Для определения ещё одной важной операции над множествами - декартова произведения множеств введём понятие упорядоченного набора длины n.

Длиной набора называется число n его компонент. Набор, составленный из элементов , взятых именно в этом порядке, обозначается . При этом iя ( ) компонента набора есть .

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

Декартовым (прямым) произведением множеств называется множество, обозначаемое и состоящее из всех тех и только тех наборов длины n, i-я компонента которых принадлежит .

А теперь обещанная картинка

На картинке точками (узлами) дерева обозначены элементы множеств , , . Для получения каждой упорядоченной тройки (так как перемножаем три множества) нужно пройти каждый полный маршрут от корня дерева (start) к конечным точкам и записать все пройденные точки. Таким образом, получаем декартово произведение множеств:

Операция декартова произведения есть в реляционной алгебре, используемой для манипулирования данными в языках запросов к базам данных, например, SQL.