Изменения

|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>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>.

}}