Доказательство окончено. Вспомогательные символы R и Q использованы для того, чтобы продукция, получаемая из продукции одной из систем описанным в доказательстве преобразованием

Вспомогательные символы R и Q использованы для того, чтобы продукция, получаемая из продукции одной из систем описанным в доказательстве преобразованием, могла применяться только к таким совокупностям слов, которые выводятся с помощью преобразованных продукций той же системы.

Если, например, при построении системы P_U в качестве множества продукций для P_Uвзять объединение множеств неизмененных продукций систем P₁ и P₂, то можно получить систему, в которой выводятся слова, не входящие в W₁ W₂.

В качестве примера рассмотрим системы P₁ и P₂ со следующими совокупностями продукций:

p_1,1: 1, p_1,2: ; (1)

p_2,1: 0, p_2,2: . (2)

Тогда с помощью продукций (1) системы P₁ можно выводить слова, составленные только из единиц, а при помощи множества (2) системы P₂ - слова, которые имеют конечное число нулей.

Однако продукции p_1,1, p_1,2, p_2,1, p_2,2, используемые совместно, позволяют выводить любые слова, состоящие из нулей и единиц.

Семейство классов слов, выводимых в системах Поста, не замкнуто относительно операции взятия дополнений таких множеств.

Это означает, что существует такая система P = (A,B,V,P), для которой множество A* \W_P не выводится ни в одной системе Поста. Доказательство этого факта будем приведено ниже после изучения связи множеств слов, выводимых в системах Поста и множества частично-рекурсивных функций.

Всякое множества W - таких слов в некотором основном алфавите A, чтоW и его дополнение до A* выводимы в некоторых системах Поста, является разрешимым.

Справедливость последнего свойства вытекает из следующей теоремы.