OctoInformBeta

OpenAI preprint, September 2026 · §6. Short global lists and changes of direction

Lemma 6.2: Strict comparisons lift when the smaller-key job belongs to the pruning set

Lifting key comparisons from a pruned list.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

For a global job set JJ, a child subproblem in scheduling has a job set W⊆JW\subseteq J, while its lists may still refer to jobs throughout JJ. The issue is how a priority comparison made within the child relates to the original list.

An indexed global set family ℒ\mathcal L on a job set JJ consists of a finite set I⊆ℕI\subseteq\mathbb N of indices and a set Li⊆JL_i\subseteq J for every i∈ℕi\in\mathbb N.✦ The membership indices Mℒ(x)M_{\mathcal L}(x) of a job x∈Jx\in J are the listed indices whose entries contain xx, as in (1). Mℒ(x)={i∈I:x∈Li}.M_{\mathcal L}(x)=\{i\in I:x\in L_i\}.(1)✦

The last membership index ℓℒ(x)\ell_{\mathcal L}(x) of a job x∈Jx\in J is the maximum of its membership indices, with default zero, as in (2). ℓℒ(x)=max⁡({0}∪Mℒ(x)).\ell_{\mathcal L}(x)=\max\bigl(\{0\}\cup M_{\mathcal L}(x)\bigr).(2)✦

For a rank function ρ:J→ℕ\rho:J\to\mathbb N, the lexicographic list priority ≺ℒ,ρ\prec_{\mathcal L,\rho} on JJ is the relation that compares the keys (ℓℒ(x),ρ(x))(\ell_{\mathcal L}(x),\rho(x)) by the rule in (3). x≺ℒ,ρy⇔ℓℒ(x)<ℓℒ(y)or(ℓℒ(x)=ℓℒ(y)andρ(x)<ρ(y)).x\prec_{\mathcal L,\rho}y \quad\Longleftrightarrow\quad \ell_{\mathcal L}(x)<\ell_{\mathcal L}(y) \ \text{or}\ \bigl(\ell_{\mathcal L}(x)=\ell_{\mathcal L}(y) \ \text{and}\ \rho(x)<\rho(y)\bigr).(3)✦

The pruned global job list ℒW\mathcal L^W of ℒ\mathcal L relative to W⊆JW\subseteq J is the indexed global set family that retains the indices whose entries meet WW and leaves every global entry unchanged, as in (4). IW={i∈I:Li∩W≠⌀},ℒW=(IW,(Li)i∈ℕ).I_W=\{i\in I:L_i\cap W\ne\varnothing\}, \qquad \mathcal L^W=\bigl(I_W,(L_i)_{i\in\mathbb N}\bigr).(4)✦

The Claim

Theorem 1. Let ℒ\mathcal L be an indexed global set family on JJ, let W⊆JW\subseteq J, and let ρ:J→ℕ\rho:J\to\mathbb N be a rank function. Suppose x∈Wx\in W and y∈Jy\in J, and suppose xx has a smaller key than yy for the pruned family ℒW\mathcal L^W. Then the original priority satisfies (5). x≺ℒ,ρy.x\prec_{\mathcal L,\rho}y.(5)✦

In the paper, the result reads: if a job x∈Wx\in W is eligible for comparison in the list pruned on WW and yy is any job in JJ eligible for comparison in that pruned list, a smaller pruned key for xx than for yy implies the same comparison before pruning.

What Is Checked

The claim is stated over indexed global set families on an arbitrary job set JJ, an arbitrary subset W⊆JW\subseteq J, and an arbitrary natural-number rank function ρ\rho, with the smaller-key job required to belong to WW.