Buktikan bahwa ada fungsi injeksi dari $\{ 1, \dots, n \}$ untuk dirinya sendiri bersifat bijektiva.

Aug 19 2020

Ini adalah Latihan 1 dari halaman 50 Analisis I oleh Amann dan Escher. Saya telah menemukan pertanyaan serupa di sini dan di sini, tetapi tidak satu pun dari pertanyaan itu memiliki solusi yang menggunakan apa yang diisyaratkan dalam teks.

Olahraga:

Upaya saya:

Tampaknya sederhana untuk menyatakan bahwa, karena fungsi injeksi mengirimkan setiap elemen dalam domainnya ke elemen yang berbeda dalam codomain, itu harus "mengenai" semua elemen di $\{ 1, \dots, n \}$. Saya tidak yakin apakah ini cukup formal, dan bagaimanapun juga itu tidak menggunakan petunjuk yang diberikan.

Jika saya menggunakan petunjuk, maka kasus dasar dari fungsi injeksi $\{ 1 \} \to \{ 1 \}$pasti bijektiva. Asumsikan bahwa setiap fungsi injeksi dari$\{ 1, \dots, n \}$ untuk $\{ 1, \dots, n \}$ bersifat bijektiva, dan pertimbangkan fungsi injeksi $f \colon \{ 1 , \dots, n + 1 \} \to \{ 1 , \dots, n + 1 \}$seperti yang dijelaskan. Kami ingin menunjukkan itu$f$ bersifat bijective.

Menurut saya, setidaknya ada dua cara dasar untuk menunjukkannya $f$bersifat bijective. Pertama, kita dapat menunjukkan bahwa itu surjective, yang melibatkan pertimbangan beberapa elemen$l \in \{ 1 , \dots, n + 1 \}$ dan menunjukkan ada elemen $m$ di set yang sama seperti itu $f(m) = l$. Cara kedua adalah menunjukkan bahwa ada suatu fungsi$i$ seperti yang $f \circ i$adalah fungsi identitas. Namun, bukti induktif harus benar-benar menggunakan asumsi induktif, dan saya tidak yakin salah satu taktik ini dapat digunakan.

Saya menemukan petunjuk yang diberikan cukup membingungkan, tetapi saya telah mengumpulkan beberapa pemikiran tentang petunjuk di bawah ini.

  1. saya melihat bahwa $g$bersifat bijective. Ini hampir merupakan fungsi identitas kecuali yang dikirimkan$k$ untuk $n + 1$ dan $n + 1$ untuk $k$.
  2. Sejak $f$ dan $g$ bersifat suntik, $h$ juga suntik.
  3. Saya juga melihat itu $g$ membatalkan apa $f$ lakukan untuk $n + 1$, karenanya $h(n + 1) = n + 1$.
  4. Fungsinya $h$ hampir sama dengan $f$, kecuali untuk pertukaran yang dilakukan oleh $g$ seperti yang dijelaskan di 1.
  5. Pembatasan $h \mid \{ 1, \dots, n\}$ tidak mengirim elemen apa pun ke $n + 1$, karena satu-satunya elemen itu $h$ mengirim ke $n + 1$ aku s $n + 1$, dan $n + 1$ berada di luar batasan.

Saya tidak tahu bagaimana mengubah ini menjadi bukti. Saya menghargai bantuan apapun.

Jawaban

2 BrianM.Scott Aug 19 2020 at 03:56

Anda memiliki semua bagiannya. Kamu tahu itu$h\upharpoonright\{1,\ldots,n\}$ adalah suntikan dari $\{1,\ldots,n\}$untuk dirinya sendiri, jadi dengan hipotesis induksi itu adalah bijection. Anda juga tahu itu$h(n+1)=n+1$, jadi $h$ adalah bijeksi dari $\{1,\ldots,n+1\}$untuk dirinya sendiri. Terakhir, Anda dapat dengan mudah memverifikasi itu$f=g\circ h$, dan $g$ jelas begitu $f$ adalah komposisi bijections dari $\{1,\ldots,n+1\}$ untuk dirinya sendiri dan oleh karena itu juga merupakan kebijaksanaan seperti itu.

Upaya pertama Anda pada dasarnya hanya melambaikan tangan.

3 JoséCarlosSantos Aug 19 2020 at 03:55

Seperti yang Anda tulis, kasusnya $n=1$gampang. Asumsikan bahwa setiap peta suntik dari$\{1,2,\ldots,n\}$ ke dalam dirinya sendiri bersifat bijective and let $f$ menjadi peta efektif dari $\{1,2,\ldots,n+1\}$ke dalam dirinya sendiri. Ada dua kemungkinan:

  1. $f(n+1)=n+1$: Lalu, sejak $f$ bersifat suntik, $f\bigl(\{1,2,\ldots,n\}\bigr)\subset \{1,2,\ldots,n\}$. Jadi, dengan hipotesis induksi, masing-masing$k\in\{1,2,\ldots,n\}$ adalah sama dengan $f(l)$, untuk beberapa $l\in\{1,2,\ldots,n\}$. Sejak$f(n+1)=n+1$, $f$ bersifat bijective.
  2. $f(n+1)=k$, untuk beberapa $k<n+1$: Kemudian $g\circ f$ peta $n+1$ ke $n+1$ dan apa yang tertulis di paragraf sebelumnya menunjukkan itu $g\circ f$bersifat bijective. Sejak$g$ bersifat bijective, $f=g^{-1}\circ(g\circ f)$ sehingga $f$ juga bersifat bijektiva.
1 EthanHorsfall Aug 19 2020 at 04:01

Anggaplah hipotesis induksi kita bahwa, jika suatu fungsi dari himpunan dengan n elemen ke himpunan dengan n elemen adalah injektif, maka itu bersifat bijektiva.

(Perhatikan bahwa kami membuat pernyataan yang sedikit lebih luas daripada berbicara tentang satu set ini, yang akan memungkinkan kami untuk menghindari kekacauan dengan kerja kasus)

Sekarang, kami membuktikan kasus n + 1. Misalkan f adalah fungsi injeksi antara dua set ukuran n + 1.$f: X \rightarrow Y, |X| = n+1, |Y|=n+1$

Ambil elemen arbitrer dari $X$, katakanlah $x$, dan pertimbangkan fungsi dari pemetaan X tanpa x ke Y tanpa f (x). Fungsi baru ini,$f^*$, didefinisikan, karena tidak ada dua titik yang dikirim ke elemen yang sama di Y. Dengan hipotesis induksi, fungsi ini bersifat surjektif dan dengan demikian bersifat bijektiva. Sekarang kita dapat menyimpulkan bahwa f yang didefinisikan pada semua X bersifat surjective ketika dikirim ke Y, karena satu-satunya elemen yang tersisa adalah f (x), yang ada pada gambar x.

Pada dasarnya, kami menghapus satu elemen, melihat f yang didefinisikan pada X \ {x}, dan menyatakan bahwa itu adalah ekspektasi dari Y {f (x)}. Kemudian kita melihat X, Y dan dapat melihat bahwa jika X \ {x} hingga Y \ {f (x)} adalah surjektiva, maka f adalah ekspresif dari X ke Y.