Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Partially ordered set"

 
m (→‎See Also)
 
(4 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 excercize 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 (further away from 0) than <math>x</math>.  This is the [[mathematical convention | conventional]] ordering of <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.
+
* 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>\displaystyle \{1\} \leq \{1, 3\}</math>, <math>\{2\} \leq \{1, 2\}</math>, <math>\{2\} \leq \{2, 3\}</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.
−
      <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 other than 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 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.
 +
 +
== 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 $P$ is a pair, $(S, \leq)$ of a set $S$ whose elements are called the elements or vertices of $P$ and an order relation $\leq$ which obeys the following rules:

  • Reflexivity: $x \leq x$ for all $x \in S$
  • Anti-symmetry: $x \leq y$ and $y \leq x$ if and only if $x = y$
  • Transitivity: if $x \leq y$ and $y \leq z$ then $x \leq z$

The name "partially ordered set" is often abbreviated poset.

Sometimes, we abuse notation and use the same letter $P$ 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 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 $x \leq y$ if $y$ is bigger than $x$, 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 $\mathbb{Z}$. 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 $S$ is the poset $P = (\mathcal{P}(S), \leq)$ where $\mathcal{P}(S)$ is the power set (that is, the set of subsets) of $S$ and for $x, y \in \mathcal{P}(S)$, $x \leq y$ if and only if $x \subseteq y$. For instance, if $S = \{1, 2, 3\}$ then the poset $P$ has 8 elements among which we have the following relations:
  • $\emptyset$ is a minimal element of the poset; every other element is larger.
  • $S = \{1, 2, 3\}$ is a maximal element: every other element is smaller.
  • Among the other 6 elements, we have the relations $\{1\} \leq \{1, 2\}$, $\{1\} \leq \{1, 3\}$, $\{2\} \leq \{1, 2\}$, $\{2\} \leq \{2, 3\}$, $\{3\} \leq \{1, 3\}$, and $\{3\} \leq \{2, 3\}$, and no others.
  • There are alternative orderings of the positive integers: for example, one might take the poset $P = (\mathbb{Z}_{> 0}, \leq)$ where $n \leq m$ if and only if $n | m$. Under this ordering, the positive integers still have a minimal element (1, which divides everything) but are no longer totally ordered. In particular, neither $2 | 3$ nor $3 | 2$, 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 $R$ be the set of well-formed formulas of Peano arithmetic. In other words, $S$ is the set of all arithmetic statements. We know that some of these statements are provably equivalent to each other. So, let $S$ be the set of equivalence classes of $R$ under the relation of provable equivalence. Let $\hat 0$ denote the set of statements which are provably false, i.e. whose negations are provable, and let $\hat 1$ 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 $P = (S, \leq)$ be the poset such that for $\mathbf{x, y} \in S$, $\mathbf{x} \leq \mathbf{y}$ if and only if $\exists x \in \mathbf{x}, y \in \mathbf{y}$ such that the formula $x$ provably implies the formula $y$. 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.


Hasse Diagrams

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Partially_ordered_set&oldid=31465"