からの単射関数を証明する $\{ 1, \dots, n \}$ それ自体は全単射です。
これは、AmannとEscherによる分析Iの50ページの演習1です。私はこことここで同様の質問を見つけましたが、それらの質問のどちらにも、テキストで示唆されていることを使用する解決策がありません。
運動：
私の試み：
単射関数はそのドメイン内の各要素を終域内の異なる要素に送信するため、のすべての要素を「ヒット」する必要があると主張するのは簡単なようです。 $\{ 1, \dots, n \}$。これが十分に形式的であるかどうかはわかりませんが、とにかく、与えられたヒントを使用していません。
ヒントを使用すると、単射関数の基本ケース $\{ 1 \} \to \{ 1 \}$間違いなく全単射です。からの単射関数を仮定します$\{ 1, \dots, n \}$ に $\{ 1, \dots, n \}$ 全単射であり、単射関数を考慮します $f \colon \{ 1 , \dots, n + 1 \} \to \{ 1 , \dots, n + 1 \}$説明したように。それを示したい$f$ 全単射です。
それを示すには少なくとも2つの基本的な方法があるように私には思えます $f$全単射です。まず、それが全射であることを示すことができます。これには、いくつかの要素を考慮することが含まれます。$l \in \{ 1 , \dots, n + 1 \}$ 要素が存在することを示す $m$ 同じセットで $f(m) = l$。2番目の方法は、関数が存在することを示すことです$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\}$それ自体に。2つの可能性があります：
- $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個の要素を持つ集合への関数が単射である場合、それは全単射であるという帰納法の仮説を考えてみましょう。
（この1セットについて話すよりも少し広い声明を出していることに注意してください。これにより、ケースワークの混乱を避けることができます）
ここで、n +1の場合を証明します。fをサイズn + 1の2つのセット間の単射関数とします。$f: X \rightarrow Y, |X| = n+1, |Y|=n+1$
から任意の要素を取ります $X$、 いう $x$、およびxなしのXからf（x）なしのYへのマッピングからの関数を検討します。この新機能、$f^*$Yの同じ要素に2つの点が送信されなかったため、が定義されます。帰納法の仮説により、この関数は全射であり、したがって全単射です。これで、残りの要素はxのイメージにあるf（x）だけだったので、X全体で定義されたfはYに送信されたときに全射であると結論付けることができます。
基本的に、1つの要素を削除し、X \ {x}で定義されたfを調べ、それがY {f（x）}に全射であると主張します。次に、X、Yを見て、X \ {x}からY \ {f（x）}が全射である場合、fはXからYまで全射であることがわかります。