AFTD Auto-Formalizing Theoretical Domains

digraph_not_is_quasi_kernel_empty_of_nonempty

theoremverified

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

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.

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

    line 3

    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.

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

/-- 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)
See it in the graphDiscuss this resultChallenge it