1

Математические отношения и их свойства

Санкт-Петербург

2006

Содержание

• Содержание………………………………………………………………………..2
• ОТНОШЕНИЯ БИНАРНЫЕ И N-АРНЫЕ……………………………………...3
• Декартово произведение………………………………………………………….3
• Бинарные отношения (соответствия)……………………………………………3
• Операции над бинарными отношениями………………………………………..5
• Функциональные отношения…………………………………………………….6
• Бинарные отношения на множестве…………………………………………….8
• Декартово произведение

Бинарным отношением, или соответствием между элементами множеств А и В называется любое подмножество RАВ декартова произведения этих множеств. Тот факт, что некоторые aA и bВ находятся в отношении R, иногда выражают как aRb. В качестве примера бинарного отношения рассмотрим отношение R между элементами множеств А={1,2,3} и B={1,2,3, 4,5,6}, которое можно выразить словами так: элемент хA есть делитель элемента уВ. Тогда имеем

R={(1,1), (1,2),(1,3), (1,4), (1,5), (1,6), (2,2), (2,4), (2,6), (3,3), (3,6)}.

Бинарное отношение удобно представлять в виде двоичной (булевой) матрицы. Если i-й элемент множества А соответствует j-му элементу множества В, то элемент матрицы, расположенный на пересечении i-ой строки и j-го столбца, имеет значение 1, в противном случае он имеет значение 0. Например, рассмотренное выше отношение R будет представлено следующей матрицей:

1 2 3 4 5 6

1 1 1 1 1 1 1

0 1 0 1 0 1 2

0 0 1 0 0 1 3

Проекция элемента (a,b) множества АВ на множество А есть элемент а. Аналогично, элемент b является проекцией элемента (a,b) множества АВ на множество В. Проекцией множества ЕАВ на А называется множество всех тех элементов из А, которые являются проекциями элементов из Е на множество А. Для множеств А и В, рассмотренных выше, проекцией элемента (2,4) на множество А является элемент 2, а проекцией множества {(1,2),(2,2), (2,4)} - множество {1, 2}.

Сечением множества ЕАВ по а, обозначаемое Е(а), называется множество всех тех элементов уВ, для которых (a,у)Е. Сечением Е(Х) множества Е по ХА является объединение сечений для всех элементов из Х. Пусть R={(1,1),(1,3) (1,5), (1,6), (2,2), (2,4), (3,3), (3,6)}. Тогда Е(2)={2,4}, а если Х={2,3}, то Е(Х)={2,3,4,6}.

Бинарное отношение можно задавать с помощью сечений. Например, отношение, представленное матрицей

b₁ b₂ b₃ b₄

1 0 1 0 a₁

1 0 1 1 a₂

1 0 0 1 a₃ ,

0 0 0 0 a₄

0 0 0 1 a₅

можно задать следующим образом: R(a₁)={b₁,b₃}, R(a₂)={b₁,b₃,b₄}, R(a₃)={b₁,b₄}, R(a₄)=, R(a₅)={b₄}. Множество сечений для всех aA называется фактор-множеством. Областью определения отношения RАВ является проекция множества R на А. Для рассматриваемого выше отношения такой областью является {а₁,а₂,а₃,а₅}. Областью значений отношения RАВ является сечение множества R по А. Областью значений рассматриваемого отношения R является {b₁,b₃,b₄}.

Образом множества ХА относительно R называется множество {b/bВ, хХ, (х,b)R}. Прообразом множества YВ относительно R называется множество {a/aA, yY, (y,a)R}. В нашем последнем примере образом множества {а₁,а₃} относительно R является {b₁,b₃,b₄}, а прообразом множества {b₃,b₄} - {а₁,а₂,а₃,а₅}.

Обратным отношением R-¹ для некоторого отношения RАВ является множество, образованное теми парами (b,а)ВА, для которых (а,b)R. Матрица, представляющая отношение R-¹, получается транспонированием (заменой строк одноименными столбцами) матрицы, представляющей отношение R.

Операции над бинарными отношениями

Поскольку всякое отношение есть некоторое множество пар, над отношениями применимы все стандартные операции над множествами, т.е. объединение, пересечение, дополнение. Универсальным множеством для операции дополнения при этом является АВ.

Рассмотрим операцию композиции отношений. Заданы множества А, В, С и отношения RАВ и SВС. Композиция отношений S и R - это такое отношение SR между элементами множеств А и С, что для всех аА сечение множества SR по а совпадает с сечением множества S по подмножеству R(a)B. Это записывается в виде (SR)(a)S(R(a)). Пусть отношения R и S заданы соответственно следующими матрицами:

b₁ b₂ b₃ b₄ с₁ с₂ с₃

1 0 1 0 a₁ 0 1 0 b₁

R =  1 0 1 1 a₂ , S = 1 1 0 b₂

1 0 0 1 a₃ 0 0 1 b₃

0 0 0 0 a₄ 0 0 1 b₄

0 0 0 1 a₅

Тогда композиция SR этих отношений представится матрицей

Функциональные отношения

Отношение RАВ называется функциональным, если для каждого аА сечение множества R по а содержит не более одного элемента. В функциональном отношении не существует пар с одинаковым левым элементом и различными правыми элементами, т.е. если (а,b)R и R - функциональное отношение, то в R не может быть пары вида (а,с), где bc.

Если отношение R-¹, обратное для функционального отношения R, также является функциональным, то отношение R называется взаимно однозначным.

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

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

Для всякого функционального отношения RАВ можно определить функцию, связанную с этим отношением. Для обозначения функции используется запись f:AB. Если (х,у)R, то это можно выразить как у=f(x), где х является аргументом, а у - значением функции f.

Множество {x/(x,y)R} называется областью определения функции f. Если это множество совпадает с А, то функция f является всюду определенной. Такая функция называется отображением множества А в В. В противном случае функцию называют частичной.

Множество {у/(x,y)R} называется областью значений функции f. Если область значений функции f совпадает с множеством В, то f называют отображением А на В, сюръективным отображением или сюръекцией. Обязательным условием существования отображения А на В является АВ.

Если функциональное отношение RАВ, определяющее функцию f, является взаимно однозначным, то функцию f называют инъективным отображением или инъекцией. В этом случае существует функция f -¹, которая является обратной к функции f. При этом если у=f(x), то х=f - ¹(у), а мощность области определения функции f не должна превышать В.

Функция f называется биективным отображением, или биекцией, если она является как сюръективным, так и инъективным отображением. Такое отображение называется еще 1-1 соответствием. На рис.1 даны схемы рассмотренных видов отображения.

Рис.1. Схемы функциональных отображений

Если R - взаимно однозначное отношение между элементами одного и того же множества, т.е. RАА=А², и, кроме того, R и R-¹ всюду определены, то отображение, связанное с R, называется подстановкой.

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

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

Отображение f:AB, где А и В - некоторые множества функций, называется оператором. Оператор преобразует одну функцию в другую.

Бинарные отношения на множестве

Пусть RАА. Определим некоторые свойства, которыми может обладать или не обладать такое отношение:

рефлексивность если a=b, то aRb;

иррефлексивность если aRb, то ab;

симметричность если aRb, то bRa;

антисимметричность если aRb и bRa, то a=b;

транзитивность если aRb и bRс, то aRс;

дихотомия если ab, то либо aRb, либо bRa.

Рассмотрим некоторые типы бинарных отношений, характеризуемые определенным тем или иным набором свойств.

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

Отношение совместимости рефлексивно и симметрично. Примерами отношения совместимости являются близость чисел, знакомство людей и т.п.

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

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

Множество М, на котором задано отношение порядка R (строгого или нестрогого), может быть полностью упорядоченным, если любые два элемента a и b из М находятся в отношении R, т.е. aRb или bRa. При этом говорят, что a и b сравнимы. Если М содержит хотя бы одну пару элементов с и d, для которых не имеет место ни cRd, ни dRc, то множество М является частично упорядоченным, а указанные элементы с и d несравнимы. Отношение полного порядка обладает свойствами иррефлексивности, антисимметричности и дихотомии. Полный порядок называют еще линейным или совершенным.

Для множества действительных чисел R отношения и являются отношениями полного порядка. Для семейства подмножеств некоторого множества М отношение является отношением частичного порядка. Например, {a₁,a₃}{a₁,a₂,a₃}, а подмножества {a₁,a₃} и {a₁,a₂,a₄} несравнимы.

Порядок букв в алфавите и естественный порядок цифр являются полными порядками. На основе порядка букв строится лексикографический порядок слов, используемый в словарях и определяемый следующим образом. Обозначим это отношение символом . Пусть имеются слова w₁=a₁₁a₁₂…a_1m и w₂=a₂₁a₂₂…a_2n. Тогда w₁w₂, если и только если либо w₁=pa_iq, w₂=pa_jr и а_ia_j, где p, q и r - некоторые слова, возможно, пустые, а а_i и a_j - буквы, либо w₂=w₁p, где р - непустое слово.

Например, учебникученик и морморе. В первом случае р=уче, а_i=б, а_j=н, q=r=ник, и в алфавите буква «н» стоит дальше буквы «б». Потому в словаре слово «ученик» следует искать после слова «учебник». Во втором случае w₁=мор и р=е. Согласно лексикографическому порядку слово «море» должно быть помещено в словаре после слова «мор».