Fungsi Surjektif antara Dua Himpunan Berhingga dengan Kardinalitas Sama

Fungsi surjektif antara dua himpunan dengan kardinalitas sama merupakan fungsi bijektif. Sebelum membuktikan teorema ini, kita akan melihat bagaimana jika kardinalitasnya kecil, misalnya 4. Tujuannya adalah agar pembaca lebih mudah memahami ide yang digunakan dalam membuktikan teorema tersebut.

Problem 1

Misalkan $X$ dan $Y$ adalah himpunan berhingga, dengan $n(X)=n(Y)=4$, dan $f$ adalah sebuah fungsi surjektif dari $X$ ke $Y$. Buktikan bahwa $f$ adalah fungsi bijektif.

Solusi

Sebelum membuktikan pernyataan di atas, kita akan membahas beberapa istilah yang akan digunakan, yaitu fungsi injektif, fungsi surjektif, dan fungsi bijektif. Misalkan $A$ dan $B$ adalah dua himpunan, dan $f$ adalah sebuah fungsi dari $A$ ke $B$.

Fungsi $f$ dikatakan injektif jika setiap anggota $A$ memiliki peta yang berbeda. Jika $a_1$ dan $a_2$ adalah dua anggota berbeda dari $A$ maka $f(a_1)$ juga berbeda dengan $f(a_2)$. Secara matematis, jika $a_1,a_2 \in A$ dengan $a_1 \neq a_2$ maka $f(a_1) \neq f(a_2)$. Pernyataan ini ekuivalen dengan kontraposisinya, yaitu jika $a_1,a_2 \in A$ dengan $f(a_1)=f(a_2)$ maka $a_1=a_2$. Fungsi $f$ dikatakan tidak injektif, jika terdapat $a_1,a_2 \in A$ dengan $a_1 \neq a_2$ tetapi $f(a_1)=f(a_2)$.

Fungsi $f$ dikatakan surjektif jika setiap anggota $B$ mempunyai setidaknya satu prapeta di himpunan A. Dalam kata lain, fungsi $f$ surjektif jika daerah hasil $f$ sama dengan himpunan $B$. Secara matematis, $f$ dikatakan surjektif, jika untuk setiap $q \in B$ terdapat $p \in A$ sehingga $f(p)=q$. Fungsi $f$ dikatakan tidak surjektif, jika terdapat anggota $B$ yang tidak mempunyai prapeta.

Fungsi bijektif adalah fungsi yang injektif sekaligus surjektif. Pada fungsi bijektif, kardinalitas domain harus sama dengan kardinalitas kodomain. Untuk membuktikan bahwa suatu fungsi surjektif adalah fungsi bijektif, cukup dengan menunjukkan bahwa fungsi tersebut injektif.

Bukti

Misalkan $X$ dan $Y$ adalah himpunan berhingga, dengan $n(X)=n(Y)=4$, dan $f$ adalah sebuah fungsi surjektif dari $X$ ke $Y$. Kita akan membuktikan bahwa $f$ fungsi bijektif. Hal ini dilakukan dengan menunjukkan bahwa $f$ fungsi injektif. Kita akan menggunakan pembuktian dengan kontradiksi.

Andaikan $f$ bukan fungsi injektif. Artinya, terdapat dua anggota berbeda dari $X$ dengan peta yang sama di $Y$. Agar lebih jelas, kita misalkan $X=\{a,b,c,d\}$ dan $Y=\{1,2,3,4\}$. Kita misalkan pula, $a$ dan $b$ sebagai anggota $X$ dengan peta yang sama, yaitu $1 \in Y$. Perhatikan gambar berikut.

Karena $f$ adalah fungsi surjektif, maka $2,3,4 \in Y$ harus mempunyai prapeta. Di lain pihak, tersisa $c,d \in X$ yang dapat menjadi prapeta. Terdapat 3 anggota $Y$ yang memerlukan prapeta, tetapi hanya ada 2 anggota $X$ yang dapat menjadi prapeta. Berdasarkan Pigeon Hole Principle, terdapat dua anggota $Y$ dengan prapeta yang sama. Namun, hal ini mengakibatkan $f$ bukan sebuah fungsi. Terjadi kontradiksi. Jadi, $f$ adalah fungsi injektif.

Diperoleh $f$ fungsi surjektif sekaligus injektif. Dengan demikian, terbukti bahwa $f$ adalah fungsi bijektif.

Problem 2

Misalkan $X$ dan $Y$ adalah himpunan berhingga, dengan $n(X)=n(Y)$, dan $f$ adalah sebuah fungsi surjektif dari $X$ ke $Y$. Buktikan bahwa $f$ fungsi bijektif.

Solusi

Misalkan $X$ dan $Y$ adalah himpunan berhingga, dengan $n(X)=n(Y)=m$, dan $f$ adalah sebuah fungsi surjektif dari $X$ ke $Y$. Kita akan membuktikan bahwa $f$ fungsi bijektif, dengan menunjukkan bahwa $f$ fungsi injektif.

Andaikan $f$ bukan fungsi injektif. Artinya, terdapat $x_1,x_2 \in X$ dengan $x_1 \neq x_2$, tetapi $f(x_1)=f(x_2)=q$ untuk suatu $q \in Y$. Karena $f$ fungsi surjektif, maka sebanyak $m-1$ anggota $Y$ (selain $q$) harus mempunyai prapeta. Di lain pihak, karena $f$ merupakan fungsi dan $x_1,x_2 \in X$ telah mempunyai peta, maka tersisa sebanyak $m-2$ anggota $X$ yang dapat menjadi prapeta. Karena $m-1 > m-2$, maka berdasarkan Pigeon Hole Principle, terdapat dua anggota $Y$ dengan prapeta yang sama. Namun, hal ini mengakibatkan $f$ bukan sebuah fungsi. Terjadi kontradiksi. Jadi, $f$ adalah fungsi injektif. Dengan demikian, terbukti bahwa $f$ fungsi bijektif.


Bagikan ke:
Click here if solved
Click here to save

Maaf, fitur ini hanya untuk pembaca yang telah terdaftar. Silakan Masuk atau buat akun terlebih dahulu.

Tambah Komentar