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

функция Скулема, сколемовская функция, - понятие логики предикатов. Если А(х 1,..., х n, у).предикатная формула от индивидных переменных х 1,..., xn, у, области изменения к-рых суть множества Х 1,..., Х п, Y соответственно, то функция f: Х 1 Х...X X Х п [img: http://localhost:8080/file/041914-9.jpg] Yназ. функцией Сколема, или разрешающей функцией, для формулы [img: http://localhost:8080/file/041914-10.jpg] (х 1,..., х п, у), если для всех [img: http://localhost:8080/file/041914-11.jpg] имеет место импликация [img: http://localhost:8080/file/041914-12.jpg] С. ф. были введены Т. Сколемом (Т. Skolem) в 20-х гг. 20 в. Понятие С. ф. широко применяется в работах по математич. логике. Объясняется это тем, что с помощью С. ф. можно исключить чередование кванторов " и $. Так, напр., для всякой формулы Аязыка узкого исчисления предикатов можно построить формулу вида $ x1,..., х п" y1,..., у т С, называемую сколемовской нормальной формой формулы А, где Сне содержит кванторов, но содержит новые (т. е. не встречающиеся в А).предикатные символы, и такую, что в исчислении предикатов формула Авыводима тогда и только тогда, когда выводима ее сколемовская нормальная форма. Идея С. ф. используется в таких фундаментальных теоремах математич. логики, как теорема Эрбрана, сводящая вопрос о выводимости в исчислении предикатов предикатной формулы к исследованию вопроса о выводимости в исчислении высказываний бесконечной последовательности пропозициональных формул, теорема Лёвенхейма - Сколема и др. В тех случаях, когда предметная область, на к-рой рассматриваются формулы, обладает дополнительной структурой, можно потребовать от С. ф. определенной связи с этой структурой. Напр., если рассматриваемая предметная область принадлежит иерархии конструктивных по Гёделю множеств, то можно потребовать, чтобы С. ф. также принадлежали определенному уровню в конструктивной иерархии. Существование С. ф., удовлетворяющих дополнительным свойствам, не всегда гарантировано, но эффект от их использования в случае, когда они существуют, оказывается более значительным. В качестве примера можно указать на результат Йенсена о выводимости гипотезы Чэна о двух кардиналах (см. [6]) и отрицания Суслипа гипотезы (см. [5]) из аксиомы конструктивности Гёделя. Теорема Новикова - Кондо об униформизации [img: http://localhost:8080/file/041914-13.jpg] -отношений из дескриптивной теории множеств утверждает существование определенного рода С. ф. (см. [2], с. 280).