Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/uroki/2012_2013/8mat_1213/spec/02-induction-aux.pdf Дата изменения: Sat Feb 9 20:07:09 2013 Дата индексирования: Mon Feb 25 14:26:56 2013 Кодировка: Windows-1251 Поисковые слова: п п п п п

Занятие 2: метод математической индукции (дополнение)

Гимназия 1543, математический спецкурс, 8 В

Многие математические объекты описываются при помощи своих . Определение описывает объект в терминах ранее введ?нных понятий. Но что делать, например, с теми понятиями, на которые ссылается самое первое определение? Чтобы придать им смысл, используются . Определение это введение нового имени для какого-то объекта. Аксиома же это утверждение об объектах, которое мы (в рамках нашей теории) считаем истинным. В школьном курсе математики вы в какой-то мере уже сталкивались как минимум с двумя важными системами аксиом: с аксиомами евклидовой плоскости (на уроках геометрии) и с аксиомами коммутативного кольца (под этими словами скрываются известные вам по начальной школе переместительные, сочетательные и распределительный законы, а также некоторые свойства нуля и единицы). Именно система аксиом зада?т тот объект, который она описывает: все свойства этого объекта в конечном итоге сводятся к аксиомам. Для того, чтобы придать смысл понятию натурального числа, оказывается, требуется всего лишь одна аксиома. Но перед тем, как е? сформулировать, напомним пару терминов. A B правило1 , по которому каждому элементу множества A сопоставлен элемент множества B . элементов множества A мы будем называть2 отображение множества натуральных чисел N в A. Нам также будет удобно считать, что 0 тоже натуральное число. Множество натуральных чисел N определяется следующей аксиомой (Ловера) N 0N +1 : N N
Натуральные числа.
определений аксиомы Отображение Последовательностью

Аксиома

. Существуют множество

, его элемент

и отображение

такие, что для

любого отображения

f :XX

и элемента

xX

существует единственная последовательность

a,

для которой

a0 = x;

an

+1

= f (an ).

соотношения

Менее формально можно сформулировать эту аксиому так: если задан начальный элемент последовательности и задано правило, по которому из каждого элемента последовательности можно получить следующий, то задана вся последовательность (такой способ задания последовательности называется заданием при помощи ). Покажем, как из аксиомы Ловера можно получить принцип индукции Пеано. Пусть A жество, содержащее 0 и вместе с каждым своим числом содержащее следующее. Тогда правило f (n) отображение A A. Зададим последовательность a соотношениями
a0 = 0; an
+1

рекуррентного

Индукция.

N = n+1

подмнозада?т

= f (an ).

Так как A подмножество N, то отображение a : N A можно рассматривать3 как отображение b : N N. Нетрудно заметить, что b удовлетворяет тому же рекуррентному соотношению (b0 = 0, bn+1 = bn + 1), что и тождественное отображение4 . Значит, по аксиоме Ловера, отображение b совпадает с тождественным. В частности, множество значений b (а, значит, и a) вс? N.
Сложение.

Операция ?x+? прибавления числа x определяется рекуррентным соотношением
x + 0 = x; x + (n + 1) = (x + n) + 1.

Почти ?бесплатно? аксиома Ловера позволяет получить, например, сочетательный закон (попробуйте его доказать явно по индукции, исходя только из рекуррентного определения ?x+?): (x + y ) + 0 = x + y = x + (y + 0); (x + y ) + (n + 1) = ((x + y ) + n) + 1 и x + (y + (n + 1)) = x + ((y + n) + 1) = (x + (y + n)) + 1, поэтому ?(x + y) + ? и ?x + (y + )? одна и та же операция. Из сочетательного закона легко следует переместительный. Сперва докажем, что ?0+? и ?+0? одно и то же: 0 + 0 = 0 = 0 + 0; 0 + (n + 1) = (0 + n) + 1 и (n + 1) + 0 = n + 1 = (n + 0) + 1. Дальше надо заметить, что ?1+? и ?+1? одно и то же. Действительно, 1 + 0 = 1 = 0 + 1; 1 + (n + 1) = (1 + n) + 1 и (n + 1) + 1 = (n + 1) + 1. Теперь нетрудно доказать, что и ?x+? и ?+x? одинаковы (обратите внимание, что в последней цепочке равенств сначала примен?н сочетательный закон, а затем эквивалентность операций ?+1? и ?1+?): x + 0 = x = 0 + x; x + (n + 1) = (x + n) + 1 и (n + 1) + x = n + (1 + x) = n + (x + 1) = (n + x) + 1.
Вообще говоря, слово ?правило? требует уточнения во избежание парадоксов. Но это тема отдельного разговора. На протяжении этого листка. Часто удобно бывает определять последовательность более общо. Если быть более точным, то b(n) = i(a(n)), где i : A N каноническое вложение (отображение, сопоставляющее каждому элементу A этот же элемент в N). 4 Тождественным отображением на множестве X называется отображение id : X X , отображающее каждый элемент X в себя, т.е. id(x) = x.
1 2 3