В библиотеке

Книги2 383
Статьи2 537
Новые поступления0
Весь каталог4 920

Рекомендуем прочитать

Баиов А.К.Вклад России в победу союзников
Автор предлагаемой книги - А. К. Байов, 1871 - 1935 гг., ординарный профессор Российской военной академии, в течение многих лет занимал кафедру русского военного искусства в Академии генерального штаба. Продолжая работу известных военных ученых, профессора Масловского и профессора Мышлаевского, генерал Байов создал курс истории русского военного искусства, как самостоятельный отдел военной науки.

Поисковая система

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

АвторНепейвода Н.Н.
НазваниеПрикладная логика
Год издания1996
РазделКниги
Рейтинг0.60 из 10.00
Zip архивскачать (1 503 Кб)
  Поиск по произведению

Глава 5. Базовые математические понятия

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

§ 5.1. Множества. Диаграммы Эйлера и Венна

В современной математике понятие множества является одним из центральных и окутанных наибольшим числом предрассудков. Множества являются прежде всего удобным средством превращать высказывания в объекты и, соответственно, операции над высказываниями в функции. При этом классическая логика переходит в булеву алгебру. Лучше все­го охарактеризовать множество как “единое имя для совокупности всех объектов, обладающих данным свойством”. Но это предложение, конечно же, не может считаться определением.

Множество всех объектов, обладающих свойством А{х), обозначается { х | А ( х )}. Если Y = { х | А ( х )}, то А{х) называется характеристическим свойством множества У, а У — сверткой предиката А. По определению Y , выполнена следующая эквивалентность:

У у { у У - ФФ - А ( у )).

Два множества считаются равными, если их характеристические свойства эквивалентны1. (Часто это выражают словами: «Множества равны,

1 Как мы уже замечали, если математики уславливаются считать некоторые объек­ты равными, то тем самым они отказываются рассматривать какие-либо их свойства, если они содержат одни и те же элементы».) Множество X вложено в множество Y ( X С Y ), если характеристическое свойство Y следует из характеристического свойства X 2 3. Поскольку

( А - фф - В ) - фф - ( А => В ) & ( В => А ),

X < z Y и Y С X тогда и только тогда, когда X = Y .

Простейшее из множеств, и чаще всего встречающееся в формулах, — пустое множество 0 , вообще не содержащее элементов. Очевидно, что пустое множество задается тождественно ложным характеристическим свойством, и соответственно все пустые множества равны. Поэтому считается, что множество квадратных кругов равно множеству удмуртов-негров. Но здесь, как и всегда, когда математика расходится со здравым смыслом4, возникают некоторые тонкости.

Было бы естественно, чтобы тождественно истинное условие, на­пример х = х , определяло “полное” множество. Но математики давно уже отказались считать, что существует единое такое полное множество для всех разделов математики, не говоря уже о ее применениях. Тут вступает в свои права контекст, и мы вспоминаем о том, что неотъемлемым элементом математической интерпретации является универс — множество всех рассматриваемых в данной теории предметов. Очевидно, что тождественно истинное условие определяет универс, и тождественно истинные формулы, относящиеся к разным теориям, определяют разные универсы нарушающие равенство. Таким образом, отождествив два множества, характеристические свойства которых эквивалентны, мы тем самым косвенно заявляем, что, во-первых, элементы во множествах совершенно равноправны, поскольку единственное свойство элемента, принимаемое во внимание при образовании множества, — характеристическое; во-вторых, элементы не повторяются. Значит, при реализации, скажем, машинной структуры данных, соответствующей множествам, нужно как-то учесть эти свойства, а это порою не так-то просто. Например, задав множество просто как массив переменной длины из элементов, мы грубо нарушаем оба требования: элементы становятся упоря­доченными согласно индексам, и в массиве могут попасться одинаковые члены.

2 Порою значок ? используют лишь для т. н. строгого вложения , когда вдобавок выполнено X = Y , анаше вложение обозначают ?. Но посмотрите, как уродливо выражается строгое вложение, и станет ясно, что лучше брать за исходное нестрогое вложение, что и ввел в математическую традицию Никола Бурбаки.

3 Никола Бурбаки — легендарный современный математик (легендарный как в смыслеосновательности его работ, так и в буквальном). Его на самом деле никогда не существовало, под этим именем выпускала серию работ группа выдающихся математиков французской школы (не говорим ‘французов', потому что в их числе был поляк).

4 Но и когда она с ним согласуется, часто все не так просто...

В математике рассматривается одна теория — теория множеств, которая длительное время претендовала на выразимость в ней всех математических понятий. В ней пытаются базироваться на одних лишь множествах, и тогда ее универс должен быть множеством всех мно­жеств. Но выяснилось, что принятие существования множества всех множеств приводит к невозможности совместить некоторые построения, принятые в математике, в рамках одной теории. Так, например, одна из аксиом теории множеств: если X — множество, то для любого условия А { х | х X & А ( х )} —также множество. Приняв существование множества всех множеств, мы при помощи данной аксиомы выделяем из него расселовское множество из примера (1.7), которое приводит к парадоксу. Оно определяется как

{ х | х U & х (? х }

(как обычно, U — универс).

Математики вышли из данного положения, как всегда, с честью, но не без потерь и хитростей: было просто принято, что множества всех множеств нет, и универс теории множеств сам множеством не является 5 . Примененный метод лечения полностью соответствует тому, как действуют представители других наук в случае появления противоречий в парадигме.

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

Она автоматически отбрасывает и те взгляды, которые ей противоречат (как ненаучные), и те понятия, которые в нее не входят (как тоже ненаучные либо не принадлежащие данной специальности и потому неинтересные). Парадигмой пользуются, пока она совсем не износится, и зачастую она уже трещит по всем швам, а на нее упорно ставят заплатки. Одним из видов таких заплаток является убийство факта, противоречащего парадигме, путем вывода данного понятия за ее пределы либо переформулировки соответствующего термина таким образом, чтобы он устранял выявленный недостаток. Другой способ — постули­рование данного факта как нового принципа 6 . Так, геологи длительное время отбрасывали как противоречащую парадигме теорию движения материков, предпочитая каждый конкретный факт либо игнорировать, либо объяснять по отдельности. Математики по крайней мере потрудились свести спасенные после заплаток принципы теории множеств в достаточно стройную систему.

5 Впрочем, американский логик Куайн предложил вариант теории множеств, в кото­ром прекрасно уживаются с множеством всех множеств, но, как и следовало ожидать, эта теория множеств показалась несколько странноватой в других отношениях и не была воспринята математиками.

Множество, состоящее из конечного числа элементов а\ , ... , а п , принято обозначать { а \ , ... , а п }. Его определение через характеристическое свойство:

{ а \ , ... , а п } = { х \ х = a i V ••• У х = а п } . (5.1)

Исходя из тождества 5.1, можно видеть, в частности, что

{ а , Ъ } = { Ъ , а ] , { а , а } = { а }.

Стоит отметить еще одну тонкость. Нужно строго различать х и { ж }. Первое выражение обозначает сам элемент, а второе — множество, заключающее этот один элемент. Разница между ними примерно такая же, как между шимпанзе и шимпанзе, посаженным в клетку в зоопарке: { ж } скорее похоже на такую клетку, чем на ее обитателя7.

Операциям конъюнкции и дизъюнкции над формулами соответствуют операции пересечения П и объединения U множеств:

X U Y = { х \ х е X \/ у eY } X f ) Y = { х \ х е X к у е Y } ,

а операцию, соответствующую отрицанию, как правило, вводят лишь тогда, когда фиксирован универс U . Дополнение X множества X — это множество элементов U , не входящих в X s .

Не важно, что он, как правило, не согласуется с другими! На много шагов вперед неприятные вещи никто продумывать не любит.

Конечно же, множество X в некотором смысле изоморфно (т. е. имеется взаимнооднозначное отображение, сохраняющее все основные структуры) множеству

{{x} x ? X } .

Но насколько такой изоморфизм может быть коварным, видно из того, что в теории множеств Куайна (где существует универс) его часто нет. Так что одно найдешь, другое потеряешь...

8 Таким образом, в теории множеств дополнений у множеств нет; но о них, тем не ме­нее, говорят, имея в виду дополнение до фиксированного подразумеваемого множества, например, некоторого множества действительных чисел до всего К .

Рис. 5.1: Диаграмма Эйлера

Говорят, что два множества не пересекаются, если их пересечение — пустое множество:

1(17 = 0.

Объединение, пересечение и дополнение обычно называются булевыми операциями, составленные из множеств с их помощью выражения — булевыми выражениями, значение такого выражения — булевой комбинацией входящих в него множеств, а равенства двух булевых выражений — булевыми тождествами (например, X U X = X ). Через булевы операции определяются еще две полезные операции над множествами — разность X \ Y = ( X П — Y ) и симметрическая разность XAY = ( X \ Y ) U ( Y \ X ). Булевы тождества позволяют продемонстрировать достаточно уникальный пример превращения иллюстраций в строгие доказательства. Он интересен еще и как пример представления данных: таблица истинности превращается в совершенно непохожую внешне, но изоморфную ей структуру.

В XVIII веке Л. Эйлер использовал для иллюстрации взаимосвязей между понятиями чертежи, которые были названы позднее «круги Эйлера» (точнее, как мы и будем называть их, “диаграммы Эйлера”). На­пример, соотношение между понятиями “протестант, католик, христианин, европеец” показывает диаграмма 5.1.

Здесь не имеет значения относительный размер кругов либо других замкнутых областей, но лишь их взаимное расположение. Безусловно, такие диаграммы могут играть в логике лишь ту же роль, что чертежи в геометрии: они иллюстрируют, помогают представить и доказать, но сами ничего не доказывают. Учитывая, что по сути своей логика не является математической наукой и поэтому имеет дело с понятиями, а областей, помеченных * , соответствует левой и правой частям тождества.

Рис. 5.2: Правильная диаграмма Венна

Следующие две диаграммы показывают, что тождество не выполнено. Объединение областей, помеченных * , соответствует левой и правой частям тождества.

Рис. 5.3: Правильная диаграмма Венна для неправильного тождества

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

Начнем с двух примеров. Рассмотрим тождество X U ( YnZ ) = ( XU Y ) П ( X U Z ) . Левой и правой его частям можно сопоставить следующие чертежи (см. рис. 5.2).

Квадрат изображает универс, круги — наши множества. Из их рассмотрения видно, что выражение в левой части совпадает с выражением в правой. Более того, интуитивно очевидно, что данный чертеж на самом деле доказывает тождество для всех возможных множеств.

Рассмотрим теперь тождество X A ( Y A Z ) = ( XUYU Z )\(( XC \ Y ) U ( X П Z ) U ( Y П Z )). Левой и правой его частям можно сопоставить следующие чертежи (см. рис. 5.3).

9 Этот вид диаграмм предложил и детально разработал Дж. Венн, поэтому они называются по его имени: диаграммы Венна .

Самая внутренняя область пропала, и кажется, что рассматриваемое тождество выполнено

Рис. 5.4: Неправильная диаграмма Венна

Если же нарисовать диаграмму чуть-чуть неаккуратно, некоторые области могут пропасть и проверка, соответственно, оказывается из­лишне оптимистичной (см. рис. 5.4 ).

Для того чтобы установить точный критерий удовлетворительности чертежа, рассмотрим соотношение между булевым тождеством и логи­ческой формулой. Каждому булеву выражению над множествами сопо­ставляется логическая формула, в которой X заменяется на с € X , П на &, U на V , — на ­. Два множества равны, когда соответствующие им фор­мулы эквивалентны. А для проверки эквивалентности нужно построить таблицу истинности. В этой таблице вычисляются значения формул, со­ответствующих двум частям равенства, при всех возможных комбина­циях значений элементарных подформул. Проанализируем, чему соот­ветствует такая комбинация на языке теории множеств. Если есть си­стема множеств Xi , то задание значений формул с € Xi соответствует указанию для всех Xi , чему именно, множеству либо его дополнению, принадлежит с. Это приводит к следующим определениям.

Определение 5.1.1. Составляющие системы множеств {Х\ ,..., Х п } за­даются следующим индуктивным определением.

Базис . Составляющие { Х± } суть само Х\ и его дополнение.

Шаг . Если S — составляющая {Х\ ,..., Х п _\}, то SP \ X n и SD Х п — составляющие { Х \, ..., Х п }.

Система множеств независима, если все ее составляющие непусты.

Теорема 5.1. (Венн) Если булево равенство выполнено для некоторой независимой системы множеств, то оно выполнено для любой системы множеств.

Доказательство. Прежде всего отметим, что любая составляющая S системы { Х \, ..., Х п } однозначно определяет значения всех формул вида с € Xi . Это легко устанавливается по индукции. Отсюда следует, что две составляющие либо совпадают, либо не пересекаются. Далее, если Y — булева комбинация { Х \ , ..., Х п }, S — составляющая этой системы, то S либо подмножество Y , либо не пересекается с Y . Это вытекает из того, что значение характеристического свойства Y полностью определяется значениями всех с € Х% . И наконец, составляющая независимой системы является подмножеством Y тогда и только тогда, когда соответствующее значение в таблице истинности формулы, определяю­щей Y , есть 1. Значит, в независимой системе любая булева комбинация однозначно разлагается на составляющие (т. е. представляется как объединение составляющих) и это разложение сохраняется и для других систем множеств (конечно, для зависимых систем могут появиться и другие разложения). Поэтому если в независимой системе две булевы комбинации имеют одни и те же составляющие, они будут иметь одинаковые значения и в любой другой системе.

Итак, булево равенство достаточно проверить на одной, но хорошо подобранной системе множеств. Следовательно, правильно нарисованная диаграмма Венна полностью обосновывает тождество. ?

Диаграммы Венна подводят нас к следующему фундаментальному вопросу. В них нет предложений, нет правил вывода, не видно умозаключений. Так что же такое доказательство с математической точки зрения? Ответом на это может быть следующая характеризация:

Доказательство — конструкция, синтаксическая правильность которой гарантирует семантическуюскую(5.2) .

Не известно ни одного случая, когда такое описание отказало бы 10 . И заодно данная формулировка показывает, насколько далеко нынешним программам до доказательств: в программе синтаксическая правильность ничего не гарантирует.

В заключение отметим, что множество всех подмножеств данного множества X называется его множеством-степенью и обозначается 2 либофХ.

Упражнения к § 5.1

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

5.1.1. Независима ли следующая система множеств:

Мы научились проверять на диаграммах булевы равенства. А как с булевыми вложениями (утверждениями формы X С У , где X и У — булевы выражения)?

Построить независимые системы из четырех и пяти множеств.

(Для тех, кто хорошо знает геометрию.) Доказать, что нет независимой системы, изображенной четырьмя окружностями на плоскости.

(Для тех, кто очень хорошо знает геометрию.)

Сколько независимых множеств может быть изображено шарами в и-мерном пространстве?

Докажите, что нет независимой системы пяти выпуклых множеств на плоскости.

Сколько независимых множеств может быть изображено выпуклыми областями в и-мерном пространстве?

5.1.6. Проверить булевы тождества:

Аи В U С = ( А \ В ) U ( В \ С ) U ( С \ А);

( А \ В ) \ С = А \ ( В U С);

( А \ В ) П ( А \ С ) = ( А \ В ) \ С;

( А \ В ) \ С = ( А \ С ) \ В;

( А \ В ) U ( А \ С ) = А \ ( В \ С);

6. ( А П В П С ) = ( A U В U С ) \ ( А П В П С);

А /\( В АС )) = ( A U В U С ) \ ( А П В ) \ ( А П С ) \ ( В П С); АДВ ) U ( ВАС ) U ( СДА ) = ( A U - В U С ) \ ( А П - В П С); АДВ ) Д (. ВДС ) Д ( СДА ) = ( А \ . В ) П ( В \ С ) П ( С \ А);

( А \ В ) U ( В \ С ) = ( А \ С ) U ( С \ - В);

( А \ В ) U ( В \ С ) U ( С \ А ) = ( A U ( В U С ));

( АДВ ) U ( ВАС ) U ( СДА ) = ( A U - В ) П ( АиС ) П ( Ви С);

(( A \ B )\ C ) U (( B \ C )\ A ) U (( C \ A )\ B ) = ( AUBUC )\ (( А Г ) В ) U ( А Г ) С ) U ( В Г ) С ));

( А \ В ) U ( В \ С ) U ( С \ D ) U ( Z ) \ А ) = ( AU В U С U D ) \ ( А Г ) В Г ) С Г ) D );

(AAB)A(CAD) = (AAD)A(C АВ );

( А \ В \ С ) U ( В \ С \ D ) U ( С \ D \ A ) U ( Z ) \ А \ i ?) = ( АГ ) В ) U ( АГ ) С ) U ( АГ ) D ) U ( В Г ) С ) U ( В Г ) D ) U ( СГ ) D );

(( Аи - В ) Д ( АиС )) Д (. ВиС ) = ( АП - В ) Д (( АпС ) Д (- ВпС ));

( АпВ ) А (( АпС ) А ( ВпС )) = ( Апв ) и ( АпС ) и ( ВпС );

(( AUB ) A ( AUC )) A ( BUC ) = ( АиВиС ) А ( АпВ Г ) С ).

5.1.7. Построить диаграмму Эйлера для следующей совокупности понятий:

{горожане, селяне, рабочие, пенсионеры, безработные}.

5.1.8. Постройте диаграмму Эйлера для понятий, встречающихся в перечисленных нижепредложениях, в предположении, что все высказанные утверждения истинны. Универс — участники олимпиад по физике, математике и программированию.

Ни один парень не стал призером всех трех олимпиад.

Ни одна девушка не стала призером не менее чем двух олимпиад.

Никто из симпатичных участников не вошел в число призе­ров ни по математике, ни по программированию.

5.1.9. Аналогично для следующих предложений.

Поэты — хорошие люди.

Все хорошие люди — поэты либо отшельники.

Ни поэты, ни отшельники не могут быть палачами.

Палач — художник тогда и только тогда, когда он — китаец.

Китайцы — хорошие палачи. Китайские отшельники — поэты.

5.1.10. (Порецкий) Относительно девиц, бывших на некоем бале, из­вестны следующие 14 утверждений:

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

Возможнолитакое?Если возможно,постройтедиаграмму Эйлера для девиц бала и выведите из нее отношения между различными их категориями.

5.1.11. Разработайте способ проверки условных тождеств следующего вида:

если X = Y , то U = V

на диаграммах, подобных диаграммам Эйлера и Венна.

§ 5.2. Кортежи , n - ки , наборы , прямые произведения , прямые суммы

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

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

Определение 5.2.1. Кортеж— конечная последовательностьобъектов , называемых егочленами. Кортежсчленами a 1 , . . . , a n , расположен - нымивданном порядке, обозначается [ a 1 , ..., a n ] . Вматематической логике принято нумеровать члены кортежа,начинаяснулевого,авболь - шинстве приложений—начинаяспервого 12 .

[ a , b ] Ф [ b , а ], [ а , а ] Ф [ a ].

Таким образом, в отличие от множеств, кортеж может содержать и повторяющиеся члены, здесь важны не только сами элементы, но и порядок, в котором они расположены. Итак,

11 Что служит неисчерпаемым источником ошибок, в том числе и тонких. Особенно
коварны такие ошибки в инструментальных системах, когда одно понятие подменяется
другим в самом начале, из-за чего возникает множество несообразностей.

12 Так что не поленитесь выяснить это, если Вам говорят о кортежах!

Как и в других случаях (в частности, для множеств), принято рассматривать и пустой кортеж, не содержащий членов. Он обозначается просто [ ] . Кортеж из одного элемента обозначается [ х ] и строго различается от самого х. Для кортежей определены следующие стандартные функции: длина кортежа х lh ( x ) — число членов в кортеже. Функция выделения г-той компоненты: ( ж )^, где г ^ lh ( x ) (если счет членов начи­нают с нуля, то неравенство становится строгим). Операция соединения (либо конкатенации) двух кортежей:

[ а \, ..., а п ] * [ Ь \, ..., bjf ] = [ а \, ..., a n , bi , ..., bk ].

Стоит выделить как фундаментальную еще одну операцию, которая отличается от предыдущей по типам данных: присоединение объекта к кортежу. Обычно для нее используют заимствованный из языка ЛИСП идентификатор APPEND :

APPEND ([ ai , ..., а п ], а ) = [ а \, ..., а п , а ]. (5.3)

Множество всех кортежей из элементов множества U обозначается U °°. В литературе оно часто обозначается также U * . Мы используем данное обозначение для более общего множества; см. ниже.

Пример 5.2.1. Строки в языках программирования могут рассматриваться как машинное представление кортежа из символов. Как и всегда, при машинном представлении математического понятия накладываются ресурсные ограничения; например, что длина строки не больше 255 символов.

Другое, более адекватное представление кортежа — линейные списки. Они могут быть заданы следующими описаниями языка Паскаль ( data — некоторый ранее определенный тип данных):

type t= record

element: data; next: A t end ;

Рассмотрим более сложное построение. Кортежи могут строиться из других кортежей и т. п. Такое представление интенсивно используется, в частности, в языке ЛИСП. Хочется иметь универс, включающий все кортежи кортежей... Чтобы аккуратно его определить, прибегают к следующей конструкции.

Пусть U 0 = U . Тогда для всякого i определим U i +1 = U i ? U i ?. Таким образом, U 1 будет множеством всех элементов и кортежей, постро­енных из элементов, к U 2 , соответственно, добавятся кортежи кортежей и элементов и т. д. Теперь определим

U * = I J Ui (5.4)

i =0

Частный случай кортежей — и-ки, или кортежи с фиксированным числом членов. Они обозначаются {а\ , ..., а п ). Простейший случай и-ок— пары ( а , Ь). Для и-ок обычно о конкатенации не говорят, применяют лишь проекции.

Операция образования множества всех и-ок из совокупности множеств Х\ , • • • , Х п гораздо более элементарна и фундаментальна, чем операция взятия множества всех кортежей. Она носит название декартова (прямого) произведения множеств.

Определение 5.2.2. Прямое произведение п множеств Х\ , ..., Х п — множество Х\ х • • • х Х п всех п- ок xi , ..., х п , таких, что х\ Х\ ,...,

х п Х п .

Стоит указать еще одну условность, отличающую n -ки от кортежей. Очевидно, что [ а , 6, е], [[ а , 6], с ] и [ а , [ Ь , с \] — разные кортежи. Но декартовы произведения А х В х С , ( А х В ) х С , А х ( В х С), как правило, отождествляются. Итак, на прямое произведение множеств смотрят обычно скорее как на алгебраическую операцию, чем как на то, что задано определением 5.2.2 13 .

Есть еще одна условность. Если принимается ассоциативность прямого произведения и одновременно принимается, что элементарной операцией является построение пары ( а , Ъ), то тройка ( а , Ъ , с ) представляется как (( а , 6), с), четверка ( a , b , c , d ) — как ((( a , b ), c ), d ) и т. д. Как говорят, скобки группируются влево14. Если множество R С Х\ х • • • х Х п (т. е. его элементы — n -ки), то на R переносятся операции взятия проекции по любому компоненту г от 1 до и .

  • Да, и математики порою грешат “двоемыслием”: пишется одно, имеется в виду другое. А на самом деле корректное определение декартова произведения в том смысле, как это нужно в математике, было дано лишь на языке теории категорий, появившемся в 60-х гг. нашего века. См. § 5.7.
  • Объяснение, почему такой способ чуть-чуть предпочтительнее, дается в комбинаторной логике.

х

X Xi & Зх \ . . . 3Xj_i ЗЖг +i . . . Зх п | .,

pr j R =

( \ тз v*- 5)

^ Ж 1, , Жг _ 1, Ж , Хг -\- 1, , Ж ^) Л

Таким образом, проекция отношения состоит из всех объектов, стоящих на г-том месте в и-ках из данного отношения.

Важный и выделяемый отдельно случай декартова произведения — когда все его компоненты одинаковы. Прямое произведение и сомножителей U называется декартовой степенью и обозначается Un . U l отождествляется с U , так что и-ка ( ж ), состоящая из одного элемента, отождествляется с самим ж15.

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

Определение 5.2.3. Прямая сумма п множеств Х\ , ..., Х п — множество Х\ ф • • • ф Х п всех пар ( г , х), таких, что х Xi .

Другими словами,

Х \ ф • • • ф Х п = {( г , ж )|1^ г ^ и & ж€ Xi } . (5.6)

Итак, вместе с каждым элементом прямой суммы хранится номер ком­понента, от которого он произошел. Это дает возможность определять отображения прямой суммы путем разбора случаев, какое из Xi соответствует данному компоненту, и применения отображения для соответствующего Xi , и обратно, определять по любому отображению прямой

15 Сам Декарт сформулировал первые примеры произведения, представив плоскость как декартово произведение двух прямых, а пространство — трех. Более общих понятий у него не было, хотя онпредставлял изобретенный им метод координат как средство решать все задачи. Так что скорее имя Декарта надо было бы присвоить не почтенному математическому понятию, а целой науке — искусственному интеллекту, воспринявшему метод Декарта в том отношении, что каждое новое представление данных рекламируется как универсальный метод решать все задачи.

Далее, если задано отображение каждого из Xi , то можно определить отображение прямого произведения, просто применяя частные отображения ко всем компонентам элемента и собирая получившиеся результаты в и-ку И наоборот, если задано отображение, результатами ко­торого служат элементы прямого произведения, то, применив проекции, можно получить и отображений из того же множества определения в каждое из Xi . А имея и таких отображений, можно задать отображение в прямую сумму.

В современном программировании концепция прямого произведения породила структуру данных запись ( record в Паскале.) Прямая сумма породила записи с вариантами. А запись с вариантами порождает соответствующий ей оператор выбора case , разбирающий случаи в со­ответствии с возможными вариантами и, таким образом, соединяющий несколько вариантов действий в один оператор.

Прямые суммы также считаются ассоциативными.

Другие операции над множествами описаны, например, в книге [20].

Напомним еще одно из базовых понятий прикладной математики, практически игнорируемое в теоретической. Это — набор (или муль­тимножество). Набор отличается от множества тем, что в нем могут присутствовать несколько экземпляров одного и того же элемента, а от кортежа тем, что в нем несуществен порядок элементов. Два набора равны, если любой элемент входит в них в одинаковом числе экземпляров. Естественно, что порядок элементов в наборе не имеет значения. Набор обозначается |_ fli , • • • , а>п\, но эта запись не столь общеупотребительна, как для множеств и кортежей. Порою набор будет обозначаться просто а±, ... ,а п , если это явно оговорено в контексте 16 .

Операция объединения распадается для наборов на две: аналог теоретико-множественного объединения, когда число экземпляров элемента в объединенном наборе равно максимуму их числа в исходных наборах, и соединения ф, когда число экземпляров равно сумме чисел в суммы, что же оно делает на каждом из JQ . Если для прямого произведения определены проекции, то для прямой суммы — стандартные вложения inj каждого из ее членов в данную сумму. Если подмножества прямого произведения можно спроектировать по каждому компоненту, то подмножества прямой суммы можно разбить на непересекающееся объединение подмножеств компонент.

Во всяком случае, кортежи и множества так не обозначаются исходных наборах. Очевидно, что соединение X с X уже не есть X . Для наборов

[а, Ь\ = [Ь, а\ , [а, а\ ф [а\ .

И, наконец, промежуточным между множеством, кортежом и набором служит понятие именованного множества. В нем каждый элемент имеет собственное имя, и нет двух элементов с одинаковыми именами.

Упражнения к § 5.2

  • Пусть S — трехместное отношение между студентами, университетами, в которых они учатся, и городами, где эти университеты находятся. Как Вы выразите его проекцию по третьему компоненту?
  • Докажите, что имеется взаимно-однозначное отображение А х В х С на А х ( В х С), сохраняющее pi ^ и переводящее рг 2 ( ж ) в pri ( pr 2 ( x )), арг 3 ( ж ) врг 2 ( рг 2 ( ж )).
  • Сравнив определение декартовой степени и множества всех кортежей, объясните, почему множество всех кортежей получило обозначение U °°.
  • Для кортежей и множеств одноэлементные структуры строго отличаются от самих объектов; для и-ок они отождествляются с объектами. А как для наборов? Обоснуйте свое мнение.
  • Можно ли выразить через наши фундаментальные операции над кортежами операцию Лж .[ ж ], переводящую каждое х в соответствующий одноэлементный кортеж.
  • Часто в математических определениях используют понятие “неупорядоченная пара”. Компоненты неупорядоченной пары не раз­личаются по месту, так что ( а , 6 ) = (6, а). Определите это понятие через одно из имеющихся у нас.
  • Определите именованные множества через множества пар.
  • Верно ли для кортежей а*Ь = Ъ*аЧ Если да, докажите, если нет, приведите опровергающий пример17.

17 Как говорилось во Введении, мы часто ставим задачи в форме “Верно ли?” Такая постановка предполагает не меньшую, чем здесь, строгость и обоснованность ответа: мы математики!

5.2.9. Верно ли для наборов А ф В = В ф А ?

Определите операцию пересечения наборов.

Что могло бы играть роль универса для наборов и как определить дополнение?

Пусть задано отображение А х В в С . Всегда ли из него можно получить пару отображений: из А в С и из В в С ?

Верно ли, что рг-^ ( X U Y ) = p i ^ X U p i ^ Y ?

Верно ли, что pr x ( X ПУ ) = pr x X П рг х У?18

Студент Интеллектуалов определил неупорядоченное произведение и множеств Х\ , ..., Х п как множество всех и-членных наборов, имеющих по одному члену из каждого множества. Что Вы можете сказать по поводу данного определения19?

Аргументируйте, можно ли принимать коммутативность прямого произведения или прямой суммы?

§ 5.3. Отношения

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

Определение 5.3.1. Подмножество R прямого произведения X х Y на­зывается отношением (соответствием) между X и Y . R С X х X называется отношением (соответствием) на X .

Два термина, приведенных в данном определении, соответствуют двум взглядам на множество пар. В случае, когда мы говорим про отношение, нас интересуют взаимосвязи между х X и у ? Y . Если мы говорим про соответствие, то в некотором смысле мы рассматриваем R как описание возможностей преобразовать х в у .

Осторожнее! При ответе на одну из двух последних задач ошибся знаменитый французский математик А. Пуанкаре.

Даже если Вы считаете, что опровергли данное определение или поставили его под серьезное сомнение, приведите условия, при которых оно оказывается правильным.

Рис. 5.5: х — у — целое число

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

Пример 5.3.1. Картинка на рис. 5.5 показывает график отношения с х — у — целое число' на множестве [0,5] .

Определение 5.3.2. Образ элемента х при соответствии R —множество всех таких у , что ( х , у ) R .

Прообраз элемента у при соответствии R — множество всех таких х , что ( х , у ) R . Образ х при соответствии R обычно обозначается через R ( x ).

Образ (прообраз) множества Х\ С X ( Y \ С Y ) — объединение образов (прообразов) его элементов. Образ X при соответствии R также обычно обозначается через R ( X ) . Как говорят, конкретный смысл операции здесь устанавливается по контексту20.

20 Ситуация, когда один и тот же знак операции применяется к выражениям разных типов и по существу означает разные вещи, на самом деле обычна в математике. Например, знак + применяется для сложения и натуральных, и целых, и рациональных чисел, и действительных, и комплексных, и матриц, и еще математик знает чего. В программировании дела обстоят точно так же. Такое “сверхиспользование” символа называется перегрузкой . С примером, как корректно решать проблемы перегрузки, мы познакомим­ся далее. Но не надейтесь, что все, использующие перегрузку, заботятся о ее корректности. Чаще всего дело ограничивается благими пожеланиями, даже если об этой пробле­ме задумываются (например, в языке Ada , созданном по заказу Министерства обороны США, по поводу перегрузки было высказано требование, чтобы алгебраические свой­ства операций, обозначающихся одним и тем же значком, совпадали и на одинаковых аргументах эти операции давали одинаковые результаты, но никаких средств проверки этого условия дано не было).

R определено на х, если образ х непуст. R не определено на х, если образ х пуст.

Рассмотрим операции над отношениями. Конечно же, поскольку отношения являются множествами, над ними можно производить обычные булевы операции, поскольку они — подмножества прямого произведения, можно находить их проекции. Но есть и специфические для бинарных отношений операции.

Первая из них — нахождение обратного отношения. Она сопоста­вляет отношению R между А и В отношение R ~ l (часто обозначаемое также R ) между В и А, определяемое следующим образом:

R ~ = {( г /, х )\ х А & у ? В & ( ж , у ) ? R }. (5.7)

Например, для изображенного на рис. 5.5 отношения обратным является оно само, для отношения < — отношение > и т. п.

Интересны два подкласса отношений между X и X (обычно называемых отношениями на X ).

Определение 5.3.3. Симметричным называется такое R , что R ~ l = R .

Антисимметричным — такое R , что R ~ l П R = 0 .

Понятия симметричности и антисимметричности выражаются наязы- ке логики:

УхУу (( х , у ) R =>¦ ( у , х ) R ),

VxVy((x,y)eR^(y,x) ? R).

Важным частными отношением на X является диагональ, или единичное соответствие, или тождественное отображение21:

idx = {( ж , ж )| ж € X } = {( х , у )\ х = г /}.

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

Определение 5.3.4. Рефлексивным называется отношение, содержащее диагональ. Антирефлексивным называется отношение, не пересекающееся с диагональю.

21 Обилие имен у математического объекта, как правило, означает, что он полезен для самых разных целей.

Понятия рефлексивности и антирефлексивности также выразимы на логическом языке:

\/ ж ( ж , ж ) € R ,

\/ ж ( ж , х ) (? R .

Определение 5.3.5. Композиция отношений RcXxY , ScYxZ отношение R о S С X х Z , такое, что

RoS = {( х , z )\ x X & z Z & Зг /( г / G 7& ( ж , г /) € i ? & ( г /, - г ) € 5 1 )}-

Итак, при композиции мы связываем жиг посредством такого у, что у соответствует х согласно R и z соответствует у согласно S . Очевидно, что если отношения имеют вид

R = \( х , у )\ х X & у ? Y & г / = f ( ж )}, (58)

Ь = \{ х , у )\ х € У & г / € ii & г / = д { х )\,

то их композиция представляется как

R о S = {( ж , у ) \ x ^ XSzy ^ ZSzy = g ( f ( x ))}. (5.9)

Приведем некоторые важные алгебраические свойства композиции отношений.

R о [ S о Т ) = ( R о S ) о Т (ассоциативность) (5.10)

R о idy = R idx ° R = R id — единица (5.11)

( R о S ) ~ l = ( S ~ l о R ~ l ) обратный к композиции (5.12)

Но вот R о R ~ l = idx выполнено отнюдь не всегда.

И последние из “джентльменского набора” классов отношений — транзитивные и антитранзитивные отношения. Чисто формально легко написать определяющие их логические условия, но и в данном случае лучше связать эти понятия с операцией композиции над отношениями наХ.

Определение 5.3.6. Квадрат отношения R С X х X — отношение R =

R о R . Соответственно определяется Rn :

R n = R о о R . n раз

Отношение называется транзитивным, если R 2 С R . Отношение антитранзитивно, если R 2 П R = 0. Понятия транзитивности и анти­транзитивности имеют выражение на логическом языке. Мы приведем его для транзитивности, а для антитранзитивности выразите сами.

УхУуУг (( х , у ) ? R $ ? ( y , z ) ? R => ( х , z ) ? R ). (5.13)

С транзитивностью связано важное понятие — транзитивное замыка­ние отношения23. Дадим два определения транзитивного замыкания и докажем их эквивалентность.

Определение 5.3.7.

1. X — наименьшее множество, обладающее свойством А, если вы
полнено А ( Х ) и

VY ( A ( Y ) => Y С . X ).

2. Транзитивное замыкание отношения R С X х X — наименьшее отношение R °° С X х X , такое, что R °° содержит все элементы из R и R °° транзитивно.

22 Не путайте данную степень с декартовой! Забавнее всего, что поскольку отношения такжемножества, можно рассматривать и декартову степень R , но в связи с тем, что в чистой математике она практически никогда не нужна, математики допускают т. н. “вольность речи,” а вот безумные программисты иногда вынуждены использовать структуры данных, соответствующие декартову произведению отношений.

23 Схема, примененная при определении транзитивного замыкания, — на самом деле общая схема, используемая при превращении структур, не обладающих замкнутостью относительно некоторой операции, в структуры, замкнутые относительно нее. Так, например, двоично-рациональные числа (числа вида 2 n m ) получаются замыканием целых чисел относительно операции деления на 2; комплексные числа — замыканием действительных чисел относительно операции нахождения корней любого алгебраического уравнения вида

a n x n + a n -1 x n -1 ••• + a 0 = 0.

3. Транзитивное замыкание отношения R С X х X

оо

В°° =[ JR n

71 =1

4. Транзитивное замыкание отношения R С X х X — пересечение всех транзитивных отношений, включающих R :

(1 X (5.14)

RCX , X транзитивно

Докажем, что три определения R 00 эквивалентны. В самом деле, U ^ Li Rn содержит R и транзитивно, поскольку если ( х , у ) Rn , ( у , z ) Rm , то ( x , z ) Rn + m . Любое транзитивное отношение, содержащее R , должно содержать и все Rn (это легко доказывается по индукции). Значит, U ^ Li Rn — наименьшее транзитивное отношение, содержащее R , что и требовалось доказать. И, наконец, пересечение семейства транзитивных отношений само транзитивно, а семейство из (5.14) включает, в частности, и минимальное из транзитивных расширений R 24.

Если отношение транзитивно и антирефлексивно, оно называется отношением (частичного) порядка и обозначается символом < либо похожими на него (например, >-). Если отношение транзитивно и рефлексивно, то оно называется отношением предпорядка и обозначается символом, похожим на ^ (например, )==). Частичный порядок называется линейным, если выполнено условие

УхУу ( х >- у У х = у У у >- х ).

24 Обратите внимание!! В третьем пункте мы определили транзитивное замыкание R через класс, содержащий само это транзитивное замыкание. Более того, если из этого класса транзитивное замыкание выбросить, порою пересечение оставшихся множеств уже будет побольше. Так что в последнем случае R ? определялось само через себя! Такая ситуация издревле рассматривалась как логическая ошибка “Порочный круг в определении”. Тем не менее в математике подобные определения широко используются; мы, правда, их стараемся избегать. Практически всегда их можно заменить более конструктивными определениями типа использованных во втором пункте, но здесь порою натуральных чисел не хватает для нумерации шагов построения.

Множество с заданным на нем отношением частичного порядка называется частично упорядоченным множеством (чум) 25 . Множество с отношением предпорядка — пум. Множество с отношением линейного порядка — линейно упорядоченное множество (лум).

Предпорядок называется строгим предпорядком (или нестрогим порядком), если выполнено

\/ х \/ у ( х ) ру & у ) рх ^ х = у ).

Пример 5.3.2. Отношение «Быть начальником» является отношением частичного порядка на множестве чиновников26. Отношение «Быть старше по званию» — отношение частичного порядка на множестве военных. Отношение «Не быть старше по званию» — отношение предпорядка на этом же множестве2 1 ' .

Для изображения частично-упорядоченных множеств имеется графический аппарат, известный под названием диаграммы Гессе. Пример диаграммы Гессе см. на рис. 5.6. На этой диаграмме, как видите, изображаются не все пары из отношения порядка. Элемент у больше элемента х , если есть путь, составленный из идущих вверх дуг диаграммы, ведущий из ж в у . Поэтому, в частности, нет нужды проводить дугу, например, от 0 к 1.

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

Определение 5.3.8. Элемент х® чума X называется наибольшим, если

Уу ( у X & у ф х 0 => х 0 >- у ).

Таким образом, он больше всех остальных. Максимальный элемент не меньше никакого другого.

У у ( у X => • у >~ Хо ).

  • Симпатичное русское сокращение чум введено новосибирской школой. Московская математическая школа его не признает, видимо, потому, что в Европе ни чумов, ни чумы нет.
  • Хотя фактически частенько чиновники занимают позицию “Начальник моего начальника — не мой начальник” и, соответственно, приказания Президента не исполняются чаще, чем повеления непосредственного шефа, но формально такое поведение противоречит законам и инструкциям.
  • То, что здесь старшинство “перепутано” — младшие по званию считаются больше старших, — частный случай того математического факта, что R — отношение порядка ттт ВГ1 — отношение порядка. Этот порядок называется обратным к R.

Рис. 5.6: Диаграммы Гессе двух важных пятиэлементных множеств

Соответственно определяются минимальный и наименьший элементы. Элемент а называется верхней гранью множества Y С X (обозначается sup Y либо ( J Y ), если

Ух ( х ? Y =^ x -< a \/ x = a )&

Ух ( х X & х -< a => • Зу ( у Y & х -< у & ( г / -< a V г / = а ))).

Соответственно определяется нижняя грань ( inf У , р|У) . Верхняя (ниж­няя) грань двух элементов обозначается a U b (а П Ь). Чум, в котором у каждых двух элементов имеется верхняя и нижняя грань, существуют наибольший и наименьший элементы, называется структура. Структура называется полной, если верхние и нижние грани существуют у любого подмножества элементов.

Определение 5.3.9. Пусть X — чум. Тогда на множестве Х°° кортежей элементов из X можно ввести отношение частичного порядка, называемое лексикографическим упорядочением.

[ Хо , ¦ ¦ ¦ , Х п ] >- [ г /0; • • • ) У k ] = 3 i ( Vj '( j < i => Xj = yj ) $? Xi >- Уг ).

Например, лексикографическое упорядочение кортежей букв используется при построении словарей.

Упражнения к § 5.3

5.3.1. В книге Н. Бурбаки “Теория множеств”, в которой понятие пары наряду с понятием множества и принадлежности рассматривается как исходное, для пар задана следующая аксиома (переписанная в наших обозначениях):

УхУуУиУи (( х , у ) = ( и , и ) => • х = и & у = и ).

Почему не задана как аксиома и обратная импликация?

Покажите, что для выполнения аксиомы Н. Бурбаки достаточно определить пару ( ж , у ) как двухэлементное множество { ж , { х , у }}.

Объясните, можно ли определять пару, скажем, так: ( х , у ) = {{ х , 0}, { у , 1}}.

Почему в формулах (5.8), (5.9) повсюду используются одни и те же переменные х , у , хотя множеств целых три: X , Y , Z 1

Проверьте следующие тождества:

( A U В ) х С = ( А х С ) U ( В х С )

( А П - В ) х С = ( А х С ) П ( В х С )

Если некоторые из них не всегда выполнены, в какую из сторон имеет место вложение?

5.3.4. Верно ли, что

(R\ U R2) о S = (R\ о S) U (i?2 ° S)

(R\ П Ri) о S = (R\ о S) П (i?2 ° 5 1 )

Когда ( ж , ж ) € RoR ~ l l Выведите из Вашего условия, когда idx С R о R 7

Каковы обратные отношения к следующим отношениям:

  • Быть отцом.
  • Быть мужем.
  • Быть начальником.

у = а ¦ х.

  • Быть братом.
  • Быть братом или сестрой.
  • Любить.
  • Ненавидеть.
  • Воевать.

5.3.7. Построить композиции следующих отношений (‘Быть A ' означает ‘ x является A для y '. Математические формулы рассматриваются на множестве действительных чисел):

  • а) Быть родителем Быть отцом
  • б) Быть родителем Быть сестрой
  • в) Быть соседом Быть другом
  • г) Быть другом Быть соседом
  • д) Быть мужем Быть отцом
  • е ) x>y y>x
  • ж ) x2 =y y2 =x
  • з ) x=e y x=sin y

Имеются ли отношения, которые одновременно и симметричны, и антисимметричны?

На каком множестве любое отношение симметрично?

Какую ошибку содержат эти диаграммы и какую из них можно упростить после исправления ошибки любым способом?

5.3.14. Студент Лыцаренко защитил студентку Примерную, заявив, что это — диаграммы для предупорядоченных множеств. Насколько обоснована его защита?

5.3.15. Определение 5.3.9 содержит неточность. Найдите и исправьте5.3.15. Определение 5.3.9 содержит неточность. Найдите и исправьте
  • А есть ли множество, на котором любое отношение рефлексивно?
  • Отношениепорядка, длякотороговыполнено R?R = R , называют плотным . Почему? Переведите данное условие на логический язык.
  • Докажите, что для любого отношения предпорядка R ? R = R .
  • Студентка Примерная нарисовала две красивых диаграммы Гессе:
  • Не ошибся лиавтор в определении максимального элемента, опустив условие y = x 0 ? А как для предупорядоченных множеств?
  • Переведите на формальный язык следующее определение:

Отношение называется согласованным , если два объекта , отно­сящиеся к одному и тому же третьему объекту , относятся между собой .

Не могли бы Вы переформулировать данное предложение на содержательном языке так, чтобы оно, не изменив математического смысла, стало бы легче понимаемым?

§ 5.4. Функции

Уже на картинке 5.5 хорошо видно, почему отношения называют соответствиями. Порою так и напрашивается интерпретация их как частичных многозначных отображений28. Зато когда говорят о функциях, то используют содержательное уточнение, которое всегда работает в математике.

Функция — правило, позволяющее по каждому элементу области определения однозначно получить элемент области значений.

Итак, каждая функция имеет область определения Dom / , над которой она работает, и область значений Val / , в которой должны содержаться полученные результаты. Надо заметить, что отнюдь не всегда функция может выдавать в качестве результата все элементы области значений. Ниже мы разберем это подробнее.

Соответствие представляет график полноправной функции только в том случае, если каждому х из X соответствует единственное у из Y . Например, таково соответствие

{( ж , у ) | ж ? Ж & г /? Ж & ж = г / + 1}.

28 Не обольщайтесь этим. Неопределенность и многозначность — глубокие и коварные вещи. Отнюдь не всегда простейшее математическое уточнение понятия частичной многозначной функции как отношения работает. Так что если кто-то говорит о частичных многозначных функциях, уточняйте, что он имеет в виду.

Поэтому соответствия, для которых Ух X 3 1 у Y ( x , у ) € Л , называют функциональными. Часто функциональные соответствия отожде­ствляются с функциями, но такое отождествление не всегда правомерно даже в классической математике (в частности, в областях, базирую­щихся на теории категорий). Другое дело, что любое соответствие формы R = {( х , у )\ у = f ( x )} является функциональным, и в математике очень стараются, чтобы по любому функциональному соответствию можно было определить функцию 29 . Если же мы интересуемся вычислимостью либо определимостью, то на первый план решительно вы­ходит первая составляющая понятия функции — наличие правила.

Определение 5.4.1. Функция f представляется в теории множеств как тройка

( X , Y , R ),

где R С X х Y — функциональное соответствие. X называется областью определения f , Y — ее областью значений. Область определения обозначается Dom / , а область значений — Val / .

Прошу обратить внимание на различие области значений и образа функции. / ( X ) С Y , но равенства обычно нет.

В последнее время композиция функций в математике определяется в соответствии с композицией отношений:

( fog )( x )= g ( f ( x )),

а чтобы при композиции функции не переставлялись, и применение функций во многих местах (в частности, в работах по алгебре) стали писать “наоборот” 30 : xf .

Определение 5.4.2. (Важные классы функций)

1. Инъекция (однозначное отображение) — такая функция / , что

Ух ? lV )/ € X ( f ( x ) = f ( y ) - Ф 4 » х = у ).

Иногда ради этого даже логику изменяют; в главе, посвященной конструктивным логикам, мы с этим немного разберемся.

Неразбериха с порядком функций при композиции длилась несколько десятилетий. “Прямая” школа считала в точности наоборот: ( f ? g )( x ) = f ( g ( x )), и до сих пор во многих работах по математическому анализу и дифференциальным уравнениям придерживаются такого определения. В принципе, здесь что в лоб, что по лбу, но не запутывайтесь!

2. Сюръекция (отображение на) —

Уу Y Зх X f ( x ) = у .

3. Биекция (взаимно-однозначное отображение) — функция, у которой существует обратная, т. е. функция, графиком которой служит отношение, обратное к графику / .

Таким образом, для сюръекций / ( Dom /) = Val /. Для инъекций множество f ~ l {у) всегда не более чем одноэлементно (здесь f ~ l — от­ношение, обратное к /, оно не обязательно является функцией, и поэто­му использовано обозначение образа, принятое для соответствий). Еще две важных характеризации инъекций и сюръекций на языке компози­ций заслуживают отдельного рассмотрения и доказательства.

Предложение 5.4.1. (Композиции с инъекциями и сюръекциями)

Композиция двух инъекций — инъекция.

Композиция двух сюръекций — сюръекция.

f : X —>• Y инъекция тогда и только тогда, когда для любых двух отображений д\, § 2 из Z в X

9 i ° / = 92 ° / "& 9 i = 92-

4. f : X —> Y сюръекция тогда и только тогда, когда для любых двух отображений д\, § 2 из Y в Z

f ° 9 i = / ° 92 ^ 9 i = 92 ¦

5. / : X —> Y инъекция тогда и только тогда, когда существует функция g : Y —>• X (называемая накрытием, ассоциированным с f ), такая, что

Ух ( х X => g ( f ( x )) = х ).

(Другими словами, f о g = idx -^

6. / : X —>¦ Y сюръекция тогда и только тогда, когда существует функция g : Y —>¦ X (называемая ретракцией, ассоциированной с f ), такая, что

Ух ( х G 7=^ f ( g ( x )) = х ).

(Другими словами, g о f = idy .)

Доказательство. Пункты 1, 2 и 4 остаются в качестве упражнений читателю.

Доказательство пункта 3. Пусть / — инъекция из X в Y . Пусть Й ° / = № ° /¦ Тогда для произвольного х f ( gi ( x )) = / ( дг ( ж ))- Но по инъективности / отсюда следует д\{х) = 5 г ( ж ). Поскольку вывод сделан для произвольного х, д\ = дч, что и требовалось установить. Теперь обратно. Пусть для всех д\, дч, таких, что g \ of = g 2 ° f , выполнено равенство д± = д2. Возьмем произвольные х\, Х2- Пусть f { x \) = /(жг)- Теперь возьмем одноэлементное множество Z = { zq } и построим два отображения из Z в X , такие, что gi ( zo ) = х\, g 2{ zo ) = Ж2- Поскольку f ( gi ( г 0 )) = f ( g 2( zo )), а других значений аргумента нет, g \ of = g 2 of . Значит, в частности, gi ( zo ) = 52 (-^ о ), и х\ = %2- Прошу Вас обратить внимание, что в этом доказательстве нет рассуждений от противного. Поэтому данное свойство инъекций весьма устойчиво при смене логики.

Доказательство пункта 5. Пусть у / есть ассоциированное с ним накрытие д . Покажем, что тогда / — инъекция. В самом деле, возьмем произвольные х\ , %2, такие, что f { x \) = / ( жг ). Тогда g { f { x \)) = Х\ = g ( f ( x 2)) = Х 2 - Теперь в обратную сторону. Пусть / — инъекция. По­строим накрытие д следующим образом: если у ? / ( Dom /) , то имеется единственное х , такое, что f ( x ) = у . Оно и будет значением функции д . Если же у ^ / ( Dom /), то такого х вообще нет, и можно задать значение д равным произвольно выбранному элементу Жо31.

Доказательство пункта 6. Поскольку / — сюръекция, для каждого у Val / множество R ~ l {у) непусто. Сопоставим каждому у какой- либо из элементов R ~ l (у) . Полученная функция и будет искомой ретракцией 32 .

Обратная импликация очевидна, поскольку, чтобы вернуться к аргументу, нужно его порою выдавать в качестве значения, что и является определением сюръекции.

Предложение 5.4.2. Функция является биекцией тогда и только тогда, когда она является и инъекцией, и сюръекцией.

Здесь есть тонкость! Прямое и обратное рассуждения принципиально различаются по логическому статусу. Если прямое рассуждение весьма устойчиво, то обратное содержит внешне безобидный шаг, требующий анализа бесконечно большого объема информации: проверка, принадлежит ли у /( Dom /). Поэтому вторая часть данной эквивалентности легко рушится при замене логики и даже просто при отходе от теории множеств в качестве основания математики.

А здесь ситуация еще хуже. Подумайте, а как мы выберем по элементу из каждого ВГ1 (у)? То, что такой выбор можно осуществить, на самом деле эквивалентно одной из аксиом современной теории множеств, причем аксиоме, чаще всего берущейся под сомнение: аксиоме выбора. Она гласит, что по любому всюду определенному соответствию можно построить вложенное в него функциональное. Из нее следуют многие приятные теоремы традиционной математики и некоторые неприятные, например, теорема Куратовского о том, что яблоко можно разрезать на четыре части таким образом, что из них можно сложить два таких же яблока. В науке всегда так: сильный принцип, полезный в одних отношениях, вреден и сбивает с толку в других областях. Ни один полезный научный результат не универсален, потому что наука — отрасль человеческого знания, а человек несовершенен, и поэтому его знания также с необходимостью несо­вершенны. Так что если кто-то уверяет Вас, что его метод всегда хорош, то это либо жулик, либо человек, слишком увлекшийся своей идеей, настолько, что она уже нахо­дится у него на стадии перехода из ценной в сверхценную (‘ценная' здесь — обычная неформальная оценка, ‘сверхценная' —термин из психиатрии, применяемый, когда человек зацикливается на одной идее и не видит больше ничего вокруг). Надо сказать, что нынешняя система организации науки, внедрившая в нее рекламу, которая всегда была противопоказана науке, поощряет такое жульничество, будьте осторожнее и осмотрительнее!

Доказательство. Пусть отношение R — график функции /. Рассмотрим отношение Д -1. Поскольку / — сюръекция, для каждого хёУ существует у ? X , ( х , у ) R ~ l . Поскольку / — инъекция, из {х,у\) R ~ l , ( ж , 1/2) €Е R ~ l следует у\ = у^. Таким образом, R ~ l — функциональное отношение.

Обратная функция, если она существует, обозначается / .

Предложение 5.4.3. / о f ~ l = Id Dom / , f '1 о f = Id Va i / .

Доказательство оставляется в качестве упражнения. Определение 5.4.3. Множествах иУ на з ыва ю тсяравномощными, если имеется биекция X на У (обозначается X = У). Мощность множества X не больше мощности множества У ( X ^ У), если имеется инъекция из X в У. Множество У покрывает множество X ( X !>= У), если имеется сюръекция X на У.

Теорема 5.2. (Кантор, Шредер, Бернштейн) Если X ^ У и У ^ X , то X и У равномощны.

Доказательство. Пусть X ^ У иУ ^ X . Тогда имеются две инъекции: / : X —> У, g : У —> X . Если хоть одна из них является сюръекцией, то эквивалентность установлена. Если ни одна из них не является сюръекцией, то множество X \ g (У) непусто. Возьмем произвольный элемент Жо этого множества. Возьмем отношение

R = {( ж 1, жг ) | х \ X & %2 ? X & Х 2 = g ( f ( xi ))} .

Рассмотрим его транзитивное замыкание Д°°. Образ хо при этом замы­кании либо конечен, либо бесконечен. Рассмотрим эти два случая.

Пусть образ R °° (хо) конечен. Тогда он состоит из конечного мно­жества элементов

Л ... Л . Л

хо , х \ = g { j { xo )), Х 2 = g ( j ( xi )), ..., х п = х п -\.

g ( f ( x n )) = Xi для некоторого г < п. Но поскольку fog — инъекция, г = 0. В самом деле, если г ф 0, то г = j + 1, но тогда Xj + i = g ( f ( xj )) = g ( f ( x n )), где Xj ф х п , чего не может быть. Но по предположению х® X \ g ( У), и соответственно, нет такого у, что xq = g ( y ).

Значит, остается лишь случай, когда образ жо бесконечен. Все элементы этого образа, очевидно, лежат в д ( Y ). Докажем теперь, что образы разных х <Е X \ д ( Y ) при соответствии R °° не пересекаются. Рассуждение аналогично тому, с помощью которого мы опровергали конечность R °° (хо). Возьмем произвольные х,у X \ д ( Y ). Если их образы пересекаются, то некоторые из х п равны некоторым из у т . Возьмем наименьшее такое и. Если оно не 0, то х п -\ ф y m - i , но 9( f ( xn - i )) = g ( f ( y m - i )).

Теперь построим, пользуясь выше установленным разбиением X , биекцию Y на X . Для этого видоизменим функцию д. Положим

( \ I 9( у ) ^ х (9( у ) ? -^ °° ( х ) к х (? X \ д ( Y ))

x n - i х Зп ( х X \ g ( Y ) к д ( у ) В°° ( ж ) к д ( у ) = х п )

Итак, все последовательности х п сдвигаются на один элемент, и в ре
зультате д\, оставаясь инъекцией, становится и сюръекцией. ?

Понятие равномощности дает возможность классифицировать множества по отобразимости друг на друга33.

Прежде всего конечные множества равномощны тогда и только то­гда, когда у них одинаковое количество элементов. Это можно было бы “доказать,” но уже с конца XIX века известно, что на самом деле лишь понятие равномощности дает возможность корректно определить конечное множество в теории множеств.

Определение 5.4.4. Множество X называется конечным, если оно рав- номощно множеству

{ х | х € N к х < п \

для некоторого п € N .

Количество элементов в конечном множестве будем обозначать N X .

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

Соответственно, бесконечному множеству чаще всего дают в ма­тематике негативное определение: бесконечное множество — множе­ство, не являющееся конечным. Нетривиальное определение бесконечного множества дал Рассел:

33 Обычно в книгах по математике пишут, что по числу элементов. Это верно лишь для конечных множеств. Для бесконечных, скорее, это классификация по сложности представления. Далее мы познакомимся подробнее с тем, почему общепринятые представления не верны и в данном случае.

Определение 5.4.5. Бесконечное множество — такое множество X , что существует взаимно-однозначное отображение X на какое-либо подмножество Y С X Sz Y ф X .

Таким образом, бесконечное множество равномощно своему подмножеству 34 . Безусловно, математик обязан обосновать, что любое множество либо конечно, либо бесконечно. Самый простой и одновременно выявляющий некоторые скрытые трудности путь к этому — через конкретный вид бесконечных множеств: счетные множества.

Определение 5.4.6. Счетное множество — множество, равномощное множеству натуральных чисел N .

Предложение 5.4.4. Если множество содержит счетное подмножество, то оно бесконечно.

Доказательство. Пусть имеется биекция / множества натуральных чи
сел на У С X . Тогда построим следующее взаимно однозначное отобра
жение ip X на X \ /(0). Если х <? Y , то положим tp ( x ) = х . Если х Y ,
х ф
/(0), то существует такое п N , что х = f ( n + 1). Тогда положи м
Ф ) = Нп ). ?

Предложение 5.4.5. Всякое бесконечное множество содержит счетное подмножество.

Доказательство. Пусть имеется биекция / множества X на Y С X , Y ф X . Тогда возьмем какое-либо хо X \ Y . f ( xo ) ф Жо , обозначим его х\ . Далее, подобно тому, как делалось в теореме Кантора-Шредера- Бернштейна, положим х п + \ = f ( x n ), и так же, как в упомянутой теореме, можно показать, что все ж, различны. Множество

{ xi | г N }

и есть искомое счетное подмножество X . ?

34 Видимо, первым обратил на это внимание кардинал Николай Кузанский , выдающийся схоласт XV века. Он применил это для обоснования того, что триединство Бога не является логическим противоречием, поскольку Бог — бесконечная сущность (одно из очень немногих корректных применений математики в богословии). Галилей, видимо, независимо, заметил, что множество натуральных чисел взаимно-однозначно отображается, в частности, на множество четных чисел, и опубликовал это в математическом тексте. Отсюда Галилей сделал вывод, что нельзя говорить о множестве всех натуральных чисел, поскольку иначе нарушается фундаментальная аксиома Евклида: «Целое больше части». В дальнейшем математики просто отказались от этой аксиомы, заме­тив, что ее нельзя выразить на математическом языке.

Предложение 5.4.6. Если множество не является конечным, то оно содержит счетное подмножество.

Доказательство. Рассмотрим следующее отношение между конечными подмножествами X :

? = {( Y , Z ) | Y С X & Z С X & Y С Z & N Y + 1 = N Z } .

Итак, данное отношение связывает между собою конечные множества, второе из которых содержит один дополнительный элемент вдобавок к элементам первого. Очевидно, что ? не определено на Y тогда и только тогда, когда Y = X . Но поскольку по условию X не является конечным, ? всегда определено.

Поэтому начнем с некоторого одноэлементного множества Vb С X , и для каждого Vi выберем35 VJ + i как произвольный элемент ? { Vj ). Очевидно, что Vi С Vj при г < J , и объединение возрастающей последовательности

V = I I V ,

и есть искомое счетное подмножество X . ?

Итак, мы показали, что, действительно, каждое множество либо конечно, либо бесконечно и что счетные множества являются в некотором смысле минимальными среди бесконечных. Но счетных множеств не так уж мало.

Пример 5.4.1. Множество рациональных чисел счетно. В самом деле, любое рациональное число представимо несократимой дробью п/тп, где m > 0 . Дробей с суммой числителя и знаменателя к — конечное число, поэтому их можно расположить в порядке возрастания п, за ними все дроби с суммой числителя и знаменателя п + 1 и так далее.

На самом деле мы дали общий способ, как показать счетность любого множества, элементы которого представимы конечной последовательностью из конечного числа символов.

35 Здесь опять применяется аксиома выбора; но на самом деле здесь используется более слабая ее форма, вызывающая меньше сомнений и, самое главное, совместимая с аксиомой детерминированности, также естественной, но противоречащей аксиоме вы­бора. Тех, кто интересуется данным вопросом, можно отослать, например, к книге [17]. См. также § 10.5.1.

Мощность множества натуральных чисел обычно обозначается ? 0 ( ? — первая буква еврейского алфавита, произносящаяся ‘алеф'). Простейший пример бесконечного множества, не являющегося счетным, следующий:

Теорема 5.3. Множество действительных чисел несчетно.

Доказательство. Пусть имеется некоторое отображение a n множества N в действительные числа из отрезка [0,1] (последовательность). По­строим по ней представленное в троичной системе число b , не входящее в данную последовательность и, более того, такое, что от данного a n оно отличается уже первыми n + 1 членами троичного разложения. a 0 не принадлежит по крайней мере одному из трех отрезков [0, 1/3], [1/3, 2/3], [2/3, 1]. Выберем первую после запятой троичную цифру так, чтобы b не попало в тот же отрезок, что и a 0 . Далее, пусть, например, первая цифра это 1. Тогда a 1 не принадлежит по крайней мере одному из трех отрезков (а возможно, и ни одному из них, если оно не попадает в [1/3, 2/3]) [1/3, 4/9], [4/9, 5/9], [5/9, 2/3]. Выберем вторую троичную цифру таким образом, чтобы a 1 разошлось с b . Так же продолжаем и далее. Итак, никакая последовательность не может перечислить всех действительных чисел.

Обратим Ваше внимание на одну тонкость в приведенном доказательстве. Может показаться, что мы брали троичное, а не двоичное разложение с той целью, чтобы избавиться от хлопот с числом 1/2. Конечно, часто математики поступают именно так, делая гораздо труднее реализуемый алгоритм лишь потому, чтобы не рассматривать отдель­но несколько исключительных случаев. Но здесь причина другая. Мы постарались, чтобы данное доказательство было абсолютным , сохра­няющим силу не только в традиционной математике, но и в ее извест­ных модификациях. Мы, в частности, нигде не предполагали, что дей­ствительные числа точно известны, и проследили, чтобы для каждого использованного в рассуждении отношения между ними можно было указать, с какой точностью его достаточно проверить.

Про множества,равномощные множеству действительных чисел,говорят, что они имеют мощность континуума, эта мощность обозначается c .

Пример 5.4.2. Любоеконечномерноепространство Rn имеетмощность континуума .

В самом деле, воспользуемся определением действительных чисел через двоичные разложения и построим инъекцию из Ж п в Ж следующим образом (( x ) i в данной формуле — г-тый знак числа х):

(ip((xi, . . . , X n )))n*i+k = (Xk+l)n (5-15)

Итак, двоичные знаки получившегося числа соединяют двоичные знаки всех аргументов, и, очевидно, каждое из X i однозначно восстанавливается по значению ip (( x \,..., х п )). Инъекция Ж в Ш. п очевидна.

теореме Кантора-Шредера-Бернштейна, М и К" равномощны.

Вопрос, существуют ли множества мощности, промежуточной между счетной и континуумом, не разрешим в принятой аксиоматике теории множеств. Предположение, что таких множеств нет, носит название континуум-гипотезы.

Теорема 5.4. (Теорема Кантора) Множество всех подмножеств множества X , обозначаемое ф X , имеет мощность большую, чем X .

Доказательство. Очевидно, что имеется инъекция X в ф X . Докажем, что обратной инъекции нет.

Приведем предположение, что / — такая инъекция, к абсурду. Для этого построим множество

К = { х | х X & х (? f ~ ( х ) .
Тогда / ( К ) eK ^f ( K ) ? К . ?

Из теоремы Кантора следует парадокс Кантора, показывающий, что множества всех множеств не существует.

(Парадокс Кантора) Множество всех множеств U содер­жит любое другое множество как подмножество, и значит, если V — некоторое множество, то имеется инъекция V в U . Но тогда имеется и инъекция ф U в U , что противоречит теореме Кантора.

Таким образом, не всякое выразимое на языке логики свойство множеств определяет множество (на самом деле проще всего здесь пример из парадокса Рассела: несуществование { х | х <? х}). В современной математике принято совокупности множеств и других математических объектов, удовлетворяющих данному свойству, называть классами . Классы не могут быть элементами других классов, и тем более множеств. Таким образом, классы рассматриваются скорее как сокращения, а не как объекты. Доказано, что добавление классов к обычной теории множеств ничего существенно не меняет.

Есть интересный критерий, позволяющий свести вопрос, является ли данная совокупность множеством, к этому же вопросу для уже известных множеств. Область значений любой функции, определенной на множестве, сама является множеством. Если избавиться от функции, то критерий примет следующий вид:

Аксиома подстановки . Если X — множество, и Ух ( х X => 31 уА ( х , у ), то

{ у | Зх ( х gX & А ( х , г /))}

также множество.

Контрапозицией аксиомы подстановки получаем, что, если X — класс, ip — инъективное отображение X в Y , то Y — также класс.

Данный критерий называется аксиомой по той причине, что, отчаявшись найти внешние критерии того, какие формулы могут определять множество, математики начала XX века решили просто постулировать возможность построения тех множеств, которые широко вошли в мате­матическую практику и не приводят к известным парадоксам. Так возникла аксиоматическая теория множеств. В настоящее время абсолют­ным большинством математиков принята формальная система теории множеств ZF (Цермело-Френкеля). В ней постулируются следующие аксиомы (помимо аксиомы подстановки)37:

1. Пустое множество :

ЭХ Ух х (? X

2. Двухэлементное множество :

Ух , у 3 Xyz ( z ? X <3> z = xVz = y )

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

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

3. Объединение множества множеств :

УХ 3 YVy ( y Y -ФФ- Зх(х ?!&)/€ ж )) ( это множество обозначается просто | J X )

4. Множество всех подмножеств :

УХ 3 YyZ ( Z ? Y - ФФ - \/ ж ( ж G 2=> x € X ))

5. Аксиома бесконечности :

Существует множество, у которого есть инъекция самого в себя.

/ : X > X &

ЗХ 3 f I Ух , у ( х GXfe (/ ? l & f ( x ) = f ( y ) =^ х = J /) & Зг /( г / GX & \/ ж ( ж G J 4> /( ж ) т ^ у ))

6. Аксиома выбора

yY ( Y ? X => Зг / г / ? У ) => •

УХ

3/(/ : X — > • X & Vy ( y G J ^> /(5^) € 5^)

7. Аксиома объемности :

VX , y ( Vz ( z ( z X <^$ z ( z Y ) ^- X = Y ) Если множества имеют одни и те же элементы, они равны.

8. Аксиома регулярности :

УХ Зх ( х ? X & Зу ( у ? ж & г / € X ))

Суть ее в том, чтобы запретить ситуации вида х ? ж. Эта аксиома служит примером технических улучшений, необходимых в каждой новой теории для ее логического замыкания.

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

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

Определение 5.4.7. Конечной последовательностью называется отображение множества { i \ i N $ z i ^ 1 $ z i ^ к}. к — ее длина. Бесконечной последовательностью называется отображение множества N либо N \ 0 .

Конечная последовательность Ь : { i | i ? N & i ^ l & i ^ fc } — > X явля­ется началом конечной последовательности

a : {i|i ? N&i^l&i^/} — > X,

если I ^ к иУг (1 ^ г & г ^ к => a(i) = b(i)).

Конечная последовательность Ь : { i | i ? N & i ^ l & i ^ fc } — > X является началом бесконечной последовательности a : N \ 0 > X , если Vz ( l ^ i & i ^ k ^ a ( i ) = Ь ( г )) .

Последовательность — это конечная либо бесконечная последовательность.

Отношение вхождения для кортежей обобщается на последовательности следующим образом:

Определение 5.4.8. Последовательность а содержит конечную последовательность [3 длины к , если существует такое п , что

\/ г (1 ^ г & г ^ к => a ( i + и ) = /3( г )).

И, наконец, обратим внимание на иное обозначение функций, появившееся по аналогии с последовательностями и употребляемое в том случае, если область определения фиксирована и нас интересуют в пер­вую очередь значения функции, а не взаимосвязь между аргументами и

38 Как Вы чувствуете из этой оговорки, появилась и неклассическая математика, но объем произведенноговклассической настолько больше, что многиеинеподозревают о существовании существенно других интерпретаций. Примерно так же сейчас в России многие, говоря ‘компьютер', понимают IBM PC .

значениями. Это — запись функции как семейства значений:

\ i ) i ? l '

Аргумент называется в данном случае индексом, результат — г-тым членом семейства. Чаще всего как семейства представляют функции, значениями которых служат объекты высших типов: множества либо другие функции.

Семейства, в частности, полезны для обобщения операций на бесконечное число аргументов, если это возможно. Например, в теории мно­жеств обобщаются на любое семейство аргументов операции объединения, пересечения, прямой суммы, прямого произведения.

Определение 5.4.9. 1. [ J Х; ь = { х \ Зг(г € / & х X ,,)}.

2. р | Xi = { х | Уг ( г G /4 i ? X ,,)}.

3. (J) Xi = {( г , x) | i € i" & x Xi\.

4. Y[ Xi = {/ | / : I >¦ |J г € X; t & Vi(i € /=>/(*) € X,,)}.

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

Упражнения к § 5.4

5.4.1. Когда тройка X f » Y = ( X , Y , X х Y ) является функцией? Когда данная функция является инъекцией? Сюръекцией? Биекцией?

5.4.2. Имеются ли функции из 0 в непустые множества? Какие? А наоборот?

5.4.3. Почему доказательство теоремы Кантора-Шредера-Бернштейна не может быть использовано для составления программы, преобразующей две инъекции в биекцию, даже для счетных множеств?

5.4.4. Дайте доказательство теоремы Кантора-Шредера-Бернштейна для конечных множеств, подходящее для построения с его помощью преобразователя программ: процедуры, трансформирующей две данные функции-инъекции в одну — биекцию39.

5.4.5. Какое из равенств выполнено? Для невыполненного укажите, есть
ли вложение в одну из сторон.

/ ( X ) U / ( Y ) = f ( X U Y ) , f ( X ) П / ( Y ) = f ( X П Y ) .

5.4.6. Является ли любая ретракция сюръекцией? А накрытие — инъ
екцией?

5.4.7. Верно ли, что X !>= Y и Y !>= X влечет, что X и Y равномощны?

5.4.8. Каковы взаимоотношения между J ^ У и F ^= J ?

5.4.9. Докажите, что если X — счетно, то и множество всех кортежей
Х°° также счетно.

5.4.10. Студент Гениалькис предложил определить конечное множество как множество, представимое в виде { х \, ..., х п }. Что Вы ска­жете по этому поводу?

5.4.11. При обсуждении предыдущего определения студент Интеллектуалов выдвинул свое:

Будьте внимательнее! Разве вы еще не поняли, что автор — ехидна?

Класс конечных множеств — транзитивное замыкание класса, содержащего 0 и все множества вида { ж } ( чтобы снять все замечания, он определил их как множества, удовлетворяющие следующему условию:

Зх ( х X & У у ( у X => • х = у )) )

относительно операции объединения двух множеств.

Что Вы скажете по поводу этого определения?

5.4.12. Студент Рессель заявил, что на самом деле лучшее определение конечных множеств следующее:

Конечное множество — множество X , неравномощное никакому

Y С X & Y ф X .

А Вы что здесь скажете?

5.4.13. Студентка Программистская заявила, что все предыдущие опре никуда не годятся, поскольку ссылаются на множество всех множеств, которого нет. Она предложила определить конечные множества так, как делают все нормальные программисты — по индукции.

0 — конечное множество.

Если а — объект, то { а } — конечное множество.

Если X и Y — конечные множества, то X U Y — конечное множество.

А что Вы здесь скажете?

Определите верхнюю и нижнюю границы мощности множества всех последовательностей действительных чисел Ж п .

Покажите, что нет сюръекции X на ф X .

Определите, а что же такое подпоследовательность бесконечной последовательности?

§ 5.5. Фактор - множества

В предыдущем параграфе у нас частенько фигурировало слово ‘мощность'. Но мы стыдливо умалчивали, что это такое. На самом деле хорошего математического определения мощности множества просто нет, наиболее прозрачной была попытка Кантора определить мощность как множество всех равномощных друг другу множеств, но из-за парадокса Кантора и несуществования универса таких множеств просто не существует (за исключением мощности пустого множества). Кантор в своем определении следовал сложившейся к концу XIX века математической традиции, когда уже был хорошо разработан способ перевода отноше­ний эквивалентности в отношения равенства через посредство фактормножества.

Условия, накладываемые на отношение эквивалентности, на самом деле минимальный вариант выразимых на логическом языке свойств равенства. А именно:

Определение 5.5.1. Отношением эквивалентности называется рефлексивное, транзитивное и симметричное отношение40.

Таким образом, класс эквивалентности элемента х есть R (х) . Отношение эквивалентности R обладает, в частности, следующими важными свойствами:

Предложение 5.5.1. 1. Ух Vy ( R (х) = R (у) V R (х) П R (у) = 0) .

Vi(x GDomi?^>i G й ( ж )) .

УхУу ( х € Domi ? & у ? Domi ? => • (R(x) = R(y) - ФФ - (x,y) ? R)).

Доказательство. Пункт 3. Если образы равны, то, по рефлексивности, у R (у) , но R ( x ) = R (у) , значит, ( х , у ) R . Если, наоборот, ( х , у ) R , то из ( у , z ) R по транзитивности следует ( x , z ) R , а из ( х , z ) R по симметричности и транзитивности следует ( у , z ) R .

Пункт 1. Пусть имеется такое z , что ( х , z ) R & ( у , z ) R . Тогда, по симметричности, ( x , z ) R & ( <?>?/ ) €Е R - По транзитивности

40 Поскольку все эти понятия применяются у нас лишь к отношениям на некотором множестве X , отсюда следует, что отношение эквивалентности является подмноже­ством некоторого X 2 .

( х , у ) R , и по пункту 3 образы равны. Значит, если они пересекаются, то они совпадают 41 .

Последний пункт очевиден. ?

Итак, отношение эквивалентности разбивает свою область определения на непересекающиеся классы эквивалентности.

Определение 5.5.2.

1. Класс эквивалентности элемента х — его образ R (х) , то есть

{ у | ( х , у ) R}-

2.Фактор-множество — множество классов эквивалентности всех элементов множества X по отношению эквивалентности = .

3. Если / — функция из множества X с заданным на нем отношением эквивалентности R \ в множество Y с заданным на нем от­ношением эквивалентности R 2 , то / называется согласованной с эквивалентностью, если

УхУу ( х eXkyeXk ( x , y ) eR 1 ^ ( f ( x ), f ( y )) е R 2 ).

Таким образом, функция согласована с эквивалентностью, если она по эквивалентным аргументам выдает эквивалентные значения.

4. Отношение эквивалентности R \ на множестве X сильнее отноше
ния эквивалентности R 2 на том же множестве, если R \ С R 2 .

Класс эквивалентности х относительно R обозначается x r и еще чаще просто х , поскольку обычно одновременно рассматривается лишь одно отношение эквивалентности.

Предложение 5.5.2. 1. Отношение равенства — сильнейшее из отношений эквивалентности.

41 То, что последующий пункт доказан раньше предыдущего и использован в доказательстве предыдущего, сознательная “небрежность”. Важно накрепко запомнить, что порядок пунктов в теореме не играет с логической точки зрения никакой роли, поскольку конъюнкция коммутативна. Зато в доказательстве порядок играет важнейшую роль, поскольку не допускается ссылка на то, что еще не обосновано.

Отношение R = X — слабейшее из отношений эквивалентно­сти.

Предикат Р ( х ) согласован с эквивалентностью ттт

УхУу (( х , у ) ( z R => ( Р ( х ) - ФФ - Р ( у ))).

Очевидно.

Отношение эквивалентности часто записывают как бинарную опе­рацию, похожую по внешнему виду на равенство, пользуясь для этого значками типа ~ , ~ , =, = , х . Полного единообразия здесь быть и не должно, поскольку на одной и той же структуре часто рассматриваются несколько отношений эквивалентности. Если отношение эквивалентно­сти обозначается бинарной операцией =, то фактор-множество X по отношению = обозначается Х /=. Класс эквивалентности элемента а по рассматриваемому в данный момент отношению эквивалентности часто обозначается а .

Если функция согласована с отношением эквивалентности R (=), то можно определить функцию из фактор-множества с теми же значениями:

//=(?) =/( я ). (5.16)

Обратим Ваше внимание на одну тонкость. Мы определили фактор-функцию, не прибегая к несколько неаккуратной конструкции, часто используемой в данном случае: не выбирая произвольного элемента из х , так что ее определение ни от каких сомнительных принципов теории множеств не зависит. Но, конечно же, отношение, заданное в ( 5.16 ), является функциональным лишь тогда, когда / согласована с эквивалентностью.

Пример 5.5.1. Фактор-множество X по отношению равенства — множество всех {{ х } | х X }. Таким образом, здесь мы просто рассаживаем все элементы по отдельным клеткам, превращая множество в зоопарк.

Пример 5.5.2. Фактор-множество X по отношению X 2 состоит из одного всеобъемлющего класса эквивалентности { X }. Здесь вместо зоопарка получается загон для всего стада элементов X .

Пример 5.5.3. Кольцо вычетов по модулю п может быть представлено как фактор-множество множества целых чисел по отношению

3 z \ x у \ = п * z .

Все арифметические операции на кольце получаются при этом из арифметических операций на целых числах простой факторизацией.

Если X — алгебра с какими-то операциями, то переходить к фактор-алгебре можно лишь тогда, когда операции по всем аргументам согласованы с эквивалентностью.

Фактор-множества тесно связаны с функциями. А именно, любая функция задает отношение эквивалентности:

{( ж , у ) | х € Dom / & у ? Dom / & f (%) = fill )} ¦

С другой стороны, Хх . х является функцией, определяющей данное отношение эквивалентности. Множества, на которых функция сохраняет одно и то же значение, часто называются множествами уровня данной функции. Таким образом, любое отношение эквивалентности предста­вляется как совокупность множеств уровня некоторой функции. Отношение эквивалентности, генерируемое функцией / , обозначается =, а

фактор-множество по = — просто X / f .

Пользуясь отношениями эквивалентности, легко установить следующий фундаментальный результат:

Предложение 5.5.3. Любая функция может быть представлена как композиция сюръекции и инъекции.

Доказательство. Возьмем Dom / / / . Хх . х является сюръекцией на это
множество, а //= — инъекцией из этого множества в Val / . ?

Еще одно фундаментальное представление фактор-множеств и от­ношений эквивалентности основывается на понятии разбиения множества.

Определение 5.5.3. Семейство множеств ( Xi ) ieI называют разбиением множества X , если:

1. и Xi = х .

ViVj(i ? l$ ? J ? l$ ? i^j=> Xi П Xj = 0) .

Ни одно из Xi не пусто.

Итак, в совокупности множества из разбиения покрывают все X и между собой они попарно не пересекаются.

Предложение 5.5.4. Любое разбиение задает отношение эквивалентности и наоборот.

Упражнения к § 5.5

  • Являются ли отношениями эквивалентности объединение и пересечение двух отношений эквивалентности?
  • Постройте фактор-множество R по отношению эквивалентности, задаваемому функцией, находящей дробную часть числа.

5.5.1. Являются ли отношениями эквивалентности отношения:

  • Иметь одну и ту же мать.
  • Иметь одну и ту же сестру.
  • Различаться на рациональное число (на множестве действительных чисел).
  • Различаться по модулю не более чем на 1.
  • Быть равномощными (для множеств).

5.5.2. Существует изоморфизм G 1 на G 2 (для групп).

5.5.3. Существует гомоморфизм G 1 в G 2 (для групп).

5.5.4. Какое из отношений эквивалентности более сильное?

  • Получить одинаковые оценки на вступительном экзамене по математике.
  • Иметь одну и ту же сумму баллов на вступительных экзаменах.
  • Решить одни и те же задачи на вступительном экзамене по математике.

5.5.5. По возможности не проводя вычислений, определите, каковы от
ношения порядка между следующими числами:

  • Число отношений эквивалентности на n -элементном множестве X .
  • Число разбиений натурального числа n на сумму натуральных положительных чисел.
  • Число отношений эквивалентности на n -элементном множестве X , с точностью до изоморфизма.
  • Число разбиений и-элементного множества X на подмножества.
  • Число представлений и в виде суммы положительных целых чисел, расположенных в порядке неубывания.
  • Число таких наборов натуральных положительных чисел Y , что

У г = п .

i &

7. Число таких множеств натуральных положительных чисел
Y , что

У г = п .

§ 5.6. Графы

То, что рассказывается в данном параграфе, может рассматриваться как пример представления сложных структур.

Графы появились как наглядное представление для системы объектов и связывающих их отношений, но быстро переросли это конкретное назначение.

Определение 5.6.1. Граф G — четверка ( V , R , begin , end ) , где V —множество вершин графа G , R — множество его ребер, begin , end — функции из V в R . begin г называется началом ребра г R , end г — его концом.

Принятая в математике форма определения

П есть кортеж , В , С , D )

означает на самом деле отказ в данный момент от содержательного раскрытия определения и замену его перечислением понятий, используемых в дальнейшем. Смысл такого “определения” раскрывается в последующих определениях 42 . Но при этом необходимо помнить, что любой математический термин нагружен основательным множеством смыслов, слишком многие из которых обычно лишь подразумеваются. Например,

Именно так!

когда говорится “мно ество”, неявно предполагается, что порядок его элементов безразличен, что среди его элементов нет повторяющихся, и т. п.

Итак, в графе есть вершины и ребра. Для каждого ребра есть начало и конец. Обычно на чертежах вершины обозначаются точками, а ребра — стрелками. Введем терминологию, касающуюся вершин и ребер.

Определение 5.6.2. Петля — ребро,укоторого началоиконец совпа -дают. Ребро r выходит извершины v , если beginr = v . Ребро r входит ввершину v , если endr = v . Путь — последовательность ребер,вко - торой начало каждого последующего ребра совпадаетсконцом преды -дущего .Ко-путь — последовательность ребер,вкоторой конец каждо - го последующего ребра совпадаетсначалом предыдущего 43 .Связь — последовательность путейико-путей, такая, что начало каждого следу - ющего ее члена совпадаетсконцом предыдущего 44 .Цикл — конечный путь, такой, что его началоиконец совпадают. Кортеж конечного пу­ти—кортеж его ребер, взятыхвтом же порядке. Путь(ко- путь)максимален, если он конечениего нельзя продолжить .Кратные ребра — ребрасоднимиитеми же началомиконцом .Начальная вершина— вер - шина,вкоторую не входит ни одно ребро .Конечная вершина — верши -на, из которой не выходит ни одного ребра .Изолированная вершина — вершина, являющаяся одновременно начальнойиконечной. Графсвя- зен, если между каждыми двумя его вершинами есть связь .

Пример 5.6.1. Проиллюстрируем введенные понятия на рис.5.8.Вгра-фе1нет петельикратных ребер.Вграфе2естьитеидругие.Вграфе 3 все пути, за исключением одного, конечны.Вграфе4есть два мини-мальныхпересекающихсяцикла.

Граф называется деревом , если у него имеется такая вершина v 0 — корень дерева, что из v 0 в любую другую вершину v ведет ровно один путь.

Предложение 5.6.1. Граф G является деревом тогда и только тогда, когда выполнены следующие условия:

  • Таким образом, ко-путь — путь, взятый “наоборот”.
  • Из данного определения следует, что и последовательность нулевой длины — связь

1. В графе есть ровно одна начальная вершина.

Граф 1

Граф 2

Граф 3

Граф 4

Граф 5 Рис. 5.8: Графы

  • В любую другую вершину входит ровно одно ребро.
  • В графе нет бесконечных ко-путей.

Доказательство. Только тогда. Пусть G — дерево. Докажем все условия.

Таких вершин не может быть две, поскольку тогда ни в одну из них нет пути из корня, а корень один. Если же их нет вообще, то в корень входит ребро a , и значит, есть вершина w , из которой можно попасть в корень.

Пусть есть вершина, в которую ведут два ребра:

Q > i /

0, 2 V 2

V \ ¦'

P \ P 2

Vo

Рассмотрим пути P 1 ? [ a 1 ] и P 2 ? [ a 2 ]. Оба они ведут в v из корня. А это противоречит свойствам дерева.

3) Докажем его приведением к абсурду. Пусть в графе есть бесконеч-

Тогда, поскольку корень — начальная вершина, он на этом пути не лежит. Есть путь из корня в ао. Поскольку этот путь содержит конечное число вершин, то не все вершины из ко-пути входят в него. Значит, он имеет вид

Pi = \ Ьо > ¦ ¦ ¦ > bi = CLj , . . . , flo ) •

Здесь все начала ребер Ь^ не лежат на бесконечном ко-пути. А вот конец bi лежит на этом ко-пути, и концом его является lOj + i .

Возьмем теперь iOj +2. Имеется путь Р<±, ведущий из корня в iOj +2. Тогда путь Рг * [ oj + i , aj > Oj - i , • • • , Яо] ведет из корня в wq . Н о он содер­жит вершину vJj +2, которой не было на исходном пути. Таким образом, из корня получаются два пути в одну точку, что противоречит определению дерева.

Тогда. Пусть все условия выполнены. Единственную вершину, в ко­торую ничего не входит, сделаем корнем. Теперь докажем, что есть путь из корня в любую вершину. Доказательство ведем от противного. Пусть ао — вершина, в которую нет пути из корня. В нее входит ребро, начало этого ребра назовем а_ь Из a _ i есть путь длины 1 в ао. Сделаем условие

Из a _ n есть путь длины и в ао (5.17)

инвариантом математической индукции 45 .

Пусть построено a _ n . Тогда в него нет пути из корня, поскольку этот путь дополнялся бы до пути в ао- а _( п +1 ) построим как начало единственного ребра, входящего в a _ n .

Таким образом, по вершине, в которую нет пути, мы строим беско
нечный ко-путь, что противоречит третьему условию. ?

Представление данных с помощью деревьев обладает многими положительными особенностями, но порою несколько неэффективно, если до некоторых объектов можно добраться несколькими способами. По­этому ищутся структуры, сохраняющие большинство достоинств деревьев, но позволяющие не дублировать одну и ту же информацию. Наиболее распространенной из них является сеть.

45 Хотя формально в данной книге индукция еще не определена, но Вы, конечно, ею пользовались.

Предложение 5.6.2. Последовательность вершин является связью ттт для любых ci n и ci n -\- i естьребро, их связывающее \т. е. либо из а п в ci n -\- i , либо из a n + i в а п ).

Определение 5.6.3. Сеть — связный ориентированный граф без ци­клов.

Сеть отличается от дерева тем, что в одну вершину может входить несколько ребер, т. е. однажды полученный объект может использоваться многократно. В частности, граф 5 на рис. 5.8 является сетью.

С понятием графа связано несчитанное множество недоразумений и недоговоренностей. Прежде всего так и тянет “упростить” понятие графа, например, следующим образом:

Определение 5.6.4. (Графы в части элементарных книг по математике) Граф — пара ( V , R ), где R С ( V х V ) \ idy .

Если мы принимаем определение 5.6.4, то графы уже не могут содержать ни петель, ни нескольких дуг с одинаковым началом и концом. Поэтому приходится вводить новые понятия: квазиграф — граф с петлями, псевдограф — граф, в котором могут быть кратные ребра из a в Ъ . Ну что же, нам не привыкать, что в элементарной математике “для упрощения” многие понятия излишне сужаются и тем самым запутываются.

Далее, в большинстве книг по математической теории графов за исходное принимается следующее определение:

Определение 5.6.5. (Неориентированный) граф — пара V , R , где ка­ждый из элементов R — двухэлементный набор вершин из V .

Определение 5.6.5 определяет существенно другую структуру. Раз у нас ребра становятся наборами, то начало и конец ребра более не различаются, и поэтому такие графы называются неориентированными. Те, кто принимают в качестве исходного понятия неориентированные графы, называют наши графы ориентированными, либо сокращенно орграфы. В неориентированных графах даже терминология часто меняется: вершина называется точкой, ребро — дугой.

Чаще всего в структурах данных графы ценны не сами по себе, а как вместилища для другой информации. В этом случае значащая информация размещается в вершинах графа, а иногда и на его ребрах. Математически это формулируется следующим образом:

Определение 5.6.6. Оснащенный граф — тройка ( G , if , ip ) , где G —граф, ip — функция, областью которой служит множество его вершин, ip функция, областью которой служит множество его ребер. Если v — ребро графа G , то ip ( v ) называется оснащением вершины v либо информацией, приписанной данной вершине. Соответственно и для ребер.

При представлении данных в программах выработалась уже почти стандартная структура данных для графа с оснащенными вершинами:

type vertex= record

content: datatype;

arcs: array [namearcs] of A vertex; end ;

В данном случае тип дуги явно не вводится, дуги являются ссылками на вершины, в которые они ведут.

Упражнения к § 5.6

5.6.1. Есть ли бесконечные пути в графе 2 на рис. 5.8?

5.6.2. В книгах можно часто встретить определение:

Путь — последовательность вершин, такая, что a n и a n + i соединены ребром.

Для каких классов графов данное определение корректно? Для каких — нет?

5.6.3. В теории графов дерево часто определяется как связный граф без циклов. Почему это так?

5.6.4. Плоским называют граф, который может быть изображен наплос- кости таким образом, что вершины изображаются точками, ребра — непрерывными кривыми из начала в конец, причем различные ребра не пересекаются. Является ли пятиконечная звезда плоским графом 46 ?

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

Теорема 5.5. (Жордан) Замкнутая кривая делит плоскость на два открытых множества (две области).

Следствием ее является утверждение, что любая кривая, начинающаяся в одной из

5.6.5. Верно ли, что добавление любого конечного числа кратных ребер к плоскому графу оставляет его плоским?

§ 5.7. Диаграммы

Здесь мы познакомимся с еще одним диалектом языка современной ма­тематики — началами языка коммутативных диаграмм, широко применяемых ныне повсюду, где пользуются теорией категорий. Начнем, как и обычно, с примера.

Попытаемся дать характеризацию прямых произведений и прямых сумм, не прибегая к теоретико-множественному языку, лишь через их отображения. На стр. 88 мы содержательно описали, как скомбинировать из n отображений в члены произведения одно отображение в X 1 ? • • • ? X n и как построить отображение из произведения в другое про­изведение на базе отображений компонент. Запишем эти свойства при помощи коммутативных диаграмм.

Сплошная стрелка на диаграмме означает заданное отображение. Пунктирная стрелка — отображение, однозначно строящееся по заданным. Из алгебры (именно на стыке алгебры с топологией впервые стали интенсивно использоваться подобные диаграммы) пришел ныне общепринятый термин: коммутативная диаграмма , означающий, что если рассматривать диаграмму как граф и брать композиции отображений по разным путям, ведущим из вершины v 1 в вершину v 2 , то полученные двух областей, на которые заданная кривая ? делит плоскость, а заканчивающаяся в другой, пересекает.

Отображения будут одинаковы. Ныне в математических работах принято, что если явно не оговорено противное, все приведенные диаграммы коммутативны.

А теперь построим такие же диаграммы для прямой суммы.

Сравнивая диаграммы, видим, что в сущности они отличаются лишь направлением стрелок. Значит, понятия прямого произведения и прямой суммы подобны друг другу. Такое подобие на­зывается в теории категорий двойственностью 47.

Дадим минимальную совокупность требований, достаточных, что­бы рассматривать стрелки и коммутативные диаграммы. Эта совокуп­ность составляет аксиоматику теории категорий . Она зачастую называется еще теорией стрелок, а порою ее называли абстрактной чепухой.

Определение 5.7.1. Категория — пара классов: класс объектов Ob и класс морфизмов Mor , на которых заданы следующие операции :

Впрочем, слово ‘двойственность' используется во многих разделах математики для обозначения однородных явлений: сохранения истинности математических теорем при взаимной замене некоторых понятий. Например, в логике двойственны Т , &, V и _1_ , V , 3 . В проективной геометрии двойственны прямые и точки. Исторически именно в проективной геометрии впервые было осознано понятие двойственности.
  1. Унарные операции Domf и Codomf , сопоставляющие каждому морфизму два объекта, называемые его областью значенийиобла - стью определения, либо, соответственно, началомиконцом, либо областьюикообластью. Через Mor ( a , b ) обозначается множество морфизмовсначалом в a и концом в b ( морфизмов из a в b ). То, что f является морфизмом из a в b , обозначается f : a > b .
  2. Унарная операция е , сопоставляющая каждому объекту а единичный морфизм е а из а в а .
  3. Тернарная операция о ( а , Ь , с), сопоставляющая каждой тройке объектов операцию композиции, дающую по паре морфизмов f : a —> b и g : b —> с их композицию f о ( а , 6 , с ) g : a —> с , и выполнены следующие алгебраические тождества48:
  4. е а ° 9 = 9> f ° е а = / для всех f b —> a, g : a —> b.
  5. a о ( b о с ) = ( а о b ) о с .

Итак, предполагается лишь ассоциативность композиции и существование единичного морфизма.

Теперь строго зададим понятие коммутативной диаграммы.

Определение 5.7.2. Коммутативная диаграмма — оснащенный граф, вершинам которого приписаны объекты категории, а ребрам — морфиз- мы из начала ребра в его конец, удовлетворяющий следующему усло­вию:

на каждом пути из вершины v \ в вершину V 2 композиции морфизмов этого пути равны.

Отметим несколько умолчаний, встречающихся в теории категорий. Пунктирные стрелки не включены в строгое определение. Это тесно связано с тем, что на диаграммах с пунктирными стрелками (а порою и на других диаграммах) имеется неявная расстановка кванторов. Неко­торые объекты и морфизмы считаются данными, некоторые — определяющимися через данные (именно их обозначают пунктирными стрелками), а другие — произвольными, причем определяется это лишь из контектста, окружающего данную диаграмму. Например, в диаграмме 5.9 даны два объекта а , b , а х Ъ и проекции определяются через них, объект с и его морфизмы — произвольные, и, наконец, пунктирная стрелка однозначно определяется через все остальное.

Пример 5.7.1. Зададим аксиоматику единичных морфизмов, да и само понятие композиции вместе с его ассоциативностью, при помощи ком-

48 При обозначении композиции тройки объектов, по которым она определена, однозначно устанавливаются из контекста и поэтому почти всегда опускаются: пишем просто f ? g .

А кстати, почему здесь нет прямой стрелки от а к d ?

Стрелки категории отнюдь не обязательно являются функциями.

Пример 5.7.2. Возьмем произвольное частично-упорядоченное множество X . Оно может рассматриваться как категория, в которой объектами служат элементы множества X , множество морфизмов из а в Ъ непусто, лишь если а ^ Ъ , и в этом случае состоит из единственного морфизма, называемого морфизмом порядка.

Пример 5.7.3. Полугруппа — алгебраическая структура с одной ассоциативной операцией умножения о , такой, что существует единица:

е ох = х ое = х .

Любая полугруппа становится категорией, в которой единственный объект — сама эта полугруппа, а морфизмы — ее элементы.

Одним из новых выразительных средств, предоставленных теорий категорий, явилось то, что коммутативные диаграммы сами часто могут рассматриваться как новые объекты или морфизмы.

Пример 5.7.4. (Навеян идеями [16]) Пусть мы построили математическую модель для некоторого класса объектов X (например, множества действительных чисел) и определили вычислимые операции над эти- ми объектами49. Пусть элементы некоторых других пространств У± и У 2 ( скажем, множества состояний двух систем) естественно кодируются знакомыми нам объектами (но вполне возможно, такие кодирования неоднозначны: например, 24.30 и 00.30 кодируют одно и то же время). Мы даже не предполагаем, что две функции кодирования v \\ X —> У± , v < i : X —)¦ У 2 согласованы. Тогда мы можем не возиться заново с переопределением вычислимости для отображений из У^ в У^ и определить их как коммутативные квадраты вида.

  • 49 Примечание для математиков. Это не обязательно означает, что мы определили все вычислимые операции. Мы могли ограничиться теми, которые нам нужныв данный момент. Единственные, но вполне естественные здесь, ограничения — что тождественное отображение вычислимо и что композиция двух вычислимых отображений вычислима; а это как раз и есть аксиомы теории категорий.

Приведенная конструкция похожа на следующую, весьма общую: категорию морфизмов данной категории. Объектами категории морфиз- мов считаются морфизмы исходной категории С . Морфизмом / в д на­зывается коммутативная диаграмма исходной категории:

Композиция морфизмов определяется следующим образом:

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

Пример 5.7.5. Рассмотрим некоторые начальныеиконечные объекты .

  • Втеории множеств пустое множество—начальный объект,алю- боеодноэлементное—конечный .
  • Подэквациональной системойлибо(простейшей)алгебраической системой понимается структура, являющаяся моделью системы

х о (г/ о z ) = ( х о у ) о z (5.18)

х о х~ = е (5.19)

х о е = х (5.20)

еох = х (5.21)

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

ip ( x о у ) = ( р(х) О if ( у ) и т. д.

В любой такой категории есть нулевой объект: система из одного элемента. На ней все равенства тривиально выполняются, а неравенств у нас быть не может.

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

t\ = U\ & • • • & t n = u n => г = s (5.22)

либо

Pi & • • • P n => Q, (5.23)

где Pi , Q — предикаты. Рассматриваются модели таких алгебраических систем, объектами которых являются замкнутые термы, составленные в данной сигнатуре из имеющихся констант при помощи явно заданных в аксиомах операций (сколемовские модели). На термах нужно определить равенство, а его можно задать по-разному. Практически стандартным способом определения равенства стало правило:

Если элементарное утверждениенедано и не следуетиз данных, то оно считается ложным. Следовательно, все термы, для которых нельзя доказать равенство, счита тся различ­ными 50 .

В категории сколемовских моделей алгебраической системы, аксиоматизированной условными равенствами, этому свойству удовлетворя­ет инициальная модель , из которой имеется единственный эпиморфизм на любую другую сколемовскую модель. Обобщая определение, получаем: инициальный объект — объект, для которого имеется единственный эпиморфизм на любой другой объект.

Подытожим:

Теория категорий стимулирует формулировку свойств математических объектов через их отображения, сохраняющие структуру.

Само понятие отображения в теории категорий обобщается и называется морфизмом .

Главным элементом языка теории категорий являются коммутативные диаграммы, в которых морфизмы, получающи­еся на любых двух путях из одного объекта в другой, совпадают.

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

Все приведенные выше соглашения о диаграммах не абсолютны, но их нарушение оговаривается явно, так что читайте тексты внимательнее!

Сами коммутативные диаграммы могут быть сделаны объектами новых категорий, в частности, так определяются категории морфизмов. Через такие конструкции теория категорий дает возможность задать весьма абстрактные объекты высших порядков.

  • 50 Это правило имеет в современном “логическом программировании” название «Принцип замкнутости мира».

Теория категорий является, в частности, языком, на котором выражено большинство наиболее тонких и важных резуль­татов современной теории типов данных.

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

Упражнения к § 5.7

5.7.1. Студент Цхалтубенко предложил следующее определение категории:

Категория — класс морфизмов, на котором задана частичная бинарная операция композиции о , удовлетворяющая следующим требованиям:

  • Если определено fo ( goh ), то определено и ( fog ) oh и их значения совпадают, и наоборот.
  • Для любого морфизма / существуют такие единичные морфизмы ei , ег , что e i о / = / , / о ег = / .

Проанализируйте данное определение и скажите, эквивалентно ли оно исходному. Если оно неэквивалентно, то как его исправить?

5.7.2.Студент Талантов заявил, что объекты можно вообще изгнать из определения категории, отождествив их с единичными морфизма- ми. Уточните идею Талантова и дайте соответствующее ей определение категории.

5.7.3.Каким свойством обладает любой морфизм из начального объекта? А в конечный?

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

5.7.5.То же для функций, таких, что задаваемые ими отношения эквивалентности совпадают (т. е. f ( x ) = f ( y ) <з> д ( х ) = д(у)).

5.7.6.Возможно ли, чтобы прямое произведение а и 6 было изоморфно их прямой сумме? Если это возможно, двиньтесь дальше: может ли для всех объектов некоторой категории прямое отображение совпадать с прямой суммой?

5.7.7. Пусть С — категория, порожденная некторым частично-упорядоченным множеством L . В каком случае два объекта а , Ъ имеют прямое произведение и как это прямое произведение определить на языке частичного порядка?

5.7.8.То же для прямой суммы.

5.7.9.Рассмотрим категорию всех подмножеств конечного множества X , отображениями в которой служат обычные функции. В каком случае два подмножества имеют прямое произведение либо прямую сумму?

5.7.10. Рассмотрим категорию частично-определенных теоретико-множественных функций (т. е. однозначных отношений). Функции, которые нигде не определены, обладают интересными свойствами. Сформулируйте эти свойства.

§ 5.8. Слова

В математической логике часто приходится следить за тем, чтобы объекты были построены конечным образом из конечного числа исходных понятий. Известно (хотя на самом деле и нетривиально; в частности, в теории алгоритмов с этим придется повозиться), что для представления таких объектов достаточно слов в конечном алфавите 51 .

Алфавит — исходное понятие. Его можно описать как конечную последовательность ясно различимых неделимых символов, называемых буквами .

Определение 5.8.1. Слово — конечная последовательность букв алфа - вита 52 . Операция приписывания слова B к концу слова A называетсясо- единениемиликонкатенациейи обозначается просто AB . Слово A есть начало (конец)слова B , если B представимоввиде AC ( соответственно , CA ).Собственное начало(конец)—начало(конец),не являющееся пустым словом или всем B . Слово A входитв слово B , если B представимо в виде CAD , т. е. если A начало конца B . Вэтом случае A называется подсловом B . Длина слова—количество входящихвнего букв .

  • Теоретическидостаточно инатуральных чисел, но здесь кодирование получается менее прямым, что часто неудобно. А удобством при представлении данных пренебрегать нельзя.
  • Пустое слово, не содержащее букв вообще, также считается словом и обозначается ? .

Заметим, что одно и то же слово может много раз входить в другое. Например, ‘ба' трижды входит в ‘баобаба'. Для точности употребляют понятие (отмеченное) вхождение A в B, представляемое как слово формы C A * D в алфавите, расширенном новым символом * .

Стандартным способом представления последовательностей, составленных из потенциально бесконечного набора исходных примитивов, является сопоставление каждому примитиву слова (в языках программирования называемого идентификатором) и разделение этих слов новым символом, например, пробелом. Мы будем придерживаться такого представления. В этом случае начала, концы и подслова не могут разбивать на части примитивы, и длиной слова будет считаться количество входящих в него примитивов. Последовательность слов вида S , разделенных символом * , есть слово вида ? i * ? 2 * • • • * ?п либо пустое слово.

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

Для избежания недоразумений (в особенности для необычно выгля­дящих слов) мы порою будем заключать рассматриваемое слово в одинарные кавычки, например, ‘Ст-т Чудаков! & ( Со' .

Для дальнейшего потребуется однозначное и достаточно простое ко­дирование слов алфавита натуральными числами. Если алфавит состоит из и букв, то естественно сопоставить буквам цифры 1, ..., п соответственно и закодировать слова как числа в системе с основанием и + 1. На многочисленные удобства такого кодирования указал Р. Смальян, мы его будем называть просто позиционным.

Упражнения к § 5.8

  1. Покажите, что множество слов в данном алфавите естественно изоморфно множеству кортежей из букв этого алфавита.
  2. Докажите, что множество систем слов естественно изоморфно множеству кортежей из кортежей.
СодержаниеДальше

наверх страницынаверх страницы на верх страницы









Заказать работу



© Библиотека учебной и научной литературы, 2012-2016 Рейтинг@Mail.ru Яндекс цитирования