Order

Introduction

An order on a non-empty set S is a binary relation on S that is reflexive, anti-symmetric, and transitive. The idea of a partial order is that not all elements in a set have a relation. Some pairs of elements are incomparable, meaning no relation exists between them. This is denoted using the parallel lines symbol: ∥, for example x ∥ y means (x, y) ∉ R and (y, x) ∉ R.

If the symbol ≤ denotes our order relation then

(∀x ∈ S) x ≤ x ∀x, y ∈ S x ≤ y and y ≤ x then x = y ∀x, y, z ∈ S x ≤ y and y ≤ z then x ≤ z

An order is defined using the notational convention: (S, ≤) where S is the set on which the order is defined and ≤ denotes the ordering relation. In a total order all elements are comparable meaning that the relationship has the following total property:

∀x, y ∈ S (x, y) ∈ R or (y, x) ∈ R

A total order is also known as a linear order or a chain. A fairly simple example of a chain is the integers 1-5 with the ordering relation less than or equals, which would be written as ({1,2,3,4,5}, ≤). An antichain is a set where no two elements are comparable:

∀ x,y ∈ S (x, y) ∉ R and (y, x) ∉ R