Элементы разбиения. Разбиения конечного множества

Число Стирлинга второго рода S ( n , k ) определяется как число разбиений n-элементного множества на k блоков:

Очевидно, что S(n,k)=0 для k>n. Принимают также S(0,0)=1, так как пустое семейство блоков является в соответствии с определением разбиением пустого множества. С числами Стирлинга второго порядка связано много любопытных тождеств:

S(n,k)=S(n-1,k-1)+kS(n-1,k) для 0

S(n,n)=1 для n≥0, (2)

S(n,0)=0 для n>0. (3)

Формулы (2) и (3) очевидны. Для доказательства формулы (1) рассмотрим множество всех разбиений множества {1, …, n} на k блоков. Это множество распадается на два различных класса: тех разбиений, которые содержат одноэлементный блок {n}, и тех разбиений, для которых n является элементом большего (по крайней мере, двухэлементного) блока. Мощность первого класса равна S(n-1,k-1), т. е. такова, каково число разбиений множества {1, …, n-1} на (k-1) блоков. Мощность другого класса составляет kS(n-1,k), так как каждому разбиению множества {1, …, n-1} на k блоков соответствует в этом классе в точности k разбиений, образованных добавлением элемента n поочерёдно к каждому блоку.

Формулы (1)-(3) позволяют легко вычислять значения S(n,k) даже для больших значений n и k.

Вот другая рекуррентная зависимость:

Для доказательства тождества рассмотрим множество всех разбиений S(n,k) множества Х={1, …, n}. Это множество распадается на различные классы, соответствующие разным подмножествам множества Х, которые являются блоками, содержащими элемент n. Отметим, что для каждого b-элементного подмножества

Число Белла

Другими словами,

Докажем рекуррентную зависимость, связанную с числами Белла:

(принимаем

Теперь опишем алгоритм генерирования всех разбиений множества.

Отметим, что каждое разбиение p множества {1,…, n} однозначно определяет разбиение

Если нам дан список

Разбиение множества {1, …, n} мы будем представлять с помощью последовательности блоков, упорядоченной по возрастанию самого маленького элемента в блоке. Этот наименьший элемент блока мы будем называть номером блока. Отметим, что номера соседних блоков, вообще говоря, не являются соседними натуральными числами. В этом алгоритме мы будем использовать переменные pred[і], sled[і], 1≤і≤n, содержащие соответственно номер предыдущего и номер следующего блока с номером і (sled[і]=0, если блок с номером і является последним блоком разбиения). Для каждого элемента і, 1≤і≤n, номер блока, содержащего элемент і, будет храниться в переменной blok[і], направление, в котором «движется» элемент і, будет закодировано в булевской переменной wper[і] (wper[і]=true, если і движется вперёд).

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

Табл.1. Последовательность разбиений множества {1,2,3,4}

Опишем теперь алгоритм решения задачи о перечислении всех понятий.

Рекурсивный алгоритм использовать нельзя, так как все решения подзадачи меньшей размерности необходимо скомбинировать со всеми решениями подзадачи оставшейся размерности. Поэтому, будем просто перебирать все варианты.

Идея такова: сохраняем все разбиения меньшей размерности и комбинируем их так, чтобы

Понятия множества и операций над множествами позволяют уточнить наше представление о классификации - действии распределения объектов по классам.

Классификацию мы выполняем достаточно часто. Так, натуральные числа представляем как два класса - четные и нечетные. Углы на плоскости разбиваем на три класса: прямые, острые и тупые.

Любая классификация связана с разбиением некоторого множества объектов на подмножества. При этом считают, что множество X разбито на классы X 1 , Х 2 ,..., Х n ..., если:

1) подмножества Х 1 , Х 2 ,..., Х п,... попарно не пересекаются; |

2) объединение подмножеств X 1 , Х 2 , ..., Х n , ... совпадает с множеством X. |

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

Так как разбиение множества на классы связано с выделением его подмножеств, то классификацию можно выполнять при помощи свойств элементов множеств.

Рассмотрим, например, множество натуральных чисел. Его элементы обладают различными свойствами. Положим, что нас интересуют числа, обладающие свойством «быть кратным 3». Это свойство позволяет выделить из множества натуральных чисел подмножество, состоящее из чисел, кратных 3. Тогда про остальные натуральные числа можно сказать, что они не кратны 3, т.е. получаем еще одно подмножество

множества натуральных чисел (рис. 12). Так как выделенные подмножества не пересекаются, а их объединение совпадает с множеством натуральных чисел, то имеем разбиение этого множества на два класса.

Рис. 12	Рис. 13

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

Рассмотрим теперь ситуацию, когда для элементов множества заданы два свойства. Например, такие свойства натуральных чисел, как «быть кратным 3» и «быть кратным 5». При помощи этих свойств из множества N натуральных чисел можно выделить два подмножества: А - подмножество чисел, кратных 3, и В - подмножество чисел, кратных 5. Эти множества пересекаются, но ни одно из них не является подмножеством другого (рис. 13). Проанализируем получившийся рисунок. Конечно, разбиения множества натуральных чисел на подмножества А и В не произошло. Но круг, изображающий множество N, можно рассматривать как состоящий из четырех непересекающихся областей - на рисунке они пронумерованы. Каждая область изображает некоторое подмножество множества N. Подмножество I состоит из чисел, кратных 3 и 5; подмножество II - из чисел, кратных 3 и не кратных 5; подмножество III - из чисел, кратных 5 и не кратных 3; подмножество IV - из чисел, не кратных 3 и не кратных 5. Объединение этих четырех подмножеств есть множество N.

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

Упражнения

1 . Из множества X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} выделили подмножества X, Х 2 и Х 3 . В каком из следующих случаев множество Х оказалось разбитым на классы:

а) Х 1 = {1, 3, 5, 7, 11}, Х 2 = {2, 4, 6, 8, 10, 12}, Х 3 = {9};

б) Х 1 = {1,3,5,7,9,11},Х 1 = {2,4,6,8, 10,12},Х 1 = {10, 11,12};

в) Х 1 = {3,6, 9, 12}, Х 2 = {1,5,7, 11},Х 3 = {2, 10}?

2. Из множества Х= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} выделим подмножества:

а) А - четных чисел, В - нечетных чисел;

б) А - чисел, кратных 2; В - чисел, кратных 3; С- чисел, кратных 4;

в) А - нечетных однозначных чисел; В - четных двузначных чисел. В каком случае произошло разбиение множества Х на классы?

3 . Из множества треугольников выделили подмножества треугольников:

а) прямоугольные, равнобедренные, равносторонние;

б) остроугольные, тупоугольные, прямоугольные;

в) равносторонние, прямоугольные, тупоугольные.

В каком случае произошло разбиение множества треугольников на классы?

4.На какие классы разбивается множество точек плоскости при помощи:

а) окружности;

в) прямой?

5.Перечертите комбинации фигур, приведенные на рисунке 15, и на каждой из них выделите (различными видами штриховки) непересекающиеся области.

6. На множестве натуральных чисел рассматривается свойство «быть кратным 7». Сколько классов разбиения множества N оно определяет? Назовите по два элемента из каждого класса.

7. Из множества четырехугольников выделили подмножество фигур с попарно параллельными сторонами. На какие классы разбивается множество четырехугольников с помощью свойства «иметь попарно параллельные стороны»? Начертите по два четырехугольника из каждого класса.

8 . Изобразите при помощи кругов Эйлера множество N натуральных чисел и его подмножества: четных чисел и чисел, кратных 7. Можно ли утверждать, что множество N разбито:

а) на два класса: четных чисел и чисел, кратных 7;

б) на четыре класса: четных чисел, кратных 7; четных чисел, не кратных 7; нечетных чисел, кратных 7; нечетных чисел, не кратных 7?

9 . На множестве четырехугольников рассматриваются два свойства: «быть прямоугольником» и «быть квадратом». На какие классы разобьется множество четырехугольников при помощи этих свойств? Начертите по два четырехугольника из каждого класса.

10 . Изменится ли ответ в упражнении 9, если на множестве четырехугольников рассмотреть свойства:

а) «быть прямоугольником» и «быть ромбом»;

б) «быть прямоугольником» и «быть трапецией»?

11. На рисунке 16 изображены множество X- студентов группы, А - множество спортсменов этой группы, В - множество отличников этой группы.

а) Укажите классы разбиения множества X, полученные с помощью свойств «быть спортсменом» и «быть отличником», и охарактеризуйте каждый из них.

б) Сколько получилось бы классов разбиения, если бы ни один отличник группы не был спортсменом?

Выполните соответствующий рисунок и назовите классы разбиения.

12 . Покажите, что решение нижеприведенных задач связано с разбиением заданного множества на классы:

а) 18 редисок связали в пучки по 6 редисок в каждом. Сколько получилось пучков?

б) 18 карандашей раздали 6 ученикам поровну. Сколько карандашей у каждого?

13. О каких множествах и операциях над ними идет речь в задачах:

а) С одной грядки сняли 25 кочанов капусты, а с другой - 15 кочанов. Всю эту капусту разложили в корзины, по 8 кочанов в каждую. Сколько потребовалось корзин?

б) Для школьного сада привезли 24 саженца яблонь. На одном участке посадили 6 саженцев, а на другом - остальные, в 3 ряда поровну. Сколько саженцев посадили в каждом ряду?

Понятия множества и операций над множествами позволяют уточнить наше представление о классификации - действии распределения объектов по классам.

Классификацию мы выполняем достаточно часто. Так, натуральные числа представляем как два класса - четные и нечетные. Углы на плоскости разбиваем на три класса: прямые, острые и тупые.

Любая классификация связана с разбиением некоторого множества объектов на подмножества. При этом считают, что множество X разбито на классы X 1 , Х 2 ,..., Х п, если:

1) подмножества X 1 , Х 2 ,..., Х п попарно не пересекаются;

2) объединение подмножеств X 1 , Х 2 ,..., Х п совпадает с множеством X.

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

Так как разбиение множества на классы связано с выделением его подмножеств, то классификацию можно выполнять мри помощи свойств элементов множеств.

Рассмотрим, например, множество натуральных чисел. Его элементы обладают различными свойствами. Положим, что нас интересуют числа, обладающие свойством «быть кратным 3». Это свойство позволяет выделить из множества натуральных чисел подмножество, состоящее из чисел, кратных 3. Тогда

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

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

Рассмотрим теперь ситуацию, когда для элементов множества заданы два свойства. Например, какие свойства натуральных чисел, как «быть кратным 3» и «быть кратным 5». При помощи этих свойств из множества N натуральных чисел можно выделить дна подмножества: А - подмножество чисел, кратных 3, и В - подмножество чисел, кратных 5. Эти множества пересекаются, но ни одно из них не является подмножеством другого (рис. 13).

Проанализируем получившийся рисунок. Конечно, разбиения множества натуральных чисел на подмножества А и В не произошло. Но круг, изображающий множество N, можно рассматривать как состоящий из четырех непересекающихся областей - на рисунке они пронумерованы. Каждая область изображает некоторое подмножество множества N. Подмножество I состоит из чисел, кратных 3 и 5; подмножество II - из чисел, кратных 3 и не кратных 5; подмножество III -из чисел, кратных 5 и не кратных 3; подмножество IV- из чисел, не кратных 3 и не кратных 5. Объединение этих четырех подмножеств есть множество N.

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

Не следует думать, что задание двух свойств элементов множества всегда приводит к разбиению этого множества на четыре класса. Например, при помощи таких двух свойств «быть кратным 3» и «быть кратным 6» множество натуральных чисел разбивается на три класса (рис. 14):

I - класс чисел, кратных 6; II - класс чисел, кратных 3, но не кратных 6; III - класс чисел, не кратных 3.

Декартово произведение

Используя две цифры, например, 3 и 5, можно записать четыре двузначных числа: 35, 53, 33 и 55. Несмотря на то что числа 35 и 53 записаны с помощью одних и тех же цифр, эти числа различные. В том случае, когда важен порядок следования элементов, в математике говорят об упорядоченных наборах элементов. В рассмотренном примере мы имели дело с упорядоченными парами.

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

Пары (а; b) и (с; d) равны в том и только в том случае, когда a =c и b = d.

В упорядоченной паре (а; b) может быть, что а = b. Так, запись чисел 33 и 55 можно рассматривать как упорядоченные пары (3; 3) и (5; 5).

Упорядоченные пары можно образовывать как из элементов одного множества, так и двух множеств. Пусть, например, 4 = {1, 2, 3}, В = {3, 5}. Образуем упорядоченные пары так, чтобы первая компонента принадлежала множеству А, а вторая- множеству В. Если мы перечислим все такие пары, то получим множество:

{(1;3),(1;5),(2;5),(3;3),(3;5)}.

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

Определение. Декартовым произведением множеств А и В называется множество всех пар, первая компонента которых принадлежит множеству А, а вторая компонента принадлежит множеству В.

Декартово произведение множеств А и В обозначают Ах В. Используя это обозначение, определение декартова произведения можно записать так:

А х В= {(х;у) |х А и у В}.

З а д а ч а 1. Найдите декартово произведение множеств А и В, если:

a)A = {m;p},B={e,f,k};

Решение. а) Действуем согласно определению- образуем все пары, первая компонента которых выбирается из А, а вторая - из В:

А х В= {(m; е), (m; f), (m; k), (p; e), (p;f), (p; к)}.

б) Декартово произведение равных множеств находят, образуя всевозможные пары из элементов данного множества:

А х А={(3;3), (3;5), (5;3), (5;5)}

Операцию нахождения декартова произведения множеств называют декартовым умножением. Выясним, какими свойствами обладает эта операция. Так как декартовы произведения А х В и В х А состоят из различных элементов, то декартово умножение множеств А и В свойством коммутативности не обладает. Можно доказать, что для декартова умножения не выполняется и свойство ассоциативности. Но декартово произведение дистрибутивно относительно объединения и вычитания множеств, т.е. для любых множеств А, В и С выполняются равенства:

(А В) х С = (А х С) (В х С),

(А \ В) х С = (А х В) \ (В х С).

З а д а ч а 2. Проверьте справедливость свойства дистрибутивности декартова умножения относительно объединения, если:

А = {3; 4; 5}, В ={5; 7}, С ={7; 8}.

Решение. Найдем объединение множеств А и В: А В = {3,4,5,7}. Далее перечислим элементы множества (А В) х С, используя определение декартова произведения: (А В) х С = {(3; 7), (3; 8), (4; 7), (4; 8), (5; 7), (5; 8), (7; 7), (7; 8)}.

Чтобы найти элементы множества (А х С) (В х С), перечислим сначала элементы множеств А х С и В х С:

А х С = {(3; 7), (3; 8), (4; 7), (4; 8), (5; 7), (5; 8)}

В х С={(5;7),(5;8),(7;7),(7;8)}.

Найдем объединение полученных декартовых произведений: (А х С) (В х С) = {(3; 7), (3; 8), (4; 7), (4; 8), (5; 7), (5; 8), (7; 7), (7; 8)}.

Видим, что множества (А В) х С и (А х С) (В х С) состоят из одних и тех же элементов, следовательно, для данных множеств А, В и С справедливо равенство (А В) х С = = (А х С) (В х С).

Выясним теперь, как можно наглядно представлять декартово произведение множеств.

Если множества А и В конечны и содержат небольшое число элементов, то можно изобразить декартово произведение этих множеств при помощи графа или таблицы. Например, декартово произведение множеств А = {1, 2, 3} и В = {3, 5} можно представить так, как показано на рисунке 17(а, б).

Декартово произведение двух числовых множеств (конечных и бесконечных) можно изображать на координатной плоскости, так как каждая пара чисел может быть единственным образом изображена точкой на этой плоскости. Например, декартово произведение А хВ множеств А = {1, 2, 3} и В = = (3, 5} на координатной плоскости будет выглядеть так, как показано на рисунке 18.

0 1 2 3 х Рис.18

Заметим, что элементы множества А мы изобразили на оси Ох, а элементы множества В - на оси Оу.

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

Задача 3. Изобразить на координатной плоскости декартово произведение Ах В, если:

а) А = {1,2,3},В = ;

б) А = , В = ;

в) A = R , В = ;

г) А = R , В = R .

Р е ш е н и е, а) Так как множество А состоит из трех элементов, а множество В содержит все действительные числа от 3 до 5, включая и сами эти числа, то декартово произведение А х В будет состоять из бесконечного множества нар, первая компонента которых либо 1, либо 2, либо 3, а вторая-любое действительное число из промежутка . Такое множество пар действительных чисел на координатной плоскости изобразится тремя отрезками (рис. 19).

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

г) Декартово произведение R x R состоит из всевозможных действительных чисел. Точки, изображающие эти пары, сплошь заполняют координатную плоскость. Таким образом, декартово произведение R x R содержит столько же элементов, сколько точек находится на координатной плоскости.

В математике и других науках рассматривают не только упорядоченные пары, но и упорядоченные наборы из трех, четырех и т.д. элементов. Например, запись числа 367- это упорядоченный набор из трех элементов, а запись слова «математика» - это упорядоченный набор из 10 элементов.

Упорядоченные наборы часто называют кортежами и различают по длине. Длина кортежа - это число элементов, из которых он состоит. Например, (3; 6; 7) - это кортеж длины 3, (м, а, т, е, м, а, т, и, к, а) - это кортеж длины 10.

Рассматривают в математике и декартово произведение трех, четырех и вообще и множеств.

Определение. Декартовым произведением множеств A 1 , А 2 ,..., А n называется множество всех кортежей длины n, первая компонента которых принадлежит множеству A 1 , вторая - множеству А 2 ,..., n-я - множеству An.

Декартово произведение множеств A 1 , А 2 ,..., А n обозначают так: A 1 х А 2 х... х А n .

З а д а ч а 4. Даны множества: A 1 = {2, b), А 2 = {3, 4, 5}, А 3 = {6,7}. Найти A 1 х А 2 х А 3 .

Ре ш е н и е. Элементами множества A 1 х А 2 х А 3 будут кортежи длины 3 такие, что первая их компонента принадлежит множеству A1, вторая - множеству А 2 , третья - множеству А 3 .

A 1 х А 2 х А 3 = {(2, 3, 6), (2, 3, 7), (2, 4, 6), (2, 4, 7),

(2, 5, 6), (2, 5,7), (3,3,6), (3,3, 7),

(3,4, 6), (3,4,7), (3,5,6), (3,5,7)}.

Два множества, содержащих одинаковые элементы, называются пересекающимися. В этом случае говорят, что множества пересекаются.

Два множества, нс имеющих общих элементов, называются непересекающимися. В этом случае говорят, что множества не пересекаются.

Пример 6.3.1. Множества {1,2,3,4,5}, {а,б,в,г,д} нс псрссскаются.

Непересекающимися являются множество треугольников и множество параллелограммов.

Также нс псрссскаются множества решений уравнений * 3 =3* 2 и *+3=0.

Пример 6.3.2. Пусть А - множество треугольников, площадь которых равна 6, В - множество прямоугольных треугольников.

А и В - пересекающиеся множества, так как существует треугольник, являющийся одновременно элементом множеств А и В , например треугольник со сторонами 3, 4, 5. Он прямоугольный и имеет площадь.

равную 6 (проверьте эти утверждения). Этот пример нс единственен. Приведите пример еще одного такого треугольника.

Пересекаются также множества решений уравнений х 2 +х=0 и х 2 -х=0, так как оба эти множества содержат число 0.

Заметим, термины «множества пересекаются» и «множества не пересекаются» определены для двух множеств. Если множеств будет больше, то необходимы уточнения. Например, множества могут нс иметь ни одного общего элемента, но некоторые из множеств могут пересекаться.

Пример 6.3.3. Множества {1,2}, {2,3} и {1,3} не пересекаются в совокупности, то есть нет ни одного элемента, который принадлежал бы каждому из множеств. Однако любая пара этих множеств имеет общий элемент.

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

Пример 6.3.4. Множества {1,2,3}, {5,7}, {4,6,8} и {9} попарно не пересекаются.

Два множества могут находиться в следующих отношениях:

• 1) множества могут быть пересекающимися,
• 2) множества могут быть нспсрссскающимися,
• 3) множества могут быть связаны отношением включения.

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

Пример 6.3.5. Рассмотрим два предложения:

Р = «Множества А и В пересекаются»,

Q = «Множество А содержится в множестве В».

Ясно, что РФ(). Оказывается, обратное утверждение в общем случае тоже неверно, то есть ()ФР. Контрпример: Л=0, В - любое. Как известно, 0сЯ, но это непересекающиеся множества.

Если же исключить случай пустого множества, то Q => Р. Действительно, берем любой элемент а из А. Так как A то аеВ. Значит, а общий элемент множеств А и В.

Теперь введем важное понятие разбиения множества на классы.

Пусть дана система К непустых подмножеств некоторого множества S. Говорят, что множества системы К образуют разбиение множества 5, если выполняются два условия:

• 1) подмножества попарно не пересекаются;
• 2) каждый элемент множества S лежит в некотором подмножестве.

Подмножества системы К называются классами разбиения. Количество классов может быть любым, в том числе бесконечным.

Вначале ограничимся примерами разбиений на конечное число классов

^2» ч А п.

Пример 6.3.6. Множества всех четных чисел {л* х2 } = {2п neZ} и всех нечетных чисел {2л+1 | пе ZJ образуют разбиение множества Z на два класса.

Множество всех простых чисел, множество всех составных чисел и множество {1} образуют разбиение множества N на три класса.

Множество всех положительных чисел, множество всех отрицательных чисел и множество {О J разбивают множество R на три класса

Пример 6.3.7. Докажем, что множество всех треугольников можно разбить на три класса:

А - множество остроугольных треугольников (треугольник называется остроугольным, если все его углы острые);

А-у - множество прямоугольных греугольников (треугольник называется прямоугольным, если он имеет прямой угол);

А з множество тупоугольных треугольников (треугольник называется тупоугольным, если он имеет тупой угол).

Действительно, каждый треугольник относится к одному из рассмотренных видов. При этом никакие два класса нс пересекаются. А нс пересекается ни с каким классом по определению. Покажем отсутствие общих элементов у множеств Л 2 и А 3 . Предположим, что в треугольнике есть прямой угол и тупой угол. Тогда их сумма будет больше 180 фадусов, поэтому сумма всех трех углов треугольника будет больше 180 градусов. А эго противоречит теореме о сумме углов rpeyi ольника.

Пример 6.3.8. Разобьем множество всех десятичных цифр {0,1,2,3,4,5,6;7,8,9} на 4 класса. Это можно сделать разными способами.

Первое разбиение: {1,2,3}, {4,5,6}, {7,8,9}, {0}.

Другое разбиение: {0,4,8}, {1,5,9}, {2,6}, {3,7}.

Подсчет числа всех разбиений л-элементного множества на определенное число классов является непростой задачей и решается средствами комбинаторного анализа.

При построении второго разбиения в примере мы использовали следующий принцип: вначале записали все цифры, кратные 4 (это числа вида 4/г), затем все цифры, дающие при делении на 4 остаток I (числа вида 4л+1), далее те цифры, которые дают остаток 2 (числа вида 4л+2) и, наконец, цифры, дающие остаток 3 (числа вида 4л+3).

Указанный принцип позволяет разбить на 4 класса все множество целых или натуральных чисел, при этом классы будут являться бесконечными множествами.

Теперь рассмотрим пример разбиения на бесконечное множество классов.

Пример 6.3.9. Возьмем числовую прямую. Тогда целые числа разделят прямую на промежутки. Однако это еще не совсем разбиение, нужны уточнения. Если рассмотреть отрезки, то, например, и будут иметь общий элемент 3. Не включить целые числа означает разбить не все множество R. Поэтому отнесем целое число к одному из концов промежутка, например к правому. Получим семейство промежутков вида (я;л+1], п - целое число.

Итак, семейство множеств К= {(п; п+] neZ} образует разбиение множества R действительных чисел на классы.

Приведенный пример разбиения множества R на бесконечное число классов не единственен. Например, можно считать множество Z целых чисел отдельным классом, а все другие классы - это интервалы вида (л; п+ 1). Есть и другие примеры разбиений.

Заметим, что любая классификация вещей, процессов или понятий приводит к соответствующим разбиениям.