Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was reviewing my old Discrete Mathematics notes, and I came across a section describing how Partial Orderings are identified. I understand this, but I can't seem to recall/find information on why partial orderings are important.

What is the significance of knowing whether a set is partially ordered?

share|improve this question
2  
If you have a partially ordered set such that every chain has an upper bound, then you can apply the magical Zorn's lemma. There's a lot of proofs out there that first defines a "funny" partial order on some set, then applies Zorn's lemma to get the result. –  Fredrik Meyer Mar 28 '11 at 18:08
3  
@Frederik: Part of the respect that the AC is given comes from the fact that one hears it referred to as magical in one's mathematical youth. I think that Zorn's lemma is quite natural (if there are no maximal elements, you can always continue an increasing chain by extending it a bit more and so on...) and its magicalness is really cultural and of historical origin... –  Mariano Suárez-Alvarez Mar 28 '11 at 18:41

4 Answers 4

up vote 4 down vote accepted

The most common partial order is the ordering by inclusion of subsets of a set $X$. The subsets are only partially ordered, since it is possible in general to have two subsets $A$ and $B$ of $X$ for which you neither have $A\subseteq B$ nor $B\subseteq A$.

This occurs even when you restrict yourself to special kinds of subsets: the collection of all subspaces of a vector space; the collection of all subgroups of a group; the collection of all subextensions of a field extension; the collection of all subvarieties of an algebraic variety; the collection of all linearly independent subsets of a vector space; etc.

One important situation is when one has a task to complete, and there are several ways to "get started", or several ways of "partially completing" the task. For example, you may be in a vector space and you want to find a basis. You can start by taking any nonzero vector, then pick a different vector not in the span, then a different one, etc. This gives you a "maze" of paths towards completing a full choice of basis. You can think of this maze as a partially ordered set (by ordering the linearly independent subsets by inclusion). A very powerful and useful result about (some) partially ordered sets is Zorn's Lemma, that tells you that under certain circumstances, you can be assured that there is at least one way of "completing the task", even if it would take infinitely many steps and there are many choices at each step.

Generally speaking, partially ordered sets are ubiquitous, so the more you know about them the better. Much like positive integers: they show up all over the place, and often you want to do things with them, so you better know what they are and what you can do.

share|improve this answer

Lots of sets one encounters in practice have naturally defined relations that want to be orders but are not total. For example, the subsets of a set are naturally comparable by inclusion, but that relation is not total at all in general. Similarly, integers come with the very natural relation of divisibility which behaves like an order but, again, is not total. There are many, many examples...

share|improve this answer

Partially ordered sets have many useful properties. Often, they can be made into lattices or boolean algebras by the addition of appropriate boolean "meet" and "join" operations.

share|improve this answer

A partial order is an abstraction of the concept of 'order' everyone is familiar with, like the one on the integers, the reals, etc. Altough this is a bit misleading because those orders are in fact 'total': any two elements can be compared.

But in fact lots of 'orders', such as total orders, are posets satisfying additional axioms. Another example is a well-order, the habitat of transfinite induction, which is an extension of induction on $\mathbb{N}$.

A poset in which any two elements have an upper bound is called a directed set. A function from a directed set is called a net, and this is a generalization of a sequence. Nets are quite useful in topology/functional analysis.

Every poset is a category, if we take as objects the elements of the poset, and if we take exactly one arrow from $a$ to $b$ if and only if $a\leq b$. Composition is defined beause of transitivity, and the existence of an identity arrow corresponds to reflexivity. Many basic concepts in category theory can be illuminated by this special choice of category. But of course this is only useful if you already know/care about posets in the first case.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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