Отношение эквивалентности




ОТНОШЕНИЯ

 

Отношениями называются соответствия между элементами одного и того же множества, то есть соответствия, у которых базисные множества совпадают:

x А, у А отношение Г = {(x,y)| P(x,y)}, P(x,y) какое-то утверждение (предикат).

Если (x,y) Г, то говорят, что х находятся в отношении Г к у.

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

Более строгое определение:

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

1) несущее множество А,

2) множество пар Г={(x,y)| x A, y A}, являющегося подмножеством квадрата несущего множества.

n-местное отношение, или n-арное (тернарное, кватернарное, …) отношение – это несущее множество А и множества кортежной размерностью n,являющегося подмножеством множества Аn.

Пример тернарного отношения: входить в «тройку игроков».

Если под отношением понимать просто множество кортежей (без несущего множества), то можно использовать все законы теории множеств. Универсальным множеством будет квадрат несущего множества, то есть множество всех возможных кортежей (когда каждый элемент находится в отношении к любому другому элементу).

Отношение можно определить также как двухместный предикат предметных переменных х, у, принимающего значение «истина», если (х, у) Г и значение «ложь», если не принадлежит.

Обозначения: (х, у) Г, у = Г(x), у = Гx или просто xГу, например, отношение равенства (х = у), отношение порядка (х < у).

Если (х, у) Г, то xГу принимает значение «истина», иначе – «ложь».

Если отношения заданы на дискретном множестве, их можно записывать в виде матрицы

Ai,j=

Отношение – частный случай соответствия, для него можно ввести обратные отношения, композицию отношений:

Г-1={(y,x)| (x,y) Г}, Г ◦ Δ = {(x,z) | y ((x,y) Г &(y,z Δ))}.

Вводят понятие «единичного элемента» Δ0 = {(x,x)} – «быть в отношении к самому себе». В матричном представлении это будет - главная диагональ).

 

 

Свойства бинарных отношений

 

1 Рефлексивность«находиться в отношении к самому себе»

хГх – истина (например, отношения х=x, х≤x, х≥x).

 

2 Антирефлексивность - «не быть в отношении к самому себе»

хГx - ложь (например, отношения х≠x, х<x, х>х).

Если множество не «рефлексивно», то это еще не значит что оно «антирефлексивно».

 

3 Симметричность «независимость от того, какой элемент первый, какой второй»

хГу – истина → уГх – истина (например, отношения х=у, х≠у).

 

4 Антисимметричность «не превосходить»

(хГу – истина) & (yГх – истина) → (х=у) (например, отношения х≤у, х≥у).

 

5 Асимметричность (несимметричность) «превосходить»

хГу – истина → уГх –ложь (например, отношения х<у, х>у).

 

6. Транзитивность «передаточность»

(хГу – истина) & (yГz – истина) → (хГz – истина) (например, отношения х=у, х<у, х>у, х≤у, х≥у, отношение х≠у транзитивностью не обладает).

 

СПЕЦИАЛЬНЫЕ БИНАРНЫЕ ОТНОШЕНИЯ

Рассмотрим «отношение эквивалентности», «отношение нестрогого порядка», «отношение строгого порядка» и «отношение доминирования».

 

Отношение эквивалентности

Отношением эквивалентности называется рефлексивное (х~x), симметричное ((х~y)=(y~x)), транзитивное ((х~у)&(y~z)→(х~z)) отношение.

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

Подмножество элементов, эквивалентных одному элементу, называется классом эквивалентности или смежным классом.

Любой элемент из класса называется представителем класса.

Свойства.

Все элементы в классе эквивалентны между собой.

Элементы из разных классов не эквивалентны.

Один элемент может входить только в свой класс.

Все множество можно представить как объединение классов.

Таким образом, множество классов эквивалентности или полная система классов образуют разбиение несущего множества. Напоминание: разбиение множества – это представление его в виде непересекающихся подмножеств.

Индекс разбиения – число классов эквивалентности.

Фактор-множество относительно отношения эквивалентности - это множество всех классов или представителей класса.

Мощность фактора-множества равна индексу разбиения.

 

Отношения порядка

Отношением порядка называют два вида бинарных отношений.

Отношением нестрогого порядка называется рефлексивное (х≥x), антисимметричное ((x≤y)&(y≤x)→ (x=y)), транзитивное ((х≥у)&(y≥z)→(х≥z)) отношение.

Говорят, что на множестве установлен нестрогий порядок. В понятия ≤, ≥ вкладывают более широкий смысл: не хуже – не лучше, не раньше – не позже и так далее. В теории множеств пример нестрого порядка - нестрогое включение (быть подмножеством другого множества0.

Отношением строгого порядка называется антирефлексивное ((х<x) - ложь), антисимметричное ((x<y)→(y<x)- ложь), транзитивное

((х>у)&(y<zх)→(х<z)) отношение.

Говорят, что на множестве установлен строгий порядок. В понятия <, > вкладывают более широкий смысл: хуже – лучше, раньше – позже и так далее. В теории множеств пример строго порядка - строгое включение (быть подмножеством другого множества и при этом не быть равным ему).

Упорядоченные множества

Множество называется линейно упорядоченным, если любы едва элемента можно сравнить)то есть сказать: больше, меньше или равно).

Множество действительных или целых чисел: классические примеры упорядоченного множества.

Если на множестве удается установить отношение порядка, но не для всех пар элементов, то такое множество называется частично упорядоченным.

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

Пример установление порядка:

a ≥b ↔(ax≥bx & ay ≥by) – частичный порядок,

a ≥b ↔|a| ≥|b| - линейный порядок,

a ≥ b ↔ axay ≥bxby - линейный порядок.

В комплексных числах иногда искусственно вводят

z1 > z2 ↔ ((x1 > x2) или (x1 = x2) & (y1>y2).

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

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

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-07 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: