Читайте также

Главная  Лучшие    Популярные   Список   Добавить
Статьи » Математика » Алгебра

Теорема: невозможность существования инъективного отображения из N<=(n+1) в N<=n

Алгебра Теорема: Если 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 не может быть инъективным.

Дополнительно по данной категории

11.03.2010 - История квадратных уравнений манэ
11.03.2010 - Квадратные уравнения
10.03.2010 - Упрощение уравнений и сведение к линейному
10.03.2010 - Упрощение уравнений и сведение к линейному
10.03.2010 - Линейные уравнения
Нет комментариев. Почему бы Вам не оставить свой?
Ваше сообщение будет опубликовано только после проверки и разрешения администратора.
Ваше имя:
Комментарий:
Смайл - 01 Смайл - 02 Смайл - 03 Смайл - 04 Смайл - 05 Смайл - 06 Смайл - 07 Смайл - 08 Смайл - 09 Смайл - 10 Смайл - 11 Смайл - 12 Смайл - 13 Смайл - 14 Смайл - 15 Смайл - 16 Смайл - 17 Смайл - 18
Секретный код:
Секретный код
Повторить:

Поиск по сайту

Поиск

Авторизация


Добро пожаловать,
Аноним

Регистрация или входРегистрация или вход
Потеряли пароль?Потеряли пароль?

Ник:
Пароль:


Содержание:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Правообладателям
Образование