Canonical grade-compatible face orders
For a finite presentation C : TDA.Simplicial.FiniteComplex n and a monotone face-value
function f, TDA.Filtration.CompatibleOrder.ofLex C f gives a bijection from
Fin (Fintype.card (TotalFace C.toPre)) to the nonempty faces. Its key orders faces by
f.value s;s.val.card;Colex s.val, using the standard order onFin n.
The grade is the primary coordinate. Cardinality ensures every proper face precedes its coface when their grades tie. Colex makes the full key injective when grades and cardinalities also tie. Consequently, the returned enumeration has nondecreasing grades and strict key increase. All faces of the supplied presentation occur once; absent ambient vertices and the empty face are not added.
The key's lexicographic order is pulled back along its injective map to the face subtype.
The finite order isomorphism from Fintype.orderIsoFinOfCardEq then supplies the canonical
sorted enumeration. This local order is used only inside the constructor and its key-order
theorem. The ambient TotalFace order remains set inclusion, so unrelated singleton faces
remain incomparable outside the construction.
An empty presentation yields Fin 0 and its empty equivalence. No face, vertex, grade default,
or inhabitant of the grade type is selected. Concrete lists for empty, tied, nonconstant,
cross-dimensional, and colex-discriminator presentations are evaluated in
CompatibleOrderExamples.lean; that file
also exhibits a monotone-grade permutation rejected by proper-face precedence.
The finite presentation supplies executable face data. The constructor evaluates on the integer-valued examples; an arbitrary value function is not thereby claimed to be runtime computable. The result is a finite presentation constructor, not a generic noncomputable linear extension. It establishes no range-order equivalence, initial-segment theorem, sublevel reconstruction, simplexwise reindexing, topological result, homology, reduction, pairing, or barcode consequence.
A tied-edge counterexample
Take the three nonempty faces {0}, {1}, and {0,1}, all with grade 5. The list
[{0,1}, {0}, {1}] is a bijective, grade-monotone enumeration: its values are all equal.
The monotone field accepts this list because all grades are equal, but face_lt would require
the index 1 of {0} to be less than the index 0 of {0,1}. The two separate conditions are
defined by CompatibleOrder. The private edge3
and badEnum definitions, with the badEnum_grade_mono and badEnum_not_compatible proofs,
are in CompatibleOrderExamples.lean.
When grades tie, the constructor's cardinality key puts both vertices before the edge, and colex breaks the tie between the two vertices. Compatibility requires each vertex before its proper coface, but it imposes no order between the incomparable vertices.
Source and API notes
FiniteComplex.leanconverts the stored finite face collection directly toTotalFaceand provides itsFintype; this constructor reuses that instance and its membership proofs.FilterFunction.leansupplies values on faces and weak monotonicity under inclusion. No additional filter assumption is introduced.- The repository baseline for those modules is develop
fa0cece24f7c00a820981872494092d8a4a3df76. - Mathlib was pinned at
0df444a360eaa60ab8c11dca51a86af692955474when this implementation was written; the current pin is56a005855ea17e0b0958f73ec801ae140b0a1679(v4.35.0). It reusesFinset.Sort(Fintype.orderIsoFinOfCardEq,Finset.orderIsoOfFin; the executable path passes throughFinset.sort,Multiset.sort, andList.SortedLT.getIso),Order.Basic(LinearOrder.lift'),Prod.Lex,Colex, andOrder.Lex. The colex linear order is onColex (Finset (Fin n)); the nested lex orders and existing equivalences are used directly. No sorting algorithm or ordering instance is added to Mathlib. - The primary mathematical source for the API is the finite presentation and monotone filter already in this repository. This document does not attribute the constructor or its tie-breaker to an external persistence theorem. The broader order-equivalence and initial-segment questions remain in parent Issue #42.