AFTD Auto-Formalizing Theoretical Domains

op_979_csym_max_nullity_empty_graph

theoremverifiedformalization

For the edgeless graph (the empty graph bot) on a finite vertex set V, the combinatorially symmetric maximum nullity equals the number of vertices |V|.

Statement

theorem op_979_csym_max_nullity_empty_graph
    {V : Type*} [Fintype V] [DecidableEq V] :
    simple_graph_csym_max_nullity (⊥ : SimpleGraph V) = Fintype.card V
Formalizes
arXiv:2611.01102 Sec. 6, Example 6.2
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • simple_graph_csym_max_nullityThe combinatorially symmetric maximum nullity N(G) of a finite simple graph G is the supremum of the nullities of all real matrices A…
  • is_csym_matrixA real matrix A indexed by V is combinatorially symmetric and associated with the simple graph G if for all i, j in V, A i j is nonzero if…
Used by 1

Read back from the Lean

For any type V with finite cardinality and decidable equality, the maximum combinatorially symmetric nullity (simple_graph_csym_max_nullity) of the empty graph (⊥ : SimpleGraph V) equals Fintype.card 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 combinatorially symmetric maximum nullity of the edgeless graph ⊥ is defined as the supremum of the nullities of all matrices whose non-zero entries match the adjacency of ⊥. The zero matrix satisfies this condition vacuously and has nullity equal to |V|, showing that |V| is attained. Since the kernel of any matrix on V is a subspace of the |V|-dimensional space V → ℝ, no matrix can have nullity greater than |V|, so |V| is also an upper bound, making the supremum |V|.

  1. Let S be the set of dimensions of kernels of real matrices that are combinatorially symmetric for the edgeless graph ⊥; the goal is to show sup S = |V|.

    Unfolding the definition of simple_graph_csym_max_nullity, the maximum nullity is defined as the supremum of the set S of nullities of all combinatorially symmetric matrices for ⊥.

    lines 5–8

      classical
      unfold simple_graph_csym_max_nullity
      set S : Set ℕ := { k : ℕ | ∃ A : Matrix V V ℝ,
        is_csym_matrix (⊥ : SimpleGraph V) A ∧ Module.finrank ℝ A.mulVecLin.ker = k } with hSdef
  2. |V| is an element of S, witnessed by the zero matrix.

    The zero matrix is combinatorially symmetric for the edgeless graph ⊥ because it has no non-zero entries, vacuously matching the absence of edges. The linear map induced by the zero matrix is the zero map (Matrix.mulVecLin_zero), whose kernel is the whole space V → ℝ (LinearMap.ker_zero, finrank_top). The dimension of V → ℝ over ℝ is |V| (Module.finrank_fintype_fun_eq_card), so the nullity of the zero matrix is |V|.

    lines 9–13

    uses Matrix.mulVecLin_zero, LinearMap.ker_zero, finrank_top, Module.finrank_fintype_fun_eq_card

      have hmem : Fintype.card V ∈ S := by
        refine ⟨0, ?_, ?_⟩
        · exact ⟨fun i j => by simp, fun i j _ => by simp⟩
        · rw [Matrix.mulVecLin_zero, LinearMap.ker_zero, finrank_top]
          exact Module.finrank_fintype_fun_eq_card ℝ
  3. Every element b ∈ S satisfies b ≤ |V|.

    Any b ∈ S is the nullity dim(ker A) of some matrix A. Because ker A is a linear subspace of V → ℝ, its dimension is bounded by dim(V → ℝ) (Submodule.finrank_le), which equals |V| (Module.finrank_fintype_fun_eq_card).

    lines 14–19

    uses Submodule.finrank_le, Module.finrank_fintype_fun_eq_card

      have hle : ∀ b ∈ S, b ≤ Fintype.card V := by
        rintro b ⟨A, -, hb⟩
        rw [← hb]
        calc Module.finrank ℝ A.mulVecLin.ker
            ≤ Module.finrank ℝ (V → ℝ) := Submodule.finrank_le _
          _ = Fintype.card V := Module.finrank_fintype_fun_eq_card ℝ
  4. The supremum of S is |V|.

    Since every element of S is at most |V|, S is bounded above. Because S is non-empty (containing |V|) and bounded above by |V|, sup S ≤ |V| (csSup_le). Conversely, since |V| ∈ S and S is bounded above, |V| ≤ sup S (le_csSup). By antisymmetry (le_antisymm), sup S = |V|.

    lines 20–21

    uses le_antisymm, csSup_le, le_csSup

      have hbdd : BddAbove S := ⟨Fintype.card V, hle⟩
      exact le_antisymm (csSup_le ⟨_, hmem⟩ hle) (le_csSup hbdd hmem)
Matrix.mulVecLin_zero
The linear map associated with the zero matrix is the zero linear map.
LinearMap.ker_zero
The kernel of the zero linear map is the top submodule (the entire domain).
finrank_top
The dimension of the top submodule of a module equals the dimension of the whole module.
Module.finrank_fintype_fun_eq_card
The dimension of the function space η → R over R equals the cardinality of the finite index set η.
Submodule.finrank_le
The dimension of any submodule is at most the dimension of the ambient module.
csSup_le
In a conditionally complete lattice, the supremum of a non-empty set is at most any upper bound of that set.
le_csSup
In a conditionally complete lattice, every element of a set bounded above is at most the supremum of the set.
le_antisymm
If a ≤ b and b ≤ a in a partial order, then a = b.

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

/-- For the edgeless graph on a finite vertex set V, N(⊥) = |V|. -/theorem op_979_csym_max_nullity_empty_graph    {V : Type*} [Fintype V] [DecidableEq V] :    simple_graph_csym_max_nullity (⊥ : SimpleGraph V) = Fintype.card V := by  classical  unfold simple_graph_csym_max_nullity  set S : Set ℕ := { k : ℕ | ∃ A : Matrix V V ℝ,    is_csym_matrix (⊥ : SimpleGraph V) A ∧ Module.finrank ℝ A.mulVecLin.ker = k } with hSdef  have hmem : Fintype.card V ∈ S := by    refine ⟨0, ?_, ?_⟩    · exact ⟨fun i j => by simp, fun i j _ => by simp⟩    · rw [Matrix.mulVecLin_zero, LinearMap.ker_zero, finrank_top]      exact Module.finrank_fintype_fun_eq_card ℝ  have hle : ∀ b ∈ S, b ≤ Fintype.card V := by    rintro b ⟨A, -, hb⟩    rw [← hb]    calc Module.finrank ℝ A.mulVecLin.ker        ≤ Module.finrank ℝ (V → ℝ) := Submodule.finrank_le _      _ = Fintype.card V := Module.finrank_fintype_fun_eq_card ℝ  have hbdd : BddAbove S := ⟨Fintype.card V, hle⟩  exact le_antisymm (csSup_le ⟨_, hmem⟩ hle) (le_csSup hbdd hmem)
See it in the graphDiscuss this resultChallenge it