01. Множества и операции над ними

Множества и подмножества. ОдниМИ из основных, исходных понятий математики являются понятия Множества И его ЭлементоВ. Множество состоит из элементов. Принадлежность элемента А множеству М обозначается А М («А принадлежит М»); непринадлежность А множеству М Обозначается А М или А М.

Пример 1.— множество всех натуральных чисел: 0, 1, 2, 3... В дальнейшем будем обозначать его; элементы — натуральные числа.

— множество всех натуральных чисел, не превосходящих 100.

— множество всех решений уравнения ; элементы — числа, являющиеся решениями этого уравнения.

— множество всех чисел вида , где .

— множество всех действительных чисел (в дальнейшем).

— футбольная команда «Арарат» (т. Е. множество ее футболистов).

— множество всех футбольных команд высшей лИГи в сезоне 1978 г.

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

Отступление 1. Понятие множестВА, как и любое другое исходное понятие математической теории, не определяется. Ведь всякое определение содержит другие понятия, логически предшествующие определяемому; поэтому, по крайНЕй мере, первое определение теории обязательно содержит неопределяемые понятия, которые и принимаются За исходные. В качестве исходных обычно выбираются понятия, в понимании которых не возникает существенных разногласий; более точно: различия в понимании которых не нарушают правильности ни одного положеНИя теории.

Множество А называется Подмножеством множества В (обозначение А В; знак называется знаком включения), если всякий элемент А является элементом В. При этом говорят, что В содержит или покрывает А. Множества А и В равны, если их элементы совпадают, иначе говоря, если А В и В А. Второй вариант определения равенства множеств указывает и на наиболее типичный метод доказательства того, что данные множества равны, заключающийся в доказательстве сначала утверждения А В («в одну сторону»), а затем В А («в другую сторону»). Форму утверждения о равенстве двух множеств имеют многие математические теоремы. Пример — тригонометрическая теорема , состоящая из двух утверждений: а) всякое решение уравнения имеет вид ; б) всякое число вида Является решением уравнения .

Если А В и А В, то А часто называется собственным, строгим или истинным подмножеством В (обозначение А В, знак называется знаком строгого включения).

Заметим, что в случае множества множеств возникает опасность смешения знаков и . Например, верно , но неверно (так как у И — разные элементы!).

Множества могут быть Конечными (т. е. состоящими из конечного числа элементов) и БесконЕЧными. Число элементов в конечном множестве М называется Мощностью М И часто обозначается . Мощность бесконечного множества — более сложное понятие. Оно будет рассмотрено после введения понятия соответствия.

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

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

Списком можно задавать лишь конечные множества. Задание типа = 1, 2, 3 ...— это не список, а условное обозначение, допустимое лишь Тогда, когда оно заведомо не вызывает разночтений. Список обычно заключается в фигурные скобки. Например, А = означает, Что множество А состоит из четырех элементовИ .

Порождающая процедура описывает способ получения элементов множества из уже полученных элементов либо из других объектов. Элементами множества считаются все объекты, которые могут быть построены с помощью такой процедуры. Примером 'Служит описание множества, Где исходными объектами для построения являются натуральные числа, а порождающей процедурой — вычисление, описанное формулой . Другой пример—множество = 1, 2, 4, 8, 16 ..., порождающая процедура для которого определяется следующими двумя правилами:

1) ;

2) Если , то 2т . (Правила, описанные таким образом, назЫВаЮТся Индуктивными иЛи Рекурсивными; о них будет речь в дальнейшем.)

Третий пример — множество, заданное следующим образом. Пусть имеется процедура вычисления цифр разложения числа В бесконечнуЮ десятичнуЮ дробь: = 3,1415926536.. По мере вычисления будем образовывать из последовательно стоящих цифр трехразрядные числа: 314, 159, 265 и т. Д. МНожество всех таких чисел обозначим .

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

Задание множества описанием свойств его элементов, пожалуй, наиболее обычно. В примере 1 так заданы множества; да и задание можно интерпретировать как описание свойства его элементов, заключающегося в воЗМожности представить их в виде . Множество можно задать фразой « - множество всех целых чисел, являющихся степенями двойки». В случае, когда свойство элементов М может быть описано короткИМ выражением Р (х) (означающим «Х обладает свойством Р»), М задается при помощи обозначения М = {}, которое читается так: «М — это множество Х, обладающих свойством P». Например, =, где ,, где. К описанию свойств естественно предъявить требование точности и недвусмысленности. Например, множество всех хороших фильмов 1978 года разные люди зададут разными списками (быть может, пустыми); сами критерии, по которым производится отбор, при этом будут различны. Такое множество нельзя считать строго заданным. Надежным способом точно описать свойство элементов данного множества служит задание распознающей (или, как говорят в математике, разрешающей) процедуры, которая для любого объекта устанавливает, обладает он данным свойством и, следовательно, является элементом данного множества или нет. Например, для , Т. Е. для свойства «быть степенью двойки», разрешающей процедурой может служить любой метод разложения целых чисел на простые множители.

Отметим, что в этом примере разрешающая процедура не является порождающей. Однако ее нетрудно сделать таковой: берем последовательно все натуральные числа и каждое из них разлагаем на простые множители; те числа, которые не содержат множителей, отличных от 2, включаем в . С другой стороны, порождающая процедура может не быть разрешающей. В этой связи предлагаем читателю поразмыслить над множеством, однако предостережем его от поспешных заключений. К этому множеству мы еще вернемся.

К какому виду принадлежит задание множества ? Ни к какому: по существу не задано, а только названо. Задать его можно, например, списком или следующим описанием: « — множество всех лиц, имеющих удостоверения футбольного клуба «Арарат»». Разрешающая процедура для такого описания связана, как легко понять, с проверкой документов.

Отступление 2. Рассмотрение способов задания множеств приводит к мысли о том, что само понятие «точно задать множество» нуждается в уточнении. Такое уточнение совсем не просто, а его важность крайне велика и выходит далеко за пределы самой теории мнОЖеств. Язык множеств — это универсальный язык математики. Любое математическое утверждение можно сформулировать как утверждение о некотором соотношении между множествами: о равенстве двух мноЖеств (см. ранее ), о непустоте некоторого множества («существУеТ непрерывная нИГде не дифференцИРуемая функция»), о Непринадлежности элемента множеству («с помощью цИРкуля и линейки нельзя построить круг, равновеликий данному квадрату») и т. Д. Поэтому анализ способов задания множеств связан с анализом строгости математических утверждений вообще, т. Е. с обсуждением самих оснований математики.

В чем трудности вопроса о задании множеств? Одна из основных трудностей заключается в том, что даже из множеств, точность описания которых не вызывает сомнений, с помощью, казалось бы, вполне законных средств можно сконструировать описания множеств, которые приводят к противоречиям - «парадоксам теории множеств», хорошо Известным в истории математики. Примером является «множество всех множеств». По смыслу своего описания оно должно содержать все мыслимые множества. Однако оно само содержится в множестве своих подмножеств в качестве элемента.

Анализ возникших трудностей привел в первой трети XX в. к бурному развитию области математики, получившей название оснований математики, или метаматематики. Здесь укажем лишь, что одной из ее основных задач является разработка средств задания математических объектов вообще и множеств в частности, которые решали бы все проблемы, связанные с точностью задания, и устраняли бы возможные парадоксы.

Таким образом, в первичной простоте понятия «множество», которая декларировалась в начале главы, при более внимательном рассмотрении не оказывается ни простоты, ни первичности. Однако сказанное там остается в силе, и понятие множества будет по-прежнему считаться исходным ввиду сделанной в отступлении 1 оговорки, которую здесь сформулируем следующим образом: для тех теорий, использующих понятие множества, которые будут рассматриваться в дальнейшем, знать все сложности, связанные с заданием множеств, не обязательно, достаточно зафиксировать некоторые конкретные средства их задания. Со своей стороны, обещаем, что эти средства всегда будут конструктивными и не должны вызывать неясностей в их толковании.

Операции над множествами. Объединением множеств А и В (обозначение — АВ) называется множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств А, В. Символически это можно записать так: Или .

Аналогично определяется объединение произвольной (в том числе бесконечной) системы множеств. Если система содержит небольшое количество множеств, то их объединение описывается явно: И т. д. В общем случае используется обозначение , которое читается так: «объединение всех множеств А, принадлежащих системе S». Если же все множества системы занумерованы индексами, то используются другие варианты Обозначе Ний: (для случая, когда ), (для случая, когда S — бесконечная система и ее множества занумерованы подряд натуральными числами), (для случая, когда совокупность индексов множеств задана множеством ).

Пример 2.

1) А = {А, B, d}, В= {B, D, E, H}, А В = {А, B, D, E, H}.

2) (так как и равны).

3) Обозначим футбольные команды высшей лиги через

: . Тогда — множество всех футболистов (но не команд!) высшей лиги.

Обобщая последнее замечание, отметим, что всЕГда , но неверно .

4) Обозначим через множество всех натуральных чисел, делящихся на и не равных , а через Р — множество всех простых чисел (принято считать, что ).

Тогда — множество всех составных, т. е. непростых, чисел.

Пересечением множеств А и В (обозначение ) называется множество, состоящее из всех тех и только тех элементов, которые принадлежат и A, и B: И .

Аналогично определяется пересечение произвольной (в том числе бесконечной) системы множеств. Обозначения для пересечения системы множеств аналогичны приведенным выше обозначениям для объединения.

Пример 3.

1) , , .

2) .

3) ; более того, для любых И J .

Заметим, что в общем случае из первого свойства не следует второе: например, если , , , то пусто, однако все Попарные пересечения непусты. Система множеств, в которой все попарные пересечения множеств пусты, называется Разбиением Множества U всех элементов этих множеств, а множества такой системы называются классами разбиения. Всякий элемент U входит в один и только в один класс разбиения. Например, является разбиением множества всех футболистов высшей лиги; классы этого разбиения — команды; всякий футболист из множества может входить только в одну команду.

4) (обозначения те же, что и в П. 4 приМЕра 2), так как элемент такого множества должен делиться на все простые числа; ввиду бесконечности множества простых чисел это невозможно.

Разностью множеств А и В (обозначение А \ В) называется множество всех тех и только тех элементов А, которые не содержатся в В:

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

Пример 4.

3) — Множество всех команд высшей лиги, за исключением «Арарата». Эта запись не вызывает разночтений, однако, строго говоря, она неточна: из вычитается не множество футболистов (это бессмысленно, так как и имеют элементы разной природы), а одноэлементное множество команд. Правильная запись . Аналогично этому для множества запись неверна, а запись А \ {А} верна. Напротив, разности (множество всех футболистов ВысШей лиги, не выступающих в «Арарате») является именно множеством футболистов, и заключать его в фигурные скобки не следует. В случаях, когда одновременно рассматриваются множества и множества множеств, соблюдение подобных тонкостей не является пустым педантизмом, а предохраняет от возможной путаницы.

Если все рассматриваемые множества являются подмножествами некоторого «универсального» множества U, то может быть определена операция дополнения. Дополнением множества А (обозначение А) называется множество всех элементов, не принадлежащих А (но принадлежащих U): Множество U должно быть либо задано, либо очевидно из контекста, в противном случае проще пользоваться выражением Например, из определения Очевидно, что - - это множество натуральных чисел, больших 100. Запись же без контекста неясна - то ли это множество отрицательных целых чисел, то ли множество положительных дробных чисел, то ли пустое множество натуральных чисел.

Векторы и прямые произведения. Вектор - это упорядоченный набор элементов. Сказанное не следует считать определением вектора, поскольку тогда потребуется давать объяснения по поводу его синонима «упорядоченный набор». Понятие «вектор» (другой синоним — «кортеж») будем считать, как и понятие множества, неопределяемым. Элементы, образующие вектор, называются координатами или Ком Понентами вектора. Координаты нумеруются слева направо. Число координат называется длиной или размерностью вектора. Бесконечные векторы рассматриваться не будут. В отличие от элементов множества координаты вектора могут совпадать. Вектор будем заключать в круглые скобки, например (0, 5, 4, 5). Иногда скобки и даже запятые опускаются. Векторы длины 2 часто называются упорядоченными парами (или просто парами), векторы длины 3 - тройками и т. Д. Вектор длины П иногда называют N-кой («энкой»).

Два вектора равны, если они имеют одинаковую длину и соответствующие координаты их равны. Иначе говоря, векторы и равны, если Т = п и .

Прямым произведением множеств А и В (обозначение ) называется множество всех пар таких, что В частности, если А = В, то обе координаты принадлежат A. Такое произведение обозначается А2. Аналогично прямым произведением множеств (обозначение ) называется множество всех вектров длинЫ N таких, чТо обозначается АN.

Пример 5.

1) Множество — это множество точек плоскости, точнее, пар вида (А, B), где И являются координатами точек плоскости.

Координатное представление точек плоскости, предложенное французским математиком и философом Декартом, исторически первый пример прямого произведения. Поэтому иногда прямое произведение называют декартовым.

2) Тогда — множество, содержащее обозначенИЯ всех 64 клеток шахматной доски.

3) Рассмотрим множество числовых матриц 3 ´ 4, т. е. матриц вида

Где принадлежат множеству R действительных чисел. Строки матрицы — это элементы множества . Сама матрица, рассматриваемая как упорядоченный набор строк (т. е. вектор), — это элемент множества Компоненты матрицы, заданной таким образом, — строки, а не числа. Поэтому Содержательный смысл этого неравенства в том, что в векторе из не содержится никакой информации о строении матрицы; тот же вектор из мог бы перечислять элементы матриц 4 ´ 3 или 2 ´ 6, которые как математические объекты вовсе не совпадают с матрицами 3 ´ 4.

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

4) Пусть А — конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания, знаки операций и т. Д.). Такие множества обычно называют АлфаВИтами. Элементы множества называются Словами длины П в алфавите А. Множество всех слов в алфавите А — Это множество При написанИи слов (которые по нашему определению являются векторами) не принято пользоваться ни запятыми, ни скобкаМи как разделителями; Зато они могут оказаться символами самого алфавита. Поэтому слово в алфавите А — это просто конечная последовательность символов алфавита А. Например, десятичное целое число — это слово в алфавите цифр {0, 1,..., 9}. Текст, напечатанный на пишущей машинке, является словом в алфавите, определяемом клавиатурой данной машинки (включая знаки препинания и пробел!).

Теорема 1. Пусть — конечные множества и Тогда мощность множества равна произведению мощностей :

Эту теорему докажем методом математической индукции. Для П = 1 теорема тривиально верна. Предположим, что Она верна для П = K, и докажем ее справедливость для . По предположению, Возьмем любой вектор из и припишем справа элемент Это можно сделать разными способами; при этом получится различных векторов из . Таким образом, из всех векторов приписыванием справа элемента из можно получить векторов из , причем все они различны и никаких других векторов в не содержится. Поэтому для теорема верна и, следовательно, верна для любых П. ™

Следствие.

Эта простая теорема и ее следствие лежат в основе очень многих комбинаторных фактов.

Проекции. Проекцией вектора N на I-ю ось (обозначение ПрIN) называется его I-я компонента. Проекцией вектора на оси с номерами называется вектор длины K (обозначение ).

Пусть V — множество векторов одинаковой длины. Тогда проекцией множества V на I-ю ось называется множество проекций всех векторов из V на I-ю ось: . Аналогично определяется проекция множества V на несколько осей: В частности, если то Отметим, что в общем случае — вовсе не обязательно прямое произведение; оно может быть его подмножеством.

Пример 6.

1) Проекция точки плоскости на 1-ю ось — это ее абсцисса (первая координата); проекция на 2-ю ось — ордината.

Следующая >