AFTD Auto-Formalizing Theoretical Domains

Cslib.HasFresh.ofNatEmbed

defimported Lean

Construct a fresh element from an embedding of ℕ using Nat.find.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
universe u in
open Finset in
@[implicit_reducible]
def Cslib.HasFresh.ofNatEmbed {α : Type u} [DecidableEq α] (e : ℕ ↪ α) : HasFresh α
Defined in
CSLib, `Cslib.HasFresh.ofNatEmbed`
Lean proof
By Fabrizio Montesi, Kenny Lau, from github.com/leanprover/cslib at 3951377e5a3f (Copyright (c) 2025 Fabrizio Montesi. 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
none listed
Built on 3
  • Cslib.HasFresh.to_infiniteHasFresh α implies a computably infinite type.
  • Cslib.HasFreshA type α has a computable fresh function if it is always possible, for any finite set of α, to compute a fresh element not in the set.
  • Cslib.instHasFreshOfInfiniteAll infinite types have an associated (at least noncomputable) fresh function. This, in conjunction with HasFresh.to_infinite,…

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
universe u in
open Finset in
/-- Construct a fresh element from an embedding of `ℕ` using `Nat.find`. -/
@[implicit_reducible]
def Cslib.HasFresh.ofNatEmbed {α : Type u} [DecidableEq α] (e : ℕ ↪ α) : HasFresh α where
  fresh s := e (Nat.find (p := fun n ↦ e n ∉ s) ⟨(s.preimage e e.2.injOn).max.succ,
    fun h ↦ not_lt_of_ge (le_max <| mem_preimage.2 h) (WithBot.lt_succ _)⟩)
  fresh_notMem s := Nat.find_spec (p := fun n ↦ e n ∉ s) _
See it in the graphDiscuss this resultChallenge it