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

  1. f.value s;
  2. s.val.card;
  3. Colex s.val, using the standard order on Fin 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.lean converts the stored finite face collection directly to TotalFace and provides its Fintype; this constructor reuses that instance and its membership proofs.
  • FilterFunction.lean supplies 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 0df444a360eaa60ab8c11dca51a86af692955474 when this implementation was written; the current pin is 56a005855ea17e0b0958f73ec801ae140b0a1679 (v4.35.0). It reuses Finset.Sort (Fintype.orderIsoFinOfCardEq, Finset.orderIsoOfFin; the executable path passes through Finset.sort, Multiset.sort, and List.SortedLT.getIso), Order.Basic (LinearOrder.lift'), Prod.Lex, Colex, and Order.Lex. The colex linear order is on Colex (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.