Difference between revisions of "Partially ordered set"
m |
|||
| Line 12: | Line 12: | ||
==Simple examples== | ==Simple examples== | ||
| − | We don't verify that the properties stated above hold for these orderings -- a good | + | We don't verify that the properties stated above hold for these orderings -- a good exercize would be to prove that each of the three properties hold for the following examples. |
| − | * The set of [[positive]] [[integer]]s has a very natural ordering: we say <math>x \leq y</math> if <math>y</math> is bigger | + | * The set of [[positive]] [[integer]]s has a very natural ordering: we say <math>x \leq y</math> if <math>y</math> is bigger than <math>x</math>, in the sense of further to the right on a [[number line]] (or further away from zero). This is the [[mathematical convention | conventional]] ordering of the positive integers inherited from <math>\displaystyle \mathbb{Z}</math>. It has the special property that any two elements are directly [[comparable]] -- note that this is not required of a poset in general. Those posets in which every two elements are comparable are known as [[totally ordered set]]s. |
* The [[Boolean lattice]] over a set <math>S</math> is the poset <math>P = (\mathcal{P}(S), \leq)</math> where <math>\mathcal{P}(S)</math> is the [[power set]] (that is, the set of [[subset]]s) of <math>S</math> and for <math>x, y \in \mathcal{P}(S)</math>, <math>x \leq y</math> if and only if <math>x \subseteq y</math>. For instance, if <math>S = \{1, 2, 3\}</math> then the poset <math>P</math> has 8 elements among which we have the following relations: | * The [[Boolean lattice]] over a set <math>S</math> is the poset <math>P = (\mathcal{P}(S), \leq)</math> where <math>\mathcal{P}(S)</math> is the [[power set]] (that is, the set of [[subset]]s) of <math>S</math> and for <math>x, y \in \mathcal{P}(S)</math>, <math>x \leq y</math> if and only if <math>x \subseteq y</math>. For instance, if <math>S = \{1, 2, 3\}</math> then the poset <math>P</math> has 8 elements among which we have the following relations: | ||
| − | + | :* <math>\emptyset</math> is a minimal element of the poset; every other element is larger. | |
| − | + | :* <math>S = \{1, 2, 3\}</math> is a maximal element: every other element is smaller. | |
| − | + | :* Among the other 6 elements, we have the relations <math>\{1\} \leq \{1, 2\}</math>, <math>\displaystyle \{1\} \leq \{1, 3\}</math>, <math>\{2\} \leq \{1, 2\}</math>, <math>\{2\} \leq \{2, 3\}</math>, <math>\{3\} \leq \{1, 3\}</math>, and <math>\{3\} \leq \{2, 3\}</math>, and no others. | |
| − | |||
| − | * There are alternative orderings of the positive integers: for example, one might take the poset <math>P = (\mathbb{Z}, \leq)</math> where <math>n \leq m</math> if and only if <math>n | m</math>. Under this ordering, the positive integers still have a minimal element (1, which divides everything) but are no longer totally ordered. In particular, neither <math>2 | 3</math> nor <math>3 | 2</math>, so the elements 2 and 3 (and in general any pair of [[relatively prime]] integers | + | * There are alternative orderings of the positive integers: for example, one might take the poset <math>P = (\mathbb{Z}_{> 0}, \leq)</math> where <math>n \leq m</math> if and only if <math>n | m</math>. Under this ordering, the positive integers still have a minimal element (1, which divides everything) but are no longer totally ordered. In particular, neither <math>2 | 3</math> nor <math>3 | 2</math>, so the elements 2 and 3 (and in general any pair of [[relatively prime]] integers not including 1) are [[incomparable]]. |
==A more involved example== | ==A more involved example== | ||
Let <math>R</math> be the set of [[well-formed formula]]s of [[Peano arithmetic]]. In other words, <math>S</math> is the set of all arithmetic statements. We know that some of these statements are provably equivalent to each other. So, let <math>S</math> be the set of [[equivalence class]]es of <math>R</math> under the relation of provable equivalence. Let <math>\hat 0</math> denote the set of statements which are provably false, i.e. whose negations are provable, and let <math>\hat 1</math> denote the set of provable statements. By [[Godel's First Incompleteness Theorem]], there exists at least one (and in fact infinitely many) formulas which do not fall into either of these two categories. So, let <math>P = (S, \leq)</math> be the poset such that for <math>\mathbf{x, y} \in S</math>, <math>\mathbf{x} \leq \mathbf{y}</math> if and only if <math>\exists x \in \mathbf{x}, y \in \mathbf{y}</math> such that the formula <math>x</math> provably implies the formula <math>y</math>. That this is in fact a poset follows immediately by the properties of logical implication. This poset has other interesting properties, as well. | Let <math>R</math> be the set of [[well-formed formula]]s of [[Peano arithmetic]]. In other words, <math>S</math> is the set of all arithmetic statements. We know that some of these statements are provably equivalent to each other. So, let <math>S</math> be the set of [[equivalence class]]es of <math>R</math> under the relation of provable equivalence. Let <math>\hat 0</math> denote the set of statements which are provably false, i.e. whose negations are provable, and let <math>\hat 1</math> denote the set of provable statements. By [[Godel's First Incompleteness Theorem]], there exists at least one (and in fact infinitely many) formulas which do not fall into either of these two categories. So, let <math>P = (S, \leq)</math> be the poset such that for <math>\mathbf{x, y} \in S</math>, <math>\mathbf{x} \leq \mathbf{y}</math> if and only if <math>\exists x \in \mathbf{x}, y \in \mathbf{y}</math> such that the formula <math>x</math> provably implies the formula <math>y</math>. That this is in fact a poset follows immediately by the properties of logical implication. This poset has other interesting properties, as well. | ||
Revision as of 15:52, 9 February 2007
A partially ordered set 
is a pair, 
of a set 
whose elements are called the elements or vertices of and an order relation 
which obeys the following rules:
- Reflexivity:
for all 
- Anti-symmetry:
and 
if and only if 
- Transitivity: if and
then 
for all 
and 
if and only if 
then 
The name "partially ordered set" is often abbreviated poset.
Sometimes, we abuse notation and use the same letter for the poset itself and its set of vertices.
Simple examples
We don't verify that the properties stated above hold for these orderings -- a good exercize would be to prove that each of the three properties hold for the following examples.
- The set of positive integers has a very natural ordering: we say if
is bigger than 
, in the sense of further to the right on a number line (or further away from zero). This is the conventional ordering of the positive integers inherited from 
. It has the special property that any two elements are directly comparable -- note that this is not required of a poset in general. Those posets in which every two elements are comparable are known as totally ordered sets.
. It has the special property that any two elements are directly - The Boolean lattice over a set
is the poset 
where 
is the power set (that is, the set of subsets) of and for 
, if and only if 
. For instance, if 
then the poset 
has 8 elements among which we have the following relations:
where 
is the 
, 
. For instance, if 
then the poset 
is a minimal element of the poset; every other element is larger.- is a maximal element: every other element is smaller.
- Among the other 6 elements, we have the relations
, 
, 
, 
, 
, and 
, and no others.
is a minimal element of the poset; every other element is larger.
, 
, 
, 
, 
, and 
, and no others.- There are alternative orderings of the positive integers: for example, one might take the poset
where 
if and only if 
. Under this ordering, the positive integers still have a minimal element (1, which divides everything) but are no longer totally ordered. In particular, neither 
nor 
, so the elements 2 and 3 (and in general any pair of relatively prime integers not including 1) are incomparable.
where 
if and only if 
. Under this ordering, the positive integers still have a minimal element (1, which divides everything) but are no longer totally ordered. In particular, neither 
nor 
, so the elements 2 and 3 (and in general any pair of
A more involved example
Let 
be the set of well-formed formulas of Peano arithmetic. In other words, is the set of all arithmetic statements. We know that some of these statements are provably equivalent to each other. So, let be the set of equivalence classes of under the relation of provable equivalence. Let 
denote the set of statements which are provably false, i.e. whose negations are provable, and let 
denote the set of provable statements. By Godel's First Incompleteness Theorem, there exists at least one (and in fact infinitely many) formulas which do not fall into either of these two categories. So, let 
be the poset such that for 
, 
if and only if 
such that the formula 
provably implies the formula 
. That this is in fact a poset follows immediately by the properties of logical implication. This poset has other interesting properties, as well.
