Леонгарда Эйлера (1707 – 1783), так как он использовал их при решении некоторых задач. Однако такой способ наглядного представления множеств использовался и до него, например, Готфридом Вильгельмом Лейбницем (1646 – 1716).

Мультимножества

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

Говорят, что мультимножество X является подмножеством мультимножества Y, если кратность каждого элемента X не больше кратности соответствующего элемента в Y.

Пусть X ={x1 k1 , x2 k 2 ,…, xn k n} , тогда X =k1+ k 2+ …+ k n .

Бинарные отношения

Бинарным отношением R между множествами X и Y называется подмножество произведения X ×Y и обозначается X RY . Если X =Y , то бинарное отношение называется отношением на множестве X.

Бинарное отношение может быть задано с помощью матрицы бинарного отношения, в которой 1 обозначает наличие пары (x , y) в бинарном отношении, и 0 – её отсутствие.

Бинарное отношение R называется:

рефлексивным, если x X :(x , x) R ; антирефлексивным, если x X :(x , x) R ;

симметричным, если x , y X , x≠ y :(x , y) R (y , x) R ;

антисимметричным, если x , y X :((x , y) R ,( y , x) R) x= y ;

транзитивным, если x , y , z X :((x , y) R ,( y , z) R) (x , z) R ;

полным (или универсальным), если x , y X , x≠y :(x , y) Rили ( y , x) R ;

нулевым, если x , y X :(x , y) R .

Если множество X конечно, то матрицы вышеперечисленных отношений R на множестве X обладают определёнными свойствами, но мы их здесь рассматривать не будем.

Упорядоченные множества

Говорят, что множество X упорядочено, если для любой пары его элементов x и y определено понятие неравенства x< y , обладающее следующими свойствами:

1)если x< y , то x≠ y ;

2)если x< y и y< z , то x <z .

Легко упорядочить известные числовые множества , , , и даже . Во множествах слов (словарях) также вводится порядок, обычно лексикографический.

Говорят, что два упорядоченных множества X и Y имеют один и тот же порядковый тип, если между ними можно установить взаимно-однозначное соответствие, сохраняющее порядок элементов этих множеств.

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

Множества в информатике и программировании

Множества в информатике и программировании применяются в тех задачах, где не важно количество каких-то объектов, а только сам факт их наличия или отсутствия. Традиционно рассмотрение множеств как структуры данных происходит в дисциплинах «Программирование» или «Алгоритмы и структуры данных». Существует несколько способов эффективного построения множеств и реализации операций над ними. Подробности в соответствующей литературе.

Библиография

Об элементах теории множеств можно прочитать в [Хаггарти]. Элементарное изложение теории множеств, плавно перетекающее в комбинаторику, в учебниках [Кузьмин: комбинаторика] и [Кузьмин: комбинаторные методы]. Увлекательное популярное введение в

теорию множеств в [Виленкин: множества]. Более подробное изложение теории множеств с акцентом на программирование в [Новиков]. Основательное изложение теории множеств в [Хаусдорф] и [Френкель, Бар-Хиллел]. Труды Кантора по теории множеств в [Кантор]. Вопросам реализации множеств как структуры данных посвящены главы в [Скиена] и [Кормен, Лейзерсон и др.].

1.[Виленкин: множества] Виленкин Н.Я. Рассказы о множествах. – М.: Наука, 1965. – 128 с.

2.[Кантор] Кантор Г. Труды по теории множеств. – М.: Наука, 1985. – 431 с.

3.[Кормен, Лейзерсон и др.] Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е изд. – М.: Вильямс, 2005. – 1296 с.

4.[Кузьмин: комбинаторные методы] Кузьмин О.В. Комбинаторные методы решения логических задач: учеб. пособ. – М.: Дрофа, 2006. – 187 с.

5.[Кузьмин: комбинаторика] Кузьмин О.В. Перечислительная комбинаторика: учеб. пособ. – М.: Дрофа, 2005. – 110 с.

6.[Новиков] Новиков Ф.А. Дискретная математика для программистов. – 2-е изд. – СПб.: Питер, 2004. – 364 с.

7.[Скиена] Скиена С. Алгоритмы. Руководство по разработке. – 2-е изд.: пер. с англ. – СПб.: БХВ-Петербург, 2011. – 720 с.

8.[Френкель, Бар-Хиллел] Френкель А.А., Бар-Хиллел И. Основания теории множеств.

– Пер. с англ. – М.: Мир, 1966. – 556 с.

9.[Хаусдорф] Хаусдорф Ф. Теория множеств. – Пер. с нем. – М., Л.: ОНТИ, 1937. – 304 с.