Teljes rendezés (Total Order)

A teljes rendezés (angolul: total order vagy linear order) olyan reláció, amely egy részbenrendezés minden tulajdonságát teljesíti (reflexív, antiszimmetrikus, tranzitív), és ezen felül teljes is, azaz bármely két elem összehasonlítható.

Formális definíció

Legyen R egy reláció egy A halmazon. R teljes rendezés, ha:

• Reflexív: ∀a ∈ A: (a,a) ∈ R.
• Antiszimmetrikus: ∀a,b ∈ A: (a,b) ∈ R ∧ (b,a) ∈ R ⇒ a = b.
• Tranzitív: ∀a,b,c ∈ A: (a,b) ∈ R ∧ (b,c) ∈ R ⇒ (a,c) ∈ R.
• Teljesség (összemérhetőség): ∀a,b ∈ A: (a,b) ∈ R ∨ (b,a) ∈ R.

A teljesség biztosítja, hogy bármely két különböző elem közül az egyik megelőzi a másikat.

Példák teljes rendezésekre

• A ≤ reláció az egész számokon: reflexív, antiszimmetrikus, tranzitív és teljes.
• Az ábécésorrend a szavakon: bármely két szót összehasonlítható.
• A kronológiai sorrend a dátumokon: bármely két dátum közül az egyik korábbi a másiknál.

Ellenpéldák (nem teljes rendezések)

• Az oszthatóság reláció a természetes számokon: reflexív, antiszimmetrikus, tranzitív, de nem teljes (pl. 2 és 3 összehasonlíthatatlan).
• A részhalmaz ⊆ reláció a halmazokon: részbenrendezés, de nem teljes (pl. {1} és {2} összehasonlíthatatlan).
• A barátja reláció emberek között: nem antiszimmetrikus.

Teljes vs. részbenrendezés

Minden teljes rendezés egyben részbenrendezés is, de nem minden részbenrendezés teljes. A különbség az összemérhetőség: a részbenrendezésekben lehetnek összehasonlíthatatlan elemek, míg a teljes rendezésben minden elem összehasonlítható.

Összefoglalás

A teljes rendezés egy olyan reláció, amely rendezett sorrendet hoz létre a halmazon: reflexív, antiszimmetrikus, tranzitív és teljes. Ez az egyik legfontosabb fogalom a matematikában, hiszen a számok, betűk, dátumok és sok más adat természetes módon teljes rendezésben állnak.

Gyakorló feladat