comp — Mathlib

English

If f: β → σ and g: α → β are primitive recursive, then the composite a ↦ f(g(a)) is primitive recursive.

Русский

Если f: β → σ и g: α → β примрrec, то композиция a ↦ f(g(a)) примрrec.

LaTeX

$$$$ \\forall f:\\beta\\to\\sigma,\\; \\forall g:\\alpha\\to\\beta,\\ \\mathrm{Primrec}(f) \\to \\mathrm{Primrec}(g) \\to \\mathrm{Primrec}(\\lambda a. f(g(a))) $$$$

Lean4

theorem comp {f : β → σ} {g : α → β} (hf : Primrec f) (hg : Primrec g) : Primrec fun a => f (g a) :=
  ((casesOn1 0 (.comp hf (pred.comp hg))).comp (Primcodable.prim α)).of_eq fun n => by
    cases @decode α _ n <;> simp [encodek]

Похожие утверждения