§ 4. Некоторые специальные классы функций

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

Определение. Подстановкой множества А назы­вается биекция на А. //

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

Пусть . Обозначим через „Р„ число таких подстановок. Значение „Р„ легко вычислить. Можно рас­сматривать задачу построения биекции на А как задачу заполнения ящиков, пронумерованных от 1 до п (рис. 3.6), объектами a₁,..., a_n. Порядок, в котором за­полняются ящики, несуществен (любой другой порядок можно получить перемешиванием ящиков). Поэтому бу­дем заполнять их слева направо. Первый ящик может быть заполнен га способами, так как мы имеем свобод­ный выбор из всего множества А. Убирая выбранный

Рис. 3.6

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

Это произведение называется факториалом п (обознача­ется n!). Следовательно, _пР_п = п!.

Так как А ~ N_n, то можно свести наше рассмотрение к N_n. Любая подстановка на N_n должна определять об­раз каждого элемента в N_n (который, конечно, должен быть единственным и отличным от других). Пусть — подстановка на N_n. Тогда можно определить как мно­жество из n пар следующим образом:

Где

Не обязательно, конечно, должно быть x₁ — 1 и т. д. Можно также представить следующим образом:

^{Пример 4.1. Пусть — подстановка на N5:}

Тогда (1) = 5, (3) = 3 и т. д. //

Достоинством этого обозначения является простота, с которой могут быть вычислены сложные подстановки, Предположим, что — подстановка на N _n, определенная выше, а ^— другая подстановка на том же самом мно­жестве. Тогда подстановка может быть записана как совокупность пар в порядке, определяемом х₁, хг, х_n. Если две последовательности записать одну над другой (первая применяемая подстановка должна быть записа­на первой), то верхняя и нижняя строки дадут резуль­тирующую подстановку.

Пример 4.2. Пусть подстановка пз примера 4.1 и

Можно переписать в виде Следовательно, например,

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

Определение. Пусть А = {а₁, а_п). Подстанов­ку называют циклом (циклической подстановкой), если

Предположим, что и В конечно. Расширяя на все В, можно определить подстановку так, что

В этом случае ведет себя подобно во всех случаях, когда элементы В не остаются на месте. Применение к А передвигает элементы по кругу циклическим образом, и, если известна область А, мы можем обозначить подстановку как (а₁, а₂, ..., а_п). Эта подстановка назы­вается циклом длины п. //

Пример 4.3. Рассмотрим опять подстановку

Подстановка является циклом длины 5 и может быть за­писана как

(1, 3, 6, 5, 4). //

Не все подстановки являются циклами. Например, под­становка в примере 4.1 не является циклом. Напом­ним, что имела вид

(1)=5, (5)=4, (4)= 1, откуда следует, что содержит цикл (1, 5, 4). Начиная с 2, получаем дру­гой цикл —(2, 6). Таким образом, имеем —(1, 5, 4)•(2, 6) и =(2, 6) •(1, 5, 4).

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

Теорема. Каждая подстановка р на конечном мно­жестве А выражается в виде произведения непересекаю­щихся циклов.

Доказательство. Поскольку |A|=n N, то А ~ N_n. Поэтому без потери общности мы можем огра­ничиться рассмотрением подстановки на N_n.

В теореме утверждается, что где каждое является циклом и циклы не пересекаются. Для доказательства теоремы построим требуемые циклы. Сначала найдем наименьший элемент такой, что и для всех х, . Если такого х₁ не существует, (т. е. является тривиаль­ным пустым произведением циклов). В противном слу­чае вычислим и т. д. Все эти элементы находятся в N_n. Поэтому элементы в этой по­следовательности должны содержать повторения. Пред­положим, что p^h(x₁)—первый такой элемент (который уже повторялся в последовательности). Покажем, что .Предположим, что это соотношение не вы­полняется. Тогда для некоторого l, 0<1< k. Следовательно,

и т.д.

Поэтому , т. е. , что противоречит минимальности к (так как k-l<k). Та­ким образом, , и подстановка

задает цикл внутри .

Если все элементы такие, что (будем называть такие элементы нестационарными), содержатся в , то — единственный цикл (который, естест­венно, не пересекается). В противном случае найдем следующий наименьший элемент такой, что и x₂ не встречается в . Из строим множе­ство различных степеней :

Это цикл длины не менее 2, и он не пересекается с , (Доказательство оставляем в качестве упражнения.) Если все нестационарные элементы исчерпаны, то . Очевидно, что множество нестационар­ных элементов, не входящих в эти циклы, можно уменьшить, и в конце концов придем к . Следовательно, , для некоторого . //

Рассмотрим теперь несколько иную ситуацию. Возь­мем множества А: |А|=n и , |В| = . Возни­кает вопрос: сколько биективных функций существует из А в В? Или, что эквивалентно, сколько существует инъективных отображений из В в A? Число перестано­вок (без повторений) из п элементов по r обозначается , и вычисляется так же, как и , за исключением того факта, что процесс прекращается после заполнения r ящиков. Таким образом,

Легко видеть, что, продолжая процесс заполнения ящи­ков, оставшиеся п — r элементов можно разместить по последним n-r ящикам _n-rP_n-r, способами. Поэтому и

При вычислении _nР, мы находим число биективных функций из А в В. Подсчитаем числа таких функций.

Определение. Пусть А — конечное множество и , . Множество В называется со­четанием (без повторений) из п элементов по r. Число таких сочетаний обозначается через .//

Вычисление производится следующим образом. Положим . Возьмем произвольное подмножество такое, что . Тогда В является образом под­становки из n элементов по r. Число инъективных функ­ций на А, имеющих В своим образом, есть _nP_r. Если f является такой функцией и g — другая такая функция, имеющая ту же самую область значений, то g связано с f соотношением , где — подстановка на В. Функции g и f определяют одну и ту же комбинацию, и в действительности число функций, определяющих эту комбинацию, равно числу подстановок на В. Сле­довательно,

_{n r}

откуда

Поскольку относительные дополнения единственны и |A\B|=n-r, то отсюда следует, что .

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

Определение. Последовательностью на множест­ве S называют отображение .

Если : - заданная последовательность и , то обычно обозначают последовательность не , a ( ) или (s₁, S₂, s₃, ...). В этом случае s_n называ­ют n-м членом последовательности. //

Часто при изучении свойств последовательностей возникает понятие «расстояние» между соседними эле­ментами последовательности (скажем, и ) и меж­ду элементами при (где n₀ — некоторый фикси­рованный элемент N) и фиксированным элементом из S,

Мы вернемся к этим вопросам несколько позже, посколь­ку в настоящий момент у нас в общем случае нет поня­тия расстояния.

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

Определение. Пусть даны множества А, В и С. Обозначим через множество всех функций из В в С. Функция называется функциона­лом. Следовательно, — функция, и . Далее, . //

На первый взгляд такая комбинация, как f(a)(b), выглядит настолько необычной, что может казаться не­законной. Это в основном потому, что рассматриваемые функции использовались как объекты особого рода, в ря­де случаев отличные от элементов, которые были в об­ласти определения и области значения функций. Конеч­но, множества функции могут рассматриваться так же, как и любые другие множества.

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

Пример 4.4. Пусть Р — множество программ, т. е. текстов программ (строк символов), которые должны быть обработаны компилятором. Аналогично пусть l и О — множества соответственно входных и выходных значений, которые доступны программе для ввода и вы­вода. Тогда компилятор (с соответствующего языка) яв­ляется функционалом типа ; для данной он пытается создать машинный код, который при выполнении будет читать и выдавать . Из дальнейшего изложения будет видно, что определение функций (или функционалов) сложности компилятора длинное и сложное. Тем не менее эти понятия можно изучать в более простых ситуациях.

Пример 4.5. Пусть все данные принадлежат R. Тогда, если , то

и ,

то время как и и т. д. //

Обращение с функционалами не вызывает трудно­стей ори условии, что ссылка делается па основной функционал (т. е. или ). Следователь­но, в дальнейшем мы будем рассматривать их просто как функции, имеющие нетривиальные области значе­ний, и будем обращаться с ними соответствующим образом.

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

Определение. Пусть X — множество, на котором задано отношение эквивалентности р. Тогда X разбива­ется отношением на - эквивалентные классы; множе­ство классов обозначается как Х/ .

Определение. Пусть X и Y — множества, а и — отношения эквивалентности на них, и пусть — отображение. Обозначим через отношение

такое, что

где [х] — класс эквивалентности х. Если — функция, то

^и f является отображением, сохраняющим эквивалент­ность. В этом случае говорят, что индуцирует отображение

Наглядный способ представления такого отображения дан на рис. 3.7.

Если рассмотреть отображение f, согласованное с отношением эквивалентности, то можно переходить от х₁ к у₂ или через х₂, используя соотношения у₂ = f(x₂) и , или через у₁, используя соотношения и .

Пример 4.6. Пусть Х = {1, 2, 3}, Y={1,4,9}, и пусть и таковы, что

,

и такое, что . Тогда

,

,

.

В этом случае и . Поэтому f является функцией и f сохраняет отношения эквивалентности. //

Пример 4.7. Пусть X, У и f те же, что и раньше, и отношение эквивалентности и , индуцируют раз­биения {{1}, (2, 3}} и {{1, 4}, {9}} соответственно. В этом случае индуцированные отношения дают

.

Так как 2 3, то [2] = [3] в Х/ , но (4, 9) , по­скольку [4] ≠ [9] в У/ . По сравнению с рис. 3.7 этот пример дает отношения, показанные на рис. 3.8. Так как

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

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