Difference between revisions of "Partially ordered set"
m (links) |
m (→See Also) |
||
(One intermediate revision by the same user not shown) | |||
Line 14: | Line 14: | ||
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. | 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>\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 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: | ||
Line 24: | Line 24: | ||
− | ==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== | ==See Also== | ||
*[[Zorn's Lemma]] | *[[Zorn's Lemma]] | ||
+ | *[[Dilworth's Lemma]] | ||
[[Category:Set theory]] | [[Category:Set theory]] |
Latest revision as of 19: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
[hide]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.