exists_lt — Mathlib

English

If f is primitive recursive and ∀ a, p(f(a)) holds, then a ↦ ⟨f(a), h(a)⟩ is primitive recursive.

Русский

Если f примитивно-рекурсивна и для всех a верно p(f(a)), то a ↦ ⟨f(a), h(a)⟩ примитивно-рекурсивна.

LaTeX

$$$\mathrm{PR}(f) \rightarrow \mathrm{PR}\big(a \mapsto \langle f(a), h(a)\rangle\big).$$$

Lean4

/-- If `R a b` is decidable, then for any fixed `n` and `y`, `g n y ↔ ∃ x < n, R x y` is a
primitive recursive relation. -/
theorem exists_lt (hf : PrimrecRel R) : PrimrecRel fun n y ↦ ∃ x < n, R x y :=
  (hf.exists_mem_list.comp (list_range.comp fst) snd).of_eq (by simp)

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