1. Понятие множества. Понятие множества является одним из наиболее общих математических понятий. Его определение не удается свести к другим понятиям. Поэтому для понятия множества дается описательное определение, содержание и смысл которого раскрываются при изучении теории множеств. Множество – это набор, совокупность каких-либо объектов, называемых его элементами, обладающих некоторым общим для них характеристическим свойством. В качестве примеров можно привести множество действительных чисел, множество решений заданного алгебраического уравнения, множество прямых, проходящих через заданную точку. В принципе никаких ограничений на природу элементов, их количество и свойства не налагается, так что допустимо рассмотрение таких множеств, как множество налогоплательщиков, множество процентных ставок и т. п.
Элементы, составляющие множество, обычно обозначаются малыми латинскими буквами, а само множество – большой латинской буквой. Знак ∈ используется для обозначения принадлежности элемента множеству. Запись a∈A означает, что элемент a принадлежит множеству A. Если некоторый объект x не является элементом множества A, пишут x∉A. Например, если A – это множество четных чисел, то 2∈A, а 1∉A. Множества A и B считаются равными (пишут A=B), если они состоят из одних и тех же элементов.
Если множество содержит конечное число элементов, его называют конечным; в противном случае множество называется бесконечным. Если множество A конечно, символом |A| будет обозначаться число его элементов. Множество, не содержащее ни одного элемента, называется пустым и обозначается символом ∅. Очевидно, |∅|=0.
Пример. Пусть A – множество действительных решений квадратного уравнения x2+px+q=0. Множество A конечно, |A|≤2. Если дискриминант D = p2–4q отрицателен, множество A пусто. Множество действительных решений квадратичного неравенства x2+px+q≤0 конечно, если D≤0, и бесконечно, если D>0.
Конечное множество может быть задано перечислением всех его элементов. Если множество A состоит из элементов x, y, z, …, пишут A={x, y, z, …}. Например, A={0, 2, 4, 6, 8} – множество четных десятичных цифр; B={2, 3} – множество решений уравнения x2–5x+6=0; C={0, 1, 2, 3, 4, 5, 6} – множество остатков при делении целых чисел на 7.
Иногда перечислением элементов задают и бесконечное множество. Это делают в тех случаях, когда ясен алгоритм последовательного порождения элементов. Например, A={0, 1, 4, 9, 16, …} – множество квадратов целых чисел.
В общем случае множества можно определять по так называемой схеме свертывания. При заданном характеристическом свойстве F и заданном классе элементов K множество A определяется как множество, которое содержит все элементы из K, обладающие свойством F. Для определения по схеме свертывания используется следующая запись:
A = {x | x обладает свойством F}.
Применяя сокращение F(x) для обозначения того, что элемент x обладает свойством F, будем писать
A = {x | F(x)}.
Класс K может быть указан явно; в этом случае используется запись
A = {x∈K | F(x)}.
Множество четных чисел P можно определить как
P = {x | x – четное целое число},
или как
P = { x∈Z| x четно},
где через Zобозначено множество целых чисел.
Неограниченное применение схемы свертывания ведет к противоречиям. Например, можно получить «множество всех множеств»:
M = {x | x – множество}.
Если считать M множеством, то получаем M∈M.
Рассмотрим парадокс Рассела, открытый в 1902 году. Назовем множество правильным, если оно не является своим элементом, и неправильным в противном случае. Определим множество R как множество всех правильных множеств. Более формально:
R = {x | x∉R}.
В соответствии с определением для любого множества A справедливо утверждение:
A∈R тогда и только тогда, когда A∉A.
В частности, если считать R множеством, то его само можно взять в качестве A, но тогда мы придем к противоречию:
R∈R тогда и только тогда, когда R∉R.
Более подробно. Если R правильное, то есть не является своим элементом, то оно должно находиться в R, то есть быть своим элементом. Если же R неправильное, то оно является своим элементом, то есть содержится в R, но R содержит только правильные множества. Таким образом, R не может быть ни правильным, ни неправильным.
Введем используемое в дальнейшем понятие индексированного семейства множеств. Пусть I – некоторое множество, каждому элементу которого i сопоставлено однозначно определенное множество Ai. Элементы множества I называют индексами, а совокупность множеств Ai называют индексированным семейством множеств и обозначают через (Ai)i∈I.
2. Подмножества. Говорят, что множество B является подмножеством (или частью) множества A и пишут B⊂A, если всякий элемент множества B является элементом множества A. Например, множество натуральных чисел N является подмножеством множества целых чисел Z, а последнее в свою очередь является подмножеством множества рациональных чисел Q, то есть N⊂Z и Z⊂Q, или, короче, N⊂Z⊂Q. Легко видеть, что если B⊂A и A⊂B, то множества A и B состоят из одних и тех же элементов, и, значит, A=B. Нарядус обозначением B⊂A используется также A⊃B, имеющее тот же смысл.
Вообще говоря, подмножество множества A может быть задано определяющим свойством. Например, свойство быть четным числом определяет в множестве целых чисел подмножество четных чисел. Каково бы ни было множество A, пустое множество и само A являются его подмножествами: ∅⊂A, A⊂A. Пустое множество может быть задано свойством, которым не обладает ни один элемент множества A, например, x≠x. Возможны и более содержательные ситуации. Например, свойство быть корнем уравнения x2+1=0 задает в множестве действительных чисел пустое подмножество. Множество A может быть задано как свое подмножество каким-нибудь свойством, которым обладают все элементы множества A, например, x=x. Подмножества множества A, отличные от ∅ и A, называются собственными. Для заданного множества A обозначим через 2A множество всех его подмножеств.
Пример. Пусть A={a, b, c}. Тогда множество 2A состоит из следующих элементов:
Далее будет показано, что если множество A конечно и содержит n элементов, то это множество имеет 2n подмножеств, то есть |2A |=2|A|.
3. Пересечение и объединение множеств.Пересечение множеств A и B, обозначаемое A∩B, – это множество, состоящее из всех тех элементов, которые принадлежат обоим множествам A и B. Например, если A={1,2,3} и B={2,3,4}, то A∩B={2,3}. В соответствии с определением
A∩B⊂A и A∩B⊂B,
причем A∩B является в определенном смысле наибольшим множеством, обладающим этими свойствами:
если C⊂A и C⊂B, то C⊂A∩B.
Далее, A∩B=B тогда и только тогда, когда B⊂A. Если множества A и B не имеют общих элементов, их пересечение пусто, A∩B=∅; в этом случае говорят, что множества A и B не пересекаются.
Объединение множеств A и B, обозначаемое A∪B, – это множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств A и B. Например, если A={1,2,3} и B={2,3,4}, то A∪B={1,2,3,4}. В соответствии с определением
A⊂A∪B и B⊂A∪B,
причем A∪B является наименьшим множеством, обладающим этими свойствами:
если A⊂C и B⊂C, то A∪B⊂C.
Далее, A∪B=B тогда и только тогда, когда A⊂B.
Операции пересечения и объединения можно обобщить на случай произвольного индексированного семейства множеств.
Если множество индексов состоит из натуральных чисел, используются и другие обозначения. Например, AПересечением семейства множеств (Ai)i∈I называется множество A, состоящее из всех тех элементов, которые принадлежат каждому из множеств Ai. Пишут A=∩i∈IAi1∩A2∩A3, если I={1,2,3}; A1∩A2∩…∩An или , если I={1,2,…,n}; , если I – это множество всех натуральных чисел, и т. п. Аналогично объединением семейства множеств (AIniiA1=I∞=1iiAi)i∈I называется множество A, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств Ai. Для объединения используют обозначение A=∪i∈IAi и другие, подобные тем, которые используются для пересечения.
Пример.Пусть +=1;0nnAn, где n=1,2,… пробегает множество натуральных чисел. Тогда, очевидно, =∞=21;01InnA, поскольку A1⊂A2⊂… . Покажем, что . В самом деле, если x∈[0; 1), то x∈A)1;0[1=∞=UnnAn, когда x>1/n, то есть при n>1/x. Если же x<0 или x>1, то x не попадает ни в одно из An, а значит, и в их объединение.
4. Разность множеств. Дополнение множества.Разность множеств A и B, обозначаемая A\B, – это множество, состоящее из всех тех элементов, которые принадлежат множеству A, но не принадлежат множеству B. Например, если A={1,2,3} и B={2,3,4}, то A\B={1}. В соответствии с определением
A\B⊂A и (A\B) ∩B=∅,
причем A\B является в определенном смысле наибольшим множеством, обладающим этими свойствами:
если C⊂A и C∩B=∅, то C⊂A\B.
Далее, A\B=A тогда и только тогда, когда A∩B=∅, и A\B=∅ тогда и только тогда, когда A⊂B. Если B⊂A, то разность A\B называют также дополнением (или относительным дополнением) множества B в множестве A. Иногда относительное дополнение будет обозначаться через AB. Любое собственное подмножество B множества A вместе со своим относительным дополнением образует разбиение множества A на два непересекающихся множества:
∅=∩ABB, ABBA=∪.
Часто в теоретико-множественных конструкциях используется универсальное множество U. Считается, что все рассматриваемые множества являются его подмножествами. Относительное дополнение множества A до универсального множества называется дополнением (без прилагательного «относительное») и обозначается через A. Очевидно, ∅=U и U=∅.
Симметрическая разность множеств A и B, обозначаемая AΔB, – это множество, состоящее из всех тех элементов, которые принадлежат одному из множеств A и B, но не принадлежат другому. Более формально,
AΔB = (A\B) ∪ (B\A).
Например, если A={1,2,3} и B={2,3,4}, то AΔB={1,4}.
5. Свойства операций над множествами.Приведем основные тождества так называемой алгебры множеств (будем предполагать, что используемые в тождествах множества A, B, C являются подмножествами универсального множества U).
Убедиться в справедливости перечисленных свойств можно путем несложной непосредственной проверки.
Пример.Проверим первый из законов де Моргана. Покажем сначала, что BABA∪⊂∩. Предположим, что BAx∩∈. Тогда x∉A∩B, так что x не принадлежит хотя бы одному из множеств A и B. Таким образом, x∉A или x∉B, то есть Ax∈ или Bx∈. Это означает, что BAx∪∈BA∩ . Мы показали, что произвольный элемент множества является элементом множества BA∪. Следовательно, BA∪⊂BA∩. Обратное включение BABA∪⊃∩ доказывается аналогично. Достаточно повторить все шаги предыдущего рассуждения в обратном порядке.
6. Диаграммы Эйлера–Венна.Для наглядного представления операций над подмножествами некоторого универсального множества используются диаграммы Эйлера–Венна. На таких диаграммах фон рисунка соответствует универсальному множеству, а фигуры изображают множества, участвующие в операциях. Например, на следующем рисунке:
круги изображают множества A и B. Объединение двух кругов соответствует объединению A∪B; область 3 соответствует пересечению A∩B; область 1 – множеству A\B=BA∩; область 2 – множеству BAAB∩=\; область 4 – множеству BA∪; объединение областей 1 и 2 соответствует симметрической разности AΔB. Легко видеть, что имеет место следующее соотношение:
AΔB = (A∪B)\(A∩B).
7. Прямое произведение множеств.Из любой пары элементов a и b (не обязательно различных) можно составить новый элемент – упорядоченную пару (a,b). Упорядоченные пары (a,b) и (c,d) считают равными и пишут (a,b)=(c,d), если a=c и b=d. В частности, (a,b)=(b,a) лишь в том случае, когда a=b. Элементы a и b называют координатами упорядоченной пары (a,b) (соответственно первой и второй).
Прямым (декартовым) произведением множеств A и B называется множество всех упорядоченных пар (a,b), где a∈A и b∈B. Прямое произведение множеств A и B обозначается через A×B. В соответствии с определением имеем
A×B = {(a,b)| a∈A, b∈B}.
Пример.Пусть A={1,2,3} и B={2,3,4}. Тогда множество A×B состоит из следующих девяти элементов: (1,4), (2,4), (3,4), (1,3), (2,3), (3,3), (1,2), (2,2), (3,2). Графически элементы произведения множеств A×B удобно помещать на «координатной плоскости», считая, что первый множитель A расположен на горизонтальной полуоси, а второй множитель B – на вертикальной. Например,
(1,4) (2,4) (3,4)
(1,3) (2,3) (3,3)
(1,2) (2,2) (3,2)
Подобно парам, можно рассматривать упорядоченные тройки, четверки и, вообще, упорядоченные наборы элементов произвольной длины. Упорядоченный набор элементов длины n обозначается через (a1,a2,…,an). Для таких наборов используется также название кортеж длины n. Допускаются в том числе и кортежи длины 1 – это просто одноэлементные множества. Кортежи (a1,a2,…,an) и (b1,b2,…,bn) считаются равными, если a1=b1, a2=b2,…,an=bn.
По аналогии с произведением двух множеств определим прямое произведение множеств A1, A2, …, An как множество всех кортежей (a1,a2,…,an) таких, что a1∈A1, a2∈A2, …, an∈An. Обозначается прямое произведение через A1×A2×…×An.
Понятие прямого произведения может быть обобщено на случай произвольного семейства множеств (Ai)i∈I. Назовем I-кортежем набор элементов (Ai)i∈I такой, что ai∈Ai для каждого i∈I. Прямое произведение семейства множеств (Ai)i∈I – это множество, состоящее из всех I-кортежей. Для обозначения этого множества используется символ Πi∈IAi и его разновидности, подобные тем, которые применяются для обозначения пересечения и объединения семейства множеств.
В случае, когда множество A умножается само на себя, произведение называют (декартовой) степенью и используют экспоненциальные обозначения. Так, в соответствии с определением A×A=A2, A×A×A=A3 и т. д. Считается, что A1=A и A0=∅.
Непосредственно из определений следует справедливость следующих соотношений:
