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.

Let $\mathbf{FinPos}$ contain finite partially ordered sets and all order-preserving functions, including the empty object. The covariant functor category $[\mathbf{FinPos},\mathbf{Set}]$ classifies weak partial orders. Finite positive presentations reduce to finite preorders with mutually comparable cycles identified. An internal model $M$ gives a flat functor $P\mapsto \mathrm{Hom}(P,M)$ on ${\mathbf{FinPos}}^{\mathrm{op}}$; conversely the corresponding filtered presentation by finite models recovers its carrier and order relation.

Every order-preserving function from a complete lattice to itself has a least and a greatest fixed point. More strongly, its set of fixed points is itself a complete lattice.

Order $\Omega =\{0,1{\}}^E$ coordinatewise. The statement ${\mu }_1{\ge }_{\mathrm{st}}{\mu }_2$ meansfor every real-valued order-preserving function $f$; equivalently, ${\mu }_1(A)\ge {\mu }_2(A)$ for every increasing event $A$. This is stochastic domination of probability measures. For strictly positive laws, the Holley condition is the sufficient conditionHere join and meet are coordinatewise maximum and minimum. The Holley inequality states that this condition implies the stated stochastic domination.

For a single positive law, the FKG lattice condition isWe prove that it gives positive association of random variables, namely ${\mathrm{Cov}}_{\mu }(f,g)\ge 0$ for all increasing $f,g$. Fix such a $g$, and for $t\ge 0$ form the strictly positive tilted lawThe lattice condition and $g(\omega \vee \eta )\ge g(\omega )$ implyThus the Holley condition applies to ${\mu }_t,\mu$, and ${\mathbb{E}}_{{\mu }_t}f\ge {\mathbb{E}}_{\mu }f$. Equality holds at $t=0$, so the right derivative there is nonnegative. Differentiating the finite sums givesHencewhich proves the requested positive association of random variables. Neither $f$ nor $g$ needs to be nonnegative; the finite space makes all differentiations justified. This is the exponential-tilt proof of positive association.

A poset becomes a category whose objects are its elements and whose hom-set $X(x,y)$ is a singleton if $x\le y$ and empty otherwise. Reflexivity supplies identity arrows and transitivity supplies composition; all possible composites are unique, so the category axioms hold. Antisymmetry says that isomorphic objects are equal. A functor between such categories is exactly an order-preserving function: an inequality must be sent to an inequality, and there is no further choice of arrow map.

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.

Order configurations coordinatewise: $\omega \le \eta$ means $\omega (e)\le \eta (e)$ for every edge. Then stochastic domination is the conditionEquivalently, ${\mathbb{E}}_{{\mu }_1}f\ge {\mathbb{E}}_{{\mu }_2}f$ for every real-valued order-preserving function $f$. The equivalence follows on this finite space by writing $f$, up to an additive constant, as a nonnegative linear combination of indicators of its increasing upper level sets. A coupling of probability distributions supported on pairs $(X_1,X_2)$ with $X_1\ge X_2$ proves this domination; conversely such an ordered coupling of probability distributions exists on a finite partially ordered space.

Order the collection $\mathrm{Ch}(P)$ of every chain in a partial order, including the empty chain, by inclusion. Suppose that $j:\mathrm{Ch}(P)\to P$ is an order-preserving function and an injection. Let $\theta =h(P)$ be the Hartogs ordinal: by Hartogs theorem, no injection from $\theta$ to $P$ exists.

Use transfinite recursion to define, for $\alpha <\theta$,We verify both that $j(C_{\alpha })$ is defined and that the values are strictly increasing. Assume inductively that the earlier values are strictly increasing. Then $C_{\alpha }$ is a chain in a partial order. For any $\beta <\alpha$, $C_{\beta }\subseteq C_{\alpha }$, so the fact that $j$ is order-preserving gives $p_{\beta }\le p_{\alpha }$. Furthermore $p_{\beta }\in C_{\alpha }$, whereas $p_{\beta }\notin C_{\beta }$ by distinctness of the earlier values. Thus $C_{\beta }\ne C_{\alpha }$, and injectivity gives $p_{\beta }\ne p_{\alpha }$. We have provedThe empty initial chain starts the induction, and the same argument applies at every limit ordinal.

If a globally defined recursion rule is desired, apply $j$ when the earlier range is a chain and otherwise use the fixed value $j(\varnothing )$. The induction shows that the fallback case never occurs. Thus no choices of new points are being made: the function $j$ uniquely determines every stage.

The resulting function $\alpha \mapsto p_{\alpha }$ is an injection from $\theta$ to $P$, contrary to its defining Hartogs ordinal property. Hence the chain-poset nonembedding lemma gives

For a finite graph $G=(V,E)$, let $o(\omega )={\sum }_{e\in E}\omega (e)$, and let $k_G(\omega )$ count connected components of the spanning open subgraph, including isolated graph vertices. The random-cluster model with $p\in [0,1]$ and $q>0$ isThe partition function $Z_{G,p,q}$ is the sum of these weights over all configurations, making the expression a probability measure.

For the lattice box, take all nearest-neighbor edges with both endpoints in ${\Lambda }_n$. A random-cluster boundary condition $\xi$ is a partition of the boundary graph vertices. Vertices in one block are identified, or wired together, before counting components; the identifications do not add random edges. Let $k_{\xi }(\omega )$ be the number of components of the resulting quotient open graph. ThenThe free random-cluster boundary condition has singleton blocks, while the wired random-cluster boundary condition has one boundary block. Arbitrary partitions are allowed; no assumption that the partition itself has a planar realization is needed for the monotonicity statement.

Write $\xi ⪯\zeta$ if every block of $\xi$ is contained in a block of $\zeta$, so $\zeta$ makes at least as many identifications. The precise boundary monotonicity of the random-cluster measure isEquivalently, the expectation of every real-valued order-preserving function is larger under the more wired measure. This is stochastic domination of probability measures on the coordinatewise configuration order.

To prove it, condition on every edge except $e=\{u,v\}$. If $u,v$ are already connected using those open edges and the boundary wiring, opening $e$ does not change $k_{\xi }$, so its conditional open probability is $p$. If they are not connected, opening it reduces $k_{\xi }$ by one. The ratio of the open weight to the closed weight is then $p/[q(1-p)]$. Thus the random-cluster single-edge conditional probability isFor $q\ge 1$ the second number is at most the first. Adding open edges or making the boundary partition coarser can only turn a disconnected pair into a connected one. Therefore these conditional open probabilities are increasing in both the exterior configuration and the amount of wiring.

Run a heat-bath Markov chain for each boundary partition. At every step choose the same uniformly sampled edge in both chains, sample the same independent uniform variable $U$, and set that edge open if $U$ is below its conditional open probability. Start both chains at the all-closed configuration. By the preceding inequality, the two configurations remain ordered at every update. Each marginal chain has its corresponding random-cluster measure as its stationary distribution: resampling one coordinate from its conditional distribution preserves that law. Because $0<p<1$ and $q>0$, every update gives both possible states positive probability; the finite chain is an irreducible Markov chain with aperiodicity, and hence converges to its unique stationary distribution. Taking expectations of any order-preserving function and passing to the limit proves the claimed stochastic domination of probability measures. At $q=1$ the two conditional probabilities agree, and the boundary condition has no effect on the independent bond percolation law.

For the final identity fix a plane embedding of the finite planar graph, and include the unbounded face in its planar dual graph. In the dual configuration ${\bar{\omega }}^{\ast }$, a dual edge is open exactly when its crossed primal edge is closed. Let $m=o(\omega )$. The spanning open primal subgraph has $|V|$ graph vertices, $m$ edges, and $k(\omega )$ components. The Euler formula for a connected planar graph, applied componentwise with the common exterior face accounted for, gives its number of faces asDeleting a closed primal edge merges its incident original faces precisely when its dual edge joins distinct dual components. Consequently the faces of the open primal subgraph correspond exactly to components of the open complementary dual subgraph. This remains true for bridges and loops, with their dual loops and bridges, and for a disconnected primal graph. Thus the planar cluster-count identity isAt the self-dual parameter of the random-cluster model, put $s=\sqrt{q}$ andFor fixed $G$ the factor $(1-p_{\mathrm{sd}}{)}^{|E|}$ is independent of $\omega$. The weight is therefore proportional toAbsorbing the remaining graph-dependent factor into the normalization gives the symmetric cluster weight at the self-dual parameter:Counting the outer dual face and all isolated primal graph vertices is essential for the constant in the Euler identity. No assumption that $G$ is self-dual is required for this proportionality.

Use $\mathbb{N}=\{0,1,\dots \}$, as required by the formula at zero, and composition of functions as multiplication in $M$. The displayed $T$ preserves identities, and for $n>0$,both sides send zero to zero. Thus $T$ is a functor on the one-object category.

For the shift monad on order-preserving maps of natural numbers, setThese are order-preserving functions. The equations $Tf\eta =\eta f$ and $\mu T^{2}f=Tf\mu$ hold pointwise, giving the required natural transformations. For the second equation, both sides are zero at $n=0,1$, and are $f(n-2)+1$ for $n\ge 2$. The two unit laws are $\mu \eta =\mu T\eta =1$. Associativity is checked byConsequently these maps define a monad. It is not an idempotent monad, since $\mu (0)=\mu (1)$, so $\mu$ cannot be invertible.

An algebra for a monad is a map $a\in M$ with $a\eta =1$ and $aTa=a\mu$. The first equation forces $a(n+1)=n$; monotonicity then forces $a(0)=0$. Thus $a=\mu$, which satisfies the second equation by the monad associativity law. The Eilenberg-Moore category therefore has exactly one object. Its endomorphisms $h$ satisfy $h\mu =\mu Th$, and this equation holds precisely when $h(0)=0$: evaluate at zero for necessity, and at $n>0$ both sides equal $h(n-1)$.

The Kleisli comparison functor takes its only object to this only algebra and sends $f\in M$ toIt is a bijection from the Kleisli arrows to the algebra endomorphisms, with inverse $h\mapsto (n\mapsto h(n+1))$. It preserves identities and composition by the comparison construction; directly, $K(\eta )=1$ and $K(g\star f)=K(g)K(f)$. Bijectivity on objects and arrows makes it an isomorphism of categories:

An encoding for radix sort must make the intended total order of sort keys agree with the lexicographic order of its fixed-width numerical digit tuples. The positional notation for bounded nonnegative integers has this property. At the most significant differing position $m$, a one-unit numerical digit difference contributes $R^m$, while all lower positions together contribute at mostThis geometric series shows why lower numerical digits cannot reverse that comparison. Leading zero padding works here because it preserves place values and the represented integer.

For signed integers in a known integer interval $L\le x\le U$, encode $e(x)=x-L$ and choose $d$ with $U-L<R^d$. This order-preserving function is also injective: $x<y$ exactly when $e(x)<e(y)$. For $-8\le x\le 7$, the four-bit encodings of $-8,-3,-1,0,4,7$ are $0000,0101,0111,1000,1100,1111$ after adding eight. Restore the original signed sort keys when displaying the complete sorting records; the encoding need not replace their data. Sorting the unsigned values of raw two's complement bit patterns would put nonnegative integers before negative ones, so their representation alone is not this ordered encoding.

For variable-length strings, first specify the alphabet order and whether a proper prefix precedes its extensions. As an original construction, use $a<b$, let every string have length at most three, encode $a$ as one and $b$ as two, and append zeros to width three. Zero is reserved for an end marker strictly below every real symbol. The strings $\epsilon ,a,aa,ab,b$ encode as $000,100,110,120,200$ in radix three, which preserves their lexicographic order. A differing real symbol decides the comparison; at a prefix boundary, the shorter string's zero comes before the extension's one or two. Left padding would instead encode $b$ as $002$ and $aa$ as $011$, reversing $aa<b$. Padding raw bytes with zero also fails if zero is an allowed data symbol: distinct strings can then receive the same encoding. A reserved end marker and an explicit symbol ordering are essential; byte order alone does not establish a desired human text order.

Let $M$ be the monoid of order-preserving functions $\mathbb{N}\to \mathbb{N}$, with $\mathbb{N}=\{0,1,\dots \}$, regarded as a one-object category. The endofunctor $T$ fixes that object and sends $f$ to $Tf(0)=0$, $Tf(n+1)=f(n)+1$. The displayed maps give its monad unit and multiplication. The multiplication is not injective, so this is not an idempotent monad. Its only algebra for a monad is $\mu$, because $a\eta =1$ forces $a(n+1)=n$ and monotonicity forces $a(0)=0$. Algebra endomorphisms are exactly the functions fixing zero. The Kleisli comparison functor sends $f$ to the function which is zero at zero and equals $f(n)$ at $n+1$; its inverse sends $h$ to $n\mapsto h(n+1)$. Thus the comparison is an isomorphism of categories even though the monad is not idempotent.

On a finite partially ordered state space, $\mu ⪯\nu$ means $\int fd\mu \le \int fd\nu$ for every real-valued order-preserving function $f$. Equivalently, every increasing subset has no larger probability under $\mu$ than under $\nu$. A coupling supported on pairs $(X,Y)$ with $X\le Y$ proves this relation. This concerns order of probability laws, rather than stochastic asymptotic order notation.