65
правок
Изменения
Новая страница: «{{Определение |definition=Множество натуральных чисел <tex>A</tex> '''m-сводится''' ко множеству натура...»
{{Определение
|definition=Множество натуральных чисел <tex>A</tex> '''m-сводится''' ко множеству натуральных чисел <tex>B</tex>, если существует всюду определённая вычислимая функция <tex>f:\mathbb{N}\rightarrow\mathbb{N}</tex> со свойством <tex>\forall{x}:x\in A\Leftrightarrow f(x)\in B</tex>. Обозначение: <tex>A\le_{m}B</tex>.
}}
{{Определение
|definition=<tex>A</tex> '''m-эквивалентно''' <tex>B</tex>, если <tex>A\le_{m}B</tex> и <tex>B\le_{m}A</tex>.
}}
== Свойства ==
# <tex>A\le_{m}A</tex>.
# Если <tex>A\le_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
# Если <tex>A\le_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
# Если <tex>A\le_{m}B</tex> и <tex>B\le_{m}C</tex>, то <tex>A\le_{m}C</tex>.
# Если <tex>A\le_{m}B</tex>, то <tex>\overline{A}\le_{m}\overline{B}</tex>.
{{Теорема
|statement=
Если <tex>A\le_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
|proof=
Если <tex>B</tex> неразрешимо, то для любого разрешимого <tex>X: X\ne B</tex>. Пусть мы хотим найти точку, в которой <tex>X</tex> отличается от <tex>B</tex>. Рассмотрим <tex>f</tex> которая m-сводит <tex>A</tex> к <tex>B</tex>. <tex>f^{-1}(X)</tex> будет разрешимым, как прообраз разрешимого множества. Поэтому можно найти точку <tex>x</tex>, в которой <tex>X</tex> отличается от <tex>A</tex>. Тогда <tex>B</tex> будет отличаться от <tex>X</tex> в точке <tex>f(x)</tex>.
}}
|definition=Множество натуральных чисел <tex>A</tex> '''m-сводится''' ко множеству натуральных чисел <tex>B</tex>, если существует всюду определённая вычислимая функция <tex>f:\mathbb{N}\rightarrow\mathbb{N}</tex> со свойством <tex>\forall{x}:x\in A\Leftrightarrow f(x)\in B</tex>. Обозначение: <tex>A\le_{m}B</tex>.
}}
{{Определение
|definition=<tex>A</tex> '''m-эквивалентно''' <tex>B</tex>, если <tex>A\le_{m}B</tex> и <tex>B\le_{m}A</tex>.
}}
== Свойства ==
# <tex>A\le_{m}A</tex>.
# Если <tex>A\le_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
# Если <tex>A\le_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
# Если <tex>A\le_{m}B</tex> и <tex>B\le_{m}C</tex>, то <tex>A\le_{m}C</tex>.
# Если <tex>A\le_{m}B</tex>, то <tex>\overline{A}\le_{m}\overline{B}</tex>.
{{Теорема
|statement=
Если <tex>A\le_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
|proof=
Если <tex>B</tex> неразрешимо, то для любого разрешимого <tex>X: X\ne B</tex>. Пусть мы хотим найти точку, в которой <tex>X</tex> отличается от <tex>B</tex>. Рассмотрим <tex>f</tex> которая m-сводит <tex>A</tex> к <tex>B</tex>. <tex>f^{-1}(X)</tex> будет разрешимым, как прообраз разрешимого множества. Поэтому можно найти точку <tex>x</tex>, в которой <tex>X</tex> отличается от <tex>A</tex>. Тогда <tex>B</tex> будет отличаться от <tex>X</tex> в точке <tex>f(x)</tex>.
}}
