digraph_not_is_quasi_kernel_empty_of_nonempty
The empty set is not a quasi-kernel in any nonempty digraph.
Statement
theorem digraph_not_is_quasi_kernel_empty_of_nonempty {α : Type*} [Nonempty α] (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_is_quasi_kernel_empty_of_isEmptyIn an empty digraph, the empty set is a quasi-kernel.
The proof, explained
To show that the empty set cannot be a quasi-kernel in a nonempty digraph, we examine the quasi-kernel definition: a quasi-kernel must be independent and must 2-dominate every vertex of the digraph. While the empty set is vacuously independent, 2-dominating every vertex requires that for each vertex there is some vertex in the empty set reaching it in at most two steps. Because no vertex belongs to the empty set and the digraph contains at least one vertex, this domination property is false, so the empty set is not a quasi-kernel.
The empty set is not a quasi-kernel of D. automation
Unfolding the definition of a quasi-kernel (`digraph_is_quasi_kernel`), a set Q is a quasi-kernel if it is independent and 2-dominates the digraph. For Q = ∅, the independence condition holds vacuously, but the 2-domination condition requires that every vertex v in the digraph is reachable from some vertex u ∈ ∅ in at most two steps. Since no vertex belongs to the empty set, the existential condition ∃ u ∈ ∅, ... is false for every vertex. Because the vertex type α is nonempty, there is at least one vertex, so the universal statement fails and the conjunction is false. The simplifier (`simpa`) evaluates these empty-set memberships and quantifiers to reduce the negated false statement to True.
uses
digraph_is_quasi_kernel,digraph_is_quasi_kernel_empty_of_isEmpty¬ digraph_is_quasi_kernel D ∅ := by first | exact digraph_is_quasi_kernel_empty_of_isEmpty | (apply digraph_is_quasi_kernel_empty_of_isEmpty <;> assumption) | (apply digraph_is_quasi_kernel_empty_of_isEmpty <;> simp_all) | simpa using digraph_is_quasi_kernel_empty_of_isEmpty | (simp only [digraph_is_quasi_kernel] at *; first | exact digraph_is_quasi_kernel_empty_of_isEmpty | (apply digraph_is_quasi_kernel_empty_of_isEmpty <;> assumption) | (apply digraph_is_quasi_kernel_empty_of_isEmpty <;> simp_all) | simpa using digraph_is_quasi_kernel_empty_of_isEmpty)
digraph_is_quasi_kernel- A subset Q of vertices in a directed graph D is a quasi-kernel if it is independent (no two vertices in Q are adjacent) and 2-dominating (every vertex in the digraph is reachable from some vertex in Q in at most two steps).
digraph_is_quasi_kernel_empty_of_isEmpty- In an empty digraph (where the vertex type is empty), the empty set is a quasi-kernel.
- The proof uses a `first` block trying several tactic scripts. The successful branch first unfolds `digraph_is_quasi_kernel` and then calls `simpa using digraph_is_quasi_kernel_empty_of_isEmpty`. However, `digraph_is_quasi_kernel_empty_of_isEmpty` applies only when the vertex type is empty (`IsEmpty α`), whereas here it is nonempty (`Nonempty α`); the simplifier solves the goal entirely by simplifying the unfolded definition to `True` without relying on the supplied lemma.
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.
/-- In any nonempty digraph, the empty set cannot be a quasi-kernel since no vertex is reached. -/theorem digraph_not_is_quasi_kernel_empty_of_nonempty {α : Type*} [Nonempty α] (D : Digraph α) : ¬ digraph_is_quasi_kernel D ∅ := by first | exact digraph_is_quasi_kernel_empty_of_isEmpty | (apply digraph_is_quasi_kernel_empty_of_isEmpty <;> assumption) | (apply digraph_is_quasi_kernel_empty_of_isEmpty <;> simp_all) | simpa using digraph_is_quasi_kernel_empty_of_isEmpty | (simp only [digraph_is_quasi_kernel] at *; first | exact digraph_is_quasi_kernel_empty_of_isEmpty | (apply digraph_is_quasi_kernel_empty_of_isEmpty <;> assumption) | (apply digraph_is_quasi_kernel_empty_of_isEmpty <;> simp_all) | simpa using digraph_is_quasi_kernel_empty_of_isEmpty)