2.6 Partially Ordered Sets

Let \(P\) be a non-empty set. A partial order relation in \(P\) is a relation symbolized \(\leq \) with the following properties for \(x,y,z\in P\):

i: \(x\leq x\) (reflexive)
ii: \(x\leq y\) and \(y\leq x\implies x=y\) (symmetric)
iii: \(x\leq y\) and \(y\leq z\implies x\leq z\) (transitivity)

Definition 2.34. A non-empty set \(P\) in which there is a partial order relation is called a partially ordered set,(sometimes called Poset).

Observe that any non-empty subset of a Poset is a Poset.

Example 2.35. \(P\) a collection of subsets of a universal set \(U\), let \(A\leq B\) means that \(A\subseteq B\) for all \(A,B\in P\).

Solution. Let \(A,B,C\in P\),then

i: \(A\leq A\), since \(A\subseteq A\).
ii: \(A\leq B\) and \(B\leq A\implies A=B\), since \(A\subseteq B\) and \(B\subseteq A\implies A=B\).
iii: \(A\leq B\) and \(B\leq C\implies A\leq C\) since \(A\subseteq B\) and \(B\subseteq C\implies A\subseteq C\).

Example 2.36. Let \(P\) be the set of all functions defined on a non-empty set \(X\). Let \(f\leq g\) mean \(f(x)\leq g(x)\) for every \(x\in X\).

Solution.

i: \(f(x)\leq f(x)\hspace {0.5cm} \forall x\in X\).
ii: \(f(x)\leq g(x)\) and \(g(x)\leq f(x)\implies f(x)=g(x)\).
iii: \(f(x)\leq g(x)\) and \(g(x)\leq h(x)\), then \(f(x)\leq h(x)\).

Example 2.37. Let \(P\) be the set \(\mathbb {R}\). Let \(x\leq y\) means \(x\) is less or equal \(y\). Then \((P,\leq )\) is a partial order relation.

Solution.

i: \(x\leq x,\hspace {0.5cm} \forall x\in \mathbb {R}\).
ii: \(x\leq y\) and \(y\leq x\implies x=y\).
iii: \(x\leq y\) and \(y\leq z\implies x\leq z\).

Example 2.38. Let \(P\) be the set of positive integers and let \(m\leq n\) mean that \(m\) divides \(n\).

Solution.

i: \(m\leq m,\hspace {0.5cm} \forall m\in \mathbb {N}\).
ii: \(m\leq n\) and \(n\leq m\implies m=n\).
iii: \(m\leq n\) and \(n\leq q\implies m\leq q\).

We now single out the order relations that have a fourth property:

iv: any two elements are comparable.

Definition 2.39. A partial order relation with property (iv) is called a totally ordered set. Sometimes a totally ordered set is called a chain.

[next] [prev] [prev-tail] [front] [up]

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.