has_ordered_copy_self
Every ordered graph contains an ordered copy of itself via the identity map.
Statement
theorem has_ordered_copy_self {α : Type*} [LinearOrder α] (G : SimpleGraph α) : has_ordered_copy G G
- Source
- arXiv:2611.08375 "New results on cyclic and ordered Ramsey numbers", Section 1
- Verified
- 07 Nov 2026
- Axioms
propext- Built on 3
- has_ordered_copyAn ordered graph G contains an ordered copy of an ordered graph H if there exists a strictly monotone map f from the vertex set of H to…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
Read back from the Lean
For every type α equipped with a linear order and every simple graph G on α, G has an ordered copy of G (that is, has_ordered_copy G G holds).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that an ordered graph G contains an ordered copy of itself, it suffices to find a strictly monotone vertex map that preserves edges. The proof provides the identity map as an explicit witness. Monotonicity follows from the fact that the identity is strictly monotone, and edge preservation is immediate since the identity fixes all vertices and edges.
The identity function is a strictly monotone, edge-preserving map from G to G.
Unfolding the definition of `has_ordered_copy`, we must provide a map on vertices that is strictly monotone with respect to the linear order and preserves adjacency in G. The proof instantiates this witness with the identity map `id`. Strict monotonicity is supplied by `strictMono_id`, and edge preservation holds tautologically (`fun _ _ h => h`) since `id u = u` and `id v = v`.
uses
strictMono_idhas_ordered_copy G G := ⟨id, strictMono_id, fun _ _ h => h⟩
strictMono_id- The identity function on a preorder is strictly monotone.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Every ordered graph contains an ordered copy of itself. -/theorem has_ordered_copy_self {α : Type*} [LinearOrder α] (G : SimpleGraph α) : has_ordered_copy G G := ⟨id, strictMono_id, fun _ _ h => h⟩