computable_of_oneOneReducible

Mathlib.Computability.Reduce

URI: https://scilib.ai/kg/mathlib#ComputablePred.computable_of_oneOneReducible

← MathLib Explorer

English

If p ≤₁ q, then computability of q implies computability of p.

Русский

Если p ≤₁ q, то вычислимость q переносится на p.

LaTeX

$$$p\le_1 q\;\Rightarrow\; (ComputablePred\,q)\;\Rightarrow\; ComputablePred\,p$$$

Lean4

theorem computable_of_oneOneReducible {p : α → Prop} {q : β → Prop} (h : p ≤₁ q) :
    ComputablePred q → ComputablePred p :=
  computable_of_manyOneReducible h.to_many_one

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

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

Разделы

MathLib Explorer
Graph RAG
Лаборатория
Блог
О проекте
Команда

Аффилиация

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