Himpunan Takhingga

Untuk n Î N, didefinisikan Nn = {1, 2, 3, …, n}. Sebagai contoh, N10 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} dan N100 = {1, 2, 3, …, 100}.

Definisi 2.6.1 Misalkan A dan B adalah himpunan. Himpunan A dikatakan ekivalen dengan B, ditulis A» B, jika ada bijeksi dari A ke B.

Konsep ekivalen memenuhi sifat-sifat berikut.

1)   A » A,                                                  (sifat refleksif)

2)   Jika A » B, maka B » A,                       (sifat simetris)

3)   Jika A » B dan B » C, maka A » C,      (sifat transitif)

dan

Sebagai contoh, misalkan

A = {1, 2, 3, 4, …, 25}

B = {2, 4, 6, 8, …, 50}.

Maka fungsi f dengan domain A dan kodomain B dengan f(x) = 2x, untuk setiap x Î A adalah fungsi bijeksi. Dengan demikian, maka A » B.

Definisi 2.6.2 Misalkan A himpunan.

(1)       A disebut finit (berhingga) jika A = 0/  atau A » Nn, untuk suatu n Î N. Selain itu A disebut infinit (takberhingga).

(2)       A disebut denumerable (enumerable) jika A » N.

(3)       A disebut countable jika A finite atau A denumerable.

Sebagai contoh misalkan S ={12, 22, 32, …}. Maka fungsi f(n) = n2 adalah fungsi satu-satu dari S pada N. Jadi S » N dan dengan demikian S countable. Selanjutnya akan ditunjukkan bahwa himpunan bilangan bulat Z adalah countable. Untuk menunjukkan bahwa N » Z, dapat juga dilakukan dengan menunjukkan bahwa Z » N. Definisikan fungsi f dari Z ke N dengan

⎧

⎪

f (x ) = ⎨

n ,      (n 2

genap)

⎪- (n - 1) , (n

ganjil)

⎩⎪   2

Maka fungsi f adalah bijeksi dari Z ke N. Dengan demikian, maka Z » N. Jadi Z

adalah countable.

Definisi 2.6.3 Misalkan A adalah himpunan. Barisan di A adalah fungsi f dari N ke A. Untuk masing-masing nÎN, misalkan xn = f(n). Maka xn disebut suku ke-n dari barisan f.

Untuk lebih jelasnya, barisan dinotasikan dengan

(x )¥

atau (x ) atau (x ⏐ n Î N)

n  n =1                   n                    n

daripada menggunakan notasi f. Perlu dibedakan antara notasi barisan (xn ⏐ n Î N) dengan notasi {xn ⏐ n Î N} yang menyatakan range dari barisan. Sebagai contoh (1 – (-1)n) menyatakan barisan f dengan

Di sisi lain,

f(n) = x = 1 – (-1)n.

n

{1 – (-1)n⎮ n Î N} = { 2, 0}.

Sesuai definisi, himpunan A dikatakan denumerable jika terdapat fungsi bijeksi f dari N pada A. Jadi,

A = Rf = {xn ⏐ n Î N}.

Barisan f ini disebut enumerasi dari himpunan A, yakni {xn ⏐ n Î N}  dengan

xn ¹ xm jika n ¹ m.

Berikut ini disajikan beberapa teorema, yang buktinya diserahkan kepada pembaca sebagai latihan.

Teorema 2.6.4 Sebarang himpunan bagian dari himpunan berhingga adalah berhingga.  Teorema 2.6.5 Sebarang himpunan bagian takberhingga dari himpunan denumerable adalah denumerable.

Teorema 2.6.6 Jika f adalah fungsi dari N pada A, maka A adalah countable.

Teorema 2.6.7 Gabungan sejumlah berhingga himpunan berhingga adalah berhingga.

Teorema 2.6.8 Gabungan sejumlah takberhingga himpunan countable adalah countable.

Teorema 2.6.9 Himpunan bilangan rasional Q adalah countable.

Bukti: Untuk masing-masing m Î N, misalkan

n

Em = {

m

Maka Em, adalah countable, maka

⎢n Î Z}.

adalah countable. ◘

¥

Q = UEm

m =1

Meskipun himpunan bilangan rasional Q adalah countable, himpunan bilangan real R tidak countable. Untuk menunjukkan bahwa R uncountable, cukup ditunjukkan bahwa interval tertutup [0, 1] adalah uncountable. Perlu diketahui bahwa setiap x Î [0, 1] dapat dinyatakan sebagai bilangan decimal

x = 0, a1a2a3a4…

dengan

an  Î {0, 1, 2, 3, .., 9}.

Teorema 2.6.10 Interval tertutup [0, 1] adalah uncountable.

Bukti: Karena terdapat sejumlah takhingga bilangan rasional dalam interval [0, 1], maka [0, 1] adalah takberhingga. Dengan demikian cukup ditunjukkan

bahwa [0, 1] adalah tidak denumerable. Andaikan [0, 1] adalah denumerable.

Misalkan x1, x2, x3, x4, … adalah enumerasi dari [0, 1]. Maka

x1 = 0, a11a12a13a14… x2 = 0, a21a22a23a24… x3 = 0, a31a32a33a34… x4 = 0, a41a42a43a44… M

Definisikan y = 0, y1y2y3y4…. sebagai berikut.

y1 = 3, jika a11 ³ 5 dan y1 = 7, jika a11 < 5. y2 = 3, jika a22 ³ 5 dan y2 = 7, jika a22 < 5. y3 = 3, jika a33 ³ 5 dan y3 = 7, jika a33 < 5.

M

Maka y Î [0, 1] tetapi y ¹ xn, untuk setiap n Î N. Kontradiksi dengan

x1, x2, x3, x4, …

sebagai enumerasi dari [0, 1]. Disimpulkan bahwa [0, 1] tidak denumerable. Dengan demikian, maka [0, 1] adalah uncountable. ◘

Karena interval tertutup [0, 1] adalah uncountable, maka R uncountable. Fakta

bahwa R uncountable membawa implikasi bahwa R\Q juga uncountable. Jika

R\Q  countable,  dan  diketahui  bahwa  Q  countable,  maka  akan  diperoleh  R

countable. Hal ini tidak mungkin karena R uncountable.

Latihan 2.6.

1.     Buktikan jika S dan T denurable maka S È T

denurabel.

2.     Buktikan jika himpunan T1  denurabel jika dan hanya jika terdapat suatu fungsi bijeksi dari T1 surjektif himpunan T2.

3.     Gunakan     induksi     matematika   untuk    membuktikan    jika                  himpunan                     S

mempunyai n anggota maka P(S) mempunyai 2n anggota