TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6.1-sol)audited 2026-10-08

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.

The interval criterion for a lattice congruence: interval classes with monotone endpoints

Statement

Let $L$ be a finite lattice and let $θ$ be an equivalence relation on $L$ whose classes are intervals: for every $x \in L$ there are elements $d (x) \leq u (x)$ of the class $[x]_{θ}$ with $[x]_{θ} = {z \in L : d (x) \leq z \leq u (x)}$ (Finite lattice congruences, interval endpoints and descending rooted-chain labels, Intervals in a poset; locally finite, lower-finite and upper-finite posets). Then $θ$ is a lattice congruence if and only if the endpoint maps $d : L \to L$ and $u : L \to L$ are order-preserving. Explicitly:

(i) (necessity) if $θ$ is a lattice congruence then $d$ and $u$ are order-preserving; this is Lattice quotient descent, class intervals and monotone endpoints(iv), with $d = π_{↓}$ and $u = π_{↑}$ ;

(ii) (sufficiency) if $d$ and $u$ are order-preserving then $x \equiv_{θ} y$ implies $x \lor z \equiv_{θ} y \lor z$ and $x \land z \equiv_{θ} y \land z$ for every $z \in L$ ; hence $θ$ is a lattice congruence, and the quotient operations of Finite lattice congruences, interval endpoints and descending rooted-chain labels are well defined.

Facts & Assumptions

Given: A finite lattice $L$ with meet $\land$ and join $\lor$ , an equivalence relation $θ$ on $L$ whose classes are intervals, and for every $w \in L$ elements $d (w) \leq u (w)$ of $[w]_{θ}$ with $[w]_{θ} = {z \in L : d (w) \leq z \leq u (w)}$ .

[F1]

$θ$ is a lattice congruence when $x \equiv_{θ} x^{'}$ and $y \equiv_{θ} y^{'}$ imply $x \land y \equiv_{θ} x^{'} \land y^{'}$ and $x \lor y \equiv_{θ} x^{'} \lor y^{'}$ (Finite lattice congruences, interval endpoints and descending rooted-chain labels).

[F2]

Interval hypothesis: the class of $w$ equals ${z : d (w) \leq z \leq u (w)}$ , and $d (w), u (w)$ lie in it; hence $d (w) \leq z \leq u (w)$ for every $z \equiv_{θ} w$ , and $d (w) \leq w \leq u (w)$ (Intervals in a poset; locally finite, lower-finite and upper-finite posets).

[F3]

Monotonicity hypothesis in (ii): if $x \leq y$ then $d (x) \leq d (y)$ and $u (x) \leq u (y)$ .

[F4]

For a lattice congruence each class has a least member $π_{↓} (w)$ and a greatest member $π_{↑} (w)$ , both in the class, and the class is the interval between them (Lattice quotient descent, class intervals and monotone endpoints (ii)).

[F5]

For a lattice congruence the endpoint maps $π_{↓}$ and $π_{↑}$ are order-preserving (Lattice quotient descent, class intervals and monotone endpoints (iv)).

[F6]

Meet and join are the greatest lower and the least upper bound of a pair: $x \land y \leq x$ , $x \land y \leq y$ , and $z \leq x \land y$ whenever $z \leq x$ and $z \leq y$ ; dually $x \leq x \lor y$ , $y \leq x \lor y$ , and $x \lor y \leq z$ whenever $x \leq z$ and $y \leq z$ (Lattices, distributive lattices, and order ideals).

[F7]

$θ$ is reflexive, symmetric and transitive; $[a]_{θ} = {b : a \equiv_{θ} b}$ ; and $a \equiv_{θ} b$ if and only if $[a]_{θ} = [b]_{θ}$ (Equivalence relation, equivalence class, and the quotient set $A / \sim$ , The equivalence classes of an equivalence relation are nonempty, cover $A$ , and are pairwise equal or disjoint; conversely every such cover arises from exactly one equivalence relation).

[F8]

Antisymmetry: $m \leq m^{'}$ and $m^{'} \leq m$ imply $m = m^{'}$ (Partial order and partially ordered set).

Proof

technique · direct

1.1F2F4F5F8

(i) Assume $θ$ is a lattice congruence. For $w \in L$ the element $d (w)$ lies in the class of $w$ and satisfies $d (w) \leq z$ for every $z$ in that class by [F2], so $d (w)$ is a least member of the class; by [F4] the class has a least member $π_{↓} (w)$ , and two least members of one set are equal by [F8], so $d (w) = π_{↓} (w)$ . Symmetrically $u (w) = π_{↑} (w)$ . Hence $d = π_{↓}$ and $u = π_{↑}$ are order-preserving by [F5].

1.2F2F7F8

If $[x]_{θ} = [y]_{θ}$ then $d (x) = d (y)$ and $u (x) = u (y)$ : indeed $d (x)$ lies in the class of $x$ , which is $[d (y), u (y)]$ , so $d (y) \leq d (x)$ ; conversely $d (y)$ lies in $[d (x), u (x)]$ , so $d (x) \leq d (y)$ ; hence $d (x) = d (y)$ by [F8], and the same argument with $u$ in place of $d$ gives $u (x) = u (y)$ . In particular $x \equiv_{θ} y$ implies $d (x) = d (y)$ and $u (x) = u (y)$ by [F7].

2.1F2F6F7step 1.2

(ii) Assume the monotonicity hypothesis [F3] and let $x \equiv_{θ} y$ . By step 1.2, $d (x) = d (y)$ and $u (x) = u (y)$ ; from [F2] and [F6], $d (x) \leq x \land y$ (since $d (x) \leq x$ and $d (x) = d (y) \leq y$ ), and $x \land y \leq x \leq u (x) = u (y)$ , and also $x \land y \leq y \leq u (y)$ . So $x \land y$ lies in $[d (x), u (x)]$ , the class of $x$ , and in $[d (y), u (y)]$ , the class of $y$ ; that is, $x \land y \equiv_{θ} x$ and $x \land y \equiv_{θ} y$ , with $x \land y \leq x$ and $x \land y \leq y$ .

2.2F2F3F6F7step 1.2

(ii) Comparable join case. Assume $x \leq y$ and $x \equiv_{θ} y$ , and let $z \in L$ . By step 1.2 and [F3] applied to $x \leq x \lor z$ , we have $u (x) = u (y) \leq u (x \lor z)$ ; since $y \leq u (y)$ by [F2], and $z \leq x \lor z \leq u (x \lor z)$ by [F6], the upper bound property of the join gives $y \lor z \leq u (x \lor z)$ . Together with $d (x \lor z) \leq x \lor z \leq y \lor z$ (from [F2] and $x \leq y$ ), the element $y \lor z$ lies in the class $[d (x \lor z), u (x \lor z)]$ of $x \lor z$ , so $x \lor z \equiv_{θ} y \lor z$ .

2.3F2F3F6F7step 1.2

(ii) Comparable meet case. Assume $x \leq y$ and $x \equiv_{θ} y$ , and let $z \in L$ . By [F3] applied to $y \land z \leq y$ and step 1.2, $d (y \land z) \leq d (y) = d (x) \leq x$ ; also $d (y \land z) \leq y \land z \leq z$ by [F6]. Hence $d (y \land z) \leq x \land z$ by the lower bound property of the meet, while $x \land z \leq y \land z$ (as $x \leq y$ ) and $y \land z \leq u (y \land z)$ by [F2]. So $x \land z$ lies in the class $[d (y \land z), u (y \land z)]$ of $y \land z$ , that is, $x \land z \equiv_{θ} y \land z$ .

3.1F7step 2.1step 2.2step 2.3

(ii) General equivalent pair. Assume $x \equiv_{θ} y$ and let $z \in L$ . By step 2.1 the element $c : = x \land y$ satisfies $c \equiv_{θ} x$ , $c \equiv_{θ} y$ , $c \leq x$ and $c \leq y$ . Step 2.2 applied to the comparable equivalent pairs $(c, x)$ and $(c, y)$ gives $c \lor z \equiv_{θ} x \lor z$ and $c \lor z \equiv_{θ} y \lor z$ ; transitivity [F7] gives $x \lor z \equiv_{θ} y \lor z$ . Step 2.3 applied to the same two pairs gives $c \land z \equiv_{θ} x \land z$ and $c \land z \equiv_{θ} y \land z$ ; transitivity gives $x \land z \equiv_{θ} y \land z$ .

4.1F1F7step 3.1

(ii) Congruence property and well-definedness. Assume $x \equiv_{θ} x^{'}$ and $y \equiv_{θ} y^{'}$ . Step 3.1 applied to the pair $(x, x^{'})$ with $z : = y$ gives $x \lor y \equiv_{θ} x^{'} \lor y$ , and applied to $(y, y^{'})$ with $z : = x^{'}$ gives $x^{'} \lor y \equiv_{θ} x^{'} \lor y^{'}$ ; transitivity gives $x \lor y \equiv_{θ} x^{'} \lor y^{'}$ . Likewise step 3.1 applied to $(x, x^{'})$ with $z : = y$ gives $x \land y \equiv_{θ} x^{'} \land y$ , and to $(y, y^{'})$ with $z : = x^{'}$ gives $x^{'} \land y \equiv_{θ} x^{'} \land y^{'}$ ; transitivity gives $x \land y \equiv_{θ} x^{'} \land y^{'}$ . By [F1] the relation $θ$ is therefore a lattice congruence. Consequently the proposed quotient operations are well defined: if $[x]_{θ} = [x^{'}]_{θ}$ and $[y]_{θ} = [y^{'}]_{θ}$ then $x \equiv_{θ} x^{'}$ and $y \equiv_{θ} y^{'}$ by [F7], so $x \lor y \equiv_{θ} x^{'} \lor y^{'}$ and $x \land y \equiv_{θ} x^{'} \land y^{'}$ , whence $[x \lor y]_{θ} = [x^{'} \lor y^{'}]_{θ}$ and $[x \land y]_{θ} = [x^{'} \land y^{'}]_{θ}$ by [F7].

5.1step 1.1step 2.1step 2.2step 2.3step 3.1step 4.1∎

Both directions of the criterion are proved: (i) is step 1.1, where necessity is the specialisation of the quotient lemma's monotone endpoints to $d, u$ ; (ii) is steps 2.1 through 4.1, in which an arbitrary equivalent pair is reduced to the comparable pairs $(c, x)$ and $(c, y)$ through the meet $c = x \land y$ , which lies in the class of $x$ and of $y$ .

Depends on

Used by

Cited to discharge well-definedness by Finite lattice congruences, interval endpoints and descending rooted-chain labels.

Dependency tree · two levels

23 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

Nathan Reading, Lattice congruences of the weak order: algebra, combinatorics, and geometry, Triangle Lectures in Combinatorics (2019), slides on the order-theoretic characterization of a lattice congruence (standard reference, not scraped)