AFTD Auto-Formalizing Theoretical Domains

digraph_is_oriented_bot

theoremverified

The empty digraph (⊥ : Digraph V) on any vertex type V is oriented, satisfying digraph_is_oriented (⊥ : Digraph V).

Statement

theorem digraph_is_oriented_bot (V : Type*) : digraph_is_oriented (⊥ : Digraph V)
Source
folklore
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • digraph_is_orientedA digraph G : Digraph V on vertex type V is oriented (digraph_is_oriented G) if for all vertices u v : V, G.Adj u v implies ¬ G.Adj v u.

Read back from the Lean

For any type V, the bottom directed graph ⊥ : Digraph V satisfies digraph_is_oriented, meaning that for all vertices u, v : V, if u is adjacent to v in ⊥, then v is not adjacent to u in ⊥.

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

A directed graph is oriented if no pair of vertices has edges in both directions. In the empty graph ⊥, there are no edges between any vertices, so the condition holds vacuously.

  1. The empty digraph satisfies the orientedness condition vacuously. automation

    Unfolding the definition of an oriented digraph (`digraph_is_oriented`), we must show that for any vertices $u$ and $v$, if there is a directed edge from $u$ to $v$ in the empty graph $\bot$, then there is no directed edge from $v$ to $u$. Since the empty graph has no edges, the antecedent is false, so the implication holds vacuously; the simplifier discharges this by replacing the empty adjacency with false and simplifying the implication.

    line 3

    uses digraph_is_oriented

      simp [digraph_is_oriented]
digraph_is_oriented
A directed graph is oriented if no pair of vertices has edges in both directions: for all vertices u and v, if there is an edge from u to v, then there is no edge from v to u.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The empty digraph is oriented. -/theorem digraph_is_oriented_bot (V : Type*) : digraph_is_oriented (⊥ : Digraph V) := by  simp [digraph_is_oriented]
See it in the graphDiscuss this resultChallenge it