---
# System prepended metadata

title: Poset
tags: [poset, math]

---

{%hackmd @RintarouTW/About %}

# Poset

## Partial Ordering

$$
(L,\preceq) \text{ is called a poset.}\\\implies
\preceq \text{is a partial ordering on a set } L \text{ and }\\\cases{ \forall a\in L, a\preceq a\text{ (reflexive)}\\\forall a,b \in L, a\preceq b\text{ and }a\not= b\implies b\npreceq a \text{ (antisymmetric)}\\ \forall a,b,c\in L, a\preceq b\text{ and } b\preceq c \implies a\preceq c \text{ (transitive)}}
$$

:::info
Under this relation$(L,\preceq)$, we may find $lub(a,b)=a\lor b$ and $glb(a,b)=a\land b$ forl $a,b \in L$ if exist.
:::

## Lower Bound, Upper Bound

$(L,\preceq)$ is a poset, 
$a,b,c,d \in L,$
$c\text{ is the lower bound of }a,b \implies c\preceq a\text{ and } c\preceq b,$
$d$ is an upper bound of $a,b\implies
a\preceq d\text{ and }b\preceq d$

## Greatest Lower Bound (glb)

$(L,\preceq)$ is a poset, 
$a,b,l,l'\in L$, $l$ is the greatest lower bound of $a,b$ $\iff \cases{l\preceq a\\l\preceq b\\\text{if }l'\preceq a\text{ and }l'\preceq b\implies l'\preceq l}$

## Least Upper Bound (lub)

$(L,\preceq)$ is a poset, 
$a,b,u,u'\in L$, $u$ is the least upper bound of $a,b$ $\iff \cases{a\preceq u\\b\preceq u\\\text{if }a\preceq u'\text{ and }b\preceq u'\implies u\preceq u'}$

:::info
GLB and LUB are unique if exist
could be proved by antisymmetric
$l\preceq l'\text{ and }l'\preceq l\implies l=l'$
:::

## Greatest Element and Least Element

$(L,\preceq)$ is a poset, 

$M \in L$ is the greatest element $\iff \forall a\in L, a\preceq M$, (denoted by **1**)

$m \in L$ is the least element $\iff \forall a\in L, m\preceq a$ (denoted by **0**)

## Examples

### The set of divisors of an integer $n$ ($D_n$)

$D_{105}$ = {1, 3, 5, 7, 15, 21, 35}
($D_{105}$,$\mid$) is a poset

```graphviz
graph {
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
105--35,21,15;
35--7,5;
15--5,3;
21--7,3;
7--1;
5--1;
3--1;
}
```

### The power set of a set

$A$ = {a, b, c}
$\mathcal{P}(A)$ = {$\varnothing$, {a}, {b}, {c}, {a,b},{a,c},{b,c},{a,b,c}}

($\mathcal{P}(A),\subseteq$) is a poset

```graphviz
graph {
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
"{a,b,c}"--"{a,b}","{a,c}","{b,c}";
"{a,b}"--"{a}","{b}";
"{a,c}"--"{a}","{c}";
"{b,c}"--"{b}","{c}";
"{a}","{b}","{c}"--0;
}
```

###### tags: `math` `poset`