Relacja spójna

Relacja spójna – typ relacji dwuargumentowej na jednym zbiorze definiowany dwojako – w sensie szerokim i wąskim; oba z nich dotyczą wiązania każdej pary elementów zbioru. Formalnie:

• relacja ${\displaystyle {\mathcal {R}}\subset X\times X}$ jest spójna, jeśli zachodzi alternatywa^[1][2]:

${\displaystyle \forall x,y\in X:\ (x,y)\in {\mathcal {R}}\,\lor \,(y,x)\in {\mathcal {R}}\,\lor x=y.}$

Oznacza to, że dla każdych dwóch różnych elementów ${\displaystyle x,y\in X}$ zachodzi ${\displaystyle x{\mathcal {R}}y}$ lub ${\displaystyle y{\mathcal {R}}x.}$ Inny zapis^[3]:

${\displaystyle x\neq y\Rightarrow x{\mathcal {R}}y\lor y{\mathcal {R}}x.}$

• Niektóre źródła podają definicję mocniejszą (węższą)^[4][5]:

${\displaystyle \forall x,y\in X:(x,y)\in {\mathcal {R}}\,\lor \,(y,x)\in {\mathcal {R}}.}$

Pociąga ona za sobą zwrotność.

Przez spójność definiuje się porządek liniowy.

Relacje spójne w sensie szerokim

• Każda relacja pełna.

• Relacja pusta na zbiorze pustym.

• Relacja ${\displaystyle \leqslant }$ na zbiorze liczb naturalnych. Jeśli weźmie się dowolne dwie liczby naturalne, to zawsze jedna z nich jest niewiększa od drugiej. Relacja ta spełnia też węższą definicję.

• Relacja ${\displaystyle <}$ na zbiorze liczb naturalnych spełnia tylko szerszą definicję.

Relacje niespójne

• Relacja pusta na zbiorze niepustym.

• Podzielność na zbiorze liczb naturalnych dodatnich. Na przykład żadna para różnych liczb pierwszych nie spełnia takiej relacji.

• Turniej (matematyka)
• Graf pełny

• Wojciech Guzicki, Piotr Zakrzewski: Wykłady ze wstępu do matematyki. Wprowadzenie do teorii mnogości. Warszawa: Wydawnictwo Naukowe PWN, 2005. ISBN 83-01-14415-7.
• Wiktor Marek, Janusz Onyszkiewicz: Elementy logiki i teorii mnogości w zadaniach. Wyd. 2. Warszawa: Państwowe Wydawnictwo Naukowe, 1975.
• Wacław Leksiński, Ireneusz Nabiałek, Wojciech Żakowski: Matematyka. Definicje, twierdzenia, przykłady, zadania. Wyd. 5. Warszawa: Wydawnictwa Naukowo-Techniczne, 1992, seria: Podręczniki akademickie. Elektronika, informatyka, telekomunikacja. ISBN 83-204-1892-5.
• Fritz Reinhardt, Heinrich Soeder: Atlas matematyki. Warszawa: Prószyński i S-ka, 2003. ISBN 83-7469-189-1.
• Barbara Stanosz: Ćwiczenia z logiki. Warszawa: Wydawnictwo Naukowe PWN, 2012. ISBN 978-83-01-14428-9.