---
tag: 0G77XFBV00
kind: definition
name: Lexicographic order
msc: [06A05]
defines: 0B68KNPGCG
uses: [011C29Q1S1, 0C81YBVTWH]
sources:
  - url: https://en.wikipedia.org/wiki/Lexicographic_order
    locator: Cartesian products
---

## Definition

Let $(A, \le_A)$ and $(B, \le_B)$ be [[partially ordered sets|011C29Q1S1]].
The lexicographic order on the [[Cartesian product|0C81YBVTWH]] $A \times B$ is the relation $\le$ with $(a, b) \le (a', b')$ when
$$a <_A a' \quad \text{or} \quad (a = a' \text{ and } b \le_B b').$$

## Remarks

It is a partial order. When $\le_A$ and $\le_B$ are [[total orders|0316AYH1SC]], it is a total order.
Example: in $\mathbb{N} \times \mathbb{N}$, $(1, 5) < (2, 0)$ and $(2, 0) < (2, 3)$.
A dictionary orders words in the same way, letter by letter.

## Explanations

### L1 human

The lexicographic order is the dictionary order.
"cat" comes before "cow", because the first letters agree and "a" comes before "o".