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

ОТНОШЕНИЯ

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

x А, у А отношение Г = {(x,направляться)| 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, хх).

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

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.

Отношениемстрогого порядка именуется антирефлексивное ((х(y

((ху)(y(х

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

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

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

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

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

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

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

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

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

a ? b — axay ?bxby — линейный порядок.

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

z1 z2 — ((x1 x2) либо (x1 = x2) (y1y2).

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

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

Интуитивная топология | теоретикомнож. вопр. | двоичные отношения | отношение эквивалентности | 2


Также читать:

Понравилась статья? Поделиться с друзьями: