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.

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.

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.

History

Orders are important in mathematics. People started talking about orders clearly in the 1800s. Famous thinkers like George Boole, Charles Sanders Peirce, Richard Dedekind, and Ernst Schröder studied how to describe order.

People also looked at orders in geometry. In 1882, Pasch showed that a type of geometry could be made without measuring things. Later, Peano, Hilbert, and Veblen made these ideas better. In 1901, Bertrand Russell wrote about basic order ideas 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.