Рассмотрим бинарное отношение R на множестве N, которое не принадлежит семеству всех $%\Sigma_{1}$%-отношений. Верно ли, что хотя бы одно из отношений $%\{(x, y) \in R \mid x$% делит $%y\}$% или $%\{(x, y) \in R \mid x$% не делит $%y\}$% не является $%\Sigma_{1}$%-отношением?

$%\Sigma_{1}$% - такое отношение на N, которое может быть получено из $%\Delta_0$%- отношения посредством однократной экзистенциальной квантификации.

$%\Delta_0$% - такое отношение, которое можно получить из отношений x + y = z, xy = z с помощью операций: 1) пересечения и объединения, 2) явных преобразований, 3) подстановкой констант, 4) ограниченной квантификации, 5) взятие дополнения.

задан 9 Мар 19:25

@falcao, может у вас есть возможность подсобить? Был бы бескрайне благодарен.

(10 Мар 17:43) lukas0664

@lukas0664: по-моему, тут простая идея, только не хочется всё подробно расписывать в обозначениях. Если есть две экзистенциальные формулы, то в них сначала можно сделать разные переменные. Далее, если они соединены знаком дизъюнкции, типа (Ea)P(a) V (Eb)Q(b), то это логически эквивалентно (Ea)(Eb)(P(a)VQ(b)). Тогда дизъюнкция двух условий превратится в (x,y) \in R ввиду того, что в одном случае x делит y, а в другом не делит. Получится, что R задаётся Sigma_1-формулой.

(10 Мар 18:06) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×4,287
×2,102
×2,012
×1,187

задан
9 Мар 19:25

показан
204 раза

обновлен
10 Мар 18:06

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

по почте:

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

по RSS:

Ответы

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

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