On the existence of a totally ordered set in a partially ordered set.

lattice-ordersorder-theoryreference-request

I can't find references regarding the following problem, could someone give me some suggestions or information?

From any partially ordered set we can extract a totally ordered set.

Definition$(\text{Partially and totally ordered set})$. A partially ordered set is a set $M$ on wich there is defined a partial orderig, that is, a binary relation which is written $\le$ and satisfies the conditions:

$$a\le a\;\text{for every}\;a\in M$$

$$\text{If}\;a\le b\;\text{and}\; b\le a,\;\text{then}\; a=b.$$

$$\text{If}\; a\le b\;\text{and}\;b\le c, \text{then}\;a\le c$$

"Partially" emphasizes taht $M$ may contain elements $a$ and $b$ for which neither $a\le b$ nor $b\le a$ holds. Then $a$ nad $b$ are called incomparable elements. In contrast, two elements $a$ and $b$ are called comparable elements if they satisfy $a\le b$ or $b\le a$ $(\text{or both}).$ A totally ordered set is a partially ordered set suh that every two elements of the set are comparable.

Therefore the problem is the following: give any partially ordered set $M$ we can find a set $P\subseteq M$ such taht $P$ is totally orderd?

Best Answer

Three things to note:

  1. a set with a single element is a totally ordered set. If $A= \{w\}$ then for all $a \in A$ then $a = w$ and $w\le w$. If $a,b\in M$ and $a\le b$ and $b \le a$ then $a=w$ and $b = w$ and $a=b$. ANd if $a\le b$ and $b \le c$ then $a=w; b=w; c=w$ and so $w \le w$ and so $a \le w$.

  2. the emptyset is a totally ordered set (by vacuous argument).

Therefore if $M$ is a partially ordered set then the empty set or (if $M$ is not empty) a set consisting of a single element will be a totally ordered set.

  1. Suppose $M$ is a partially ordered set with multiple elements but which contain no comparable different elements (That is if $a\in M$ then $a \le a$ but if $a, b\in M$ so that $a \ne b$ then neither $a\le b$ nor $b \le a$-- such a set is partially ordered as: if $a\le b$ then $a =b$ and same if $b\le a$, so if $a\le b$ and $b \le a$ that is only possible if $a=b$; and if $a\le b$ and $b\le c$ that is only possible of $a=b$ and $b=c$ and so $a=c$ and $a \le c$) the such a set can not have any multi-element totally ordered subset (because if $a,b\in P\subset M$ with $a\ne b$ then $a\not \le b$ and $b\not \le a$).

And from that that answers the question completely.

-Every partially ordered set will have the empty set as a totally ordered subset.

-A non empty partially ordered subset will have every singleton subset be a totally ordered subset.

-We have no guarantee there can be any other totally ordered subsets.

Related Question