1.4. Декартово произведение множеств.

Рассмотрим некоторые дополнительные термины, характерные для операций над множествами.

Вектор – это упорядоченный набор элементов, другой синоним этого термина – “кортеж”.

Элементы, образующие вектор, называются координатами или компонентами вектора. Координаты нумеруются слева направо. Число координат называется длинной или размерностью вектора. Вектор будем заключать в круглые скобки, например (0, 5, 4, 5) иногда скобки и даже запятые опускаются.

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

Два вектора равны, если они имеют одинаковую длину и соответствующие координаты их равны иначе говорят, векторы (а₁, …..,а_m) и (b₁,…..,b_n) равны, если m=n и a₁=b₁, a₂=b₂,……., a_m=b_m.

Прямым (декартовым) произведением множеств А и В (обозначают А х В) называется множество всех пар (а, в), таких что аА и вВ. В частности, если А=В, то обе координаты принадлежат А. Такое произведение обозначается А². Аналогично прямым произведением множеств А₁, ….,А_n (обозначение А₁ х ….х А_n) называется множество всех векторов (а₁, …,а_n) длины n, таких, что а₁А₁….а_nА_n .А х А х…х А обозначается Аⁿ.

Пример 1. Множество R x R=R² – это множество точек плоскости, точнее пар (а, в), где а, вR и являются координатами точек плоскости.

Пример 2. А={а, в, c, d, e, f, g, h}, B={1, 2,….,8}тогда А х В ={a₁, a₂, a₃, …,h₇, h₈} – множество, содержащие обозначения всех 64 клеток шахматной доски.

Пример 3. Рассмотрим множество числовых матриц 3 х 4, т. е. матриц вида

а₁₁ а₁₂ а₁₃ а₁₄

а₂₁ а₂₂ а₂₃ а₂₄

а₃₁ а₃₂ а₃₃ а₃₄ ,

где а_ij принадлежит множеству R действительных чисел. Строки матрицы – это элементы множества R⁴ (векторы длинны 4). Сама матрица, рассматриваемая как упорядоченный набор ( т. е. вектор ) строк – это элемент множества (R⁴)³=R⁴ x R⁴ x R⁴. Компоненты матрицы, заданной таким образом – строки, а не числа. Поэтому (R⁴)³R¹². Содержательный смысл этого неравенства в том что в векторе R¹² не содержится никакой информации о строении матрицы, тот же вектор мог бы перечислять элементы 4 х 3 или 2 х 6, которые как математические объекты не совпадают с матрицами 3 х 4.

1.5. Отношения

Подмножество R Mⁿ называется n- местным отношением на множество М. Говорят, что а₁, …., а_n находится в отношении R, если (а₁,…..,а_n)R. Одноместное отношение это просто подмножество М. Такие отношения называют признаками: а обладает признаком R, если аR и RМ. Свойства одноместных отношений это свойства подмножеств М; поэтому для случая n=1 термин отношение употребляется редко. Примером трехместного отношения является множество троек нападающих в хоккейной команде. Каждый из нападающих находится в этом отношении со всеми теми игроками, с которыми он играет в тройке.

Наиболее часто встречаются и лучше всего изучены двухмерные или бинарные отношения. Записывают, что если а и в находятся в бинарном отношении R  а R в.

Пример. Отношение на N (где N – множество положительных чисел):

1. отношение выполняется для пар (7, 9) и (7, 7), но не выполняется для пар (9, 7).

2. отношение “иметь общий делитель, отличный от единицы” выполняется для пар (6, 9), (4, 2), (2, 4), (4, 4), но не выполняется для пар (7, 9) и (9, 7).

3. Отношение “быть делителем” а R в - а- делитель- в – выполняется для пар (2, 4) и (4, 4), но не выполняется для пар (4, 2) и(7, 9).

Пример. Отношения на множестве точек действительной плоскости:

1. отношение “находиться на одинаковом расстоянии от начала координат” выполняется для пар точек находящихся на одной и той же окружности с центром в начале координат.

2. отношение “находиться на разном расстоянии от начала координат” выполняется для тех и только тех пар точек, для которых не выполняется предыдущее отношение.

3. отношение “быть симметричным относительно оси Х” выполняется для всех пар точек (х₁y₁) и (x₂y₂), удовлетворяющих условию х₁ = х₂ и y₁ = -y₂.

Пример. Отношения на множестве людей “жить в одном городе”, “быть моложе”, “быть сыном”, “быть знаменитым”.

Пусть дано отношение R и М. Для любого подмножества М₁  М естественно определяется отношение R^’, называемое сужением R на М₁, которое получается из R удалением всех пар, содержащих элементы, не принадлежащие множеству М₁. Другими словами, R’=R  M₁². Строго говоря, R и R’ - это разные отношения с разными областями определения. Однако, если не возникает разночтений этот педантизм не соблюдается; например, вполне можно говорить “быть делителем” не уточняя, задано оно на N или каком-либо его подмножестве.

Для задания бинарных отношений можно использовать любые способы, задания множеств, например, список пар, для которых данное отношение выполняется. Отношение на конечных множествах обычно задаются списком или матрицей. Матрица, задающая бинарные отношения на множестве M={a₁, ….,a_m} – это квадратная матрица с порядком m, в которой элемент c_ij, стоящий на пересечении i-й строки и j-го столбца определяется следующим образом:

ij

 1, если a_i R a_j;

c_ij = 

 0 – в противном случае.

Например, для конечного множества {1, 2, …,6} матрицы отношений  , “имеет общий делитель”, “быть делителем” имеют вид:

1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6

1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1

2 0 1 1 1 1 1 2 0 1 0 1 0 1 2 0 1 0 1 0 1

3 0 0 1 1 1 1 3 0 0 1 0 0 1 3 0 0 1 0 0 1

4 0 0 0 1 1 1 4 0 1 0 1 0 1 4 0 0 0 1 0 0

5 0 0 0 0 1 1 5 0 0 0 0 1 0 5 0 0 0 0 1 0

6 0 0 0 0 0 1 6 0 1 1 1 0 1 6 0 0 0 0 0 1

Для любого множества М отношение Е, заданное матрицей, в которой по главной диагонали стоят единицы, а в остальных местах – нули, называется отношением равенства на М.

Поскольку отношение на М задаются подмножествами М², для них можно определить те же операции, что и над множествами.

Определим еще одну операцию над отношениями. Отношение является обратным к R ( обозначается R^-1), если a_i R^-1 a_j тогда и только тогда когда a_j R a_i. Так например, для отношения  обратным является .