is_k_connected_set_empty
In every matroid $M$, the empty set is $k$-connected for all $k$.
Statement
theorem is_k_connected_set_empty {α : Type*} (M : Matroid α) (k : ℕ) : IsKConnectedSet M k ∅
- Formalizes
- arXiv:2610.29979, Section 2
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- IsKConnectedSetA set $Z$ in a matroid $M$ is $k$-connected for an integer $k \ge 2$ if for every subset $A \subseteq E(M)$, the connectivity function…
- matroid_connectivityThe connectivity function $\lambda_M(X)$ of a subset $X$ of the ground set of a matroid $M$ is defined as…
Read back from the Lean
For every type α, every matroid M on α, and every natural number k, the empty set ∅ is a k-connected set in M (IsKConnectedSet M k ∅).
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
By definition, a set $Z$ is $k$-connected in a matroid $M$ if $\min(\min(|Z \cap A|, |Z \setminus A|), k - 1) \le \lambda_M(A)$ for every subset $A$ of the ground set $E(M)$. When $Z = \emptyset$, both $\emptyset \cap A$ and $\emptyset \setminus A$ are empty, so their cardinalities are $0$. The left-hand side reduces to $0$, which is trivially bounded by the non-negative connectivity $\lambda_M(A)$.
Let $A \subseteq E(M)$ be an arbitrary subset of the ground set of $M$.
By definition, a set $Z$ is $k$-connected in $M$ if every subset $A$ of the ground set $E(M)$ satisfies $\min(\min(|Z \cap A|, |Z \setminus A|), k - 1) \le \lambda_M(A)$, where $\lambda_M(A)$ is the matroid connectivity of $A$. We introduce an arbitrary set $A$ together with the assumption $A \subseteq E(M)$.
intro A _The connectivity inequality $\min(\min(|\emptyset \cap A|, |\emptyset \setminus A|), k - 1) \le \lambda_M(A)$ holds. automation
Both $\emptyset \cap A$ and $\emptyset \setminus A$ simplify to the empty set, which has cardinality $0$. The expression $\min(0, k - 1)$ in $\mathbb{N}$ evaluates to $0$, and $0 \le \lambda_M(A)$ is trivially true since the connectivity is a natural number. The simplifier automatically performs these set-theoretic and arithmetic simplifications to close the goal.
simp
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 is k-connected in every matroid for all k. -/theorem is_k_connected_set_empty {α : Type*} (M : Matroid α) (k : ℕ) : IsKConnectedSet M k ∅ := by intro A _ simp