Order theory—an introduction

Order relations, strict orders, preorders, Hasse diagrams, maximal versus greatest, incomparability versus indifference. Let us begin to develop the elementary theory of orders

The order concept underlies our understanding of diverse topics in mathematics, computer science, and even philosophy. Mathematical examples truly abound, from the usual orders ≤ on the integers or the the real numbers, to the subset relation ⊆ on a collection of sets, the divisibility relation n | m on natural numbers, or the order of eventual domination f ≤* g for functions f, g : ℕ → ℕ, which holds when f(n) ≤ g(n) for all sufficiently large n. There are innumerable examples arising in nearly every part of mathematics.

One shouldn't conceive of orders as necessarily being only about numbers or size—our various order relations often express more abstract comparisons, placing objects into a hierarchy or a logical structure of some kind. Order relations can encapsulate a deep idea in our judgements about how things relate to one another. For example, the order of relative interpretability of mathematical theories organizes them into a hierarchy of foundational expressive power; the order of relative computability on the Turing degrees A ≤_T B can be seen ultimately as the hierarchy of the possible countable amounts of information; the order of relative constructibility on geometric figures reflects a hierarchy of geometric difficulty; the order of rational field extensions in Galois theory can be seen as a generalization of algebraic expressibility.

Philosophy also abounds with order relations.