AFTD Auto-Formalizing Theoretical Domains

has_ordered_copy_self

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

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.

  1. 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`.

    line 3

    uses strictMono_id

        has_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⟩
See it in the graphDiscuss this resultChallenge it