Аксиома индукции: если множество $%M \subset \mathbb{N}$% таково, что $$1\in M, \forall n\in \mathbb{N}:n\in M\Rightarrow (n+1)\in M,$$ то $%M=\mathbb{N}.$% Доказать, что она эквивалентна утверждению: если множество $%M \subset \mathbb{N}$% таково, что $$\forall n\in \mathbb{N}:1,2,...,(n-1)\in M\Rightarrow n\in M,$$ то $%M=\mathbb{N}.$%
P.S. В одну сторону я вроде бы доказал. По аксиоме индукции 1∈M. Делаем гипотезу: 1,2,...,(n-1)∈M. Тогда естественно (n-1)∈M. По аксиоме n∈M=>(n+1)∈M. Из этого следует: (n-1)∈M=>n∈М. Итого 1,2,...,(n-1)∈M=>(n-1)∈M=>n∈M.

задан 11 Июн '15 23:19

изменен 12 Июн '15 0:03

Прошу также подсказать как убрать перенос строки перед формулой в латехе.

(11 Июн '15 23:20) R0b

@R0b: если Вы хотите, чтобы формула не занимала отдельную строку, то здесь, в отличие от обычного ТеХ'а, надо в начале и в конце формулы писать $% (доллар+процент).

Формулировку второго утверждения надо подправить: или убрать фигурные скобки, или заменить символ принадлежности на символ включения.

(11 Июн '15 23:29) falcao

Спасибо, поправил

(11 Июн '15 23:54) R0b
10|600 символов нужно символов осталось
1

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

Будем называть аксиому индукции Принципом Индукции, а второе условие -- Принципом Индукции-2. Докажем, что ПИ-2 влечёт ПИ.

Рассмотрим множество $%M$%, удовлетворяющее условию ПИ. Требуется доказать, что $%M=\mathbb N$%. Для этого достаточно установить, что $%M$% удовлетворяет условию ПИ-2, то есть для всех $%n\in\mathbb N$% истинна импликация $$1,2,\ldots,n-1\in M\Rightarrow n\in M.$$ При $%n=1$% она верна, так как истинно её заключение. Пусть $%n > 1$%. Тогда $%n=k+1$% для некоторого натурального $%k$%. Если посылка импликации ложна, то сама импликация истинна. Поэтому достаточно рассмотреть случай, когда $%1,2,\ldots,k\in M$%. Как частный случай, $%k\in M$%, и тогда $%k+1\in M$% ввиду предположения о том, что $%M$% удовлетворяет условиям ПИ. Следовательно, заключение импликации истинно, и сама она тоже истинна.

Для доказательства обратного утверждения полезно ввести ещё одну форму принципа индукции, а именно, Принцип Наименьшего Числа. Он формулируется так: всякое непустое подмножество $%K\subseteq\mathbb N$% имеет наименьший элемент. Мы сначала докажем, что ПИ влечёт ПНЧ, а затем -- что ПНЧ влечёт ПИ-2. Сам этот третий принцип очень удобен во многих индуктивных доказательствах.

Итак, пусть ПИ справедлив. Рассмотрим произвольное непустое подмножество $%K\subseteq\mathbb N$%. По определению, найдётся число $%n\in K$%. В качестве $%M$% возьмём множество всех таких $%n$%, для которых верна импликация: "для всех $%K\subseteq\mathbb N$%, если $%n\in K$%, то $%K$% обладает наименьшим элементом". Проверим, что $%M$% удовлетворяет условию ПИ. Тогда будет установлено, что $%M=\mathbb N$%. Тогда импликация верна для всех $%n$%, а у нас есть конкретное $%n$%, для которого $%n\in K$%. Отсюда будет следовать, что $%K$% обладает наименьшим элементом.

Прежде всего, $%1\in M$%, так как если $%1\in K$%, то $%K$% обладает наименьшим элементом, равным $%1$%. Теперь надо проверить, что $%n\in M\Rightarrow n+1\in M$%. Это значит, что надо для произвольного $%K$% доказать истинность импликации: "если $%n+1\in K$%, то $%K$% обладает наименьшим элементом".

Пусть $%n+1\in K$%. Допустим, что $%n\in K$%. Тогда по индукционному предположению $%K$% обладает наименьшим элементом. Допустим, что $%n\notin K$%. Рассмотрим множество $%K'=K\cup\{n\}$%. Поскольку $%n\in K'$%, в силу предположения в $%K'$% есть наименьший элемент, равный некоторому числу $%m$%. Ясно, что $%m\le n$%. Если $%m < n$%, то $%m$% будет наименьшим в $%K$%. Если же $%m=n$%, то $%n+1$% будет наименьшим элементом $%K$%. В любом случае, в $%K$% есть наименьший элемент, что и требовалось доказать.

Теперь докажем, что ПНЧ влечёт ПИ-2. Рассмотрим множество $%M$%, удовлетворяющее условию ПИ-2. Рассуждая от противного, предположим, что $%M\ne\mathbb N$%. Тогда множество $%K=\mathbb N\setminus M$% непусто. Согласно ПНЧ, в нём имеется наименьший элемент $%n$%. По определению наименьшего элемента, $%1,2\ldots,n-1\in M$%. Тогда из условия ПИ-2 для множества $%M$% получается $%n\in M$%, что является противоречием.

ссылка

отвечен 12 Июн '15 0:51

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×476
×65

задан
11 Июн '15 23:19

показан
414 раз

обновлен
12 Июн '15 10:17

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

по почте:

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

по RSS:

Ответы

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

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