Соответствия и функции

Соответствием между множествами А и В называется подмножество их декартова произведения GА•В.
Если (а,b)G, то b соответствует а при соответствии G. Множество проекций пр1G называется областью определения соответствия, множество пр2G – областью значений соответствия. Если пр2G=А, то соответствие полностью определенное (в противном случае – частичное). Если пр2G=В, то соответствие сюрьективно.
Множество всех bВ, соответствующих элементу а, в А называется образом а в В при соответствии G. Множество всех а, которым соответствует b, называется прообразом b в А при соответствии G.
Всюду определенное соответствие называют отображением и иногда записывают как Г:ХY, где  – знак отображения.
Подмножество FX•Y называется функцией, если для каждого элемента х, хХ найдется не более одного элемента yY в парах вида (х,y)F. При этом, если для каждого элемента х имеется один элемент y, то функция полностью определена, в противном случае – частично определена (недоопределена). Множество Х – область определения функции F, множество Y – область значений функции. Часто вместо записи (х,y)F используют запись y=F(х), при этом элемент х называют аргументом или переменной, а y – значением функции F. Количество аргументов определяет местность функции.
Сопоставим с декартовым произведением двух множеств прямоугольную решетку, узлы которой взаимно однозначно соответствуют элементам декартова произведения [9-10].
На рис. 7а изображено подмножество декартова произведения мно-жеств Х={х1,х2,х3,х4} и Y={y1,y2,y3}, не являющееся функцией, на рис. 7б – являющееся полностью определенной функцией; на рис. 7в – являющееся частично определенной функцией.

а) F1XY, не являю-щееся функцией, т.к. одному значению х может соответствовать два значения y. б) F2XY, являющее-ся полностью опреде-ленной функцией. в) F3XY, являющееся недоопределенной функцией, не опреде-ленной на значении ар-гумента х3.
Рис.7. Подмножества декартова произведения XY

Соответствие G между множествами Х и Y называется взаимно одно-значным, если каждому элементу хХ соответствует определенный эле-мент yY, и, наоборот, каждый элемент yY оказывается поставленным в соответствие одному элементу хХ.
Соответствие между множеством функций и множеством чисел назы-вается функционалом [19]. Часто говорят «функционал качества».
Например, функционалом может быть определенный интеграл, ставящий в соответствие некоторой функции число.
Соответствие между двумя множествами функций называется опера-тором. Например, имеется оператор дифференцирования.
Множество А называется эквивалентным множеству В, если существует взаимнооднозначное соответствие множеств А и В, это обозначается как
А=В или АВ.
Этот факт позволяет определять неизвестную мощность одних мно-жеств по известной мощности других, им эквивалентным. Множества, эквивалентные (равномощные) множеству натуральных чисел, называются счетными. В счетных множествах возможна нумерация элементов. Пример множества, не являющегося счетным – множество всех действительных чисел отрезка [0,1]. Это доказывается теоремой Кантора [19]. Попробуем пронумеровать это множество. Расположим все числа, изображенные бесконечными десятичными дробями в порядке нумерации:
0, а11 а12 а13 ...
0, а21 а22 а23 ...
0, а31 а32 а33 ...
. . . . . .,
где первая цифра индекса – номер бесконечной десятичной дроби. Рас-смотрим теперь любую бесконечную десятичную дробь 0, b1 b2 b3... такую, что b1а11, b2а22, b3а33 и т.д. Такая дробь не входит в указанную последовательность, так как отличается от первого числа первой цифрой, от второго числа – второй цифрой и т.д. Следовательно, все числа из отрезка [0,1] не могут быть пронумерованы, т.е. это множество несчетно. Его мощность называется континуум и все эквивалентные ему множества называются континуальными. Так, множество всех подмножеств счетного множества континуально.

Отношения

Подмножество RMn называется n местным отношением на множе-стве М. Говорят, что а1,...,аn находятся в отношении n, если (а1,...аn)R. Одноместное отношение (свойство, признак) – это просто подмножество М. Наиболее часто встречающиеся и хорошо изученные – бинарные отношения, для них RM2. Если а,b находятся в отношении R, то это часто записывают в виде аRb.
Примеры бинарных отношений на множестве людей «быть сыном», «служить в одном полку», «любить», «дружить».
Примером трехместного (тернарного) отношения является множество троек нападающих в хоккейной команде или отношение «ставить оценку», определяемое следующим образом: «преподаватель х ставит студенту y оценку z».
Можно определить обратное отношение R-1. Например, для отноше-ния  обратным является отношение .
Рассмотрим свойства отношений.
Отношение R называется рефлексивным, если для любого аМ имеет место аRа. Отношение антирефлексивно, если ни для какого аМ не вы-полняется аRа.
Отношение  рефлексивно, а отношение «быть сыном» антирефлек-сивно.
Таким образом, рефлексивность – свойство выполнимости отношения для каждого элемента подмножества R относительно самого себя.
Отношение R симметрично, если из aRb следует bRa (это может быть записано с использованием стрелки следования aRbbRa). В противном случае отношение R несимметрично, то есть, если aRb истинно, то bRa ложно. Отношение R антисимметрично, если из aiRaj и ajRai следует, что ai=aj.
Отношение дружбы симметрично. Отношение любви, как правило, несимметрично. Отношение  антисимметрично, действительно, если аb и bа, то а=b. Отношение R симметрично тогда и только тогда, когда R=R-1.
Отношение R транзитивно, если для любых а,b,с из аRb и bRс следует аRс. Это можно записать с использованием знака конъюнкции  (союз «И») и символа  «следует»:
(аRb)&(bRс)аRс
Например, отношение «являться начальником» транзитивно. Отношение дружбы нетранзитивно. Для любого отношения R отношение  , называемое транзитивным замыканием R, определяется следующим образом: а b, если существует цепочка из n элементов а=а1,а2,...,аn-1,аn=b, в которой между соседними элементами выполнено R:а1Ra2,a2Ra3,...,an-1Rb.
Транзитивным замыканием отношения «быть сыном» является отно-шение «быть прямым потомком», являющееся объединением отношений «быть сыном», «быть внуком», «быть правнуком» и т.д.
Отношение называется отношением эквивалентности, если оно реф-лексивно, симметрично, транзитивно.
Таково отношение равенства.
Отношение нестрогого порядка рефлексивно, антисимметрично и транзитивно.
Отношение строгого порядка антирефлексивно, антисимметрично и транзитивно.
Отношения  и  для чисел – отношения нестрогого порядка, отношения <, > – отношения строгого порядка.
Пример лексико-графического упорядочения слов в словарях: леслето, где  – символ упорядочения.
Отношение доминирования (например, на множестве спортсменов или спортивных команд) обозначается >>. Это отношение антирефлексивно, несимметрично и нетранзитивно.
Отношения (relations) являются основным объектом современных систем управления реляционными базами данных (СУБД), в которых отношения задаются, как правило, на произведении различных множеств. В теории СУБД, в отличие от «академической» записи отношений, принятой в математике используется содержательные записи, например:
<Иван, Мария, цветы, восьмое марта> – четырехместное отношение «Дарить», <Профессор Иванов, студент Петров, отлично> – тернарное отношение «Ставить оценку».
Чаще всего отношения в СУБД задаются таблицами, столбцы которых называют также атрибутами, полями, а строки – кортежами, записями.
Реляционная база данных, то есть база данных, основанных на отно-шениях, представляет собой совокупность таблиц. Таблица состоит из строк и столбцов. Столбец, то есть поле, задается так называемыми реквизитами: именем, типом (числовой, признаковый и т.д.), длиной, точностью для числовых данных.
Запись, таким образом – это совокупность связанных полей. Таблица – совокупность записей одной структуры. Одно из полей является так называемым первичным ключём, значения которого однозначно указывает на соответствующие ему записи (отношения).