«Прикладная логика Учебное пособие Рекомендовано Государственным комитетом Российской Федерации по высшему образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальностям ...»

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

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

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

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

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

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

Естественно, что порядок элементов в наборе не имеет значения. Набор обозначается a1,..., an, но эта запись не столь общеупотребительна, как для множеств и кортежей. Порою набор будет обозначаться просто a1,..., an, если это явно оговорено в контексте16.

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

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

Упражнения к § 5. 5.2.1. Пусть S — трехместное отношение между студентами, университетами, в которых они учатся, и городами, где эти университеты находятся. Как Вы выразите его проекцию по третьему компоненту?

5.2.2. Докажите, что имеется взаимно-однозначное отображение A B C на A (B C), сохраняющее pr1 и переводящее pr2 (x) в pr1 (pr2 (x)), a pr3 (x) в pr2 (pr2 (x)).

5.2.3. Сравнив определение декартовой степени и множества всех кортежей, объясните, почему множество всех кортежей получило обозначение U.

5.2.4. Для кортежей и множеств одноэлементные структуры строго отличаются от самих объектов; для n-ок они отождествляются с объектами. А как для наборов? Обоснуйте свое мнение.

5.2.5. Можно ли выразить через наши фундаментальные операции над кортежами операцию x.[x], переводящую каждое x в соответствующий одноэлементный кортеж.

5.2.6. Часто в математических определениях используют понятие “неупорядоченная пара”. Компоненты неупорядоченной пары не различаются по месту, так что (a, b) = (b, a). Определите это понятие через одно из имеющихся у нас.

5.2.7. Определите именованные множества через множества пар.

5.2.8. Верно ли для кортежей a b = b a? Если да, докажите, если нет, приведите опровергающий пример17.

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

мы математики!

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

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

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

5.2.12. Пусть задано отображение A B в C. Всегда ли из него можно получить пару отображений: из A в C и из B в C?

5.2.13. Верно ли, что pr1 (X Y ) = pr1 X pr1 Y ?

5.2.14. Верно ли, что pr1 (X Y ) = pr1 X pr1 Y ? 5.2.15. Студент Интеллектуалов определил неупорядоченное произведение n множеств X1,..., Xn как множество всех n-членных наборов, имеющих по одному члену из каждого множества. Что Вы можете сказать по поводу данного определения19 ?

';

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

ОТНОШЕНИЯ

§ 5.3.

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

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

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

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

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

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

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

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

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

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

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

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

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

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

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

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

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

Антисимметричным — такое R, что R1 R =.

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

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

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

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

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

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

Определение 5.3.5. Композиция отношений R X Y, S Y Z — отношение R S X Z, такое, что Итак, при композиции мы связываем x и z посредством такого y, что y соответствует x согласно R и z соответствует y согласно S. Очевидно, что если отношения имеют вид то их композиция представляется как Приведем некоторые важные алгебраические свойства композиции отношений.

Но вот R R1 = idX выполнено отнюдь не всегда.

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

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

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

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

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

1. X — наименьшее множество, обладающее свойством A, если выполнено A(X) и 2. Транзитивное замыкание отношения R X X — наименьшее отношение R X X, такое, что R содержит все элементы Не путайте данную степень с декартовой! Забавнее всего, что поскольку отношения также множества, можно рассматривать и декартову степень R, но в связи с тем, что в чистой математике она практически никогда не нужна, математики допускают т. н. “вольность речи,” а вот безумные программисты иногда вынуждены использовать структуры данных, соответствующие декартову произведению отношений.

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

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

Если отношение транзитивно и антирефлексивно, оно называется отношением (частичного) порядка и обозначается символом < либо похожими на него (например, ). Если отношение транзитивно и рефлексивно, то оно называется отношением предпорядка и обозначается символом, похожим на (например, ). Частичный порядок называется линейным, если выполнено условие Обратите внимание!! В третьем пункте мы определили транзитивное замыкание R через класс, содержащий само это транзитивное замыкание. Более того, если из этого класса транзитивное замыкание выбросить, порою пересечение оставшихся множеств уже будет побольше. Так что в последнем случае R определялось само через себя!

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

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

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

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

Определение 5.3.8. Элемент x0 чума X называется наибольшим, если Таким образом, он больше всех остальных. Максимальный элемент не меньше никакого другого.

Симпатичное русское сокращение чум введено новосибирской школой. Московская математическая школа его не признает, видимо, потому, что в Европе ни чумов, ни чумы нет.

Хотя фактически частенько чиновники занимают позицию “Начальник моего начальника — не мой начальник” и, соответственно, приказания Президента не исполняются чаще, чем повеления непосредственного шефа, но формально такое поведение противоречит законам и инструкциям.

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

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

Элемент a называется верхней гранью множества Y X (обозначается sup Y либо Y ), если Соответственно определяется нижняя грань (inf Y, Y ). Верхняя (нижняя) грань двух элементов обозначается a b (a b). Чум, в котором у каждых двух элементов имеется верхняя и нижняя грань, существуют наибольший и наименьший элементы, называется структура. Структура называется полной, если верхние и нижние грани существуют у любого подмножества элементов.

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

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

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

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

Объясните, можно ли определять пару, скажем, так:

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

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

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

5.3.4. Верно ли, что 5.3.5. Когда (x, x) RR1 ? Выведите из Вашего условия, когда idX 5.3.6. Каковы обратные отношения к следующим отношениям:

3. Быть начальником.

6. Быть братом или сестрой.

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

a) Быть родителем Быть отцом б) Быть родителем Быть сестрой 5.3.8. Имеются ли отношения, которые одновременно и симметричны, и антисимметричны?

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

5.3.10. А есть ли множество, на котором любое отношение рефлексивно?

5.3.11. Отношение порядка, для которого выполнено RR = R, называют плотным. Почему? Переведите данное условие на логический 5.3.12. Докажите, что для любого отношения предпорядка R R = R.

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

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

5.3.15. Определение 5.3.9 содержит неточность. Найдите и исправьте.

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

5.3.16. Не ошибся ли автор в определении максимального элемента, опустив условие y = x0 ? А как для предупорядоченных множеств?

5.3.17. Переведите на формальный язык следующее определение:

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

ФУНКЦИИ

§ 5.4.

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

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

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

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

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

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

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

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

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

Определение 5.4.2. (Важные классы функций) 1. Инъекция (однозначное отображение) — такая функция f, что Иногда ради этого даже логику изменяют; в главе, посвященной конструктивным логикам, мы с этим немного разберемся.

Неразбериха с порядком функций при композиции длилась несколько десятилетий.

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

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

Предложение 5.4.1. (Композиции с инъекциями и сюръекциями) 1. Композиция двух инъекций — инъекция.

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

3. f : X Y инъекция тогда и только тогда, когда для любых двух 4. f : X Y сюръекция тогда и только тогда, когда для любых 5. f : X Y инъекция тогда и только тогда, когда существует функция g : Y X (называемая накрытием, ассоциированным Рис. 5.7: Инъекция и накрытие, сюръекция и ретракция 6. f : X Y сюръекция тогда и только тогда, когда существует функция g : Y X (называемая ретракцией, ассоциированной с (Другими словами, g f = idY.) Доказательство. Пункты 1, 2 и 4 остаются в качестве упражнений читателю.

Доказательство пункта 3. Пусть f — инъекция из X в Y. Пусть g1 f = g2 f. Тогда для произвольного x f (g1 (x)) = f (g2 (x)). Но по инъективности f отсюда следует g1 (x) = g2 (x). Поскольку вывод сделан для произвольного x, g1 = g2, что и требовалось установить. Теперь обратно. Пусть для всех g1, g2, таких, что g1 f = g2 f, выполнено равенство g1 = g2. Возьмем произвольные x1, x2. Пусть f (x1 ) = f (x2 ).

Теперь возьмем одноэлементное множество Z = {z0 } и построим два отображения из Z в X, такие, что g1 (z0 ) = x1, g2 (z0 ) = x2. Поскольку f (g1 (z0 )) = f (g2 (z0 )), а других значений аргумента нет, g1 f = g2 f.

Значит, в частности, g1 (z0 ) = g2 (z0 ), и x1 = x2. Прошу Вас обратить внимание, что в этом доказательстве нет рассуждений от противного.

Поэтому данное свойство инъекций весьма устойчиво при смене логики.

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

Доказательство пункта 5. Пусть у f есть ассоциированное с ним накрытие g. Покажем, что тогда f — инъекция. В самом деле, возьмем произвольные x1, x2, такие, что f (x1 ) = f (x2 ). Тогда g(f (x1 )) = x1 = g(f (x2 )) = x2. Теперь в обратную сторону. Пусть f — инъекция. Построим накрытие g следующим образом: если y f Dom f, то имеется единственное x, такое, что f (x) = y. Оно и будет значением функции g. Если же y f Dom f, то такого x вообще нет, и можно задать значение g равным произвольно выбранному элементу x0 31.

Доказательство пункта 6. Поскольку f — сюръекция, для каждого y Val f множество R1 y непусто. Сопоставим каждому y какойлибо из элементов R1 y. Полученная функция и будет искомой ретракцией32.

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

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

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

когда она является и инъекцией, и сюръекцией.

Доказательство. Пусть отношение R — график функции f. Рассмотрим отношение R1. Поскольку f — сюръекция, для каждого x Y существует y X, (x, y) R1. Поскольку f — инъекция, из (x, y1 ) R1, (x, y2 ) R1 следует y1 = y2. Таким образом, R1 — функциональное отношение.

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

Предложение 5.4.3. f f 1 = IdDom f, f 1 f = IdVal f.

Доказательство оставляется в качестве упражнения.

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

то X и Y равномощны.

Доказательство. Пусть X Y и Y X. Тогда имеются две инъекции:

f : X Y, g : Y X. Если хоть одна из них является сюръекцией, то эквивалентность установлена. Если ни одна из них не является сюръекцией, то множество X \ g Y непусто. Возьмем произвольный элемент x0 этого множества. Возьмем отношение Рассмотрим его транзитивное замыкание R. Образ x0 при этом замыкании либо конечен, либо бесконечен. Рассмотрим эти два случая.

Пусть образ R x0 конечен. Тогда он состоит из конечного множества элементов g(f (xn )) = xi для некоторого i < n. Но поскольку f g — инъекция, i = 0. В самом деле, если i = 0, то i = j + 1, но тогда xj+1 = g(f (xj )) = g(f (xn )), где xj = xn, чего не может быть. Но по предположению x X \ g Y, и соответственно, нет такого y, что x0 = g(y).

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

Значит, остается лишь случай, когда образ x0 бесконечен. Все элементы этого образа, очевидно, лежат в g Y. Докажем теперь, что образы разных x X \ g Y при соответствии R не пересекаются. Рассуждение аналогично тому, с помощью которого мы опровергали конечность R x0. Возьмем произвольные x, y X \ g Y. Если их образы пересекаются, то некоторые из xn равны некоторым из ym. Возьмем наименьшее такое n. Если оно не 0, то xn1 = ym1, но g(f (xn1 )) = Теперь построим, пользуясь выше установленным разбиением X, g(f (ym1 )).

биекцию Y на X. Для этого видоизменим функцию g. Положим g1 (y) = Итак, все последовательности xn сдвигаются на один элемент, и в результате g1, оставаясь инъекцией, становится и сюръекцией.

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

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

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

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

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

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

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

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

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

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

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

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

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

Доказательство. Пусть имеется биекция f множества X на Y X, Y = X. Тогда возьмем какое-либо x0 X \ Y. f (x0 ) = x0, обозначим его x1. Далее, подобно тому, как делалось в теореме Кантора-ШредераБернштейна, положим xn+1 = f (xn ), и так же, как в упомянутой теореме, можно показать, что все xi различны. Множество и есть искомое счетное подмножество X.

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

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

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

Поэтому начнем с некоторого одноэлементного множества V0 X, и для каждого Vi выберем35 Vi+1 как произвольный элемент E Vi. Очевидно, что Vi Vj при i < j, и объединение возрастающей последовательности и есть искомое счетное подмножество X.

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

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

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

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

См. также § 10.5.1.

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

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

Доказательство. Пусть имеется некоторое отображение an множества N в действительные числа из отрезка [0, 1] (последовательность). Построим по ней представленное в троичной системе число b, не входящее в данную последовательность и, более того, такое, что от данного an оно отличается уже первыми n + 1 членами троичного разложения.

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

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

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

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

Итак, двоичные знаки получившегося числа соединяют двоичные знаки всех аргументов, и, очевидно, каждое из xi однозначно восстанавливается по значению ((x1,..., xn )). Инъекция R в Rn очевидна.

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

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

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

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

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

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

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

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

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

Аксиома подстановки. Если X — множество, и x(x X также множество.

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

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

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

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

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

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

(это множество обозначается просто X) 4. Множество всех подмножеств:

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

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

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

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

Если множества имеют одни и те же элементы, они равны.

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

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

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

Функции, аргументом которых служат натуральные числа, обычно называют последовательностями и обозначают несколько по-другому:

саму функцию (an )nN, конкретное значение ai. В данной книге мы, следуя логической традиции, несколько расширяем понятие последовательности.

Определение 5.4.7. Конечной последовательностью называется отображение множества {i | i N & i 1 & i k}. k — ее длина.

Бесконечной последовательностью называется отображение множества N либо N \ 0.

Конечная последовательность b : {i | i N & i 1 & i k} X является началом конечной последовательности если l k и i(1 i & i k a(i) = b(i)).

Конечная последовательность b : {i | i N & i 1 & i k} X является началом бесконечной последовательности a : N \ 0 X, если Последовательность — это конечная либо бесконечная последовательi(1 i & i k a(i) = b(i)).

ность.

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

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

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

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

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

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

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

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

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

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

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

5.4.9. Докажите, что если X — счетно, то и множество всех кортежей 5.4.10. Студент Гениалькис предложил определить конечное множество как множество, представимое в виде {x1,..., xn }. Что Вы скажете по этому поводу?

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

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

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

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

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

Конечное множество — множество X, неравномощное А Вы что здесь скажете?

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

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

3. Если X и Y — конечные множества, то X Y — конечное А что Вы здесь скажете?

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

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

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

ФАКТОР-МНОЖЕСТВА

§ 5.5.

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

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

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

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

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

Пункт 1. Пусть имеется такое z, что (x, z) R & (y, z) R. Тогда, по симметричности, (x, z) R & (z, y) R. По транзитивности Поскольку все эти понятия применяются у нас лишь к отношениям на некотором множестве X, отсюда следует, что отношение эквивалентности является подмножеством некоторого X 2.

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

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

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

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

1. Класс эквивалентности элемента x — его образ R x, то есть 2. Фактор-множество — множество классов эквивалентности всех элементов множества X по отношению эквивалентности.

3. Если f — функция из множества X с заданным на нем отношением эквивалентности R1 в множество Y с заданным на нем отношением эквивалентности R2, то f называется согласованной с эквивалентностью, если Таким образом, функция согласована с эквивалентностью, если она по эквивалентным аргументам выдает эквивалентные значения.

4. Отношение эквивалентности R1 на множестве X сильнее отношения эквивалентности R2 на том же множестве, если R1 R2.

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

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

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

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

3. Предикат P (x) согласован с эквивалентностью ттт Очевидно.

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

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

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

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

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

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

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

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

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

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

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

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

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

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

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

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

Упражнения к § 5. 5.5.1. Являются ли отношениями эквивалентности объединение и пересечение двух отношений эквивалентности?

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

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

2. Иметь одну и ту же сестру.

3. Различаться на рациональное число (на множестве действительных чисел).

4. Различаться по модулю не более чем на 1.

5. Быть равномощными (для множеств).

6. Существует изоморфизм G1 на G2 (для групп).

7. Существует гомоморфизм G1 в G2 (для групп).

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

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

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

1. Число отношений эквивалентности на n-элементном множестве X.

2. Число разбиений натурального числа n на сумму натуральных положительных чисел.

3. Число отношений эквивалентности на n-элементном множестве X, с точностью до изоморфизма.

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

4. Число разбиений n-элементного множества X на подмножества.

5. Число представлений n в виде суммы положительных целых чисел, расположенных в порядке неубывания.

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

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

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

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

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

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

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

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

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

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

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

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

Таким образом, ко-путь — путь, взятый “наоборот”.

Из данного определения следует, что и последовательность нулевой длины — связь.

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

2. В любую другую вершину входит ровно одно ребро.

3. В графе нет бесконечных ко-путей.

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

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

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

Рассмотрим пути P1 [a1 ] и P2 [a2 ]. Оба они ведут в v из корня. А это противоречит свойствам дерева.

3) Докажем его приведением к абсурду. Пусть в графе есть бесконечный ко-путь a0, a1,... an,..., проходящий через вершины w0,... wn ,...

Тогда, поскольку корень — начальная вершина, он на этом пути не лежит. Есть путь из корня в a0. Поскольку этот путь содержит конечное число вершин, то не все вершины из ко-пути входят в него. Значит, он имеет вид Здесь все начала ребер bk не лежат на бесконечном ко-пути. А вот конец bi лежит на этом ко-пути, и концом его является wj+1.

Возьмем теперь wj+2. Имеется путь P2, ведущий из корня в wj+2.

Тогда путь P2 [aj+1, aj, aj1,..., a0 ] ведет из корня в w0. Но он содержит вершину wj+2, которой не было на исходном пути. Таким образом, из корня получаются два пути в одну точку, что противоречит определению дерева.

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

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

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

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

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

Предложение 5.6.2. Последовательность вершин является связью ттт для любых an и an+1 есть ребро, их связывающее (т. е. либо из an в an+1, либо из an+1 в an ).

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

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

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

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

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

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

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

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

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

вершина называется точкой, ребро — дугой.

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

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

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

type vertex= record content: datatype;

arcs: array[namearcs] of ^vertex;

end;

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

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

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

Путь — последовательность вершин, такая, что an и Для каких классов графов данное определение корректно? Для каких — нет?

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

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

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

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

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

ДИАГРАММЫ

§ 5.7.

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

AB AB C D

Рис. 5.9: Диаграммы для прямого произведения Попытаемся дать характеризацию прямых произведений и прямых сумм, не прибегая к теоретико-множественному языку, лишь через их отображения. На стр. 88 мы содержательно описали, как скомбинировать из n отображений в члены произведения одно отображение в X Xn и как построить отображение из произведения в другое произведение на базе отображений компонент. Запишем эти свойства при помощи коммутативных диаграмм (см. рис. 5.9).

Сплошная стрелка на диаграмме означает заданное отображение.

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

AB AB C D

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

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

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

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

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

1. Унарные операции Dom f и Codom f, сопоставляющие каждому морфизму два объекта, называемые его областью значений и областью определения, либо, соответственно, началом и концом, либо областью и кообластью. Через Mor(a, b) обозначается множество морфизмов с началом в a и концом в b (морфизмов из a в b). То, что f является морфизмом из a в b, обозначается f : a b.

Впрочем, слово ‘двойственность’ используется во многих разделах математики для обозначения однородных явлений: сохранения истинности математических теорем при взаимной замене некоторых понятий. Например, в логике двойственны, &, и,,. В проективной геометрии двойственны прямые и точки. Исторически именно в проективной геометрии впервые было осознано понятие двойственности.

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

2. Унарная операция e, сопоставляющая каждому объекту a единичный морфизм ea из a в a.

3. Тернарная операция (a, b, c), сопоставляющая каждой тройке объектов операцию композиции, дающую по паре морфизмов f : a и выполнены следующие алгебраические тождества48 :

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

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

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

на каждом пути из вершины v1 в вершину v2 композиции морфизмов этого пути равны.

Отметим несколько умолчаний, встречающихся в теории категорий.

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

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

мутативных диаграмм.

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

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

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

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

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

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

Пример 5.7.4. (Навеян идеями [16]) Пусть мы построили математическую модель для некоторого класса объектов X (например, множества действительных чисел) и определили вычислимые операции над этими объектами49. Пусть элементы некоторых других пространств Y1 и Y2 (скажем, множества состояний двух систем) естественно кодируются знакомыми нам объектами (но вполне возможно, такие кодирования неоднозначны: например, 24.30 и 00.30 кодируют одно и то же время).

Мы даже не предполагаем, что две функции кодирования 1 : X Y1, 2 : X Y2 согласованы. Тогда мы можем не возиться заново с переопределением вычислимости для отображений из Yi в Yj и определить Примечание для математиков. Это не обязательно означает, что мы определили все вычислимые операции. Мы могли ограничиться теми, которые нам нужны в данный момент. Единственные, но вполне естественные здесь, ограничения — что тождественное отображение вычислимо и что композиция двух вычислимых отображений вычислима;

а это как раз и есть аксиомы теории категорий.

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

их как коммутативные квадраты вида Приведенная конструкция похожа на следующую, весьма общую:

категорию морфизмов данной категории. Объектами категории морфизмов считаются морфизмы исходной категории C. Морфизмом f в g называется коммутативная диаграмма исходной категории:

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

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

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

1. В теории множеств пустое множество — начальный объект, а любое одноэлементное — конечный.

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

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

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

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

для которых нельзя доказать равенство, считаются различными50.

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

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

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

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

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

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

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

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

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

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

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

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

1. Если определено f (gh), то определено и (f g)h 2. Для любого морфизма f существуют такие единичные морфизмы e1, e2, что e1 f = f, f e2 = f.

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

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

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

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

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

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

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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 в алфавите, расширенном новым символом.

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

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

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

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

На многочисленные удобства такого кодирования указал Р. Смальян, мы его будем называть просто позиционным.

Упражнения к § 5. 5.8.1. Покажите, что множество слов в данном алфавите естественно изоморфно множеству кортежей из букв этого алфавита.

5.8.2. Докажите, что множество систем слов естественно изоморфно множеству кортежей из кортежей.

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

Классическая логика Глава 6. Индукция и определения

О РАЗНЫХ ВИДАХ ИНДУКЦИИ

§ 6.1.

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

Пример 6.1.1. Докажем, что сумма трех последовательных кубов натуральных чисел делится на 9.

Базис. 13 + 23 + 33 = 36 и делится на 9.

Шаг. Чтобы произвести шаг, нужно предположить доказываемое утверждение для n и затем доказать его для n + 1. Пусть n3 + (n + 1)3 + (n + 2)3 делится на 9. Тогда Но все слагаемые в последней скобке делятся на 9, а первая скобка делится на 9 по предположению, значит, и исходная сумма делится на 9.

Таким образом, мы установили, что делимость суммы, начинающейся с n, влечет делимость суммы, начинающейся с n + 1.

Следовательно, утверждение доказано для всех n.

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

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

Пример 6.1.2. Докажем, что n плоскостей, проходящих через одну точку, никакие три из которых не проходят через одну прямую, делят пространство на An = n(n 1) + 2 частей.

Шаг. Пусть утверждение доказано для n. Докажем его для n + 1.

Пусть Pn+1 — n + 1-я плоскость. Каждая область разбиения представляет собой многогранный угол, вершиной которого является общая точка всех плоскостей p. Число частей при разбиении n + 1-ой плоскостью равно (здесь мы применяем предположение индукции) An + число многогранных углов, разбиваемых на две части Pn+1.

Поскольку сечение каждого из таких двугранных углов плоскостью Pn+ является плоским углом с вершиной в p, число разбиваемых двугранных углов не может быть больше 2n, а поскольку никакие три плоскости не пересекаются по прямой, их не может быть меньше 2n. Таким образом, Пример 6.1.3. Пусть на плоскости имеется точечный прожектор, освещающий сектор внутри угла < 180. Пусть заданы n непересекающихся отрезков (которые могут смыкаться концами). Докажем, что тогда выполнено одно и только одно из трех:

1. Прожектор не освещает ни одной точки ни одного отрезка.

2. Прожектор освещает конец хотя бы одного из отрезков 3. Имеется отрезок ai (часть которого, пересекающаяся с сектором, полностью освещена), полностью затеняющий все остальные, пересекающиеся с сектором освещения.

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

Точка A освещена, если отрезок OA находится внутри освещенного сектора и не пересекается ни с одним из отрезков ai, кроме, возможно, самой точки A.

Точка A затенена отрезком ai, если внутри отрезка OA встречается точка из ai.

Базис индукции. Если у нас всего один отрезок AB, то он либо пересекается, либо не пересекается с освещенным сектором. Если он не пересекается, то выполнена первая возможность. Если же он пересекается, то либо хотя бы один из его концов лежит в освещенном секторе, либо же оба они лежат вне его. В первом случае соответствующий конец A освещен (либо же, если отрезок тянется вдоль луча OA и B лежит на этом луче до A, то освещен B). Во втором возьмем на отрезке произвольную точку C, лежащую внутри освещенного сектора. Отрезок не может лежать вдоль OC, так как его концы не освещены, значит, точка C освещена.

Шаг индукции. Пусть для любой системы из n отрезков имеет место один из рассмотренных случаев. Рассмотрим систему из n + 1 отрезка.

Удалим из нее последний отрезок. Рассмотрим три возможных случая для получившейся системы.

Если ни один из отрезков a1,..., an не освещен, то ни один из них не пересекается с сектором освещения, и все рассматривается точно так же, как в базисе индукции, в соответствии с положением последнего отрезка.

Если некоторые из концов отрезков были освещены, то рассмотрим, затеняет ли их отрезок an+1. Если все освещенные концы им затеняются, то остается рассмотреть два подслучая:

1. Хотя бы один из концов an+1 лежит в секторе освещения. Тогда хотя бы один из его концов будет освещен, и выполнен второй случай.

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

В программировании математическая индукция соответствует циклам типа пересчета (for i:=0 to k do языка Паскаль).

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

Пример 6.1.4. Докажем, что все лошади одного цвета. Действуем по индукции. Параметр индукции — число n лошадей в их множестве.

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

Базис. n = 1. Одна лошадь, естественно, одного цвета. Точнее, все лошади, принадлежащие одноэлементному множеству лошадей, одного цвета.

Шаг. Пусть доказано для n. Докажем для n + 1. Возьмем произвольное множество Л из n + 1 лошади. Удалим из него некоторую лошадь л0.

По предположению индукции, Л0 = Л \ {л0 } состоит из лошадей одного цвета. Теперь удалим из Л0 некоторую лошадь л1 и добавим туда л0. Полученное множество Л1 также состоит из лошадей одного цвета, значит, л0 того же цвета, что и остальные лошади из Л1, а они являются элементами Л0 и того же цвета, что и л1. Что и требовалось доказать.

Пример 6.1.5. Докажем, что все ученые — лысые.

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

Но если лысому человеку добавить один волос, то он останется лысым. Значит, по индукции получаем, что ученые с любым количеством волос на голове лысые.

Ошибки найдите сами.

Принцип математической индукции допускает несколько переформулировок, которые в традиционной математике эквивалентны исходному принципу.

Первая из них — возвратная индукция. Здесь переход происходит не от одного значения к следующему, а от всех предыдущих значений к последующему, шаг индукции переводит не от A(n) к A(n + 1), а от x < n A(x) к A(n). Как ни парадоксально, при таком переходе не требуется базиса индукции. В самом деле, поскольку условие x < 0 тождественно ложно, то, поскольку из лжи следует все что угодно, имеем а отсюда по шагу индукции имеем A(0).

Соответственно, формулировка принципа возвратной индукции следующая:

Докажем при помощи возвратной индукции следующее предложение.

Пример 6.1.6. Сумма внутренних углов любого плоского n-угольника без самопересечений равна (n 2).

Рис. 6.1: Предложение о внутренних углах многоугольника Для треугольника это доказывается в элементарной математике, а многоугольников с числом углов меньше 3 нет. Таким образом, утверждение индукции доказано для всех n 31.

Пусть имеется многоугольник с числом сторон n > 3, и для всех k < n утверждение индукции уже доказано. Возьмем в многоугольнике любые три смежные вершины A, B, C. Из вершины B либо виден один из других углов D2, либо не виден ни один, и тогда все лучи, лежащие в угле ABC, первой пересекают одну и ту же сторону многоугольника.

В последнем из случаев могу быть еще два подслучая, симметричных друг другу. Либо на продолжении одной из сторон BA, BC первой встречается некоторая вершина D, либо никакой вершины не встречается. Тогда могут быть два случая (см. рис. 6.1).

1. Луч первой пересекает одну из сторон многоугольника. Тогда многоугольник разбивается лучом на два многоугольника. В каждом из них появляется одна новая вершина D, но пары вершин {A, E1 }, {B, E2 } лежат в разных многоугольниках, так что каждый из них содержит меньшее число вершин, чем исходный. Пусть один из них содержит m1 вершин, а второй — m2. Тогда m1 + m2 = n + (поскольку вершина B теперь принадлежит обоим многоугольникам, а D вообще новая и также принадлежит им обоим). Соответственно, вычисляя по индукции сумму внутренних углов нашего многоугольника, получаем:

Хотя мы только что обращали внимание на то, что формально возвратная индукция базиса не требует, фактически подобие базиса появляется практически в каждом таком доказательстве, поскольку случаи для наименьших возможных n обычно приходится рассматривать отдельно.

Виден — означает, что отрезок BD целиком лежит внутри открытого многоугольника

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

2. Луч прежде всего входит в вершину многоугольника. Опять-таки многоугольник разбивается на два многоугольника. В каждом из них присутствуют две вершины исходного многоугольника B и D, а все остальные вершины распределены между ними. Каждый из получившихся многоугольников содержит меньше вершин, чем исходные, поскольку в нем не присутствует хотя бы одна из вершин A, C.

Еще одна переформулировка метода математической индукции была известна еще древним грекам, хотя явно сформулировали ее лишь в XVII веке. Это — метод бесконечного спуска.

Если для каждого натурального числа, удовлетворяющего свойству A(n), найдется меньшее, удовлетворяющее этому же свойству, то чисел n, для которых выполнено A(n), вообще нет. Или формально:

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

Рассмотрим пример применения метода бесконечного спуска.

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

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

Еще одно следствие из возвратной индукции, эквивалентное ей5 :

принцип наименьшего числа.

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

Правда, Диоген искал хотя бы одного человека в Афинах днем с огнем...

Но только в классической математике!

Предложение 6.1.1. Во всяком непустом множестве натуральных чисел найдется наименьший элемент.

Доказательство. Принцип наименьшего числа является контрапозицией принципа бесконечного спуска.

Если у нас выполнен принцип наименьшего числа, то, поскольку это наименьшее число одно и только одно в каждом непустом множестве, появляется новая кванторная операция: квантор минимизации x x X либо, поскольку подмножество определяется свойством, x A(x). Такое выражение означает наименьшее число, обладающее данным свойством.

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

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

Доказательство. Если бы она была бесконечна, это противоречило бы принципу бесконечного спуска. Теперь выведем принцип бесконечного спуска из конечности убывающих последовательностей. Если бы для каждого ni, удовлетворяющего свойству A(ni ), нашлось бы меньшее его ni+1, удовлетворяющее этому же свойству, то получившаяся последовательность была бы бесконечной убывающей, чего не может быть.

Таким образом, от противного обоснован метод бесконечного спуска.

6.1.1. Вернемся к ситуации из примера 6.1.3 и несколько видоизменим 2. Что изменится, если разрешить счетное число отрезков?