Identifiability and Order-Dimension Limits of In-Context Learning on Partial Orders

# Identifiability and Order-Dimension Limits of In-Context Learning on Partial Orders
Source: [https://arxiv.org/html/2608.14004](https://arxiv.org/html/2608.14004)
Faizanuddin AnsariAffiliation:Indian Statistical InstituteAffiliation:Kolkata, IndiaAffiliation:[faizanansari541@gmail\.com](mailto:[email protected]?subject=[From%20arXiv]%20PosetICL%20Paper)Swagatam DasAffiliation:Indian Statistical InstituteAffiliation:Kolkata, IndiaAffiliation:[swagatam\.das@isical\.ac\.in](mailto:[email protected]?subject=[From%20arXiv]%20PosetICL%20Paper)

###### Abstract

In\-context learning is commonly formalized as inference from examples of a function\. Partial orders instead combine transitivity, antisymmetry, and incomparability, so a finite prompt may not determine a queried comparison\. We develop a theory of in\-context learning on partial orders that separates logical identifiability, prompt teaching cost, structural complexity, and the exact capacity of a formal coordinate\-decoder class\. A version\-space semantics makes background knowledge and open\- versus closed\-world assumptions explicit\. For finite open\-world prompts with positive and negative comparisons, we prove an exact completion trichotomy: after taking the reflexive transitive closure of the positive demonstrations, a query is forced true, forced false because every true completion creates a cycle or violates a negative demonstration, or remains genuinely ambiguous\. For a knownnn\-element universe, we characterize the open\-world teaching number as the number of covers plus a blocker\-set hitting number, prove that its maximum over allnn\-element posets isn⁡\(n−1\)n\(n\-1\)and is uniquely attained by the antichain, and identify the blocker term as the exact cost of open\-world rather than complete\-Hasse semantics\. We formalize prompt\-dependentss\-coordinate decoders and use the classical coordinate\-order equivalence to obtain an exact representation boundary: dimension at mostssis necessary and sufficient, while width at mostssis a convenient sufficient condition\.

###### Abstract

This appendix supplies expanded proofs, edge\-case checks, and the exact enumeration underlying the deterministic ambiguity illustration in the main paper\. Results use the prefix S, and the opening map links each main\-paper result to the corresponding statement here\. We also give the full class\-maximum teaching argument, the open\- versus closed\-world teaching comparison, the exact coordinate\-decoder capability boundary, and details behind the structural profile table\.

## 1Introduction

Large language models can adapt to a task from demonstrations in the prompt without parameter updates, a capability known as in\-context learning \(ICL\)[3](https://arxiv.org/html/2608.14004#bib.bib1)\. Much of the theory studies prompts sampled from an unknown function and asks the model to predict the function value at a new input[10](https://arxiv.org/html/2608.14004#bib.bib2);[1](https://arxiv.org/html/2608.14004#bib.bib3);[5](https://arxiv.org/html/2608.14004#bib.bib4);[12](https://arxiv.org/html/2608.14004#bib.bib5);[2](https://arxiv.org/html/2608.14004#bib.bib6)\. Statistical analyses characterize Bayes\-optimal or information\-limited ICL under generative assumptions[14](https://arxiv.org/html/2608.14004#bib.bib7)\. These formulations are valuable, but many reasoning tasks are relational rather than single\-valued\.

A partial order⪯\\preceqis reflexive, antisymmetric, and transitive and may leave pairs incomparable\. Finite posets are represented by Hasse diagrams, and comparability is reachability in the reflexive transitive closure of the cover graph[7](https://arxiv.org/html/2608.14004#bib.bib17);[20](https://arxiv.org/html/2608.14004#bib.bib18)\. Posets therefore expose two difficulties that function\-learning abstractions can hide\. First, missing evidence is not the same as evidence of incomparability\. Second, even when the relation is fully specified, its structure may require several independent ordering coordinates or long transitive certificates\.

A prior empirical study introduced prompts for linear order and divisibility and reported performance saturation on current language models[8](https://arxiv.org/html/2608.14004#bib.bib23)\. This study asks what a relational prompt logically determines, how many labels are required to teach a finite poset, and which posets admit exact decoding by a formally specified coordinate\-order representation\. Our framework includes a background theoryℬ\\mathcal\{B\}\. This matters because a prompt naming “less than on natural numbers” may permit semantic recall from pretraining, whereas an abstract relation symbol with only poset axioms permits many completions\. We distinguish these cases through the version space[16](https://arxiv.org/html/2608.14004#bib.bib21)\. We also separate open\-world semantics, where unmentioned relations may hold, from closed\-world semantics, where a displayed finite Hasse diagram is declared complete[18](https://arxiv.org/html/2608.14004#bib.bib22)\.

### Contributions\.

\(1\) We formalize relational ICL using a version space of posets on a fixed known universe, consistent with demonstrations and background knowledge\. \(2\) We prove an exact true/false/unknown completion theorem for finite open\-world prompts with positive and negative demonstrations and give its per\-query classification cost\. \(3\) We characterize optimal open\-world teaching prompts through cover labels and a blocker\-set hitting problem, derive exact chain and antichain values, and prove the tight class maximumn⁡\(n−1\)n\(n\-1\)\. \(4\) We organize structural difficulty using height, width, order dimension, and positive and negative certificates, and establish an exact capability boundary for prompt\-dependent monotone coordinate decoders\.

### Overview\.

The paper moves from logic to teaching, representation, and certification\. We first formalize relational prompts through a fixed universe, a background theory, and a version space, making the distinction between open\- and closed\-world semantics explicit\. We then characterize when a queried comparison is forced true, forced false, or genuinely ambiguous, and illustrate this trichotomy through an exhaustive enumeration of four\-element posets\. Next, we determine the labels required to teach an entire finite poset and isolate the additional cost created by open\-world semantics\. Finally, we compare representative poset families, establish the exact capability boundary for coordinate\-order decoders, analyze positive and negative certificates, and conclude with the implications, scope, and limitations of the framework\.

## 2Related Work and Positioning

### ICL mechanisms and limits\.

Function\-learning, implicit\-optimization, Bayesian, and task\-representation accounts of ICL are developed by[10](https://arxiv.org/html/2608.14004#bib.bib2)\([10](https://arxiv.org/html/2608.14004#bib.bib2)\),[1](https://arxiv.org/html/2608.14004#bib.bib3)\([1](https://arxiv.org/html/2608.14004#bib.bib3)\),[5](https://arxiv.org/html/2608.14004#bib.bib4)\([5](https://arxiv.org/html/2608.14004#bib.bib4)\),[14](https://arxiv.org/html/2608.14004#bib.bib7)\([14](https://arxiv.org/html/2608.14004#bib.bib7)\), and[13](https://arxiv.org/html/2608.14004#bib.bib8)\([13](https://arxiv.org/html/2608.14004#bib.bib8)\)\. Recent mechanistic work finds task information in selected attention heads or low\-dimensional activation subspaces[24](https://arxiv.org/html/2608.14004#bib.bib9)\. A contemporaneous 2026 preprint develops a concept\-subspace account of structured ICL[19](https://arxiv.org/html/2608.14004#bib.bib10)\. These findings motivate the explicit prompt\-dependent coordinate decoder defined below\.

### Relational and graph reasoning\.

LLMs have been studied on graph problems and relational databases[21](https://arxiv.org/html/2608.14004#bib.bib15);[22](https://arxiv.org/html/2608.14004#bib.bib12)\. A contemporaneous 2026 preprint analyzes relational\-database ICL through support identifiability and relational label coverage[4](https://arxiv.org/html/2608.14004#bib.bib11)\. Those settings concern database prediction\. We instead study logical completion of mathematical partial orders and use order dimension as the representation invariant\. Transformer expressivity results establish universality under suitable constructions[17](https://arxiv.org/html/2608.14004#bib.bib13);[9](https://arxiv.org/html/2608.14004#bib.bib14); they do not imply that a finite prompt uniquely identifies its target\.

### Order theory\.

Dushnik–Miller dimension is the minimum number of linear extensions whose intersection is a poset[7](https://arxiv.org/html/2608.14004#bib.bib17);[20](https://arxiv.org/html/2608.14004#bib.bib18)\. The dimension of finite divisibility orders has a developed combinatorial theory[15](https://arxiv.org/html/2608.14004#bib.bib20)\. We use these classical results rather than claiming them as new; our contribution is their connection to a precisely restricted ICL representation class\.

## 3Formal Model

Fix a finite known universeUU\. Every targetP=\(U,⪯P\)P=\(U,\\preceq\_\{P\}\)and every hypothesis in the background theoryℬ\\mathcal\{B\}has this same ground set\.

We represent the labeled relational evidence in a prompt by

𝒟:=\(𝒟\+,𝒟−\),𝒟\+,𝒟−⊆U×U,\\mathcal\{D\}:=\(\\mathcal\{D\}^\{\+\},\\mathcal\{D\}^\{\-\}\),\\qquad\\mathcal\{D\}^\{\+\},\\mathcal\{D\}^\{\-\}\\subseteq U\\times U,where:

- •\(x,y\)∈𝒟\+\(x,y\)\\in\\mathcal\{D\}^\{\+\}is a positive demonstration asserting thatx⪯Pyx\\preceq\_\{P\}y; and
- •\(x,y\)∈𝒟−\(x,y\)\\in\\mathcal\{D\}^\{\-\}is a negative demonstration asserting thatx⋠Pyx\\not\\preceq\_\{P\}y\.

Thus,𝒟\\mathcal\{D\}denotes the complete labeled demonstration component of the prompt and does not include the query\. We write

\|𝒟\|:=\|𝒟\+\|\+\|𝒟−\|\|\\mathcal\{D\}\|:=\|\\mathcal\{D\}^\{\+\}\|\+\|\\mathcal\{D\}^\{\-\}\|for the total number of demonstrations\.

A queryq=\(a,b\)∈U×Uq=\(a,b\)\\in U\\times Uasks whethera⪯Pba\\preceq\_\{P\}b\. The classℬ\\mathcal\{B\}may additionally encode relation semantics or a completeness assumption\. Fixing the common ground setUUmakes every demonstrated pair and every query well\-defined for every hypothesis inℬ\\mathcal\{B\}\.

###### Definition 1\(Version space and identifiability\)\.

For a posetP=\(U,⪯P\)P=\(U,\\preceq\_\{P\}\), let

RP:=\{\(x,y\)∈U2:x⪯Py\}R\_\{P\}:=\\\{\(x,y\)\\in U^\{2\}:x\\preceq\_\{P\}y\\\}denote the graph of its order relation\. Given a labeled demonstration set𝒟=\(𝒟\+,𝒟−\)\\mathcal\{D\}=\(\\mathcal\{D\}^\{\+\},\\mathcal\{D\}^\{\-\}\), its version space under the background theoryℬ\\mathcal\{B\}is

𝒱ℬ\(𝒟\)=\{P∈ℬ:\\displaystyle\\mathcal\{V\}\_\{\\mathcal\{B\}\}\(\\mathcal\{D\}\)=\\bigl\\\{P\\in\\mathcal\{B\}:\{\}𝒟\+⊆RP,\\displaystyle\\mathcal\{D\}^\{\+\}\\subseteq R\_\{P\},𝒟−∩RP=∅\}\.\\displaystyle\\mathcal\{D\}^\{\-\}\\cap R\_\{P\}=\\varnothing\\bigr\\\}\.The prompt𝒟\\mathcal\{D\}is*satisfiable underℬ\\mathcal\{B\}*when

𝒱ℬ​\(𝒟\)≠∅\.\\mathcal\{V\}\_\{\\mathcal\{B\}\}\(\\mathcal\{D\}\)\\neq\\varnothing\.For a satisfiable prompt, a queryq=\(a,b\)q=\(a,b\)is*identified*if

\|\{𝟏\[a⪯Pb\]:P∈𝒱ℬ\(𝒟\)\}\|=1\.\\left\|\\left\\\{\\mathbf\{1\}\[a\\preceq\_\{P\}b\]:P\\in\\mathcal\{V\}\_\{\\mathcal\{B\}\}\(\\mathcal\{D\}\)\\right\\\}\\right\|=1\.

A binary answer rule is*universally sound*for\(ℬ,𝒟,q\)\(\\mathcal\{B\},\\mathcal\{D\},q\)if it returns the correct answer for everyP∈𝒱ℬ​\(𝒟\)P\\in\\mathcal\{V\}\_\{\\mathcal\{B\}\}\(\\mathcal\{D\}\)\.

Under*open\-world semantics*,ℬ\\mathcal\{B\}permits additional comparisons onUUbeyond those explicitly demonstrated or forced by the partial\-order axioms, provided that no negative demonstration is violated\. Under*closed\-world Hasse semantics*, the displayed finite DAG \(Directed acyclic graph\) is declared to be the complete Hasse diagram, andℬ\\mathcal\{B\}contains only the poset generated by that diagram\.

## 4Open\-World Identifiability

###### Proposition 2\(Sound\-answer criterion\)\.

A universally sound binary answer exists for\(ℬ,𝒟,q\)\(\\mathcal\{B\},\\mathcal\{D\},q\)if and only ifqqis identified\.

###### Proof\.

If all consistent posets give valuevv, returningvvis sound\. If two consistent posets disagree, either binary output is wrong for one of them; randomization cannot guarantee correctness for both\. ∎

Supplementary Proposition S1 gives the fully quantified version, including the randomized\-rule case and the nonempty\-version\-space assumption\.

The general criterion is simple but exposes the correct evaluation target\. The next theorem gives an exact characterization for arbitrary finite positive and negative comparison prompts under the least restrictive poset background\.

For a reflexive relationRRandx∈Ux\\in U, write

PredR⁡\(x\)=\{u:u​R​x\},SuccR⁡\(x\)=\{v:x​R​v\}\.\\operatorname\{Pred\}\_\{R\}\(x\)=\\\{u:uRx\\\},\\qquad\\operatorname\{Succ\}\_\{R\}\(x\)=\\\{v:xRv\\\}\.
###### Theorem 3\(Open\-world completion trichotomy\)\.

LetUUbe finite, letℬ\\mathcal\{B\}be the class of all posets onUU, and let𝒟=\(𝒟\+,𝒟−\)\\mathcal\{D\}=\(\\mathcal\{D\}^\{\+\},\\mathcal\{D\}^\{\-\}\)be satisfiable\. PutR=TC⁡\(𝒟\+\)R=\\operatorname\{TC\}\(\\mathcal\{D\}^\{\+\}\), whereTC\\operatorname\{TC\}denotes reflexive transitive closure\. For a query\(a,b\)\(a,b\), exactly one of the following holds:

1. 1\.a​R​baRb, in which case the query is identified true;
2. 2\.a​𝑅​ba\{\\not\\mathrel\{R\}\}band eitherb​R​abRaor\(PredR⁡\(a\)×SuccR⁡\(b\)\)∩𝒟−≠∅\\bigl\(\\operatorname\{Pred\}\_\{R\}\(a\)\\times\\operatorname\{Succ\}\_\{R\}\(b\)\\bigr\)\\cap\\mathcal\{D\}^\{\-\}\\neq\\varnothing, in which case the query is identified false;
3. 3\.neither condition holds, in which case the query is unidentifiable\.

###### Proof\.

Satisfiability gives a poset containing𝒟\+\\mathcal\{D\}^\{\+\}and excluding𝒟−\\mathcal\{D\}^\{\-\}\. ThereforeRRis antisymmetric andR∩𝒟−=∅R\\cap\\mathcal\{D\}^\{\-\}=\\varnothing; henceP−=\(U,R\)P^\{\-\}=\(U,R\)is itself a consistent poset\. This disjointness is why, after adding\(a,b\)\(a,b\), it suffices to test only the newly forced predecessor–successor rectangle against𝒟−\\mathcal\{D\}^\{\-\}\. Ifa​R​baRb, every poset containing𝒟\+\\mathcal\{D\}^\{\+\}containsRR, so every completion makes the query true\.

Assume now thata​𝑅​ba\{\\not\\mathrel\{R\}\}b\. The posetP−P^\{\-\}is a consistent completion in which the query is false\. It remains to decide whether a true completion exists\. Any poset containingRRanda⪯ba\\preceq bmust also contain every pair\(x,y\)\(x,y\)withx​R​axRaandb​R​ybRy, by transitivity\. Conversely, the reflexive transitive closure after adding\(a,b\)\(a,b\)is exactly

Ra,b=R∪\(PredR⁡\(a\)×SuccR⁡\(b\)\)\.R\_\{a,b\}=R\\cup\\bigl\(\\operatorname\{Pred\}\_\{R\}\(a\)\\times\\operatorname\{Succ\}\_\{R\}\(b\)\\bigr\)\.The displayed rectangle is forced by transitivity\. For the reverse inclusion, call the right\-hand relationR′R^\{\\prime\}\. It containsRRand\(a,b\)\(a,b\)and is transitive: composing anRR\-pair with a rectangle pair, or a rectangle pair with anRR\-pair, stays in the rectangle; composing two rectangle pairs does as well\. Hence the least reflexive transitive relation containingR∪\{\(a,b\)\}R\\cup\\\{\(a,b\)\\\}is contained inR′R^\{\\prime\}, proving equality\.

Ifb​R​abRa, thenRa,bR\_\{a,b\}contains botha​R​baRbandb​R​abRafor distincta,ba,b, so no antisymmetric true completion exists\. If the displayed cross\-product contains a negative demonstration, every true completion violates that demonstration\. Thus either condition in item 2 forces false\.

Suppose neither obstruction holds\. Sinceb​𝑅​ab\{\\not\\mathrel\{R\}\}a, adding\(a,b\)\(a,b\)creates no directed cycle, soRa,bR\_\{a,b\}is antisymmetric\. By assumption it also avoids every pair in𝒟−\\mathcal\{D\}^\{\-\}\. ThereforeP\+=\(U,Ra,b\)P^\{\+\}=\(U,R\_\{a,b\}\)is a consistent poset in which the query is true, whileP−P^\{\-\}is a consistent poset in which it is false\. The query is unidentifiable\. These alternatives are mutually exclusive and exhaustive\. ∎

Lemmas S2–S3 \(Appendix\) isolate the least\-closure and one\-edge\-closure arguments, and Theorem S4 \(Appendix\) restates the trichotomy with a fully modular proof\.

### Example\.

LetU=\{a,b,c\}U=\\\{a,b,c\\\}, let𝒟\+=\{\(a,b\)\}\\mathcal\{D\}^\{\+\}=\\\{\(a,b\)\\\}, and let𝒟−=\{\(a,c\)\}\\mathcal\{D\}^\{\-\}=\\\{\(a,c\)\\\}\. The querya⪯ba\\preceq bis forced true\. Forb⪯cb\\preceq c, adding\(b,c\)\(b,c\)forces\(a,c\)\(a,c\)by transitivity, contradicting the negative label, so the query is forced false even thoughc⪯bc\\preceq bis not known\. By contrast,c⪯bc\\preceq bis ambiguous: both the least closure and its extension by\(c,b\)\(c,b\)satisfy the prompt\. This illustrates all three outcomes without invoking model behavior\.

###### Corollary 4\(Positive\-only trichotomy\)\.

If𝒟−=∅\\mathcal\{D\}^\{\-\}=\\varnothing, a query is identified true whena​R​baRb, identified false whena≠ba\\neq bandb​R​abRa, and otherwise unidentifiable\.

Theorem[3](https://arxiv.org/html/2608.14004#Thmtheorem3)is also an algorithm\. ComputeRRonce inO⁡\(\|U\|3\)O\(\|U\|^\{3\}\)time by a straightforward transitive\-closure method\. For each query, testa​R​baRbandb​R​abRa, then scan each\(x,y\)∈𝒟−\(x,y\)\\in\\mathcal\{D\}^\{\-\}and testx​R​axRaandb​R​ybRy; this costsO⁡\(\|𝒟−\|\)O\(\|\\mathcal\{D\}^\{\-\}\|\)per query after closure preprocessing\. With\|U\|\|U\|\-bit predecessor, successor, and negative\-adjacency bitsets, the rectangle test costsO⁡\(\|U\|2/w\)O\(\|U\|^\{2\}/w\)word operations per query, wherewwis the machine word size\. A query between two distinct elements absent from all demonstrations falls into the ambiguous case unless background knowledge relates them\.

Figure 1:Exact ambiguity fraction over all 219 labeled four\-element posets, averaged uniformly over targets, observedmm\-subsets of the 12 nonreflexive ordered pairs, and unobserved queries\. Observed labels are target\-consistent; the calculation is exhaustive\.
### Deterministic finite\-universe illustration\.

The trichotomy also permits a model\-free prevalence calculation\. We exhaustively enumerate all 219 labeled posets on four elements\. For eachm∈\{0,…,11\}m\\in\\\{0,\\ldots,11\\\}, we average uniformly overmm\-subsets of the 12 ordered nonreflexive pairs and over unobserved queries, using target\-consistent labels\. Figure[1](https://arxiv.org/html/2608.14004#S4.F1)shows that ambiguity decreases with coverage but remains0\.44750\.4475when 11 of 12 labels are observed\. This finite averaging scheme is not a model evaluation or a universal poset distribution; the supplement gives the exact values, and the accompanying code package reproduces them\.

The next elementary statement is the standard reachability interpretation of a complete Hasse diagram[20](https://arxiv.org/html/2608.14004#bib.bib18); we record it to contrast closed\- and open\-world semantics\.

###### Observation 5\(Closed\-world reachability\)\.

If a finite DAGH=\(U,E\)H=\(U,E\)is declared to be the complete Hasse diagram, thena⪯ba\\preceq bif and only ifb∈ReachH⁡\(a\)b\\in\\operatorname\{Reach\}\_\{H\}\(a\), including the length\-zero path whena=ba=b\.

###### Proof\.

A directed path is a chain of cover relations and implies comparability by transitivity\. Conversely, leta≺ba\\prec b\. If the pair is not a cover, chooseccwitha≺c≺ba\\prec c\\prec band refine both intervals\. Finiteness makes the refinement terminate in a saturated chain of covers, hence a directed Hasse path\. Reflexivity handlesa=ba=b\. ∎

Supplementary Observation S5 gives the expanded saturated\-chain argument and states the required completeness assumption explicitly\.

These statements depend onℬ\\mathcal\{B\}\. Ifℬ\\mathcal\{B\}fixes the standard numerical order, a query may be identified from background semantics even when demonstrations alone do not identify it\. Therefore a benchmark should state whether it measures prompt\-only induction, use of pretrained semantic knowledge, or both\. Supplementary Proposition S6 formalizes the monotonicity of identifiability and teaching cost under stronger background knowledge\.

## 5Prompt Teaching Complexity

Identifiability can also be studied as a sample\-complexity question\. LetℬU\\mathcal\{B\}\_\{U\}be the class of all posets on the known finite universeUU\. A labeled demonstration set𝒟\\mathcal\{D\}*teaches*PPunder open\-world semantics if𝒱ℬU​\(𝒟\)=\{P\}\\mathcal\{V\}\_\{\\mathcal\{B\}\_\{U\}\}\(\\mathcal\{D\}\)=\\\{P\\\}\. Define

τow​\(P\)=min⁡\{\|𝒟\+\|\+\|𝒟−\|:𝒱ℬU​\(𝒟\)=\{P\}\}\.\\tau\_\{\\mathrm\{ow\}\}\(P\)=\\min\\\{\|\\mathcal\{D\}^\{\+\}\|\+\|\\mathcal\{D\}^\{\-\}\|:\\mathcal\{V\}\_\{\\mathcal\{B\}\_\{U\}\}\(\\mathcal\{D\}\)=\\\{P\\\}\\\}\.The known ground set is essential: if arbitrary fresh elements are allowed, no finite prompt can isolate an antichain because a new isolated element may always be added\. This definition specializes teaching dimension to relation\-valued concepts[11](https://arxiv.org/html/2608.14004#bib.bib24)\. LetCov⁡\(P\)\\operatorname\{Cov\}\(P\)be the strict cover relation\. For an*ordered*incomparable paira∥Pba\\parallel\_\{P\}b, define its blocker set

BP\(a,b\)=\(PredP\(a\)×SuccP\(b\)\)∖⪯P\.B\_\{P\}\(a,b\)=\\bigl\(\\operatorname\{Pred\}\_\{P\}\(a\)\\times\\operatorname\{Succ\}\_\{P\}\(b\)\\bigr\)\\setminus\\preceq\_\{P\}\.Letβ⁡\(P\)\\beta\(P\)be the minimum size of a setN⊆U2∖⪯PN\\subseteq U^\{2\}\\setminus\\preceq\_\{P\}that intersectsBP​\(a,b\)B\_\{P\}\(a,b\)for every ordered incomparable pair\(a,b\)\(a,b\)\. The orientations\(a,b\)\(a,b\)and\(b,a\)\(b,a\)are distinct constraints; this convention is essential for the antichain value below\.

###### Theorem 6\(Exact teaching characterization\)\.

For every finite posetPP,

τow​\(P\)=\|Cov⁡\(P\)\|\+β⁡\(P\)\.\\tau\_\{\\mathrm\{ow\}\}\(P\)=\|\\operatorname\{Cov\}\(P\)\|\+\\beta\(P\)\.

###### Proof\.

Every cover\(x,y\)\(x,y\)must be a positive demonstration\. Otherwise deleting onlyx⪯yx\\preceq yleaves a poset: a transitivity violation would require an intermediatex≺z≺yx\\prec z\\prec y, contradicting coverhood\. The reduced poset agrees with every other valid label, so the prompt would not teachPP\.

LetNNbe the negative labels of a teaching set\. IfNNmissesBP​\(a,b\)B\_\{P\}\(a,b\)for somea∥Pba\\parallel\_\{P\}b, then addinga⪯ba\\preceq band closing transitively givesP∪\(PredP⁡\(a\)×SuccP⁡\(b\)\)P\\cup\(\\operatorname\{Pred\}\_\{P\}\(a\)\\times\\operatorname\{Succ\}\_\{P\}\(b\)\)\. It is antisymmetric becauseb⋠Pab\\not\\preceq\_\{P\}aand it avoidsNNby assumption, producing a second consistent poset\. ThusNNmust be a hitting set and\|N\|≥β⁡\(P\)\|N\|\\geq\\beta\(P\)\.

Conversely, label every cover positive and choose a blocker hitting setNNof sizeβ⁡\(P\)\\beta\(P\)as negative\. The covers generate all ofPP\. Any different consistent extension must add some ordered pair\(a,b\)∉P\(a,b\)\\notin P\. The reverse pair cannot lie inPPby antisymmetry, soa∥Pba\\parallel\_\{P\}b\. Transitivity then forces every pair inBP​\(a,b\)B\_\{P\}\(a,b\), including a member ofNN, a contradiction\. Hence the prompt teachesPP\. ∎

Supplementary Lemma S7 proves cover necessity separately, while Supplementary Theorem S8 gives the complete lower\- and upper\-bound proof with the one\-edge extension justified through Supplementary Lemma S3\.

###### Corollary 7\(General bounds and exact extremal values\)\.

IfI⁡\(P\)I\(P\)is the number of unordered incomparable pairs, then

\|Cov⁡\(P\)\|≤τow​\(P\)≤\|Cov⁡\(P\)\|\+2​I​\(P\)\.\|\\operatorname\{Cov\}\(P\)\|\\leq\\tau\_\{\\mathrm\{ow\}\}\(P\)\\leq\|\\operatorname\{Cov\}\(P\)\|\+2I\(P\)\.For thenn\-element chainCnC\_\{n\}and antichainAnA\_\{n\},

τow​\(Cn\)=n−1,τow​\(An\)=n⁡\(n−1\)\.\\tau\_\{\\mathrm\{ow\}\}\(C\_\{n\}\)=n\-1,\\qquad\\tau\_\{\\mathrm\{ow\}\}\(A\_\{n\}\)=n\(n\-1\)\.Moreover, among all posets on annn\-element universe,

maxP⁡τow​\(P\)=n⁡\(n−1\),\\max\_\{P\}\\tau\_\{\\mathrm\{ow\}\}\(P\)=n\(n\-1\),and equality is attained uniquely by the antichain\.

###### Proof\.

Each blocker set contains its defining ordered pair\(a,b\)\(a,b\), so selecting all ordered incomparable pairs is a hitting set of size2​I​\(P\)2I\(P\)\. A chain hasn−1n\-1covers and no incomparable pairs\. In an antichain,BP​\(a,b\)=\{\(a,b\)\}B\_\{P\}\(a,b\)=\\\{\(a,b\)\\\}for every distinct ordered pair, so alln⁡\(n−1\)n\(n\-1\)negative labels are required\.

For the class maximum, the number of unordered comparable pairs is\(n2\)−I⁡\(P\)\\binom\{n\}\{2\}\-I\(P\), and every cover is such a pair\. Hence

τow​\(P\)≤\|Cov⁡\(P\)\|\+2​I​\(P\)≤\(n2\)\+I⁡\(P\)≤n⁡\(n−1\)\.\\tau\_\{\\mathrm\{ow\}\}\(P\)\\leq\|\\operatorname\{Cov\}\(P\)\|\+2I\(P\)\\leq\\binom\{n\}\{2\}\+I\(P\)\\leq n\(n\-1\)\.Equality in the final inequality requiresI⁡\(P\)=\(n2\)I\(P\)=\\binom\{n\}\{2\}, so every distinct pair is incomparable andPPis the antichain\. The antichain attains the bound by the preceding calculation\. ∎

Supplementary Corollary S9 records the edge cases, the class\-maximum argument, and the following open\- versus closed\-world comparison\.

### Price of open\-world semantics\.

If a prompt is declared to be the complete Hasse diagram, letτcw​\(P\)\\tau\_\{\\mathrm\{cw\}\}\(P\)be the minimum number of displayed cover edges needed to specifyPP\. Every cover is necessary and all covers are sufficient, so

τcw​\(P\)=\|Cov⁡\(P\)\|,τow​\(P\)−τcw​\(P\)=β⁡\(P\)\.\\tau\_\{\\mathrm\{cw\}\}\(P\)=\|\\operatorname\{Cov\}\(P\)\|,\\qquad\\tau\_\{\\mathrm\{ow\}\}\(P\)\-\\tau\_\{\\mathrm\{cw\}\}\(P\)=\\beta\(P\)\.Thusβ⁡\(P\)\\beta\(P\)is exactly the label cost of open\-world semantics\.

Theorem[6](https://arxiv.org/html/2608.14004#Thmtheorem6)turns optimal prompt design into a structured hitting\-set problem\. Minimum hitting set is NP\-hard in general; we do not establish the complexity of the blocker sets induced specifically by posets\. The theorem also shows why order dimension alone does not determine teaching cost: a nontrivial antichain has dimension two but quadratic teaching number, whereas a chain has dimension one and linear teaching number\. Background theory can shrink both quantities, which is whyℬ\\mathcal\{B\}must be reported\.

## 6Structural Complexity

For a finite prompt–query instance with target posetPPand queryq=\(a,b\)q=\(a,b\), we use the profile

𝖢𝗈𝗆𝗉⁡\(P,q\)=\(CLOSE\\displaystyle\\mathsf\{Comp\}\(P,q\)=\\bigl\(OPEN0​p​t​\(P\),0​p​t​\(P\),dim⁡\(P\),λP\+​\(q\),νP−​\(q\),ηℬ​\(𝒟,q\)\)\.\\displaystyle 0pt\(P\),0pt\(P\),\\operatorname\{dim\}\(P\),\\lambda\_\{P\}^\{\+\}\(q\),\\nu\_\{P\}^\{\-\}\(q\),\\eta\_\{\\mathcal\{B\}\}\(\\mathcal\{D\},q\)\\bigr\)\.This is a taxonomy rather than a scalar ordering\. Hereηℬ\\eta\_\{\\mathcal\{B\}\}is zero when the query is identified and one otherwise\. Ifa⪯Pba\\preceq\_\{P\}b, thenλP\+​\(a,b\)\\lambda\_\{P\}^\{\+\}\(a,b\)is the shortest Hasse\-path length and we setνP−​\(a,b\)=∞\\nu\_\{P\}^\{\-\}\(a,b\)=\\infty\. Ifa⋠Pba\\not\\preceq\_\{P\}b, defineνP−​\(a,b\)=\|ReachH⁡\(P\)⁡\(a\)\|\\nu\_\{P\}^\{\-\}\(a,b\)=\|\\operatorname\{Reach\}\_\{H\(P\)\}\(a\)\|and setλP\+​\(a,b\)=∞\\lambda\_\{P\}^\{\+\}\(a,b\)=\\infty; Lemma[14](https://arxiv.org/html/2608.14004#Thmtheorem14)shows that this reachable set is the canonical minimum forward\-closed witness\. Height and positive path length measure chain depth; width measures incomparability; order dimension measures the number of linear orders needed to realize all comparisons\.

For a family\-level view, letL\+​\(P\)=maxa⪯b⁡λP\+​\(a,b\)L^\{\+\}\(P\)=\\max\_\{a\\preceq b\}\\lambda\_\{P\}^\{\+\}\(a,b\)andN−​\(P\)=maxa⋠b⁡νP−​\(a,b\)N^\{\-\}\(P\)=\\max\_\{a\\not\\preceq b\}\\nu\_\{P\}^\{\-\}\(a,b\)\. Table[1](https://arxiv.org/html/2608.14004#S6.T1)uses these worst\-case query coordinates\. ForN=∏i=1rpieiN=\\prod\_\{i=1\}^\{r\}p\_\{i\}^\{e\_\{i\}\}, writeE=∑ieiE=\\sum\_\{i\}e\_\{i\}andWN=0​p​t​\(Div⁡\(N\)\)W\_\{N\}=0pt\(\\operatorname\{Div\}\(N\)\); forDn=\(\[n\],∣\)D\_\{n\}=\(\[n\],\\mid\), letr\(n\)=max\{r:p1⋯pr≤n\}r\(n\)=\\max\\\{r:p\_\{1\}\\cdots p\_\{r\}\\leq n\\\}\.

Table 1:Structural profiles forn≥2n\\geq 2\. Entries are exact except the displayed lower bounds forDnD\_\{n\};WNW\_\{N\}denotes the width of the fixed divisor lattice\. The table makes visible that cover count, width, dimension, and positive/negative certificate sizes are independent axes rather than a single notion of difficulty\.For example, a chain has dimension one but can have an arbitrarily long positive certificate, whereas a cover query in a Boolean lattice has certificate length one even though the family has growing width and dimension\.

###### Proposition 8\(Standard families\)\.

Forn,m,r≥1n,m,r\\geq 1: \(i\) a chainCnC\_\{n\}has dimension11; \(ii\) the Boolean latticeBm=\(2\[m\],⊆\)B\_\{m\}=\(2^\{\[m\]\},\\subseteq\)has dimensionmm; and \(iii\) ifN=∏i=1rpieiN=\\prod\_\{i=1\}^\{r\}p\_\{i\}^\{e\_\{i\}\}with distinct primes andei≥1e\_\{i\}\\geq 1, then the poset of positive divisors ofNNunder divisibility has dimensionrr\.

###### Proof\.

A chain is already a linear order\. ForB1B\_\{1\}, the claim is the chain case\. ForB2B\_\{2\}, the two membership indicators give the upper bound, whileB2B\_\{2\}is not a chain, so its dimension is at least two\. Assumem≥3m\\geq 3\. Themmmembership indicatorsϕi\(A\)=𝟏\[i∈A\]\\phi\_\{i\}\(A\)=\\mathbf\{1\}\[i\\in A\]give anmm\-coordinate realization\. By the classical coordinate\-order equivalence recorded later as Theorem[11](https://arxiv.org/html/2608.14004#Thmtheorem11), this gives anmm\-extension upper bound\. For the lower bound, letai=\{i\}a\_\{i\}=\\\{i\\\}andbi=\[m\]∖\{i\}b\_\{i\}=\[m\]\\setminus\\\{i\\\}\. Thenai⊆bja\_\{i\}\\subseteq b\_\{j\}exactly wheni≠ji\\neq j, while each pair\(ai,bi\)\(a\_\{i\},b\_\{i\}\)is incomparable\. In a linear extension, at most one such pair can be reversed: if bothbi<aib\_\{i\}<a\_\{i\}andbj<ajb\_\{j\}<a\_\{j\}held fori≠ji\\neq j, the forced relationsai<bja\_\{i\}<b\_\{j\}andaj<bia\_\{j\}<b\_\{i\}would form a cycle\. Every incomparable pair must be reversed in some member of a realizer, so at leastmmextensions are required\.

For the divisor poset, mapd\|Nd\\mid Nto\(vp1​\(d\),…,vpr​\(d\)\)\(v\_\{p\_\{1\}\}\(d\),\\ldots,v\_\{p\_\{r\}\}\(d\)\)\. Divisibility is coordinatewise comparison, giving dimension at mostrr\. The squarefree divisors∏i∈Api\\prod\_\{i\\in A\}p\_\{i\}induce a copy ofBrB\_\{r\}; dimension is monotone under subposets, so the lower bound isrr\. ∎

Supplementary Theorem S10 proves the coordinate\-order equivalence used for the upper bounds, and Supplementary Proposition S12 gives the full family arguments, including them=1,2m=1,2Boolean\-lattice cases\.

###### Corollary 9\(Growing dimension of finite divisibility\)\.

LetDn=\(\[n\],∣\)D\_\{n\}=\(\[n\],\\mid\)\. If the product of the firstrrprimes is at mostnn, thendim⁡\(Dn\)≥r\\operatorname\{dim\}\(D\_\{n\}\)\\geq r\. Consequently, the dimensions ofDnD\_\{n\}are unbounded asn→∞n\\to\\infty\.

###### Proof\.

LetM=p1⋯pr≤nM=p\_\{1\}\\cdots p\_\{r\}\\leq n\. Every squarefree divisor ofMMlies in\[n\]\[n\], and these divisors induce a copy ofBrB\_\{r\}under divisibility\. Proposition[8](https://arxiv.org/html/2608.14004#Thmtheorem8)and monotonicity under subposets give the bound\. Sharper asymptotic estimates are known[15](https://arxiv.org/html/2608.14004#bib.bib20)\. ∎

Thus the comparison is family\-level: higher order dimension requires more coordinates for exact uniform representation under the decoder defined next, but it does not impose a behavioral difficulty ordering on every individual query or model\.

## 7Coordinate\-Order Representation Limits

###### Definition 10\(Prompt\-dependent monotone coordinate decoder\)\.

Let𝖯𝗋𝗈𝗆𝗉𝗍⁡\(U\)\\mathsf\{Prompt\}\(U\)be the set of finite labeled prompts overUU, and fix an integers≥1s\\geq 1\. Anss\-coordinate decoder is a fixed map

Φ:𝖯𝗋𝗈𝗆𝗉𝗍⁡\(U\)⟶\(ℝU\)s,Φ⁡\(𝒟\)=\(ϕ1𝒟,…,ϕs𝒟\),\\Phi:\\mathsf\{Prompt\}\(U\)\\longrightarrow\(\\mathbb\{R\}^\{U\}\)^\{s\},\\qquad\\Phi\(\\mathcal\{D\}\)=\(\\phi\_\{1\}^\{\\mathcal\{D\}\},\\ldots,\\phi\_\{s\}^\{\\mathcal\{D\}\}\),together with the conjunctive decision rule

AΦ\(𝒟;x,y\)=1⟺\\displaystyle A\_\{\\Phi\}\(\\mathcal\{D\};x,y\)=1\\quad\\Longleftrightarrowϕi𝒟​\(x\)≤ϕi𝒟​\(y\)​for every​i∈\[s\]\.\\displaystyle\\phi\_\{i\}^\{\\mathcal\{D\}\}\(x\)\\leq\\phi\_\{i\}^\{\\mathcal\{D\}\}\(y\)\\text\{ for every \}i\\in\[s\]\.A task family𝒯\\mathcal\{T\}is a subset of𝖯𝗋𝗈𝗆𝗉𝗍⁡\(U\)×𝖯𝗈𝗌𝖾𝗍⁡\(U\)\\mathsf\{Prompt\}\(U\)\\times\\mathsf\{Poset\}\(U\)that is functional in its first coordinate: if\(𝒟,P\),\(𝒟,Q\)∈𝒯\(\\mathcal\{D\},P\),\(\\mathcal\{D\},Q\)\\in\\mathcal\{T\}, thenP=QP=Q\. Write this unique target asP𝒟P\_\{\\mathcal\{D\}\}\. The decoder is*exact on𝒯\\mathcal\{T\}*ifAΦ\(𝒟;x,y\)=𝟏\[x⪯P𝒟y\]A\_\{\\Phi\}\(\\mathcal\{D\};x,y\)=\\mathbf\{1\}\[x\\preceq\_\{P\_\{\\mathcal\{D\}\}\}y\]for every\(𝒟,P𝒟\)∈𝒯\(\\mathcal\{D\},P\_\{\\mathcal\{D\}\}\)\\in\\mathcal\{T\}and every\(x,y\)∈U2\(x,y\)\\in U^\{2\}\. The coordinate maps may depend on the prompt, butΦ\\Phiis one decoder for the whole family\. This is a zero\-error exact\-representation notion; no claim is made here for approximate or error\-tolerant decoding\.

For a single posetPP, anss\-coordinate order representation means mapsϕ1,…,ϕs:U→ℝ\\phi\_\{1\},\\ldots,\\phi\_\{s\}:U\\to\\mathbb\{R\}satisfyingx⪯Pyx\\preceq\_\{P\}yif and only ifϕi​\(x\)≤ϕi​\(y\)\\phi\_\{i\}\(x\)\\leq\\phi\_\{i\}\(y\)for everyi∈\[s\]i\\in\[s\]\. The following equivalence is classical; see[20](https://arxiv.org/html/2608.14004#bib.bib18)\. We record it with a proof for self\-containment because Corollary[12](https://arxiv.org/html/2608.14004#Thmtheorem12)depends on the exact biconditional form\.

###### Theorem 11\(Classical coordinate\-order equivalence\)\.

A finite poset has anss\-coordinate order representation if and only ifdim⁡\(P\)≤s\\operatorname\{dim\}\(P\)\\leq s\.

###### Proof\.

Supposeϕ1,…,ϕs\\phi\_\{1\},\\ldots,\\phi\_\{s\}representPP\. Fix a linear extensionL0L\_\{0\}ofPP\. For eachii, sort elements by increasingϕi\\phi\_\{i\}, breaking ties byL0L\_\{0\}, to obtain a linear extensionLiL\_\{i\}\. Ifx⪯Pyx\\preceq\_\{P\}y, everyLiL\_\{i\}placesxxbeforeyy\. Ifx⋠Pyx\\not\\preceq\_\{P\}y, the representation gives somejjwithϕj​\(x\)\>ϕj​\(y\)\\phi\_\{j\}\(x\)\>\\phi\_\{j\}\(y\), soLjL\_\{j\}placesyybeforexx\. HenceP=∩iLiP=\\cap\_\{i\}L\_\{i\}anddim⁡\(P\)≤s\\operatorname\{dim\}\(P\)\\leq s\. Conversely, ifdim⁡\(P\)=t≤s\\operatorname\{dim\}\(P\)=t\\leq s, take att\-member realizer and repeat one of its linear extensions untilssordersL1,…,LsL\_\{1\},\\ldots,L\_\{s\}are listed\. Letϕi​\(x\)\\phi\_\{i\}\(x\)be the rank ofxxinLiL\_\{i\}\. Then the coordinatewise condition is equivalent to membership in everyLiL\_\{i\}, hence tox⪯Pyx\\preceq\_\{P\}y\. ∎

Supplementary Theorem S10 gives the same proof in expanded form, explicitly checking tie\-breaking and both inclusions of the intersection; Supplementary Corollary S11 gives the task\-family version of the capability boundary\.

###### Corollary 12\(Exact capability boundary for coordinate decoders\)\.

Let𝒯\\mathcal\{T\}be a task family as in Definition[10](https://arxiv.org/html/2608.14004#Thmtheorem10)\. An exactss\-coordinate decoder exists on𝒯\\mathcal\{T\}if and only ifdim⁡\(P𝒟\)≤s\\operatorname\{dim\}\(P\_\{\\mathcal\{D\}\}\)\\leq sfor every\(𝒟,P𝒟\)∈𝒯\(\\mathcal\{D\},P\_\{\\mathcal\{D\}\}\)\\in\\mathcal\{T\}\. Consequently:

1. 1\.if every target in𝒯\\mathcal\{T\}has0​p​t​\(P𝒟\)≤s0pt\(P\_\{\\mathcal\{D\}\}\)\\leq s, then an exactss\-coordinate decoder exists; and
2. 2\.if some target hasdim⁡\(P𝒟\)\>s\\operatorname\{dim\}\(P\_\{\\mathcal\{D\}\}\)\>s, no exactss\-coordinate decoder exists on𝒯\\mathcal\{T\}\.

###### Proof\.

If an exact decoder exists, its coordinates for each prompt form anss\-coordinate representation of the associated target; Theorem[11](https://arxiv.org/html/2608.14004#Thmtheorem11)givesdim⁡\(P𝒟\)≤s\\operatorname\{dim\}\(P\_\{\\mathcal\{D\}\}\)\\leq s\. Conversely, if every target has dimension at mostss, choose oness\-coordinate realization for each target \(padding by repeated coordinates when necessary\), defineΦ⁡\(𝒟\)\\Phi\(\\mathcal\{D\}\)to return that realization on prompts appearing in𝒯\\mathcal\{T\}, and extendΦ\\Phiarbitrarily elsewhere\. This gives one exact decoder on the whole family\. For the sufficient width condition, the classical inequalitydim⁡\(P\)≤0​p​t​\(P\)\\operatorname\{dim\}\(P\)\\leq 0pt\(P\)givesdim⁡\(P𝒟\)≤s\\operatorname\{dim\}\(P\_\{\\mathcal\{D\}\}\)\\leq swhenever0​p​t​\(P𝒟\)≤s0pt\(P\_\{\\mathcal\{D\}\}\)\\leq s[6](https://arxiv.org/html/2608.14004#bib.bib19);[20](https://arxiv.org/html/2608.14004#bib.bib18)\. The impossibility statement is the first implication applied to a target of dimension greater thanss\. ∎

This boundary is exact for the decoder class in Definition[10](https://arxiv.org/html/2608.14004#Thmtheorem10)\. Its sufficiency direction is representational and may be nonconstructive; it does not assert efficient recovery of the selected coordinates from demonstrations\. It also does not show that transformer hidden width, attention\-update rank, or the number of arbitrary task vectors bounds order dimension: unrestricted vectors can encode finite combinatorial objects, and unrestricted decoders need not be coordinatewise monotone\. Proposition[8](https://arxiv.org/html/2608.14004#Thmtheorem8)gives concrete instances: one coordinate for chains,mmforBmB\_\{m\}, and one coordinate per distinct prime for the divisor lattice of a fixedNN\.

## 8Positive and Negative Certificates

LetH⁡\(P\)H\(P\)be the complete Hasse DAG of a finite poset\. Fora⪯ba\\preceq b, define

λP\+\(a,b\)=min\{k:\\displaystyle\\lambda\_\{P\}^\{\+\}\(a,b\)=\\min\\\{k:\{\}a=x0≺x1≺⋯≺xk=bis a cover path\}\.\\displaystyle a=x\_\{0\}\\prec x\_\{1\}\\prec\\cdots\\prec x\_\{k\}=b\\text\{ is a cover path\}\\\}\.
###### Proposition 13\(Positive chain\-certificate bound\)\.

Any positive certificate consisting only of demonstrated cover edges has at leastλP\+​\(a,b\)\\lambda\_\{P\}^\{\+\}\(a,b\)edges\. Consequently, a procedure restricted to composing at mostTTcover edges cannot certify every positive query withλP\+​\(a,b\)\>T\\lambda\_\{P\}^\{\+\}\(a,b\)\>T\.

###### Proof\.

Such a certificate is exactly a directed Hasse path, andλP\+​\(a,b\)\\lambda\_\{P\}^\{\+\}\(a,b\)is the minimum length of any such path\. ∎

Supplementary Proposition S13 states the certificate model formally and separates proof length from unrestricted reachability computation\.

A false query admits a dual witness\. CallS⊆US\\subseteq U*forward closed*inHHif no edge leavesSS\. The following elementary graph fact is recorded for self\-containment because it identifies the canonical witness used byνP−\\nu\_\{P\}^\{\-\}\.

###### Lemma 14\(Forward\-closed nonreachability witness\)\.

For verticesa,ba,bof a finite Hasse DAG, there is no directed path fromaatobbif and only if there exists a forward\-closed setSSwitha∈Sa\\in Sandb∉Sb\\notin S\.

###### Proof\.

If such anSSexists, a path beginning ata∈Sa\\in Scannot leaveSS, so it cannot reachb∉Sb\\notin S\. Conversely, ifbbis not reachable fromaa, takeS=ReachH⁡\(a\)S=\\operatorname\{Reach\}\_\{H\}\(a\)\. It containsaaand excludesbb\. If an edge leftSS, its endpoint would also be reachable fromaa, a contradiction\. ThusSSis forward closed\. ∎

###### Corollary 15\(Minimality of the canonical negative witness\)\.

Ifbbis not reachable fromaa, thenReachH⁡\(a\)\\operatorname\{Reach\}\_\{H\}\(a\)is the unique inclusion\-minimal forward\-closed set containingaaand excludingbb\. It therefore also has minimum cardinality among such sets, andνP−​\(a,b\)=\|ReachH⁡\(a\)\|\\nu\_\{P\}^\{\-\}\(a,b\)=\|\\operatorname\{Reach\}\_\{H\}\(a\)\|\. In particular, for fixedHHandaa, this quantity is independent of which nonreachable vertexbbis queried\.

###### Proof\.

Every forward\-closed set containingaamust contain every vertex reachable fromaa, whileReachH⁡\(a\)\\operatorname\{Reach\}\_\{H\}\(a\)itself is forward closed by Lemma[14](https://arxiv.org/html/2608.14004#Thmtheorem14)\. ∎

Supplementary Lemma S14 and Supplementary Corollary S15 provide the full equivalence and minimality proof, including induction on path length\.

Positive certificates can be local paths, while the canonical negative witness may expose a large reachable region\. This distinction refines the informal claim that false comparability is merely “absence of a path\.” It still does not yield an unrestricted transformer\-depth lower bound: a model may use a global algorithm or an encoded topological summary\. Graph\-transformer depth–width tradeoffs provide a related architectural perspective[23](https://arxiv.org/html/2608.14004#bib.bib16)\.

## 9Implications, Scope, and Limitations

### How the proposed framework fits together\.

Our framework analyzes poset ICL as a sequence of logically distinct questions\. First, Proposition[2](https://arxiv.org/html/2608.14004#Thmtheorem2)asks whether the prompt determines the answer at all: a binary answer is universally sound exactly when every poset in the version space agrees on the query\. For the open\-world background containing all posets on the fixed universe, Theorem[3](https://arxiv.org/html/2608.14004#Thmtheorem3)turns this general criterion into an explicit classifier with three outcomes—forced true, forced false, or genuinely unknown—while Corollary[4](https://arxiv.org/html/2608.14004#Thmtheorem4)gives the corresponding positive\-only case\. If the prompt instead declares a complete Hasse diagram, Observation[5](https://arxiv.org/html/2608.14004#Thmtheorem5)reduces comparison to graph reachability\. Theorem[6](https://arxiv.org/html/2608.14004#Thmtheorem6)then changes the question from answering one query to identifying the entire target poset: the optimal open\-world prompt consists of all indispensable cover relations together with a minimum set of negative blockers\. Corollary[7](https://arxiv.org/html/2608.14004#Thmtheorem7)gives the resulting bounds and exact extremal values, and the identity

τow​\(P\)−τcw​\(P\)=β⁡\(P\)\\tau\_\{\\mathrm\{ow\}\}\(P\)\-\\tau\_\{\\mathrm\{cw\}\}\(P\)=\\beta\(P\)shows that the blocker term is precisely the additional label cost of open\-world semantics\. Once the target relation is identified, Table[1](https://arxiv.org/html/2608.14004#S6.T1)separates its structural and proof\-related difficulty into height, width, order dimension, cover count, and positive and negative certificate sizes\. Finally, Definition[10](https://arxiv.org/html/2608.14004#Thmtheorem10), Theorem[11](https://arxiv.org/html/2608.14004#Thmtheorem11), and Corollary[12](https://arxiv.org/html/2608.14004#Thmtheorem12)characterize exactly which targets can be represented by the proposed monotone coordinate\-decoder class, while Proposition[13](https://arxiv.org/html/2608.14004#Thmtheorem13), Lemma[14](https://arxiv.org/html/2608.14004#Thmtheorem14), and Corollary[15](https://arxiv.org/html/2608.14004#Thmtheorem15)describe explicit witnesses for positive comparability and negative nonreachability\.

### Examples illustrating the separation of difficulty sources\.

Consider first the chainCnC\_\{n\}\. It has order dimension one by Proposition[8](https://arxiv.org/html/2608.14004#Thmtheorem8), and itsn−1n\-1cover edges are sufficient to teach it under both open\- and closed\-world semantics\. Nevertheless, comparing its bottom and top elements requires a positive Hasse certificate of lengthn−1n\-1; thus representation is simple even though a particular proof can be long\. The antichainAnA\_\{n\}demonstrates the opposite teaching behavior\. Its complete Hasse diagram contains no cover edges, so it is specified without positive edges under closed\-world semantics, but Corollary[7](https://arxiv.org/html/2608.14004#Thmtheorem7)shows that open\-world teaching requires alln⁡\(n−1\)n\(n\-1\)ordered negative comparisons\. The Boolean latticeBmB\_\{m\}provides a third contrast: a cover query has a one\-edge positive certificate, yet Proposition[8](https://arxiv.org/html/2608.14004#Thmtheorem8)givesdim⁡\(Bm\)=m\\operatorname\{dim\}\(B\_\{m\}\)=m, so Corollary[12](https://arxiv.org/html/2608.14004#Thmtheorem12)rules out exact representation by fewer thanmmmonotone coordinates\. Similarly, the divisor lattice ofN=∏i=1rpieiN=\\prod\_\{i=1\}^\{r\}p\_\{i\}^\{e\_\{i\}\}has dimensionrr, corresponding to therrindependent prime\-exponent coordinates\. These examples show why prompt ambiguity, teaching cost, certificate length, and representation dimension must not be collapsed into a single notion of “difficulty\.”

### Consequences for benchmark design\.

A poset benchmark should state the universe and background theory, whether demonstrations denote covers or arbitrary comparisons, whether the displayed diagram is complete, and whether*unknown*is an admissible output\. Theorem[3](https://arxiv.org/html/2608.14004#Thmtheorem3)can be used as a model\-independent logical baseline for mixed positive/negative open\-world prompts\. Figure[1](https://arxiv.org/html/2608.14004#S4.F1)illustrates why this distinction matters: under the explicitly defined exhaustive averaging scheme over all 219 labeled four\-element posets, a substantial fraction of unobserved queries remain ambiguous even at high label coverage\. Such queries should not automatically be scored as ordinary binary errors\. In addition, prompts using familiar relation names or numerical elements may permit pretrained semantic recall\. Abstract relation symbols, randomized element names, or relabeling controls are therefore needed when the objective is to isolate inference from demonstrations rather than prior factual knowledge\.

### Scope of the theoretical conclusions\.

The results separate four possible sources of failure\. Non\-identifiability is an information limitation established by Proposition[2](https://arxiv.org/html/2608.14004#Thmtheorem2)and Theorem[3](https://arxiv.org/html/2608.14004#Thmtheorem3); a large value ofτow​\(P\)\\tau\_\{\\mathrm\{ow\}\}\(P\)is a prompt\-budget limitation characterized by Theorem[6](https://arxiv.org/html/2608.14004#Thmtheorem6); large values ofλP\+\\lambda\_\{P\}^\{\+\}orνP−\\nu\_\{P\}^\{\-\}are certificate limitations for procedures restricted to the witnesses formalized in Proposition[13](https://arxiv.org/html/2608.14004#Thmtheorem13)and Lemma[14](https://arxiv.org/html/2608.14004#Thmtheorem14); and high order dimension is a representation limitation only for the exact monotone coordinate decoders of Definition[10](https://arxiv.org/html/2608.14004#Thmtheorem10)\. We therefore do not infer limitations for unrestricted transformers, softmax attention, general task vectors, approximate decoders, or arbitrary graph algorithms\. Transformer universality results remain compatible with our theory: they concern what a sufficiently expressive architecture and prompt can compute, whereas our identifiability results concern what a particular finite prompt logically entails\.

### Novelty relative to prior and concurrent work\.

The earlier empirical study of poset ICL[8](https://arxiv.org/html/2608.14004#bib.bib23)motivates the problem through observed model behavior, but it does not provide the version\-space trichotomy, the blocker\-based teaching characterization, or the exact coordinate\-decoder boundary developed here\. Information\-theoretic analyses of ICL study uncertainty under data\-generating distributions[14](https://arxiv.org/html/2608.14004#bib.bib7); in contrast, Proposition[2](https://arxiv.org/html/2608.14004#Thmtheorem2)and Theorem[3](https://arxiv.org/html/2608.14004#Thmtheorem3)use logical agreement over all relational completions consistent with the prompt\. Concurrent relational\-database work studies whether support labels identify latent predictive mechanisms[4](https://arxiv.org/html/2608.14004#bib.bib11), whereas our results characterize completions of partial orders, their open\-world teaching cost, and their Dushnik–Miller dimension\. The contribution is therefore not a claim to the first theory of relational learning in general, but a unified framework connecting logical identifiability, optimal prompt teaching, order\-theoretic structure, exact coordinate representation, and proof certificates for in\-context learning on finite posets\.

## 10Conclusion

We presented a theory of ICL on partial orders that begins with a basic requirement: the prompt must identify the queried comparison\. Finite open\-world prompts admit an exact true/false/unknown characterization through reflexive transitive closure, antisymmetry, and negative constraints; complete Hasse prompts reduce to reachability\. Open\-world teaching cost decomposes into mandatory covers and a blocker\-set surcharge, with a tight class maximum at the antichain\. For identified structures, the profile table exposes independent dimensions of structural and certificate complexity\. Finally, the classical order\-dimension equivalence yields an exact capability boundary for the formally defined coordinate\-decoder class\. The framework supports benchmark design while keeping logical ambiguity, prompt budget, structural complexity, and decoder capacity distinct\.

## References

- Akyüreket al\.\(2023\)E\. Akyürek, D\. Schuurmans, J\. Andreas, T\. Ma, and D\. ZhouWhat learning algorithm is in\-context learning? investigations with linear models\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2608.14004#S1.p1.1),[§2](https://arxiv.org/html/2608.14004#S2.SS0.SSS0.Px1.p1.1)\.
- Bhattamishraet al\.\(2024\)S\. Bhattamishra, A\. Patel, P\. Blunsom, and V\. KanadeUnderstanding in\-context learning in transformers and LLMs by learning to learn discrete functions\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2608.14004#S1.p1.1)\.
- Brownet al\.\(2020\)T\. B\. Brown, B\. Mann, N\. Ryder, M\. Subbiah, J\. Kaplan, P\. Dhariwal, A\. Neelakantan, P\. Shyam, G\. Sastry, A\. Askell, S\. Agarwal, A\. Herbert\-Voss, G\. Krueger, T\. Henighan, R\. Child, A\. Ramesh, D\. M\. Ziegler, J\. Wu, C\. Winter, C\. Hesse, M\. Chen, E\. Sigler, M\. Litwin, S\. Gray, B\. Chess, J\. Clark, C\. Berner, S\. McCandlish, A\. Radford, I\. Sutskever, and D\. AmodeiLanguage models are few\-shot learners\.InAdvances in Neural Information Processing Systems,Vol\.33,pp\. 1877–1901\.Cited by:[§1](https://arxiv.org/html/2608.14004#S1.p1.1)\.
- Chenet al\.\(2026\)Z\. Chen, J\. Yin, J\. Gu, S\. Xiong, X\. Liu, R\. Zhang, K\. Zhou, and K\. GuoOpenRFM: dissecting relational in\-context learning\.arXiv preprint arXiv:2606\.04320\.Cited by:[§2](https://arxiv.org/html/2608.14004#S2.SS0.SSS0.Px2.p1.1),[§9](https://arxiv.org/html/2608.14004#S9.SS0.SSS0.Px5.p1.1)\.
- Daiet al\.\(2023\)D\. Dai, Y\. Sun, L\. Dong, Y\. Hao, S\. Ma, Z\. Sui, and F\. WeiWhy can GPT learn in\-context? language models secretly perform gradient descent as meta\-optimizers\.InFindings of the Association for Computational Linguistics: ACL 2023,pp\. 4005–4019\.Cited by:[§1](https://arxiv.org/html/2608.14004#S1.p1.1),[§2](https://arxiv.org/html/2608.14004#S2.SS0.SSS0.Px1.p1.1)\.
- Dilworth \(1950\)R\. P\. DilworthA decomposition theorem for partially ordered sets\.Annals of Mathematics51\(1\),pp\. 161–166\.External Links:[Document](https://dx.doi.org/10.2307/1969503)Cited by:[§6](https://arxiv.org/html/2608.14004#S6a.p6.1.1),[§7](https://arxiv.org/html/2608.14004#S7.p4.1.1)\.
- Dushnik and Miller \(1941\)B\. Dushnik and E\. W\. MillerPartially ordered sets\.American Journal of Mathematics63\(3\),pp\. 600–610\.Cited by:[§1](https://arxiv.org/html/2608.14004#S1.p2.1),[§2](https://arxiv.org/html/2608.14004#S2.SS0.SSS0.Px3.p1.1),[§6](https://arxiv.org/html/2608.14004#S6a.p1.1),[§8](https://arxiv.org/html/2608.14004#S8a.p2.1)\.
- Duttaet al\.\(2025\)D\. Dutta, F\. Ansari, and S\. DasAssessing the limits of in\-context learning beyond functions using partially ordered relation\.InProceedings of the 14th International Joint Conference on Natural Language Processing and the 4th Conference of the Asia\-Pacific Chapter of the Association for Computational Linguistics,pp\. 900–918\.External Links:[Link](https://aclanthology.org/2025.ijcnlp-long.50/),[Document](https://dx.doi.org/10.18653/v1/2025.ijcnlp-long.50),ISBN 979\-8\-89176\-298\-5Cited by:[§1](https://arxiv.org/html/2608.14004#S1.p3.1),[§9](https://arxiv.org/html/2608.14004#S9.SS0.SSS0.Px5.p1.1)\.
- Furuyaet al\.\(2025\)T\. Furuya, M\. V\. de Hoop, and G\. PeyréTransformers are universal in\-context learners\.InInternational Conference on Learning Representations,Cited by:[§2](https://arxiv.org/html/2608.14004#S2.SS0.SSS0.Px2.p1.1)\.
- Garget al\.\(2022\)S\. Garg, D\. Tsipras, P\. S\. Liang, and G\. ValiantWhat can transformers learn in\-context? a case study of simple function classes\.InAdvances in Neural Information Processing Systems,Vol\.35,pp\. 30583–30598\.Cited by:[§1](https://arxiv.org/html/2608.14004#S1.p1.1),[§2](https://arxiv.org/html/2608.14004#S2.SS0.SSS0.Px1.p1.1)\.
- Goldman and Kearns \(1995\)S\. A\. Goldman and M\. J\. KearnsOn the complexity of teaching\.Journal of Computer and System Sciences50\(1\),pp\. 20–31\.Cited by:[§5](https://arxiv.org/html/2608.14004#S5.p1.2),[§8](https://arxiv.org/html/2608.14004#S8a.p2.1)\.
- Guoet al\.\(2024\)T\. Guo, W\. Hu, S\. Mei, H\. Wang, C\. Xiong, S\. Savarese, and Y\. BaiHow do transformers learn in\-context beyond simple functions? a case study on learning with representations\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2608.14004#S1.p1.1)\.
- Hendelet al\.\(2023\)R\. Hendel, M\. Geva, and A\. GlobersonIn\-context learning creates task vectors\.InFindings of the Association for Computational Linguistics: EMNLP 2023,pp\. 9318–9333\.Cited by:[§2](https://arxiv.org/html/2608.14004#S2.SS0.SSS0.Px1.p1.1)\.
- Jeonet al\.\(2024\)H\. J\. Jeon, J\. D\. Lee, Q\. Lei, and B\. Van RoyAn information\-theoretic analysis of in\-context learning\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 21522–21554\.Cited by:[§1](https://arxiv.org/html/2608.14004#S1.p1.1),[§2](https://arxiv.org/html/2608.14004#S2.SS0.SSS0.Px1.p1.1),[§9](https://arxiv.org/html/2608.14004#S9.SS0.SSS0.Px5.p1.1)\.
- Lewis and Souza \(2021\)D\. Lewis and V\. SouzaThe order dimension of divisibility\.Journal of Combinatorial Theory, Series A179,pp\. 105391\.Cited by:[§2](https://arxiv.org/html/2608.14004#S2.SS0.SSS0.Px3.p1.1),[§6](https://arxiv.org/html/2608.14004#S6.p7.1.1),[§6](https://arxiv.org/html/2608.14004#S6a.p11.1.1)\.
- Mitchell \(1977\)T\. M\. MitchellVersion spaces: a candidate elimination approach to rule learning\.InProceedings of the Fifth International Joint Conference on Artificial Intelligence,pp\. 305–310\.Cited by:[§1](https://arxiv.org/html/2608.14004#S1.p3.1),[§8](https://arxiv.org/html/2608.14004#S8a.p2.1)\.
- Qiuet al\.\(2025\)R\. Qiu, Z\. Xu, W\. Bao, and H\. TongAsk, and it shall be given: on the turing completeness of prompting\.InInternational Conference on Learning Representations,Cited by:[§2](https://arxiv.org/html/2608.14004#S2.SS0.SSS0.Px2.p1.1)\.
- Reiter \(1989\)R\. ReiterOn closed world data bases\.InReadings in Artificial Intelligence and Databases,pp\. 248–258\.Cited by:[§1](https://arxiv.org/html/2608.14004#S1.p3.1)\.
- Tanget al\.\(2026\)W\. Tang, X\. Jiang, F\. Karray, and L\. HuIn\-context learning operates as concept subspace learning\.arXiv preprint arXiv:2605\.18830\.Cited by:[§2](https://arxiv.org/html/2608.14004#S2.SS0.SSS0.Px1.p1.1)\.
- Trotter \(1992\)W\. T\. TrotterCombinatorics and partially ordered sets: dimension theory\.Johns Hopkins University Press,Baltimore, Maryland\.Cited by:[§1](https://arxiv.org/html/2608.14004#S1.p2.1),[§2](https://arxiv.org/html/2608.14004#S2.SS0.SSS0.Px3.p1.1),[§4](https://arxiv.org/html/2608.14004#S4.SS0.SSS0.Px2.p2.1),[§6](https://arxiv.org/html/2608.14004#S6a.p1.1),[§6](https://arxiv.org/html/2608.14004#S6a.p6.1.1),[§7](https://arxiv.org/html/2608.14004#S7.p1.1),[§7](https://arxiv.org/html/2608.14004#S7.p4.1.1),[§8](https://arxiv.org/html/2608.14004#S8a.p2.1)\.
- Wanget al\.\(2023\)H\. Wang, S\. Feng, T\. He, Z\. Tan, X\. Han, and Y\. TsvetkovCan language models solve graph problems in natural language?\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 30840–30861\.Cited by:[§2](https://arxiv.org/html/2608.14004#S2.SS0.SSS0.Px2.p1.1)\.
- Wuet al\.\(2025\)F\. Wu, V\. P\. Dwivedi, and J\. LeskovecLarge language models are good relational learners\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),Vienna, Austria,pp\. 7835–7854\.External Links:[Document](https://dx.doi.org/10.18653/v1/2025.acl-long.386)Cited by:[§2](https://arxiv.org/html/2608.14004#S2.SS0.SSS0.Px2.p1.1)\.
- Yehudaiet al\.\(2025\)G\. Yehudai, C\. Sanford, M\. Bechler\-Speicher, O\. Fischer, R\. Gilad\-Bachrach, and A\. GlobersonDepth\-width tradeoffs for transformers on graph tasks\.InAdvances in Neural Information Processing Systems,Vol\.38,pp\. 22949–22981\.Cited by:[§8](https://arxiv.org/html/2608.14004#S8.p8.1)\.
- Yin and Steinhardt \(2025\)K\. Yin and J\. SteinhardtWhich attention heads matter for in\-context learning?\.InProceedings of the 42nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.267,pp\. 72428–72461\.Cited by:[§2](https://arxiv.org/html/2608.14004#S2.SS0.SSS0.Px1.p1.1)\.

Supplementary Material for “Identifiability and Order\-Dimension Limits of In\-Context Learning on Partial Orders”

## 1Cross\-Document Reference Map

The theorem titles below are copied exactly from the main paper\. Each item gives the expanded proof in this document\.

- •Sound\-answer criterion:Proposition S1\.
- •Open\-world completion trichotomy and positive\-only trichotomy:Lemmas S2–S3 and Theorem S4\.
- •Deterministic ambiguity illustration in Figure 1 of the main paper:the section “Exact Finite\-Universe Ambiguity Enumeration\.”
- •Closed\-world reachability:Observation S5\.
- •Dependence on background theory:Proposition S6\.
- •Exact teaching characterization:Lemma S7 and Theorem S8\.
- •Teaching bounds, class maximum, and open/closed\-world cost:Corollary S9\.
- •Classical coordinate\-order equivalence:Theorem S10\.
- •Exact coordinate\-decoder capability boundary:Corollary S11\.
- •Standard families, profile\-table details, and finite divisibility:Proposition S12 and the following profile derivations\.
- •Positive chain\-certificate bound:Proposition S13\.
- •Forward\-closed witness and canonical negative witness:Lemma S14 and Corollary S15\.

## 2Semantic Setup and Sound Answers

LetUUbe a finite known universe\. A prompt is𝒟=\(𝒟\+,𝒟−\)\\mathcal\{D\}=\(\\mathcal\{D\}^\{\+\},\\mathcal\{D\}^\{\-\}\), where𝒟\+⊆U2\\mathcal\{D\}^\{\+\}\\subseteq U^\{2\}contains positive comparisons and𝒟−⊆U2\\mathcal\{D\}^\{\-\}\\subseteq U^\{2\}contains negative comparisons\. A background theoryℬ\\mathcal\{B\}is a class of posets onUU\. Its version space is

𝒱ℬ\(𝒟\)=\{P∈ℬ:𝒟\+⊆⪯P,𝒟−∩⪯P=∅\}\.\\mathcal\{V\}\_\{\\mathcal\{B\}\}\(\\mathcal\{D\}\)=\\\{P\\in\\mathcal\{B\}:\\mathcal\{D\}^\{\+\}\\subseteq\\preceq\_\{P\},\\ \\mathcal\{D\}^\{\-\}\\cap\\preceq\_\{P\}=\\varnothing\\\}\.We call𝒟\\mathcal\{D\}*satisfiable underℬ\\mathcal\{B\}*when𝒱ℬ​\(𝒟\)≠∅\\mathcal\{V\}\_\{\\mathcal\{B\}\}\(\\mathcal\{D\}\)\\neq\\varnothing, and all statements below assume satisfiability\. A binary answer rule is universally sound forq=\(a,b\)q=\(a,b\)if its output equals𝟏\[a⪯Pb\]\\mathbf\{1\}\[a\\preceq\_\{P\}b\]for everyP∈𝒱ℬ​\(𝒟\)P\\in\\mathcal\{V\}\_\{\\mathcal\{B\}\}\(\\mathcal\{D\}\)\.

###### Proposition S1\(Sound\-answer criterion\)\.

A universally sound binary answer exists for\(ℬ,𝒟,q\)\(\\mathcal\{B\},\\mathcal\{D\},q\)if and only if all posets in𝒱ℬ​\(𝒟\)\\mathcal\{V\}\_\{\\mathcal\{B\}\}\(\\mathcal\{D\}\)assign the same truth value toqq\.

###### Proof\.

If all consistent posets assign the common valuev∈\{0,1\}v\\in\\\{0,1\\\}, the rule that returnsvvis correct for every member of the version space\. Conversely, if the query is not identified, there areP0,P1∈𝒱ℬ​\(𝒟\)P\_\{0\},P\_\{1\}\\in\\mathcal\{V\}\_\{\\mathcal\{B\}\}\(\\mathcal\{D\}\)with values zero and one, respectively\. Every deterministic binary answer is therefore wrong on one of them\. A randomized rule cannot guarantee correctness on both either: each realized output in its support is zero or one and is wrong on one ofP0,P1P\_\{0\},P\_\{1\}\. Thus universal, sure correctness is possible exactly under agreement of the version space\. This statement concerns logical identifiability, not average\-case accuracy under a distribution over targets\. ∎

## 3Expanded Open\-World Completion Proof

For the least\-restrictive open\-world background, letℬ\\mathcal\{B\}contain all posets onUUand putR=TC⁡\(𝒟\+\)R=\\operatorname\{TC\}\(\\mathcal\{D\}^\{\+\}\), whereTC\\operatorname\{TC\}is reflexive transitive closure\. Define

PredR⁡\(x\)=\{u:u​R​x\},SuccR⁡\(x\)=\{v:x​R​v\}\.\\operatorname\{Pred\}\_\{R\}\(x\)=\\\{u:uRx\\\},\\qquad\\operatorname\{Succ\}\_\{R\}\(x\)=\\\{v:xRv\\\}\.
###### Lemma S2\(Consistency of the least positive closure\)\.

If𝒟\\mathcal\{D\}is satisfiable, thenRRis a partial order,R∩𝒟−=∅R\\cap\\mathcal\{D\}^\{\-\}=\\varnothing, andRRis contained in every poset consistent with𝒟\\mathcal\{D\}\.

###### Proof\.

Reflexivity and transitivity hold by construction\. LetPPbe any consistent poset\. EveryRR\-comparison is witnessed by a path of positive demonstrations, so transitivity ofPPgivesR⊆⪯PR\\subseteq\\preceq\_\{P\}\. If distinctx,yx,ysatisfied bothx​R​yxRyandy​R​xyRx, thenPPwould contain both comparisons, contradicting antisymmetry\. ThusRRis antisymmetric\. If\(x,y\)∈R∩𝒟−\(x,y\)\\in R\\cap\\mathcal\{D\}^\{\-\}, every consistentPPwould both contain and exclude\(x,y\)\(x,y\), contradicting satisfiability\. The same path argument proves containment in every consistent poset\. ∎

###### Lemma S3\(One\-edge closure formula\)\.

LetRRbe reflexive and transitive, and supposea​𝑅​ba\{\\not\\mathrel\{R\}\}b\. Then

TC⁡\(R∪\{\(a,b\)\}\)=R∪\(PredR⁡\(a\)×SuccR⁡\(b\)\)\.\\operatorname\{TC\}\(R\\cup\\\{\(a,b\)\\\}\)=R\\cup\\bigl\(\\operatorname\{Pred\}\_\{R\}\(a\)\\times\\operatorname\{Succ\}\_\{R\}\(b\)\\bigr\)\.IfRRis antisymmetric, the displayed closure is antisymmetric if and only ifb​𝑅​ab\{\\not\\mathrel\{R\}\}a\.

###### Proof\.

Call the relation on the rightR′R^\{\\prime\}\. It containsRRand\(a,b\)\(a,b\)becausea​R​aaRaandb​R​bbRb\. Ifx​R​axRaandb​R​ybRy, then the pathx​R​axRa,a→ba\\to b,b​R​ybRyshows that\(x,y\)\(x,y\)belongs to the left\-hand closure\. HenceR′⊆TC⁡\(R∪\{\(a,b\)\}\)R^\{\\prime\}\\subseteq\\operatorname\{TC\}\(R\\cup\\\{\(a,b\)\\\}\)\.

For the reverse inclusion, it is enough to prove thatR′R^\{\\prime\}is reflexive and transitive\. Reflexivity comes fromRR\. Consider\(x,y\),\(y,z\)∈R′\(x,y\),\(y,z\)\\in R^\{\\prime\}\. If both lie inRR, thenx​R​zxRz\. If the first lies inRRand the second in the rectangle, thenx​R​yxRyandy​R​ayRaimplyx​R​axRa, whileb​R​zbRzholds, so\(x,z\)\(x,z\)lies in the rectangle\. If the first lies in the rectangle and the second inRR, thenx​R​axRaandb​R​y​R​zbRyRz, again giving a rectangle pair\. If both lie in the rectangle, the first givesx​R​axRaand the second givesb​R​zbRz, which is sufficient\. ThusR′R^\{\\prime\}is transitive, and minimality of transitive closure gives the reverse inclusion\.

Ifb​R​abRa, then addinga​R​baRbcreates a two\-way comparison between distinct elements, so antisymmetry fails\. Conversely, supposeb​𝑅​ab\{\\not\\mathrel\{R\}\}aand consider the directed graph whose nonreflexive edges are those ofRRtogether with the single new edgea→ba\\to b\. Any directed cycle on distinct vertices that was not already present inRRmust usea→ba\\to b; removing that edge gives anRR\-path frombbtoaa, contradictingb​𝑅​ab\{\\not\\mathrel\{R\}\}a\. The graph is therefore acyclic on distinct vertices, and its transitive closure is antisymmetric\. ∎

###### Theorem S4\(Open\-world completion trichotomy\)\.

LetUUbe finite, letℬ\\mathcal\{B\}be the class of all posets onUU, and let𝒟=\(𝒟\+,𝒟−\)\\mathcal\{D\}=\(\\mathcal\{D\}^\{\+\},\\mathcal\{D\}^\{\-\}\)be satisfiable\. PutR=TC⁡\(𝒟\+\)R=\\operatorname\{TC\}\(\\mathcal\{D\}^\{\+\}\)\. For a query\(a,b\)\(a,b\), exactly one of the following holds:

1. 1\.a​R​baRb, and the query is identified true;
2. 2\.a​𝑅​ba\{\\not\\mathrel\{R\}\}band eitherb​R​abRaor\(PredR⁡\(a\)×SuccR⁡\(b\)\)∩𝒟−≠∅\\bigl\(\\operatorname\{Pred\}\_\{R\}\(a\)\\times\\operatorname\{Succ\}\_\{R\}\(b\)\\bigr\)\\cap\\mathcal\{D\}^\{\-\}\\neq\\varnothing, and the query is identified false;
3. 3\.neither condition holds, and the query is unidentifiable\.

###### Proof\.

By Lemma[S2](https://arxiv.org/html/2608.14004#Thmtheorem2a),P−=\(U,R\)P^\{\-\}=\(U,R\)is a consistent poset\. Ifa​R​baRb, every consistent poset containsRR, so every one makes the query true\.

Assumea​𝑅​ba\{\\not\\mathrel\{R\}\}b\. ThenP−P^\{\-\}is a consistent false completion\. Any true completion must containRR, the comparisona⪯ba\\preceq b, and therefore every pair inPredR⁡\(a\)×SuccR⁡\(b\)\\operatorname\{Pred\}\_\{R\}\(a\)\\times\\operatorname\{Succ\}\_\{R\}\(b\)by transitivity\. Lemma[S3](https://arxiv.org/html/2608.14004#Thmtheorem3a)shows that adding precisely this rectangle is already the least reflexive transitive true extension\.

Ifb​R​abRa, Lemma[S3](https://arxiv.org/html/2608.14004#Thmtheorem3a)shows that every true extension violates antisymmetry\. If the rectangle intersects𝒟−\\mathcal\{D\}^\{\-\}, every true extension violates a negative demonstration\. Either obstruction therefore makes the query forced false\.

Finally suppose that neither obstruction occurs\. Lemma[S3](https://arxiv.org/html/2608.14004#Thmtheorem3a)shows that

P\+=\(U,R∪\(PredR⁡\(a\)×SuccR⁡\(b\)\)\)P^\{\+\}=\\left\(U,R\\cup\\bigl\(\\operatorname\{Pred\}\_\{R\}\(a\)\\times\\operatorname\{Succ\}\_\{R\}\(b\)\\bigr\)\\right\)is reflexive, transitive, and antisymmetric\. Lemma[S2](https://arxiv.org/html/2608.14004#Thmtheorem2a)saysRRavoids𝒟−\\mathcal\{D\}^\{\-\}, and the assumed empty intersection says the added pairs avoid𝒟−\\mathcal\{D\}^\{\-\}as well\. ThusP\+P^\{\+\}is a consistent true completion, whileP−P^\{\-\}is a consistent false completion\. The query is unidentifiable\. The three cases are mutually exclusive and cover all possibilities\. ∎

If𝒟−=∅\\mathcal\{D\}^\{\-\}=\\varnothing, Theorem[S4](https://arxiv.org/html/2608.14004#Thmtheorem4a)reduces to: true ifa​R​baRb, false ifa≠ba\\neq bandb​R​abRa, and unknown otherwise\. Algorithmically, Floyd–Warshall givesO⁡\(\|U\|3\)O\(\|U\|^\{3\}\)closure preprocessing\. Afterward, a query costsO⁡\(\|𝒟−\|\)O\(\|\\mathcal\{D\}^\{\-\}\|\)naively by scanning negative pairs and testing membership in the predecessor–successor rectangle\. With\|U\|\|U\|\-bit reachability and negative\-adjacency bitsets, the rectangle test costsO⁡\(\|U\|2/w\)O\(\|U\|^\{2\}/w\)word operations per query, wherewwis the machine word size\. This is a logical oracle, not a learned predictor\.

## 4Exact Finite\-Universe Ambiguity Enumeration

Figure 1 of the main paper is an exhaustive consequence of the version\-space definition, not a language\-model experiment\. Let𝒫4\\mathcal\{P\}\_\{4\}be the set of all 219 labeled posets onU=\{1,2,3,4\}U=\\\{1,2,3,4\\\}, and let

Q4=\{\(i,j\)∈U2:i≠j\},\|Q4\|=12\.Q\_\{4\}=\\\{\(i,j\)\\in U^\{2\}:i\\neq j\\\},\\qquad\|Q\_\{4\}\|=12\.The four reflexive pairs are omitted because every poset labels them true, so observing them would add no information\. For a targetP∈𝒫4P\\in\\mathcal\{P\}\_\{4\}and an observed\-pair setS⊆Q4S\\subseteq Q\_\{4\}, define the complete target\-consistent prompt onSSby

𝒟S\(P\)\+=S∩⪯P,𝒟S\(P\)−=S∖⪯P\.\\mathcal\{D\}\_\{S\}\(P\)^\{\+\}=S\\cap\\preceq\_\{P\},\\qquad\\mathcal\{D\}\_\{S\}\(P\)^\{\-\}=S\\setminus\\preceq\_\{P\}\.Its version space is

𝒱\(P,S\)=\{P′∈𝒫4:⪯P′∩S=⪯P∩S\}\.\\mathcal\{V\}\(P,S\)=\\\{P^\{\\prime\}\\in\\mathcal\{P\}\_\{4\}:\\preceq\_\{P^\{\\prime\}\}\\cap S=\\preceq\_\{P\}\\cap S\\\}\.For an unobserved queryq∈Q4∖Sq\\in Q\_\{4\}\\setminus S, write

A\(P,S,q\)=\[\{𝟏\[q∈⪯P′\]:P′∈𝒱\(P,S\)\}=\{0,1\}\]\.A\(P,S,q\)=\\mathbf\{1\}\\\!\\left\[\\\{\\mathbf\{1\}\[q\\in\\preceq\_\{P^\{\\prime\}\}\]:P^\{\\prime\}\\in\\mathcal\{V\}\(P,S\)\\\}=\\\{0,1\\\}\\right\]\.ThusA⁡\(P,S,q\)=1A\(P,S,q\)=1exactly when the prompt leavesqqambiguous\. For prompt sizem∈\{0,…,11\}m\\in\\\{0,\\ldots,11\\\}, the plotted quantity is

αm=1219​\(12m\)​\(12−m\)​∑P∈𝒫4∑S⊆Q4\|S\|=m∑q∈Q4∖SA⁡\(P,S,q\)\.\\alpha\_\{m\}=\\frac\{1\}\{219\\binom\{12\}\{m\}\(12\-m\)\}\\sum\_\{P\\in\\mathcal\{P\}\_\{4\}\}\\sum\_\{\\begin\{subarray\}\{c\}S\\subseteq Q\_\{4\}\\\\ \|S\|=m\\end\{subarray\}\}\\sum\_\{q\\in Q\_\{4\}\\setminus S\}A\(P,S,q\)\.Every target, prompt subset, and unobserved query therefore receives equal weight\. There is no random\-poset generator, fitted parameter, or Monte Carlo error\.

Table 2:Exact values plotted in Figure 1 of the main paper\.
The computation groups posets by their restrictions to the observed setSS\. Within one such version\-space cell, an unobserved query is ambiguous precisely when its truth bit is not constant across the cell\. Enumerating all2122^\{12\}observed\-pair masks and all 219 posets therefore yields the exact counts without repeatedly solving a completion problem\. The supplied script writes both the CSV values and the publication figure\. These values illustrate the prevalence of the unknown outcome for one fully specified finite averaging scheme; they are not asserted to approximate a natural distribution over larger posets\.

### Implementation details\.

The bundled script uses Python 3\.13\.5 and integer bit masks for the exact enumeration; Matplotlib 3\.10\.8 is used only to render the figure\. The supplied run used a CPU\-only AMD EPYC 9V74 environment with nine logical cores and 5\.9 GiB of visible memory\. It completed in approximately 1\.6 seconds with a peak resident set size of 164 MiB\. The exact integer counts are independent of hardware, and no random seed is required\.

The following is the standard reachability interpretation of a complete Hasse diagram; it is recorded for self\-containment\.

###### Observation S5\(Closed\-world reachability\)\.

If a finite DAGH=\(U,E\)H=\(U,E\)is declared to be the complete Hasse diagram of a poset, thena⪯ba\\preceq bif and only ifb∈ReachH⁡\(a\)b\\in\\operatorname\{Reach\}\_\{H\}\(a\), including the length\-zero path fora=ba=b\.

###### Proof\.

A directed Hasse path is a chain of cover relations, so transitivity implies comparability\. Conversely, supposea≺ba\\prec b\. If\(a,b\)\(a,b\)is a cover, it is an edge\. Otherwise chooseccwitha≺c≺ba\\prec c\\prec band refine the two intervals\. Each refinement strictly decreases the size of the corresponding finite interval, so the process terminates in a saturated chaina=x0≺x1≺⋯≺xk=ba=x\_\{0\}\\prec x\_\{1\}\\prec\\cdots\\prec x\_\{k\}=bwhose adjacent pairs are covers\. This is a directed path inHH\. Reflexivity handlesa=ba=b\. ∎

###### Proposition S6\(Monotonicity under stronger background knowledge\)\.

Letℬ1⊆ℬ2\\mathcal\{B\}\_\{1\}\\subseteq\\mathcal\{B\}\_\{2\}\. Then𝒱ℬ1​\(𝒟\)⊆𝒱ℬ2​\(𝒟\)\\mathcal\{V\}\_\{\\mathcal\{B\}\_\{1\}\}\(\\mathcal\{D\}\)\\subseteq\\mathcal\{V\}\_\{\\mathcal\{B\}\_\{2\}\}\(\\mathcal\{D\}\)\. Consequently, a query identified underℬ2\\mathcal\{B\}\_\{2\}is identified with the same value underℬ1\\mathcal\{B\}\_\{1\}\. For a fixed targetP∈ℬ1P\\in\\mathcal\{B\}\_\{1\}, the minimum teaching\-set size relative toℬ1\\mathcal\{B\}\_\{1\}is no greater than the minimum relative toℬ2\\mathcal\{B\}\_\{2\}\.

###### Proof\.

The version\-space inclusion follows directly because every hypothesis admitted byℬ1\\mathcal\{B\}\_\{1\}is admitted byℬ2\\mathcal\{B\}\_\{2\}\. Agreement on the larger version space implies agreement on its subset\. Any label set isolatingPPamongℬ2\\mathcal\{B\}\_\{2\}also isolates it among the smaller classℬ1\\mathcal\{B\}\_\{1\}, so restricting the background cannot increase the minimum teaching size\. ∎

## 5Expanded Teaching\-Number Proof

LetℬU\\mathcal\{B\}\_\{U\}be the class of all posets on a known finite universeUU\. A prompt teachesPPunder open\-world semantics if𝒱ℬU​\(𝒟\)=\{P\}\\mathcal\{V\}\_\{\\mathcal\{B\}\_\{U\}\}\(\\mathcal\{D\}\)=\\\{P\\\}\. Define

τow​\(P\)=min⁡\{\|𝒟\+\|\+\|𝒟−\|:𝒱ℬU​\(𝒟\)=\{P\}\}\.\\tau\_\{\\mathrm\{ow\}\}\(P\)=\\min\\\{\|\\mathcal\{D\}^\{\+\}\|\+\|\\mathcal\{D\}^\{\-\}\|:\\mathcal\{V\}\_\{\\mathcal\{B\}\_\{U\}\}\(\\mathcal\{D\}\)=\\\{P\\\}\\\}\.The fixed universe is essential: if fresh elements are permitted, a finite prompt cannot isolate an antichain because another isolated element can be added\. LetCov⁡\(P\)\\operatorname\{Cov\}\(P\)denote the strict covers\. For an*ordered*incomparable paira∥Pba\\parallel\_\{P\}b, define

BP\(a,b\)=\(PredP\(a\)×SuccP\(b\)\)∖⪯P\.B\_\{P\}\(a,b\)=\\bigl\(\\operatorname\{Pred\}\_\{P\}\(a\)\\times\\operatorname\{Succ\}\_\{P\}\(b\)\\bigr\)\\setminus\\preceq\_\{P\}\.Letβ⁡\(P\)\\beta\(P\)be the minimum size of a setN⊆U2∖⪯PN\\subseteq U^\{2\}\\setminus\\preceq\_\{P\}that intersects everyBP​\(a,b\)B\_\{P\}\(a,b\)\. The ordered constraints\(a,b\)\(a,b\)and\(b,a\)\(b,a\)are counted separately\.

###### Lemma S7\(Cover necessity\)\.

Every strict cover\(x,y\)\(x,y\)ofPPmust appear as a positive label in every teaching set forPP\.

###### Proof\.

Suppose the positive pair\(x,y\)\(x,y\)is omitted\. Delete only this pair fromPPand call the resulting relationQQ\. Reflexivity and antisymmetry are unchanged\. If transitivity failed, there would beu⪯Qv⪯Qwu\\preceq\_\{Q\}v\\preceq\_\{Q\}wwhose required pair is the only deleted pair, sou=xu=xandw=yw=y\. The intermediate vertex cannot bexxoryy, because one of the two premises would then itself be the deleted pair\. Hencex≺Pv≺Pyx\\prec\_\{P\}v\\prec\_\{P\}y, contradicting that\(x,y\)\(x,y\)is a cover\. ThusQQis a poset\. Every other positive label remains true, and every negative label remains false becauseQ⊂PQ\\subset P\. The prompt would therefore be consistent withQ≠PQ\\neq P, contradicting teaching\. ∎

###### Theorem S8\(Exact teaching characterization\)\.

For every finite posetPP,

τow​\(P\)=\|Cov⁡\(P\)\|\+β⁡\(P\)\.\\tau\_\{\\mathrm\{ow\}\}\(P\)=\|\\operatorname\{Cov\}\(P\)\|\+\\beta\(P\)\.

###### Proof\.

For the lower bound, Lemma[S7](https://arxiv.org/html/2608.14004#Thmtheorem7a)requires all covers as positive labels\. LetNNbe the negative labels of any teaching set\. SupposeNNmissesBP​\(a,b\)B\_\{P\}\(a,b\)for an ordered incomparable pair\. Apply Lemma[S3](https://arxiv.org/html/2608.14004#Thmtheorem3a)withR=⪯PR=\\preceq\_\{P\}\. Sincea∥Pba\\parallel\_\{P\}b, in particularb⋠Pab\\not\\preceq\_\{P\}a, so the extension

Pa,b=P∪\(PredP⁡\(a\)×SuccP⁡\(b\)\)P\_\{a,b\}=P\\cup\\bigl\(\\operatorname\{Pred\}\_\{P\}\(a\)\\times\\operatorname\{Succ\}\_\{P\}\(b\)\\bigr\)is a poset\. Its newly added pairs are exactly contained inBP​\(a,b\)B\_\{P\}\(a,b\), and by assumption none is inNN\. It contains all positive labels and violates no negative label, contradicting uniqueness\. HenceNNhits every blocker set, so\|N\|≥β⁡\(P\)\|N\|\\geq\\beta\(P\)andτow​\(P\)≥\|Cov⁡\(P\)\|\+β⁡\(P\)\\tau\_\{\\mathrm\{ow\}\}\(P\)\\geq\|\\operatorname\{Cov\}\(P\)\|\+\\beta\(P\)\.

For the upper bound, label every cover positive and choose a minimum blocker hitting setNNas negative\. In a finite poset, every strict comparison lies on a saturated chain of covers; therefore every consistent posetQQcontains all ofPP\. IfQ≠PQ\\neq P, choose\(a,b\)∈Q∖P\(a,b\)\\in Q\\setminus P\. The reverse pair cannot belong toPP, because thenQQwould contain both directions between distinct elements and violate antisymmetry\. Thusa∥Pba\\parallel\_\{P\}b\. SinceQQcontainsPPanda⪯Qba\\preceq\_\{Q\}b, transitivity forces every pair inPredP⁡\(a\)×SuccP⁡\(b\)\\operatorname\{Pred\}\_\{P\}\(a\)\\times\\operatorname\{Succ\}\_\{P\}\(b\), including every member ofBP​\(a,b\)B\_\{P\}\(a,b\)\. The hitting set contains some negative label in this blocker set, contradicting consistency ofQQ\. HenceQ=PQ=P, proving the matching upper bound\. ∎

###### Corollary S9\(General bounds, exact extrema, and semantic cost\)\.

IfI⁡\(P\)I\(P\)is the number of unordered incomparable pairs, then

\|Cov⁡\(P\)\|≤τow​\(P\)≤\|Cov⁡\(P\)\|\+2​I​\(P\)\.\|\\operatorname\{Cov\}\(P\)\|\\leq\\tau\_\{\\mathrm\{ow\}\}\(P\)\\leq\|\\operatorname\{Cov\}\(P\)\|\+2I\(P\)\.For thenn\-element chainCnC\_\{n\}and antichainAnA\_\{n\},

τow​\(Cn\)=n−1,τow​\(An\)=n⁡\(n−1\)\.\\tau\_\{\\mathrm\{ow\}\}\(C\_\{n\}\)=n\-1,\\qquad\\tau\_\{\\mathrm\{ow\}\}\(A\_\{n\}\)=n\(n\-1\)\.Moreover,

maxP​on​n​elements⁡τow​\(P\)=n⁡\(n−1\),\\max\_\{P\\text\{ on \}n\\text\{ elements\}\}\\tau\_\{\\mathrm\{ow\}\}\(P\)=n\(n\-1\),with equality uniquely forAnA\_\{n\}\. Ifτcw​\(P\)\\tau\_\{\\mathrm\{cw\}\}\(P\)counts the cover edges needed when a prompt is declared to be the complete Hasse diagram, then

τcw​\(P\)=\|Cov⁡\(P\)\|,τow​\(P\)−τcw​\(P\)=β⁡\(P\)\.\\tau\_\{\\mathrm\{cw\}\}\(P\)=\|\\operatorname\{Cov\}\(P\)\|,\\qquad\\tau\_\{\\mathrm\{ow\}\}\(P\)\-\\tau\_\{\\mathrm\{cw\}\}\(P\)=\\beta\(P\)\.

###### Proof\.

For every ordered incomparable pair\(a,b\)\(a,b\), reflexivity gives\(a,b\)∈BP​\(a,b\)\(a,b\)\\in B\_\{P\}\(a,b\)\. Selecting all ordered incomparable pairs is therefore a hitting set of size2​I​\(P\)2I\(P\), proving the upper bound; the cover term gives the lower bound\. A chain hasn−1n\-1covers and no incomparable pairs, including the edge casen=1n=1\. In an antichain,BP​\(a,b\)=\{\(a,b\)\}B\_\{P\}\(a,b\)=\\\{\(a,b\)\\\}for every distinct ordered pair, so alln⁡\(n−1\)n\(n\-1\)negative labels are necessary and there are no covers\.

For anynn\-element poset, the number of unordered comparable pairs is\(n2\)−I⁡\(P\)\\binom\{n\}\{2\}\-I\(P\)and covers form a subset of them\. Therefore

τow​\(P\)≤\|Cov⁡\(P\)\|\+2​I​\(P\)≤\(n2\)\+I⁡\(P\)≤n⁡\(n−1\)\.\\tau\_\{\\mathrm\{ow\}\}\(P\)\\leq\|\\operatorname\{Cov\}\(P\)\|\+2I\(P\)\\leq\\binom\{n\}\{2\}\+I\(P\)\\leq n\(n\-1\)\.If equality holds, then the last inequality forcesI⁡\(P\)=\(n2\)I\(P\)=\\binom\{n\}\{2\}, so every distinct pair is incomparable andP=AnP=A\_\{n\}\. The antichain calculation shows attainability\.

Under complete\-Hasse semantics, displaying all covers is sufficient because their reflexive transitive closure isPP\. Every cover is necessary: omitting it changes the declared complete Hasse diagram and therefore the generated poset\. Thusτcw​\(P\)=\|Cov⁡\(P\)\|\\tau\_\{\\mathrm\{cw\}\}\(P\)=\|\\operatorname\{Cov\}\(P\)\|\. Theorem[S8](https://arxiv.org/html/2608.14004#Thmtheorem8a)then gives the differenceβ⁡\(P\)\\beta\(P\)\. ∎

The quantityβ⁡\(P\)\\beta\(P\)is a minimum hitting\-set instance\. Minimum hitting set is NP\-hard in general, but we do not determine the complexity of the structured blocker\-set instances induced by posets\.

## 6Order Dimension and the Conditional Decoder Bound

Order dimension is classical[7](https://arxiv.org/html/2608.14004#bib.bib17);[20](https://arxiv.org/html/2608.14004#bib.bib18)\. The following equivalence is classical as well; see[20](https://arxiv.org/html/2608.14004#bib.bib18)\. We record the exact form because the prompt\-dependent decoder corollary uses both directions\.

###### Theorem S10\(Coordinate\-order equivalence\)\.

For a nonempty finite posetPPand an integers≥1s\\geq 1, the following are equivalent:

1. 1\.there are mapsϕi:U→ℝ\\phi\_\{i\}:U\\to\\mathbb\{R\},i∈\[s\]i\\in\[s\], such that x⪯Py⟺ϕi\(x\)≤ϕi\(y\)for everyi;x\\preceq\_\{P\}y\\quad\\Longleftrightarrow\\quad\\phi\_\{i\}\(x\)\\leq\\phi\_\{i\}\(y\)\\quad\\text\{for every \}i;
2. 2\.dim⁡\(P\)≤s\\operatorname\{dim\}\(P\)\\leq s\.

###### Proof\.

Assume the coordinate representation\. Fix a linear extensionL0L\_\{0\}ofPP\. For eachii, order the elements by increasingϕi\\phi\_\{i\}and break ties according toL0L\_\{0\}; call the resulting total orderLiL\_\{i\}\. Ifx⪯Pyx\\preceq\_\{P\}y, thenϕi​\(x\)≤ϕi​\(y\)\\phi\_\{i\}\(x\)\\leq\\phi\_\{i\}\(y\)for everyii\. A strict inequality putsxxbeforeyydirectly, and an equality is resolved in the same direction byL0L\_\{0\}\. Thus everyLiL\_\{i\}extendsPP\.

Ifx⋠Pyx\\not\\preceq\_\{P\}y, the biconditional in the coordinate representation implies that somejjsatisfiesϕj​\(x\)\>ϕj​\(y\)\\phi\_\{j\}\(x\)\>\\phi\_\{j\}\(y\)\. HenceLjL\_\{j\}placesyybeforexx, so\(x,y\)\(x,y\)is absent from the intersection of theLiL\_\{i\}\. We have shown both inclusionsP⊆⋂iLiP\\subseteq\\bigcap\_\{i\}L\_\{i\}and⋂iLi⊆P\\bigcap\_\{i\}L\_\{i\}\\subseteq P\. Therefore theLiL\_\{i\}form a realizer anddim⁡\(P\)≤s\\operatorname\{dim\}\(P\)\\leq s\.

Conversely, ifdim⁡\(P\)=t≤s\\operatorname\{dim\}\(P\)=t\\leq s, take att\-member realizer and repeat one member untilssordersL1,…,LsL\_\{1\},\\ldots,L\_\{s\}are listed\. Letϕi​\(x\)\\phi\_\{i\}\(x\)be the rank ofxxinLiL\_\{i\}\. Thenϕi​\(x\)≤ϕi​\(y\)\\phi\_\{i\}\(x\)\\leq\\phi\_\{i\}\(y\)for alliiexactly whenxxprecedesyyin every realizer order, which is equivalent tox⪯Pyx\\preceq\_\{P\}y\. ∎

Let𝖯𝗋𝗈𝗆𝗉𝗍⁡\(U\)\\mathsf\{Prompt\}\(U\)be the prompts overUU, and fix an integers≥1s\\geq 1\. Anss\-coordinate decoder is a fixed mapΦ:𝖯𝗋𝗈𝗆𝗉𝗍⁡\(U\)→\(ℝU\)s\\Phi:\\mathsf\{Prompt\}\(U\)\\to\(\\mathbb\{R\}^\{U\}\)^\{s\}with the conjunctive coordinatewise decision rule\. A task family𝒯⊆𝖯𝗋𝗈𝗆𝗉𝗍⁡\(U\)×𝖯𝗈𝗌𝖾𝗍⁡\(U\)\\mathcal\{T\}\\subseteq\\mathsf\{Prompt\}\(U\)\\times\\mathsf\{Poset\}\(U\)is functional in its first coordinate:\(𝒟,P\),\(𝒟,Q\)∈𝒯\(\\mathcal\{D\},P\),\(\\mathcal\{D\},Q\)\\in\\mathcal\{T\}impliesP=QP=Q\.

###### Corollary S11\(Exact coordinate\-decoder capability boundary\)\.

An exactss\-coordinate decoder exists on𝒯\\mathcal\{T\}if and only if every targetP𝒟P\_\{\\mathcal\{D\}\}in the family satisfiesdim⁡\(P𝒟\)≤s\\operatorname\{dim\}\(P\_\{\\mathcal\{D\}\}\)\\leq s\. In particular, width at mostssfor every target is sufficient, whereas one target of dimension greater thanssmakes exact decoding impossible\.

###### Proof\.

If a decoder is exact, its coordinates at prompt𝒟\\mathcal\{D\}form anss\-coordinate representation ofP𝒟P\_\{\\mathcal\{D\}\}, so Theorem[S10](https://arxiv.org/html/2608.14004#Thmtheorem10a)givesdim⁡\(P𝒟\)≤s\\operatorname\{dim\}\(P\_\{\\mathcal\{D\}\}\)\\leq s\. Conversely, if every target has dimension at mostss, choose anss\-coordinate realization for each target, padding by repeated coordinates when needed\. Define the fixed mapΦ\\Phito return that realization on prompts occurring in𝒯\\mathcal\{T\}and extend it arbitrarily to all other prompts\. The width statement follows from the classical inequalitydim⁡\(P\)≤0​p​t​\(P\)\\operatorname\{dim\}\(P\)\\leq 0pt\(P\)[6](https://arxiv.org/html/2608.14004#bib.bib19);[20](https://arxiv.org/html/2608.14004#bib.bib18)\. ∎

This is an exact, zero\-error representation boundary for the specified decoder form\. The sufficiency argument is not an efficient learning algorithm, and approximate decoders and unrestricted neural representations are outside the statement\.

###### Proposition S12\(Standard poset families and finite divisibility\)\.

Forn,m,r≥1n,m,r\\geq 1:

1. 1\.a chainCnC\_\{n\}has dimension one;
2. 2\.the Boolean latticeBm=\(2\[m\],⊆\)B\_\{m\}=\(2^\{\[m\]\},\\subseteq\)has dimensionmm;
3. 3\.ifN=∏i=1rpieiN=\\prod\_\{i=1\}^\{r\}p\_\{i\}^\{e\_\{i\}\}with distinct primes andei≥1e\_\{i\}\\geq 1, then the positive\-divisor poset ofNNhas dimensionrr;
4. 4\.ifDn=\(\[n\],∣\)D\_\{n\}=\(\[n\],\\mid\)and the product of the firstrrprimes is at mostnn, thendim⁡\(Dn\)≥r\\operatorname\{dim\}\(D\_\{n\}\)\\geq r, so these dimensions are unbounded\.

###### Proof\.

A nonempty chain is already a linear order, so its dimension is one\.

ForBmB\_\{m\}, membership indicators give anmm\-coordinate representation, so Theorem[S10](https://arxiv.org/html/2608.14004#Thmtheorem10a)yields the upper bound\. The casem=1m=1is a chain\. The latticeB2B\_\{2\}is not a chain, so its dimension is at least two, matching the upper bound\. Assumem≥3m\\geq 3and defineai=\{i\}a\_\{i\}=\\\{i\\\}andbi=\[m\]∖\{i\}b\_\{i\}=\[m\]\\setminus\\\{i\\\}\. Thenai⊆bja\_\{i\}\\subseteq b\_\{j\}wheni≠ji\\neq j, whileaia\_\{i\}andbib\_\{i\}are incomparable\. A single linear extension cannot reverse both pairs\(ai,bi\)\(a\_\{i\},b\_\{i\}\)and\(aj,bj\)\(a\_\{j\},b\_\{j\}\)fori≠ji\\neq j, because the required relations would give

bi<ai<bj<aj<bi\.b\_\{i\}<a\_\{i\}<b\_\{j\}<a\_\{j\}<b\_\{i\}\.For each incomparable pair\(ai,bi\)\(a\_\{i\},b\_\{i\}\), some member of any realizer must placebib\_\{i\}beforeaia\_\{i\}; otherwiseai≤bia\_\{i\}\\leq b\_\{i\}would survive in the intersection\. Hence at leastmmlinear extensions are needed, provingdim⁡\(Bm\)=m\\operatorname\{dim\}\(B\_\{m\}\)=m\.

For divisors ofNN, mapddto the exponent vector\(vp1​\(d\),…,vpr​\(d\)\)\(v\_\{p\_\{1\}\}\(d\),\\ldots,v\_\{p\_\{r\}\}\(d\)\)\. Divisibility is exactly coordinatewise comparison, giving dimension at mostrr\. The squarefree divisors∏i∈Api\\prod\_\{i\\in A\}p\_\{i\}induce a copy ofBrB\_\{r\}\. Order dimension is monotone under subposets because restricting every linear extension in a realizer gives a realizer of the subposet\. Thus the divisor poset has dimension at leastrrand therefore exactlyrr\.

Finally, ifM=p1⋯pr≤nM=p\_\{1\}\\cdots p\_\{r\}\\leq n, every squarefree divisor ofMMlies in\[n\]\[n\]and the induced divisibility subposet isBrB\_\{r\}\. Monotonicity givesdim⁡\(Dn\)≥r\\operatorname\{dim\}\(D\_\{n\}\)\\geq r\. Since primorials are finite for every fixedrr, the dimensions are unbounded asnngrows\. Sharper asymptotics are known[15](https://arxiv.org/html/2608.14004#bib.bib20)\. ∎

### Structural\-profile entries\.

For a chainCnC\_\{n\}, the longest cover path and the largest reachable set associated with a false query both have sizen−1n\-1\. ForBmB\_\{m\}, covers add one ground\-set element, givingm​2m−1m2^\{m\-1\}covers and maximum positive path lengthmm; a false query with a singleton left set has2m−12^\{m\-1\}reachable supersets, which is maximal\. ForN=∏ipieiN=\\prod\_\{i\}p\_\{i\}^\{e\_\{i\}\}, exponent vectors show height1\+∑iei1\+\\sum\_\{i\}e\_\{i\}, cover count∑iei​∏j≠i\(ej\+1\)\\sum\_\{i\}e\_\{i\}\\prod\_\{j\\neq i\}\(e\_\{j\}\+1\), maximum positive path length∑iei\\sum\_\{i\}e\_\{i\}, and maximum negative witness sizemaxi⁡ei​∏j≠i\(ej\+1\)\\max\_\{i\}e\_\{i\}\\prod\_\{j\\neq i\}\(e\_\{j\}\+1\)\. ForDn=\(\[n\],∣\)D\_\{n\}=\(\[n\],\\mid\), the chain1,2,4,…1,2,4,\\ldotsgives height⌊log2⁡n⌋\+1\\lfloor\\log\_\{2\}n\\rfloor\+1and maximum positive length⌊log2⁡n⌋\\lfloor\\log\_\{2\}n\\rfloor; the numbers greater thann/2n/2form an antichain of size⌈n/2⌉\\lceil n/2\\rceil; covers are exactly pairs\(a,a​p\)\(a,ap\)withppprime, giving∑p≤n⌊n/p⌋\\sum\_\{p\\leq n\}\\lfloor n/p\\rfloor; and a false query froma=2a=2has⌊n/2⌋\\lfloor n/2\\rfloorreachable multiples, which is maximal amonga≥2a\\geq 2\.

## 7Expanded Certificate Proofs

LetH⁡\(P\)H\(P\)be the complete Hasse DAG of a finite poset\. Fora⪯Pba\\preceq\_\{P\}b, letλP\+​\(a,b\)\\lambda\_\{P\}^\{\+\}\(a,b\)be the length of the shortest directed cover path fromaatobb, with length zero whena=ba=b\.

###### Proposition S13\(Positive chain\-certificate bound\)\.

Any positive certificate that consists only of demonstrated cover edges has at leastλP\+​\(a,b\)\\lambda\_\{P\}^\{\+\}\(a,b\)edges\. A procedure required to produce or verify a cover path of length at mostTTtherefore cannot certify every positive query withλP\+​\(a,b\)\>T\\lambda\_\{P\}^\{\+\}\(a,b\)\>T\.

###### Proof\.

A certificate made only of cover edges is a directed path in the Hasse DAG\. By definition,λP\+​\(a,b\)\\lambda\_\{P\}^\{\+\}\(a,b\)is the minimum number of edges among all such paths\. No shorter valid chain certificate exists\. The second statement follows from the restriction on the permitted witness\. It does not rule out a different global reachability algorithm\. ∎

CallS⊆US\\subseteq Uforward closed if no Hasse edge has its tail inSSand its head outsideSS\.

The following elementary graph observation is recorded because it yields the canonical negative witness\.

###### Lemma S14\(Forward\-closed nonreachability witness\)\.

There is no directed path fromaatobbin a finite Hasse DAG if and only if there exists a forward\-closed setSSwitha∈Sa\\in Sandb∉Sb\\notin S\.

###### Proof\.

If such anSSexists, a directed path starting ata∈Sa\\in Scannot leaveSS, because every traversed edge remains inside a forward\-closed set\. It therefore cannot reachb∉Sb\\notin S\.

Conversely, supposebbis not reachable fromaaand takeS=ReachH⁡\(a\)S=\\operatorname\{Reach\}\_\{H\}\(a\)\. Thena∈Sa\\in Sandb∉Sb\\notin S\. If an edge\(x,y\)\(x,y\)leftSS, thenxxwould be reachable fromaaand the additional edge would makeyyreachable as well, contradictingy∉Sy\\notin S\. HenceSSis forward closed\. ∎

For a nonreachable pair define the canonical witness\-size statistic directly by

νP−​\(a,b\)=\|ReachH⁡\(a\)\|\.\\nu\_\{P\}^\{\-\}\(a,b\)=\|\\operatorname\{Reach\}\_\{H\}\(a\)\|\.
###### Corollary S15\(Minimality of the canonical negative witness\)\.

Ifbbis not reachable fromaa, thenReachH⁡\(a\)\\operatorname\{Reach\}\_\{H\}\(a\)is the unique inclusion\-minimal forward\-closed set containingaaand excludingbb\. It also has minimum cardinality among such sets\. Thus the direct definition ofνP−​\(a,b\)\\nu\_\{P\}^\{\-\}\(a,b\)equals the corresponding minimum, and for fixedHHandaait is independent of the choice of nonreachablebb\.

###### Proof\.

Lemma[S14](https://arxiv.org/html/2608.14004#Thmtheorem14a)shows thatReachH⁡\(a\)\\operatorname\{Reach\}\_\{H\}\(a\)is an eligible separator\. LetSSbe any forward\-closed set containingaa\. We prove by induction on path length that every vertex reachable fromaalies inSS\. The base vertexaalies inSS\. If a path reachesyythrough an edge\(x,y\)\(x,y\)and the induction hypothesis givesx∈Sx\\in S, forward closure givesy∈Sy\\in S\. ThusReachH⁡\(a\)⊆S\\operatorname\{Reach\}\_\{H\}\(a\)\\subseteq Sfor every eligible separator\. It is therefore the unique inclusion\-minimal one and has minimum cardinality\. ∎

## 8Assumptions and Dependency Summary

The completion and teaching results depend on Lemma S3’s one\-edge closure formula\. The trichotomy assumes all posets on a fixed finite universe and a satisfiable mixed\-label prompt\. The deterministic illustration is an exhaustive enumeration for the specifically defined uniform distribution over four\-element targets, prompt subsets, and unobserved queries; no theorem depends on that illustration\. The teaching theorem uses the same known universe and arbitrary positive and negative ordered\-pair labels\. Corollary S11 concerns exact prompt\-dependent monotone\-coordinate decoding, and the certificate results concern the stated path and forward\-closed witness systems\.

Version spaces, teaching dimension, Hasse reachability, and Dushnik–Miller dimension are classical[16](https://arxiv.org/html/2608.14004#bib.bib21);[11](https://arxiv.org/html/2608.14004#bib.bib24);[7](https://arxiv.org/html/2608.14004#bib.bib17);[20](https://arxiv.org/html/2608.14004#bib.bib18)\. The new synthesis separates prompt entailment, the open\-world teaching surcharge, structural profile coordinates, certificate size, and the exact capacity of a specified coordinate\-decoder class\.