AFTD Auto-Formalizing Theoretical Domains

Cslib.goodSelection_exists

theoremverifiedformalizationimported Lean

Given any infinite vertex set, a good selection from it always exists.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Function Set in
variable {Vertex Color : Type*} [Finite Color] (color : Finset Vertex → Color) in
lemma Cslib.goodSelection_exists (ivs : InfVSet Vertex) :
    ∃ S : Selection Vertex Color, GoodSelection color ivs S
Formalizes
CSLib, `Cslib.goodSelection_exists`
Lean proof
By Ching-Tsun Chou, from github.com/leanprover/cslib at 3951377e5a3f (Copyright (c) 2026 Ching-Tsun Chou. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 1
  • Cslib.goodSelection_seqStarting from the infinite set of all vertices, inductively make an infinite sequence of good selections.

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Function Set invariable {Vertex Color : Type*} [Finite Color] (color : Finset Vertex → Color) in/-- Given any infinite vertex set, a good selection from it always exists. -/lemma Cslib.goodSelection_exists (ivs : InfVSet Vertex) :    ∃ S : Selection Vertex Color, GoodSelection color ivs S := by  classical  obtain ⟨v, h_v⟩ := Set.Infinite.nonempty ivs.inf  let f u := color {v, u}  obtain ⟨c, vs, h_inf, h_vs, h_col⟩ := infinite_pigeonhole_principle f <|    Set.Infinite.sdiff ivs.inf (finite_singleton v)  simp only [subset_sdiff] at h_vs  let ivs' := InfVSet.mk vs h_inf  use {vs := ivs', v := v, c := c}  grind [GoodSelection]
See it in the graphDiscuss this resultChallenge it