алгоритм построения предполных классов в $P_{k}$

[jorik]

Здравствуйте. Не могли бы Вы подсказать, где можно посмотреть алгоритм построения предполных классов в $P_{k}$, или описать простейший вариант такого алгоритма? В учебнике Яблонского я обнаружил лишь такие полезные в этой связи соображения, используемые при доказательстве теоремы Кузнецова:
1. Выбираются все собственные подмножества функций из $P_{k}$, зависящих от двух переменных $x}$ и $y$, содержащие $x$ и $y$.
2. С помощью алгоритма распознавания полноты выбираются те подмножества $A_{i}$, для которых $[A_{i}]_{xy}=A$.
3. Рассматриваются классы функций, сохраняющих каждое из полученных на втором этапе множеств функций. Эти классы $M_{i}$ оказываются замкнутыми и $(M_{i})_{xy}=A_{i}$.
4. Из полученных классов отсеиваем те, которые содержатся в каком-либо из остальных.
Вот, собственно, вопрос в том, как осуществить последнюю операцию?

[Xaositect]

У Марченкова в книге "Функциональные системы с операцией суперпозиции" в первой главе можете посмотреть полное описание всех предполных классов в $P_k$ как классов сохранения нескольких семейств предикатов (теорема Розенберга).

Что касается Вашего вопроса - мы имеем набор классов $M_i$, сохраняющих множества $(M_i)_{xy}$. Что значит, что $M_i\subset M_j$? Это значит, что любая $f$, сохраняющая $(M_i)_{xy}$, сохраняет также и $(M_j)_{xy}$. Соответственно $M_i\not\subset M_j$ тогда и только тогда, когда сущетсует $f$, сохраняющая $(M_i)_{xy}$, но не сохр. $(M_j)_{xy}$, т.е. существует набор $g_1,\dots g_n\in (M_j)_{xy}$: $f(g_1(x,y),\dots, g_n(x,y))\notin (M_j)_{xy}$. Если у $f$ переменных больше, чем функций в $(M_j)_{xy}$, то некоторые из $g_i$ в этом тождестве совпадают, и, отождествив соответствующие аргументы ф-и $f$, мы получим ф-ю $f'$, которая тоже обладает таким свойством.
То есть, для того, чтобы проверить $M_i\subset M_j$, необходимо проверить, что все ф-и из $M_i$, у которых переменных не больше, чем функций в $ (M_j)_{xy}$, сохраняют $(M_j)_{xy}$.

[jorik]

Да, большое спасибо. Действительно очень просто... Книгу тоже посмотрю.