1.3 Количество элементов в множестве
Мощность множества – это обобщение понятия количества (числа элементов множества), которое имеет смысл для всех множеств, включая бесконечные.
Существуют большие, есть меньшие бесконечные множества, среди них счётное множество является самым маленьким.
В теории множеств счётное множество есть бесконечное множество, элементы которого возможно занумеровать натуральными числами. Более формально: множество X является счётным, если существует биекция 
, где 
обозначает множество всех натуральных чисел. Другими словами, счётное множество — это множество, равномощное множеству натуральных чисел.
Счётное множество является «наименьшим» бесконечным множеством, т. е. в любом бесконечном множестве найдётся счётное подмножество.
Любое подмножество счётного множества конечно или счётно;
Объединение конечного или счётного числа счётных множеств счётно;
Прямое произведение конечного числа счётных множеств счётно;
Множество всех конечных подмножеств счётного множества счётно;
Множество всех подмножеств счётного множества континуально и, в частности, не является счётным.
Несчётное множество – такое бесконечное множество, которое не является счётным. Таким образом, любое множество является либо конечным, либо счётным, либо несчётным. Множество рациональных чисел и множество алгебраических чисел счётны, однако множество вещественных чисел континуально и, следовательно, несчётно. Два множества называются равномощными, если между ними существует биекция. Существование биекции между множествами есть отношение эквивалентности, а мощность множества — это соответствующий ему класс эквивалентности.
Два конечных множества равномощны тогда и только тогда, когда они состоят из одинакового числа элементов. Т.е. для конечного множества понятие мощности совпадает с привычным понятием количества.
Для бесконечных множеств мощность множества может совпадать с мощностью его собственного подмножества, например 
N (множество натуральных чисел) = <1,2,3,4,5,6,7. >;
0 ,1,-1,2,-2,3,-3… целых чисел столько же, сколько и натуральных
Теорема Кантора гарантирует существование более мощного множества для любого данного: Множество всех подмножеств множества A мощнее A, или | 2 A | > | A | .
С помощью канторова квадрата можно также доказать следующее полезное утверждение: Декартово произведение бесконечного множества A с самим собой равномощно A.
Следуя Кантору, мощность множества называется кардинальным числом и обозначается мощность такого множества A через | A | (сам Кантор использовал обозначение 
). Иногда встречается обозначение 
.
Мощность множества натуральных чисел обозначается символом 
(«алеф-нуль»). Множество называется бесконечным, если его мощность 
, таким образом, счётные множества — это «самые маленькие» из бесконечных множеств. Следующие кардинальные числа в порядке возрастания обозначаются 
.
Про множества, равномощные множеству всех вещественных чисел, говорят, что они имеют мощность континуума, и мощность таких множеств обозначается символом c (continuum). Континуум-гипотеза утверждает, что 
.
Для мощностей, как и в случае конечных множеств, имеются понятия: равенство, больше, меньше. Т.е. для любых множеств A и B возможно только одно из трёх:
| A | = | B | или A и B равномощны;
| A | > | B | или A мощнее B, т. е. A содержит подмножество, равномощное B, но A и B не равномощны;
| A | < | B | или B мощнее A, в этом случае B содержит подмножество, равномощное A, но A и B не равномощны.
Ситуация, в которой A и B не равномощны и ни в одном из них нет части, равномощной другому, невозможна. Это следует из теоремы Цермело. Иначе это означало бы существование несравнимых между собой мощностей (что в принципе возможно, если не принимать аксиому выбора).
Ситуация, в которой | A | > | B | и | A | < | B | , невозможна по теореме Кантора — Бернштейна.
Два множества называются эквивалентными, если их элементы можно разбить на пары, так, чтобы вне этих пар не останется ни одного элемента из этих множеств.
Множество правильных положительных дробей содержит столько же элементов, сколько и натуральных чисел.
Теория множеств: основы и базовые операции над множествами
Мы знаем довольно много о структурах данных, понимаем их устройство, разбираемся, какие структуры работают быстро и помогают решать конкретные задачи. Но эти знания бесполезны, если мы не понимаем, как это использовать в реальной жизни. Это похоже на изучение геометрии в школе. Вы долго считаете предмет бесполезным, пока однажды не появляется необходимость рассчитать площадь пола, чтобы заказать новое ковровое покрытие. Впрочем, пользу геометрии можно почувствовать, даже если вы никогда не считали площадь пола в комнате самостоятельно.
Сегодня поговорим о структуре данных, которая в теории очень догматична, а на практике очень популярна. На самом деле вы так или иначе уже сталкивались с этой структурой, а также слышали о ней на уроках математики в школе. Вы уже догадались, что речь идёт о множествах.
Теория множеств без страха
Прежде чем разбирать устройство множеств, давайте поймём, откуда они появляются. То есть давайте сразу погрузимся в теорию — да-да, в теорию множеств! Не бойтесь сложностей — высока вероятность того, что вы уже так или иначе использовали эту теорию. Возможно, вы сталкивались с теорией множеств, когда проходили в школе диаграмму Венна. Диаграмму Венна включили в программу изучения множеств, так как она хорошо иллюстрирует отношения подмножеств.
Мы выяснили, что теория множеств не должна никого пугать. Теперь пришло время разобраться, что это за теория на самом деле. Множество — математическая концепция. Теорией множеств описывают отношения множеств.
Множество — ни что иное, как неупорядоченная коллекция, в которой нет дублирующихся элементов.
В этом определении есть три важных слова: «неупорядоченная», «дублирующихся» и «элементов». Эти слова точно передают суть и устройство множества. Если мы это запомним, то будем знать основную информацию о том, как работает эта структура данных.
Нужно понять, почему это важно. Для начала давайте посмотрим на множества в действии. Как сказано выше, отношения множеств удачно иллюстрирует диаграмма Венна. Давайте взглянем на два множества: книги, которые есть у человека дома, и книги, которые этот человек прочитал.
Если вы знакомы с диаграммой Венна, то понимаете, что в центре в зелёном круге находятся книги, которыми человек владеет, и которые он прочитал. Здесь множества пересекаются. Также вы понимаете, что два множества — прочитанные человеком книги и книги, которые есть у человека — существуют внутри другого множества. Это все существующие в мире книги.
Диаграмма Венна — хорошая база для понимания теории множеств, так как с её помощью легче понять более сложные вещи. Допустим, вы хотите представить два множества книг в какой-то структуре данных. Вы уже знаете, что книги надо разделить на два множества: которые человек прочитал и которые есть у него дома. Для удобства назовём первое множество Set X, а второе Set Y. Эти множества после реконфигурации в структуры данных можно представить с помощью диаграммы Венна.
Можно заметить, что множества Set X и Set Y стали похожи на объекты или хэши: элементы внутри них не имеют индексов или других элементов, позволяющих их упорядочить. В них также нет повторяющихся элементов, что делает эти структуры данных множествами. Как вы уже знаете, множество — это коллекция неупорядоченных элементов, которые не повторяются.
Начните изучать разработку с бесплатного курса «Основы современной вёрстки». Вы научитесь создавать статические веб-страницы, стилизовать элементы, использовать редакторы кода с полезными расширениями. В конце курса вы опубликуете свой первый сайт на GitHub Pages.
Об операциях с множествами без боли
Какие возможности открывает представление множеств в формате структур данных? С ними теперь можно выполнять разные операции. Две самые важные операции, которые выполняются над множествами — это пересечение и объединение.
Пересечение множеств часто записывается с помощью такой нотации: X ∩ Y. Пересечение определяет, где два множества пересекаются. Другими словами, эта операция возвращает все элементы, которые входят в два множества. В нашем примере пересечение Set X и Set Y возвращает все книги, которые человек читал и которые есть у него дома. Хороший ключ к пониманию пересечения — ключевое слово «и». Мы получаем книги, которые человек читал и которые есть у него дома. Несмотря на то, что полученные с помощью пересечения книги существуют в двух множествах, мы не повторяем их, так как в множестве могут быть только уникальные элементы.
Объединение двух множеств обозначается так: X ∪ Y. Объединение возвращает общность двух множеств или объединённое множество. Иными словами, с помощью объединения множеств можно получить новое множество элементов, которые существуют хотя бы в одном исходном множестве. В нашем случае объединение вернёт все книги, которые человек читал, а также все книги, которые есть у него дома. Обратите внимание, если книга входит одновременно в Set X и Set Y, она не может дублироваться в новом множестве после объединения, так как в множества входят только уникальные элементы.
С помощью диаграммы Венна пересечение и объединение можно представить так:
Теперь давайте рассмотрим более сложные вещи. Объединение и пересечение — важные операции над множествами, но это только азы теории. Нам надо познакомиться с другими операциями, чтобы решать более серьёзные задачи. Важно понимать разность множеств и относительные дополнения множеств. Ниже мы разберём, почему это важные операции, но сначала нужно понять, как они работают.
Как понятно из названия, разность множеств определяет разницу между множествами. Иными словами, мы определяем, какие элементы останутся в множестве X, если удалить из него все элементы, которые содержатся в множестве Y. Это действие можно обозначить так: X — Y. В примере на иллюстрации ниже разница между множеством X и множеством Y — это элементы, которые существуют в Set X, но не существуют в Set Y. Они обозначены буквами C, Z и W.
Относительное дополнение — противоположность разности множеств. Например, относительное дополнение Y по сравнению с X возвращает все элементы множества Y, которые не входят в множество X. Относительное дополнение можно обозначить так: X \ Y. Относительное дополнение X \ Y фактически возвращает такой же набор элементов, как разность Y — X. В нашем примере множество Y меньше множества X. Единственный элемент, который входит в Set Y, но не входит в Set X — число 2.
По сути, мы просто вычитаем множество X из множества Y и отвечаем на вопрос: что существует в Y, чего нет в X?
Вы могли заметить, что в части примеров мы имеем дело со строками, в другой части в качестве элементов выступают буквы и числа. Здесь надо подчеркнуть важный момент: множество может включать любой тип элементов или объектов. Вы можете рассматривать множества как хэши: они включают любые сущности, если те встречаются во множестве только один раз.
Теперь давайте рассмотрим ещё одну операцию, она самая сложная из всех. Но не пугайтесь, с ней тоже можно разобраться.
В некоторых случаях требуется найти противоположность пересечению множеств. Иными словами, речь идёт о книгах, которые есть у человека, и книгах, которые он прочитал, но которые не входят одновременно в оба множества. Как назвать это подмножество? И как найти его?
Правильное название для этого кейса — симметрическая разность множеств. Также употребляют термины «дизъюнктивное объединение» и «несвязное объединение». Симметрическая разность возвращает все элементы, которые входят в одно из множеств, но не входят в пересечение этих множеств. Пример на иллюстрации поможет разобраться с дизъюнктивным объединением.
В примере выше симметрическая разность похожа на поиск относительного дополнения множества X и множества Y. Если подходить к этому с позиции математики, поиск симметричной разницы — то же самое, что и объединение относительных дополнений множества X и множества Y. Эту операцию можно записать так: X △ Y= (X ∖ Y) ∪ (Y ∖ X).
Но не дайте сбить себя с толку!
Всё, что нужно для поиска симметрической разности — найти элементы, которые есть в множестве X, но отсутствуют в множестве Y, и какие элементы есть в множестве Y, но отсутствуют в множестве X. Иными словами, надо найти уникальные элементы в каждом множестве.
В примере выше числа 1, 2 и 3 входят в множества X и Y одновременно. А буквы A, B, C, X, Y, Z входят только в множества X или Y. Поэтому они представляют симметрическую разность множеств X и Y.
Мы рассмотрели теоретические вопросы. Теперь можно посмотреть, как теория множеств работает на практике.
Множества вокруг нас
К этому моменту вы наверняка задумались, зачем надо изучать теорию множеств. Это хороший вопрос, и пришло время ответить на него.
Уже догадались? Множества повсюду. Это структуры данных, которые мы можем использовать при работе с разными языками программирования, например, Python, Java, Ruby, JavaScript и так далее. Если вы знакомы с этими или другими языками программирования, то уже вспомнили методы, которые позволяют работать с множествами.
Вот пример на JavaScript.
Очевидно, что имена методов могут меняться в зависимости от языка. Например, метод has из примера выше в Ruby называется include?, но эти методы работают практически одинаково. А в Python при работе с множествами можно использовать методы intersection, union и symmetric_difference.
Но в чём именно польза множеств? Понятно, что с ними можно работать в разных языках программирования, но зачем это нужно на практике?
Один из моментов — множества могут сэкономить вам много времени. Помните все эти сложные операции — intersection, union, difference? Уже догадались? Продолжительность выполнения этих операций зависит от размера множеств. Это связано с тем, что для выполнения операций нам надо обойти все элементы множества. Обычно даже гигантские множества можно обойти достаточно быстро.
Но как насчёт основных операций? Как насчёт добавления элементов в одно из множеств, удаления элементов, поиска конкретного элемента в множестве? Все эти операции выполняются за константное время или 0(1). Это очень мощный инструмент, и это значит, что множества могут быть даже более удобной структурой данных, чем словарь или хэш.
Но подождите, почему все операции с множествами выполняются так быстро? Как это возможно? Как оказалось, под капотом множества представляют собой хэши. Теперь вся информация собирается воедино. С хэш-таблицами знакомо большинство программистов, но почему с их помощью так удобно реализовывать множества?
Это возможно благодаря нескольким факторам. Первый: в хэш-таблицах каждый элемент всегда имеет уникальный индекс. Это очень хорошо с точки зрения реализации множеств, так как множества могут включать только уникальные элементы. Второй фактор: в хэш-таблицах порядок элементов не имеет значения. В множествах порядок элементов тоже не имеет значения. Наконец, хэш-таблицы обеспечивют константное время доступа 0(1). Это идеально для выполнения базовых операций с множествами.
Заключение
Теория множеств используется в разных областях computer science. Это важная для программистов концепция, понимание которой помогает разработчикам эффективно работать с данными.
Адаптированный перевод статьи Set Theory: the Method To Database Madness by Vaidehi Joshi.
Никогда не останавливайтесь: В программировании говорят, что нужно постоянно учиться даже для того, чтобы просто находиться на месте. Развивайтесь с нами — на Хекслете есть сотни курсов по разработке на разных языках и технологиях.
Множество. Число элементов множества. Подмножество
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет.
Получите невероятные возможности
Конспект урока «Множество. Число элементов множества. Подмножество»
Сегодня на уроке мы познакомимся с таким понятием, как множество и с числом элементов множества.
Ребята, на уроках информатики вы уже научились описывать состав объектов, выделять их отличительные признаки, отвечать на вопросы «Что это такое?» и «Кто это такой?». Также научились отвечать на вопрос «Как это делается?» с помощью составления алгоритма. Но существуют и другие вопросы, на которые нужно уметь отвечать. Например, как определить относится ли объект к данной группе? А чтобы узнать, как ответить на этот вопрос, давайте для начала отгадаем загадки.
Он любит мёд
Зимой он спит
Весной хороший аппетит!
Крепко сбит да невысок,
На носу – крепкий рог,
Кто его дразнить посмеет –
Того он на свой рог подденет.
Он один сидит на ветке,
Зорок глаз и когти цепки,
Всех в два счёта б поборол,
Потому что он – .
Гнездо своё он в поле вьёт,
Где тянутся растения.
Его и песни, и полет
Вошли в стихотворения!
Симпатичен, сер, усат,
Его хвостик полосат.
Пищу грязной не грызёт —
Моет всё в воде .
Днём спит, ночью летает,
Ухает, людей пугает.
В темноте горят глаза –
Всем мышам она гроза.
Он хвостатый и усатый,
И, конечно, полосатый.
̶ Рррр, ̶ рычит, ̶ мне не до игр.
Кто же это, дети? …
Эта птица всем знакома ̶
Важно ходит возле дома
Кар-Кар-Кар вдруг закричит,
И спокойно улетит.
Он других не обижает.
Ест траву, в лесу гуляет,
Но ветвистыми рогами
Может справиться с волками!
По велению волшебной палочки объекты все распределились вот так!
И получилось две группы. Как мы разделили объекты? По общему признаку. В одной группе у нас находятся животные, а в другой птицы.
А теперь посмотрите – из первых букв можно сложить слово. Какое? Слово "Множество". И это очень важное слово для нашего урока!
Под множеством понимают объединение объектов на основе каких-то общих свойств или признаков.
Чтобы узнать принадлежит объект данному множеству или нет, достаточно выделить характерный признак, по которому точно можно определить, что этот объект можно включить в данное множество. Другой же предмет, у которого этот признак отсутствует, включать в это множество нельзя.
Глядя на две наши группы, можно сказать, что у нас есть два множества: множество животных и множество птиц.
Какие объекты входят в эти множества?
В первое множество входят: медведь, енот, олень, носорог, тигр.
Во второе множество: орёл, жаворонок, сова, ворона.
Объекты, которые принадлежат множеству, называются элементами множества.
Как вы думаете, от какого слова произошло название «множество»? Много.
А сколько это много? Точно мы сказать не можем.
Во множестве может быть любое количество элементов, даже один элемент. Может быть бесконечно большое число элементов, например, множество чисел. А также может быть и такое, что во множестве не будет ни одного элемента. Такое множество называется пустым. Например, множество чисел, которые делятся на ноль. Мы знаем, что нет таких чисел, которые бы делились на ноль, ведь на ноль делить нельзя.
Множества могут быть самыми разными: детей, гуляющих в парке, множество сказок Пушкина, множество учащихся, занимающихся танцами, множество страниц в книге и т.д.
А сколько всего элементов в наших множествах? Во множестве животных пять, а во множестве птиц четыре.
А как нам отмечать объекты во множестве, не рисовать же рисунки всё время? А отмечать объекты мы будем точками.
И так в нашем множестве животных пять объектов, значит, ставим пять точек: раз, два, три, четыре, пять.
Как можно показать, что они вместе составляют одно множество? Обвести их.
Теперь тоже самое делаем для множества птиц. Ставим четыре точки и обводим их.
Итак, ребята у нас получилось множество животных, в которое входит пять элементов и множество птиц, в это множество входят четыре элемента.
А сейчас я предлагаю вам построить пирамиду множеств.
На первом этаже будут жить четыре элемента, на втором – три, на третьем – два. На четвёртом этаже будет жить один элемент, а на чердаке – никто не будет жить. Давайте посмотрим какие это множества, и разместим их по этажам, так, чтобы на каждом этаже находилось множество с соответствующим количеством элементов.
Итак! Согласные в слове «пирамида». Сколько согласных в слове «пирамида»? Четыре. Значит, это множество разместим на этаж, где будут жить четыре элемента.
Крылья у птицы. У птицы два крыла, значит, помещаем туда, где два элемента.
Ученики шестнадцатого класса. Шестнадцатого класса? Хм, это пустое множество, нет в школе 16 класса. Помещаем на чердак.
Зимние месяцы. Их три. Помещаем на второй этаж.
Гласные в слове «торт». В этом слове одна гласная – это буква о. Помещаем на четвёртый этаж.
Множества расставлены по своим местам. И пирамида готова!
Но, несмотря на то, что на чердаке находится пустое множество, там не так уж и пусто. Оказывается, там лежала записка.
А я очень любопытная и мне хочется её прочитать. Надеюсь, вы не против…
«Это письмо множества. Если вы его нашли, то обязаны выполнить одно очень важное задание. Выбрасывать это письмо или не выполнять задание нельзя. Если вы его всё-таки выбросите, то получать вам по информатике только двойки. » Я не хочу получать по информатике двойки, как и вы, надеюсь, поэтому будем выполнять.
А вот и само задание!
«Необходимо, разместить объекты во множества. Но будьте очень внимательны. Всё не так просто, как вам может показаться».
Для начала давайте прочитаем названия элементов множеств: сосна, яблоня, ель, вишня, дуб, ромашка.
А теперь прочитаем названия множеств: деревья, плодовые деревья, растения.
Какой фигурой обозначено множество плодовых деревьев? Кругом.
Какие элементы войдут в это множество? Яблоня, вишня.
Перенесём название элементов в круг.
А теперь запишем элементы множества деревьев.
Сосна, яблоня, ель, вишня, дуб. Впишем их в квадрат.
А как получилось, что яблоня и вишня входят в оба множества?
Яблоня и вишня, это – плодовые деревья. Все плодовые деревья входят и во множество деревьев.
Какое множество больше: плодовых деревьев или всех деревьев?
Множества деревьев больше, так как в него входят все плодовые деревья и остальные деревья тоже.
По велению волшебной полочки получилось следующее.
Оказывается, если ВСЕ элементы одного множества входят в другое более крупное множество, то первое является подмножеством второго. Значит, во множестве деревьев есть подмножество плодовые деревья.
Однако есть ещё одно множество – растений. Назовём его элементы. Это все элементы в списке: сосна, яблоня, ель, вишня, дуб, ромашка. Они все растения.
Ребята, получается, что это множество ещё больше: в него входят все элементы, из предыдущих множеств и ещё ромашка. Впишем эти элементы в прямоугольник.
По велению нашей волшебной палочки произошло следующее.
Рассмотрите, что получилось. Есть большое множество растений, в которое входят ромашка и подмножество Деревья. А в подмножество Деревья входит подмножество Плодовые деревья.
Ребята, сегодня вы узнали, что такое множество.
Множество – это объединение объектов на основе каких-то общих свойств или признаков.
Сколько же элементов может быть во множестве? Сколько угодно. И один, и два, и бесконечно много, и даже ни одного. Такое множество называется пустым.
А так же вы узнали, что есть множество, которое входит в другое множество и оно называется подмножеством.
Множества
Множество — это совокупность любых объектов. Множества обозначают большими буквами латинского алфавита — от A до Z.
Основные числовые множества: множество натуральных чисел и множество целых чисел, всегда обозначаются одними и теми же буквами:
N — множество натуральных чисел,
Z — множество целых чисел.
Элемент множества — это любой объект, входящий в состав множества. Принадлежность объекта к множеству обозначается с помощью знака ∈ . Запись
читается так: 5 принадлежит множеству Z или 5 – элемент множества Z .
Множества делятся на конечные и бесконечные. Конечное множество — множество, содержащее определённое (конечное) количество элементов. Бесконечное множество — множество, содержащее бесконечно много элементов. К бесконечным множествам можно отнести множества натуральных и целых чисел.
Для определения множества используются фигурные скобки, в которых через запятую перечисляются элементы. Например, запись
означает, что множество L состоит из четырёх чётных чисел.
Термин множество употребляется независимо от того, сколько элементов оно содержит. Множества не содержащие ни одного элемента называются пустыми.
Подмножество
Подмножество — это множество, все элементы которого, являются частью другого множества.
Визуально продемонстрировать отношение множества и входящего в него подмножества можно с помощью кругов Эйлера. Круги Эйлера — это геометрические схемы, помогающие визуализировать отношения различных объектов, в нашем случае, множеств.
Рассмотрим два множества:
Каждый элемент множества L принадлежит и множеству M, значит, множество L является подмножеством множества M. Такое соотношение множеств обозначают знаком ⊂ :
Запись L⊂M читается так: множество L является подмножеством множества M .
Множества, состоящие из одних и тех же элементов, независимо от их порядка, называются равными и обозначаются знаком = .
Рассмотрим два множества:
Так как оба множества состоят из одних и тех же элементов, то L = M.
Пересечение и объединение множеств
Пересечение двух множеств — это совокупность элементов, принадлежащих каждому из этих множеств, то есть их общая часть. Пересечение обозначается знаком ∩ .
Запись L∩M читается так: пересечение множеств L и M .
Из данного примера следует, что пересечением множеств называется множество, которое содержит только те элементы, которые встречаются во всех пересекающихся множествах.
Объединением двух множеств называется множество, содержащее все элементы исходных множеств в единственном экземпляре, то есть если один и тот же элемент встречается в обоих множествах, то в новое множество этот элемент будет включён только один раз. Объединение обозначается знаком ∪ .
Запись L∪M читается так: объединение множеств L и M .
При объединении равных множеств объединение будет равно любому из данных множеств:
если L = M, то L∪M = L и L∪M = M.
