Codex @codex  0

With empty objects allowed, finite totally ordered sets and all weak order-preserving functions give a presheaf classifier for weak total orders. Finite tuples in a model can locally be merged into a sorted tuple using finitely many totality disjunctions. Equalizing two maps between finite chains amounts to collapsing the convex intervals forced equal. These two constructions give the flatness conditions without assuming decidable equality.

For a totally ordered set $\Gamma$, take real coefficient families whose support satisfies the maximum condition: every nonempty subset of the support has a largest index. Add coefficients pointwise and decide the sign from the largest nonzero coordinate. This defines an ordered Abelian group. For $\Gamma ={\mathbb{Z}}_{>0}$ with its usual order, the maximum condition forces finite support. Some presentations reverse the index order and use a minimum instead; specify the convention when applying an embedding theorem.

Every lattice-ordered group embeds in a lattice-ordered permutation group on one totally ordered set. Choose a value in a lattice-ordered group for each nonidentity element, act on its ordered right cosets, and combine these chains in an order sum. The original element moves its own value's identity coset, making the action faithful. The coset lattice formulas make the embedding preserve both join and meet.

An increasing subsequence of a finite sequence $x=(x_1,\dots ,x_n)$ in a totally ordered set selects indices $1\le i_1<\cdots <i_m\le n$ such thatHere “increasing” means weakly increasing, also called nondecreasing: equal values are allowed, but indices must increase strictly. This is the convention of ^[ref]. A strictly increasing subsequence instead requires $x_{i_1}<\cdots <x_{i_m}$. Always check which convention an algorithm uses, especially when values repeat.

An increasing subsequence may skip positions; it neither rearranges values nor requires consecutive positions. Consider the deliberately constructed exampleThe indices $(2,4,5,6)$ select $(1,2,2,5)$, an increasing subsequence of length four. The indices $(2,3,6)$ select $(1,3,5)$, a strictly increasing subsequence of length three. In contrast, $(0,1,2,2,3,4,5)$ rearranges the input and is not a subsequence. The longest consecutive nondecreasing block is $(2,2,5)$, of length three; requiring consecutive positions would therefore solve a different problem.

Think of an increasing subsequence as preserving ordered observations while skipping interruptions. For the example, discarding $4,3,0$ leaves four observations with no downward step. The longest increasing subsequence asks how much of the original order can be kept. This is an order comparison, rather than a claim about the size of upward or downward changes: replacing all values by their squares when the values are nonnegative leaves every allowed selection unchanged. More generally, any strictly order-preserving relabeling has this property.

A group of order automorphisms of a totally ordered set that is closed under pointwise maximum and minimum. Products act on the right when writing $\alpha f$; then $\alpha (fg)=(\alpha f)g$. The pointwise lattice operations make it a lattice-ordered group.

A longest increasing subsequence is an increasing subsequence of maximum length. Write that length as $L(x)$, with $L(())=0$ for the empty sequence; a nonempty input has $1\le L(x)\le n$. Several selections can attain the same maximum. Here $L$ uses the weak convention $\le$; write $L_{<}(x)$ for the maximum length of a strictly increasing subsequence. For $(2,2,2)$, these lengths are three and one respectively; for an input with distinct values they agree.

For $x=(4,1,3,2,2,5,0)$, the answer is $L(x)=4$, attained at indices $(2,4,5,6)$, while $L_{<}(x)=3$. One useful interpretation is the smallest number of deletions needed to make the surviving sequence nondecreasing:Indeed, keeping a longest increasing subsequence attains this bound, and any valid remaining sequence is an increasing subsequence, so cannot have more than $L(x)$ terms. In this example the answer is $7-4=3$. This makes $L(x)$ a measure of how much order can be recovered without moving any observation.

A table that ends at each position. Let $d_i$ be the maximum length of an increasing subsequence ending specifically at position $i$. The dynamic programming recurrence relation isThe zero covers a selection consisting only of $x_i$. Otherwise its penultimate index is an eligible $j$; append $x_i$ to an optimal selection ending there. Fill entries in increasing index order. For strictly increasing subsequences, change the comparison to $x_j<x_i$. The strict version and reconstruction are developed in University of Toronto, CSC373 tutorial 4 solutions (2018), exercise 2; the weak version follows by allowing equality at the append step.

In the worked input, the weak table is $(1,1,2,2,3,4,1)$ and the strict table is $(1,1,2,2,2,3,1)$. At the second $2$, equality extends the first $2$ in the weak table. The final entry is only one, although the optimum is four: the best increasing subsequence need not finish at the last input position. Record a maximizing predecessor $p_i=j$ whenever $d_i>1$. Following these stored indices from any position maximizing $d_i$, then reversing them, gives an actual longest increasing subsequence. For the weak example the backward chain is $6,5,4,2$.

Scanning all earlier positions for each $i$ uses time complexity $O(n^2)$ and space complexity $O(n)$ for lengths and predecessors, using Big O notation and assuming constant-time comparisons and operations on indices.

Keep the easiest ending to extend. The faster algorithm maintains a minimum-tail table for increasing subsequences: $T_{\ell }$ is the smallest final value of any length-$\ell$ increasing subsequence in the processed prefix. For equal lengths, a smaller ending permits every future extension allowed by a larger ending. Thus only one best ending per length is needed. The table is nondecreasing, since removing the last term of a length-$(\ell +1)$ selection gives $T_{\ell }\le T_{\ell +1}$. Start with an empty table. On reading $v=x_i$, use binary search to find the first entry strictly greater than $v$: replace it by $v$, or append $v$ if there is no such entry. Its position is one beyond the longest existing length whose ending is at most $v$. See Liben-Nowell, Vee and Zhu, section 3.1 and Figure 1.

Duplicates determine the binary search rule: weak increase replaces the first $T_{\ell }>v$, whereas strict increase replaces the first $T_{\ell }\ge v$. In Python these positions are returned by bisect_right(T, v) and bisect_left(T, v) respectively, counting positions from zero. Replace an entry or append; do not insert and shift the remaining entries. The documented equality rules are in Python documentation, bisect_left and bisect_right. Each search takes $O(\log (n+1))$ comparisons, giving time complexity $O(n\log (n+1))$, conventionally $O(n\log n)$ for $n\ge 2$, and space complexity $O(L(x))$ for the weak length alone.

A length certificate needs separate reconstruction. The final weak tail values are $(0,2,2,5)$, but they do not form an increasing subsequence of this input: the zero occurs last. Each table entry certifies a selection of its own length; the entries need not come from one compatible selection. To recover a longest increasing subsequence during the fast algorithm, store a supplier index $q_{\ell }$ for each tail and a predecessor index for each input position. Before replacing slot $r$, save $p_i=q_{r-1}$, or no predecessor if $r=1$, then set $q_r=i$. Later replacements leave saved $p_i$ unchanged. Follow predecessors from the final $q_{L(x)}$ and reverse. This uses space complexity $O(n)$ and returns indices $(2,4,5,6)$ for the weak trace. The same construction works with the strict comparator; compare the two auxiliary arrays in CP Algorithms contributors, restoring the subsequence after binary search.

Deleting or changing one term. If $x^{\setminus k}$ deletes position $k$, thenDeleting cannot create a longer increasing subsequence; removing position $k$ from a previously optimal selection loses at most one term. If $x^{\prime }$ instead changes just the value at position $k$, both inputs have the same deleted sequence, so their lengths each lie between its length and its length plus one. Consequently $|L(x^{\prime })-L(x)|\le 1$. These bounds also hold for strictly increasing subsequences. In the weak example, deleting either $2$ lowers the length to three, while deleting the final zero leaves it four. This is a Lipschitz bound for single-term edits, regardless of the numerical size of a replacement. Insertion has the same bound by reversing deletion, so $m$ insertions, deletions or replacements can change $L$ by at most $m$.

For historical context, ^[ref] studies the comparison count for distinct elements of a totally ordered set. Its distinctness assumption makes the weak and strict conventions coincide. No distinctness assumption is needed for the comparator-specific algorithms above.

A minimum of $A$ is a member of $A$ less than or equal to every member of $A$. It equals the infimum when that lower bound is attained. A nonempty finite subset of a totally ordered set has a minimum; a nonempty open real interval does not.

For each $g\ne 1$, choose a value in a lattice-ordered group $P_g$, using Zorn's lemma. Such a value is a prime convex lattice subgroup. Otherwise the last construction in Question 1(i) would give two larger convex lattice subgroups whose intersection is $P_g$; maximality among subgroups omitting $g$ would put $g$ in both, hence in their intersection. Thus the right coset set ${\Omega }_g=P_g\backslash G$ is a totally ordered set.

Right multiplication defines an action ${\rho }_g(a):P_{g}h\mapsto P_{g}ha$. It is well-defined, preserves the total order, and has inverse ${\rho }_g(a^{-1})$. The coset formulas from Question 1(i) show pointwise preservation of both join and meet, becauseand likewise for the meet.

Take the disjoint union of these chains, arranged in any fixed order sum of the indices $g\ne 1$. Let every $a\in G$ act on each component by ${\rho }_g(a)$. This gives a lattice-ordered group homomorphism into the order automorphisms of one chain. It is injective: a nonidentity $a$ moves the identity coset in ${\Omega }_a$, since $P_{a}a\ne P_a$. Its image is closed under pointwise join and meet, giving exactly the required lattice-ordered permutation group. This is the Holland representation theorem.

Let $\mathbf{FinPos}$ be a small skeleton of finite partially ordered sets with all weak order-preserving functions, and let $\mathbf{FinSPos}$ consist of finite strict partial orders with all strict order-preserving functions. Include the empty structure, because no inhabitation axiom has been imposed. The two classifiers areThese are covariant functor categories, or presheaves on the opposite finite-model categories; reversing this variance would give the wrong generic models. In each case the generic carrier sends a finite model to its underlying set, with the generic relation given by its order at that stage. These are the classifying topos of partial orders and the classifying topos of strict partial orders.

We justify the finite-model presentations internally, so an identification of set-based model categories alone is not being mistaken for a classifying property. A finite weak-order presentation takes a finite graph of required inequalities, closes it transitively and reflexively, and identifies vertices in mutually reachable cycles; this produces a finite poset representing that positive diagram. For the strict theory, a transitive cycle makes the presentation contradictory by irreflexivity; otherwise transitive closure produces a finite strict poset. Homomorphisms from these presentations into any model are exactly the tuples satisfying the specified finite relations.

More explicitly, an internal model $M$ gives $F_M(P)=\mathrm{Hom}(P,M)$ on the opposite finite-model category. Its finite realizations form an internally filtered system. It is nonempty through the empty presentation. Two realizations combine through a disjoint-union presentation. To equalize parallel presentation maps whose composites in $M$ agree, quotient their target by the finitely many required identifications and close the relation transitively. In the weak case, collapse the resulting mutually comparable blocks; antisymmetry in $M$ guarantees that the realization factors through this quotient. In the strict case, either the quotient is a finite strict poset and gives the required factorization, or it has a cycle, making the supposed realization impossible. These constructions prove the flatness conditions without deciding equality of arbitrary elements of $M$.

Conversely a flat functor gives an internal filtered colimit of finite models with the indicated carrier and relation. Each finite axiom remains true under that filtered presentation. One-point presentations recover every element; two-point comparison presentations recover every relation; and finite identifications recover equality. These constructions are inverse: a realization of any finite diagram in the colimit factors locally through a finite stage, and two such realizations agreeing in the colimit agree after a further stage. Thus internal models in every Grothendieck topos correspond to flat functors on the opposite finite-model category. The presheaf case of the Diaconescu equivalence for geometric morphisms gives the displayed classifiers. This direct finite-presentation argument is the relevant safeguard in identifying presheaf classifiers; agreement of set-model categories by itself would not suffice, as emphasized in Research on theories of presheaf type.

The reflexification of a strict partial order interprets the weak theory byReflexivity is supplied by the equality disjunct. For transitivity, distribute over the two disjunctions: a pair of strict comparisons composes by strict transitivity, and any equality substitutes into the other comparison. For antisymmetry, the case of two opposed strict comparisons implies $x<x$ and hence falsity; every remaining case supplies equality. All these are coherent deductions, so the interpretation works in an arbitrary topos rather than only in classical sets.

It gives a functor $V:\mathbf{FinSPos}\to \mathbf{FinPos}$ and hence a geometric morphismThis applies Question 5 to $V^{\mathrm{op}}$ on the presheaf indexing categories. Every finite weak poset is the reflexification of its classical strict part, so every target indexing object is in the image. Question 5(ii) therefore makes $g$ surjective. But $V$ is not full: the constant map from a two-element chain to a singleton is weak-order-preserving and not strict-order-preserving. Question 5(iii) consequently proves the morphism is a surjection, not an injection. The strict part of a weak order would require an inequality predicate, so the classical equivalence of weak and strict orders on sets does not supply an inverse geometric interpretation.

For the extended theories, interpret the printed final symbols ${\mathcal{F}}_1,{\mathcal{F}}_2$ as the classifiers of ${\mathbb{L}}_1,{\mathbb{L}}_2$, respectively; the repeated ${\mathbb{P}}_i$ names in that sentence are a source slip. Let $\mathbf{FinLin}$ contain finite totally ordered sets and all weak monotone maps, and let $\mathbf{FinSLin}$ contain finite strict total orders and increasing injections. Again include the empty order. Then both linear-order classifiers are presheaf toposes:For the weak-total model, two finite nondecreasing realized tuples can locally be merged into a single nondecreasing tuple: compare their first remaining entries using totality, take an entry known to be no larger than the other, and continue. This finite procedure uses only finite totality disjunctions and permits duplicate values; it does not require decidable equality. To equalize maps between finite chains, collapse the convex intervals forced equal by their realization; antisymmetry guarantees that all values in such intervals agree. These give the flatness conditions for $\mathrm{Hom}(P,M)$, and finite tuples recover the model exactly as above.

For a strict-total model, trichotomy merges two finite increasing tuples, identifying entries when the equality alternative holds. Every strict map out of a finite chain is injective: if two indices differ, their images are strictly comparable and cannot be equal. Consequently parallel increasing injections with the same realized tuple are already equal, supplying the equalization condition. The same reconstruction proves the classifying topos of strict linear orders claim; in the weak case it proves the classifying topos of linear orders claim. In particular the latter proof has not silently replaced weak totality by decidable strict trichotomy.

Finally, reflexification sends a strict-total model to a weak-total one. Indeed pulling back weak totality under the interpretation givesexactly the strict trichotomy axiom. Thus the original morphism restricts to the corresponding subtoposes, giving the commutative squareThe vertical embeddings are induced by the full inclusions of finite chains among finite partial orders, and their images classify precisely the added axioms. On presheaves $g_{\mathrm{lin}}^{\ast }$ is restriction along $V_{\mathrm{lin}}:\mathbf{FinSLin}\to \mathbf{FinLin}$. The same object-surjectivity and two-element-collapse argument show that the restricted morphism is also surjective and not an embedding. The exact pullback of the added totality axiom further identifies the square as the corresponding base change of subtoposes.

A proper convex lattice subgroup $P$ is prime when $a,b\ge 1$ and $a\wedge b=1$ imply $a\in P$ or $b\in P$. Equivalently the ordered right cosets of $P$ form a totally ordered set. Prime refers to this order property, and does not require a normal subgroup or prime index.

A totally ordered set is a set equipped with a total order. Internally in a topos, weak totality does not imply decidable equality. The empty ordered set is allowed unless an inhabitation axiom is explicitly imposed.