Hlutröðunarvensl

Hlutröðunarvensl eru vensl sem skilgreina röðun staka í mengi. Hlutröðunarvensl eru sjálfhverf, andsamhverf og gegnvirk. Mengi ásamt hlutröðunarvenslum er kallað ýmist raðað mengi, raðmengi, hlutraðað mengi eða hlaðmengi.

Mengi allra hlutmengja af {x, y, z}, raðað eftir þátttöku stakanna.

Tvö stök, a og b, í raðmengi $(S,R)$ eru sögð sambærileg ef að $aRb$ eða $bRa$. Ef að hvorugt gildir eru þau sögð ósambærileg.

Ef að $(S,R)$ er raðmengi og sérhver tvö stök eru sambærileg er raðmengið sagt alraðað eða línulega raðað, og $R$ er kölluð alröðunarvensl. Alröðuð mengi eru gjarnan kallaðar keðjur.

Mengi er sagt vel raðað ef að sérhvert hlutmengi þess sem er ekki tómamengið hefur minnsta stak. Velröðun er forsenda þrepasönnunar.

Hlutröðunarvenslum má lýsa með Hasse-myndum.

Dæmi

Náttúrlegu tölurnar eiga sér raðvenslin $\geq$. Þá er $(\mathbb {N} ,\geq )$ raðmengi þar sem að:

• $\forall a\in \mathbb {N} :a\geq a$ (sjálfhverf)
• Ef $a\geq b$ og $b\geq a$, þá $a=b$ (andsamhverf)
• Ef $a\geq b$ og $b\geq c$, þá $a\geq c$ (gegnvirk)
• Náttúrlegu tölurnar eru vel raðaðar.

Að sama skapi eru hlutmengjavenslin $\subseteq$ hlutröðun á mengjum:

• Fyrir öll mengi A gildir: $A\subseteq A$ (sjálfhverf)
• Ef $A\subseteq B$ og $B\subseteq A$, þá $A=B$ (andsamhverf)
• Ef $A\subseteq B$ og $B\subseteq C$, þá $A\subseteq C$ (gegnvirk)

Stafrófsröð er annað dæmi um velröðun.