Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 3
Текст из файла (страница 3)
Заметим, что мы говорим об универсальном множестве как О множестве всех элементов, „рассматриваемых в данной ситуации". При этом мы должны быть уверены в том, что У существует. Например, если взять в качестве У „множество всех множеств", то снова получится парадокс Рассела. Заметим также, что В не определено, если не ясно, по отношению к какому универсальному множеству рассматривается операция дополнения.
1 ) Заметим, что существование множества А ЦВ не гарантировано, так что аксиовозможность опредетения с помощью предиката вызывает сомнение. В магической теории множеств существование множества А()В принимается за аксиому. е !. Ос!юанын пОнятия теОРии множеств Вообще А — В=-А О В. Диаграммы Венна для этих операций вад множествами показаны на рис. 0.2. Если А ОВ= к|, то говорят, что А и В не пересекаются.
Определение. Пусть 1 — некоторое множество, элементы которого использу|отся как индексы, и для каждого |Е! множество А! уже известно. Через () А! обозначим множество (Х ! суще|с! ствует такое ! Е (, что ХЕ А!). Так как сможет не быть конечным, то это определение обобщает определение объединения двух Ацв А гт В А — В рис.
О.2. диаграммы Венка для операций иад множествами. множеств. Если множество !' определено с помощью предиката Р(!), то иногда пишут () А, вместо О А!. Например, () А! оз! |о |е! |> 2 начает Аз() А,() Аа().... Определение. Пусть А — множество. Множество всех подмножеств множества А будем обозначать через У (А) или 2", т. е. У (А) = — (В ! В: — ' А) '). Пример 0.4.
Пусть А = (1, 2!. Тогда У (А) =:= ()д', (1), (2), (!, 2)). Другой пример: У (8)= (66). Г) Вообще, если А — конечное множество, состоящее из и! элементов, то У(А) состоит из 2м элементов. Пустое множество является элементом множества У (А) для любого А. Мы уже отмечали, что элементы множества считаются неупорядоченными. При некоторых обстоятельствах удобно рассматривать упорядоченные пары объектов. Поэтому дадим следующее определение. ') Существование множества всех подмножеств для любого множествз— аксиома теории множеств.
Другими аксиомами теории множеств, в дополнение к этой и к ранее упомянутой аксиоме об объединении, являются следующие: (!) Если А — множество и Р— преднкат, то (Х ) Р (Х) и Х Е А) — множество. (2) Если Х вЂ” атом или множество, то (Х) — множество. (3) Если А — множество, то (Х ! сущестпует У, для которого ХЕ)г н )'Е А) — множество.
ОА.З. Отношении 16 17 гл. а пведвавитвльиые математические сведения Определение. Пусть а и Ь вЂ” объекты. Через (а, Ь) обозначим упорядоченную пару, состоящую из объектов а и Ь, взятых в этом порядке. Упорядоченные пары (а, Ь) и (с, а) называются равными, если а=--с и Ь=й. В противоположность этому (а, Ь)=(Ь, а). Упорядоченные пары можно рассматривать как множества, если определить (а, Ь) как множество (а, (а, Ь)). Мы оставляем в качестве упражнения доказательство того, что (а, (а, Ь)) = =- (с, (с, а()) тогда и только тогда, когда а=Ь и с=А. Таким образом, это определение согласуется с тем, чтб можно считать фундаментальным свойством упорядоченных пар.
Определение. Декартовым произведением множеств А и В, обозначаемым через Ах В, называют множество ((а, Ь) 1аЕА и ЬЕВ). Пример 0.5. Пусть А= (1, 2) и В= (2, 3, 4). Тогда А х В = ((1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4)) Многие распространенные математические понятия, такие, кзк принадлежность, включение множеств, числовое неравенство, являются отношениями.
Мы дадим формальное определение понятия отношения и посмотрим, как под это определение подходят известные примеры отношений. Определение. Пусть А и  — множества. Отношением из А в В называется любое подмножество множества А х В. Если А =-В, то говорят, что отношение задано, или определено, на А (или просто, что это — отношение на множестве А). Если 1с — отношение из А в В и (а, Ь) Е)1, то пишут аДЬ, Множество А называют областью определения отношения Я, а множество  — множеством его значений.
Пример 0.6. Пусть А — множество целых чисел. Отношение < представляет собой множество ((а, Ь) (а меньше Ь). Как и следовало ожидать, для таких пар (а, Ь) мы будем писать а Ь. Определение. Отношение ((Ь, а) ( (а, Ь) Е Д) называется обратным к отноп1ению Д и часто обозначается через Я '. Понятие отношения очень общее. Часто отношение обладает рядом свойств, для которых установлены специальные названия. Определение. Пусть А — множество и Д вЂ” отношение на А.
Отношение Я называется ал. ОснОВные понятия теОРии мно еетв (1) рефлексивным если а)та для всех а нз А (2) симметричным, если а)ТЬ влечет ЬЯа для а и Ь из А, (3) транзитивным, если аДЬ и Ь)тс влекут аВс для а, Ь и с из А. Элементы а, Ь и с не обязаны быть различными. Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности. Важное свойство любого отношения эквивалентности Д, определенного на множестве А, заключается в том, что оно разбивает множество А на непересека1ощиеся подмножества, называемые классами эквивалентности. Для каждого элемента аЕА обозначим через [а1 класс зквивилентноппи, содержии(ий а, т.
е. Множество (Ь1аДЬ). Пример 0.7. Рассмотрим отношение сравнения по модулю 1Т', определенное на множестве неотрицательных целых чисел. Говорят, что а сравнимо с Ь по модулю й1, и пишут а — Ь(шоб Ж), если существует такое целое число й, что а — Ь=йй1. Пусть, например, У=З. Тогда множество (О, 3, 6, ..., Зп, ...) будет одним из классов эквивалентности, поскольку Зп = Зт(шой 3) для любых целых чисел т и п. Этот класс обозначим через [О); можно взять также [31, или [б|„или [3111, поскольку любой элемент класса эквивалентности является представителем этого класса. Другие два класса эквивалентности отношения сравнения по модулю 3 таковы: [11 = (1, 4, 7, ..., Зп + 1, ...) [21 = (2, 5, 8, ..., Зз + 2, ...) Объединение трех множеств [01, Щ и [21 совпадает с множеством всех неотрицательных целых чисел.
Таким образом, это отношение эквивалентности разбивает множество всех неотрицательных целых чисел па три непересекающихся класса эквивалентности [О), [11 и [2( (рис. 0.3). Рвс. 0.3. Классы аквнвалентвьстн отношения сравнения по модулю 3. Индексом отношения эквивалентности, определенного на множестве А, называется число классов эквивалентности, на которые разбивается множество А этим отношением, ГЛ, О ПРЕДВАРИТЕЛЬНЪ!Е МАТЕМАТИЧЕСКИЕ СВЕДЕНИЯ ы.. ОснОВные ИОнятия теОРии множеств В качестве упражнения предлагаем доказать следующую теорему об отношениях эквивалентности: Теорема О.1.
Пусть Р— отношение эквивалентности на А. Тогда г(ля всех а и Ь из А либо !а1-.--1Ь), либо 1а1 и !Ь) не иересекаютсв. Доказательство. Упражнение. П ОЛ.4. Замыкание Отношений Для данного отношения Р часто бывает нужно найти другое отношение Р', включающее Р и обладающее некоторыми дополнительными свойствами, например транзитивностью. Более того, обычно хочется, чтобы Р' было как можно „меньше", т. е. чтобы оно было подмножеством любого другого отношения, включающего Р и обладающего желаемыми свойствами. Конечно, это „наименьшее" отношение может определиться неоднозначно, если дополнительные свойства какие-нибудь странные. Однако для тех распространенных свойств, которые упоминались в предыдущем разделе, часто можно однозначно найти наименынее надмножество данного отношения, обладающее этими свойствами.
Далее мы рассмотрим 'некоторые частные случаи. Определение. я-я степень отношения Р на множестве А (обозначаемая Р'), определяется следующим образом: (1) аР'Ь тогда и только тогда, когда аЯЬ; (2) аР|Ь для |' > 1 тогда и только тогда, когда существует такое сЕА, что аРс и сР' Гб. Зто пример рекурсивного определения; таким методом определения мы будем пользоваться много раз. Чтобы уяснить себе рекурсивный аспект этого определения, допустим, что аР'Ь. Тогда, по (2), существует такое с„что аРс, и с,Р'Ь. Снова применяя (2), видим, что существует такое с„что с,Рс, и С,Рлб.
Еще одно применение (2) говорит о том, что существует такое с„что с,Рс, н с,Р'Ь. Теперь можно применить (1) и убедиться, что С,РЬ. Таким образом, если аР'Ь, то существует такая последовательность элементов с„с„с, из А, что аРс„с,Рс,, с,Рс, и с,РЬ. Транзитивное замыкание отношения Я на множестве А обозначается через Р+ и определяется так: аР Ь тогда и только тогда, когда аР'Ь для некоторого 1) 1. Мы увидим, что Я+в наименьшее транзитивное отношение, включающее Р. Можно было бы иначе определять Р+, сказав, что аР+Ь, если существует такая последовательность с„с„..., сл, состоящая из нуля илн более элементов, принадлежащих А, что аРс„, с,Рс„... ..., с„,Рс„, с„РЬ. Если и =О, то полагаем аРЬ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
