Отношения на множествах

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

Отношение «быть братом» (аналогично, как и «быть сестрой») будет полностью определено, если мы составим список всех пар людей таких, что один из них брат второго. Предположим, что Татьяна, Александр и Михаил – дети одних и тех же родителей. Тогда на этом множестве из трех людей отношение «быть братом» выполнено для следующих пар:

«Александр – брат Татьяны»;

«Александр – брат Михаила»;

«Михаил – брат Татьяны»;

«Михаил – брат Александра».

В первом и третьем предложениях объекты (точнее – субъекты) нельзя поменять местами. Это означает, что отношение «быть братом», в общем случае не симметрично. Оно всегда и нерефлексивно, т.е. отношение «Александр – брат Александра» не выполняется (не имеет смысла).

В этом примере отношения рассматривались между объектами одного и того же множества – детьми одних и тех же родителей.

Отношения можно устанавливать и между объектами разных множеств. Так, если М₁ – множество студентов некоторого вуза, а М₂ – множество преподавателей того же вуза, то можно установить отношение «х –студент y», где х – один из студентов (элемент множества М₁), а y – один из преподавателей (элемент множества М₂). Ясно, что для одного и того же студента х это отношение может выполняться при разных y. И, наоборот, один и тот же преподаватель y имеет разных студентов x.

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

В математике отношения выражаются сказуемыми: …меньше, чем…, …больше, чем…, …равно…, …конгруэнтно…, …делится на… и многими другими. Хороший пример трехместных (тернарных) отношений представляют алгебраические операции. Например, отношение «образовывать сумму» применимо для троек чисел и выполняется в том случае, когда Пропорциональность чисел

есть отношение, выполненное для четверок чисел .

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

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

Пусть даны множества A и B. Рассмотрим множество всех упорядоченных пар элементов (кортежей) вида , где , Множество таких пар принято обозначать и называют декартовым произведением. Это множество образовано всеми упорядоченными парами, первые элементы которых принадлежат множеству А, а вторые – множеству B. Если то Если же то

Например, для множеств А = {1, 2} и B = {3, 4, 5} декартово произведение

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

Отношением Ф на множестве М называют подмножество множества Содержательный смысл такого определения состоит в том, что выбор подмножества Ф во множестве определяет, какие упорядоченные пары находятся в отношении Ф. При этом используют следующие обозначения. Если упорядоченная пара входит в Ф, т.е. то пишут что читается: «х находится в отношении Ф с у».

Следует отметить, что отношение – это не любое множество соответствующих пар, а подмножество множества пар при фиксированном М. Говоря формально, отношением называется упорядоченная пара где Таким образом, отношение – это пара где М – множество, на котором определено отношение (область определения отношения), а Ф – множество пар, для которых это отношение выполняется (область значений отношения). Множество М называют также областью задания отношения Ф, а множество пар Ф называется графиком отношения Как видим, определение графика в теории множеств есть именно то, к чему мы давно привыкли.

Приведенные выше записи отношений и требуют комментария. Привычные нам обозначения знаков математических отношений, такие как <, ≤, >, ≥ и др., исходят не от обозначения , а от в котором Ф заменено на соответствующий знак =, <, ≤ или ≥, ≠. В связи с этим могут возникнуть определенные недоразумения: с одной стороны Ф – это множество, но в записи отношения в конкретном случае символ Ф мы заменяем на соответствующий математический знак отношения =, <, ≤ и т.д., которые не представляют множество. Поэтому нужно иметь ввиду, что отношение , в котором Ф заменено на соответствующий математический знак, должно выполняться на всем множестве Ф.

Рассмотрим примеры. Пусть А = В = {0, 1, 2, 3, 4}. Декартово произведение этих множеств можно представить в виде квадратной матрицы, каждый элемент которой будет состоять из двух цифр. Первая цифра берется из множества А, вторая – из множества В.

. (1)

Исходя из (1), отношение равенства для элементов (цифр) множеств А и В будет определяться диагональной матрицей, являющейся частью . Каждый элемент диагональной матрицы будет содержать две одинаковые цифры. Обозначим ее символом е (от e quality – равенство)

е = . (2)

Отношение порядка а ≤ в будет представлять треугольную матрицу (обозначим ее о, order – порядок), также являющуюся частью

о = (3)

Отношение строгого порядка а < в представляет треугольную матрицу (обозначим ее символом s), являющуюся частью , имеет вид

s = (4)

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

Рассматривая в начале данного подраздела вербально выраженные отношения родства, например «Александр – брат Татьяны», мы отметили, что оно не симметрично, т.е. нельзя поменять местами Александра и Татьяну. В то же время отношение «Михаил – брат Александра» – симметрично. Это наталкивает на мысль, что для каждого отношения может существовать или не существовать обратное отношение.

Формально обратным отношением для Ф называется отношение Ф ^-1, записываемое в виде

ǀ .

Иначе говоря, обратное отношение Ф ^-1 образовано всеми теми упорядоченными парами (кортежами) , для которых существует кортеж выполнимый на множестве Ф. Так, например, обратным отношением е^{- 1} для отношения равенства е, определяемого матрицей (2) с областью определения (1), является оно само, т.е. е^{- 1} = е.

Обратным отношением порядка о^-1 для отношения о (т.е. а ≤ в), заданного матрицей (3), является отношение вида в ≤ а

о^-1 = .

Обратным отношением строгого порядка s^-1 для отношения s (т.е.вида а < в), заданного матрицей (4), является отношение вида в < а

s^-1 = .