Order type of a tuple
Lax345067.OrderTypes · concepts/Lax345067/OrderTypes.lean · lax-345067
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
Fix a linearly ordered set and a tuple a = (a₁, …, a_ℓ) of its elements. The order type of a records which coordinates carry strictly smaller entries than which: it is the relation that holds of i and j when aᵢ < aⱼ. Two tuples have the same order type when they are arranged in the same way — in particular they then agree on which coordinates carry equal entries, since a linear order is total.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Order.Basic |
| 2 | import Mathlib.Data.Fin.Basic |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Order type of a tuple |
| 7 | type: definition |
| 8 | --- |
| 9 | Fix a linearly ordered set and a tuple *a* = (*a*₁, …, *a*_ℓ) of its |
| 10 | elements. The order type of *a* records which coordinates carry strictly |
| 11 | smaller entries than which: it is the relation that holds of *i* and *j* |
| 12 | when *a*ᵢ < *a*ⱼ. Two tuples have the same order type when they are |
| 13 | arranged in the same way — in particular they then agree on which |
| 14 | coordinates carry equal entries, since a linear order is total. |
| 15 | |
| 16 | # Formalization notes |
| 17 | |
| 18 | The order type is a `Prop`-valued relation on coordinates rather than a |
| 19 | three-valued code: in a linear order the strict-order pattern determines |
| 20 | the equality pattern (`a i = a j` exactly when neither `a i < a j` nor |
| 21 | `a j < a i`), so recording `<` alone loses nothing and keeps |
| 22 | decidability, `compare` and `Ordering` off the endorsement surface. |
| 23 | |
| 24 | The definition is stated for an arbitrary linearly ordered vertex type, |
| 25 | not only for `Fin n`: it is a pointwise notion, and proofs that consume it |
| 26 | work over intermediate carriers. Statements of this submission still |
| 27 | instantiate it at the canonical carriers. |
| 28 | -/ |
| 29 | |
| 30 | namespace Lax345067.OrderTypes |
| 31 | |
| 32 | /-- The order type of a tuple: the relation holding of coordinates `i` and |
| 33 | `j` when the `i`-th entry is strictly smaller than the `j`-th. Two tuples |
| 34 | have the same order type when this relation is the same. -/ |
| 35 | def orderType {V : Type*} [LinearOrder V] {ℓ : ℕ} (a : Fin ℓ → V) : |
| 36 | Fin ℓ → Fin ℓ → Prop := |
| 37 | fun i j => a i < a j |
| 38 | |
| 39 | end Lax345067.OrderTypes |
| 40 |
Formalization notes
The order type is a -valued relation on coordinates rather than a three-valued code: in a linear order the strict-order pattern determines the equality pattern ( exactly when neither nor ), so recording alone loses nothing and keeps decidability, and off the endorsement surface.
The definition is stated for an arbitrary linearly ordered vertex type, not only for : it is a pointwise notion, and proofs that consume it work over intermediate carriers. Statements of this submission still instantiate it at the canonical carriers.
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments