9.Отношения на множествах. 1 курс

Отношение - это одна из форм всеобщей взаимосвязи всех предметов, явлений, процессов в природе, обществе и
мышлении. Спектр отношений на множествах многоаспектен, начиная с определения понятия множества, аксиоматики
и заканчивая разбором парадоксов.

ОТНОШЕНИЕ - произвольное подмножество R множества Aⁿ всех упорядоченных наборов элементов вида
á(a₁,...,a_n), где a₁,...,a_n -элементы некоторого множества A; в этом случае говорят, что R есть n-местное отношение на A.
Понятие отношения служит в математике для выражения (на теоретико-множественном языке) связей между
объектами. Множество всех таких элементов a, которые входят хотя бы в один набор элементов, принадлежащий
отношению R называется полем этого отношения. Двухместные отношения называются бинарными. Если R - бинарное
отношение, то вместо á a, bñî R, часто пишут aRb. Частным случаем понятия отношения является соответствие.

Через î обозначается отношение принадлежности, т.е. x î A означает, что элемент x принадлежит множеству A.

Если x не является элементом множества A, то это записывается x ï A.

Два множества A и B считаются равными, если они состоят из одних и тех же элементов. Пишется A = B, если A и B равны, и A ╧ B в противном случае.

Через í обозначается отношение включения множеств, т.е. A í B означает, что каждый элемент множества A является элементом множества B. В этом случае A называется подмножествомB, а B - надмножествомA. Если A í B и A ╧ B, то A называется собственным подмножеством B, и в этом случае пишем A ì B.

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

Объединением (ДИЗЪЮНКЦИЕЙ, СУММОЙ) множеств A и B называется множество

Пересечением (КОНЪЮНКЦИЕЙ) множеств A и B называется множество

Разностью множеств A и B называется множество

Симметрической разностью множеств A и B называется множество

Мощностью (или КАРДИНАЛЬНЫМ ЧИСЛОМ) множества называется количество элементов в нем.

Некоторое, общее для всех множеств данной мощности, надмножество, называется универсальным множеством или УНИВЕРСУМОМ и обозначается обычно как U. Разность U \ A называется дополнением множества A и обозначается через -A.

Соответствие, бинарное отношение между двумя множествами A и B - произвольное подмножество Rдекартова произведенияA ╢B.

Если a îA, b î B и (a, b) î R, то пишут также R(a, b) или aRb. Если R = æ - пустое множество, то соответствие называется пустым, а если R = A ╢ B, то соответствие называется полным.

Пусть R í A ╢ B. Областью определения Dom R называется множество элементов a î A, для каждого из которых найдется хотя бы один элемент b î B такой, что aRb. Областью значений, или образом, Im R соответствия R называется множество элементов b î B, для каждого из которых найдется хотя бы один элемент a îA такой, что aRb. Соответствие R называется всюду определенным, если Dom R = A, и сюръективным, если Im R = B.

Для каждого a îA множество элементов bî B таких, что aRb, называется образом a относительно R и обозначается im_Ra. Прообразом элемента b î B относительно R называется множество элементов a î A таких, что aRb; прообраз обозначается coim_Rb. Ясно, что

Каждое соответствие однозначно определяет функцию a (r) im_Ra, которая отображает множество A в множество подмножеств B. Обратно, всякая функция f из множества A в множество подмножеств B определяет некоторое соответствие R(f): aR(f)b тогда и только тогда, когда b îf(a). Указанные сопоставления взаимно однозначны, что позволяет рассматривать соответствия как частично определенные многозначные функции.

Для конечных множеств A и B широко используются матричное и графовое представления соответствия. Пусть A = {a₁, a₂, ..., a_n}, B = {b₁, b₂, ..., b_m} и R í A ╢B. Соответствию R сопоставляется матрица размера n ╢ m, строки которой помечены элементами из A, столбцы - элементами из B , а на пересечении строки a_i и столбца b_j стоит 1, если a_i R b_j, и 0 в противном случае. Например,

Каждая матрица подобного вида однозначно определяет соответствие между A и B.

При графовом представлении элементы множеств A и B изображаются точками на плоскости. Обычно эти точки обозначаются теми же символами, что и соответствующие элементы. Точки a и b соединяются направленной дугой от a к b, если aRb

Различных отношений на множестве бесконечно. Но, когда говорят об отношениях одних множеств по сравнению с другими, то как правило подразумевают отношение эквивалентности множеств и свойств анализируемых множеств.

Отношение эквивалентности множеств характеризуется следующими свойствами:

Рефлексивность - это одно из свойств некоторых отношений, когда каждый элемент множества находится в данном отношении к самому себе. Например отношения между числами а = с и а ³ с рефлексивны, так как всегда а = а, с = с, а ³ а, с ³ с. Но отношение неравенства а > с антирефлексивно, так как неравенство а > а невозможно.

Аксиома рефлексивности записывается так: aRc ® aRa ù cRc , здесь ® означает слово "влечёт" ("имплицирует"), а знак ù - союз "и" (конъюнкция).

Из этой аксиомы следует: если суждение aRc истинно. то истинны и суждения aRa и cRc.

Симметричное отношение - это такое отношение между объектами, когда наличие этого отношения влечё за собой наличие этого отношения и в том случае, если объекты поменять местами; иначе говоря при счимметричном отношении перестановка объектов не ведёт к изменению вида отношения. Например, отношение равенства а = с симметрично, так как оно эквивалентно (равносильно) отношению с = а , си мметрично и отношение а ¹ с , так как оно эквивалентно отношению с ¹ а.

Транзитивное множество - это такое множество, например множдество х, если выполняется следующее требование: у î х, z î y ® z î x где ® это знак, представляющий слова: " если ..., то ..." Читается формула так: Если у принадлежит х, z принадлежит у, то z принадлежит х".