177
правок
Изменения
м
}}
{{Утверждение
|id=th2
|statement=
Отношение сводимости является отношением эквивалентности
|proof= Следует из рефлексивности, симметричности и транзитивности.
→Отношение эквивалентности
|definition=<tex>A</tex> '''<tex>\textbf m</tex>-эквивалентно''' (англ. ''many-one equivalent'', ''m-equivalent'') <tex>B</tex>, если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}A</tex>. Обозначение: <tex>A\equiv_{m}B</tex>.
}}
== Отношение эквивалентности Свойства ==
{{Утверждение
|about=рефлексивность
Если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}C</tex>, то <tex>A\leqslant_{m}C</tex>.
|proof=Если <tex>f:A\to B</tex> и <tex>g:B\to C</tex>, то <tex>m</tex>-сводящая функция <tex>h:A\to C</tex> выглядит так <tex>h(x) = g(f(x))</tex>.
}}
