109
правок
Изменения
м
→Доказательство
Упорядочим все слова по возрастанию длины. Разобьем всё <math>\Sigma^{*}</math> на множества
<math>A_i</math>, <math>\forall i,j : i<j , \forall \alpha \in A_i, \beta \in A_j |\alpha| < |\beta|</math>
так, что <math>SAT \cap \bigcup_{i=0}^{k} A_{2i}</math> отличается от <math>L(p_k)</math> элементом
из <math>\bigcup_{i=0}^{2k} A_i</math> и существует <math>\alpha \in \bigcup_{i=0}^{2k+1}A_i</math>,для которого выполняются условия <math>f(\alpha) \in \bigcup_{i=0}^{2k+1}A_i</math> и
<math>[\alpha \in SAT] \ne [f(\alpha) \in SAT \cap \bigcup_{i=0}^{k} A_{2i}]</math>.
