Order theory

Order theory is a part of mathematics that helps us understand how things can be arranged in a specific way. It looks at the idea of order, like when we say one thing is smaller, earlier, or comes before another thing. In order theory, mathematicians use something called binary relations to make these ideas clear and easy to work with.

This area of math is important because it helps us organize and compare many different kinds of information. Whether we are sorting numbers, deciding which tasks to do first, or even thinking about how ideas relate to each other, order theory gives us tools to understand these relationships better.

By studying order, mathematicians can create rules and patterns that apply to many different situations. This makes order theory a useful and interesting part of math that connects to many other areas of learning.

Background and motivation

Orders help us understand how things can be compared, like numbers or words. In school, you learn that 2 is less than 3 or that the letter A comes before B. These ideas can also apply to other things, like grouping objects or family relationships.

Some orders let us compare every pair of things, like numbers. But other orders, such as grouping animals, might not let us compare every pair — for example, birds and dogs are both animals, but one is not a group of the other. Order theory studies these ideas in a general way, helping us understand many different types of comparisons.

Basic definitions

This section talks about ordered sets using ideas from set theory, arithmetic, and binary relations.

Orders are special types of binary relations. Imagine a set P and a relation ≤ on P. If ≤ follows three rules—reflexivity, antisymmetry, and transitivity—then it is a partial order. A set with a partial order is called a partially ordered set or poset.

We can think of common orders, like those on natural numbers, integers, rational numbers, and reals. These orders have an extra property: any two elements can be compared. Such orders are called total orders or linear orders. Examples of orders that are not total include the subset order on sets and the divisibility relation |, where we say n|m if n divides m without remainder.

Hasse diagrams help us visualize partial orders. These diagrams show the elements and their relations using graph drawings where vertices are the elements, and the order is shown by edges and the positions of the vertices.

In a partially ordered set, some elements might be special. For example, the least element is an element m such that m ≤ a for all elements a. The notation 0 often represents the least element. However, in some orders, like the divisibility order, the number 1 is the least element because it divides all other numbers, while 0 is the greatest element.

Other special elements include minimal and maximal elements. Minimal elements have no elements below them, while maximal elements have no elements above them.

The concept of upper bounds also exists. Given a subset S of a poset P, an upper bound of S is an element b such that s ≤ b for all s in S. Similarly, lower bounds are defined by reversing the order.

The least upper bound (or supremum) and the greatest lower bound (or infimum) are important ideas in order theory. For two elements x and y, we can write x ∨ y for their least upper bound and x ∧ y for their greatest lower bound.

Order theory also studies how to create new orders from existing ones. For example, we can invert an order to get its dual order. We can also combine orders using the cartesian product or the disjoint union.

Order theory connects closely with other areas like topology and category theory. For instance, certain topologies can be defined based on orders, and orders can be represented as special types of graphs or categories.

History

Orders are found everywhere in mathematics. The idea of order was first talked about clearly in the 1800s. Important thinkers like George Boole, Charles Sanders Peirce, Richard Dedekind, and Ernst Schröder all studied ways to describe order.

People also worked on orders in geometry. In 1882, Pasch showed that a geometry of order could be built without measuring things. Later, Peano, Hilbert, and Veblen improved these ideas. In 1901, Bertrand Russell wrote about the basic ideas of order, and he talked more about it in his book The Principles of Mathematics in 1903. The word "poset," short for partially ordered set, was first used by Garrett Birkhoff in his book Lattice Theory.