Помогите доказать, пожалуйста, что формула $% \neg x < x$% является теоремой в теории P. Преподаватель немного запутал с этим вопросом, хотя вроде это просто

Аксиомы этой теории:

$%1.\forall x \forall y (s(x) = s(y) \supset x = y $%

$%2.\forall x (\neg s(x)= 0 )$%

$%3.\forall x (\neg x = 0 \exists y (x = s(y))) $%

$%4.\forall x (x + 0= x)$%

$%5.\forall x \forall y (x + s(y) = s(x+y)) $%

$%6.\forall x (x\ast 0 = 0) $%

$%7.\forall x \forall y (x\ast s(y) = x\ast y + x) $%

$%8.$%Бесконечное множество формул вида $%P(A)\forall y ((A(0)\&\forall x(A(x) \supset A(s(x)) \supset A(y) $%, где $%A(x)$% - любая формула со свободной переменной $%x$%, и $%P(A)$% - аксиома индукции для $%A$%

задан 27 Дек '19 17:52

изменен 27 Дек '19 17:53

@Aniorp: у Вас формула записана неправильно. Я даже не сразу догадался до смысла. Там скобки нужны: отрицается ведь не число x, а высказывание о том, что x меньше x. В принципе, это доказывается по индукции. Очень хорошо, что приложили список аксиом (так как есть куча разных аксиоматик того же самого). Но здесь не хватает определения отношения "меньше". Надо его привести (от вида определения может зависеть ход рассуждений).

(27 Дек '19 19:36) falcao

А в задачнике скобок нет, почему-то. "Меньше" определено как $%x\le y \& \neg x = y$%, а "меньше или равно" как $%\exists z (z + x = y)$%

(27 Дек '19 19:46) Aniorp

@Aniorp: да, определения тут стандартные. Чуть позже постараюсь описать. Скобок могло не быть по причине того, что перед предикатами их не ставят, а x < x выступает как сокращение предикатной записи P(x,x). Но раз уж мы перешли к более "человеческой" форме записи, то скобки всячески уместны.

(27 Дек '19 19:50) falcao

@Aniorp: здесь вообще-то даже индукции не надо (в другой версии, когда натуральный ряд начинается с 1, доказательство по индукции требуется). Здесь рассуждаем от противного: принимаем гипотезу x < x и приводим её к противоречию. Из (x<=x)&not(x=x) выводим not(x=x), что сразу противоречит аксиоме рефлексивности равенства.

(28 Дек '19 3:14) falcao

@falcao Благодарю! Разобрался уже и сам, и с Вашей помощью тоже :3

(29 Дек '19 16:31) Aniorp
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×865

задан
27 Дек '19 17:52

показан
72 раза

обновлен
29 Дек '19 16:31

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

по почте:

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

по RSS:

Ответы

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

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