manyOneReducible_refl

Mathlib.Computability.Reduce

URI: https://scilib.ai/kg/mathlib#manyOneReducible_refl

English

Any predicate is many-one reducible to itself.

Русский

Любое свойство может быть сведено к самому себе через рекурсию.

LaTeX

$$$\forall {\alpha} [Primcodable \alpha],\forall p: \alpha \to Prop,\ p \le_0 p$$$

Lean4

@[refl]
theorem manyOneReducible_refl {α} [Primcodable α] (p : α → Prop) : p ≤₀ p :=
  ⟨id, Computable.id, by simp⟩

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

Научная платформа российской исследовательской школы.

Разделы

Аффилиация

Вычислительный центр им. А. А. Дороницына при ФИЦ «Информатика и Управление» РАН frccsc.ru