Множества и отношения. Алгебра множеств.Отображения и соответствия. Отношения и операции. Элементы математической логики (Избранные лекции)

Московский государственный технический университетимени Н.Э. БауманаÌÃÒÓФакультет «Фундаментальные науки»Кафедра «Математическое моделирование»ÌÃÒÓÀ.Í. ÊàíàòíèêîâÈÇÁÐÀÍÍÛÅ ËÅÊÖÈÈÏÎ ÀËÃÅÁÐÅÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12Äëÿ ñòóäåíòîâ ôàêóëüòåòà ÔÍÌÃÒÓÊîíñïåêò ëåêöèéÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12Москва2009ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ14.

МНОЖЕСТВА И ОТНОШЕНИЯÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-1226ÌÃÒÓМножество — это любая совокупность объектов, понимаемая как единое целое.Эту фразу не следует рассматривать как определение. На самом деле множество — неопределимое математическое понятие, а сказанное лишь описывает, каким образом это понятиеможет использоваться на практике. С точки зрения математики важно, каким образом объекты, называемые множествами, могут использоваться.Множество — это совокупность объектов, каждый из которых называется элементоммножества. Если x — элемент множества A, то пишут x ∈ A. Два множества могут бытьсвязаны отношением включения. Запись A ⊂ B означает, что каждый элемент множестваA является и элементом множества B.

Если A ⊂ B и B ⊂ A, то множества A и B состоят изодних и тех же элементов, т.е. совпадают, иначе говоря, равны: A = B. Иногда различаютстрогое включения, при котором A ⊂ B и A 6= B, и нестрогое включение, при которомA ⊂ B, но, возможно, что и A = B. В этом случае строгое включение обозначают A ⊂ B, анестрогое — A ⊆ B.С множествами можно выполнять различные операции.

Объединением A ∪ B множествA и B называется множество, состоящее из всех элементов, каждый из которых принадлежитA или B (или обоим множествам сразу). Пересечением A ∩ B множеств A и B называетсямножество, состоящее из всех элементов, каждый из которых принадлежит одновременно иA, и B. Разностью A \ B множеств A и B называется множество, представляющее собойсовокупность элементов множества, не принадлежащих множеству B.Операции над множествами обладают следующими свойствами:1) A ∪ B = B ∪ A (коммутативность объединения);2) (A ∪ B) ∪ C = A ∪ (B ∪ C) (ассоциативность объединения);3) A ∩ B = B ∩ A (коммутативность пересечения);4) (A ∩ B) ∩ C = A ∩ (B ∩ C) (ассоциативность пересечения);5) (A∪B)∩C = (A∩C)∪(B∩C) (дистрибутивность пересечения относительно объединения);6) (A∩B)∪C = (A∪C)∩(B∪C) (дистрибутивность объединения относительно пересечения);7) A ∩ B ⊂ A;8) A ⊂ A ∪ B;9) (A ∩ B) ∪ B = B;10) (A ∪ B) ∩ B = B;11) A \ B = A \ (A ∩ B);12) A ∪ B = (A \ B) ∪ B.Перечислены не все свойства, а только основные.С помощью трех введенных операций над множествами можно определить и другие операции.

Одна из наиболее употребительных — симметрическая разность A4B = (A \ B) ∪∪ (B \ A) = (A ∪ B) \ (A ∩ B). Это коммутативная ассоциативная операция.ÔÍ-12ÔÍ-12Основные понятия. Отношение принадлежности. Отношение включения. Операции объединения и пересечения. Разность и симметрическая разность. Свойства операций (коммутативность,ассоциативность, дистрибутивность). Зависимость операций. Основные и второстепенные операции. Универсум. Способы доказательства теоретико-множественных равенств. Диаграммы Венна.Характеристические функции. Способы задания и записи множеств. Антиномии. Декартово произведение.ÌÃÒÓÌÃÒÓ14.1. Алгебра множествÌÃÒÓACBCРис. 14.1ÔÍ-12Во-вторых, можно использовать метод двух включений, смысл которого состоит в следующем. Пусть мы доказываем равенство A = B.

Сначала, предполагая, что x ∈ A, мы путемнекоторых умозаключений доказываем, что x ∈ B. Затем точно так же мы показываем, чтоесли x ∈ B, то x ∈ A.В-третьих, можно использовать метод эквивалентных преобразований. Используя уже известный набор равенств, преобразуем левую часть доказываемого равенства так, чтобы получить правую. Можно также преобразовывать правую часть равенства, получая левую часть,или обе его части, получая слева и справа одно и то же выражение.ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓBÌÃÒÓAÔÍ-12Множества A и B могут вообще не иметь общих элементов. Для таких множеств операцияпересечения будет иметь смысл, если определить специальное пустое множество, котороевообще не имеет элементов.

Такое множество обозначают ∅. Оно имеет следующие свойства:1∗ ∅ ⊂ A;2∗ A ∪ ∅ = A;3∗ A ∩ ∅ = ∅;4∗ A \ ∅ = A;5∗ ∅ \ A = ∅;6∗ A4∅ = A.Видно, что пустое множество играет роль нулевого“ множества, если ассоциировать объ”единение со сложением чисел, а пересечение — с умножением чисел.Операции можно выражать друг через друга.

Можно выделить некоторые операции какосновные, первоначальные, отнеся остальные операции к второстепенным, поскольку они могут записаны с помощью основных. В представленном изложении роль основных операцийиграют объединение, пересечение и разность, а операция симметрической разности оказывается второстепенной. Но могут быть и другие варианты. Например, A ∩ B = A \ (A \ B),т.е. пересечение выражается через разность. Аналогично объединение можно выразить черезпересечение и симметрическую разность: A ∪ B = (A4B)4(A ∩ B).

Таким образом, выборосновных операций не является однозначным.В каждой области математики или каком-либо разделе естествознания (говорят в предметной области) используют вполне определенный набор объектов, рассматриваемых какэлементы множества. Например, в планиметрии элементами множеств могут быть точки илипрямые, в математическом анализе рассматривают множества, состоящие из чисел или группчисел (элементов арифметических пространств). Совокупность всех элементов всех множеств,рассматриваемых в данной предметной области называется универсумом. В качестве универсума в рамках частной теории может рассматриваться какое-либо конкретное множество(например, множество действительных чисел).Если задано универсальное множество U , содержащее все рассматриваемые объекты, тодля любого рассматриваемого множества A имеем A ⊂ U .

Можно определить операцию A =U \ A. Множество A называют дополнением множества A. Для дополнения используютдругие обозначения: CA, CA, Ac и т.п.Сформулированные свойства можно доказывать по-разному. Во-первых, можно использовать графический метод, изображая множества как множества точек плоскости, ограниченныезамкнутыми кривыми (такие изображения называют диаграммами Венна). Например, ассоциативность объединения видна из диаграмм на рис.

14.1.ÌÃÒÓÌÃÒÓÌÃÒÓ27ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ14. МНОЖЕСТВА ÔÍ-12И ОТНОШЕНИЯÌÃÒÓA = {a, b, c, . . .}.A = {x: ϕ(x)} .Говорят, что множество A определено свертыванием по свойству ϕ(x), называя правуючасть равенства сверткой по этому свойству. Например, запись {x: x ∈ R, x > 0} определяет множество всех положительных действительных чисел (R — множество всех действительных чисел).Иногда используют следующую форму свертки:ÔÍ-12При этом говорят об определении множества выделением. Например, можно вместо{x: x ∈ R, x > 0} записать {x ∈ R: x > 0}.Из пояснения понятия множества можно сделать вывод, что множество рассматриваетсякак самостоятельный объект (единое целое).

Из таких объектов могут составляться новыемножества. Таким образом, любое множество может оказаться элементом другого множества.Зачастую множества обозначают прописными буквами, а их элементы — строчными (это соглашение выдержано выше). Но поскольку множество может быть элементом другого множества,такое разделение обозначений (элемент, множество) теряет смысл. Впрочем, в ряде случаеврассматриваются только простые множества, элементами которых являются простые объекты.Например, дифференциальное исчисление функций одного переменного ограничивается рассмотрением числовых множеств.

В этом случае разделение обозначений остается оправданным.ÌÃÒÓA = {x ∈ U : ϕ(x)} .ÔÍ-12Например: {1, 2, 5}.Для бесконечных множеств, и даже конечных с большим количеством элементов этот способ неприемлем. В этом случае множество можно определять, указывая одно или несколькосвойств, выделяющих элементы множества в ряду остальных В этом случае говорят о коллективизирующем свойстве. Коллективизирующее свойство можно представить как некое утверждение, которое истинно для элементов множества и не истинно для других объектов,например: множество целых четных чисел (коллективизирующее свойство: число целое четное), множество непрерывных на отрезке [a, b] функций (коллективизирующее свойство: функция непрерывна на [a, b]).

Записав коллективизирующее свойство через ϕ(x), множество, имопределяемое, можно записать следующим образом:ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12Основные операции над множествами можно выразить соотношениями между их характеристическими функциями:• χA∪B (x) = χA (x) + χB (x) − χA (x)χB (x);• χA∩B (x) = χA (x)χB (x);• χA\B (x) = χA (x) − χA (x)χB (x) = χA (x) 1 − χB (x) ;• χA4B (x) = χA (x) + χB (x) − 2χA (x)χB (x);• χA (x) = 1 − χA (x).Доказав равенство характеристических функций двух множеств с использованием известныхпреобразований функций и операций над функциями, мы тем самым установим равенство самихмножеств.Множества можно разделить на конечные множества и бесконечные множества.Первые можно определять, перечисляя их элементы.