Определение слова «Сколема Функция»

Математическая энциклопедия:

Функция Скулема, сколемовская функция, — понятие логики предикатов. Если А( х 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. В. Н. Гришин.

Смотреть другие определения →