Teori Dasar

Philip J. Erdelsky

20 Juli 2010

Silakan e-mail komentar, koreksi dan penambahan pada webmaster di pje@efgh.com .

1. Perkenalan

Kebanyakan, jika tidak semua, matematika murni ditulis dalam bahasa set. Anda mungkin memperhatikan bahwa bagian ini mengandung banyak definisi dan hanya beberapa teorema. Namun, bahkan definisi dapat berisi banyak hikmat matematika. Butuh matematikawan abad merumuskan beberapa definisi yang mendasar.

Sebuah set adalah kumpulan item dianggap secara keseluruhan. Jika hanya ada beberapa item, set dapat didefinisikan dengan mendaftarkannya di kawat gigi. Misalnya, set A mungkin didefinisikan sebagai berikut:

A = {1,2,3}

Item dalam set disebut elemen atau anggota dari himpunan. Mereka juga mengatakan untuk milik ke set atau menjadi di set, dan set dikatakan mengandung mereka. Simbol  digunakan untuk mengekspresikan hubungan ini - a∈ A berarti suatu milik A , dan a∉ A berarti suatu bukan milik A .

Dua set yang sama jika mereka berisi persis elemen yang sama. Artinya, mengatur A adalah sama dengan mengatur B jika setiap unsur A juga merupakan unsur B , dan setiap elemen B juga merupakan elemen dari A . Urutan di mana unsur-unsur dari suatu himpunan tercantum dalam definisi tidak relevan. Misalnya, set {1,2,3} dan {3,2,1} adalah sama.

Sebuah elemen tidak bisa milik set lebih dari sekali. Oleh karena itu, ketika set didefinisikan dengan daftar unsur-unsurnya, setiap elemen terdaftar hanya sekali.

Satu set yang tidak mengandung unsur-unsur yang disebut kosong set, dan diwakili oleh simbol  .

Jika setiap elemen dari himpunan A juga merupakan elemen dari himpunan B , maka A dikatakan menjadi bagian dari B , yang diwakili secara simbolis oleh A⊆ B , atau B dikatakan termasuk A . Setiap set adalah bagian dari dirinya sendiri, dan himpunan kosong adalah bagian dari setiap set.

Jika A⊆ B dan ada setidaknya satu unsur B yang tidak unsur A , maka A dikatakan menjadi tepat bagian dari B , yang diwakili secara simbolis oleh A⊂ B .

Sebuah subset sering didefinisikan oleh beberapa properti dari unsur-unsurnya. Sebagai contoh, mari A = {1,2,3,4,5,6} , dan biarkan B = {2,4,6} . Kemudian B dapat didefinisikan sebagai himpunan semua elemen dari A yang bahkan, atau simbol-simbol:

B = {x∈ A | x bahkan } .

Sini simbol | berarti "seperti itu". Kata "semua" dipahami. Dalam beberapa kasus set A juga dapat dipahami.

The persimpangan dari sejumlah set adalah himpunan elemen yang mereka semua memiliki kesamaan. Misalnya, persimpangan {1,2,3,4,5} , {2,3,4,5,6,7,8,9} dan {3,5,7,9} adalah {3,5 } . Hal ini jelas bahwa persimpangan koleksi set adalah bagian dari setiap set dalam koleksi. Persimpangan dua set A dan B diwakili secara simbolis oleh A∩B .

Operasi persimpangan memiliki beberapa sifat yang jelas:

  • Komutatif: A∩B = B∩A .
  • Associativity: (A∩B) ∩C = A∩ (B∩C) .
  • A∩B = A jika, dan hanya jika, A⊆ B .

The serikat dari sejumlah set adalah himpunan semua elemen mereka. Misalnya persatuan {1,2,3,4,5} , {2,3,4,5,6,7,8,9} dan {3,5,7,9} adalah {1,2, 3,4,5,6,7,8,9} . Hal ini jelas bahwa setiap set dalam persatuan adalah bagian dari serikat mereka. Penyatuan dua set A dan B diwakili secara simbolis oleh A∪B .

Operasi serikat memiliki beberapa sifat yang jelas:

  • Komutatif: A∪B = B∪A .
  • Associativity: (A∪B) ∪C = A∪ (B∪C) .
  • A∪B = B jika dan hanya jika, A⊆ B .

Dua set dikatakan saling lepas jika mereka tidak memiliki unsur-unsur yang sama; yaitu, A dan B yang saling lepas jika A∩B = ∅ . Tiga atau lebih set dikatakan saling lepas jika setiap dua dari mereka adalah menguraikan.

Notasi AB digunakan untuk menunjukkan himpunan semua elemen A yang tidak unsur B . Operasi ini tidak memiliki nama standar, tetapi ketika B adalah himpunan bagian dari A , AB kadang-kadang dikatakan pelengkap dari B di A .

Hubungan antara set sering diwakili pictorially oleh diagram Venn , di mana set direpresentasikan sebagai interior lingkaran yang tumpang tindih (atau tokoh pesawat lain). Set kombinasi diwakili oleh daerah yang dibatasi oleh lingkaran, seperti yang ditunjukkan dalam contoh berikut untuk dua set:

2. Pasangan Memerintahkan

Sebuah pasangan memerintahkan adalah satu set dari dua elemen dalam urutan tertentu. Sebuah pasangan biasanya ditulis (a, b) di mana suatu adalah elemen pertama dan b adalah elemen kedua. Dua memerintahkan pasangan (a, b) dan (c, d) adalah sama jika a = c dan b = d . Membalikkan unsur sebuah pasangan menghasilkan sepasang memerintahkan berbeda jika unsur-unsur yang tidak sama. Misalnya, pasangan memerintahkan (1,2) tidak sama dengan pasangan memerintahkan (2,1) .

Untuk dua set A dan B , yang produk silang A⨯ B adalah himpunan semua pasangan memerintahkan yang unsur pertama dan kedua adalah elemen dari A dan B , masing-masing. Itu adalah,

A⨯ B = {(a, b) | a∈ A dan b∈ B}

memerintahkan tiga kali lipat, empat kali lipat, dll bisa didefinisikan, tetapi mereka jarang diperlukan.

3. Hubungan

Sebuah relasi R pada himpunan A hanyalah sebuah himpunan pasangan terurut elemen A , yaitu, R ⊆ A⨯ A . Dua elemen a dan b dikatakan mematuhi relasi jika (a, b) adalah di R . Namun, bagi sebagian besar hubungan, notasi set tidak digunakan. Sebaliknya, simbol seperti ~ ditempatkan di antara unsur-unsur untuk menunjukkan bahwa mereka mematuhi relasi; misalnya sebuah ~ b berarti bahwa (a, b) adalah di R.

simbol lainnya sering digunakan untuk hubungan yang

=> <≥ ≤ | ≠ ⊃ ⊂ ⊇ ⊆ ≡

Kebanyakan hubungan yang berguna memiliki beberapa sifat tambahan. Suatu relasi ~ pada set A adalah kesetaraan jika terus mengikuti untuk setiap a , b dan c di A :

  • Ini adalah refleksif : a ~ a .
  • Ini adalah simetris : a ~ b menyiratkan bahwa b ~ a .
  • Ini adalah transitif : a ~ b dan b ~ c menyiratkan bahwa sebuah ~ c .

Satu set himpunan bagian tak kosong dari set A disebut partisi dari A jika setiap elemen A milik satu dan hanya satu dari subset; yaitu, jika subset saling terpisah dan serikat mereka adalah A . Teorema berikut membentuk koneksi antara hubungan ekuivalensi dan partisi.

Teorema 3.1. Jika ~ adalah relasi ekivalen pada himpunan A, maka ada partisi dari himpunan A sedemikian sehingga ~ b jika dan hanya jika, a dan b milik set yang sama di partisi. Sebaliknya, jika P adalah partisi dari A, maka "a dan b milik set yang sama di P" adalah relasi ekivalen.

Bukti. Mempertimbangkan set P subset a = {x ∈ A | x ~ a} . Jelas setiap a di A milik setidaknya satu bagian di P , yaitu dalam T a . Oleh karena itu set di P adalah tidak kosong dan serikat mereka adalah A .

Sekarang mari a dan b menjadi dua himpunan bagian dalam P . Jika mereka memiliki unsur c kesamaan, maka c ~ a , c ~ b dan x ~ b untuk setiap x ∈ T b . Dengan transitivitas x ~ a dan x ∈ T a , juga. Argumen serupa menunjukkan bahwa setiap elemen dari a juga merupakan elemen dari b . Oleh karena itu a dan b adalah sama. Jika dua himpunan bagian di P tidak memiliki unsur yang sama, mereka menguraikan. Maka P adalah partisi yang diinginkan.

Kebalikannya adalah sepele. █

Set di partisi terkait dengan cara ini dengan relasi ekivalen disebut nya kelas kesetaraan . Mereka sering digunakan untuk mendefinisikan sistem matematika.

Hubungan kesetaraan pada dua set A dan B dapat digunakan untuk mendefinisikan relasi ekivalen pada A⨯ B dengan cara yang jelas: (a, b) adalah setara dengan (c, d) jika a setara dengan c dan b setara dengan d .

4. Pesanan

Sebuah urutan parsial pada himpunan A adalah relasi ≤ dengan sifat sebagai berikut untuk setiap a , b dan c di A :

  • Ini adalah refleksif : a ≤ a .
  • Ini adalah antisymmetric : a ≤ b dan b ≤ a berarti bahwa a = b .
  • Ini adalah transitif : a ≤ b dan b ≤ c menyiratkan bahwa sebuah ≤ c .

Sebuah urutan parsial ≤ pada set A disebut urutan linear (atau total order ) jika, untuk setiap dua elemen a dan b dari A , a ≤ b atau b ≤ a (atau keduanya, jika a = b ).

Himpunan semua himpunan bagian dari suatu himpunan sebagian diperintahkan oleh inklusi: S ≤ T berarti S⊆ T . Agar parsial ini biasanya bukan total order karena kita dapat menemukan dua himpunan bagian, seperti {1,2,3} dan {2,3,4} , sehingga tidak adalah bagian dari yang lain.

Akrab hubungan ≤ dalam aritmatika adalah total order.

Dalam bekerja dengan urutan parsial atau total, itu adalah umum untuk menentukan beberapa hubungan yang terkait:

  • a ≥ b berarti b ≤ a ,
  • a <b berarti a ≤ b dan a ≠ b ,
  • a> b berarti b ≤ a dan b ≠ a .

Ada cara alternatif untuk mendefinisikan perintah parsial dan total. Suatu relasi <adalah urutan parsial jika mematuhi dua kondisi berikut:

  • Ini adalah transitif: a <b dan b <c menyiratkan bahwa a <c .
  • a <a selalu salah.

Sebuah urutan parsial adalah total order jika juga trikotomi : untuk setiap dua elemen a dan b, satu dan hanya satu dari berikut ini berlaku:

  • a <b ,
  • a = b ,
  • b <a .

Hubungan lainnya kemudian didefinisikan dalam istilah < :

  • a ≤ b berarti a <b atau a = b .
  • a ≥ b berarti b <a atau a = b .
  • a> b berarti b <a .

Hal ini dapat ditunjukkan bahwa dua cara mendefinisikan perintah parsial dan jumlah yang setara.

Secara umum, nama "parsial order" dan "total order" yang diterapkan ke seluruh himpunan relasi ≤, < , > dan ≥ tanpa menentukan yang merupakan urutan hubungan dan yang terkait dengannya.

5. Fungsi

Sebuah fungsi f dari himpunan A ke himpunan B adalah aturan yang, mengingat setiap elemen x dari A , menghasilkan tepat satu elemen yang sesuai dari B diwakili oleh f (x) . Konsep ini sering dinyatakan secara simbolis sebagai f: A⟶B .

Sebuah fungsi juga disebut pemetaan . Kedua nama yang umum digunakan dalam matematika, tapi dari titik ini sebagainya kita akan menggunakan fungsi nama.

Kedua, dan lebih abstrak, cara untuk menentukan fungsi f: A⟶B adalah sebagai bagian dari A ⨯ B sehingga untuk setiap elemen x dari A ada satu dan hanya satu memerintahkan pasangan di bagian yang elemen pertama adalah x . Elemen kedua dari pasangan ini kemudian ditetapkan untuk f (x) .

Unsur f (x) disebut citra dari x di bawah fungsi. Fungsi f juga dikatakan memetakan atau membawa elemen x ke elemen f (x) .

Jika f: A⟶B maka A disebut domain dari f , dan himpunan semua elemen B yang gambar elemen dalam A disebut rentang dari f . Set A dan B tidak perlu berbeda; pada kenyataannya, mereka adalah sama di banyak aplikasi.

Beberapa fungsi memiliki sifat khusus yang membuat mereka sangat menarik atau berguna. Jika f: A⟶B , maka

Jika kisaran adalah sama dengan b , maka f disebut surjection , sebuah surjective fungsi, atau fungsi dari ke B . Fungsi ini kadang-kadang juga dikatakan "ke", tetapi penggunaan preposisi sebagai kata sifat terdengar begitu kaku bahwa penulis yang baik cenderung menghindarinya.

Jika kisaran adalah bagian yang tepat dari B , maka f disebut fungsi dari ke B .

Jika f membawa paling banyak satu unsur domainnya ke setiap elemen dari jangkauan, yaitu, jika f (x) = f (y) menyiratkan bahwa x = y , maka f disebut injeksi , sebuah fungsi injektif , atau satu -untuk-satu fungsi.

Jika f adalah baik surjective dan satu-ke-satu maka disebut korespondensi satu-ke-satu dari A dan B . Jika f adalah satu-ke-satu tapi tidak surjective, maka itu adalah korespondensi satu-ke-satu dari A dan jangkauan, yang merupakan bagian yang tepat dari B .

Jika f: A⟶B adalah korespondensi satu-ke-satu maka memiliki invers fungsi yang disebut -1 : B⟶A didefinisikan oleh

-1 (x) = elemen w dari A sehingga f (w) = x .

Tentu saja, sebaliknya juga benar. Jika fungsi memiliki invers, maka itu adalah korespondensi satu-ke-satu.

Dua fungsi f: A⟶B dan g: A⟶B yang sama jika f (x) = g (x) untuk setiap x di A .

Jika kisaran satu fungsi adalah bagian dari domain lain, maka komposit fungsi didefinisikan dengan menerapkan fungsi berturut-turut. Artinya, jika f: A⟶B dan g: B⟶C maka fungsi komposit (f◌g): A⟶Cdidefinisikan oleh

(f ◌g) (x) = g (f (x)) untuk setiap x di A .

Jika fungsi memiliki domain dan rentang yang tepat, komposisi adalah asosiatif, yaitu, (f ◌g) ◌h = f ◌ (g ◌h) .

Sebuah satu-ke-satu fungsi f: A⟶B dari dua set dengan beberapa struktur disebut isomorfisme jika mempertahankan struktur. Kita telah melihat salah satu contoh dari satu set dengan struktur: set sebagian memerintahkan. Jika set A dan B yang sebagian diperintahkan, maka f: A⟶B adalah isomorfisme jika satu-ke-satu, surjective, dan f (x) <f (y) jika, dan hanya jika, x <y .

Isomorfisme dari satu set terstruktur dengan dirinya sendiri disebut automorphism . Jelas, fungsi identitas ( f (x) = x untuk semua x ) adalah automorphism dari setiap set terstruktur. Sebuah contoh yang baik dari automorphism trivial adalah fungsi yang membawa sejumlah kompleks menjadi konjugat (yaitu ,. f (x + iy) = x-iy untuk semua nyata x dan y ). Ini adalah satu-ke-satu, surjective, dan mempertahankan penjumlahan dan perkalian dari bilangan kompleks.

Misalkan f: A⟶B dan ada hubungan kesetaraan pada set A dan B . Mari A dan B menjadi set yang sesuai dari kelas kesetaraan A dan B , masing-masing. Jika f membawa unsur setara dengan A menjadi elemen-elemen setara B , yaitu , jika sebuah ~ b menyiratkan bahwa f (a) ~ f (b) , maka ada yang unik fungsi g: P A ⟶P B didefinisikan dengan cara berikut. Biarkan S menjadi kelas kesetaraan di A . Pilih elemen a dari kelas kesetaraan ini dan menentukan g (S) menjadi mengandung kelas kesetaraan f (a) . Hal ini mudah menunjukkan bahwa ini tidak tergantung pada elemen tertentu yang dipilih dari A . Selain itu, g mewarisi banyak sifat dari f ; misalnya , jika f adalah surjective, begitu juga g .

5. Operasi

Sebuah operasi unary di set adalah fungsi yang domain adalah set itu. Apa yang membedakan operasi unary dari fungsi biasa adalah notasi yang digunakan, dan sering hubungan dengan fungsi atau operasi lainnya. Misalnya, fungsi yang membawa sejumlah nyata x ke nomor -x adalah operasi unary yang disebut negasi . Kisaran fungsi sering set yang sama, tapi ini tidak diperlukan.

Sebuah operasi biner adalah fungsi yang domain adalah produk silang dari dua set (atau produk silang dari set dengan dirinya sendiri). Misalnya, penjumlahan dan perkalian dua operasi biner pada set R⨯ R , di mana R adalah himpunan bilangan real. Citra sebuah pasangan (x, y) biasanya ditulis sebagai x + y untuk penambahan dan xy untuk perbanyakan. Berikut x dan y disebut operan . Mantan notasi biasanya digunakan hanya untuk tambahan, atau operasi sangat banyak seperti penambahan. Notasi terakhir ini digunakan untuk operasi yang lebih umum.

operasi unary dan biner sangat umum dalam matematika; operasi dengan tiga atau lebih operan jarang, kecuali untuk ekstensi operasi biner seperti di bawah ini. operasi biner pada satu set yang lebih umum daripada operasi biner pada pasang set, namun keduanya sering ditemui.

Operasi biner dikatakan asosiatif jika dapat digunakan pada tiga operan tanpa memperhatikan pengelompokan mereka, yaitu, jika

(xy) z = x (yz) 
(x + y) + z = x + (y + z)

Jika operasi biner adalah asosiatif, kita dapat menulis hasilnya selama tiga operan tanpa tanda kurung, sehingga operasi terdefinisi dengan tiga operan:

xyz = (xy) z = x (yz) 
x + y + z = (x + y) + z = x + (y + z)

Selain biasa dan perkalian yang asosiatif; begitu banyak operasi biner lainnya. Komposisi fungsi adalah operasi biner asosiatif (tersedia fungsi memiliki domain yang sesuai dan rentang). Bahkan, sebagian besar operasi biner adalah asosiatif.

Jika operasi biner adalah asosiatif, mudah untuk memperpanjang properti untuk operasi pada empat atau lebih operan:

wxyz = (Lyx) z = (w (xy)) z = a ((xy) z) = w (xyz).

Operasi biner adalah komutatif jika urutan operan tidak mempengaruhi hasil; yaitu, jika

xy = x 
x + y = y + x

Jika operasi komutatif juga asosiatif, komutatif dapat dengan mudah diperluas untuk operasi pada tiga atau lebih operan:

xyz = (xy) z = (yx) z = yxz = y (xz) = (yx) z = yxz , dll

operasi biner yang komutatif tapi tidak asosiatif sangat jarang. operasi biner yang asosiatif namun tidak komutatif cukup umum. Komposisi fungsi adalah salah satu contoh; demonstrasi fakta yang akan diberikan kemudian.

Sekarang mempertimbangkan operasi biner pada A⨯ B dengan jangkauan di C (yang tidak perlu set yang berbeda). Misalkan ada operasi kesetaraan di set ini (yang juga tidak perlu berbeda), dan operasi biner mempertahankan kesetaraan, yaitu , operasi bila diterapkan operan setara memberikan hasil yang setara, atau sebuah ~ b dan c ~ d menyiratkan bahwa ac ~ bd . Kemudian, hanya sebagai fungsi dari satu variabel diperpanjang untuk fungsi pada kelas kesetaraan, operasi pada dua variabel dapat diperpanjang sama. Jika seorang dan b adalah elemen dari kelas ekivalen P dan Q , masing-masing, maka PQ didefinisikan sebagai kelas kesetaraan mengandung ab . Operasi baru mewarisi banyak sifat yang lama, termasuk associativity dan komutatif.