Alphabeta Math
LemmaStatement: 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.

A convex chain (in particular a covering pair) of a finite poset occurs consecutively in some linear extension

Statement

Let (P,⪯) be a finite poset (Partial order and partially ordered set) and let C⊆P be a nonempty convex chain, meaning that C is a chain (Chain in a poset) and that x,z∈C and x⪯y⪯z imply y∈C. Then there is a linear extension of P (Linear extensions of a finite poset) in which the elements of C occur consecutively. In particular, for every covering pair x⋖y of P (Graded poset, rank function, and rank levels) there is a linear extension of P in which x and y are consecutive.

Facts & Assumptions

Given: A finite poset (P,⪯) and a nonempty convex chain C⊆P.

[F1]

A partial order is reflexive, antisymmetric and transitive, and its strict order is defined by x≺y if and only if x⪯y and x≠y (Partial order and partially ordered set).

[F2]

A subset of a poset is a chain when any two of its elements are comparable (Chain in a poset).

[F3]

An element y covers x when x≺y and there is no z∈P with x≺z≺y (Graded poset, rank function, and rank levels).

[F5]

A linear extension of a finite poset Q is a tuple listing every element of Q exactly once in which x≺y implies that x occurs before y (Linear extensions of a finite poset).

Proof

Given: A finite poset (P,⪯) and a nonempty convex chain C⊆P.

Proof technique: direct.

1.1givenF1F2

Setup. Enumerate the nonempty chain C in increasing order as C={c1≺c2≺⋯≺cm}, and set Q:=(P∖C)∪{∗} for a new element ∗∉P. Let R be the relation on Q consisting of the pairs (x,y) with x,y∈P∖C and x≺y, the pairs (x,∗) with x∈P∖C and x≺c for some c∈C, and the pairs (∗,y) with y∈P∖C and c≺y for some c∈C. Let ⪯Q be the reflexive transitive closure of R, so ⪯Q is reflexive and transitive by construction.

2.1givenF1step 1.1

The relation ⪯Q is antisymmetric. A cycle of R whose vertices lie in P∖C would produce x1≺x2≺⋯≺x1 in the poset P, impossible by transitivity and antisymmetry; so every nontrivial cycle passes through ∗, and between two consecutive occurrences of ∗ it consists of an edge (∗,y), a path inside P∖C from y to an element x, and an edge (x,∗). By the definition of R there are then c′,c∈C with c′≺y and x≺c, and the path inside P∖C gives y⪯x; hence c′⪯y⪯x⪯c. Since c′,c∈C and C is convex, this forces x∈C, contradicting x∈P∖C. Therefore R has no nontrivial cycles, and ⪯Q is a partial order on the finite set Q.

3.1givenF1F4F5step 2.1

By [F4] the finite poset Q has a linear extension πQ=(u1,…,ur); let π be the tuple obtained from πQ by replacing the one occurrence of ∗ with the block (c1,…,cm). Then π lists every element of P exactly once. It is a linear extension of P: if x≺y with x,y∈P∖C then x⪯Qy, so x precedes y in π; if x∈P∖C and x≺ci then (x,∗)∈R, so x precedes ∗ in πQ and hence precedes the whole block; if ci≺y with y∈P∖C then (∗,y)∈R, so the whole block precedes y; and the block itself lists c1,…,cm in increasing order, so it respects the relations inside C. Since C exhausts the block, its elements occur consecutively in π.

4.1givenF3step 3.1∎

In particular, let x⋖y be a covering pair and put C:={x,y}. Then C is a nonempty chain, and it is convex: if x⪯z⪯y with z∈P, then either z=x, or z=y, or x≺z≺y, which is excluded by [F3]; in all cases z∈C. So step 3.1 applies and yields a linear extension of P in which x and y are consecutive.

Depends on

Used by

Dependency tree · two levels

7 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