모든 주입 기능이 $\{ 1, \dots, n \}$ 그 자체로는 bijective입니다.
이것은 Amann과 Escher 의 분석 I 50 페이지의 연습 1입니다 . 여기 와 여기 에서 비슷한 질문을 찾았 지만 그 질문 중 어느 것도 텍스트에서 암시하는 것을 사용하는 솔루션이 없습니다.
운동:
내 시도 :
주입 함수는 도메인의 각 요소를 공동 도메인의 다른 요소로 보내기 때문에 모든 요소를 "적중"해야한다고 주장하는 것은 간단 해 보입니다. $\{ 1, \dots, n \}$. 나는 이것이 충분히 공식적인지 확실하지 않으며, 어쨌든 주어진 힌트를 사용하지 않습니다.
힌트를 사용하면 주입 함수의 기본 케이스 $\{ 1 \} \to \{ 1 \}$확실히 bijective입니다. 모든 주입 함수가$\{ 1, \dots, n \}$ ...에 $\{ 1, \dots, n \}$ bijective이고 주입 기능을 고려하십시오. $f \colon \{ 1 , \dots, n + 1 \} \to \{ 1 , \dots, n + 1 \}$설명한대로. 우리는 그것을 보여주고 싶습니다$f$ bijective입니다.
그것을 보여주는 데 최소한 두 가지 기본 방법이있는 것 같습니다. $f$bijective입니다. 첫째, 우리는 그것이 어떤 요소를 고려하는 것을 포함하는 추측임을 보여줄 수 있습니다$l \in \{ 1 , \dots, n + 1 \}$ 요소가 있음을 보여주는 $m$ 같은 세트에서 $f(m) = l$. 두 번째 방법은 기능이 있음을 보여주는 것입니다.$i$ 그런 $f \circ i$ID 함수입니다. 그러나 귀납적 증명은 실제로 귀납적 가정을 사용해야하며,이 두 전술 중 어느 것도 사용하는지 잘 모르겠습니다.
주어진 힌트가 꽤 신비 스럽지만 아래 힌트에 대한 몇 가지 생각을 모았습니다.
- 내가 볼 $g$bijective입니다. 보내는 것을 제외하고 거의 식별 기능입니다$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\}$그 자체로, 귀납 가설에 의해 그것은 bijection입니다. 당신은 또한 알고 있습니다$h(n+1)=n+1$, 그래서 $h$ 에서 bijection입니다 $\{1,\ldots,n+1\}$그 자체로. 마지막으로, 쉽게 확인할 수 있습니다.$f=g\circ h$, 및 $g$ 분명히 그렇게 $f$ 다음의 bijections의 구성입니다 $\{1,\ldots,n+1\}$ 따라서 그 자체로도 그러한 bijection입니다.
첫 번째 시도는 기본적으로 손 흔들기입니다.
당신이 쓴 것처럼 사건 $n=1$쉽습니다. 모든 주입 맵이$\{1,2,\ldots,n\}$ 그 자체로 bijective이고 $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$ bijective입니다.
- $f(n+1)=k$, 일부 $k<n+1$: 그럼 $g\circ f$ 지도 $n+1$ 으로 $n+1$ 이전 단락에 쓰여진 내용은 $g\circ f$bijective입니다. 이후$g$ bijective, $f=g^{-1}\circ(g\circ f)$ 그래서 $f$ 역시 bijective입니다.
우리의 귀납 가설은 n 개의 요소를 가진 집합에서 n 개의 요소를 가진 집합으로의 함수가 주입 적이라면 그것은 bijective라는 것입니다.
(이 한 세트에 대해 이야기하는 것보다 약간 더 광범위한 진술을하고 있다는 점에 유의하십시오.
이제 우리는 n + 1 사례를 증명합니다. f를 크기 n + 1의 두 세트 사이의 주입 함수라고합시다.$f: X \rightarrow Y, |X| = n+1, |Y|=n+1$
임의의 요소를 가져옵니다. $X$, 말 $x$, x없이 X를 f (x)없이 Y로 매핑하는 함수를 고려합니다. 이 새로운 기능은$f^*$는 Y의 동일한 요소에 두 점이 전송되지 않았기 때문에 정의됩니다. 귀납 가설에 따르면이 함수는 추측 적이며 따라서 bijective입니다. 이제 우리는 모든 X에 정의 된 f가 Y로 전송 될 때 추측 적이라는 결론을 내릴 수 있습니다. 남은 요소는 x 이미지에있는 f (x)뿐입니다.
기본적으로 우리는 하나의 요소를 제거하고 X \ {x}에 정의 된 f를보고 Y {f (x)}에 대한 추측이라고 주장합니다. 그런 다음 X, Y를보고 X \ {x}에서 Y \ {f (x)}까지가 추측이면 f는 X에서 Y까지 추측입니다.