AFTD Auto-Formalizing Theoretical Domains

is_k_connected_set_empty

theoremverifiedformalization

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)$.

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

    line 3

      intro A _
  2. 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.

    line 4

      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

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