Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas tentang Teorema Komposisi dalam Matematika Diskrit, khususnya pada topik Relasi. Teorema tersebut menyatakan bahwa relasi pada himpunan A adalah relasi transitif jika dan hanya jika R pangkat n merupakan subset dari R untuk setiap n. Untuk membuktikannya, digunakan dua arah dengan induksi matematik. Selain itu, video juga menjelaskan konsep relasi n-ary yang merupakan sub-himpunan dari direct product dari N himpunan, dengan domain A1 sampai An dan derajat N. Contoh penerapan konsep tersebut adalah relasi pada Z pangkat tiga yang memeriksa apakah setiap triple ABC membentuk arithmetic progression.

Sekarang, kalau R punya sifat tertentu, misalnya dia punya relasi transitif,

apa sih kaitannya si R tadi yang kita komposisikan?

Itu ternyata R pangkat n-nya artinya di komposisi sebanyak n kali untuk n, 1, 2, 3 dan seterusnya,

itu merupakan subset dari R, begitu juga sebaliknya.

Jadi, teoremanya mengatakan relasi pada himpunan A adalah relasi transitif

jika dan hanya jika R pangkat n itu subset dari R untuk setiap n, 1, 2, 3 dan seterusnya,

Karena di sini ada jika dan hanya jika, kita harus buktikan dua arah,

kalau kita tahu dia mempunyai relasi yang transitif,

kita harus buktikan R pangkat n itu subset dari R

dan kalau R pangkat n itu subset dari R, kita harus buktikan dia transitif.

Kita buktikan yang pertama yang diketahui adalah R pangkat n itu subset dari R,

mau dibuktikan R-nya itu mempunyai sifat transitif.

Jadi, kalau kita lihat n-nya 2 berarti kan R kuadratnya itu subset dari R,

Kalau kita punya AB anggota R dan BC anggota R,

maka dengan komposisi kita akan dapat AC anggota R

dan ini berlaku untuk setiap AB dan BC di R.

Jadi, kalau B sama B yang satu sebagai elemen kedua,

Sehingga kita mempunyai sifat transitif di sini,

Jadi, kita sudah membuktikan R-nya mempunyai sifat transitif.

kalau kita tahu relasinya itu bersifat transitif,

apakah R pangkat n itu subset dari R untuk n 1 2 3 dan seterusnya?

Untuk membuktikannya, kita menggunakan induksi matematik.

Untuk n sama dengan 1 itu jelas karena R itu subset dari R.

Kemudian, asumsikan bahwa R pangkat n itu subset dengan R

di mana n adalah suatu bilangan bulat positif.

Sekarang kita mau cek apakah R pangkat n plus 1 itu juga subset dari R.

Kita asumsikan AB itu elemen dari R pangkat n plus 1.

R pangkat n plus 1 itu adalah Rn dikomposisi dengan R.

sehingga AX-nya anggota R, XB-nya anggota R pangkat n.

Berarti kalau AX di R, XB di Rn, maka AB-nya itu ada di R.

Dan Rnya transitif, jadi kalau AX anggota R,

Sehingga AB yang tadi kita ambil dari R pangkat n plus 1

Jadi, kita sudah membuktikan R pangkat n plus 1 itu subset dari R.

Jadi, ini ada kaitannya antara komposisi dengan sifat transitif.

Tadi kita melihat ada relasi yang diulang beberapa kali,

dan biasanya kita cuma pakai contoh-contoh yang sebelumnya itu A sama B saja.

tidak cuma dua himpunan, bisa tiga himpunan, empat himpunan, lima himpunan, sampai N himpunan.

Dan relasinya akan kita sebut sebagai n-ary,

kalau yang sebelumnya itu binar atau binary.

Kita punya A1, A2 sampai An itu himpunan,

makanya relasi n-ary pada himpunan-himpunan ini adalah

sub-himpunan dari A1 cross A2 cross sampai An.

Jadi, direct product dari N himpunan tersebut.

itu istilah yang mungkin bisa kita pakai.

misalnya relasinya itu relasi pada Z cross Z atau Z pangkat tiga di sini

yang kalau kita kaitkan dengan aljabar linear yang ruang R2 dan R3,

tapi kita punya R pangkat N di sini tidak berarti ruang real atau ruang dimensi tiga,

ini R pangkat tiga itu kaitan komposisi relasi.

Kalau misalnya tadi R-nya relasinya itu pada himpunan Z cross Z cross Z,

isinya adalah semua triple ABC dengan AB dan C membentuk arithmetic progression,

arithmetic progression itu artinya selisih antara B dengan A itu akan sama dengan selisih C dengan A,

dalam arti B-nya itu akan sama dengan A plus K,

jadi nanti ada A kemudian A plus K, A plus 2K dan seterusnya.

Sehingga nanti kita bisa lihat B-A itu selisihnya akan sama dengan K,

Kita lihat misalnya 1, 3, 5 itu anggota relasi ini tidak?

Kita punya tiga elemen sekarang bukan dua elemen lagi,

jadi triple sekarang bukan pasangan terurut,

1, 3, 5 dan kita lihat selisihnya antara 1, 3, 5 itu 2,

berarti 3 itu 1 tambah 2, 5 itu 1 tambah 2 kali 2,

tapi kalau 2, 5, 9 itu bukan ada di R karena selisihnya beda,

2 sama 5 itu selisihnya 3, 5 sama 9 itu selisihnya 4,

jadi kita tidak bisa bilang dia itu memenuhi arithmetic progression.

Dan ini karena kita punya tiga elemen itu anggota dari Z pangkat ini,

dia berarti derajatnya 3 dan domennya adalah semua bilangan bulat.