LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-5.6-terra)audited 2026-09-14

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Finite word-calculus rearrangement

Statement

For every positive integer $d$ ,

$\forall a_{1} \dots \forall a_{d} \exists x_{1} \dots \exists x_{d} ⊢_{d} \exists A_{1} \dots \exists A_{d} \forall x_{1} \dots \forall x_{d} .$

Facts & Assumptions

Given: A positive integer $d$ and the two displayed endpoint words.

[F1]

The language $L_{d}$ , elementary commutations, matched-pair replacement, finite block permutation, and $⊢_{d}$ are exactly the finite calculus in the preceding definition. The finite word calculus for the Halpern–Läuchli argument

Proof

technique · induction on $d$

1.1F1

Write $U_{m} = \forall a_{1} \dots \forall a_{m}$ , $X_{m} = \exists x_{1} \dots \exists x_{m}$ , $E_{m} = \exists A_{1} \dots \exists A_{m}$ , and $V_{m} = \forall x_{1} \dots \forall x_{m}$ . For $d > 1$ there is a bridge $\forall a_{d} E_{d - 1} V_{d - 1} \exists x_{d} ⊢_{d} \exists A_{d} U_{d - 1} X_{d - 1} \forall x_{d}$ : Rule 3 moves $E_{d - 1}$ left of $\forall a_{d}$ ; Rule 1 rearranges the middle as $(\exists A_{i} \forall x_{i})_{i = 1}^{d - 1} \forall a_{d} \exists x_{d}$ ; Rule 2 changes all $d$ matched pairs to $(\forall a_{i} \exists x_{i})_{i = 1}^{d - 1} \exists A_{d} \forall x_{d}$ ; Rule 1 moves each earlier $\exists x_{i}$ past later universal $a$ -symbols and commutes the existential symbols to give $U_{d - 1} \exists A_{d} X_{d - 1} \forall x_{d}$ ; and Rule 3 moves $\exists A_{d}$ left of $U_{d - 1}$ .

1.2F1

Derivations in $L_{d - 1}$ lift through either outside matched pair: $W ⊢_{d - 1} W^{'}$ implies both $\forall a_{d} W \exists x_{d} ⊢_{d} \forall a_{d} W^{'} \exists x_{d}$ and $\exists A_{d} W \forall x_{d} ⊢_{d} \exists A_{d} W^{'} \forall x_{d}$ . It suffices to lift one rule step. Rules 1 and 2 apply unchanged inside the context. For Rule 3, Rule 1 first rearranges its adjacent prefix of $a$ - and $A$ -symbols into a universal block followed by an existential block, Rule 3 exchanges the blocks, and Rule 1 restores the required order. The outside coordinate remains a complete ordered pair; induction on the finite derivation length proves both implications.

1.3F1base

If $d = 1$ , the asserted derivation is exactly $\forall a_{1} \exists x_{1} ⊢_{1} \exists A_{1} \forall x_{1}$ , an instance of Rule 2.

2.1F1step 1.1step 1.2ih

Suppose $d > 1$ and the result holds in dimension $d - 1$ . Rule 1 gives $U_{d} X_{d} ⊢_{d} \forall a_{d} U_{d - 1} X_{d - 1} \exists x_{d}$ . Lift the induction hypothesis by the first implication in step 1.2, apply the bridge from step 1.1, and lift the induction hypothesis by the second implication in step 1.2; thus $\forall a_{d} U_{d - 1} X_{d - 1} \exists x_{d} ⊢_{d} \forall a_{d} E_{d - 1} V_{d - 1} \exists x_{d} ⊢_{d} \exists A_{d} U_{d - 1} X_{d - 1} \forall x_{d} ⊢_{d} \exists A_{d} E_{d - 1} V_{d - 1} \forall x_{d}$ . Rule 1 finally commutes the $A$ -symbols and the $x$ -symbols to obtain $E_{d} V_{d}$ .

3.1F1step 1.3step 2.1discharge-induction∎

Every intermediate word lies in $L_{d}$ : elementary commutation changes no coordinate's selected pair, Rule 2 replaces one legal ordered pair by the other, and Rule 3 is invoked only with its result in $L_{d}$ . Steps 1.3 and 2.1 therefore prove the assertion for every positive $d$ .

Depends on

The finite word calculus for the Halpern–Läuchli argument

Used by

A dimension-two Halpern–Läuchli word rearrangement Example
Halpern–Läuchli dense-matrix dichotomy Theorem

Dependency tree · two levels

2 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Halpern–Läuchli, A partition theorem (1966), Lemma 1, pp. 364–365 (standard reference, not scraped)
Monk, Set theory following Jech (2024), endpoint-word derivation in Theorem 29.28, pp. 662–664 (standard reference, not scraped)