---
tag: W8DZ5KGGHN
kind: concept
name: Linear extension
msc: [06A05, 06A07]
sources:
  - url: https://en.wikipedia.org/wiki/Linear_extension
same_as:
  wikidata: Q6553442
  wikipedia: Linear extension
---

## Summary

A linear extension of a [[partial order|0QV2JS9RJ3]] is a [[total order|0FRXBVVR03]] on the same set that keeps every relation of the partial order.
Every partial order has one, and the order is recovered as the intersection of all of them.
Linear extensions are the basis of order dimension, of sorting problems, and of many counting questions about finite posets.

## Explanations

### L1 human

A partial order is a set of rules of the form "this comes before that".
A linear extension is a way to put all the elements in a single row so that every rule holds.
For the tasks "dress" before "leave" and "eat" before "leave", both rows dress, eat, leave and eat, dress, leave are linear extensions.
The row leave, dress, eat is not, since it breaks a rule.