ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 16.12.2020
Просмотров: 2156
Скачиваний: 53
20
Глава I. Множества и действия над ними
Подмножества
Введение понятия множества в математику оказалось очень по-
лезным. Из-за того, что элементами множеств могут быть вещи са-
мой различной природы, одни и те же утверждения, касающиеся
множеств, можно истолковать и как утверждения о точках геомет-
рических фигур, и как утверждения о натуральных числах, и как
утверждения о животных или растениях, и как утверждения об ато-
мах или молекулах. Понятия и теоремы теории множеств облада-
ют очень большой общностью. Мы расскажем сейчас о некоторых
из них.
В первую очередь познакомимся с понятием
подмножества
. Оно
возникает каждый раз, когда приходится рассматривать некоторое
множество не самостоятельно, а как часть другого, более широкого
множества. Именно, говорят, что множество
B
является подмноже-
ством другого множества
A
, если каждый элемент
x
из
B
является
вместе с тем и элементом множества
A
. В этом случае пишут
B
⊂
A
.
Например, если взять какую-нибудь среднюю школу, то множе-
ство учеников десятых классов этой школы является подмножеством
Рис. 7
в множестве всех учеников данной школы.
В свою очередь множество учеников этой шко-
лы является подмножеством в множестве всех
школьников.
Множество всех лис является подмноже-
ством в множестве всех хищных зверей, множе-
ство хищных зверей — подмножеством в мно-
жестве млекопитающих, а множество млекопи-
тающих — подмножеством в множестве позвоночных. Если геомет-
рическая фигура
X
является частью геометрической фигуры
Y
,
то множество точек фигуры
X
есть подмножество множества точек
фигуры
Y
(рис. 7).
В геометрии также часто приходится иметь дело с подмножества-
ми некоторых множеств геометрических фигур. Возьмем, например,
следующие множества: множество
A
состоит из всех четырехуголь-
ников; множество
B
состоит из всех трапеций; множество
C
состоит
из всех параллелограммов; множество
D
состоит из всех прямоуголь-
ников; множество
E
состоит из всех квадратов. В этом списке фи-
гура каждого следующего типа является частным случаем фигуры
предыдущего типа (трапеция — частный случай четырехугольника,
Подмножества
21
параллелограмм — частный случай трапеции
1
и т. д.). Но это и озна-
чает, что каждое следующее множество является подмножеством
предыдущего:
A
⊃
B
⊃
C
⊃
D
⊃
E.
Точно так же в следующем списке каждое следующее множество
является подмножеством предыдущего: множество всех комплекс-
ных чисел; множество всех действительных чисел; множество всех
рациональных чисел; множество всех целых чисел; множество всех
натуральных чисел. Во многих случаях, чтобы выделить в данном
множестве некоторое подмножество, добавляют к характеристиче-
скому признаку множества то или иное дополнительное условие. На-
пример, подмножество натуральных чисел выделяется в множестве
целых чисел добавлением условия
n >
0
, а подмножество равносто-
ронних треугольников в множестве всех треугольников — добавле-
нием условия
a
=
b
=
c
.
F
Мы уже говорили, что многие теоремы формулируются как
теоремы о совпадении двух множеств. Наряду с ними встречают-
ся и теоремы, в которых речь идет лишь о том, что одно множество
является частью другого. Например, в теореме «Диагонали четырех-
угольника с равными сторонами (ромба) взаимно перпендикулярны»
речь идет о двух множествах:
A
— множество всех ромбов,
B
—
множество всех четырехугольников с взаимно перпендикулярными
диагоналями. И теорема состоит в том, что
A
⊂
B
.
Если множество
A
является подмножеством множества
B
,
A
⊂
B
,
то принадлежность множеству
A
является достаточным условием
принадлежности к множеству
B
, а принадлежность к множе-
ству
B
— необходимым условием принадлежности множеству
A
.
Например, пусть
B
— множество всех четных положительных чисел,
а
A
— множество натуральных чисел, последней цифрой которых
является 4. Ясно, что
A
⊂
B
. Поэтому для того, чтобы целое число
n
было четным, достаточно, чтобы его последней цифрой было 4.
С другой стороны, для того чтобы последней цифрой целого числа
было 4, необходимо, чтобы это число было четным.
В случае, когда множества
A
и
B
совпадают, принадлеж-
ность к
A
необходима и достаточна для принадлежности к
B
.
Иными словами, теоремы о том, что некоторое условие является
1
Хотя в некоторых курсах геометрии параллелограмм не считается трапе-
цией.
22
Глава I. Множества и действия над ними
необходимым и достаточным, — это теоремы о совпадении двух
множеств.
Так, для того чтобы целое число
n
делилось на 10, необходимо
и достаточно, чтобы его последней цифрой был 0. Иными словами,
множество
A
чисел, кратных 10, совпадает с множеством
B
целых
чисел, последней цифрой которых является 0.
Точно так же множество всех ромбов совпадает с множеством па-
раллелограммов, имеющих взаимно перпендикулярные диагонали.
Поэтому для того, чтобы параллелограмм был ромбом, необходи-
мо и достаточно, чтобы его диагонали были взаимно перпендику-
лярны.
F
Теория множеств и комбинаторика
F
Подсчитаем, сколько подмножеств имеет конечное множество
(в число подмножеств мы включаем и пустое множество, и само
множество). Множество, состоящее из одного элемента
a
, имеет два
подмножества:
∅
и
{
a
}
. Множество, состоящее из двух элементов
a
и
b
, имеет уже четыре подмножества: те же подмножества
∅
и
{
a
}
и еще
{
b
}
и
{
a, b
}
. Если прибавить к множеству третий элемент
c
,
то кроме уже найденных четырех подмножеств
∅
,
{
a
}
,
{
b
}
и
{
a, b
}
появятся еще четыре подмножества:
{
c
}
,
{
a, c
}
,
{
b, c
}
и
{
a, b, c
}
,
получаемые добавлением элемента
c
к каждому из имевшихся ранее
подмножеств. Ясно, что каждый раз добавление нового элемента
удваивает число подмножеств. Поэтому множество, содержащее
n
элементов, имеет
2
n
подмножеств.
Подмножества конечного множества можно расклассифициро-
вать по числу входящих в них элементов. Если множество содер-
жит
n
элементов, то его подмножества, состоящие из
k
элементов,
называются
сочетаниями из
n
по
k
. Их число обозначается
C
k
n
. Так
как общее число подмножеств равно
2
n
, то справедливо равенство
C
0
n
+
C
1
n
+
. . .
+
C
k
n
+
. . .
+
C
n
n
= 2
n
.
Для чисел
C
k
n
существует немало любопытных соотношений, многие
из которых удается вывести, рассматривая некоторые подмножества
с определенными свойствами. Докажем, например, соотношение
C
k
n
=
C
k
−
1
n
−
1
+
C
k
n
−
1
(1)
в предположении
1
6
k < n
. С этой целью среди всех сочетаний
из
n
элементов
a
1
, . . . , a
n
по
k
выберем сочетания, содержащие
Теория множеств и комбинаторика
23
элемент
a
n
. Остальные
k
−
1
мест в сочетании могут занимать
любые из
n
−
1
элементов
a
1
, . . . , a
n
−
1
. Поэтому число выбран-
ных сочетаний равно
C
k
−
1
n
−
1
. Теперь подсчитаем, сколько сочетаний
из элементов
a
1
, . . . , a
n
по
k
не содержат элемента
a
n
. Эти соче-
тания составлены из элементов
a
1
, . . . , a
n
−
1
. Так как в сочетание
входят
k
элементов, то число таких сочетаний равно
C
k
n
−
1
. Посколь-
ку в каждое из
C
k
n
сочетаний либо входит, либо не входит элемент
a
n
,
то должно выполняться равенство (1).
Отметим еще, что
C
0
n
= 1
при любом
n
>
0
, так как каждое множе-
ство имеет лишь одно пустое подмножество. Точно так же очевидно,
что
C
n
n
= 1
.
Пользуясь сделанными замечаниями, можно последовательно
подсчитывать числа
C
k
n
сначала при
n
= 0
, потом при
n
= 1
, потом
при
n
= 2
и т. д. Таблица чисел
C
k
n
записывается обычно в виде
C
0
0
C
0
1
C
1
1
C
0
2
C
1
2
C
2
2
C
0
3
C
1
3
C
2
3
C
3
3
. . . . . . . . . . . . . . . . . . . . . . . .
(так называемый треугольник Паскаля).
Так как
C
0
n
=
C
n
n
= 1
, то на сторонах треугольника Паскаля стоят
единицы. А остальные числа последовательно вычисляем, учитывая,
что в силу соотношения (1) каждое число равно сумме чисел, сто-
ящих в предыдущей строке слева и справа от него. В результате
получаем следующую таблицу:
1
1
1
1
2
1
1
3
3
1
1
4
6
4
1
1
5
10
10
5
1
. . . . . . . . . . . . . . . . . . . . . . . . .
Существует формула для непосредственного вычисления чи-
сел
C
k
n
. Она имеет вид
C
k
n
=
n
!
k
!(
n
−
k
)!
,
24
Глава I. Множества и действия над ними
где
k
! = 1
·
2
·
. . .
·
k
и
0! = 1
. Предоставляем читателю проверить, что
определяемые этой формулой числа действительно удовлетворяют
соотношению (1) и равенствам
C
0
n
=
C
n
n
= 1
.
Универсальное множество
Крайне редко может встретиться случай, когда в одном и том же
рассуждении пойдет речь и о множестве всех комплексных чисел
и о множестве всех китов в океане (хотя, конечно, не исключено,
что методы теории функций комплексного переменного будут при-
лагаться к изучению движения кита в воде). Обычно все множества,
с которыми имеют дело в том или ином рассуждении, являются под-
множествами некоторого фиксированного множества
I
. Мы будем
называть в этом случае множество
I
универсальным множеством
.
Например, все числовые множества являются подмножествами
множества действительных чисел, множество точек любой геометри-
ческой фигуры — подмножеством в множестве всех точек геометри-
ческого пространства, множество сторон плоского многоугольника —
подмножеством в множестве всех отрезков на плоскости и т. д.
Пересечение множеств
В сентябре 1887 года знаменитому сыщику Шерлоку Холмсу по-
надобилось выяснить название одного парусного судна
1
. Он знал
об этом корабле не слишком много: в январе или феврале 1883 го-
да оно было в Пондишери, в январе 1885 года — в Данди, а сейчас
стояло в Лондонском порту. Пользуясь этими данными, он все-таки
установил название корабля. Для этого достаточно было сравнить
три множества: множество парусников, бывших в указанное вре-
мя в Пондишери, множество парусников, находившихся в январе
1885 года в Данди, и множество парусников, находившихся сейчас
в Лондоне. Оказалось, что только одно судно входило во все три
множества — американский корабль «Одинокая звезда». А так как
Шерлок Холмс полагал к тому же, что преступники родом из Аме-
рики, то круг замкнулся и преступление было раскрыто.
Искать общие элементы множеств приходится не только сыщи-
кам. Ученый-бактериолог, ищущий возбудителя болезни, наблюдает
1
Отсылаем читателя за подробностями к рассказу Конан Дойля «Пять апель-
синовых зернышек».