Theorems · Theorem · logic and foundations

Primrec.of_graph

∀ {α : Type u_1} [inst : Primcodable α] {f : α → ℕ},
  Primrec.PrimrecBounded f → (PrimrecRel fun a b => f a = b) → Primrec f

To show a function f : α → ℕ is primitive recursive, it is enough to show that the function is bounded by a primitive recursive function and that its graph is primitive recursive

Defined in

Mathlib.Computability.Primrec.Basic

Cited by

1 results in Mathlib

Foundations

Depth 84 from the axioms · uses propext, Classical.choice, Quot.sound

Assumes

Primcodable