KNOWED.RU

Теорема: Если n – произвольное натуральное число, а f – отображение из множества N<=(n+1) в N<=n, где N<n – множество натуральных чисел, ограниченное сверху элементом n, а N<=(n+1) – множество натуральных чисел, ограниченное сверху элементом n+1. Тогда f не является инъективным.

Доказательство: Не сложно догадаться, что для доказательства теоремы выгодно применить метод математической индукции.

База индукции: Если n=1, то очевидно, что отображение f из {12} в {1} не будет инъективным.

Предположение индукции: Предположим, что для некоторого n=k данное утверждение выполнено. То есть f:N<=(k+1)->N<=k не инъективно.

Шаг индукции: Докажем, что утверждение выполняется для n=k+1.Пусть f – произвольное отображение из множества N<=k+1 в N<=n. Тогда возможны два случая:
1) Для любого i<=k справедливо неравенство: f(i)<k-1;
2) Существует такое j<=k, что f(j)=k.
В первом случае существует отображение g из N<=k в N<=k-1, заданное правилом g(i)=f(i). К этому предложению применимо предположение индукции, а следовательно, оно не является инъективным.
Во втором случае, если f(k+1)=k, то f(j)=f(k+1)=k, причем j не равно k+1, а тогда, отображение f не является инъективным. Если же f(k+1)=l<k, то можно считать, что кроме чисел k+1 и j в элементы k и l никакие другие не отображаются, иначе оно не обладало бы свойством инъективности. В таком случае зададим отображение h:N<=(k+1)->N<=k следующим образом:
1) h(i)=f(i), если I не равно k+1 или j;
2) h(i)=l, если i=j;
3) h(i)=n, если i=k+1.
Понятно, что в этом случае отображение f приписывается к случаю, когда для любого i<=k справедливо неравенство: f(i)<k-1, а значит, h, а вслед за ним и f не являются инъективными.
Что и требовалось доказать

Интересно, что из этой теоремы вытекает так называемый принцип Дирихле: Пусть f – отображение из N<=n в N<=m, причем n>m. Тогда отображение f не может быть инъективным.
Опубликовано на сайте: http://www.knowed.ru
Прямая ссылка: http://www.knowed.ru/index.php?name=pages&op=view&id=82
1111