logo
флеров

Представление о результатах Поста

Весьма глубокое изучение замкнутых классов в Р2 было осуществлено американским математиком Э. Постом в 1921 - 1941 годах. Им была описана структура всех замкнутых классов в Р2 . Сформулируем некоторые из важнейших результатов этих исследований.

Определение. Система функций { f1 , f2 , ... , fn , ...} из замкнутого класса К называется полной в К, если ее замыкание совпадает с К.

Иначе говоря, система полна в К, если каждая функция из К может быть выражена в виде формулы через функции данной системы.

Определение. Система функций { f1 , f2 , ... , f n , ...} из замкнутого класса К называется его базисом , если она полна в К, но всякая ее собственная подсистема не является полной в К.

Так, система f1 = x1x2 , f2 = 0 , f3 = 1, f4 = x1 +x2 является базисом в Р2 . Можно показать, что система функций {0, 1, x1x2 , x1  x2} является базисом для класса М монотонных функций.

Теорема 2.12. Каждый замкнутый класс из Р2 имеет конечный базис.

Теорема 2.13. Мощность множества замкнутых классов в Р2 счетная.

Хотя вторая из приведенных теорем логически вытекает из первой, однако в доказательствах Поста сначала устанавливается второй факт, а затем - первый.

  1.