Релация

Релацията представлява препокриващо съпоставяне между елементи от две или повече множества.^[1] Всяко подмножество на декартовото произведение на множествата A₁, A₂,..., A_n (R ⊆ A₁xA₂x...xA_n) се нарича n-местна релация. Казваме, че наредената n-орка (a₁, a₂,..., a_n) принадлежи на релацията R ((a₁, a₂,..., a_n) ∈ R), когато е зададено правило за образуване на връзка между елементите a₁ ∈ A₁,...,a_n ∈ A_n.

Бинарна релация

Една релация се нарича бинарна (още двуместна или двучленна), когато представлява съпоставянето между елементите на две множества. Има два начина за записване на една бинарна релация, от които по-често се използва вторият:

• (a, b) ∈ R
• aRb

Записът aRb ⇔ P(a, b) се чете: a е в релация R с b, когато съществува връзка P(a, b) между елементите a и b.

Примери: R ⊆ AxB

• aRb ⇔ a и b имат еднакъв цвят
• aRb ⇔ a и b имат общи познати

Релация над декартов квадрат

Релация над декартовия квадрат на дадено множество А, представлява бинарната релация R ⊆ AxA.

Видове

• рефлексивна – ако ∀a∈A (a, а)∈R
• антирефлексивна – ако ∀a∈A (a, а) ∉ R
• симетрична – ако ∀a,b∈A, a и b са различни (a, b)∈R ⇒ (b, а)∈R
• антисиметрична – ако ∀a,b∈A, a и b са различни (a, b)∈R ∧ (b, а)∈R ⇒ a=b
• силно антисиметрична – ако за ∀a,b∈A е изпълнено точно едно от двете: (a, b)∈R или (b, а)∈R
• транзитивна – ако ∀a,b,c∈A ((a, b)∈R, (b, c)∈R ⇒ (a, c)∈R)

Примери: R ⊆ ℝxℝ

• aRb ⇔ a < b (антирефлексивна, силно антисиметрична, транзитивна)
• aRb ⇔ a е кратно на b (рефлексивна, антисиметрична, транзитивна)

Релация на еквивалентност

Казваме, че една релация над декартов квадрат е релация на еквивалентност, ако тя е рефлексивна, симетрична и транзитивна.

Примери: R ⊆ ℝxℝ

• aRb ⇔ a = b

Частична наредба

Казваме, че една релация над декартов квадрат е частична наредба, ако тя е рефлексивна, антисиметрична и транзитивна.

Примери: R ⊆ ℝxℝ

• aRb ⇔ a ≤ b

Строга частична наредба

Казваме, че една релация над декартов квадрат е пълна наредба, ако тя е антирефлексивна, силно антисиметрична и транзитивна.