OSN 2017 Matematika Hari Pertama (Soal dan Solusi)

Silakan unduh soal dan solusinya di sini: osn2017h1.pdf.

 

Advertisements

Salah mendefinisikan himpunan

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)

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. 🙂

Transitive filtration on (Q,<)

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)

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

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. 🙂