Дискретная математика : основные теоретико-множественные конструкции. Ч. IV

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ 

№ 494 
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ 

ИНСТИТУТ СТАЛИ и СПЛАВОВ 

Технологический университет 

МИСиС 

Кафедра автоматизированных систем управления 

В.А. Грузман 
Ю.Ю. Прокопчук 
А.И. Широков 

Дискретная математика 

Основные теоретико-множественные 
конструкции 

Часть IV 

Учебное пособие 

Под редакцией профессора А.Г. Дьячко 

Рекомендовано редакционно-издательским 
советом института 

Москва 
Издательство «УЧЕБА» 2 0 0 6 

УДК 591.45 
Г90 

Рецензент 
д-р техн. наук, проф. МГГА Л.П. Рябов 

Грузман В.А., Прокопчук Ю.Ю., Широков А.И. 
Г90 
Дискретная 
математика: 
Основные 
теоретикомножественные конструкции. Ч. IV: Учеб. пособие/ Под ред. 
проф. А.Г. Дьячко. – М.: МИСиС, 2006. – 128 с. 

Пособие представляет собой четвертую часть раздела «Основные теоретико-множественные конструкции» учебного курса «Дискретная математика». На основе свойств соответствий в рассмотрение вводится количественная характеристика множества – его мощность и изучаются ее свойства и 
связи с другими математическими объектами. В заключение приводятся элементарные сведения из комбинаторики. 

Содержание пособия соответствует программе курса «Дискретная математика». 

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

© Московский государственный институт 
стали и сплавов (технологический 
университет) (МИСиС), 2006 

ОГЛАВЛЕНИЕ 

От авторов 
5 

Введение 
6 

Глава VII. Количественные характеристики множеств 
7 

§1. Отношение равномощности на совокупности множеств и 
порожденные им связи 
7 

1. Отношение равномощности на семействе множеств 
7 

2. Отношение неравномощности на семействе множеств 
13 

3. О понятии «мощность множества» 
16 

Упражнения 
19 

Примечания 
27 

*§2. Отношения порядка на семействах множеств и 
мощностей множеств 
30 

1. Отношения порядка на семействе множеств 
30 

2. Отношения порядка на семействе мощностей множеств 
33 

Упражнения 
36 

Примечания 
44 

§3. Конечные и бесконечные множества 
45 

1. Определение конечных и бесконечных множеств 
45 

2. Конечные множества 
46 

3. Бесконечные множества 
52 

Упражнения 
54 

Примечания 
61 

§4. Классы бесконечных множеств 
63 

1. Счетные множества 
63 

2. Несчетные множества 
67 

3. Континуальные множества 
68 

Упражнения 
72 

Примечания 
74 

Приложение 1. Элементы теории действительных чисел 
79 

П1.1. Определение действительного числа. Терминология. .79 
П1.2. Действительные периодические числа 
80 

П1.3. Отношение между множествами действительных 
периодических и рациональных чисел 
82 

П1.4. Иррациональные числа 
83 

П1.5. Систематические дроби 
84 

Упражнения 
86 

Примечания 
88 

3 

Глава VIII. Элементы комбинаторики 
89 

§1. О комбинаторике 
89 

1. Об одном подходе к определению конечных и 
бесконечных множеств 
89 

2. О комбинаторике 
91 

3. О задачах пересчета 
91 

Упражнения 
93 

Примечания 
93 

§2. Комбинаторные правила 
94 

1. Правило произведения 
94 

2. Правило суммы и обобщенное правило суммы 
97 

3. Правило «включения-исключения» 
100 

Упражнения 
103 

Примечания 
112 

Приложение 2. Логическая форма правила 
«включения-исключения» 
113 

П2.1. Исходные понятия 
113 

П2.2. Логическая форма правила 
«включения-исключения» 
114 

Упражнения 
119 

Примечания 
120 

Указатель знаков и обозначений 
122 

Указатель терминов 
123 

Библиографический список 
126 

4 

Памяти 

Александра Алексеевича 

Мельникова 

От авторов 

Данное пособие авторы посвящают светлой памяти своего коллеги Александра Алексеевича Мельникова, доцента Московского государственного института стали и сплавов (МИСиС), скоропостижно 
скончавшегося 1 февраля 2002 г. 

А.А. Мельников был студентом (1971 – 1977 г.) и аспирантом 
(1977 – 1980 гг.) кафедры инженерной кибернетики (КИК) МИСиС, 
возглавляемой академиком РАН С.В. Емельяновым. После окончания аспирантуры А.А. Мельников работал инженером, а затем преподавателем (ассистентом и старшим преподавателем) в период с 
мая 1980 по сентябрь 1987 г. При организации в МИСиС кафедры 
автоматизированных систем управления (АСУ), руководимой доктором технических наук, профессором А.Г. Дьячко, выделением ее из 
состава КИК в сентябре 1987 г., А.А. Мельников стал ученым секретарем новой кафедры, а с 1992 г. – доцентом кафедры АСУ. Все студенты, обучавшиеся на кафедре АСУ, овладевали основами программирования и других базисных дисциплин именно у Александра 
Алексеевича. Им написан целый ряд учебных и методических пособий, изданных большим тиражом. Под его научным руководством 
защитили дипломные работы десятки выпускников кафедр ИК и 
АСУ. Одна из заслуг А.А. Мельникова состояла в том, что он начиная с 1986 г. играл ведущую роль в организации московских олимпиад по программированию среди технических вузов, а также неоднократно был членом жюри всесоюзных и всероссийских олимпиад. 
Александр Алексеевич был редактором-составителем многих сборников научных и методических трудов, отдавая этому много сил и 
времени. 

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

5 

ВВЕДЕНИЕ 

В пособии [22, гл. I, §1, п.3, с. 9–10] были рассмотрены два направления эволюции математических знаний. Развитие первого из 
них, философско-логического, или качественного, привело к выявлению и уточнению таких двусторонних связей между м а т е м а т и ч е с к и м и о б ъ е к т а м и [19, с. 10–11], как п р и н а д л е ж н о с т ь 
э л е м е н т а м н о ж е с т в у [22, гл. I, §2, п.1, с. 19], р а в е н с т в о и 
в к л ю ч е н и е м н о ж е с т в [22, гл. I, §2, пп. 2 и 3, с. 21 и 25 соответственно] и др. Некоторые аспекты указанного направления изложены в пособиях [22 – 24]. 

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

В гл. VII читатель получает представление о количественных характеристиках множеств, в частности семейств множеств (СМ). А 
именно, в §1 на основе бинарного отношения равномощности на СМ 
и результатов, полученных главным образом в пособии [24], формально определяется и анализируется понятие мощность множества, а также приводятся утверждения, разносторонне раскрывающие 
его содержание. В §2 читатель кратко знакомится с о т н о ш е н и я м и п о р я д к а [7, с. 52–53] на семействах множеств и мощностей 
множеств. Определенные здесь объекты позволяют ввести в §3 известную иерархию в классе мощностей, в частности, дать логически 
строгие определения таким фундаментальным математическим понятиям, как конечное и бесконечное множества и их виды. В §4 осуществляется классификация мощностей бесконечных множеств и 
доказываются относящиеся к ним основные утверждения. 

В гл. VIII представлены некоторые фрагменты комбинаторики – 
раздела теории множеств [22, гл. I, §1, п.3, с. 12], в котором исследуются о п е р а ц и и н а д к о н е ч н ы м и м н о ж е с т в а м и и к о л и ч е с т в е н н ы е о т н о ш е н и я м е ж д у н и м и . В §1 гл. VIII 
даны предварительные понятия о комбинаторике, а во втором – 
сформулированы ее основные правила. Их применение иллюстрируется примерами. 

Авторы благодарят Т.В. Дубравину и М.С. Кузьмина за помощь в 
работе. 

6 

ГЛАВА VII. КОЛИЧЕСТВЕННЫЕ 
ХАРАКТЕРИСТИКИ МНОЖЕСТВ 

§1. Отношение равномощности на совокупности 
множеств и порожденные им связи 

1. Отношение равномощности 
на семействе 
множеств 

Бинарное отношение равномощности 
на семействе м н о ж е с т в 
(СМ), то есть семействе, состоящем исключительно из множеств [23, 
гл. IV, §2, п. 2, с. 130], вводится на основе понятия б и е к ц и я , или 
в з а и м н о 
о д н о з н а ч н о е 
с о о т в е т с т в и е 
м е ж д у 
м н о ж е с т в а м и 
[24, гл. V I , §1, п. 2, с. 34], следующим образом. 

Определение 1. Пусть 

Y=(X;);eL 
(1) 

- СМ, i,j,keL, а Xi,Xj,XkeY. Множество X i называют 
равномощным 
множеству Xj, и этот факт обозначают так: 

Xi^Xj, 
(2) 

если с у щ е с т в у е т б и е к ц и я т и п а X ^ X j [24, гл. V, §2, п.1; с. 13]. 
Несложно убедиться, что бинарное отношение = (на С М (1)) обладает следующими свойствами: 

X i ^ X i (рефлексивность); 
(3) 

(Xi^Xj)^(Xj=Xi) (симметричность); 
(4) 

(Xi^Xj)A(Xj=Xk)^(Xi^Xk) (транзитивность). 
(5) 

Свойство (4) позволяет использовать в речи вместо утверждения 
«множество X i равномощно множеству Xj» равносильное ему, но более лаконичное предложение «множества X i и Xj равномощны». 

*Из соотношений (3) - (5) следует, что отношение = на С М (1) является отношением э к в и в а л е н т н о с т и . Порожденное им разбиение этого С М состоит из блоков, к каждому из которых принадлежат только равномощные множества [7, с. 50-52].* 

7 

Пример 1. 1) Пусть a, b, c, d, e и f - попарно различные объекты. 
В следующих парах множеств их первые компоненты находятся в 
отношении = со вторыми: <{a}, 
{a}>; 
<{a}, 
{b}>; 
<{a, b } , {a, 
b}>; 
<{a, b, c}, {d, e, f}>; 
<[0; n], [2n; 3n]>, где neN;*<Nч, N>; <N, Z > ; 
<N, Q>;. <(–n/2, n/2), R > (см. пп. 1)-3) и 6) из примера 2)*. 

2) Множества N 
и N^ равномощны, поскольку 
соответствие 
Г=df<G,N,N > с графиком G, состоящим исключительно из пар вида 
<n,n+1>, где nе N, - биекция. Таким образом, N=N . 

Пример 2. 1) Множество N всех натуральных чисел и его с о б с т в е н н а я ч а с т ь Nч, содержащая только все четные натуральные 
числа, 
равномощны. 
Об 
этом 
свидетельствует 
соответствие 
Г=df< G,N,Nч >, где G - график, составленный только из всех пар 
вида < n,2n >, nе N ' . 

2) Покажем, что множество N равномощно множеству Z всех целых чисел. Предположим, что график G состоит лишь из пары (0,0) и 
всех пар вида (2n–1, n) и (2n, –n), где nе N . Очевидно, что G - функциональный и инъективный график, а соответствие r=df(G,N,Z) 
всюду определенное и сюръективное, то есть является биекцией между множествами N и Z. Таким образом, N=Z. 

*3) Установим, что множество N равномощно множеству Q, состоящему только из всех р а ц и о н а л ь н ы х 
ч и с е л 
(РЧ)^. Обозначим через Q " множество, состоящее только из всех 
р а ц и о н а л ь н ы х 
д р о б е й 
(РД)^^. Оно может быть задано при помощи 
«бесконечной таблицы с двумя входами» (см. табл. VII.1). Опишем 
ее. В 1-й строке этой таблицы расположены в порядке возрастания 
модулей их числителей все РД со знаменателем 1, во 2-й - все РД со 
знаменателем 2 и т.д. Очевидно, что в этой таблице находятся в с е 
РД. Так, РД p/q, где pе Z, а qe N , находится в q-й строке и 1-м столбце, если р=0; 2p-м столбце, если p>0, и в (2p+1)-м столбце, если p < 0. 
С и н о н и м ы ^ ^ РД 0/q расположены в 1-м столбце, РД 1/1 - в «клетках» табл. VII.1 с «координатами» (2,4), (3,6) и т.д. 

Таблица VII.1 

1 
2 
3 
4 
5 
M 

1 
0/1 
0/2 
0/3 
0/4 
0/5 
M 

2 
1/1 
1/2 
1/3 
1/4 
1/5 
M 

3 

–1/1 
–1/2 
–1/3 
–1/4 
–1/5 

M 

4 
2/1 
2/2 
2/3 
2/4 
2/5 
M 

5 

–2/1 
–2/2 
–2/3 
–2/4 
–2/5 

M 

… 
… 
… 
… 
… 
… 
MMM 

8 

Существуют различные методы н у м е р а ц и и 
[23, гл. IV, §2, 

п.1, с. 130] РЧ. Часть этих методов основана на различных способах 
р а з б и е н и я 
[23, гл. IV, §2, п.3, с. 135] множества Q0 на к о н е ч н ы е блоки (*которых необходимо б е с к о н е ч н о е 
множество*) и 
нахождении в каждом из них м и н и м а л ь н о г о 
э л е м е н т а 2 ) . В 
упр.14 и 15 мы рассмотрим методы классификации элементов Q0 по 
способу «обхода» табл. VII.1 посредством различных ломаных, а 
здесь - классификацию элементов Q0 по их высоте. 

Обозначим через Qp/q часть множества Q0, состоящую только из 
всех РД, 
с и н о н и м и ч н ы х 
РД p/q. Например, Q0/1=Q0/n={0/1, 
0/2,…, 0/n,…}, где nе N+. Легко видеть, что 

((p/q)~(s/t))<^(Qp/q=Qs/t). 

Назовем высотой РД p/q и обозначим через h(p/q) натуральное число 
|p|+q. Таким образом, 

h(p/q)=df(|p|+q). 

*Очевидно, что бинарное отношение ~ на множестве Q0, определяемое так: 

(Qp/q~Qs/t) =df (h(p/q)=h(s/t)), 

является э к в и в а л е н т н о с т ь ю . Два класса синонимов РД являются блоками класса Qn высоты neN+, если высóты этих классов 
равны n. Например, Q1={0/1}, Q2={0/2, 1/1, -1/1}, Q3={0/3, 1/2, -1/2, 

2/1, -2/1} и т.д. Легко понять, что Q1=Q0/1, Q2=Q0/2uQ1/1uQ-1/1 и т.п. В 
общем случае получаем 

Q n = U(p/q6Qº)A(h(p/q)=n)Qp/q . 

Несложно доказать, что 

|Qn|=1+2(n-1). 
(I) 

Отсюда вытекает: 

(Vne N+)(Qn - непустое конечное 
множество)*. 

Обозначив через r(p/q) РЧ, соответствующее РД p/q, получаем 
следующее соотношение: 

(Vp/q, s/te Q0)((p/q~s/t) <^ (r(p/q)=r(s/t))). 

9 

Например, r(0/1)=r(0/2)=…=0, r(1/1)=r(2/2)=…=1, r(-1/1)=r(-2/2)= 
= … = - 1 и т.д. 

Переходим к описанию процедуры построения соответствия g типа N 
Q. Ее последовательно получаемые результаты будем помещать в «бесконечную с одним входом» табл. VII.2, которая «устроена» следующим образом. 

Таблица VII.2 

h 

N 
Q 

1 

0 
0 

2 

1 
1 

2 
- 1 

3 

3 
1/2 

4 
-1/2 

5 
2 

6 
- 2 

4 

7 
1/3 

8 
-1/3 

9 
3 

… 
… 

Она имеет три строки и |N| столбцов (условно). В ее 1-й строке 
расположены высóты классов Q,, где j ∈N ; во 2-й - элементы из N в 
возрастающем порядке, а в 3-й - образы g(n) элементов из 2-й строки 
(где n ∈ N), то есть элементы Q. 

На j - м шаге, где j ∈N , указанной процедуры анализируются элементы множества Q,. Те их них, которые не встречались на предыдущих шагах, нумеруются последовательными натуральными числами, а уже пронумерованные (то есть представляющие собой синонимы рассмотренных выше м и н и м а л ь н ы х 
РД2^) удаляются из рассмотрения. *Поскольку любая минимальная РД, например p/q, имеет 
к о н е ч н у ю 
высоту (а именно |p|+q), то она будет пронумерована 
на h(|p|+q)-м шаге, а все РД, не являющиеся минимальными, нумероваться не будут.* 

Опишем несколько шагов предложенного алгоритма. 
1-й шаг. На нем анализируются все РД высоты 1. Поскольку 
Qi={0/1}, то r(0/1) = 0. Полагая g(0) = 0, заносим эти результаты в 
соответствующие клетки табл. VII.2 и переходим к следующему шагу. 

2-й шаг. Здесь исследуются все РД высоты 2. Так как Q2={0/2, 1/1, 
-1/1}, а r(0/2) = 0, r(1/1) = 1 и r(-1/1) = - 1 , то РЧ 0 удаляется из рассмотрения, поскольку оно уже пронумеровано выше (а именно на 1-м 
шаге). Полагая g(1) = 1 и g(2) = - 1 , заполняем соответствующие клетки табл. VII.2 и переходим к следующему шагу. 

3-й шаг. Ясно что, Q3={0/3, 1/2, -1/2, 2/1, -2/1}. Отсюда получаем: 
r(0/3) = 0, r(1/2) = 1/2, r(-1/2) = -1/2, r(2/1) = 2 и, наконец, r(-2/1) = - 2 . 
Легко понять, что в соответствующие клетки табл. VII.2 заносятся 
последние 4 из полученных здесь 5 результатов. Далее осуществляется переход к следующему шагу. 

10 

… … … … … … … … … … … … … … … … … … … … … … … … … … … … … . . 

i-й шаг. На этом шаге анализируются все РД высоты i, где ie N . В 
силу формулы (I) имеем: |Qi|=1+2(i–1), *то есть Qi - 
н е п у с т о е 
к о н е ч н о е множество*. Оно имеет вид: 

Qi={0/i, 1/(i-1), -1/(i-1), 2/(i-2), -2/(i-2), …,(i-1)/1, -(i-1)/1}. 

Поэтому нам необходимо проанализировать на i-м шаге лишь к о н е ч н о е 
число РД и сравнить полученные результаты с результатами предыдущих шагов, которых также к о н е ч н о е 
число. Выполнив к о н е ч н о е 
ч и с л о 
указанных действий и заполнив соответствующие клетки табл. VII.2, переходим к следующему шагу. 

… … … … … … … … … … … … … … … … … … … … … … … … … … … … … . . 

Легко понять, что л ю б о е 
nе N служит номером некоторого РЧ, 
а к а ж д о е 
РЧ будет занумеровано на некотором шаге алгоритма, 
имеющем натуральный номер. Так, если минимальная РД для РЧ r 
есть p/q, где p e Z , а q e N , то r будет занумеровано на (|p|+q)-м шаге 
алгоритма, то есть соответствие g является всюду определенным и 
сюръективным. Очевидно, что при действии по указанному алгоритму всякое натуральное число нумерует е д и н с т в е н н о е 
РЧ, и 
р а з н ы е 
элементы из N нумеруют р а з л и ч н ы е 
РЧ, то есть g функциональное и инъективное, а потому и биективное соответствие 
типа N ^ Q , то есть N=Q. 

4) Пусть a1,a2,b1,b2^R, a1<a2 и b1<b2, то есть (a 1; a2) и (b 1; b 2) - 
о т к р ы т ы е 
и н т е р в а л ы 
множества R (см. упр.3 к §2 из гл.IV пособия [23, с. 136]). При помощи корреспонденции 

Г=df<F, (a 1; a 2 ), (b 1; b2) 

с графиком F, состоящим только из всех пар (x,y), где xе ( a 1; a 2), а 

y=df((b2– b 1)/(a2– a 1))-(x-a1)+b 1, 
(II) 

устанавливается равномощность множеств (a 1; a 2) и ( b 1; b 2). 

5) В условиях пп. 4) соответствие 

S=df(H, [ a 1; a 2 ] , [ b 1; b 2]) 

c графиком H, состоящим только из всех пар (x,y), где xе [ a 1; a 2 ] , а y 
определяется по формуле (II) из пп. 4), «указывает» на равномощность множеств [a1; a] и [b 1; b 2]. 

11 

6) Соответствие типа (–n/2, 7t/2)^R, осуществляемое при помощи 
вещественного терма tg x, является биекцией. 

При решении задач по установлению равномощности множеств, 
например множеств X и Y, каждый раз приходится прикладывать 
определенные усилия, иногда довольно большие, для построении 
биекции типа X ^ Y (см., в частности, пп. 3 из примера 2), а также 
решение задачи по установлению равномощности интервала (a,b)ciR 
отрезку [a,b]сR-см. [29, с. 195]. Теорема Кантора3) - Шредера Бернштейна, о которой мы будем говорить сейчас, носит не только 
принципиальный характер, но и служит существенным подспорьем в 
работе над указанными задачами. 

Теорема Кантора - Шредера - Бернштейна (теорема К Ш Б ) [2, 
с. 37, теорема 13; 13, с. 196]. 

Пусть X и Y - множества, а X'сX и Y'cY. Тогда 

( X = Y ' л Y=X') ^ (X=Y). 
(1) 

Данная теорема дает возможность при решении задачи установления равномощности двух множеств X и Y заменить выявление и 
построение 
б и е к ц и и 
типа X ^ Y 
выявлением и 
построением 
д в у х 
и н ъ е к т и в н ы х 
о т о б р а ж е н и й 
типов X ^ Y 
и 
Y ^ X 

4) 

(см. [24, гл.V, §3, п.1, с. 22-23] . Если такие отображения найдены, 
то в силу этой теоремы множества X и Y равномощны. 

Пример 3. Чтобы построить биекцию типа X ^ Y , где X=df(a1; a 2), 
Y=df[a1; a 2], a1,a2eR и a1<a2, требуется известное старание (см., например, [29, с. 195]). Доказать же равномощность этих множеств на 
основании теоремы К Ш Б не составляет труда. Убедимся в этом. 

Пусть b1,b2^ R и b 1< b 2. Установим здесь следующее соотношение: 

( a 1; a2)=[b 1; b 2], 
(I) 

тривиальным следствием которого является факт существования указанной биекции (см. упр.20). 
Доказательство. 

Для того чтобы обосновать справедливость соотношения равномощности (I) при помощи теоремы К Ш Б , достаточно доказать, что 
для некоторых множеств 

X 1c(a1; a 2) 
(II) 

и 

12