順序関係と順序集合
集合$U$上の二項関係$Rxy$が次の性質を満たすとき，$Rxy$を$U$上の順序関係（半順序関係）と言う．
$\forall x Rxx$（反射律） $\forall x \forall y ((Rxy \land Ryx) \to x=y)$（反対称律） $\forall x \forall y \forall z ((Rxy \land Ryz) \to Rxz)$（推移律）
加えて次を満たすとき，$Rxy$を$U$上の線形順序関係（全順序関係）と言う．
$\forall x \forall y (Rxy \lor Ryx)$
集合$U$上に順序関係$Rxy$が定まっているとする．このときとくに$Rxy$に注目して集合$U$を扱う場合に，$U$を$Rxy$についての順序集合と言う．
たとえば，部分集合であるという関係$\subseteq$は順序関係である．したがって$\set{1,2,3}$の冪集合は$\subseteq$に関する順序集合である．つまり，
$\set{\emptyset,\set{1},\set{2},\set{3},\set{1,2},\set{2,3},\set{3,1},\set{1,2,3}}$
は順序集合であり，要素間で$\set{1}\subseteq\set{1,2}$といった順序づけが成り立っている．
順序に関する諸概念
$U$上に順序関係$\leq$が定まっているとする．また，$a \in U$，$X \subseteq U$とする．
- $a$は$X$の上界 $\iff$ $\forall x (x \in X \to x\leq a)$
- $a$は$X$の下界 $\iff$ $\forall x (x \in X \to a\leq x)$
- $a$は$X$の最大元 $\iff$ $a \in X \land \forall x (x \in X \to x\leq a)$
- $a$は$X$の最小元 $\iff$ $a \in X \land \forall x (x \in X \to a\leq x)$
- $a$は$X$の上限 $\iff$ $a$が$X$の最小上界（$X$の上界全体からなる集合の最小元）
- $a$は$X$の下限 $\iff$ $a$が$X$の最大下界（$X$の下界全体からなる集合の最大元）
- $a$は$X$の極大元 $\iff$ $\forall x ((x\in X \land a\leq x) \to x=a)$．すなわち$\lnot\exists x (x \in X \land a<x)$
- $a$は$X$の極小元 $\iff$ $\forall x ((x\in X \land x\leq a) \to x=a)$．すなわち$\lnot\exists x (x \in X \land x<a)$
$X$の上界が存在するとき，$X$は上に有界であると言い，$X$の下界が存在するとき，$X$は下に有界であると言う．$X$が上にも下にも有界であるとき，たんに「$X$は有界である」と言う．
なお，最大ならば極大だが，極大だからといって最大であるとは限らない．
上限も極大元も、いわば最大元の一般化と考えられる。上限は存在するとすれば一意であるから最大元と非常に似ているが、$X$内に入っていない。極大元は複数存在する場合があるからこの点は最大元と似ていないが、$X$内に入っているのでその点は最大元と似ている。
参考までに，それぞれの直観的な意味を考えてみると次のようになろう．
- $a$は$X$の上界……$a$は$X$を上から押さえつけている
- $a$は$X$の下界……$a$は$X$を下から支えている
- $a$は$X$の最大元……$a$は$X$のなかで一番大きい
- $a$は$X$の最小元……$a$は$X$のなかで一番小さい
- $a$は$X$の上限……$a$は$X$を上から押さえつけているもののなかで一番小さい
- $a$は$X$の下限……$a$は$X$を下から支えているもののなかで一番大きい
- $a$は$X$の極大元……$X$の要素のなかには$a$より大きいものはない
- $a$は$X$の極小元……$X$の要素のなかには$a$より小さいものはない