BAB
I
HIMPUNAN
DAN FUNGSI
- HIMPUNAN
Jika
A
adalah suatu himpunan, dan x
adalah suatu anggota A,
maka kita menuliskannya dengan :
x
A
Jika
x
bukan anggota A,
maka kita menuliskannya dengan :
xA
Jika
semua anggota himpunan A
merupakan anggota himpunan B,
maka himpunan A
adalah himpnan bagian dari B,
ditulis:
AB
1.1.1
Contoh
- Misalkan A = {1,3,4,5}, maka 4A dan 6A
- Misalkan A = {a,c,d} dan B = {a,b,c,d,e,f}, maka AB
Suatu
himpunan dapat dinyatakan dengan dua cara, yaitu mendaftar semua
anggota atau dengan menyebutkan sifat keanggotaannya. Jika himpunan A
yang unsur-unsurnya x,
mempunyai sifat P(x)
maka himpunan itu dituliskan dengan:
A
= {x
|
P(x)}
atau
A
= {x
S
|
P(x)}
Apabila
himpunan tersebut merupakan himpunan bagian S.
Berikut
disajikan beberapa notasi himpunan yang sering muncul.
- Himpunan bilangan asli dinyatakan dengan:
N
= {1,2,3,4, ...}
- Himpunan bilangan bulat dinyatakan dengan:
Z
= {..., -2,-1, 0, 1, 2,..}
- Himpunan bilangan rasional dinyatakan dengan:
Q
= {|
m,nZ
dan n
0}
- Himpunan bilangan real dinyatakan dengan:
R
= {x
| x
bilangan real}
1.1.2
Definisi
Dua
himpunan
A dan
B dikatakan
sama, jika keduanya memuat elemen yang sama.
Dengan
demikian, untuk menunjukkan bahwa A
= B,
maka harus ditunjukkan bahwa AB
dan BA
1.1.3
Definisi
a.
Gabungan dua himpunan A
dan B
adalah:
AB
= {x
: xA
atau xB}
b.
Irisan dua himpunan A
dan B
adalah:
AB
= {x
: xA
dan xB}
c.
Selisih dua himpunan A
dan B
adalah:
A
– B
= A|B
=
{x
: xA
dan xB}
- (ii) (iii)
Gambar
1.1
Pada
gambar 1.1 diatas, daerah yang diarsir pada (i) menunjukkan AB,
daerah yang diarsir pada (ii) menunjukkan AB,
dan daerah yang diarsir pada (iii) menujukkan A
– B.
Himpunan yang tidak memiliki anggota disebut himpunan kosong,
disimbolkan dengan “Ø” atau “{}”. Dua himpunan A
dan B
dikatakan saling lepas apabila himpunan A
dan himpunan B
tidak
memiliki anggota persekutuan, atau AB
= Ø.
1.1.4
Teorema
Jika
A,
B,dan
C adalah
himpunan, maka:
(a).
AB
= BA
(b).
AB
= BA
(c).
(AB)C
= A(BC)
(d).
(AB)C
= A(BC)
(e).
(AB)C
= (AC)(BC)
(f).
A
– (BC)
= (A
– B)(A
– C)
(g).
A
– (BC)
= (A
– B)(A
– C)
Sifat
(a) dan (b) merupakan sifat komutatif gabungan dan irisan dua
himpunan, sifat (c) dan (d) merupakan sifat assosiatif gabungan dan
irisan himpunan, sifat (e) merupakan sifat distributif gabungan
terhadap irisan himpunan, sedangkan (f) dan (g) merupakan hukum De
Morgan.
Selanjutnya
akan dibahas bukti dari sifat diatas, dalam hal ini akan dibuktikan
sifat bagian (d), (e) dan (f) sedangkan (a), (b), (c) dan (g)
diserahkan kepada pembaca untuk membuktikan sendiri.
Bukti.
d.
Untuk membuktikan bahwa (AB)C
= A(BC),
maka harus ditunjukkan bahwa (ABCA(BC)
dan A(BC)
(AB)C,
dengan cara sebagai berikut.
Ambil
sebarang x(AB)C,
maka x(AB)
dan xC.
Karena x(AB)
maka xA
dan
xB.
Jadi xA
dan juga xB
dan C,
atau dengan kata lain xA
dan xBC.
Ini berarti xA(BC).
Dengan demikian (AB)CA(BC).
Sebaliknya
ambil sebarang xA(BC),
maka xA
dan x(BC).
Karena x(BC)
maka xB
dan
xC.
Jadi xA
dan B
serta xC,
atau dengan kata lain xAB
dan
xC.
Ini berarti x(AB)C.
Dengan demikian A(BC)(AB)C.
Karena
(AB)CA(BC)
dan A(BC)(AB)C,
maka dapat dikatakan (AB)C
= A(BC).
e. Ambil
sebarang x(AB)C,
maka xA
dan
B
atau xC.
Ini berarti juga xA
atau
C
dan
xB
atau C,
atau dengan kata lain xAC
dan xBC.
Akibatnya x(AC)(BC).
Dengan demikian diperoleh (AB)C
(AC)(BC)
Sebaliknya,
ambil sebarang x(AC)(BC),
maka xAC
dan xBC,
atau dengan kata lain xA
atau
C
dan xB
atau
C.
Ini berarti bahwa x
A dan
B
atau xC.
Akibatnya x(AB)C.
Dengan demikian diperoleh (AC)(BC)
(AB)C.
Karena
(AB)C
(AC)(BC)
dan juga (AC)(BC)
(AB)C,
maka dapat dikatakan (AB)C
= (AC)(BC)
f.
Ambil sebarang xA
– (BC),
maka xA
dan xBC.
Karena xBC,
berarti xB
dan xC.
Dengan kata lain xA
dan xB
yang berarti xA
– B
dan juga
xA
dan xC,
yang berarti xA
– C.
Dengan demikian diperoleh xA
– B
dan xA
– C,
atau x(A
– B)(A
– C).
Jadi A
– (BC)
(A
– B)(A
– C)
Sebaliknya,
ambil sebarang x(A
– B)(A
– C)
, maka xA
– B
dan xA
– C.
Karena xA
– B,
berarti xA
dan xB
serta xA
– C,
berarti xA
dan xC.
Jelas bahwa xA
serta xB
dan xC
atau dengan kata lain xA
dan xBC.
Dengan demikian diperoleh xA
– (BC).
Jadi (A
– B)(A
– C)
A
– (BC)
Karena
A
– (BC)
(A
– B)(A
– C)
dan juga (A
– B)(A
– C)
A
– (BC),
maka dapat dikatakan (AB)C
= (AC)(BC).
Berikut
ini akan diberikan definisi tentang direct image dan invers image
suatu fungsi.
1.1.5
Definisi
Misalkan
f
: A
B adalah
fungsi dengan domain D(f)
= A
dan
range R(f)
B.
- Jika E A, maka direct image E oleh f adalah f(E) B yang diberikan sebagai:
f(E):=
{ f(x)
: x
E
}
- Jika H B, maka inverse image H oleh f adalah f -1 (H) A yang diberikan sebagai:
f
-1(H):=
{ xA
:
f(x)E
}
1.1.6
Contoh
Misalkan
f
(x)
:=’ x
0, xR.
- Tentukan direct image f (E) dimana E:={xR: 1x2}
- Tentukan invers image f -1(G) dimana G:={f(x)R 1f(x)4}
Jawab
- Diketahui f (x) :=’ x 0, xR, sehingga jika 1x2, maka:
1
1 1
Dengan
demikian f
(E):={yR:
y1}
- Diketahui f (x) :=’ x 0, xR, sehingga jika 1f(x)4, maka:
14
x21.
Karena
x2
maka diperoleh x
dan x
....(1)
Karena
x21
maka -1x1
... (2)
Dari
(1) dan (2) diperoleh:
f
-1(G):={xR:
-1x
atau x1}
Berikut
ini diberikan definisi dari fungsi injektif, surjektif dan juga
bikjektif.
1.1.7
Definisi
Misalkan
f
: A
B
adalah fungsi dari A ke B.
- Fungsi f adalah injektif (satu-satu) apabila untuk setiap x1x2 maka f(x1)f(x2)
2.
Fungsi
f
adalah surjektif
(onto)
apabila
f
(A)
= B
sehingga R(f
)
= B
- Fungsi f adalah bijektif apabila f adalah injektif dan sekaligus surjektif.
Untuk
menunjukkan bahwa f
injektif, maka harus dibuktikan bahwa:
x1,x2
A
x1x2
f(x1)f(x2)
atau
x1,x2
A
f(x1)
=
f(x2)
x1
=
x2
Untuk
menunjukkan bahwa f
surjektif, maka harus dibuktikan bahwa:
yB,
xA
f(x)
= y
1.1.8
Contoh
- Misalkan A ={xR} dan didefinisikan f(x) = x2 + 2. Apakah f bijektif? Buktikan!
Jawab
f
tidak bijektif, sebab f
tidak injektif, sebab:
dengan
memilih -1,1A
tetapi f
(-1) = (-1)2
+2 = 12
+ 2 = f
(1)
- Misalkan B = {xR: x0} dan didefinisikan f(x) = . Apakah f bijektif? Buktikan!
Jawab
f
adalah bijektif.
- Ambil sembarang x1,x2 B, sehingga jika f (x1) = f (x2) maka
=
2x1x2
+ x2
= 2x1x2
+ x1
x2
= x1
Jadi
x1,x2
B
x1x2
f(x1)f(x2)
, yang menunjukkan f
adalah injektif.
- Ambil sembarang yRf . Pilih x =B, y2 sehingga
f(x)
= f
= = = y
Jadi
yRf
, xB
f(x)
= y,
yang menunjukkan bahwa f
surjektif.
Dari
(i) dan (ii) menunjukan bahwa f
adalah bijektif.
1.1.9
Definisi
Misalkan
f
: A
B
adalah fungsi bijektif dari A
pada B,
maka
g
=
{(b,a)B
xA
:
(a,b)f
}
adalah
fungsi dari B
pada A.
Fungsi
g
adalah invers dari fungsi f
atau di tulis g
= f
-1.
1.1.10
Contoh
Misalkan
A
= {xR:
x3}
dan didefinisikan f(x)
= . tentukan f
-1!
Jawab
Diketahui
f(x)
= y
=
y(x
– 3) = 2x
+ 1
yx
– 2x
= 3y
+ 1
x
(y
–
2) = 3y
+ 1
x
=
Jadi
f
-1(y)
= dengan y2
1.1.11
Definisi
Jika
f : AB dan
g : BC dan
jika
R(f )
D(g)
= B, maka
komposisi fungsi g
o f adalah
fungsi
A kepada
C didefinisikan
sebagai:
(g
o f
)(x)
:= g(f
(x
)), untuk semua xA
1.1.12
Teorema
Jika
f
: AB
adalah
bijektif dan g
: BC
adalah bijektif, maka g
o f
adalah pemetaan bijektif dari A
pada C.
Bukti.
Ambil
sebarang x1,
x2A,
sehingga g(f
(x1))
= g(f
(x2)).
Karena g
bijektif, maka f
(x1)
= f
(x2).
Karena f
bijektif, maka diperoleh x1
= x2.
Dengan demikian g
o f
adalah injektif.
Selanjutnya
karena g
bijektif, maka untuk setiap wC,
terdapat yB
sehingga g(y)
= w.
Demikian halnya karena f
bijektif, maka jika yB,
terdapat xA
sehingga f
(x)
= y.
Jadi g(f
(x))
= w.
Dengan demikian g
o f
adalah surjektif.
Karena
g
o f
adalah injektif dan surjektif, maka g
o f
bijektif.
1.1.13
Teorema
Misalkan
f : AB dan
g: BC adalah
fung si dan misalkan
H adalah
subset dari
C. Maka
(gof
)-1(H)
= f
-1(g-1(H))
Bukti
Ambil
sembarang x(gof
)-1(H),
maka (gof
)(x)(H).
Ini berarti bahwa f
(x)g
-1(H)
sehingga
xf
-1
(g
-1(H)).
Dengan demikian diperoleh
(gof
)-1(H)
f
-1(g-1(H))
.
Selanjutnya
ambil sembarang xf
-1
(g
-1(H)),
maka f
(x)g-1(H).
Akibatnya g(f
(x))H
atau (gof
)(x)H.
Ini berarti bahwa x(gof
)-1(H).
Dengan demikian diperoleh f
-1(g-1(H))
(gof
)-1(H).
Karena
(gof
)-1(H)
f
-1(g-1(H))
dan f
-1(g-1(H))
(gof
)-1(H),
maka terbukti (gof
)-1(H)
= f
-1(g-1(H))
1.1.14
Soal Latihan
1.
Jika A
dan B
adalah himpunan, maka AB
jika
dan hanya jika AB
=A
2.
Buktikan bahwa
- AB = BA
- (AB)C = A(BC)
- A – (BC) = (A – B)(A – C)
3.
Untuk setiap nN,
misalkan An
= {(n+1)k
: kN
}.
a.
Tentukan A1A2.
b.
Tentukan himpunan {An
: nN
} dan {An
: nN
}
4.
Misalkan f
(x)
= , x
2, xR.
a. Tentukan
direct image dari f
(E)
dimana E
= {x
R
: -1x1}
b. Tentukan
invers image dari f
-1(G)
dimana G
= {xR
: -3x-1}
5. Misalkan
A=
{xR:
x-1}
dan didefinisikan f(x)
= . Apakah f
bijektif? Buktikan!
6. Tunjukkan
bahwa jika f
: A
B
dan E,
F
adalah subset dari A,
maka:
a.
f
(EF)
= f
(E)
f
(F)
b.
f
(EF)
f
(E)f
(F)
7. Tunjukkan
bahwa jika f
: A
B
dan G,
H
adalah subset dari B,
maka:
a.
f
-1(GH)
= f
-1(G)
f
-1(H)
b.
f
-1
(GH)
= f
-1
(G)f
(H)
8. Misalkan
f
adalah injektif.
a.
Tunjukkan bahwa f
-1o
f
(x)
= x
untuk semua xD(f
)
dan juga f
o
f
-1(y)
= y
untuk semua yR(f
)
b.
Jika f
adalah suatu bijektif dari A
pada B,
tunjukkan bahwa f
-1
adalah suatu bijektif dari B
kepada A.
9. Misalkan
f
: A
B
dan g
: B
C
adalah fungsi.
a.
Tunjukkan bahwa jika gof
injektif, maka f
injektif.
b.
Tunjukkan bahwa jika gof
surjektif, maka g
surjektif.
10. Misalkan
f
dan g
adalah fungsi sedemikian sehingga (gof
)(x)
= x
untuk semua xD(f
)
dan (f
og)(y)
= y
untuk semua yD(g
).
Buktikan bahwa g
= f
-1.
1.2
Induksi Matematika
Induksi
matematika ialah sebuah teknik pembuktian pernyataan yang berkaitan
dengan objek diskrit (kompleksitas algoritma, teorema mengenai graf,
identitas dan ketidaksamaan yang melibatkan bilangan bulat, dan
sebagainya yang sangat penting).
Induksi
matematika tidak dapat digunakan untuk menemukan rumus atau teorema
tetapi hanya sekedar untuk melakukan pembuktian. Prinsip
Induksi Matematika di tentukan dengan langkah-langkah berikut.
Untuk
menyatakan pernyataan P(n),
nN
benar maka harus di tunjukkan bahwa:
- P(1) adalah benar.
- kN, jika P(k) benar, maka P(k + 1) adalah benar.
1.2.1
Contoh
- Tunjukkan bahwa 1 + 2 + 3 + ... + n = ( n + 1)
Jawab
Misalkan
P(n)
: 1 + 2 + 3 + ... + n
- Untuk n = 1, maka : 1 = .( 1 + 1) 1 = 1 adalah benar.
- Andaikan benar untuk P(k), yaitu
1
+ 2 + 3 + ... + k
=
(k
+
1), dengan kN
maka
akan ditunjukkan benar untuk
P(k
+ 1), yaitu
1
+ 2 + 3 + ... + (k
+
1)
=
(k
+ 1)(k
+
2)
Perhatikan
bahwa:
1
+ 2 + 3 + ... + (k
+
1)
=
1 + 2 + 3 + ... + k
+ (k
+
1)
=
k
(k
+
1) + k
+ 1
=
k2
+
k
+ 1
=
(k2
+ k
+ 2)
=(k
+1)(k
+ 2)
Jadi
untuk kN,
jika P(k)
benar, maka untuk P(k
+ 1) juga benar.
- Buktikan bahwa n3 + 5n habis dibagi oleh 6.
Jawab
Misalkan
P(n)
= n3
+ 5n
- Untuk n = 1, maka P(1) = 13 + 5.1 = 6 adalah habis di bagi 6
- Andaikan benar untuk kN, P(k) habis dibagi 6, maka terdapat mZ, sedemikian sehingga P(k) = k3 + 5k = 6m.
Akan
ditunjukkan bahwa untuk kN,
maka P(k
+
1) habis dibagi 6.
Perhatikan
bahwa:
P(k
+
1) = (k
+ 1)3
+ 5(k
+ 1)
=
k3
+ 3k2
+ 3k
+ 1 + 5k
+ 6
=
k3
+ 5k
+ 3k2
+ 3k
+ 6
=
6m
+ 3k(k
+ 1) + 6
=
6(m
+ 1) + 3k(k
+ 1)
Dengan
menggunakan induksi matematika, pembaca dapat membuktikan bahwa untuk
kN,
maka k(k
+ 1) adalah bilangan genap, sehingga terdapat q
Z,
sedemikian
sehingga k(k
+ 1) = 2q.
Jadi:
P(k
+
1) = 6(m
+ 1) + 3. 2q
=
6(m
+ 1) + 6q
= 6(m
+ q
+ 1)
Karena
m
+ q
+ 1 q
Z,
maka
dapat dikatakan bahwa untuk
kN,
maka P(k
+
1) habis dibagi 6.
Jadi
dengan induksi matematika terbukti bahwa n3
+ 5n
habis dibagi 6
1.2.2
Latihan Soal
1.
Buktikan bahwa ++
... += untuk
semua nN
2.
Buktikan bahwa 13+
23
+ ... + n3
=
untuk
semua nN
3.
Buktikan bahwa 12
– 22
+ 32
+ ... +(-1)n+1n2
= untuk semua nN
4.
Buktikan bahwa 52n
– 1 terbagi oleh 8, untuk semua nN
5.
Buktikan bahwa n3
+ (n
+ 1)3
+ (n
+ 2)3
terbagi oleh 9, untuk semua nN
1.3
Himpunan Finit dan Infinit
1.3.1
Definisi
a.
Himpunan kosong adalah himpunan yang mempunyai 0 elemen
b.
Jika nN,
himpunan S
dikatakan memiliki elemen jika ada bijektif dari himpunan Nn
:= {1,2,3,..,n}
pada S
c.
Himpunan S
adalah finit
jika S
=
,
atau S
mempunyai n
elemen, nN.
d.
Himpunan S
adalah infinit
jika S
tidak finit.
Karena
invers fungsi bijektif adalah bijektif (latihan 1.1.14. 9(b)) maka
mudah untuk melihat bahwa himpunan S
memiliki n
elemen jika dan hanya jika terdapat suatu bijektif dari himpunan S
kepada himpunan {1,2,,3, ..., n}.
Demikian juga halnya dengan komposisi dua fungsi bikektif adalah
bijektif (teorema 1.1.12), maka dapat diketahui bahwa himpunan S
memiliki n
elemen jika dan hanya jika terdapat suatu bijektif dari S1
kepada S2
yang memiliki n
elemen. Selanjutnya himpunan T1
adalah finit jika dan hanya jika terdapat suatu bijektif dari T1
kepada T2
yang juga finit.
1.3.2
Teorema
Jika
S
merupakan himpunan finit, maka banyak elemen
S
adalah tunggal pada N.
1.3.3
Teorema
Himpunan
bilangan asli
N
adalah
infinit.
Bukti.
Andaikan
N
finit, maka nN
sehingga
Nn
onto N.
Tetapi n
+1
N
dan n
+ 1 > n,
yang mengakibatkan Nn
tidak bijektif pada N.
Jadi pengandaian salah, seharusnya N
infinit.
1.3.4
Teorema
a.
Jika
A adalah
himpunan dengan m
elemen,
B adalah
himpunan dengan
n elemen
dan A
B=
, maka
AB mempunyai
m+n
elemen.
b.
Jika
A adalah
himpunan dengan
mN
elemen
dan
CA adalah
himpunan dengan sebuah elemen, maka
A|B
adalah himpunan dengan m
– 1
elemen.
c.
Jika
C
adalah himpunan infinit dan
B adalah
himpunan finit, maka
C|B
adalah himpunan infinit.
1.3.5
Teorema
Misalkan
S dan T adalah himpunan dan TS.
- Jika S finit, maka T finit
- Jika T infinit, maka S infinit
Bukti
a. Jika
T
=Ø maka menurut definisi 1.3.1 himpunan T
adalah finit. Jadi sekarang akan dibuktikan untuk T
Ø dan pembuktian dilakukan dengan menggunakan Induksi Matematika.
Jika
S
memiliki 1 elemen, maka himpunan tak kosong TS
harus seperti S,
sehingga T
finit.
Misalkan
T
S1
dan S1
memiliki k
elemen
berakibat T
finit adalah benar. Akan ditunjukkan bahwa jika S
memiliki k
+ 1 elemen, maka T
finit.
Sekarang
misalkan S
memiliki k
+ 1 elemen, maka terdapat suatu bijektif f
dari Nk+1
pada S.
Jika f
(k
+ 1)T,
maka berdasarkan teorema 1.3.4(b) dapat ditentukan S1
= S\{f
(k
+ 1)}memiliki k
elemen. Karena TS1
maka T
finit. Selanjutnya jika f
(k
+ 1)T,
maka T1
= T
\
{f
(k
+ 1)}dan T1S1.
Karena S1
memiliki k
elemen, maka T1
adalah finit. Akibatnya T
= T1{f
(k
+ 1)} adalah finit.
Dengan
demikian terbukti bahwa jika S
finit maka T
finit.
b.
Pernyataan “Jika
T
infinit, maka
S
infinit” merupakan kontrapositif dari pernyataan “jika
S
finit maka T
finit”.
Jadi Jika
T
infinit, maka
S
infinit.
1.3.6
Contoh
- Jika himpunan A={nZ: 1n10} dan BA. Tentukan himpunan B yang mungkin! Apakah B finit atau infinit?
Jawab
Himpunan
B
yang mungkin adalah:
B1
= {1, 2, 5, 7}, B2
= {2,3,4,5,6,7,8,9,10}, dan sebagainya.
B1
dan B2
adalah finit
- Jika himpunan N={ 4n: nN} dan NM. Tentukan himpunan M yang mungkin! Apakah M finit atau infinit?
Jawab
Himpunan
M
yang mungkin adalah:
M1
={n
:
nN},
M2
= {2n
:
nN},
dan sebagainya
M1
dan M2
adalah infinit.
Selanjutnya
akan diberikan definisi tentang himpunan denumerabel, countable, dan
uncountabel.
1.3.7
Definisi
a.
Himpunan S
adalah denumerabel
(infinit
countabel) jika ada bijektif N
pada
S.
b.
Himpunan S
adalah countabel
jika
S
finit atau denumerabel.
c.
Himpunan S
adalah uncountabel
jika
S
tidak countabel.
1.3.8
Teorema
Himpunan
NxN
adalah
denumerabel.
1.3.9
Teorema
Misalkan
S dan
T
adalah himpunan dan TS.
- Jika S countabel, maka T countabel
- Jika T uncountabel, maka S uncountabel.
1.3.10
Teorema
Pernyataan
berikut ini adalah ekuivalen.
- Himpunan S adalah countabel
- Ada surjektif dari N kepada S
- Ada injektif dari S kepada N.
1.3.11
Teorema
Himpunan
bilangan rasional Q
adalah denumerabel
1.3.12
Contoh
1. Himpunan
E
= {2n
: nN}
adalah denumerabel karena pemetaan f
: N
E
yang didefinisikan oleh f
(n)
= 2n,
nN
adalah suatu bijektif dari N
kepada E.
2. Himpunan
semua bilangan bulat Z
adalah denumerabel.
1.3.13
Latihan Soal
1.
Berikan masing-masing dua buah contoh dari teorema
1.3.8 dan teorema 1.3.9.
2. Buktikan
teorema 1.3.8
3.
Buktikan teorema 1.3.9.
4. Buktikan
bahwa himpunan takkosong T1
adalah finit jika dan hanya jika terdapat suatu bijektif dari T1
kepada himpunan finit T2.
5.
Buktikan bahwa jika S
dan T
denumerabel, maka ST
denumerabel.
Music MP3
0 komentar:
Posting Komentar