Сколема Функция

функция Скулема, сколемовская функция, - понятие логики предикатов. Если А( х 1 ,. , х n, у).предикатная формула от индивидных переменных х 1,. , xn, у, области изменения к-рых суть множества Х 1, . , Х п, Y соответственно, то функция f . Х 1 Х. .X X Х пYназ. Функцией Сколема, или разрешающей функцией, для формулы ( х 1, . , х п, у), если для всех имеет место импликация С. Ф. Были введены Т. Сколемом (Т. Skolem) в 20-х гг. 20 в. Понятие С. Ф. Широко применяется в работах по математич. Логике. Объясняется это тем, что с помощью С. Ф. Можно исключить чередование кванторов " и $. Так, напр., для всякой формулы Аязыка узкого исчисления предикатов можно построить формулу вида $ x1 ,. , х п" y1 ,..., у т С, называемую сколемовской нормальной формой формулы А, где Сне содержит кванторов, но содержит новые (т.

Е. Не встречающиеся в А).предикатные символы, и такую, что в исчислении предикатов формула Авыводима тогда и только тогда, когда выводима ее сколемовская нормальная форма. Идея С. Ф. Используется в таких фундаментальных теоремах математич. Логики, как теорема Эрбрана, сводящая вопрос о выводимости в исчислении предикатов предикатной формулы к исследованию вопроса о выводимости в исчислении высказываний бесконечной последовательности пропозициональных формул, теорема Лёвенхейма - Сколема и др. В тех случаях, когда предметная область, на к-рой рассматриваются формулы, обладает дополнительной структурой, можно потребовать от С. Ф. Определенной связи с этой структурой. Напр., если рассматриваемая предметная область принадлежит иерархии конструктивных по Гёделю множеств, то можно потребовать, чтобы С.

Ф. Также принадлежали определенному уровню в конструктивной иерархии. Существование С. Ф., удовлетворяющих дополнительным свойствам, не всегда гарантировано, но эффект от их использования в случае, когда они существуют, оказывается более значительным. В качестве примера можно указать на результат Йенсена о выводимости гипотезы Чэна о двух кардиналах (см. [6]) и отрицания Суслипа гипотезы (см. [5]) из аксиомы конструктивности Гёделя. Теорема Новикова - Кондо об униформизации -отношений из дескриптивной теории множеств утверждает существование определенного рода С. Ф. (см. [2], с. 280). Лит.:[1] Новиков П. С., Элементы математической логики, 2 изд., М., 1973. [2] Шенфилд Дж. Р., Математическая логика, пер. С англ., М., 1975.

[3] Кейслер Г., Чэн Ч. Ч., Теория моделей, пер. С англ., М., 1977. [4] Ершов Ю. Л. Палютин Е. А., Математическая логика М. 1979. [5] Handbook of mathematical logic, Amst., 1977. [6] Dev1in K. J.,.Aspects of constnietibility, В. - [а. О.], 1973. В. Н. Гришин.