digraph_is_quasi_kernel_empty_of_isEmpty
In an empty digraph, the empty set is a quasi-kernel.
Statement
theorem digraph_is_quasi_kernel_empty_of_isEmpty {α : Type*} [IsEmpty α] (D : Digraph α) : digraph_is_quasi_kernel D ∅
- Source
- step towards digraph_small_quasi_kernel_exists
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- digraph_is_quasi_kernelA subset Q of vertices in a digraph D is a quasi-kernel if Q is independent (no arcs between distinct vertices of Q) and 2-dominating…
- digraph_reverse_reverseReversing a digraph twice yields the original digraph.
- Used by 1
- digraph_not_is_quasi_kernel_empty_of_nonemptyThe empty set is not a quasi-kernel in any nonempty digraph.
The proof, explained
In an empty digraph (where the vertex type is empty), the empty set of vertices is vacuously a quasi-kernel. Unfolding the definition gives an independence condition on vertices in ∅ and a reachability condition for all vertices in the graph, both of which are vacuously true because there are no vertices. The simplifier recognizes these vacuous truths and closes the goal.
The empty set ∅ is a quasi-kernel of any digraph D on an empty vertex type. automation
Unfolding the definition of a quasi-kernel (`digraph_is_quasi_kernel`) requires verifying two conditions: independence of the subset, and that every vertex in the graph is reachable from the subset in at most two steps. Because the subset is ∅, the independence condition is vacuously satisfied. Because the vertex type α is empty (`IsEmpty α`), the reachability condition for all vertices is also vacuously satisfied. The automated simplifier `simpa` reduces both conditions to true.
uses
digraph_is_quasi_kernel,digraph_reverse_reversedigraph_is_quasi_kernel D ∅ := by first | exact digraph_reverse_reverse | (apply digraph_reverse_reverse <;> assumption) | (apply digraph_reverse_reverse <;> simp_all) | simpa using digraph_reverse_reverse | (simp only [digraph_is_quasi_kernel] at *; first | exact digraph_reverse_reverse | (apply digraph_reverse_reverse <;> assumption) | (apply digraph_reverse_reverse <;> simp_all) | simpa using digraph_reverse_reverse)
digraph_is_quasi_kernel- a subset Q of vertices in a digraph is a quasi-kernel if it is independent (no two vertices in Q are adjacent) and every vertex in the graph is reachable from some vertex in Q in at most two steps
digraph_reverse_reverse- reversing all edges of a directed graph twice yields the original digraph
- The proof script was produced by an automated search that repeatedly tries tactics mentioning `digraph_reverse_reverse`. That lemma is completely irrelevant to the mathematical statement; `simpa` closes the goal solely by simplifying the vacuous quantifiers over the empty set and the empty vertex type α.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The empty set of vertices is a quasi-kernel in any empty digraph. -/theorem digraph_is_quasi_kernel_empty_of_isEmpty {α : Type*} [IsEmpty α] (D : Digraph α) : digraph_is_quasi_kernel D ∅ := by first | exact digraph_reverse_reverse | (apply digraph_reverse_reverse <;> assumption) | (apply digraph_reverse_reverse <;> simp_all) | simpa using digraph_reverse_reverse | (simp only [digraph_is_quasi_kernel] at *; first | exact digraph_reverse_reverse | (apply digraph_reverse_reverse <;> assumption) | (apply digraph_reverse_reverse <;> simp_all) | simpa using digraph_reverse_reverse)