# Undirected partially ordered sets

I know that, unlike totally ordered sets, partially ordered sets need not be directed. My understanding of directed is that for every $i$, $j$ in the set there exists a common upper bound $k$ s.t. $i \leq k$ and $j \leq k$ (where $\leq$ denotes some arbitrary partial ordering). However I can't think of an example of a partially ordered set which doesn't satisfy that.

So, what is an example of an undirected partially ordered set?

• a trivial two-element set the elements of which are not related. A less trivial example all points on the line $y=-x$ with relation $(p,q)\le(u,v)$ if both $p\le u$ and $q\le v$. – Mirko Dec 15 '15 at 14:13

For a simple non-trivial example, consider the set $Fin$ of all finite partial functions from $\mathbb{N}$ to $\mathbb{N}$. In other words each element of $Fin$ is a finite function with both the domain and range a subset of $\mathbb{N}$. Then $\subseteq$ on this set satisfies your requirements. While some pairs of elements have a common upper bound, any two functions $f, g$ such that $\exists n, n \in Dom(f) \wedge n \in Dom(g) \wedge f(n) \neq g(n)$ have no common upper bound. So because $f$ and $g$ both define but don't agree on the value at $n$, any element $h$ such that $f \subseteq h$, $g \subseteq h$, could not be a valid function.

If you look at the Wikipedia page for partially ordered sets, you will see that all we need to do is define a relation over the set that satisfies three conditions: reflexity, transitivity, antisymmetry. From this, we get that equality is in fact a partial order. That is, suppose we have a set $X$. Then the relation $\{(a, a) \;|\; a \in X\}$ is a partial order. Let's write $x \sim y$ whenever $(x, y) \in R$. Now, for any $X$ at all we can define this relation, which is a partial order, but it clearly does not have the property of directedness that you mention in your question, as long as $X$ has at least two distinct elements. To see why, just choose any two distinct elements, call them $x, y$. Then if there was some $z$ such that $x \sim z$ and $y \sim z$, then by the very definition of $R$, we'd have $x = z = y$, contradicting the distinctness of $x$ and $y$.