AFTD Auto-Formalizing Theoretical Domains

is_mutual_visibility_set_empty

theoremverified

The empty set of vertices in any simple graph G is a mutual-visibility set.

Statement

theorem is_mutual_visibility_set_empty {V : Type*} (G : SimpleGraph V) :
    is_mutual_visibility_set G ∅
Source
arXiv:2611.09513, Section 1
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

Read back from the Lean

For any type V and any simple graph G on V, the empty set ∅ is a mutual visibility set in G. That is, for all vertices u, v : V, if u ∈ ∅, v ∈ ∅, and u ≠ v, then there exists a walk p from u to v in G whose length is G.dist u v and such that every vertex w in the support of p that is in ∅ is equal to u or v.

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

The empty set of vertices in any simple graph is a mutual-visibility set because the condition is vacuously satisfied. By definition, a set of vertices is a mutual-visibility set if every pair of distinct vertices in it can see each other via a shortest path containing no other vertices from the set. Since the empty set contains no vertices, there are no pairs to consider, and the implication holds vacuously.

  1. The empty set $\emptyset$ is a mutual-visibility set in $G$.

    Unfolding the definition of `is_mutual_visibility_set` expresses the goal as a universal quantification over vertices $u, v \in V$: if $u \in \emptyset$, $v \in \emptyset$, and $u \ne v$, then there exists a distance-achieving walk whose internal vertices avoid $\emptyset$. Because no element belongs to the empty set, the hypothesis $u \in \emptyset$ simplifies to `False`, making the conditional statement vacuously true. The automated proof ladder tries several tactics and succeeds on the branch that unfolds the definition and simplifies this vacuous implication.

    line 3

    uses is_mutual_visibility_set, simple_graph_power_one

        is_mutual_visibility_set G ∅ := by first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one | (simp only [is_mutual_visibility_set] at *; first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one)
is_mutual_visibility_set
A subset $S$ of vertices in a simple graph $G$ is a mutual-visibility set if for every pair of distinct vertices $u, v \in S$, there is a shortest path in $G$ between $u$ and $v$ whose internal vertices contain no elements of $S$.
simple_graph_power_one
The first power of a simple graph $G$ is identical to $G$.

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 set is a mutual-visibility set. -/theorem is_mutual_visibility_set_empty {V : Type*} (G : SimpleGraph V) :    is_mutual_visibility_set G ∅ := by first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one | (simp only [is_mutual_visibility_set] at *; first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one)
See it in the graphDiscuss this resultChallenge it