Latihan Tentang Ordinal

Soal-soal ini diambil dari kuliah di MIT edX yang berjudul Paradox and Infinity. Ini adalah suatu kebetulan karena saya sedang belajar tentang Teori Himpunan secara independen.

Latihan 0. Tentukan apakah himpunan-himpunan berikut ini (i) well-ordered oleh \in (ii) set-transitive:

  1. \displaystyle \emptyset
  2. \cal{P}(\cal{P}(\cal{P}(\emptyset)))
  3. \cal{P}(\cal{P}(\cal{P}(\emptyset)))-\{ \emptyset\}
  4. \cal{P}(\cal{P}(\cal{P}(\emptyset)))- \{ \{ \emptyset \} \}
  5. \cal{P}(\cal{P}(\cal{P}(\emptyset))) - \{ \{ \{ \emptyset \} \} \}.

Latihan 1. Tunjukkan bahwa setiap anggota dari ordinal adalah ordinal.

Latihan 2. Jika \alpha adalah ordinal, kita definisikan \alpha' = \alpha \cup \{ \alpha \}. Tunjukkan bahwa \alpha' juga merupakan ordinal.

Latihan 3. Tunjukkan bahwa jika \alpha dan \beta merupakan ordinal dan beberapa anggota \beta bukan anggota dari \alpha, maka \alpha \in \beta.

Latihan 4. Tunjukkan bahwa jika \alpha dan \beta merupakan ordinal yang berbeda, maka \alpha \in \beta atau \beta \in \alpha.

Latihan 5. Tunjukkan bahwa jika A merupakan himpunan ordinal-ordinal, maka \displaystyle \bigcup (A) merupakan ordinal.


Latihan 0.

  1. Karena \emptyset tidak punya anggota, maka jelas ia set-transitive. Kemudian, karena subhimpunan dari \emptyset hanyalah \{\}, maka tidak perlu diperiksa karena syaratnya hanya untuk himpunan tak kosong.
  2. Perhatikan bahwa
    \cal{P}(\cal{P}(\cal{P}(\emptyset))) = \{ \emptyset, \{ \emptyset \}, \{ \{ \emptyset \} \}, \{ \emptyset, \{ \emptyset \} \} \}.
    Himpunan \cal{P}(\cal{P}(\cal{P}(\emptyset))) merupakan himpunan yang set-transitive, dapat diperiksa satu per satu bahwa:
    himpunan \emptyset tidak punya anggota, sehingga tidak ada yang perlu diperiksa,
    anggota \{ \emptyset \}, yaitu \emptyset merupakan anggota \cal{P}(\cal{P}(\cal{P}(\emptyset))),
    anggota \{ \{ \emptyset \} \}, yaitu \{ \emptyset \} merupakan anggota \cal{P}(\cal{P}(\cal{P}(\emptyset))) juga, dan
    anggota \{ \emptyset, \{ \emptyset \} \} juga merupakan anggotaa \cal{P}(\cal{P}(\cal{P}(\emptyset))).
    Namun, himpunan \cal{P}(\cal{P}(\cal{P}(\emptyset))) bukan merupakan himpunan yang well-ordered, karena subhimpunan \{ \{ \{ \emptyset \} \}, \{ \emptyset, \{ \emptyset \} \} \} tidak memiliki anggota minimal.
  3. Perhatikan bahwa:
    \cal{P}(\cal{P}(\cal{P}(\emptyset))) - \{ \emptyset \}= \{ \{ \emptyset \}, \{ \{ \emptyset \} \}, \{ \emptyset, \{ \emptyset \} \} \}.
    Jelas himpunan ini tidak set-transitive karena anggota \{ \emptyset \}, yaitu \emptyset bukan anggotanya. Selain itu, himpunan ini juga tidak well-ordered dengan memandang subhimpunan yang sama dengan contoh 2 di atas.
  4. Perhatikan bahwa:
    \cal{P}(\cal{P}(\cal{P}(\emptyset))) - \{ \{ \emptyset \} \}= \{ \emptyset, \{ \{ \emptyset \} \}, \{ \emptyset, \{ \emptyset \} \} \}.
    Jelas bahwa himpunan ini tidak set-transitive karena salah satu anggota dari \{ \emptyset, \{ \emptyset \} \}, yaitu \{ \emptyset \} bukan anggotanya. Selain itu, himpunan ini juga tidak well-ordered dengan memandang himpunan yang sama dengan contoh 2 di atas.
  5. Perhatikan bahwa:
    \cal{P}(\cal{P}(\cal{P}(\emptyset))) - \{ \{ \{ \emptyset \} \} \}= \{ \emptyset, \{ \emptyset \}, \{ \emptyset, \{ \emptyset \} \} \}.
    Perhatikan bahwa himpunan ini set-transitive karena dapat diperiksa bahwa:
    himpunan \emptyset tak punya anggota, sehingga tidak ada yang perlu diperiksa,
    anggota himpunan \{ \emptyset \}, yaitu \emptyset, ada di himpunan \cal{P}(\cal{P}(\cal{P}(\emptyset))) - \{ \{ \{ \emptyset \} \} \}, dan
    anggota himpunan \{ \emptyset, \{ \emptyset \} \}  juga ada di \cal{P}(\cal{P}(\cal{P}(\emptyset))) - \{ \{ \{ \emptyset \} \} \}.
    Himpunan ini juga well-ordered karena himpunan ini memiliki linear order \emptyset \in \{ \emptyset \} \in \{ \emptyset, \{ \emptyset \} \}.

Latihan 1.

Misalkan x \in \alpha. Akan ditunjukkan bahwa x ordinal: well-ordered and set-transitive.

Bukti x set-transitive:

Misalkan x tidak set-transitive, maka terdapat y \in x dan z \in y sehingga z \notin x. Karena \alpha transitive, maka y \in \alpha. Akibatnya, berlaku pula z \in \alpha. Namun, karena \alpha well-ordered, maka subhimpunan \{ z, x\} harus memiliki anggota minimal. Karena diasumsikan z \notin x, maka haruslah x \in z. Akibatnya, x \in z \in y \in x yang mengakibatkan kontradiksi dengan sifat \in yang irrefleksif dan transitif.

Bukti x well-ordered:

Misalkan p \subseteq x. Akan ditunjukkan bahwa p memiliki anggota minimal. Perhatikan bahwa untuk setiap y \in p, berlaku y \in \alpha sehingga p \subseteq \alpha. Akibatnya, karena \alpha ordinal, maka p juga memiliki anggota minimal.

Latihan 2.

Akan ditunjukkan bahwa \alpha' = \alpha \cup \{ \alpha \} merupakan ordinal.

Bukti \alpha' set-transitive:

Jika x \in \alpha', akan ditunjukkan jika y \in x, maka y \in \alpha'. Perhatikan bahwa x \in \alpha atau x = \alpha. Jika x \in \alpha, maka karena \alpha ordinal, maka jika y \in x, juga berlaku y \in \alpha. Namun, ini berarti y \in \alpha'. Jika x = \alpha, maka jelas x \in \alpha' dari definisi.

Bukti \alpha' well-ordered:

Jika p \subseteq \alpha', akan ditunjukkan bahwa p  memiliki anggota minimal. Jika p \subseteq \alpha, maka hal ini jelas terpenuhi. Misalkan q \subseteq \alpha sehingga p = q \cup \{ \alpha \}. Karena \alpha ordinal, maka q punya anggota minimal, sebut saja x_q. Karena x_q \in p \subseteq \alpha, maka x_q \in \alpha dan juga x_q \in x untuk setiap x \in q. Akibatnya x_q juga anggota  minimal p.

Latihan 3.

Perhatikan bahwa himpunan p=\alpha - \beta bukan himpunan kosong, sehingga karena p \subseteq \alpha, di mana \alpha suatu ordinal, haruslah p punya anggota minimal, sebut saja x_p.

Pertama, akan ditunjukkan bahwa x_p \subseteq \beta. Misalkan x \in x_p. Perhatikan bahwa x_p \in \alpha, sehingga x \in \alpha juga. Jika seandainya x \notin \beta, maka akan berlaku x \in \alpha - \beta yang akibatnya x \in p. Karena x_p merupakan anggota minimal, maka berlaku x_p \in x. Namun, dari permisalan berlaku x \in x_p sehingga tidak mungkin. Akibatnya, haruslah x \in \beta. Jadi, terbukti bahwwa x_p \subseteq \beta.

Selanjutnya, akan ditunjukkan bahwa \beta \subseteq x_p. … (bersambung)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s