1. Основные понятия теории множеств. Способы задания множеств. Операции над множествами. Теоретикомножественные тождества
 Скачать 4.95 Mb.
|
|
1. Основные понятия теории множеств. Способы задания множеств. Операции над множествами. Теоретико-множественные тождества. Объекты, составляющие множество, называют его элементами. Множества обозначают прописными буквами латинского алфавита ( ), элементы множеств – строчными буквами ( ). Если каждый элемент множества входит в множество , то называется подмножеством . При этом пишут: или . Множество, не содержащее ни одного элемента, называется пустым (обозначается). Множество называется истинным, если оно не пустое. Из определения подмножества следует, что каждое множество является подмножеством самого себя: . Кроме того, считают, что пустое множество есть подмножество любого множества : . Различают два вида подмножеств множества : само и называют несобственными подмножествами; все остальные подмножества, если они существуют, – собственными. В теории множеств для удобства и краткости записей используют специальные обозначения: – квантор общности (означающий «любой», «для всех», «каков бы ни был»); – квантор существования (означающий «существует», «найдется», «можно найти»); – импликация (символ следствия, означающий «влечет за собой). С помощью этих символов условие запишется так: . Множество называется эквивалентным множеству (обозначается ), если между элементами и можно установить взаимно однозначное соответствие. Различают конечные и бесконечные множества. Число элементов множества называется его мощностью или кардинальным числом и обозначается. Таким образом, конечное множество, содержащее элементов, имеет мощность . Если эквивалентно множеству натуральных чисел , то его называют счетным и его мощность обозначается через . Множество , эквивалентное множеству действительных чисел , называется континуальным, а его кардинальное число c – мощностью континуума. Способы задания множеств Задание множества с использованием общепринятых обозначений. Для числовых множеств имеем: – множество натуральных чисел; – множество целых чисел; – множество рациональных чисел; – множество действительных чисел; – множество комплексных чисел. Задание множества перечислением его элементов. Конечное множество можно задать перечислением его элементов и записать в виде . Например, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} – множество десятичных цифр. Задание множества с помощью характеристического свойства его элементов. Характеристическое свойство – это свойство, которым обладают все элементы данного множества и только они. Этот способ применим для конечных и бесконечных множеств. Пусть – утверждение, заключающееся в том, что элемент обладает свойством . Тогда запись означает, что рассматривается множество всех элементов , обладающих свойством . Например, отрезок [0, 1] действительной прямой можно определить следующим образом . Рекурсивное задание множества. Этот способ заключается в следующем: 1. Указываются некоторые исходные элементы, входящие в множество. 2. Описывается механизм, позволяющий получить новые элементы из имеющихся. 3. Объявляется, что в множестве нет никаких других объектов кроме тех, которые можно получить из исходных, применяя описанный в п. 2 механизм. Например, множество можно задать рекурсивно: 1. . 2. . 3. – наименьшее подмножество натурального ряда, удовлетворяющее условиям 1 и 2. Условие 3 определяет как пересечение всех множеств, удовлетворяющих условиям 1 и 2. Теория множеств, рассматриваемая без ограничений на способы задания множеств, называется наивной теорией множеств. В этой теории еще при жизни ее создателя Г. Кантора были обнаружены многочисленные парадоксы. Операции над множествами Объединением множеств и (обозначение ) называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств или : . Вместо символа объединения используется также символ +. Пересечением множеств и (обозначение ) называется множество, состоящее из элементов, принадлежащих каждому из множеств и : . Для операции пересечения используются также другие обозначения: . Аналогично определяются объединение и пересечение произвольной совокупности множеств , . Здесь – множество индексов. Если – множество первых натуральных чисел, то употребляются обозначения и , а в случае если , то будем писать и . Разностью множеств и (обозначение ) называется множество, состоящее из всех элементов , не принадлежащих : . В отличие от двух предыдущих операций разность некоммутативна: . Если , то . Симметрической разностью множеств и (обозначение ) называется множество элементов и , которые содержатся только в одном из этих множеств: . Дополнением к множеству (обозначение ) относительно универсального множества называется множество: или . Операции объединения, пересечения и дополнения часто называют булевыми операциями над множествами. Так как операция разности не обладает свойством ассоциативности, то ее выражают через другие операции, например, операции дополнения и пересечения: . Универсальное множество позволяет геометрически изображать множества и операции над ними с помощью диаграмм Венна (рис. 1). Рис. 1. Диаграммы Венна Теоретико-множественные тождества ассоциативность объединения и пересечения. коммутативность объединения и пересечения. дистрибутивность. идемпотентность. законы де Моргана. дополнимость. 13. – закон двойного дополнения. существование универсальных границ. законы дополнения. 2. Прямое произведение множеств. Соответствие между множествами. Понятие отображения множеств. Прямым произведением множеств и называют множество , элементами которого являются всевозможные упорядоченные пары , такие, что , : Прямое произведение в общем случае не обладает свойствами коммутативности и ассоциативности: , . Пусть теперь даны множеств: . Упорядоченный набор из элементов, таких, что , ,…, , называется вектором или кортежем. Множество таких векторов представляет собой прямое произведение множеств : Если , то множество называется степенью (прямой) множества и обозначается через . Проекцией вектора на -ю ось (обозначение ) называется его компонента. Проекцией вектора на оси с номерами называется вектор длины (обозначение ). Пусть – множество векторов одинаковой длины. Тогда проекцией множества на -ю ось называется множество проекций всех векторов на -ю ось: . Аналогично определяется проекция множества на несколько осей: . Соответствием между множествами и называется подмножество . Если , то говорят, что соответствует при соответствии . Множество называется областью определения, а множество – областью значений соответствия. Если , то соответствие называется всюду определенным или полностью определенным (в противном случае – частичным); если , то соответствие называется сюръективным или сюръекцией. Множество всех , соответствующих элементу , называется образом в при соответствии . Множество всех , которым соответствует элемент , называется прообразом в при соответствии . Соответствие называется инъективным или инъекцией, если прообразом любого элемента из является единственный элемент из . Соответствие называется функциональным или однозначным, если образом любого элемента из является единственный элемент из . Соответствие называется взаимно однозначным или биекцией, если оно всюду определено, сюръективно, функционально и инъективно. Отображением множества во множество называется функциональное соответствие (обозначение ). Множество называется областью определения отображения, элемент – аргументом отображения, элемент – образом при отображении . При этом пишут . Часто, когда множества – числовые, отображение называют функцией. Если числовое только множество , то отображение называют функционалом. Образом подмножества при отображении называется множество . Прообразом подмножества при отображении называется множество . Отображения вида называются преобразованиями множества . Преобразование называется тождественным, если . Пусть и – некоторые отображения. Суперпозицией этих отображений называется отображение , определяемое следующим образом: . Отметим, что суперпозиция определена не для любых пар отображений. Однако суперпозиция двух преобразований одного и того же множества определена всегда. Операция суперпозиции ассоциативна: , где , , – отображения. Пусть и . Отображение называется обратным к отображению (а отображение обратным к ), если , . Обратное отображение обозначается . Если обратное отображение существует, то оно единственно. Необходимое и достаточное условие существования обратного отображения дает следующая теорема. Теорема 1. Отображение имеет обратное тогда и только тогда, когда оно биективно. 3. Отношения на множестве. Отношения эквивалентности и порядка. Примеры. Бинарным отношением на множестве называется подмножество . Тот факт, что находится в отношении с , обозначается следующим образом: Областью определения бинарного отношения на множестве называется множество , а областью значений – множество . Пример 2. Примеры отношений: – отношение равенства «=» на множестве состоит из всех пар вида , Если элемент находится в отношении равенства к элементу , то пишут ; – отношение неравенства « » на множестве R: ; – отношение делимости «|»на множестве : . Так как отношения определяются как подмножества, то над ними можно производить теоретико-множественные операции. Дополнением бинарного отношения на множестве считается множество . Например, если – отношение «=», то =« », а « ». Обратным отношением(обращением) для бинарного отношения называется множество . Произведением отношений и называется отношение . Всякое подмножество называют -местным отношением на множестве . Свойства отношений. Отношения делятся на различные виды в зависимости от того, обладают или не обладают некоторыми свойствами. Рефлексивность: . Например, рефлексивно на множестве прямых отношение «прямая пересекает прямую ». Симметричность: . Например, симметрично отношение параллельности на множестве прямых плоскости. Транзитивность: . Например, транзитивно на множестве отрезков отношение «отрезок длиннее отрезка ». Отношение эквивалентности. Отношение на множестве называется отношением эквивалентности, если оно обладает свойствами рефлексивности, симметричности и транзитивности. Отношение эквивалентности часто обозначают: . Пример 3. Примеры отношения эквивалентности: – отношение «одного роста» на множестве людей; – отношение подобия на множестве треугольников; – отношение принадлежности двух студентов к одной студенческой группе. Смежным классом (классом эквивалентности) элемента по эквивалентности называется множество . Любой элемент называется представителем этого класса. Множество классов эквивалентности элементов множества по эквивалентности называется фактор-множеством по и обозначается . С каждым отношением эквивалентности связано разбиение множества на непересекающиеся подмножества, которое лежит в основе всевозможных классификаций. Разбиением множества называется всякое представление этого множества в виде суммы непересекающихся подмножеств: , . Здесь – множество индексов, которое может быть конечным, счетным или несчетным. Множества называют слоями разбиения. Имеет место следующая теорема. Теорема 2. Для того чтобы отношение позволяло разбить множество на классы, необходимо и достаточно, чтобы было отношением эквивалентности. Приведем примеры использования отношения эквивалентности для образования математических понятий. Понятие вектора. Сначала вводится понятие направленного отрезка, как пары точек . Два отрезка и объявляются эквивалентными, если середины отрезков и совпадают. Далее проверяется, что это отношение между направленными отрезками рефлексивно, симметрично и транзитивно. Класс эквивалентных отрезков и есть вектор. Построение рациональных чисел из целых. Рассмотрим всевозможные пары из целых чисел такие, что . Пары и объявляются эквивалентными, если . Далее проверяется рефлексивность, симметричность и транзитивность. Класс эквивалентных пар – рациональное число. Отношение порядка. Бинарное отношение на множестве называется отношением порядка, если оно рефлексивно, транзитивно и антисимметрично. Последнее свойство означает: . Пример 5. Примеры отношений порядка: – отношение « » на множестве действительных чисел. Отношение « » порядком не является, так как оно не рефлексивно; – отношение « » на множестве подмножеств некоторого множества; – на множестве двоичных слов длины можно ввести отношение порядка следующим образом. Пусть и – двоичные слова. Положим , если для , 1, 2, …, . Пусть – отношение порядка на множестве . Элементы называются сравнимыми, если или , в противном случае – несравнимыми. Порядок называется линейным, если любые два элемента сравнимы. В противном случае говорят о частичном порядке. Множество с заданным на нем порядком (частичным или линейным) называется упорядоченным (частично или линейно). Первое отношение в примере 5 задает линейный порядок, два других отношения порядка – частичные. Например, двоичные слова 011 и 110 несравнимы. Элемент частично упорядоченного множества называется максимальным (минимальным), если из того, что следует . Элемент называется наибольшим (наименьшим), если ( ) для всех . Верхней (нижней) гранью подмножества частично упорядоченного множества называется такой элемент , что ( ). Точной верхней (нижней) гранью подмножества называется наименьшая верхняя (наибольшая нижняя) грань для . Точная верхняя и точная нижняя грани обозначаются соответственно и . Линейный порядок на множестве называется полным, если каждое непустое подмножество множества имеет наименьший элемент. В этом случае множество называется вполне упорядоченным. Частично упорядоченное множество называется решёткой, или структурой, если для любых двух элементов существует точная нижняя и точная верхняя грани. Пример 6. Примеры решёток: – множество всех подмножеств данного множества, упорядоченное по включению; – всякое линейно упорядоченное множество; причем, если , то . 4. Общие правила комбинаторики: правила суммы, произведения и биекции. Булеан конечного множества. Примеры. Правило суммы Это правило позволяет найти число элементов в объединении двух конечных множеств и : . (1) Если множества и не пересекаются ( ), то . (2) Иногда правило суммы формулируют следующим образом: если объект можно выбрать способами, а объект – способами, то выбор «либо , либо » можно осуществить способами. Пример 1. Сколько имеется путей из вершины в вершину на решетке, показанной на рис. 1? Рис.1. Решетка размером [4 5] Обозначим множество всех путей из в через и разобьем его на два непересекающиеся подмножества: – множество путей, проходящих через вершину , – множество путей, проходящих через вершину . Тогда . Очевидно, что искомое количество путей зависит только от размеров решетки. Обозначим через количество путей в решетке размером [ ], где , – соответственно количество горизонтальных и вертикальных путей. Тогда причем . Пользуясь этим соотношением для данного примера , , получим: . Правило произведения Это правило позволяет подсчитать число кортежей, которые можно составить из элементов данных конечных множеств. Для двух множеств и (3) Из равенства (3) следует, что число упорядоченных пар, которые можно составить из элементов множеств и равно произведению числа элементов в этих множествах. Это правило можно сформулировать иначе: если объект можно выбрать способами и после каждого из таких выборов другой объект можно выбрать способами, то выбор « и » можно осуществить способами. По индукции правило умножения можно распространить на любое число сомножителей в декартовом произведении: . (4) Наиболее часто последнее равенство применяется, когда : . (5) В этом случае множество называют алфавитом, его элементы – буквами, а элементы декартова произведения – словами в алфавите . Слова записывают как в обычном языке, то есть без разделения букв запятыми и без внешних скобок: . Число называют длиной слова. Пусть . Тогда правило (5) можно сформулировать следующим образом: число слов длины в алфавите из букв равно . Пример.2. Из 80 студентов 40 играют в футбол, а 50 – в волейбол, причем 27 студентов играют и в футбол и в волейбол. Сколько студентов играют хотя бы в одну из этих игр? Сколько студентов играют лишь в одну из этих игр? Сколько студентов не играют ни в одну из этих игр? Пусть – множество студентов, играющих в футбол, – множество студентов, играющих в волейбол. Тогда , , . Число студентов, играющих хотя бы в одну из этих игр, согласно формуле (2.1): . Число студентов, играющих только в футбол: , а только в волейбол: . Число студентов, играющих только в одну из этих игр: . Число студентов, не играющих ни в одну из этих игр: . Пример 3. Сколько существует 6-значных телефонных номеров? Алфавит состоит из 10 цифр, номер – слово длины 6 в этом алфавите. Поэтому количество номеров равно . Пример 4. Найти число слов, содержащих 4 буквы, в которых любые две соседние буквы различны (число букв в алфавите равно 33). Первую букву можно выбрать 33-мя способами, вторую, третью и четвертую – 32 способами. Число слов равно 33∙323=1081344. |