0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Mirko Dec 15 '15 at 14:13
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.