Файл: Тема. Соотношения. Соответствия. Бинарные отношения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 08.11.2023
Просмотров: 60
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Тема. СООТНОШЕНИЯ. СООТВЕТСТВИЯ. БИНАРНЫЕ ОТНОШЕНИЯ
2.1. Соотношения Между элементами множеств могут устанавливаться различные взаимосвязи, обычно называемые соотношениями. Человек может соотноситься с профессией, зарплата – с должностью, наказание – с преступлением, оценка – сознанием. Для определения конкретного соотношения надо определить два множества множество (область) определения и множество (область) значений. Эти множества могут быть различными (как, например, отношение между множеством студентов группы и множеством полученных ими оценок) или одинаковыми (как, например, быть братом на множестве людей. Наиболее изученными и чаще всего используемыми являются так называемые бинарные, или двухместные, отношения. Определение 2.1. Бинарным, или двухместным, соотношением R называется подмножество упорядоченных пар ⟨a,b⟩ ∈ R декартова (прямого) произведения A×B, те. Говорят, что соотношение R задано на A×B . Очень часто все элементы принадлежат одному множеству Ат. е. R ⊆ А, или R ⊆ A
2
. Так, на множестве студентов группы могут быть заданы такие бинарные соотношения, как жить водной комнате общежития, быть моложе, быть земляком и т. д. Тогда говорят, что соотношение R задано на множестве А. Наравне с обозначением ⟨a,b⟩ ∈ R, R ⊆ A×B используется обозначение aρb, ρ ⊆ A×B. Факт того, что a и b не находятся в соотношении ρ записывается aρb. В общем случае могут рассматриваться местные (n-арные) соотношения это равно степени множества A×B и показывает, сколько элементов могут находиться в этом соотношении, например, соотношения между тройками элементов (тернарные) и т. д. Пример 2.1. Равенство x
2
+ y
2
= z
2
задает тернарное соотношение на множестве целых чисел. Соотношение является множеством, включающим все тройки чисел ⟨x,y,z⟩, удовлетворяющие данному равенству. Пустое соотношение X×X, если X=Ø. Тождественное соотношение X×X, l x
= {⟨x,x⟩ | x∈X} (главная диагональ множества X
2
). Определение 2.2. Если основным предметом изучения служат не множество точек на плоскости (не отдельные пары, находящиеся в соотношении, асами по себе соотношения, то множество точек, соответствующих элементам соотношения, называют графиком этого соотношения G(ρ). Таким образом, график – это совокупность упорядоченных пар, образующих подмножество R. Пример 2.2. Пусть ρ – есть соотношение в R с определяющим свойством
0≤x≤2, а σ – соотношение со свойством 0≤y≤1. Причем ρ ⊆ R×R, σ ⊆ R×R.
2.1. Соотношения Между элементами множеств могут устанавливаться различные взаимосвязи, обычно называемые соотношениями. Человек может соотноситься с профессией, зарплата – с должностью, наказание – с преступлением, оценка – сознанием. Для определения конкретного соотношения надо определить два множества множество (область) определения и множество (область) значений. Эти множества могут быть различными (как, например, отношение между множеством студентов группы и множеством полученных ими оценок) или одинаковыми (как, например, быть братом на множестве людей. Наиболее изученными и чаще всего используемыми являются так называемые бинарные, или двухместные, отношения. Определение 2.1. Бинарным, или двухместным, соотношением R называется подмножество упорядоченных пар ⟨a,b⟩ ∈ R декартова (прямого) произведения A×B, те. Говорят, что соотношение R задано на A×B . Очень часто все элементы принадлежат одному множеству Ат. е. R ⊆ А, или R ⊆ A
2
. Так, на множестве студентов группы могут быть заданы такие бинарные соотношения, как жить водной комнате общежития, быть моложе, быть земляком и т. д. Тогда говорят, что соотношение R задано на множестве А. Наравне с обозначением ⟨a,b⟩ ∈ R, R ⊆ A×B используется обозначение aρb, ρ ⊆ A×B. Факт того, что a и b не находятся в соотношении ρ записывается aρb. В общем случае могут рассматриваться местные (n-арные) соотношения это равно степени множества A×B и показывает, сколько элементов могут находиться в этом соотношении, например, соотношения между тройками элементов (тернарные) и т. д. Пример 2.1. Равенство x
2
+ y
2
= z
2
задает тернарное соотношение на множестве целых чисел. Соотношение является множеством, включающим все тройки чисел ⟨x,y,z⟩, удовлетворяющие данному равенству. Пустое соотношение X×X, если X=Ø. Тождественное соотношение X×X, l x
= {⟨x,x⟩ | x∈X} (главная диагональ множества X
2
). Определение 2.2. Если основным предметом изучения служат не множество точек на плоскости (не отдельные пары, находящиеся в соотношении, асами по себе соотношения, то множество точек, соответствующих элементам соотношения, называют графиком этого соотношения G(ρ). Таким образом, график – это совокупность упорядоченных пар, образующих подмножество R. Пример 2.2. Пусть ρ – есть соотношение в R с определяющим свойством
0≤x≤2, а σ – соотношение со свойством 0≤y≤1. Причем ρ ⊆ R×R, σ ⊆ R×R.
Тогда график соотношения ρ ∪ σ = {⟨x,y⟩ ∈ R×R | 0≤x≤2 или 0≤y≤1} представлен на риса график соотношения ρ ∩ σ = {⟨x,y⟩ ∈ R×R | 0≤x≤2 и
0≤y≤1} – на рис. 2.2. Причем график объединения или пересечения соотношений есть объединение или пересечение этих графиков.
Рис. 2.1 Рис. 2.2 Пример 2.3. Пусть ρ – это соотношение быть отцом. Если A – множество всех жителей России, то ρ(A) – множество всех людей, чьи отцы проживают в России. Пусть R ⊆ A×B определено в соответствии с рис. 2.3, из которого следует, что в соотношении R задействованы не все, а лишь некоторые элементы исходных множеств A и B.
Рис. 2.3 Определение 2.3. Областью определения соотношения ρ: D(ρ) между множествами A и B называется совокупность тех элементов из A, которые в качестве первого элемента входят хотя бы в одну из пар графика G(ρ,A,B), те. первая проекция pr
1
G графика G. Определение 2.4. Областью значений соотношения ρ: Q(ρ) называется pr
2
G, те. совокупность вторых элементов из пары, принадлежащих G(ρ,A,B). Определение 2.5. образом ρ(x), где X⊆A, называется подмножество из
B, определяемое следующим равенством
ρ(x)= {b | ∃ a∈X, ⟨a,b⟩ ∈ G}. Таким образом, область значений соотношения – это образ его области определения.
Определение 2.6. прообразом подмножества Y из множества B для соотношения ρ между A и B называется совокупность элементов из А обозначается ρ
-1
(Y)), для каждого из которых в В найдется хотя бы один элемент b, такой, что пара ⟨a,b⟩ принадлежит графику G: ρ
-1
(Y)={a | ∃ b∈Y ⟨a,b⟩
∈ R}, те. прообразом области значений соотношения ρ является область его определения.
0≤y≤1} – на рис. 2.2. Причем график объединения или пересечения соотношений есть объединение или пересечение этих графиков.
Рис. 2.1 Рис. 2.2 Пример 2.3. Пусть ρ – это соотношение быть отцом. Если A – множество всех жителей России, то ρ(A) – множество всех людей, чьи отцы проживают в России. Пусть R ⊆ A×B определено в соответствии с рис. 2.3, из которого следует, что в соотношении R задействованы не все, а лишь некоторые элементы исходных множеств A и B.
Рис. 2.3 Определение 2.3. Областью определения соотношения ρ: D(ρ) между множествами A и B называется совокупность тех элементов из A, которые в качестве первого элемента входят хотя бы в одну из пар графика G(ρ,A,B), те. первая проекция pr
1
G графика G. Определение 2.4. Областью значений соотношения ρ: Q(ρ) называется pr
2
G, те. совокупность вторых элементов из пары, принадлежащих G(ρ,A,B). Определение 2.5. образом ρ(x), где X⊆A, называется подмножество из
B, определяемое следующим равенством
ρ(x)= {b | ∃ a∈X, ⟨a,b⟩ ∈ G}. Таким образом, область значений соотношения – это образ его области определения.
Определение 2.6. прообразом подмножества Y из множества B для соотношения ρ между A и B называется совокупность элементов из А обозначается ρ
-1
(Y)), для каждого из которых в В найдется хотя бы один элемент b, такой, что пара ⟨a,b⟩ принадлежит графику G: ρ
-1
(Y)={a | ∃ b∈Y ⟨a,b⟩
∈ R}, те. прообразом области значений соотношения ρ является область его определения.
Определение 2.7. Соотношением, обратным к соотношению ρ, называется отношение между B и A, график которого получается из графика G соотношения ρ изменением порядка элементов внутри каждой пары, входящей в G. Иными словами, если G – график ρ, то R
-1
– график соотношения ρ
-1
, те тогда и только тогда, когда b ρ a. Например, Если R – быть моложе, то R
-1
– быть старше если R – быть подчиненным, то R
-1
– быть начальником. Замечание. Область определения соотношения, обратного к ρ, совпадает с областью значений ρ, область значений ρ
-1
совпадает с областью определения
ρ.
2.2. Отображения, соответствия, функция Исходя из определения соотношения, можно увидеть, что любой элемент из множества A может вступать в соотношение с одним или более элементами из множества B, те. в графике G могут быть следующие упорядоченные пары
{1
,b
1
>, 1
,b
3
>, 2
,b
4
>, …}. Наложим некоторое ограничение. Определение 2.8. Пусть ρ – некоторое соотношение между множествами
A и B. Если для любого элемента a∈A его образ, ρ(a), состоит ровно из одного элемента (∈B), то такое соотношение называется функциональным. Заметим, что с одними тем же элементом b∈B может находиться в соотношении любое количество a∈A. Определение 2.9. Если между элементами множества A и B установлено функциональное соотношение, то говорят, что задано отображение множества A вили функция (закон, правило, которая определена на A» и принимает свои значения в B». Чтобы в данном случае подчеркнуть функциональность соотношения между A и B, термин соотношение заменяют на соответствие. Этот закон, соотношение, функцию обозначают через f.
Рис. 2.4 Таким образом, соотношение f тогда и только тогда является функцией, когда оно удовлетворяет следующим требованиям
(1) элементами f являются упорядоченные пары
(2) если
B (f отображает A в B), f: A→B ⇔ ∀a∈A ∃ b∈B: b=f(a).
Поскольку функция является частным случаем соотношения, то для функции сохраняется смысл всех определений для соотношений. Пример 2.4.
1. Область определения f – множество A, область значений f – множество B.
2. b∈B, в котором отображен a∈A, называют образом элемента a при f и обозначают f(a). Элемент a в этом случае называют прообразом элемента f(a)
{b=f(a)}.
3. Графиком функции f: A→B является совокупность упорядоченных пар
{ | a∈A }.
4. Две функции f и g совпадают только тогда, когда совпадают их графики. Или, другими словами, D(f)=D(g); f(a)=g(a) для ∀ a ∈ D(f) и ∈ D(g). Определение 2.10. Отображение f
-1
называется обратным к отображению f, если a →
f b, b →
f −1 a, те. элементу b∈B ставится в соответствие тот a∈A, образом которого при отображении f является b: f
-1
: B →A ⇔ ∀ b∈B ∃ a∈A: a= f
-1
(b). Определение 2.11. Если f: X→Y и A⊆X, то f ∩ (A×Y) есть функция, определенная на A, со значениями в Y. Эту функцию называют сужением функции f на множество A и обозначают (f/A). То. (f/A)(a)=f(a) для ∀ a∈A. Аналогично, если g – сужение f и g ⊆ f, то функция f называется продолжением функции g. Определение 2.12. Если B = f(A), те. для ∀ b∈B ∃ a∈A, такое, что b=f(a), то говорят, что функция f есть отображение множества A на множество B и называют такое отображение сюръективным или сюръекцией. Определение 2.13. Если любой элемент из B имеет не более одного прообраза длят. е. f
-1
({b}) либо пусто, либо состоит из единственного элемента, то f называется взаимно-однозначным или инъективным отображением A в B (инъекцией. Определение 2.14. Если отображение A→
f
B является одновременно и инъективным и сюръективным, то оно называется биективным (биекцией): f – биекция ⇔ ∀ b∈B ∃ a∈A: b=f(a) ∀a
1
, a
2
∈A a
1
≠a
2
⇒ f(a
1
)≠f(a
2
).
2.3. Композиция функций. Функции принадлежности для подмножеств Рассмотрим два отображения (функции f : R→R, f(x)=2x+1 и g : R
+
→ R
+
, g(x) = √x . Из этой пары функций можно получить новую сложную функцию h: h(x) = g(f(x)). Так как D(g) = R
+
, то значения f(x) = 2x+1 > 0. Таким образом, комбинируя g и f, мы получаем новую функцию си. Определение 2.15. Композицией функций f и g (g°f) называется следующая совокупность упорядоченных пар { | ∃y, что xfy и ygz}. Например, если R – быть сыном, то R°R – быть внуком.
1. Область определения f – множество A, область значений f – множество B.
2. b∈B, в котором отображен a∈A, называют образом элемента a при f и обозначают f(a). Элемент a в этом случае называют прообразом элемента f(a)
{b=f(a)}.
3. Графиком функции f: A→B является совокупность упорядоченных пар
{ | a∈A }.
4. Две функции f и g совпадают только тогда, когда совпадают их графики. Или, другими словами, D(f)=D(g); f(a)=g(a) для ∀ a ∈ D(f) и ∈ D(g). Определение 2.10. Отображение f
-1
называется обратным к отображению f, если a →
f b, b →
f −1 a, те. элементу b∈B ставится в соответствие тот a∈A, образом которого при отображении f является b: f
-1
: B →A ⇔ ∀ b∈B ∃ a∈A: a= f
-1
(b). Определение 2.11. Если f: X→Y и A⊆X, то f ∩ (A×Y) есть функция, определенная на A, со значениями в Y. Эту функцию называют сужением функции f на множество A и обозначают (f/A). То. (f/A)(a)=f(a) для ∀ a∈A. Аналогично, если g – сужение f и g ⊆ f, то функция f называется продолжением функции g. Определение 2.12. Если B = f(A), те. для ∀ b∈B ∃ a∈A, такое, что b=f(a), то говорят, что функция f есть отображение множества A на множество B и называют такое отображение сюръективным или сюръекцией. Определение 2.13. Если любой элемент из B имеет не более одного прообраза длят. е. f
-1
({b}) либо пусто, либо состоит из единственного элемента, то f называется взаимно-однозначным или инъективным отображением A в B (инъекцией. Определение 2.14. Если отображение A→
f
B является одновременно и инъективным и сюръективным, то оно называется биективным (биекцией): f – биекция ⇔ ∀ b∈B ∃ a∈A: b=f(a) ∀a
1
, a
2
∈A a
1
≠a
2
⇒ f(a
1
)≠f(a
2
).
2.3. Композиция функций. Функции принадлежности для подмножеств Рассмотрим два отображения (функции f : R→R, f(x)=2x+1 и g : R
+
→ R
+
, g(x) = √x . Из этой пары функций можно получить новую сложную функцию h: h(x) = g(f(x)). Так как D(g) = R
+
, то значения f(x) = 2x+1 > 0. Таким образом, комбинируя g и f, мы получаем новую функцию си. Определение 2.15. Композицией функций f и g (g°f) называется следующая совокупность упорядоченных пар {
Операция композиции ассоциативна: f°(g°h)=(f°g)°h. Нов общем случае, не коммутативна (не выполняется закон коммутативности f°g ≠ g°f. Любое подмножество X⊆A можно однозначно определить с помощью числовой функции µ
x
, отображающей A в {0,1}:
µ
x
=
1, если а ∈ Х, если а ∉ Х,
где µ
x
– функция принадлежности или характеристическая функция подмножества X. Таким образом, операции над подмножествами можно заменить операциями на Действительно,
µ
x∪y
(a) = max{µ
x
(a), µ
y
(a)},
µ
x∩y
(a) = min{µ
x
(a), µ
y
(a)}. Аналогично, можно определить функцию принадлежности для графиков, функций. Например, для двуместного соотношения ρ между A и B:
∀ a∈A ∀ b∈B µ
R
=
1, если < a, b > ∈ R;
0, если < a, b > ∉ R,
2.4. Бинарные отношения Определение 2.16. Если соотношение ρ задано между элементами одного итого же множества, говорят, что между элементами данного множества задано отношение ρ. Итак, если задать на множестве А местное (n-арное) отношение, это значит выделить в й степени, А, этого множества некоторое подмножество, которое будет служить графиком этого отношения (арность – это количество элементов, находящихся в данном соотношении. Чаще всего на практике имеют дело с двуместными (бинарными) и трехместными (тернарными) отношениями. Определение 2.17. Говорят, что на множестве А задано бинарное отношение ρ, если в декартовом квадрате этого множества А выделена некоторая его часть R, называемая графиком бинарного отношения ρ, те. На бинарные отношения (БО) распространяются все определения, данные для соотношения. Так как А – это и область определения и область значения ρ, то теперь А называется областью задания отношения ρ. Назовем способы задания бинарного отношения. Пусть A={a
1
,a
2
,a
3
,a
4
} – область значения БОА. Задать бинарное отношение – это выделить подмножество R, в которое входят пары ∈ρ.
x
, отображающей A в {0,1}:
µ
x
=
1, если а ∈ Х, если а ∉ Х,
где µ
x
– функция принадлежности или характеристическая функция подмножества X. Таким образом, операции над подмножествами можно заменить операциями на Действительно,
µ
x∪y
(a) = max{µ
x
(a), µ
y
(a)},
µ
x∩y
(a) = min{µ
x
(a), µ
y
(a)}. Аналогично, можно определить функцию принадлежности для графиков, функций. Например, для двуместного соотношения ρ между A и B:
∀ a∈A ∀ b∈B µ
R
=
1, если < a, b > ∈ R;
0, если < a, b > ∉ R,
2.4. Бинарные отношения Определение 2.16. Если соотношение ρ задано между элементами одного итого же множества, говорят, что между элементами данного множества задано отношение ρ. Итак, если задать на множестве А местное (n-арное) отношение, это значит выделить в й степени, А, этого множества некоторое подмножество, которое будет служить графиком этого отношения (арность – это количество элементов, находящихся в данном соотношении. Чаще всего на практике имеют дело с двуместными (бинарными) и трехместными (тернарными) отношениями. Определение 2.17. Говорят, что на множестве А задано бинарное отношение ρ, если в декартовом квадрате этого множества А выделена некоторая его часть R, называемая графиком бинарного отношения ρ, те. На бинарные отношения (БО) распространяются все определения, данные для соотношения. Так как А – это и область определения и область значения ρ, то теперь А называется областью задания отношения ρ. Назовем способы задания бинарного отношения. Пусть A={a
1
,a
2
,a
3
,a
4
} – область значения БОА. Задать бинарное отношение – это выделить подмножество R, в которое входят пары ∈ρ.
Способы задания бинарных отношений. Для задания бинарных отношений могут быть использованы любые, рассмотренные ранее, способы задания множеств. Кроме того, отношения, определенные наконечных множествах, могут задаваться Способ 1. Списком (перечислением) пар, для которых это отношение выполняется
R ={1
,a
2
>,2
,a
3
>,2
,a
4
>}. Способ 2. Матрицей (c помощью функций принадлежности графика
µ
R
(a,b)). Бинарному отношению R ⊆ A×A, соответствует матрица размера n×m, в которой элемент c ij
, стоящий на пересечении й строки иго столбца, равен
1, если между аи имеет место отношение ρ, или 0, если его нет. Тогда матрица А примет вид (для R, указанного в способе 1): А =
0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 Способ 3. Направленным графом, те. структурой, состоящей из вершин и дуг (направленных ребер. Элементы множеств отображаются в виде вершин графа, а отношения – в виде дуг, соединяющих эти вершины. Два первых способа одинаково применимы как для отношений, заданных на разных множествах, таки для отношений на одном множестве. Третий способ больше подходит для отношений на одном множестве, т. к. позволяет получить более компактный граф. Способ 4. Если в качестве области задания бинарного отношения берется бесконечное множество, то задать график БО в явном виде нельзя. В этом случае описание БО представляется в виде свойств. Иногда, в этом случае, трудно представить график ρ. Пример 2.5. Пусть А. Задать в явном виде (списком, описанием характеристических свойств, матрицей и графом отношение R ⊆ А, если R означает – быть строго меньше. а) С использованием распознающей процедуры можно записать
R = {(a,b) | a, b ∈ A, aR 1 2 3 4 5 6 1 0 1 1 1 1 1 2 0 0 1 1 1 1 3 0 0 0 1 1 1 4 0 0 0 0 1 1 5 0 0 0 0 0 1 6 0 0 0 0 0 0 г) Граф отношения приведен на рис. 1.6.:
R ={1
,a
2
>,2
,a
3
>,2
,a
4
>}. Способ 2. Матрицей (c помощью функций принадлежности графика
µ
R
(a,b)). Бинарному отношению R ⊆ A×A, соответствует матрица размера n×m, в которой элемент c ij
, стоящий на пересечении й строки иго столбца, равен
1, если между аи имеет место отношение ρ, или 0, если его нет. Тогда матрица А примет вид (для R, указанного в способе 1): А =
0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 Способ 3. Направленным графом, те. структурой, состоящей из вершин и дуг (направленных ребер. Элементы множеств отображаются в виде вершин графа, а отношения – в виде дуг, соединяющих эти вершины. Два первых способа одинаково применимы как для отношений, заданных на разных множествах, таки для отношений на одном множестве. Третий способ больше подходит для отношений на одном множестве, т. к. позволяет получить более компактный граф. Способ 4. Если в качестве области задания бинарного отношения берется бесконечное множество, то задать график БО в явном виде нельзя. В этом случае описание БО представляется в виде свойств. Иногда, в этом случае, трудно представить график ρ. Пример 2.5. Пусть А. Задать в явном виде (списком, описанием характеристических свойств, матрицей и графом отношение R ⊆ А, если R означает – быть строго меньше. а) С использованием распознающей процедуры можно записать
R = {(a,b) | a, b ∈ A, aR 1 2 3 4 5 6 1 0 1 1 1 1 1 2 0 0 1 1 1 1 3 0 0 0 1 1 1 4 0 0 0 0 1 1 5 0 0 0 0 0 1 6 0 0 0 0 0 0 г) Граф отношения приведен на рис. 1.6.:
Рис. 1.6. Пример 2.6. Пусть А – любое непустое числовое множество, например,
A=R. аи находится в отношении равенства, если х=у. График этого отношения это прямая в задаваемая уравнением ух. б) x∈A и y∈A: отношение не меньше, если x ≥ y. График этого отношения представлен на рис. 2.5.
Рис. 2.5 Замечание. Если А ⊂ R, то бинарные отношения рассматривают как сужение бинарных отношений, заданных в R. Некоторые виды бинарных отношений a. Бинарное отношение на А называется тривиальным ε (эпсилон, если любая пара элементов из А находится в этом отношении, те. Его график А. Бинарное отношение на множестве А называется тождественным
ι (йота, если пары, находящиеся в этом отношении, состоят из одинаковых элементов ∀ a, b ∈ A, aιb : Его график диагональ в А ∆
A
{(a,a)}. c. Бинарное отношение, заданное на А, называется пустым ω (омега, если ни одна пара из Ане находится в этом отношении ∀ a, b ∈ A : a????b . График ∅. Свойства бинарных отношений Определение 2.18. Бинарное отношение ρ называется рефлексивным, если для любого элемента a ∈ А, этот элемент находится в отношении ρ с самим собой, те. Например, =, ≤, ≥. Замечание. Тождественное отношение всегда содержится в рефлексивном отношении, те. Определение 2.19. Бинарное отношение ρ, заданное на множестве А, называется симметричным, если из того что пара (а) находится в отношении
ρ, следует, что симметричная ей пара (b,a) также находится в отношении ρ, те. Примерили быть братом на множестве мужчин.
Определение 2.20. Бинарное отношение ρ, заданное на множестве А, называется асимметричным, если для ∀ a, b ∈ A, из того, что а находится в отношении ρ сне следует, что b находится в отношении ρ с ат. е.
∀ a, b ∈ A aρb ⇒ aρb. Пример 2.8. Отношения <, >. Определение 2.21. Бинарное отношение ρ, заданное на множестве А, называется антисимметричным если ∀ a, b ∈ A (a ≠ b) aρb => bρa, что эквивалентно ∀ a, b ∈ A aρb∧bρa => a=b. Таким образом, для антисимметричного отношения ρ утверждения aρb и bρa могут выполняться одновременно только для совпадающих элементов. Пример 2.9. Отношения ≤, ≥. Определение 2.22. Бинарное отношение ρ, заданное на множестве А, называется транзитивным, если ∀ a, b, c ∈ A : aρb ∧ bρa => aρc . Пример 2.10. Быть моложе, <, >, ≤, ≥, =. Определение 2.23. Бинарное отношение, обладающее свойствами рефлексивности, симметричности и транзитивности, называется отношением эквивалентности. Пример 2.11.
1. Равенство в произвольной системе множеств.
2. Отношение параллельности прямых во множестве прямых в евклидовой плоскости.
3. Отношение жить водном городе на множестве людей. Отношение эквивалентности имеет важную особенность эквивалентность ρ разбивает множество А, на котором оно задано, на непересекающиеся подмножества так, что элементы одного итого же подмножества находятся в отношении ρ, а между элементами разных подмножеств оно отсутствует. Определение 2.24. Если ρ – это отношение эквивалентности на множестве Х, то подмножество A ⊆ X называется классом эквивалентности (классом эквивалентности, если ∃ x ∈ A, что А совпадает с множеством всех у, для которых xρy. Совокупность различных классов эквивалентности является разбиением множества Х (расчлененное семейство, система классов эквивалентности по отношению ρ). Мощность этой системы называется индексом разбиения. Любое разбиение множества на классы определяет некоторое отношение эквивалентности, а именно отношение входить в один и тот же класс данного разбиения. Это очень важное утверждение, т. к. дает основание строго определить свойства рефлексивности, симметричности и транзитивности некоторых отношений. Например, что сказать об отношении, заданном нуль-графом с петлями Таким будет отношение жить водном городе на множестве, где все люди живут в разных городах, или отношение быть равным на множестве
∀ a, b ∈ A aρb ⇒ aρb. Пример 2.8. Отношения <, >. Определение 2.21. Бинарное отношение ρ, заданное на множестве А, называется антисимметричным если ∀ a, b ∈ A (a ≠ b) aρb => bρa, что эквивалентно ∀ a, b ∈ A aρb∧bρa => a=b. Таким образом, для антисимметричного отношения ρ утверждения aρb и bρa могут выполняться одновременно только для совпадающих элементов. Пример 2.9. Отношения ≤, ≥. Определение 2.22. Бинарное отношение ρ, заданное на множестве А, называется транзитивным, если ∀ a, b, c ∈ A : aρb ∧ bρa => aρc . Пример 2.10. Быть моложе, <, >, ≤, ≥, =. Определение 2.23. Бинарное отношение, обладающее свойствами рефлексивности, симметричности и транзитивности, называется отношением эквивалентности. Пример 2.11.
1. Равенство в произвольной системе множеств.
2. Отношение параллельности прямых во множестве прямых в евклидовой плоскости.
3. Отношение жить водном городе на множестве людей. Отношение эквивалентности имеет важную особенность эквивалентность ρ разбивает множество А, на котором оно задано, на непересекающиеся подмножества так, что элементы одного итого же подмножества находятся в отношении ρ, а между элементами разных подмножеств оно отсутствует. Определение 2.24. Если ρ – это отношение эквивалентности на множестве Х, то подмножество A ⊆ X называется классом эквивалентности (классом эквивалентности, если ∃ x ∈ A, что А совпадает с множеством всех у, для которых xρy. Совокупность различных классов эквивалентности является разбиением множества Х (расчлененное семейство, система классов эквивалентности по отношению ρ). Мощность этой системы называется индексом разбиения. Любое разбиение множества на классы определяет некоторое отношение эквивалентности, а именно отношение входить в один и тот же класс данного разбиения. Это очень важное утверждение, т. к. дает основание строго определить свойства рефлексивности, симметричности и транзитивности некоторых отношений. Например, что сказать об отношении, заданном нуль-графом с петлями Таким будет отношение жить водном городе на множестве, где все люди живут в разных городах, или отношение быть равным на множестве
натуральных чисел. Сам факт, что данное отношение разбивает множество на классы эквивалентности говорит о том, что оно симметрично и транзитивно, хотя граф не имеет ни одного ребра. Определение 2.25. Рефлексивные и симметричные бинарные отношения называются толерантными τ (тау. Отношение эквивалентности и толерантности – это результат математической формализации понятия сходства. Но решение многих практических задач связано с несходными объектами ранжирование объектов по каким-то признакам (приоритетам. Пример 2.12. Пусть множество A – это набор разноцветных шаров, а отношение ρ задается условием (a, b) ∈ R тогда и только тогда, когда a и b имеют одинаковый цвет. Поскольку ρ – отношение эквивалентности, каждый класс эквивалентности будет состоять из шаров, имеющих одинаковый цвет. Замечание. Из того, что отношение жить водном городе разбивает множество людей на непересекающиеся подмножества, те. является эквивалентностью, следует, что сточки зрения математики вполне естественно утверждение Иванов живет водном городе с самим собой как условие рефлексивности данного отношения. Такие утверждения, не вызывающие сомнения при работе с числами, например 1=1, выглядят непривычно, если элементами множеств являются люди. Определение 2.26. Отношением нестрогого порядка (или нестрогим порядком) называют бинарное отношение на множестве, если оно рефлексивно, антисимметрично, транзитивно. Определение 2.27. Отношением строгого порядка (строгим порядком, называют бинарное отношение на множестве, если оно антирефлексивно, антисимметрично, транзитивно. Оба эти отношения называются отношениями порядка. Например, отношение быть не старше на множестве людей, быть не больше на множестве натуральных чисел – нестрогий порядок. Отношения быть моложе, быть прямым потомком на множестве людей – строгий порядок. Элементы a, b сравнимы по отношению порядка ρ на А, если выполняется aρb или bρa. Множество А, на котором задано отношение порядка ρ, может быть
полностью упорядоченным множеством, если любые два элемента этого множества сравнимы по отношению порядка ρ;
частично упорядоченным множеством, если сравнимы лишь некоторые элементы этого множества. Пример 2.13. Отношения полного порядка на множестве людей – быть моложе, быть выше и т. д. Отношение частичного порядка на множестве людей
– быть начальником.
полностью упорядоченным множеством, если любые два элемента этого множества сравнимы по отношению порядка ρ;
частично упорядоченным множеством, если сравнимы лишь некоторые элементы этого множества. Пример 2.13. Отношения полного порядка на множестве людей – быть моложе, быть выше и т. д. Отношение частичного порядка на множестве людей
– быть начальником.