Математическая логика.Доказать теорему теории S-форм.арифмет

[MakagonovD]

$\forall x($A(x)\to\exists(y<x \wedge A(y))$)\rightarrow \forall x \neg A(x)$

Это задание из Мендельсона,так называемый метод бесконечного спуска,нужно доказать это утверждение. Ребят подскажите как это сделать,кучу литературы перебрал...ничего толкового не нашёл...

[Xaositect]

На естественном языке (в смысле, по-русски) Вы можете это утверждение сформулировать и доказать?

[MakagonovD]

Нет не знаю...Но думаю,что это звучит так :"Для любых х, (которые обладают свойством А следует,что существует у,который меньше х и обладает свойством А) и из этого всего следует,что не любые х обладают свойтсвом А " это конечно очень криво...но я по другому не знаю,пытался найти хотя бы обычное математическое доказательство метода бесконечного спуска,но ничего не нашёл...

[Maslov]

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

[MakagonovD]

Максим,я это заметил,но вся проблема в том,что в методе мин.элемента стоит импликация,а в моём примере конъюнкция

[Xaositect]

Давайте тогда я сформулирую.
"Если для любого натурального $x$, обладающего свойством $A$, найдется $y$, строго меньший $x$ и также обладающий свойством $A$, то свойство $A$ не может выполняться ни для какого натурального числа"
Понятно почему это именно это утверждение?
Попробуйте его сначала по-русски с использованием индукции доказать.

[MakagonovD]

Утверждение понятно,я это приблизительно так и понимал,только вот не учёл множество натуральных чисел...я интуитивно понимаю как доказать с помощью индукции,но не разу не получалось довести это дело до конца...вообщем я нифига не соображаю в индукции...

-- 21.05.2012, 20:40 --

Это не потому,что я ленивый...я просто серьёзно не знаю как это сделать,помоги пожалуйста,если понимаешь...просто я уже столько над этой работой просидел и никакого толку...

[Xaositect]

Давайте доказывать.
Итак, предположим нам известно, что для люого красного $x$ найдется $y$, тоже красное и меньше $x$
А теперь индукция
1) База индукции. Почему $0$ (или $1$, с чего там у Вас натуральные числа начинаются?) не может быть красным?
2) Пусть известно, что все числа от $0$ до $z$ не красные. Почему $z+1$ не может быть красным?

А потом запишите аксиому индукции, которая позволит перейти от (1) и (2) к тому факту, что красных чисел нет. (тут есть небольшая хитрость --- в качестве формулы в аксиоме индукции нужно использовать не само свойство красноты числа, а кое-что посложнее. Скорее всего, в Мендельсоне такая форма индукции тоже разбирается.)

[MakagonovD]

я попробую....

[Toucan]

MakagonovD в сообщении #574259 писал(а):

помоги пожалуйста,если понимаешь

MakagonovD, устное замечание за фамильярность. Читайте Правила форума:

Правила форума в http://dxdy.ru/post27356.html#p27356 писал(а):

1) Нарушением считается:
…
е) ..., фамильярность (у нас принято обращаться друг к другу на "Вы")...

[MakagonovD]

спасибо за совет)

[Maslov]

MakagonovD в сообщении #574242 писал(а):

Максим,я это заметил,но вся проблема в том,что в методе мин.элемента стоит импликация,а в моём примере конъюнкция

Я просто хотел обратить Ваше внимание на тот факт, что принцип наименьшего числа утверждает: из существования некоторого натурального числа, обладающего свойством $A$, следует существование наименьшего натурального числа, обладающего этим свойством. А в левой части формулировки принципа бесконечного спуска записано условие, что наименьшего числа, обладающего свойством $A$, не существует.

Такой вот modus tollens.

[MakagonovD]

Спасибо за совет))Попробую из этого что-нибудь выжать))