Salah mendefinisikan himpunan

Posted on 28 Feb 2017 by raja.damanik under Uncategorized

Beberapa hari yang lalu saya (akhirnya pernah) mengerjakan soal matematika dengan mendefinisikan kelas/koleksi yang saya pikir merupakan himpunan, namun ternyata bukan. (Ini seakan-akan sebuah pencapaian tersendiri sebagai orang yang belajar logika hahaha). Awalnya saya bingung asisten dosennya menulis komentar bahwa yang saya definisikan itu bukan himpunan, kemudian saya berpikir mengapa itu bukan himpunan. Setelah berdiskusi dengan teman saya, Anna dan Marvin, saat makan siang, baru benar-benar yakin kalau yang saya definisikan bukan himpunan.

Salah satu intuisi paling mudah sesuatu itu bukan himpunan adalah bahwa ia merupakan koleksi yang “terlalu besar” untuk menjadi sebuah himpunan. Misalnya koleksi semua himpunan bukanlah sebuah himpunan. Koleksi semua kardinal atau ordinal juga bukan sebuah himpunan.

Nah, soal yang saya kerjakan ini adalah soal PR Teori Model. Saya membuktikan bahwa jika ada suatu model $B$ terhadap teori $T$ sehingga teori tentang $B$ tidak konsisten dengan $A$ , maka ada suatu formula $\varphi_B$ di teori tentang $B$ yang tidak konsisten juga dengan $A$ . Kemudian, yang saya lakukan adalah mengambil semua formula $\varphi_B$ dari setiap model $B$ dari $T$ , d.k.l.

$S=\{\varphi_B: B \vDash T\}$ .

Dari konstruksi $S$ ini, $S$ bukanlah sebuah himpunan jika $T$ punya model dengan kardinalitas tak hingga. Mengapa? Karena menurut Teorema Skolem-Loewenheim versi upward maupun downward, jika $T$ memiliki suatu model tak hingga, maka untuk sembarang kardinal tak hingga $\kappa$ , maka $T$ akan memiliki model dengan kardinalitas $\kappa$ . Ini berarti, $S$ memuat model dengan hampir semua kardinal. Ini mengindikasikan konstruksi $S$ ini bukan merupakan himpunan.

Terus kenapa kalau $S$ bukan himpunan? Ya, intinya kita belum tentu boleh mengaplikasikan operasi-operasi yang valid untuk himpunan kepada $S$ , seperti tidak bisa mengambil subhimpunan dari $S$ dengan properti tertentu. It is black magic!

Karya tahun 2008 (omg)

Posted on 6 Feb 2017 by raja.damanik under Uncategorized

Tahun 2008 mungkin dikenal dengan masa-masa kealayan. Orang-orang baru mulai mengenal Facebook (dan meninggalkan Friendster).

Bagi saya, tahun 2008 (dan mungkin 2007) adalah masa di mana (selain juga mejadi alay), saya juga mulai menekuni bidang matematika! Saya agak freak waktu itu karena belajar matematika sampai larut malam hampir setiap hari. Well, rumah saya agak jauh ya dari pusat ibu kota Pekanbaru jadi jalan-jalan juga malas dan jarang 😛

Saya ingat dulu suka bikin kompilasi soal-soal olimpiade. Nah, ternyata masih beredar di internet! Berikut adalah tautannya:

https://matematikaict.files.wordpress.com/2009/05/soal-latihan-olimpiade-matematika-100-soal.pdf

OMG. Nostalgia abis!

Meskipun hal ini merupakan hal yang bisa ditertawakan, menurut saya menerjemahkan soal-soal olimpiade dari bahasa asing ke bahasa Indonesia saja sudah sangat berguna. Saya ingat beberapa orang sempat menyapa saya karena mereka menggunakan kompilasi soal-soal di atas untuk latihan. Saya yang sombong sudah lupa dan terus memasang muka terkejut “Oh yaa?” Sekarang sih jadi ingat lagi.

(Padahal sekarang sedang mengerjakan laporan proyek yang deadlinenya 3 jam lagi. Post ini hanya pelarian saja… ckck).

Oh ya, kalau diperhatikan ada hal yang lucu. Nama saya di berkas kompilasi tersebut bukan Raja Oktovin P. D. tetapi Raja Octovin P. D yang menurut saya lucu. Pertama, saya dulu memang suka memaksakan nama saya Octovin, pake c. Karena menurut saya lebih English. LOL. Tapi akhirnya saya menerima kenyataan setelah memastikan di akte kelahiran saya, kalau nama saya pakai huruf k. (Beneran saya periksa dulu). Kemudian, saya merasa agak bodoh tidak menaruh titik di belakang huruf D.

Oke, sudah cukup procrastinating-nya. Melihat pekerjaan saya yang tak seberapa ini membuat saya ingin memproduksi lebih banyak karya lagi. Gak tau apakah akan dipakai orang atau tidak. Saya ga peduli. 🙂

Yes, Douwe Bob, just yes

Posted on 22 Oct 2016 by raja.damanik under Uncategorized

I am in love.

Thanks again for Eurovision for letting person from far-away country to know more singers like Mr. Douwe Bob. Since now I am living in Amsterdam, it’ll be easier for me to meet my idol. See you soon, Douwe Bob.

Transitive filtration on (Q,<)

Posted on 15 Oct 2016 by raja.damanik under Uncategorized

This a bonus question for HW 2 Basic Modal Logic course 2016/2017.

Show that transitive fitration on $(\mathbb{Q},<)$ is a finite list of clusters, maybe interspersed by some irreflexive singletons, no two of which may be adjacent.

What I did is to consider it in four steps.

Finiteness and transitivity

This follows from filtration property (upon finite $\Sigma$ ) and the property that $R$ has as a transitive filtration.

Linearity

For all $a \ne b$ , we have $Rab \vee Rba$ .

Proof. WLOG, $a<b$ . Then, we show that for all $\diamond \phi \in \Sigma$ , we have that if $b \Vdash \phi \vee \diamond \phi$ , then $a \Vdash \diamond \phi$ . If $b \Vdash \phi$ , then because $a<b$ , we have $a \Vdash \diamond \phi$ . If $b \Vdash \diamond \phi$ , then there exists some $c>b$ , such that $c \Vdash \phi$ , and thus becaue $a<b<c$ , $a \Vdash \diamond \phi$ . $\blacksquare$

Moreover, we basically have $< \subseteq R$ .

Properties of irreflexive points

If $\neg Raa$ , then there must be some $\diamond \phi \in \Sigma$ , such that $a$ is the greatest number satisfying $\phi$ .

Proof. If $\neg Raa$ , it means that for some $\diamond \phi \in \Sigma$ , we have $a \Vdash \phi \vee \diamond \phi$ but $a \nVdash \diamond \phi$ . Thus, $a \Vdash \phi$ and $a \nVdash \diamond \phi$ . $\blacksquare$

I also claim no two irreflexive points can be adjacent.

Proof. Suppose that $a<b$ are irreflexive points w.r.t. formula $\alpha$ and $\beta$ , respectively and suppose that they are adjacent in the finite list of filtration. Take any number $c \in (a,b) \cap \mathbb{Q}$ . Clearly, $Rac$ . But $a$ and $b$ are adjacent in the filtration, then we must have $Rbc$ for all such $c$ . This means that for all $\diamond \phi \in \Sigma$ , particularly $\diamond \beta$ , we have $c \vDash \beta \vee \diamond \beta$ implies $b \vDash \diamond \beta$ . But, we have $b \nvDash \diamond \beta$ . $\blacksquare$

Properties of non-simple cluster

Now, we prove that for any reflexive point, it belongs to a non-simple cluster.

Proof. If there is no $\diamond \phi \in \Sigma$ , then all the points belong to the same cluster. If there exist $\diamond \phi$ , then for reflexive points $a$ , $Raa$ means for all $\diamond \phi \in \Sigma$ , $a \vDash \phi \vee \diamond \phi$ implies $a \vDash \Diamond \phi$ . This means, $a$ must not be the greatest number satisfying formula $\phi$ for any $\diamond \phi \in \Sigma$ . Because there is only finite number of singletons (due to the finiteness of $\Sigma$ , we can choose rational number $a_1 >a$ such that all the numbers in $(a,a_1) \cap \mathbb{Q}$ are all reflexive (not a singleton). Now pick any $x \in (a,a_1) \cap \mathbb{Q}$ . Clearly $Rax$ . We show $Rxa$ now. Because it means for all $\diamond \phi \in \Sigma$ , $a \vDash \diamond \phi$ implies $x \vDash \diamond \phi$ , and because $a$ is not a singleton, we then just need to check $a \vDash \diamond \phi$ implies $x \vDash \diamond \phi$ . Suppose $a \vDash \diamond \phi$ but $x \nvDash \diamond \phi$ . This means that there’s a singleton for $\phi \in (a,x)$ which is a contradiction. Thus $a$ belongs to a cluster which also contains at least the whole $(a,a_1) \cap \mathbb{Q}$ .

Because every point in filtration is either reflexive or irreflexive, these properties show that the result of filtration is a finite list of clusters, may be interspersed by some irreflexive singletons, no two of which are adjacent.

This is approximately what I wrote in my homework. I have not got any feedback yet at the time I am writing this. I hope it got almost full marks (like 8 or more).

Membangun kombinator lain dari kombinator S dan K (Bagian 1)

Posted on 5 Aug 2016 by raja.damanik under Uncategorized

Kombinator $S$ dan $K$ dalam CL (combinatory logic) didefinisikan dengan

$SXYZ \equiv XZ(YZ)$

dan

$KXY \equiv X$

untuk sembarang CL-term $X,Y,Z$ .

Secara makna, kombinator $K$ dapat dipandang sebagai fungsi yang menerima dua masukan $X$ dan $Y$ , kemudian memberikan keluaran berupa parameter pertama $X$ . Kombinator $S$ sendiri dapat dipandang sebagai fungsi komposisi (saya baru paham cara menggunakannya setelah membaca buku Lambda Calculus and Combinators – an Introduction oleh J. Roger Hindley dan Jonathan P. Seldin). Fungsi komposisinya kurang lebih begini secara simbol:

$(S(f,g))x = f(x,g(x))$ .

Jika Anda mempelajari logika melalui jalur lain, pasti cukup familiar dengan fungsi $f(x,g(x))$ ini. Dapat dilihat bahwa makna $S$ yang berbentuk $SXYZ \equiv XZ(YZ)$ ini sesuai dengan makna fungsi rekursif ini.

Sekarang, fungsi-fungsi kombinator lain dapat dibangun hanya menggunakan kombinator $S$ dan $K$ ini. Berikut adalah contoh dan cara mencari bentuk ekivalennya.

Contoh 1. Kombinator identitas

Kombinator $I$ identitas memenuhi sifat $IX \equiv X$ . Kombinator $I$ ini dapat ditulis sebagai $SKK$ . Mudah diverifikasi bahwa $SKKX \rhd_w KX(KX) \rhd_w X$ . Namun, bagaimana cara mendapatkan bentuk $SKK$ ini?

Contoh 2. Kombinator komposisi

Kombinator komposisi $B$ berfungsi sebagai berikut:

$(B(f,g))x \equiv f(g(x))$

atau dalam bahasa CL, ditulis $BXYZ = X(YZ)$ . Mudah diverifikasi bahwa $B \equiv S(KS)K$ :

$S(KS)KXYZ \rhd_w (KSX)(KX)YZ \rhd_w S(KX)YZ \rhd_w (KXY)(YZ) \rhd_w X(YZ)$ .

Nah, bagaimana pula mendapatkan bentuk $S(KS)K$ ini?

Contoh 3. Fungsi suka-suka seperti $[x,y,z].y(xz)$ atau $[x,y].xyy$

Kita juga bisa mencari bentuk CL-term dalam $S$ dan $K$ untuk fungsi di atas, misalnya

$[x,y,z].y(xz) \equiv S(S(KS)(K(S(KS)K)))K$

$[x,y].xyy \equiv S(S(KS)(S(S(KS)K)(K(SKK))))(K(SKK))$ .

Sepertinya ribet sekali, ya? Padahal setelah paham cara menggunakan kombinator $S$ ini sama sekali tidak susah ternyata. Kalau mau coba-coba latihan, coba kerjakan ini dulu:

Latihan 1. $[x].xx$

Latihan 2. $[x,y,z].xzy$

Pada bagian selanjutnya, saya akan mencoba menjelaskan cara mendapatkan kombinator ekivalen dalam $S$ dan $K$ saja.

(bersambung…)

Ketaksamaan kompleks ekivalen

Posted on 21 Jul 2016 by raja.damanik under Uncategorized

Misalkan $a,b\in \mathbb{C}$ . Buktikan bahwa $\left| az+b\bar{z} \right|\le 1$ , untuk setiap $z\in \mathbb{C}$ , dengan $\left| z \right|=1$ , jika dan hanya jika $\left| a \right|+\left| b \right|\le 1$ .

Bukti.

(Jika)

Jika $|a|+|b| \le 1$ , maka dengan ketaksamaan segitiga, berlaku $|az+b\overline{z}| \le |a||z|+|b||\overline{z}| = |a|+|b| \le 1$ .

(Hanya jika)

Asumsikan bahwa $|az+b\overline{z}| \le 1$ untuk setiap $z$ dengan $|z|=1$ . Jika $a=0$ atau $b=0$ , ketaksamaan $|a|+|b| \le 1$ terpenuhi. Asumsikan $ab \ne 0$ . Dengan manipulasi aljabar, berlaku $|az^2+b| \le 1$ . Ini juga berakibat $|az+b| \le 1$ untuk setiap $|z|=1$ . Akibatnya
$|a|^2+|b|^2+a\overline{b}z+\overline{a}b\overline{b} \le 1 \quad (*)$ .
Ambil $z=\dfrac{|a||b|}{a\overline{b}}$ , perhatikan bahwa $|z|=1$ dan ketaksamaan $(*)$ menjadi $|a|^2+|b|^2+2|a||b| \le 1$ yang berakibat $|a|+|b| \le 1$ .

Terbukti.

Refleksi.

Soal yang cukup rutin kecuali ide untuk kalimat terakhir yang mengambil $z=\dfrac{|a||b|}{a\overline{b}}$ harus sedikit licik. 🙂

Kronologi peradaban Islam & pertanyaan yang belum terjawab

Posted on 6 Jul 2016 by raja.damanik under Uncategorized

Saat ini saya sedang mencoba mengikuti course An Introduction to Islamic Civilization dari Bibliotecha Alexandrina di MIT edX. Kuliah pertamanya adalah tentang kronologi singkat peradaban Islam, sehingga bisa “meraba-raba” posisi waktu dan jarak antar kejadian-kejadian penting selama peradaban Islam. Saya juga tuliskan beberapa pertanyaan saya di sini untuk further research yang secara berangsur-angsur akan saya jawab sendiri selama belajar. Sepertinya tidak sulit untuk dicari dengan pencarian sederhana di Google tapi kalau ada yang mengetahui jawabannya (dan sumbernya), bolehlah dibantu jawab hehehe.

Berikut adalah lini waktu peradaban Islam.

570 M: Birth of Prophet Muhammad
Sepertinya, sejarawan sepakat bahwa kelahiran Nabi Muhammad sebagai penanda mulainya peradaban Islam. Saya jadi bertanya mengapa ya? Kemudian jika memang dimulainya sejak Nabi Muhammad, apa bisa saya simpulkan kejadian-kejadian sebelum kelahiran Nabi Muhammad tidak ada sangkut pautnya dengan agama Islam? Artinya, Islam dapat dianggap “totally unknown” sebagai sebuah set ajaran agama sebelum masa ini? Apakah ini berarti sejarawan menganggap bahwa nabi-nabi sebelum Nabi Muhammad pada dasarnya mengajarkan nilai-nilai yang bukan Islam (maksudnya, nilai-nilai tidak dipandang sebagai satu kesatuan dalam Islam) namun lebih ke nilai-nilai yang terpisah? Mungkin tidak ada historical evidence tentang pewahyuan yang diperoleh nabi-nabi sebelumnya berkaitan dengan Islam.
610 M: Muhammad’s call to be the Seal of the Prophets on Mount Hira, and the beginning of Revelation of the Qur’an
Berarti panggilan ini ada saat Nabi Muhammad berumumr 40 tahun. Kemudian Gunung Hira, menurut Wikipedia, jaraknya hanya 3 km dari Mekah. Ga jauh ya hehehe. Ini fotonya:

Sumber: Wikipedia

Mungkin yang sudah pernah umroh ke sana mengunjungi tempat ini.Tapi kok sepertinya banyak vandalisme ya di batu-batu gunung ini. Hadeh. Udah kayak Indonesia aja. Kemudian, pertanyaan saya terkait masa ini adalah kalau wahyu Al-Quran dimulai saat Nabi Muhammad berumur 40 tahun, apa saja yang dilakukan Nabi Muhammad selama 40 tahun? Jika ia mengajarkan sesuatu, bersumber dari mana?
622 M: Prophet’s Hijrah from Makkah (Mecca) to Madina (Medina), whose importance is commemorated by the Islamic calendar, which counts years from this point (A.H.)
Jadi ini saat Nabi Muhammad berumur 50-an dan sepertinya Islam sudah memiliki pengikut dan sepertinya pengikutnya juga ikut hijrah. Pertanyaan yang muncul adalah penyebab hijrahnya apa ya? Terus kok ini kuliahnya kontradiktif dengan yang dibilang di Wikipedia ya karena kata Wikipedia kalendar Islam tidak dimulai sejak hijrah ini. Hmmm. Jadi bagaimana sebenarnya penentuan kalender Islam? Berapa lama? Kenapa lebaran dan mulai puasa tiap tahun harus dirapatkan dulu?
Oh ya Medinah katanya nama asli kotanya adalah Yathrib yang kemudian diberi nama “the city of the prophet” kemudian the prophet-nya dihilangkan sehingga jadinya “the city” aja. Cool.
630 M: Muhammad’s conquest of Mecca, and rededication of the Ka’ba to monotheistic worship
Wow. Jadi tidak sampai 10 tahun kemudian, Mekah sudah kembali di bawah kekuasaan umat Islam. Kemudian, jadi bertanya lagi, siapa sebenarnya yang menguasai Mekah waktu itu dan Kabah digunakan sebagai apa ya?
632 M: Death of Muhammad
Berarti Nabi Muhammad meninggal saat berumur sekitar 60 tahun ya.
632-661 M: Period of the “Rightly Guided Caliphs” (Abu Bakr, Umar, Uthman, Ali), when the Umma (Islamic community) was led by the Companions of the Prophet. This period is marked by Muslims consolidating their power in Arabia, and the conquests of Syria, Palestine, Egypt, Iraq, Persia—all of which would come to constitute the heart of the Islamic Empire.
Setelah Nabi Muhammad meninggal, katanya ada empat khalifah pertama, yang biasa disebut Rashidun. Yang dipilih oleh lembaga tertentu atau pendahulunya. Ini berlangsung sampai 661 M yang berarti berjalan selama 30 tahun. Pendek juga ya.
Kemudian, katanya ada juga Rashidun di Baghdad. Apa bedanya ya? Kemudian, apa yang terjadi setelah keempat Rashidun ini selesai memimpin? Kalaupun masih ada khalifah, apa yang berbeda dengan keempat khalifah ini? Apa mereka ini yang ada saat Nabi Muhammad masih hidup kali ya?
Oh ya lini waktunya kurang lebih seperti ini:

Sumber: Wikipedia

661-750 M: Muawiyah, founder of the Umayyad dynasty, becomes the caliph and moves the capital from Mecca to Damascus
Belum pernah dengan Muawiyah sama sekali. Jadi, ini benar-benar informasi baru hehehe. Apa ya signifikansi dinasti Umayyad? Sepertinya ini masa-masa Islam menyebar hingga ke Eropa kali ya?
669 M: The Muslim conquest reaches Morocco in North Africa
Kenapa Maroko perlu dimasukkan lini waktu ini? Apa signifikansinya?
672 M: Muslims under Muawiyah capture the Island of Rhodes
Hmmm ini pulau di Yunani. Apa ya yang mereka lakukan di pulau ini? Sepenting apakah pulau ini? Maklum saya nubitol nih belajar sejarah hehe.
711 M: With the conquest of Egypt, Spain and North Africa, the Persian empire and most of the old Roman world came under the Islamic rule. Muslims began the conquest of Sindh in Afghanistan.
Oh saya baru tahu kerajaan Islam pernah menguasai daerah-daerah Kerajaan Romawi ya. Keren. Anyway, kayaknya Sindh itu adanya di Pakistan deh bukan Afghanistan.
750 M: Fall of the Umayyads and the rise of the Abbasid Dynasty, which conquered the Umayyads and ruled from Baghdad until the Mongol conquest in 1258 CE
Berarti dinasti Umayyad sudah berdiri selama 89 tahun. Tidak terlalu panjang ya, ternyata. Kemudian bagaimana Abbasid bisa menguasai dinasti Umayyad, ya? Kemudian, sepertinya dinasti Abbasid ini panjang sekali hidupnya, yaitu sekitar 508 tahun. Wow.
968-1171 M: The Fatimids, a “Sevener” Shi’ite Dynasty, founds the city of Cairo and rules Egypt
Wah, ada muncul Syiah di masa ini. Lumayanlah nanti belajar sejarah hubungan Islam Sunni dan Syiah hehe dan kontribusi apa kedua aliran ini berikan bagi dunia. Bagaimana daerah kekuasaan Fatimid dan juga Umayyad tersebar dan bagaimana efek geografisnya bagi masing-masing? Bagaimana konflik-konflik dari zaman ke zaman bisa terselesaikan? Jangan-jangan dari dulu permasalahannya masih sama saja? 🙂
1099 M: The Crusaders take Jerusalem
Katanya perang salib terjadi berkali-kali sejak abad ke-11 hingga ke-15. Kadang menang dan kadang kalah. Apa saja ya dampaknya bagi peradaban Islam?
1187 M: Saladin (the most famous of the Ayyubids, the dynasty that toppled the Fatimids in Egypt in 1169 CE) retakes Jerusalem at Battle of Hattin
Yerusalem kembali lagi di bawah kekuasaan pemerintahan Islam. Sepertinya Saladin merupakan orang hebat karena berhasil menghentikan kekuasaan Fatimid di Mesir kemudian mengambil kembali Yerusalem. Terus, kenapa dinasti Ayyubid tiba-tiba muncul ya tapi tidak di-mention di kronologi ini. Apa hubungannya dengan dinasti Abbasid?
1258 M: The Mongol conquest causes the fall of the Abbasid Dynasty
Wah Mongolia bisa mengganggu juga, ya. Daerah mana yang menerima dampak serangan dari Mongolia ini? Bagaimana pemerintahan Islam berlanjut setelah dinasti Abbasid berlangsung? Padahal kan baru benar-benar selesai tahun 1492 yang artinya masih 234 tahun. Bagaimana bentuk pemerintahannya?
1492 M: End of the Period of the Islamic rule of Spain
Katanya Andalusia (Al-Andalus) adalah daerah di Spanyol, Portugis, dan sekitarnya yang saat itu di bawah pemerintahan Islam namun tetap terdapat harmoni dalam masyarakatnya berupa kemajemukan masyarakat non-Muslim di dalam Andalusia. Ini menghasilkan karya-karya seni misalnya yang merupakan perpaduan budaya barat dan timur. Wah, saya jadi penasaran pengen ke sana. 🙂 Katanya Andalusia berakhir karena serangan dari kerajaan Eropa yang mulai bangkit lagi.

Lukisan orang Yahudi dan orang Islam bermain catur. (Sumber: Wikipedia)

Refleksi

Sangat menarik untuk dipelajari lebih lanjut. Mohon koreksinya jika Anda kebetulan membaca dan menemukan kesalahan (dan peduli). 🙂