От решёток к булевым алгебрам. Султанбеков Ф.Ф. - 7 стр.

              §1. Отношения. Упорядоченные множества


  1.1. Отношением в множестве X называется любое подмножество α ⊆
X × X . В множестве всех отношений RX помимо теоретико-множественных
операций ∪, ∩,c , ⊆, \ рассматриваются еще композиция отношений и обрат-
ное отношение, определенные равенствами
                α ◦ β = {(x, y) : ∃ z ∈ X((x, z) ∈ α; (z, y) ∈ β)},
                           α−1 = {(x, y) : (y, x) ∈ α}.
Определим также множество ∆ = {(x, x) : x ∈ X}, называемое диагональю.
  1.2. Отметим легко проверяемые свойства этих операций:
a) ∆ ◦ α = α ◦ ∆ = α; b) α ⊆ β, γ ⊆ δ ⇒ α ◦ γ ⊆ β ◦ δ, α−1 ⊆ β −1 ;
c) α ◦ (β ◦ γ) = (α ◦ β) ◦ γ ; d) (α ◦ β)−1 = β −1 ◦ α−1 ;
e) (∪αi )−1 = ∪αi−1 , (∩αi )−1 = ∩αi−1 .
  1.3. Отношение α называется рефлексивным, если ∆ ⊆ α; симметричным,
если α−1 ⊆ α; антисимметричным, если α ∩ α−1 ⊆ ∆; транзитивным, если
α ◦ α ⊆ α; иерархичным, если α ◦ α−1 = X × X .
  Пусть α рефлексивно и транзитивно. Отношение α называется:
порядком, если оно антисимметрично; эквивалентностью, если оно симмет-
рично; направлением, если оно иерархично.
  Обозначим через OX (соотв. EX и N X ) множество всех порядков в X
(соотв. всех эквивалентностей и всех направлений в X ). Заметим, что с уче-
том 1.2 все включения (кроме рефлексивности) в определениях порядка, эк-
вивалентности и направления превращаются в равенства. Таким образом,
α ∈ OX ⇔ α ∩ α−1 = ∆ ⊆ α = α ◦ α, α ∈ EX ⇔ ∆ ⊆ α = α−1 = α ◦ α, α ∈
N X ⇔ ∆ ⊆ α = α ◦ α и α ◦ α−1 = X × X .
  Пара (X, α), где α порядок в X называется упорядоченным множеством
(у.м). Часто, когда ясно о каком порядке идет речь, и само X называют
упорядоченным множеством.
  1.4. Далее мы будем использовать также традиционную запись сравнения
двух элементов у.м (X, α): "(x, y) ∈ α ≡ x ≤ y ≡ y ≥ x". При этом x <

                                           7