Докажите, что любая инъективная функция из $\{ 1, \dots, n \}$ сам по себе биективен.
Это Упражнение 1 со страницы 50 Анализа I Аманна и Эшера. Я нашел похожие вопросы здесь и здесь, но ни один из этих вопросов не имеет решения, использующего то, на что намекается в тексте.
Упражнение:
Моя попытка:
Кажется простым утверждать, что, поскольку инъективная функция отправляет каждый элемент в своем домене другому элементу в кодомене, она должна «поразить» все элементы в $\{ 1, \dots, n \}$. Я не уверен, достаточно ли это формально, и, во всяком случае, здесь не используется данный намек.
Если я использую подсказку, то базовый случай инъективной функции $\{ 1 \} \to \{ 1 \}$определенно биективен. Предположим, что любая инъективная функция из$\{ 1, \dots, n \}$ к $\{ 1, \dots, n \}$ биективен, и рассмотрим инъективную функцию $f \colon \{ 1 , \dots, n + 1 \} \to \{ 1 , \dots, n + 1 \}$как описано. Мы хотим показать, что$f$ биективен.
Мне кажется, есть как минимум два основных способа показать, что $f$биективен. Во-первых, мы можем показать, что это сюръективно, что предполагает рассмотрение некоторого элемента$l \in \{ 1 , \dots, n + 1 \}$ и показывая, что существует элемент $m$ в том же наборе, что $f(m) = l$. Второй способ - показать, что существует функция$i$ такой, что $f \circ i$- функция тождества. Тем не менее, индуктивное доказательство действительно должно использовать индуктивное предположение, и я не уверен, что какая-либо из этих тактик работает.
Я нахожу данную подсказку довольно загадочной, но я собрал несколько мыслей относительно подсказки ниже.
- я вижу это $g$биективен. Это почти функция идентичности, за исключением того, что она отправляет$k$ к $n + 1$ и $n + 1$ к $k$.
- поскольку $f$ и $g$ инъективны, $h$ также инъективен.
- Я также вижу это $g$ отменяет то, что $f$ делает для $n + 1$, следовательно $h(n + 1) = n + 1$.
- Функция $h$ почти то же самое, что $f$, за исключением замены, выполненной $g$ как описано в 1.
- Ограничение $h \mid \{ 1, \dots, n\}$ не отправляет элемент в $n + 1$, потому что единственный элемент, который $h$ отправляет в $n + 1$ является $n + 1$, и $n + 1$ вне ограничения.
Я не знаю, как превратить это в доказательство. Я ценю любую помощь.
Ответы
У вас есть все части. Ты знаешь что$h\upharpoonright\{1,\ldots,n\}$ это инъекция от $\{1,\ldots,n\}$самому себе, поэтому по предположению индукции это биекция. Вы также знаете, что$h(n+1)=n+1$, так $h$ это биекция от $\{1,\ldots,n+1\}$себе. Наконец, вы можете легко убедиться, что$f=g\circ h$, и $g$ явно так $f$ состав биекций от $\{1,\ldots,n+1\}$ самому себе и, следовательно, тоже такое взаимное соответствие.
Ваша первая попытка - это просто махание рукой.
Как вы писали, дело $n=1$легко. Предположим, что каждое инъективное отображение из$\{1,2,\ldots,n\}$ в себя является биективным и пусть $f$ быть неэффективной картой из $\{1,2,\ldots,n+1\}$в себя. Есть две возможности:
- $f(n+1)=n+1$: Тогда, поскольку $f$ инъективен, $f\bigl(\{1,2,\ldots,n\}\bigr)\subset \{1,2,\ldots,n\}$. Итак, по предположению индукции каждый$k\in\{1,2,\ldots,n\}$ равно $f(l)$, для некоторых $l\in\{1,2,\ldots,n\}$. поскольку$f(n+1)=n+1$, $f$ биективен.
- $f(n+1)=k$, для некоторых $k<n+1$: Потом $g\circ f$ карты $n+1$ в $n+1$ и то, что было написано в предыдущем абзаце, показывает, что $g\circ f$биективен. поскольку$g$ биективен, $f=g^{-1}\circ(g\circ f)$ и так $f$ тоже биективен.
Пусть наша гипотеза индукции состоит в том, что если функция из набора с n элементами в набор с n элементами инъективна, то она биективна.
(Обратите внимание, что мы делаем несколько более широкое заявление, чем говорим об этом одном наборе, что позволит нам избежать беспорядка с делом)
Теперь докажем случай n + 1. Пусть f - инъективная функция между двумя наборами размера n + 1.$f: X \rightarrow Y, |X| = n+1, |Y|=n+1$
Возьмите произвольный элемент из $X$, сказать $x$, и рассмотрим функцию от отображения X без x в Y без f (x). Эта новая функция,$f^*$, определено, потому что никакие две точки не были отправлены в один и тот же элемент в Y. По предположению индукции эта функция сюръективна и, следовательно, биективна. Теперь мы можем сделать вывод, что f, определенный на всем X, является сюръективным при отправке в Y, поскольку единственным оставшимся элементом был f (x), который находится в образе x.
По сути, мы удаляем один элемент, смотрим на f, определенный на X \ {x}, и утверждаем, что он сюръективен к Y {f (x)}. Затем мы смотрим на X, Y и видим, что если X \ {x} к Y \ {f (x)} сюръективно, то f сюръективно от X к Y.