Difference between revisions of "Ordering"

Revision as of 19:43, 14 March 2015

An ordering is a special kind of relation, we can define an order uniquely as a partial or strict ordering. That is the two are equivalent.

Definition

So far it varies so much as to what "Ordering" means that based on the context it could be either partial or strict. The big clue will be the symbols used:

Relation	Partial form	Strict form
Less than (or equal to)	$\le$	$<$
(Other ordering symbol)	$\preceq$	$\prec$
proper subset (or equal to)	$\subseteq$	$\subset$

Partial Ordering

A binary relation that is antisymmetric, reflexive and transitive is a partial ordering. Example $\le$

Strict ordering

A relation $S$ in $A$ is a strict ordering if it is asymmetric and transitive. Example $<$

Reminder of terms

These are restated from the relation page for convenience

Here $R$ will be a relation in $A$

Property	Statement	Example	Partial	Strict
Symmetric	$\forall a\in A\forall b\in A(aRb\implies bRa)$	equiv relations
Antisymmetric	$\forall a\in A\forall b\in A([aRb\wedge bRa]\implies a=b)$	Let $A=\mathbb{N}$ then $[a\le b\wedge b\le a]\implies a=b$	#
Asymmetric	$\forall a\in A\forall b\in B(aRb\implies (b,a)\notin R)$	If $a < b$ then $b < a$ is false		#
Reflexive	$\forall a\in A(aRa)$	equiv relations, Let $A=\mathbb{N}$ then $a\le a$	#
Transitive	$\forall a\in A\forall b\in A\forall c\in A([aRb\wedge bRc]\implies aRc)$	equiv relations, $A=\mathbb{N}$ then $a\le b\wedge b\le c\iff a\le b\le c\implies a\le c$	#	#

Moving between partial and strict relations

Given a partial relation $\le$ we may define a strict relation $<$ by:

$a< b\iff[a\le b\wedge a\ne b]$

If given a $<$ we can define a $\le$ by:

$a\le b\iff[a< b\vee a=b]$

Comparable elements

We say $a$ and $b$ are comparable if the following hold:

Partial ordering

For $a$ and $b$ to be comparable we must have $aRb\vee bRa$

Strict ordering

For $a$ and $b$ to be comparable we require $a\ne b\implies[aRb\vee bRa]$ , notice that false implies false

Total ordering (Linear ordering)

A (partial or strict) ordering is a total (also known as linear) ordering if , $a$ and $b$ are comparable using the definitions above.

For example the ordering meaning $a$ divides $b$ (example: $(3,6)\iff 3|6$ ) is not total, however $\le$ is, as is $>$

Properties

Given a partial ordering of and let $B\subset A$

Property	Statement

Proof that $\le$ is a partial ordering $\iff <$ is a strict ordering

[Expand]
Proof that $\le$ is a partial ordering $\iff <$ is a strict ordering

First: $\le$ is partial $\implies <$ is strict

$<$ is transitive
Suppose $x< y$ and $y < z$ (which may be written more compactly as $x< y< z$ ) then:
- $x\le y\wedge x\ne y$
- $y\le z\wedge y\ne z$
As $x\le y$ and $y\le z$ by transitivity of $\le$ we see $x\le z$

However all we know is $x\ne y\wedge y\ne z$ so we cannot yet conclude $x=z$ or $x\ne z$
Suppose $x=z$ we already know $[x\le y]\wedge [y\le z]$ but $z=x$

thus $[x\le y]\wedge[y \le x]$ but $\iff y=x$ contradicting that $y\ne x$

Now we know $x\ne z$

Noting that $[x< y\wedge y< z]\implies [x\le z\wedge x\ne z]\implies x< z$ . We conclude $<$ is transitive.
$<$ is asymmetric (we have $a< b\implies b\not< a$ )
If $x< y$ then we know $x\le y\wedge x\ne y$
So we must have $y\not\le x$ as if:
- $y\le x$ were true then we'd have $[x\le y\wedge y\le x]\implies x=y$
  contradicting that and $y$ are different
But $y< x\iff[y\le x\wedge x\ne y]$ - we do not have $y\le x$ so we cannot have $y< x$

Thus we see that $x< y\implies x\not< y$ - we conclude that $<$ is asymmetric

Second: $<$ is strict $\implies \le$ is partial

TODO: Fill this out

Good resources

http://www.math.uah.edu/stat/foundations/Order.html

@@ Line 1: / Line 1: @@
-An ordering is a special kind of [[Relation|relation]], other than the concept of a relation we require three properties before we can define it.
+An ordering is a special kind of [[Relation|relation]], we can define an order uniquely as a partial or strict ordering. That is the two are equivalent.
-==Note==
-Partial orderings and strict orderings are very similar, and the terms differ slightly for each. For example for {{M|a}} and {{M|b}} to be '''comparable''' in a partial ordering (for a relation {{M|R}} in {{M|A}}) it means that <math>aRb\vee bRa</math> - an example would be {{M|\le}}
-However! For a strict ordering for {{M|a}} and {{M|b}} to be comparable we must have: <math>a\ne b\implies[aRb\vee bRa]</math>, for example {{M|<}}
-It can be shown that if <math><</math> is (strict and linear ordering) then <math>\le</math> defined by <math>p\le q\iff[p< q\vee p=q]</math> is a partial ordering. So you can switch from a strict to a partial quite easily.
-One can also use common sense, and notice that <math>\not <\iff\ge</math>
-It can be shown that a partial ordering has a natural corresponding strict ordering and a strict ordering has a natural corresponding partial ordering.
-{{Todo|corresponding orderings}}
 ==Definition==
-If we have "just an ordering" it refers to a partial ordering.
+So far it varies so much as to what "Ordering" means that based on the context it could be either partial or strict. The big clue will be the symbols used:
-===Partial Ordering===
-A binary relation that is antisymmetric, reflexive and transitive is a partial ordering. An example of a partial ordering is {{M|\le}}, notice {{M|a\le b}} and <math>b\le a\implies a=b</math>
-===Strict ordering===
-A relation {{M|S}} in {{M|A}} is a strict ordering if it is asymmetric and transitive.
-===Well ordering===
-(see [[Well-ordering]])
-==Properties==
-Given a partial ordering <math>\le</math> of <math>A</math> and let {{M|B\subset A}}
 {| class="wikitable" border="1"
 |-
-! Property
+! Relation
-! Statement
+! Partial form
+! Strict form
 |-
+| Less than (or equal to)
+| <math>\le</math>
+| <math><</math>
+|-
+| (Other ordering symbol)
+| <math>\preceq</math>
+| <math>\prec</math>
+|-
+| proper subset (or equal to)
+| <math>\subseteq</math>
+| <math>\subset</math>
 |}
-==Required properties for definition==
+===Partial Ordering===
+A binary relation that is antisymmetric, reflexive and transitive is a partial ordering. Example <math>\le</math>
+===Strict ordering===
+A relation {{M|S}} in {{M|A}} is a strict ordering if it is asymmetric and transitive. Example <math>< </math>
+===Reminder of terms===
 These are restated from the [[Relation|relation]] page for convenience
@@ Line 80: / Line 68: @@
 | #
 |}
+==Moving between partial and strict relations==
+Given a partial relation <math>\le</math> we may define a strict relation <math><</math> by:
+<math>a< b\iff[a\le b\wedge a\ne b]</math>
+If given a <math><</math> we can define a <math>\le</math> by:
+<math>a\le b\iff[a< b\vee a=b]</math>
 ==Comparable elements==
@@ Line 93: / Line 90: @@
 For example the ordering <math>a|b</math> meaning {{M|a}} divides {{M|b}} (example: <math>(3,6)\iff 3|6</math>) is not total, however <math>\le</math> is, as is <math> ></math>
+==Properties==
+Given a partial ordering <math>\le</math> of <math>A</math> and let {{M|B\subset A}}
+{| class="wikitable" border="1"
+|-
+! Property
+! Statement
+|-
+|}
+==Proof that <math>\le</math> is a partial ordering <math>\iff <</math> is a strict ordering==
+{{Begin Theorem}}
+Proof that <math>\le</math> is a partial ordering <math>\iff <</math> is a strict ordering
+{{Begin Proof}}
+'''First: <math>\le</math> is partial <math>\implies <</math> is strict'''
+# '''<math><</math> is transitive'''
+#:
+#: Suppose <math>x< y</math> and <math>y < z</math> (which may be written more compactly as <math>x< y< z</math>) then:
+#:* <math>x\le y\wedge x\ne y</math>
+#:* <math>y\le z\wedge y\ne z</math>
+#: As <math>x\le y</math> and <math>y\le z</math> by transitivity of <math>\le</math> we see <math>x\le z</math>
+#: ''However'' all we know is <math>x\ne y\wedge y\ne z</math> so we cannot yet conclude <math>x=z</math> or <math>x\ne z</math>
+#:: Suppose <math>x=z</math> we already know <math>[x\le y]\wedge [y\le z]</math> but <math>z=x</math>
+#:: thus <math>[x\le y]\wedge[y \le x]</math> but <math>\iff y=x</math> '''contradicting''' that <math>y\ne x</math>
+#: Now we know <math>x\ne z</math>
+#: Noting that <math>[x< y\wedge y< z]\implies [x\le z\wedge x\ne z]\implies x< z</math>. We conclude <math><</math> is transitive.
+#:
+#:
+# '''<math><</math> is asymmetric (we have <math>a< b\implies b\not< a</math>)'''
+#:
+#: If <math>x< y</math> then we know <math>x\le y\wedge x\ne y</math>
+#: So we must have <math>y\not\le x</math> as if:
+#:* <math>y\le x</math> were true then we'd have <math>[x\le y\wedge y\le x]\implies x=y</math>
+#:*: contradicting that <math>x</math> and {{M|y}} are different
+#: But <math>y< x\iff[y\le x\wedge x\ne y]</math> - we do not have <math>y\le x</math> so we cannot have <math>y< x</math>
+#: Thus we see that <math>x< y\implies x\not< y</math> - we conclude that <math><</math> is asymmetric
+'''Second: <math><</math> is strict <math>\implies \le</math> is partial'''
+{{Todo|Fill this out}}
+{{End Proof}}
+{{End Theorem}}
+==Good resources==
+* [http://www.math.uah.edu/stat/foundations/Order.html http://www.math.uah.edu/stat/foundations/Order.html]
 {{Definition|Set Theory}}

Difference between revisions of "Ordering"

Revision as of 19:43, 14 March 2015

Contents

Definition

Partial Ordering

Strict ordering

Reminder of terms

Moving between partial and strict relations

Comparable elements

Partial ordering

Strict ordering

Total ordering (Linear ordering)

Properties

Proof that $\le$ is a partial ordering $\iff <$ is a strict ordering

Good resources

Navigation menu

Views

Personal tools

Navigation

Search

Tools

Difference between revisions of "Ordering"

Revision as of 19:43, 14 March 2015

Contents

Definition

Partial Ordering

Strict ordering

Reminder of terms

Moving between partial and strict relations

Comparable elements

Partial ordering

Strict ordering

Total ordering (Linear ordering)

Properties

Proof that ≤\le is a partial ordering ⟺<\iff < is a strict ordering

Good resources

Navigation menu

Search

Proof that $\le$ is a partial ordering $\iff <$ is a strict ordering