$%\Pi_n$% множества определяются так:

alt text

Как доказать, что $%\{p: \text{ область определения функции }\phi_p\text{ есть простое множество}\}$% является $%\Pi_3$%? (определение простого множества имеется ниже)

То есть если $%X$% - простое множество, то надо найти вычислимое отношение $%S$% такое что

$%x\in X\leftrightarrow \forall y_1\exists y_2\forall y_3 S(x,y_1,y_2,y_3)$%


Множество $%X$% простое, если

  • $%X$% - рекурсивно перечислимо
  • дополнение $%X^c$% бесконечно
  • если $%W$% - бесконечное рекурсивно перечислимое множество, то $%X\cap W\ne \emptyset$%

задан 30 Ноя 7:00

изменен 1 Дек 3:04

В условии была опечатка.

(1 Дек 3:03) logic
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×821

задан
30 Ноя 7:00

показан
25 раз

обновлен
1 Дек 3:04

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru