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 ${\mathcal {R}}\subset X\times X$ jest spójna, jeśli zachodzi alternatywa:

$\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 $x,y\in X$ zachodzi $x{\mathcal {R}}y$ lub $y{\mathcal {R}}x.$ Inny zapis:

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

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

$\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.

Przykłady

Relacje spójne w sensie szerokim

• Każda relacja pełna.

• Relacja pusta na zbiorze pustym.

• Relacja $\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 $<$ 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.

Zobacz też

• Turniej (matematyka)
• Graf pełny

Bibliografia

• 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.