Рассмотрим строку (0 ^ p) 1 (0 ^ p) 1 (0 ^ p-1) 10 длиной 3p + 3. Это строка в языке, поскольку при выборе | x | = | y | = | z | означает, что x = (0 ^ p) 1, y = (0 ^ p) 1 и z = (0 ^ p-1) 10, а 1 + 1 = 10. Теперь лемма прокачки говорит, что это можно записать как где:
- | RS | <= p </li>
- | s | > 0
- r (s ^ k) t на языке для всех натуральных чисел k
Обратите внимание, что в нашем случае s должно полностью состоять из нуля от нашего компонента x. Предположим, что мы выбрали k = 0. Рассмотрим несколько случаев:
- | к.т. | не делится поровну на 3. В этом случае строка не может быть на нашем языке, так как условие | x | = | y | = | z | не может быть удовлетворен.
- если | rt | делится поровну на 3, рассмотрим наши новые x, y и z: мы удалили некоторое число 3m из ведущих 0. Это означает, что | x | = | y | = | z | = р + 1 - м. Первоначально 1 в конце нашего старого x будет смещен влево на (m - 1) позиций в новой строке; 1 в конце y первоначально будет смещен влево на (m - 2) позиций в новой строке; и 1 в конце z останется в предпоследней позиции в z.
- если m = 1, то y больше не будет содержать 1, поэтому x + y + z не может быть удовлетворено
- если m> 1, то x будет представлять число, большее или равное 10, а y будет представлять собой положительное число. Однако сумма числа, большего или равного 10, и положительного (ненулевого) числа не может быть равна 10. Таким образом, x + y + z здесь также не может быть выполнено.
Следовательно, нет выбора для m = | s | такой, что выбор k = 0 дает нам r (s ^ k) t в языке. Это противоречие, и поэтому наше подразумеваемое предположение о правильности языка должно быть ложным.