Editing Preorder (section)

==Preorders as partial orders on partitions==

Given a preorder <math>\,\lesssim\,</math> on <math>S</math> one may define an [[equivalence relation]] <math>\,\sim\,</math> on <math>S</math> such that 
<math display=block>a \sim b \quad \text{ if and only if } \quad a \lesssim b \; \text{ and } \; b \lesssim a.</math> 
The resulting relation <math>\,\sim\,</math> is reflexive since the preorder <math>\,\lesssim\,</math> is reflexive; transitive by applying the transitivity of <math>\,\lesssim\,</math> twice; and symmetric by definition. 

Using this relation, it is possible to construct a partial order on the quotient set of the equivalence, <math>S / \sim,</math> which is the set of all [[equivalence class]]es of <math>\,\sim.</math> If the preorder is denoted by <math>R^{+=},</math> then <math>S / \sim</math> is the set of <math>R</math>-[[Cycle (graph theory)|cycle]] equivalence classes: 
<math>x \in [y]</math> if and only if <math>x = y</math> or <math>x</math> is in an <math>R</math>-cycle with <math>y</math>. 
In any case, on <math>S / \sim</math> it is possible to define <math>[x] \leq [y]</math> if and only if <math>x \lesssim y.</math> 
That this is well-defined, meaning that its defining condition does not depend on which representatives of <math>[x]</math> and <math>[y]</math> are chosen, follows from the definition of <math>\,\sim.\,</math> It is readily verified that this yields a partially ordered set.

Conversely, from any partial order on a partition of a set <math>S,</math> it is possible to construct a preorder on <math>S</math> itself. There is a [[one-to-one correspondence]] between preorders and pairs (partition, partial order).

{{em|Example}}: Let <math>S</math> be a [[Theory (mathematical logic)|formal theory]], which is a set of [[Sentence (mathematical logic)|sentences]] with certain properties (details of which can be found in [[Theory (mathematical logic)|the article on the subject]]). For instance, <math>S</math> could be a [[first-order theory]] (like [[Zermelo–Fraenkel set theory]]) or a simpler [[Propositional calculus|zeroth-order theory]]. One of the many properties of <math>S</math> is that it is closed under logical consequences so that, for instance, if a sentence <math>A \in S</math> logically implies some sentence <math>B,</math> which will be written as <math>A \Rightarrow B</math> and also as <math>B \Leftarrow A,</math> then necessarily <math>B \in S</math> (by ''[[modus ponens]]''). 
The relation <math>\,\Leftarrow\,</math> is a preorder on <math>S</math> because <math>A \Leftarrow A</math> always holds and whenever <math>A \Leftarrow B</math> and <math>B \Leftarrow C</math> both hold then so does <math>A \Leftarrow C.</math> 
Furthermore, for any <math>A, B \in S,</math> <math>A \sim B</math> if and only if <math>A \Leftarrow B \text{ and } B \Leftarrow A</math>; that is, two sentences are equivalent with respect to <math>\,\Leftarrow\,</math> if and only if they are [[logically equivalent]]. This particular equivalence relation <math>A \sim B</math> is commonly denoted with its own special symbol <math>A \iff B,</math> and so this symbol <math>\,\iff\,</math> may be used instead of <math>\,\sim.</math> The equivalence class of a sentence <math>A,</math> denoted by <math>[A],</math> consists of all sentences <math>B \in S</math> that are logically equivalent to <math>A</math> (that is, all <math>B \in S</math> such that <math>A \iff B</math>). 
The partial order on <math>S / \sim</math> induced by <math>\,\Leftarrow,\,</math> which will also be denoted by the same symbol <math>\,\Leftarrow,\,</math> is characterized by <math>[A] \Leftarrow [B]</math> if and only if <math>A \Leftarrow B,</math> where the right hand side condition is independent of the choice of representatives <math>A \in [A]</math> and <math>B \in [B]</math> of the equivalence classes. 
All that has been said of <math>\,\Leftarrow\,</math> so far can also be said of its [[converse relation]] <math>\,\Rightarrow.\,</math> 
The preordered set <math>(S, \Leftarrow)</math> is a [[directed set]] because if <math>A, B \in S</math> and if <math>C := A \wedge B</math> denotes the sentence formed by [[logical conjunction]] <math>\,\wedge,\,</math> then <math>A \Leftarrow C</math> and <math>B \Leftarrow C</math> where <math>C \in S.</math> The partially ordered set <math>\left(S / \sim, \Leftarrow\right)</math> is consequently also a directed set. 
See [[Lindenbaum–Tarski algebra]] for a related example.