Пусть T - трехместный предикат. Какова связь между предикатами

$$T(e,x,y)$$ и $$\exists y T(e,x,y)$$?

Второй предикат, как я понимаю, это множество $%\{(e,x,y):(e,x,y)\in T\text{ для некоторого } y\}$%. Это не то же самое, что первый?

И в терминах вычислимости, вычислимость какого из них влечет вычислимость другого?

задан 8 Ноя 19:40

@logic: тут часть формул снова не пропечаталась.

Предикаты совсем разные: один трёхместный, а второй двуместный. Он от переменной y не зависит, и область истинности состоит из пар (e,x), для которых существует y, для которого верно условие T(e,x,y).

Связи между вычислимостью нет ни в одну из сторон -- примеры привести нетрудно.

(8 Ноя 23:45) falcao

А если exists заменить на forall, то предикат сколькиместным будет? Вот тут https://math.stackexchange.com/questions/3425062/quantifier-in-front-of-a-relation написали, что вставление forall "местность" предиката не изменяет

(10 Ноя 0:10) logic

@logic: если переменная находится под квантором (любым из двух), то от неё предикат не зависит. Другое дело, что при ограниченной квантификации (опять же, с любым из кванторов), мы сами добавляем новую свободную переменную x, когда пишем (Qy < x), где Q -- квантор. За счёт этого арность остаётся прежней.

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

Ваш ответ

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

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

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

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

отмечен:

×797

задан
8 Ноя 19:40

показан
31 раз

обновлен
10 Ноя 10:55

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

по почте:

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

по RSS:

Ответы

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

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