Difference between revisions of "Partially ordered set"
m |
m (→See Also) |
||
(3 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
− | A '''partially ordered set''' <math>P</math> is a pair, <math>(S, \leq)</math> of a [[set]] <math>S</math> whose [[element]]s are called the ''elements'' or ''vertices'' of <math>P</math> and an order [[relation]] <math>\leq</math> which obeys the following rules: | + | A '''partially ordered set''' <math>P</math> is a pair, <math>(S, \leq)</math> of a [[set]] <math>S</math> whose [[element]]s are called the ''elements'' or ''vertices'' of <math>P</math> and an [[order relation | order]] [[relation]] <math>\leq</math> which obeys the following rules: |
* Reflexivity: <math>x \leq x</math> for all <math>x \in S</math> | * Reflexivity: <math>x \leq x</math> for all <math>x \in S</math> | ||
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 exercise 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 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> | + | * 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>\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, or [[chain]]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>\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. | :* <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> | + | :* Among the other 6 elements, we have the relations <math>\{1\} \leq \{1, 2\}</math>, <math>\{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}_{> 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]]. | * 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 | + | ==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. | ||
+ | |||
+ | == Other Important Families of Posets == | ||
+ | * [[Antichain]]s are posets in which no two elements are comparable. | ||
+ | |||
+ | |||
+ | == Hasse Diagrams == | ||
+ | |||
+ | ==See Also== | ||
+ | *[[Zorn's Lemma]] | ||
+ | *[[Dilworth's Lemma]] | ||
+ | |||
+ | |||
+ | [[Category:Set theory]] |
Latest revision as of 20:01, 25 April 2009
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
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.
Contents
Simple examples
We don't verify that the properties stated above hold for these orderings -- a good exercise 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, or chains.
- 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:
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.
- 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.
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.
Other Important Families of Posets
- Antichains are posets in which no two elements are comparable.