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

При этом используют запись:ÌÃÒÓÌÃÒÓНаконец, можно использовать метод характеристических функций. Каждое множество A можно описать характеристической функцией множества(1, x ∈ A;χA (x) =0, x ∈ A.ÌÃÒÓÔÍ-12ÌÃÒÓ28ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ14. МНОЖЕСТВА ÔÍ-12И ОТНОШЕНИЯÌÃÒÓВыход из создавшегося положения может быть таким. Мы четко оговариваем, каким образом могут образовываться множества. Вот часть этих правил (список неполон и далее могутдобавляться новые правила):*На самом деле было бы достаточно оговорить существование множества N; существование остальных можнодоказать.ÔÍ-12Запись {x: ϕ(x)} в общем случае определяет класс.

Частным случаем класса является множество. Но есть классы, не являющиеся множествами (например, класс Рассела). Собственноклассы отличаются от множество только в одном: они не могут рассматриваться в качествеэлементов других классов или множеств. Такое разделение позволяет снять парадоксы теориимножеств.ÌÃÒÓ1) существует пустое множество;2) из любой конечной совокупности множеств M1 , M2 , . . . , Mk можно образовать конечноемножество {M1 , M2 , . . . , Mk };3) объединение, пересечение, разность двух множеств есть множество;4) существует множества N натуральных чисел, Z целых чисел, Q рациональных чисел, Rдействительных чисел, C комплексных чисел* ;5) для всякого множества M существует множество всех его подмножеств 2M — булеан;6) для любого множества M и любого условия ϕ(x) существует множество {x ∈ M : ϕ(x)}.ÔÍ-12Замечание 14.1.

В качестве парадокса иногда приводят следующее. Деревенский парикмахер бреет тех и только тех в своей деревне, кто сам не бреется. Бреет ли этот парикмахерсебя? Конструкция очень похожа на парадокс Рассела, но на самом деле от него отличается.Здесь нет ссылки на себя самого: все объекты, рассматриваемые в качестве элементов множества (жители деревни) определены, и их конечное число. Здесь не может возникнуть нарушенияпричинно-следственной связи, как в парадоксе Рассела, приводящей к незамкнутости определения. Можно проверить всех жителей деревни на соответствие условию и убедиться в том, чтомножество описанных парикмахеров пусто. Коллективизирующее свойство содержит противоречие и определяет пустое множество. Увязать рассмотренный пример с парадоксом Расселаможно только в аллегорическом плане.ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓОпределение множества свертыванием не связано какими-либо ограничениями. Например,можно попытаться определить множество всех множеств, не принадлежащих самому себе“,”что записывается следующим образом: {x: x ∈/ x}.

Формальная сторона определения соблюдена: любое множество, как элемент, может находиться слева от знака принадлежности, и втоже время оно может находиться справа от этого знака. Однако определение A = {x: x ∈/ x}внутренне противоречиво. Действительно, что верно A ∈ A или A ∈/ A? Если предположить,что A ∈ A, то по своему определению заключаем: A ∈/ A. А если предположить, что A ∈/ A, тозаключаем, что A ∈ A. В результате в любом случае имеем два взаимоисключающих утверждения.Полученное противоречие называют парадоксом Рассела. Это не единственное противоречие в теории множеств, использующей неограниченное свертывание — наивной теориимножеств.

Такие противоречия часто называют антиномиями или парадоксами теориимножеств.Причины возникновения парадоксов в теории множеств можно понять на содержательномуровне: объект определяется через другие еще не определенные объекты (в данном случаечерез себя). Налицо нарушение причинно-следственной связи. Это противоречие проявляетсяи в таком определении: множество всех множеств“. Если это множество, то оно должно”принадлежать самому себе. Но если мы допускаем такое свойство, то мы можем рассмотретьчасть этого множества, а именно множество всех множеств, не принадлежащих самому себе!Так что и здесь есть противоречие.ÌÃÒÓÔÍ-12ÌÃÒÓ29ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ14. МНОЖЕСТВА ÔÍ-12И ОТНОШЕНИЯÌÃÒÓÌÃÒÓÔÍ-12Отметим, что в подавляющем числе предметных областей универсум оказывается множеством.

В этом случае все рассматриваемые множества получаются выделением, и противоречийне возникает.Рассмотрим еще один способ определения множеств. Напомним, что из двух объектов a иb можно образовать упорядоченную пару — новый объект (a, b). Термин упорядоченный“”указывает на то, что объекты (a, b) и (b, a) при различных a и b различаются. Формальноупорядоченную пару можно определить как множество {{a}, {a, b}}. С помощью объектов a1 ,a2 , .

. . , an можно определить упорядоченную n-ку, или кортеж (a1 , a2 , . . . , an ). Объекты a1 ,a2 , . . . , an называются компонентами этого кортежа.Для любого конечного набора множеств A1 , A2 , . . . , An определено множествоA1 × A2 × . . . × An = {(a1 , a2 , . . . , an ): a1 ∈ A1 , a2 ∈ A2 , . . . , an ∈ An }всех кортежей длины n. Это множество называется декартовым произведением множествA1 , A2 , . .

. , An . Множество A × A × . . . × A называют n-й декартовой степенью множества A иобозначают An . В частности, A2 — декартов квадрат A, A3 — декартов куб A.Замечание 14.2. Обратим внимание на то, что, например, A1 × A2 × A3 и (A1 × A2 ) × A3 —разные множества. Первое состоит из кортежей длины 3, а второе из кортежей длины 2, перваякомпонента которых есть кортеж длины 2.

Элементы первого множества имеют вид (a1 , a2 , a3 ),а элементы второго — вид ((a1 , a2 ), a3 ). Однако указанное различие формально, на практикетакие конструкции не различают.14.2. Отображения и соответствияОпределение. Обозначения. Виды отображений (сюръекция, инъекция и биекция). Композиция.Обратное отображение. Соответствия. Композиция соответствий и обратное соответствие.ÌÃÒÓD(F ) = {x ∈ X: ∃y ∈ Y : (x, y) ∈ F }ÔÍ-12Пусть даны множества X и Y . Любое подмножество F ⊂ X × Y называется соответствием. Выделим два тривиальных соответствия: пустое соответствие ∅ ⊂ X × Y иуниверсальное соответствие F = X × Y .Соответствия обозначаются так же, как и отображения: F : X → Y . Это становится понятным, если заметить, что отображения — фактически частный случай соответствия.Напомним, что отображением F множества X в множество Y называют закон или правило, которое с каждым элементом x ∈ X сопоставляет единственный элемент y ∈ Y .

В этомопределении есть неопределенный термин закон или правило“. Но в действительности такой”неопределенный термин в определении отображения не нужен. Этот закон или правило“ —”всего лишь способ определения множества F упорядоченных пар (x, y), удовлетворяющих двумусловиям:• ∀x ∈ X ∃y: (x, y) ∈ F ;• (x, y1 ) ∈ F , (x, y2 ) ∈ F , ⇒ y1 = y2 .Каждому соответствию F : X → Y отвечают область определения соответствияÌÃÒÓÌÃÒÓÌÃÒÓ30ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ14. МНОЖЕСТВА ÔÍ-12И ОТНОШЕНИЯR(F ) = {y ∈ Y : ∃x ∈ X : (x, y) ∈ F } .Соответствие F : X → Y всюду определено, если D(F ) = X.

Соответствие F : X → Yфункционально по второй (первой) компоненте, если для любых упорядоченных пар (x, y1 ) ∈F и (x, y2 ) ∈ F выполняется условие y1 = y2 . Всюду определенное функциональное по второйкомпоненте соответствие называется отображением.ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12и область значений соответствияÌÃÒÓ{(x, z) ∈ X × Z: ∃y ∈ Y (x, y) ∈ F, (y, z) ∈ G} .Легко увидеть, что в частном случае отображений композиция соответствий совпадает с композицией отображений.Замечание 14.4.

Установилась традиция, когда отображения, участвующие в композиции,записываются справа налево. Это связано с равенством g ◦ f (x) = g(f (x)). Для композициисоответствий принято то же соглашение, однако это не является обязательным* .Для соответствия F : X → Y множество{(y, x) ∈ Y × X: (x, y) ∈ F }idX = (x, y) ∈ X 2 : x = y .i∈Ii∈I*В книге Дискретная математика“ А.И.

Белоусова, С.Б. Ткачева (вып. XIX серии Математика в техниче””ском университете“) как раз использовано прямое обозначение композиции.**Это не совсем точно: область определения F −1 ◦ F может не совпадать с множеством X.ÔÍ-12Индексация семейства множеств нужна лишь из соображений удобства. Например, можнобыло бы рассмотреть множество A, элементами которого являются множества и ввести операцию ∪A = {z: ∃u ∈ A, z ∈ u}, которая представляет собой объединение всех элементов множества A.ÌÃÒÓПусть I, U — некоторые множества.

Отображение F : I → 2U можно интепретироватькак индексированное семейство множеств {Ai , i ∈ I}. Например, когда мы пишемA1 , A2 , . . . , Am , то тем самым каждому значению индекса в соответствие ставим множествосемейства. С помощью индексированных семейств можно ввести объединение и пересечениебесконечного числа множеств. Пусть задано семейство {Ai , i ∈ I}. Тогда определены множества[\Ai = {x: ∃i ∈ I, x ∈ Ai } ,Ai = {x: ∀i ∈ I, x ∈ Ai } ,ÔÍ-12определяет обратное соответствие F −1 . Композиция F −1 ◦ F есть тождественноеотображение** idX : X → X, определяяемое как диагональ декартова квадратаÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12Хотя соответствие определено нейтрально — как определенного вида множество, его обозначение указывает, с какой точки зрения рассматривается этот объект.