Доказательство

Проведем доказательство теоремы только для класса Т ₀. Для остальных классов такое доказательство может быть выполнено аналогично.

1. Уже известно, что Т ₀ - неполный класс.

2. Покажем, что в Т ₀ содержатся функции, не принадлежащие каждому из остальных классов.

Действительно, f (x ₁, x ₂) = x ₁+ x ₂ Î Т ₀, но f Ï Т ₁, f Ï S, f Ï M. Кроме того, h (x ₁, x ₂)= x ₁& x ₂ Т ₀, но h L. Поэтому, по критерию полноты в P ₂, добавление к Т ₀ любой функции g Т ₀ преобразует Т ₀ в полную систему, т.е. Т ₀ является предполным классом.

Доказательство окончено.

ТЕОРЕМА 4.11

В P ₂ существует ровно 5 предполных классов.