С. С. Гончаров, Н. Т. Когабаев, “О $\Sigma^0_1$-классификации отношений на вычислимых структурах”, Вестн. НГУ. Сер. матем., мех., информ., 2008, том 8, выпуск 4,страницы 23

Эта публикация цитируется в 2 статьях

О $\Sigma^0_1$-классификации отношений на вычислимых структурах

С. С. Гончаров^ab, Н. Т. Когабаев^ab

^a РОССИЯ, 630090, Новосибирск, 90, пр. Акад. Коптюга, 4, Институт математики им. С. Л. Соболева СО РАН
^b РОССИЯ, 630090, Новосибирск, 90, ул. Пирогова, 2, Новосибирский государственный университет

Аннотация: В статье построен пример вычислимой структуры сигнатуры, состоящей из бесконечного числа бинарных предикатных символов, для которой не существует $\Sigma^0_1$-классификации всех одноместных отношений, определимых в указанной структуре $\Sigma^0_1$-формулами.

Ключевые слова: вычислимая структура, $\Sigma^0_1$-формула, $\Sigma^0_1$-классификация.

УДК: 510.5

Поступила в редакцию: 17.05.2008