listFilter_listRange — Mathlib

English

The negation of a primitive recursive relation is primitive recursive.

Русский

Нейтрация примитивно-рекурсивного отношения также является примитивно-рекурсивной.

LaTeX

$$$\mathrm{PR}( \neg R ) \quad\text{if } \mathrm{PR}(R).$$$

Lean4

/-- A helper lemma for proofs about bounded quantifiers on decidable relations. -/
theorem listFilter_listRange {R : ℕ → ℕ → Prop} (s : ℕ) [DecidableRel R] (hf : PrimrecRel R) :
    Primrec fun n ↦ (range s).filter (fun y ↦ R y n) :=
  by
  simp only [← filterMap_eq_filter]
  refine listFilterMap (.const (range s)) ?_
  refine ite (Primrec.eq.comp ?_ (const true)) (option_some_iff.mpr snd) (.const Option.none)
  exact hf.decide.comp snd fst

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