Развитие представлений о числе составляет важную часть нашей истории. Оно является одним из основных математических понятий, которое позволяет выразить результаты измерения или счета. Исходным для множества математических теорий служит понятие числа. Оно применяется также в механике, физике, химии, астрономии и множестве других наук. Кроме того, в повседневной жизни мы постоянно пользуемся числами.
Последователи учения Пифагора считали, что числа содержат в себе мистическую сущность вещей. Эти математические абстракции руководят миром, устанавливая порядок в нем. Пифагорейцы предполагали, что все существующие в мире закономерности можно выразить с помощью чисел. Именно с Пифагора теория развития чисел стала интересовать множество ученых. Символы эти считались основой материального мира, а не просто выражениями некоторого закономерного порядка.
История развития числа и счета началась с того, что был создан практический счет предметов, а также измерения объемов, поверхностей и линий.
Постепенно формировалось понятие о натуральных числах. Этот процесс осложнялся тем, что первобытный человек не умел отделять от конкретного представления абстрактное. Счет в результате этого оставался долгое время лишь вещественным. Использовались пометки, камешки, пальцы и т. п. Применяли для запоминания его результатов узелки, зарубки и пр. После изобретения письменности история развития числа была отмечена тем, что начали использовать буквы, а также особые значки, применявшиеся для сокращенного изображения на письме больших чисел. Обычно воспроизводился при таком кодировании принцип нумерации, аналогичный использовавшемуся в языке.
Позднее появилась идея считать десятками, а не только единицами. В 100 различных индоевропейских языках названия чисел от двух до десяти сходны, как и названия десятков. Следовательно, очень давно появилось понятие абстрактного числа, еще до того, как языки эти были разделены.
Знание математики Древнего Египта основано сегодня на двух папирусах, которые датируются приблизительно 1700 годом до н. э.
Письменность в Древнем Египте была основана на иероглифах. Пользовались египтяне непозиционной десятичной системой, в которой количеством вертикальных черт обозначались числа от 1 до 9. Индивидуальные символы вводились для степеней десяти. История развития числа в Древнем Египте продолжилась следующим образом. С возникновением папируса было введено иератическое письмо (то есть скоропись). Специальный символ использовался в нем для обозначения чисел от 1 до 9, а также кратных 10, 100 и т. д. Развитие рациональных чисел в то время происходило медленно. Они записывались, как сумма дробей с равным единице числителем.
На использовании различных букв алфавита была основана греческая система счисления. История натуральных чисел в этой стране отмечена тем, что употреблявшаяся с 6-3 веков до н. э. аттическая система для обозначения единицы применяла вертикальную черту, а 5, 10, 100 и т. д. писались с помощью начальных букв их названий на греческом языке. В ионической системе, более поздней, использовались для обозначения чисел 24 действующие буквы алфавита, а также 3 архаические. Как первые 9 чисел (от 1 до 9) обозначались кратные 1000 до 9000, однако перед буквой ставилась при этом вертикальная черта. "М" обозначались десятки тысяч (от греческого слова "мириои"). После нее следовало число, на которое следовало умножить 10000.
В Греции в 3 веке до н. э. возникла числовая система, в которой собственный знак алфавита соответствовал каждой цифре. Греки, начиная с 6 века, в качестве цифр стали использовать первые десять знаков своего алфавита. Именно в этой стране не только активно развивалась история натуральных чисел, но и зародилась математика в современном ее понимании. В других государствах того времени она применялась либо для обыденных нужд, либо для различных магических ритуалов, с помощью которых выясняли волю богов (нумерология, астрология и т. п.).
История счисления в Индии
Многообразны и широки достижения математики в Индии. Эта страна внесла большой вклад в развитие понятия о числе. Именно здесь была изобретена десятичная позиционная система, привычная нам. Индийцы предложили символы для записи 10 цифр, с некоторыми изменениями использующиеся в наши дни повсеместно. Именно в этой стране были заложены также основы десятичной арифметики.
Современные цифры произошли от индийских значков, начертание которых использовалось еще в 1 веке н. э. Изначально индийская нумерация была изысканной. Средства для записи чисел до десяти в пятидесятой степени применялись в санскрите. Сначала для цифр использовалась так называемая "сиро-финикийская" система, а с 6 века до н. э. - "брахми", с отдельными знаками для них. Эти значки, несколько видоизменившись, стали современными цифрами, называемыми сегодня арабскими.
Возникновение понятия натурального числа.
К построению математических моделей явлений, основанному на отвлечении от всех свойств предметов, кроме их количественных отношений, и пространственных форм, человечество прибегало с первых шагов изучения окружающего мира. Одним из первых достижений на этом пути было возникновение и формирование понятия натурального числа . Оно появилось, по-видимому, на довольно позднем этапе развития мышления, поскольку предполагает уже способность к созданию и оперированию абстрактными понятиями.
Дальнейшее развитие натурального числа произошло в начале семнадцатого века, когда индийские цифры стали известны на Руси. Вплоть до восемнадцатого века использовалась в России славянская нумерация. После этого она была заменена современной.
Виды письменной нумерации.
Счет стал развиваться быстрее с того времени, когда люди догадались обратиться к своим пальцам. Именно они стали тем простым и в то же время уникальным «аппаратом», который положил дальнейшее начало развитию нумерации письменной.
Существовал, конечно, и словесный счет, но он стал активен только после того, как развилось сельское хозяйство.
Со временем многие народы стали придумывать наименованиям различные слова, которые и закрепились за числами. Например, если необходимо было обозначить число один, то его обозначали как «нос». «рот», «голова» (тем, что имеется у человека в одном количестве). Соответственно, за числом два закрепились слова «глаза», «руки», «ноги» и т. д.
Пальцевой счет постепенно привел к тому, что счет стал упорядочиваться, а человек, соответственно словесно упрощал числа. Допустим, выражение, которое соответствовало числу 13 – «десять пальцев на обеих ногах и три пальца на одной руке» - упрощалось в «палец на руке»; для выражения числа 26 вместо слов «десять пальцев на обеих ногах, десять пальцев на обеих руках и три пальца на ноге другого человека» говорилось иначе: «три пальца другого человека».
Первым русским памятником математического содержания до настоящего времени считается рукописное сочинение новгородского монаха Кирика, написанное им в 1136 г.
К XVI в. относится изобретение замечательного счетного прибора, получившего впоследствии название «русские счеты».
Письменная система счисления претерпела множество изменений по мере развития и становления человеческого общества, при плавном переходе от древнего человека к современной личности.
Лекция №7
Разбиение конечного множества образует любое семейство непустых и непересекающихся подмножеств его элементов, обычно называемых классами, когда каждый элемент является представителем своего класса. Каждый класс однозначно определяет состав его элементов, а порядок перечисления классов разбиений и элементов классов не имеет значения. Различными считаются разбиения, которые отличаются числом классов или составом хотя бы двух классов. Например, существует всего 5 различных разбиений трехэлементного множества {X,Y,Z} на классы. Эти разбиения перечислены ниже в таком порядке, когда число их классов не убывает:
{ {X,Y,Z} }; { {X,Y}, {Z} }; { {X,Z}, {Y} }; { {X}, {Y,Z} }; { {X}, {Y},{Z} }.
Если зафиксировать количество классов, то в общем случае число разбиений множества из n элементов на m классов при любых n ≥ m ≥ 0 оказывается соответствующим по значениям для чисел Стирлинга второго рода . Формально эти числа определяют коэффициенты разложения степени n произвольной переменной Z по убывающим m -факториалам от Z при всех целых значениях m от 0 до n :
Z n = (Z) 0 + (Z) 1 + ... + (Z) m + ... + (Z) n .
В этом разложении фигурные коэффициенты обозначают числа Стирлинга второго рода, а убывающие факториалы, перед которыми они стоят, определяют следующие произведения:
(Z) m = Z(Z−1)(Z−2) … (Z−m+1).
Учитывая выражение для убывающих факториалов, указанное разложение, например при n=3 можно записать следующим образом:
Z 3 = + Z + Z(Z - 1) + Z (Z - 1)(Z - 2).
Равенство левой и правой частей этого разложения, очевидно, будет достигнуто при следующих значениях коэффициентов, заданных соответствующими числами Стирлинга второго рода:
0 ; = 1 ; = 3 ; = 1 ;
В общем случае значения чисел Стирлинга второго рода при любых целых величинах n≥m≥0 можно записать в форме бесконечной нижнетреугольной матрицы, которая называется треугольником Стирлинга второго рода . Его начальный фрагмент, например, при 0≤n,m≤8 можно представить следующей таблицей:
Таблица 1
| n | ... | |||||||||
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ... |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ... |
| 2 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | ... |
| 3 | 0 | 1 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | ... |
| 4 | 0 | 1 | 7 | 6 | 1 | 0 | 0 | 0 | 0 | ... |
| 5 | 0 | 1 | 15 | 25 | 10 | 1 | 0 | 0 | 0 | ... |
| 6 | 0 | 1 | 31 | 90 | 65 | 15 | 1 | 0 | 0 | ... |
| 7 | 0 | 1 | 63 | 301 | 350 | 140 | 21 | 1 | 0 | ... |
| 8 | 0 | 1 | 127 | 966 | 1701 | 1050 | 266 | 28 | 1 | ... |
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... |
По своей структуре эта таблица похожа на треугольник Паскаля. Ее внутренние элементы определяются по следующему мнемоническому правилу. Каждое число в любой строке n>0 и столбце m>0 равно сумме числа слева над ним и непосредственно над ним, которое умножено на m . Это правило иллюстрирует следующий пример для n=3 и m=2 :
2 = 1 + 2∙1 = 3 .
В общем случае данное правило формально отражает следующее рекуррентное соотношение, которое справедливо для любых натуральных значений n≥m>0 :
Граничные условия для этого рекуррентного соотношения определяют следующие значения чисел Стирлинга второго рода при m=0 и m=n :
0 ; = 1 ; = 1.
2 = + + 2 = 0 + 1 + 2∙1 = 3 .
N(n - 1)2 и = 2 n-1 - 1 .
Следующий пример показывает, как с их помощью найти значение числа Стирлинга второго рода при n=6 и m=4 более коротким путем, чем по базовому рекуррентному соотношению:
4 = + 3 + 4= (2 4-1 - 1) + 34(4 - 1)2 + 45(5 -1)2 = 65.
Как отмечалось выше, числа Стирлинга второго рода дают мощность множества разбиений n элементов на фиксированное число классов m≤n . Общее число всех разбиений n элементов без ограничения по числу классов определяется числом Белла , значение которого равно следующей сумме чисел Стирлинга второго рода:
B n = + ... + + ... +
Принимая величину B 0 = 1 , для вычисления значений чисел Белла можно использовать также следующую рекуррентную зависимость с биномиальными коэффициентами:
B n = B 0 + B 1 + ... + B k + ... + B n
Результаты рекуррентных вычислений чисел Белла для всех значений n от 0 до 10 приведены в следующей таблице:
Таблица 2
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| B n | 1 | 1 | 2 | 5 | 15 | 52 | 203 | 877 | 4140 | 21147 | 115975 |
Из таблицы значений чисел Белла следует, что мощность множества разбиений быстро растет с увеличением количества элементов. Поэтому для решения разнообразных практических задач необходимо иметь комбинаторные алгоритмы, которые обеспечивают систематический перебор разбиений конечных множеств элементов любой мощности. По ряду причин перебор разбиений целесообразно производить в порядке минимального изменения состава их классов, когда любые 2 последовательных разбиения отличаются расположением только одного элемента в их классах. Очевидно, такое изменение следует считать минимальным. Например, в следующей последовательности все 5 разбиений множества {X,Y,Z} перечислены в порядке минимального изменения, а элементы, которые при этом переходят в другой класс, выделены подчеркиванием:
{ {X,Y,Z } }; { {X,Y }, {Z} }; { {X}, {Y}, {Z } }; { {X} {Y,Z } }; { {X,Z} {Y} }.
Для генерации разбиений в порядке минимального изменения были разработаны рекурсивный и итерационный алгоритмы, которые напоминают аналогичные методы транспозиции смежных элементов для перестановок. Они ориентированы на обработку любого множества натуральных чисел от 1 до n и обеспечивают систематическое перечисление всех его разбиений в порядке минимального изменения. При этом классы разбиений обычно упорядочивают по возрастанию величин своих минимальных элементов. С учетом указанного порядка перечисления классов, последовательность разбиений, например, числового множества {1,2,3} , которую формируют алгоритмы минимального изменения, имеет следующий вид:
{ {1,2,3} }; { {1,2}, {3} }; { {1}, {2}, {3} }; { {1} {2,3} }; { {1,3} {2} }.
В рекурсивном алгоритме минимального изменения такая последовательность, в общем случае, строится по следующему рекуррентному правилу. Пусть уже получен список всех разбиений множества из (n−1) натуральных чисел от 1 до (n−1) , где классы упорядочены по возрастанию своих наименьших элементов, а любые последовательные разбиения минимально различны, в указанном выше смысле. Каждое разбиение этого списка дополняется одноэлементным классом {n} , а его классы дополняются элементом n . Причем указанные дополнения для нечетных по номеру разбиений производятся в порядке возрастания минимальных элементов классов и заканчиваются добавлением одноэлементного класса. Для четных по номеру разбиений такие же дополнения производятся в обратном порядке. В результате этой обработки получается уже список разбиений множества из n натуральных чисел, где все классы по-прежнему остаются упорядоченны по возрастанию своих наименьших элементов, а любые два соседних разбиения отличаются только расположением элемента n и, следовательно, минимально различны. Следующая диаграмма демонстрирует пример рассмотренного рекурсивного процесса, который начинается с одноэлементного множества {1} и завершается списком разбиений множества из трех чисел {1,2,3} . Для наглядности разбиения каждого уровня пронумерованы, а добавленные элементы выделены подчеркиванием, кроме того, стрелки указывают направление добавлений:
Для практической реализации рекурсивного алгоритма минимального изменения удобно задать каждое разбиение вектором наименьших элементов его классов. Тогда в общем случае любое разбиение множества последовательных натуральных чисел от 1 до n представляется вектором E(n) из n значений, где каждое значение E j обозначает наименьший элемент класса, которому принадлежит элемент j . Такое соответствие можно формально задать следующим образом:
E j = min i | E j = E i ; j = 1, ... n .
Для примера в следующей таблице перечислены все 5 последовательных разбиения множества {1,2,3} и соответствующие им векторы наименьших элементов их классов E(3) :
Таблица 3
| 1 | 2 | 3 | 4 | 5 |
| {1 2 3} | {1 2} {3} | {1} {2} {3} | {1} {2 3} | {1 3} {2} |
| (1 1 1 2 1 3) | (1 1 1 2 3 3) | (1 1 2 2 3 3) | (1 1 2 2 2 3) | (1 1 2 2 1 3) |
В соответствие с рекурсивным алгоритмом каждый вектор наименьших элементов E(n) классов разбиения множества из n элементов расширяет соответствующий вектор E(n−1) значением E n для добавленного элемента n . При этом нужно последовательно присвоить E n все различные значения из вектора E(n−1) , которые равны по величине своим индексам (j=E j) и n . Для нечетных по номеру векторов E(n−1) такое присваивание делается в порядке возрастания индексов, что соответствует увеличению значений наименьших элементов классов разбиения, и завершается присваиванием E n = n :
E n = E j | E j = j = 1, … n.
Например, вектор E(3) = (1,2,1) , который соответствует разбиению { {1,3}, {2} } , с нечетным порядковым номером 5 расширяется в следующие различные варианты вектора E(4) , образуя соответствующие им разбиения множества {1,2,3,4} :
E(3) = (1 ̲ 1 2 2 1 3) + (E4 = 1 1) −> (1 1 2 2 1 3 1 4) = E(4) ~ Ё;
E(3) = (1 1 2̲ 2 1 3) + (E4 = 2 2) −> (1 1 2 2 1 3 2 4) = E(4) ~ { {1 3} {2 4} };
E(3) = (1 1 2 2 1 3) + (E4 = 4) −> (1 1 2 2 1 3 4 4) = E(4) ~ { {1 3} {2} {4} }.
Для четных по номеру векторов E(n−1) дополнение производится аналогично, но в порядке уменьшения значений наименьших элементов классов, и начинается присваиванием E n = n :
E n = E j | E j = j = n, … 1.
Например, вектор E(3)=(1,2,2) , который соответствует разбиению { {1}, {2 3} } , с четным порядковым номером 4 расширяется в следующие различные варианты вектора E(4) , образуя соответствующие им разбиения множества {1,2,3,4} :
E(3) = (1 1 2 2 1 3) + (E4 = 1 1) −> (1 1 2 2 1 3 1 4) = E(4) ~ { {1} {2 3} {4} };
E(3) = (1 1 2̲ 2 1 3) + (E4 = 2 2) −> (1 1 2 2 1 3 2 4) = E(4) ~ { {1} {2 3 4} };
E(3) = (1̲ 1 2 2 1 3) + (E4 = 4) −> (1 1 2 2 1 3 4 4) = E(4) ~ { {1 4} {2 3} }.
Несмотря на простоту, рассмотренный рекурсивный алгоритм нельзя признать экономичным, так как приходится последовательно порождать разбиения всех множеств с мощностями от 1 до n , хотя требуется получить разбиение только множества из n элементов. В этом отношении более привлекательным представляется итерационный алгоритм минимального изменения разбиений, который реализует систематический переход элементов между классами. При этом на каждой итерации очередное разбиение образуется из предыдущего переходом одного элемента в соседний класс слева или справа, если считать, что классы упорядочены по возрастанию значений своих наименьших элементов. Такой переход может изменять состав классов при сохранении их числа и приводить к удалению или образованию одноэлементного класса. В любом случае разбиения двух соседних итераций отличаются расположением только одного элемента в своих классах и, следовательно, минимально различны. В частности, следующая последовательность переходов элементов обеспечивает перечисление разбиений множества {1,2,3} в порядке минимального изменения, а стрелки указывают направление перехода элементов между классами:
{ { 1 2 ->3} }; { { 1 ->2}, { 3 } }; { {1}, { ->2}, {3} }; { {1} { 2 <-3 } }; { {1 3} {2} }.
В общем случае для систематической организации итерационного процесса важно установить правила перехода. Они должны обеспечивать выбор направления, элемента и классов перехода на каждой итерации при генерации разбиений любого множества последовательных чисел от 1 до n. Для формального описания этих правил удобно, как и раньше, задавать каждое разбиение вектором (E 1 ,…E j, …,E n) наименьших элементов его классов, где:
E j = min i | E j = E i .
Для получения последующих разбиений на каждой итерации необходимо сначала выбрать для перехода наибольший по значению элемент m , который допустимо передвинуть вправо или влево в зависимости от установленного для него текущего направления перехода. Очевидно, переход влево любого элемента ограничен классом с наименьшим элементом 1 , который сам не может быть влево или вправо. Переход вправо любого элемента j>1 ограничен классом, где он сам является наименьшим элементом. Поэтому правило выбора наименьшего элемента m для перехода на каждой итерации можно формально записать следующим образом:
m = max j | (E ←j > 1 или E →j < j).
Для удобства практической реализации этого правила целесообразно ввести знаковую функцию d(j) кодирования направления перехода каждого элемента j . Она должна принимать значение +1 или −1 при переходе элемента j вправо или влево, соответственно. Тогда в правиле выбора переходного элемента m можно исключить альтернативную проверку направления перехода и записать его следующим образом:
Em должно быть выполнено следующее соотношение:
t < E m ≤ m.
Если для выбранного элемента m установлено направление перехода вправо, то возможны два случая. В одном случае элемент m переходит в соседний справа класс, где наименьший элемент меньше, чем m . В другом случае, когда наименьший элемент соседнего справа класса больше, чем m , или элемент m принадлежит крайнему правому классу разбиения, из m должен быть образован одноэлементный класс {m} .
Оба указанных случая учитывает следующее формальное правило, которое идентифицирует наименьший элемент t класса, куда попадет элемент m после перехода вправо:
t = min { m; E (j > m) | E j > E m }.
Очевидно, что при переходе элемента m вправо, между значениями t , m и E m должно быть выполнено следующее соотношение:
E m < t ≤ m.
Оба правила идентификации класса для перехода выбранного элемента m влево или вправо можно формально объединить, используя числовой код d(m) направления перехода элемента m . Такое комплексное правило автоматически учитывает направление перехода элемента m и идентифицирует наименьший элемент t класса для его перехода следующим образом:
t = min { m; E j | d(m)∙E j > d(m)∙E m }.
Независимо от способа идентификации формальный переход выбранного элемента m в класс с наименьшим элементом t обеспечивает следующее присваивание:
E m <− t .
В результате образуется очередное разбиение, которое отличается от разбиения предыдущей итерации только по составу двух классам, откуда и куда был передвинут элемент m . При этом в векторе наименьших элементов классов изменяется только значение E m . Очевидно, что такое изменение разбиения является минимальным. Аналогичные итерации нужно продолжать до получения конечного разбиения, где для перехода формально выбирается элемент m=1 , потому что все остальные элементы j>1 уже достигли своих крайних классов по установленному для них направлению перехода. Такое разбиение можно формально записать следующим образом:
d(→j)∙E j = j или d(←j)∙E j = −1 при j = 1, …, n .
Выполнение итераций рассмотренного итерационного алгоритма иллюстрируется в следующей таблице, где последовательные разбиения множества чисел {1,2,3} записаны в традиционном и векторном формате, а стрелки и знаки индексов обозначают направления перехода элементов:
Таблица 4
| { →1 →2 →3̲ } | { →1 →2̲ } { →3 } | { →1 →} { 2 } { →3̲ } | { →1 } { →2 →3̲ } | { →1 →3 } { →2 } |
| (1 1 1 2 1 3̲) | (1 1 1 2̱̲ 1 3) | (1 1 1 2 1 -3̲) | (1 1 1 2 1 -3̲) | (1 1 1 2 1 -3) |
Определение. Разбиением множества А на подмножества (классы) называется система его непустых подмножеств, обладающая следующими свойствами:
1) объединение всех подмножеств этой системы равно множеству А;
2) никакие два различные подмножества не содержат общих элементов.
Графическое изображение разбиения множества изображено на рисунке 7.
Множество А разбито на пять классов А1, А2, А3, А4, А5.
Первое условие, накладываемое на систему подмножеств, которая является разбиением множества А, означает, что каждый элемент из множества А входит в какое–нибудь подмножество системы; другое условие означает, что каждый элемент из А входит только в одно подмножество системы.
Пример 1. Будем рассматривать множество учеников школы. Школа состоит из классов: 1, 2, 3, …, 11. Совокупность классов является разбиением, так как объединение учеников всех классов дает множество учеников школы, и никакие два класса не пересекаются: один и тот же ученик не может учиться в двух разных классах.
Отметим, что не всякая система подмножеств данного множества представляет собой разбиение этого множества.
Пример 3. Рассмотрим множество параллелограммов и выделим в нём следующие подмножества: а) прямоугольников, б) ромбов, в) параллелограммов с неравными сторонками и непрямыми углами. Будет ли это разбиением? Нет, потому что квадраты попадают в множество а) и в множество б).
Таким образом, разбиение связано с выделением из множества его подмножеств. Но, чтобы выделить подмножества, достаточно указать характеристическое свойство его элементов.
При помощи одного свойства осуществляется разбиение множества, вообще, на 2 класса, при помощи двух свойств - на 4 класса, при помощи трех свойств - на 8 классов, при помощи свойств - на классов. В частных случаях может получиться меньше классов, так как некоторые из подмножеств оказываются пустыми.
Еще по теме §5. Разбиение множества на классы:
- 1. Понятие множества. Операции над множествами. Отображения. Характеристическая функция множества
- 9. Нигде не плотные множества. Понятие категории множеств метрического пространства. Теорема Бэра
- Соответствие между множеством выделенных значений и множеством акцентов
- 4.3.4 Контрастирование фрагментов и разбиение номера на сегменты
- Определение замкнутого множества. Определение компакта. Может ли множество точек на плоскости быть одновременно открытым и замкнутым?
1. Множества множеств. Мы можем рассматривать множества, состоящие из самых различных элементов. В частности, можем рассматривать множества множеств, т. е. множества, элементы которых сами суть множества. Таково, например, множество всех пар весел, имеющихся на данной лодочной станции. Множеством множеств является также множество всех спортивных команд Москвы (каждая спортивная команда есть множество составляющих ее спортсменов).
Множество всех профессиональных союзов, а также множество всех воинских частей (дивизий, полков, батальонов, рот, взводов и т. д.) данной армии являются множествами множеств. Эти примеры показывают, что множества, являющиеся элементами данного множества множеств, могут в одних случаях пересекаться, в других случаях, наоборот, не иметь общих элементов.
Так, например, множество всех профессиональных союзов СССР есть множество попарно не пересекающихся множеств, так как гражданин СССР не может быть одновременно членом двух профессиональных союзов. С другой стороны, множество всех воинских частей какой-либо армии есть пример множества множеств, некоторые элементы которого являются подмножествами других элементов: так, каждый взвод есть подмножество некоторого полка, полк есть подмножество дивизии и т. д.
Множество спортивных команд данного города состоит, вообще говоря, из пересекающихся множеств, так как одно и то же лицо может входить в несколько спортивных команд (например, в команду пловцов и в команду волейболистов или лыжников).
Замечание. Для облегчения речи иногда вместо выражения «множество множеств» употребляются как совершенно равнозначащие выражения «система множеств» или «совокупность множеств».
2. Разбиение на классы. Очень важный класс систем множеств получаем, если рассматриваем всевозможные разбиения какого-нибудь множества на попарно не пересекающиеся множества. Дано множество X, представленное в виде суммы попарно не пересекающихся подмножеств; множества, слагаемые нашей суммы, и являются элементами данного разбиения множества X.
Пример 1. М есть множество всех учащихся в средних школах Москвы. Множество М можно разбить на попарно не пересекающиеся подмножества, например, следующими двумя способами:
1) мы объединяем в одно слагаемое всех учащихся одной и той же школы (т. е. разбиваем множество всех учащихся по школам);
2) мы объединяем в одно слагаемое всех учащихся одного и того же класса (хотя бы и разных школ).
Пример 2. Пусть X есть множество всех точек плоскости; возьмем на этой плоскости какую-нибудь прямую g и разобьем всю плоскость на прямые, параллельные прямой g. Множества точек каждой такой прямой и являются теми подмножествами, на которые мы разбиваем множество X.
Если данное множество X разбито на попарно не пересекающиеся подмножества, дающие в сумме множество М, то для краткости говорят просто о разбиении множества М на классы.
Теорема 3. Пусть дано отображение f множества А на множество В. Полные прообразы всевозможных точек b множества В образуют разбиение множества А на классы. Множество этих классов находится во взаимно однозначном соответствии с множеством В.
Эта теорема, в сущности, очевидна: каждому элементу а множества А соответствует, в силу отображения, один и только один элемент множества В, так что а входит в один полный прообраз . А это и значит, что полные прообразы точек во-первых, дают в сумме все множество А, во-вторых, попарно пересекаются.
Множество классов находится во взаимно однозначном соответствии с множеством В: каждому элементу b множества В соответствует класс и каждому классу соответствует элемент b множества В.
Теорема 4. Пусть дано разбиение множества А на классы. Это разбиение порождает отображение множества А на некоторое множество В, а именно на множество В всех классов данного разбиения. Это отображение получается, если заставить соответствовать каждому элементу множества А тот класс, к которому он принадлежит.
Доказательство теоремы уже заключено в самой ее формулировке.
Пример. Тем самым, что учащиеся Москвы распределены но школам, уже установлено отображение множества А всех учащихся на множество В всех школ: каждому учащемуся соответствует та школа, в которой он учится.
При всей самоочевидности наших двух теорем факты, устанавливаемые ими, не сразу получили в математике отчетливую формулировку; получив же эту формулировку, они приобрели очень важное значение в логическом построении различных математических дисциплин и прежде всего алгебры.
3. Отношение эквивалентности. Пусть дано разбиение множества X на классы. Введем следующее определение: назовем два элемента множества X эквивалентными по отношению к данному разбиению множества X на классы, если они принадлежат к одному и тому же классу.
Таким образом, если мы разобьем учащихся Москвы по школам, то двое учащихся будут «эквивалентны», если они учатся в одной и той же школе (хотя бы и в разных классах). Если же мы разобьем учащихся по классам, то двое учащихся будут «эквивалентны», если они учатся в одном и том же классе (хотя бы и различных школ).
Отношение эквивалентности, только что определенное нами, очевидно, обладает следующими свойствами.
Свойство симметрии (или взаимности). Если а и b эквивалентны, то эквивалентны также и а.
Свойство транзитивности (или переходности). Если эквивалентны элементы а и а также b и с, то а и с эквивалентны («два элемента а и с, эквивалентные третьему эквивалентны между собою»).
Наконец, мы считаем каждый элемент эквивалентным самому себе; это свойство отношения эквивалентности называется свойством рефлексивности.
Три условия; рефлексивности, симметрии и транзитивности, которым подчинено отношение эквивалентности, называются условиями или аксиомами эквивалентности (а также аксиомами равенства).
Итак, всякое разбиение данного множества на классы определяет между элементами этого множества некоторое отношение эквивалентности, обладающее свойствами симметрии, транзитивности и рефлексивности.
Предположим теперь, что нам удалось, каким бы то ни было способом, установить некоторый признак, дающий нам возможность о некоторых парах элементов множества X говорить как о парах эквивалентных элементов. При этом мы требуем от этой эквивалентности, только чтобы она обладала свойствами симметрии, транзитивности и рефлексивности.
Докажем, что это отношение эквивалентности определяет разбиение множества X на классы.
В самом деле, обозначим классом данного элемента а множестиа X множество всех элементов, эквивалентных элементу а.
В силу того, что наше отношение эквивалентности по предположению обладает свойством рефлексивности, каждый элемент а содержится в своем классе.
Докажем: если два класса пересекаются (т. а. имеют хоть один общий элемент), то они непременно совпадают (т. е. каждый элемент одного класса является в то же время элементом другого).
В самом деле, пусть классы имеют общий элемент с. Записывая эквивалентность двух каких-нибудь элементов х и у так: имеем по определению классов:
Следовательно, в силу симметрии с силу транзитивности.
Таким образом, два класса имеющие общий элемент с, действительно совпадают между собой.
Мы доказали, что различные классы образуют систему попарно не пересекающихся подмножеств множества X. Далее, классы в сумме дают все множество X, так как каждый элемент множества X принадлежит к своему классу.
Повторим еще раз доказанные выше результаты, объединив их в следующее предложение.
Теорема 5. Каждое разбиение на классы какого-нибудь множества X определяет между элементами множества некоторое отношение эквивалентности, обладающее свойствами симметрии, транзитивности и рефлексивности. Обратно: каждое отношение эквивалентности, установленное между элементами множества X и обладающее свойствами симметрии, транзитивности и рефлексивности, определяет разбиение множества X на классы попарно эквивалентных между собой элементов.
Понятие множества и операций над множествами позволяют уточнить наше представление о классификации.
Классификация - это действие распределения объектов по классам на основании сходств объектов внутри класса и их отличия от объектов других классов.
Любая классификация связана с расчленением некоторого множества объектов на подмножества. Если при этом каждый элемент данного множества попадает в одно и только одно подмножество, а объединение всех выделенных подмножеств совпадает со всем множеством, то говорят, что данное множество разбито на непересекающиеся подмножества или классы.
Считается, что множество X разбито на классы X 1 , X 2 ,..., Х n , если:
1) подмножества X 1 , Х 2 ,..., Х n попарно не пересекаются;
2) объединение подмножеств Х 1 , Х 2 ,
..., Х n совпадает с множеством X.
Если не выполнено хотя бы одно из этих условий, классификацию считают
неправильной.
Так, множество X треугольников можно разбить на три класса: остроугольные, тупоугольные и прямоугольные. Выделенные подмножества попарно не пересекаются и их объединение совпадает с подмножеством X.
Однако не всякая система подмножеств данного множества представляет собой разбиение этого множества. Так, если из множества X треугольников выделить подмножества равнобедренных, равносторонних и разносторонних, то разбиения множества X на классы мы не получим, т.к. множества равнобедренных и равносторонних треугольников пересекаются.
Итак, классификация связана с выделением из множества его подмножеств. Но чтобы выделить подмножество, достаточно указать характеристическое свойство его элементов.
Рассмотрим множество натуральных чисел. Его элементы обладают различными свойствами. Среди натуральных чисел есть четные, нечетные, кратные трем, кратные пяти и т.д. Предположим, что нас интересуют натуральные числа, обладающие свойством делится на три. Это свойство позволяет выделить из множества натуральных чисел подмножество чисел, кратных 3. Тогда про остальные натуральные числа можно сказать, что они не кратны 3, т.е. получаем еще одно подмножество множества натуральных чисел. Данные подмножества не пересекаются, а их объединение совпадает с множеством N натуральных чисел.
Т.о., Задание одного свойства элементов множества натуральных чисел привело к разбиению этого множества на два класса: класс чисел, кратных 3, и класс чисел кратных 3.
А каким будет разбиение множества на классы, если для его элементов указать два свойства, т.е. выделить из множества два различных подмножества?
Рассмотрим два свойства натуральных чисел: «быть кратным 3» и «быть кратным 5». При помощи этих свойств из множества натуральных чисел можно выделить два подмножества: А - подмножество чисел, кратных 3, и В -подмножество чисел, кратных 5. Эти подмножества пересекаются, но ни одно из них не является подмножеством другого.
Выделение двух свойств натуральных чисел привело к изменению множества натуральных чисел на 4 класса: класс чисел, кратных 3 и 5; класс чисел, кратных 3 и не кратных 5; класс чисел, кратных 5 и не кратных 3;.класс чисел, не кратных 3 и не кратных 5.
Не следует думать, что задание двух свойств элементов множества приводит к разбиению этого множества именно на 4 класса. Так бывает не всегда. Например, при помощи двух свойств «быть прямоугольным» и «быть тупоугольным» множество треугольников разбивается на три класса: класс прямоугольных треугольников; класс тупоугольных треугольников; класс треугольников, не являющихся ни прямоугольными, ни тупоугольными треугольниками.
