Artikel lain dalam siklus
Teori formal pemodelan menggunakan relasi aljabar, termasuk dalam tanda tangan model struktur aljabar, yang mendeskripsikan fisik nyata, objek teknis dan proses fungsinya. Publikasi ini merupakan kelanjutan dari publikasi sebelumnya , yang perlu dibaca karena banyak konsep dan istilah yang digunakan di sini dijelaskan di sana.
Penyajiannya tidak ditawarkan dengan gaya tradisional (panah), tetapi dengan cara yang saya sendiri harus membayangkan dan menguasai seluruh dapur ini baik dari buku teks / manual maupun dari artikel majalah. Saya menganggap katalog yang telah saya buat sangat berguna, memungkinkan Anda untuk memilih hampir semua ruang dan menyajikan elemen-elemennya dalam bentuk yang mudah: matriks, grafik, dll. Anda dapat langsung melihat apa yang Anda hadapi dan properti (telah ditulis) sering tidak perlu diperiksa.
Konsep hubungan
Saya pikir istilah sikap sudah tidak asing lagi bagi setiap pembaca, tetapi menanyakan definisi akan sangat membingungkan. Ada banyak alasan untuk ini. Mereka paling sering pada guru yang, jika mereka menggunakan hubungan dalam proses pengajaran, tidak fokus pada istilah ini, tidak memberikan contoh yang mudah diingat. Beberapa komentator di artikel tersebut mengaitkan komentar tersebut dengan akun mereka sendiri dan menambahkan minus. Tapi Anda tidak bisa menyembunyikan jahitan di dalam karung. Tidak ada publikasi yang serius, dan tidak ada. Tanyakan pada diri Anda, apakah Anda pernah bekerja dengan ruang hubungan? Dan dengan jujur jawab dirimu sendiri. Apa yang dapat Anda ceritakan kepada dunia tentang ruang ini? Pertama-tama, paling tidak daftarkan elemen-elemennya dan tentukan propertinya. Anda bahkan melihat DBMS melalui mata penciptanya, tetapi mereka juga tidak melihat semuanya, atau mereka tidak menampilkan semuanya, seperti, misalnya, di sirkuit mikro.
Saya akan melakukan sedikit pengulangan di sini. Seseorang harus memulai dengan himpunan abstrak A = {a1, a2, a3, ..., an}. Anda dapat membacanya di sini . Untuk pemahaman yang lebih baik, kami akan mengurangi set menjadi 3 elemen, yaitu A = {a1, a2, a3}. Sekarang kita melakukan perkalian Cartesian × = 2 dan secara eksplisit menyebutkan semua elemen dari kotak Cartesian
× = {(a1, a1), (a1, a2), (a1, a3), (a2, a1), (a2, a2 ), (a2, a3), (a3, a1), (a3, a2), (a3, a3)}.
Kami mendapat 9 pasang elemen yang teratur dari A × A, dalam pasangan elemen pertama dari faktor pertama, yang kedua dari yang kedua. Sekarang mari kita coba mendapatkan semua himpunan bagian dari kotak A × A Cartesian. Himpunan bagian akan berisi jumlah pasangan yang berbeda: satu, dua, tiga, dan seterusnya hingga semua 9 pasangan, kami juga menyertakan himpunan kosong ∅ dalam daftar ini. Ada berapa subset? Banyak, yaitu 2 9= 512 elemen.
Definisi . Himpunan bagian dari himpunan kuadrat Cartesian disebut relasi biner. Jika kuadrat Cartesian terdiri dari dua faktor, rasionya adalah biner, jika 3 internal, dari 4 adalah tetrar, dan dari n adalah n-ary. Arity adalah jumlah tempat dalam elemen hubungan.
Definisi . Himpunan semua subset dari himpunan A disebut Boolean. Boolean terdiri dari 2 | A | elemen, di sini | A | Apakah kardinalitas himpunan.
Hubungan dapat didefinisikan dengan berbagai cara:
- pencacahan elemen; R1 = {(a2, a2), (a2, a3), (a3, a1)}; R2 = {(a3, a3)}
- vektor biner; <000011100>; <000000001>
- matriks;
- grafik dan cara lain.
Selanjutnya, kami beralih ke pertimbangan ruang relasi, dengan asumsi bahwa konsep, properti relasi, dan operasi dengannya sudah tidak asing lagi bagi pembaca setidaknya sejauh publikasi kami di tautan.
Ruang hubungan biner
Mari kita perjelas lebih awal bahwa hubungan bisa ketat (ini semua adalah hubungan anti-reflektif) atau non-ketat (semua yang lain). Kami akan fokus pada hubungan ketidakpedulian dan preferensi, yang terakhir dibagi menjadi preferensi yang lemah dan preferensi yang ketat (untuk beberapa alasan, tidak kuat). Secara umum, tidak ada keteraturan dalam sains dengan terminologi dan kemungkinan besar tidak akan ada. Dalam kriptografi, misalnya, menghapus sandi dari kriptogram dengan adanya kunci adalah dekripsi, dan tanpa kunci, dekripsi. Tampaknya decoder decode, tetapi tidak.
Ruang relasi biner dengan himpunan pembawa adalah himpunan arbitrer dari himpunan relasi biner yang diberikan. Pertimbangkan ruang utama untuk hubungan preferensi (Gambar 2.15).
R- ruang semua hubungan preferensi yang lemah, memenuhi kondisi refleksivitas dan kelengkapan.
QT - preferensi lemah yang memenuhi kondisi quasi-transitivity.
QO adalah ruang kuasi order linier, yaitu hubungan dari QT yang transitif.
TO adalah ruang dari semua tatanan sempurna, yaitu hubungan dari QO yang antisimetris.
SP adalah ruang dari semua hubungan preferensi yang ketat; mereka memenuhi sifat antirefleksivitas dan antisimetri.
RO- hubungan urutan parsial ketat, atau preferensi ketat transitif. Karena relasi tatanan parsial ketat bersifat transitif, maka wajar untuk menggunakannya untuk merepresentasikannya dengan grafik tereduksi, yaitu grafik di mana busur transitivitas dihilangkan. Grafik yang disingkat seperti itu disebut diagram Hasse.
QS adalah ruang quasiseries, yaitu, order parsial ketat yang relasinya I = ¬ (PUP -1 ) adalah ekuivalen.
TSO adalah ruang tatanan linier ketat, yaitu, pesanan parsial yang properti kelengkapannya terpenuhi.
Perlu dicatat bahwa ada total n dari relasi semacam itu! .. Misalnya, untuk n = 3, jumlah relasi sempurna adalah 6, dan semuanya ditunjukkan pada Gambar. 2.13.
T- ruang semua hubungan toleransi (ketidakpedulian), mereka memiliki sifat simetri dan refleksivitas.
TOT adalah ruang relasi toleransi yang berorientasi
transitorif , yaitu relasi yang komplemen ke I direpresentasikan sebagai gabungan relasi transitif yang saling terbalik, yaitu ¬I = R∩R -1 .
I adalah ruang dari semua relasi ekivalen, yaitu relasi simetris, refleksif dan transitif.
E - ruang relasi persamaan, terdiri dari satu relasi yang direpresentasikan oleh matriks diagonal. Ada hubungan satu-ke-satu antara ruang R, P dan I, ditentukan oleh pemetaan relasi preferensi.
Gambar 2.15 Skema ruang hubungan biner Hubungan yang
terungkap antar ruang digunakan untuk mentransfer masalah pengambilan keputusan (DM) dari satu ruang ke ruang lain, di mana masalah tersebut dapat diselesaikan dengan cara yang lebih sederhana, dan kemudian solusi yang dihasilkan dikembalikan ke ruang semula, tempat DP dirumuskan.
Hubungan ini ditunjukkan secara diagram pada Gambar. 2.14. Spasi hubungan biner (jenis hubungan) disajikan pada Gambar. 2.15.
Hubungan kesetaraan
Definisi . Sebuah relasi biner σ ⊆ A × A, yang memiliki tiga sifat refleksivitas, simetri, transitivitas, disebut relasi ekivalensi biner (BOE). Hubungan kesetaraan σ (x, y), (x, y) ∊σ, xσy, x≈y dilambangkan. Lebih mudah menggunakan representasi matriks (tabel) dari hubungan tersebut. Di bawah ini pada Gambar 2.24 hanyalah representasi matriks. Di atas himpunan 4 elemen, ada 15 BOE, yang semuanya tergambar.
Representasi dan analisis struktur hubungan kesetaraan (n = 4)
Persamaan dari hubungan biner mungkin adalah BO yang paling umum. Jarang sains mengelola tanpa konsep ini, tetapi bahkan ketika persamaan digunakan untuk menyatakan pertanyaan apa pun, mungkin sulit untuk memahami apa yang penulis maksudkan. Bahkan dengan definisi yang benar dan penghitungan sifat yang melekat dalam hubungan biner ini, kesulitan persepsi tetap ada.
Mari kita mulai dengan contoh persamaan, yang menggambarkan batasan jumlahnya.
Contoh 1 . Biarkan ada tiga kubus. Mari kita buat daftar properti yang dianugerahi kubus dan penggunaan praktisnya (sifat-sifat kubus) membuatnya, seolah-olah, dapat dipertukarkan. Mari kita tetapkan angka ke kubus, dan merepresentasikan propertinya pada Tabel 1.
Untuk setiap properti, BOE dan kelas kesetaraan muncul. Melanjutkan daftar properti, kita tidak akan mendapatkan relasi ekivalen baru. Hanya akan ada pengulangan yang sudah dibangun, tetapi untuk tanda lain. Mari kita tunjukkan hubungan antara BOE dan set.
Pertimbangkan satu set dari tiga elemen A = {1,2,3} dan dapatkan semua kemungkinan partisi menjadi semua bagian. ①1 | 2 | 3; ②12 | 3; ③13 | 2; ④ 1 | 23; ⑤123. Pembagian terakhir menjadi satu bagian. Nomor partisi dan BO dalam lingkaran.
Definisi . Partisi himpunan A adalah keluarga i, i = 1 (1) I, dari himpunan pemisah berpasangan yang tidak kosong dari , penyatuan yang membentuk seluruh himpunan asli = Ui, i∩j = ∅, ∀ i ≠ j. Sub-himpunan i disebut kelas ekivalen dari partisi himpunan asli.
Ini semua adalah partisi dari himpunan (5 buah). Analisis BO menunjukkan bahwa hanya ada 5 relasi ekivalensi yang berbeda. Apakah ini kebetulan? Kita dapat mengasosiasikan setiap partisi dengan matriks sembilan sel (3 × 3 = 9), yang masing-masing berisi pasangan elemen yang dipesan dari himpunan A, atau sel tetap kosong jika tidak ada objek untuk pasangan yang sesuai. Baris dan kolom dari matriks ditandai dengan elemen himpunan A, dan perpotongan baris-kolom sesuai dengan pasangan terurut (i, j). Ini bukan pasangan yang cocok dengan sel matriks, tetapi hanya satu atau nol, bagaimanapun, nol sering tidak ditulis sama sekali.
Tidak, kebetulan itu bukan kebetulan. Ternyata setiap partisi himpunan dalam korespondensi satu-ke-satu dengan BOE, dan kardinalitas himpunan dapat berupa | A | = n.
Hubungan ini mungkin yang paling sering digunakan dalam sirkulasi ilmiah, tetapi kombinasi sifat-sifat yang diwujudkan dalam hal ini sangat membatasi prevalensinya.
Jadi di antara semua relasi biner abstrak atas himpunan tiga elemen (total ada 2 9 = 512 relasi), hanya lima yang ekuivalen - pembawa properti yang diperlukan, kurang dari satu persen.
Untuk | A | = 4 hubungan ada 2 16= 65536, tetapi hanya ada 15 persamaan. Ini adalah jenis hubungan yang sangat langka. Di sisi lain, hubungan kesetaraan tersebar luas dalam masalah terapan. Dimanapun ada dan dianggap himpunan objek yang sangat berbeda dan partisi yang berbeda dari himpunan tersebut (bukan angka) menjadi beberapa bagian, hubungan kesetaraan muncul. Mereka dapat disebut model matematika (aljabar) dari partisi semacam itu, yang mengklasifikasikan kumpulan objek menurut berbagai kriteria.
Partisi minimal dari himpunan A yang terbentuk dari himpunan satu elemen A = U {a} dan partisi A yang terdiri dari himpunan {A} itu sendiri disebut partisi trivial (tidak tepat).
Kisi (4): semua partisi dari himpunan = {a1, a2, a3, a4} = {1,2,3,4}
Partisi minimum sesuai dengan relasi ekivalen P15, yang disebut kesetaraan atau relasi unit. Setiap kelas ekivalen berisi satu elemen. Untuk partisi dari himpunan A, yang hanya mencakup himpunan A itu sendiri, ada hubungan ekivalensi yang mengandung semua elemen bujur sangkar Kartesius A × A.
Jenis yang paling dekat dengan relasi ekivalen adalah relasi toleransi . Himpunan relasi toleransi berisi semua relasi ekivalensi. Untuk pembawa A terdapat tiga unsur toleransi 8. Semuanya memiliki sifat refleksivitas dan simetri.
Ketika properti transitivitas terpenuhi, lima dari delapan toleransi berubah menjadi ekuivalen (Gambar 2.24 dan 2.25).
Definisi . Himpunan kelas ekivalensi [a] σ dari unsur-unsur himpunan A disebut himpunan hasil bagi (dilambangkan dengan A / σ) dari himpunan A dengan kesetaraan σ.
Definisi . Pemetaan natural (kanonik) f: A → A / σ adalah pemetaan f sehingga f (a) = [a] σ.
Hubungan toleransi dan analisisnya
BO ini telah disebutkan sebelumnya, tetapi di sini kami akan membahasnya lebih detail. Semua orang tahu konsep kesamaan, kesamaan, kesamaan, indistinguishability, interchangeability objek. Mereka tampaknya memiliki konten yang serupa, tetapi bukan hal yang sama. Jika hanya kesamaan yang diindikasikan untuk objek, tidak mungkin untuk memecahnya menjadi kelas yang jelas sehingga dalam suatu kelas objek tersebut serupa, dan tidak ada kesamaan antara objek dari kelas yang berbeda. Dalam kasus kemiripan, situasi samar muncul tanpa batas yang jelas. Di sisi lain, akumulasi perbedaan yang tidak signifikan pada objek serupa dapat menyebabkan objek yang sama sekali berbeda.
Pada bagian sebelumnya kita telah membahas tentang arti makna dari relasi kesamaan (ekuivalensi) objek. Yang tidak kalah pentingnya adalah situasi ketika perlu untuk menetapkan kesamaan objek.
Biarkan bentuk benda geometris dipelajari. Jika kemiripan bentuk objek, misalnya kubus, berarti dapat dipertukarkan sepenuhnya dalam situasi pembelajaran tertentu, maka kesamaannya adalah dapat dipertukarkan sebagian (bila di antara kubus ada paralelepipeds yang sangat mirip dengannya), yaitu kemungkinan dapat dipertukarkan dengan beberapa (dapat diterima dalam situasi ini) ) kerugian.
Ukuran terbesar untuk kemiripan adalah tidak dapat dibedakan, sama sekali tidak sama, seperti yang terlihat pada pandangan pertama. Identitas adalah properti yang berbeda secara kualitatif. Identitas hanya dapat dilihat sebagai kasus khusus dari ketidakmampuan membedakan dan kesamaan.
Intinya adalah bahwa objek yang tidak dapat dibedakan (serta yang serupa, yang serupa) tidak dapat dibagi ke dalam kelas sehingga elemen di setiap kelas tidak berbeda, dan elemen dari kelas yang berbeda jelas berbeda.
Memang, kami akan mempertimbangkan himpunan titik (x, y) di pesawat. Misalkan nilai d memiliki nilai yang kurang dari ambang ketetapan mata, yaitu, d adalah jarak di mana dua titik yang terletak pada jarak ini bergabung menjadi satu, yaitu. secara visual tidak dapat dibedakan (pada jarak pesawat yang dipilih dari pengamat). Pertimbangkan sekarang n titik terletak pada satu garis lurus dan diberi jarak (masing-masing dari tetangga) pada jarak d. Setiap pasang
titik yang berdekatan tidak dapat dibedakan, tetapi jika n cukup besar, titik pertama dan terakhir akan berjauhan satu sama lain dan tentunya dapat dibedakan.
Pendekatan tradisional untuk mempelajari kesamaan atau indistinguishability adalah pertama-tama menentukan tingkat kesamaan, dan kemudian memeriksa posisi relatif dari objek yang serupa. Matematikawan Inggris Ziman, yang mempelajari model-model alat visual, mengusulkan definisi kemiripan aksiomatik. Dengan demikian, menjadi mungkin untuk mempelajari sifat-sifat kesamaan terlepas dari bagaimana tepatnya itu ditentukan dalam situasi tertentu: jarak antar objek, kebetulan beberapa tanda, atau pendapat subjektif pengamat.
Mari kita perkenalkan penjelasan tentang konsep kesamaan atau ketidakmampuan membedakan.
Definisi . Relasi T pada himpunan M disebut relasi toleransi atau toleransi jika bersifat refleksif dan simetris.
Kebenaran definisi ini terbukti dari fakta bahwa objek jelas tidak dapat dibedakan dari dirinya sendiri dan, tentu saja, terlihat seperti dirinya sendiri (ini memberikan refleksivitas dari hubungan). Urutan pertimbangan dua objek tidak mempengaruhi kesimpulan akhir tentang kesamaan atau ketidaksamaan (simetri) mereka.
Dari contoh dengan indistinguishability visual dari titik-titik pada bidang, kita melihat bahwa toleransi transitivitas tidak terpenuhi untuk semua pasangan objek.
Jelas juga bahwa karena kesamaan adalah kasus khusus dari kesamaan, maka kesetaraan harus menjadi kasus toleransi yang khusus. Membandingkan definisi kesetaraan dan toleransi, kami yakin demikian. Prinsip filosofis: "yang khusus lebih kaya daripada yang umum" dengan jelas ditegaskan. Properti tambahan - transitivitas membuat beberapa relasi toleransi menjadi setara. Dua saudara kembar sangat mirip sehingga mereka dapat mengikuti ujian untuk satu sama lain tanpa risiko. Namun, jika dua siswa hanya sama, trik seperti itu, meskipun mungkin, berisiko.
Setiap elemen himpunan membawa informasi tertentu tentang elemen yang mirip dengannya. Tetapi tidak semua informasi, seperti dalam kasus elemen identik Di sini, tingkat informasi yang berbeda dimungkinkan yang dikandung satu elemen dalam hubungannya dengan yang lain.
Mari pertimbangkan contoh di mana toleransi diatur dengan cara yang berbeda.
Contoh 2 . Himpunan M terdiri dari kata-kata Rusia empat huruf - kata benda umum dalam kasus nominatif. Kami akan menyebut kata-kata seperti itu serupa jika berbeda tidak lebih dari satu huruf. Masalah umum yang terkenal "Mengubah lalat menjadi gajah" secara tepat dirumuskan sebagai berikut. Temukan urutan kata yang dimulai dengan kata "fly" dan diakhiri dengan kata "elephant", dua kata yang berdekatan yang serupa dalam arti definisi yang baru saja diberikan. Solusi untuk masalah ini:
fly - mura - tura - tara - kara - kare - cafe - kaffr - musher - skiff - hook - croc - time - stock - groan - elephant.
Contoh 3... Misalkan p adalah bilangan asli. Kami menunjukkan dengan Sp kumpulan semua himpunan bagian yang tidak kosong dari himpunan M = {1, 2, ..., p}. Relasi "memiliki setidaknya satu elemen yang sama" pada himpunan Sp adalah relasi toleransi. Kemudian dua himpunan bagian seperti itu disebut toleran jika mereka memiliki setidaknya satu elemen yang sama. Sangat mudah untuk melihat bahwa refleksivitas dan simetri dari hubungan itu terpenuhi.
Himpunan Sp disebut simpleks berdimensi (p –1). Konsep ini menggeneralisasi konsep ruas, segitiga dan tetrahedron ke kasus multidimensi. Angka 1, 2, 3, ..., p diartikan sebagai simpul dari sebuah simpleks. Himpunan bagian dua elemen - sebagai tepi, tiga elemen - sebagai permukaan datar (dua dimensi), subset elemen k lainnya - sebagai permukaan berdimensi (k –1). Jumlah semua elemen (himpunan bagian) dari Sp sama dengan 2 p - 1.
Toleransi subset (wajah) berarti mereka memiliki simpul yang sama.
Definisi . Himpunan M dengan relasi toleransi τ yang diberikan padanya disebut ruang toleransi. Jadi, ruang toleransi adalah berpasangan (M, τ).
Contoh 4 . Ruang toleransi Sp dapat digeneralisasikan ke kasus tak terbatas. Misalkan H himpunan sewenang-wenang. Jika SH adalah kumpulan dari semua himpunan bagian yang tidak kosong dari himpunan H, maka relasi toleransi T pada SH diberikan oleh kondisi: X T Y jika X∩Y ≠ ∅. Simetri dan refleksivitas dari hubungan ini terlihat jelas. Ruang SH diberi tanda <H, T> dan disebut ruang toleransi "universal".
Contoh 5... Misalkan p adalah bilangan asli. Kami menyatakan dengan Bp himpunan semua titik ruang berdimensi p yang koordinatnya sama dengan 0 atau 1. Toleransi dalam Bp diberikan oleh aturan: xτy jika x dan y mengandung setidaknya satu komponen yang bertepatan (koordinat). Jumlah total elemen di Bp adalah 2 r . Untuk setiap elemen x = (a1, a2, ..., ap) dari himpunan Bp, hanya ada satu elemen y = (1 - a1, 1 - a2, ..., 1 - ap) yang tidak toleran terhadapnya.
Jelas, Bp terdiri dari semua simpul dari kubus berdimensi p.
Contoh 6 . Pertimbangkan ruang toleransi, yang komponennya mengambil nilai nyata apa pun.
Secara khusus, ini adalah himpunan semua titik x = (a1, a2) di bidang Kartesius. Toleransi dua titik berarti mereka memiliki setidaknya satu koordinat. Ini berarti bahwa dua titik toleran berada pada vertikal yang sama atau pada horizontal yang sama.
Untuk nilai p lainnya, ruang dapat diartikan sebagai sekumpulan titik dalam ruang berdimensi p. Secara khusus, setiap elemen x dapat dianggap sebagai fungsi numerik yang ditentukan pada himpunan bilangan asli {1, 2, 3, ...}, yang menetapkan ke setiap bilangan asli i: 1 ≤ i ≤ p bilangan real ai (urutan bilangan hingga). Maka toleransi dua fungsi x dan y berarti keduanya sama setidaknya pada satu titik.
Hubungan tatanan parsial dan analisisnya
Himpunan berurutan adalah himpunan dengan relasi urutan yang diperkenalkan padanya. Definisi . Himpunan A dan relasi urutan biner R di atasnya (≤) disebut terurut sebagian jika relasi tersebut memiliki (seperti dalam BOE) tiga kondisi (satu kondisi berbeda):
- refleksivitas ∀ x ∊ A (xRx); (antirefleksivitas ∀ x ∊ A ¬ (xRx));
- antisimetri ∀ , y ∊ (Ry yRx → x = y);
- transitivitas ∀ x, y, z ∊ A (xRy & yRz → xRz).
Dengan sikap anti-reflektif, tatanan parsial yang ketat muncul . Himpunan B (A) dari semua himpunan bagian dari himpunan A, diurutkan dengan memasukkan elemen, adalah himpunan berurutan sebagian (PN). Himpunan terurut sebagian (B (A), ⊆) sering disebut Boolean.
Sebuah elemen x∊A POZA A mencakup elemen y∊A jika x> y dan tidak ada z∊A sehingga x> z> y. Sepasang elemen x, y∊A disebut sebanding jika x ≥ y atau x ≤ y.
Jika di PLA A setiap pasang elemennya sebanding, maka A disebut rangkaian atau rantai yang dipesan secara linier . Jika beberapa wabah B hanya terdiri dari elemen-elemen yang tidak dapat dibandingkan satu sama lain, maka himpunan B disebut antichain
... Rantai di PLAG A disebut jenuh jika tidak dapat bersarang di rantai lain selain dirinya sendiri.
Antikain jenuh didefinisikan serupa. Rantai maksimum (antichain) adalah rantai (antichain) yang mengandung jumlah elemen maksimum.
Unsur m dari PLM A disebut minimal jika tidak ada unsur ∊ di selain m dan sedemikian rupa sehingga ≤m. Unsur M dari wabah A disebut maksimal jika tidak ada unsur x “lebih besar” dari M, selain M dan sedemikian sehingga x ≥ M.
Unsur y∊A dari wabah A disebut maksimal jika ∀ x∊ A x ≤ y. Unsur y∊ A PLAG A disebut yang terkeciljika ∀ x∊A x ≥ y. Untuk elemen terbesar dan terkecil, biasanya menggunakan sebutan 1 dan 0. Itu disebut batas universal. Setiap wabah A memiliki paling banyak satu elemen terkecil dan paling banyak satu elemen terbesar. Dalam PLA A, beberapa elemen minimum dan beberapa maksimum diperbolehkan. Lebih
mudah untuk menggambarkan PLA A akhir dengan diagram Hasse , yang merupakan grafik berarah, simpulnya didistribusikan di atas level diagram dan sesuai dengan elemen dari A, dan setiap busur diarahkan ke bawah dan digambar jika dan hanya jika elemen x∊A mencakup elemen y∊A.
Busur transitif tidak digambar. Level grafik Hasse mengandung elemen dengan peringkat yang sama, yaitu terhubung dengan elemen minimal PCM dengan jalur dengan panjang yang sama (sesuai dengan jumlah busur).
Misalkan B adalah subset yang tidak kosong dari PLA A, maka elemen x∊A disebut batas atas yang tepat (dilambangkan dengan sup A B) dari himpunan B jika x ≥ y untuk semua y∊B dan jika mengikuti dari kebenaran relasi z ≥ y untuk semua y∊B, bahwa z ≥ x.
Batas bawah yang tepat (dilambangkan dengan inf A B) dari himpunan B adalah elemen x∊A jika x ≤ y untuk semua y∊B dan jika kondisi z ≤ y untuk semua y∊ B menyiratkan bahwa z ≤ x.
Contoh 7 . Dua himpunan numerik hingga
A = {0,1,2, ..., 21} dan B = {6,7,10,11} diberikan.
CHUM (A, ≤) ditunjukkan pada Gambar. 2.26.
Koleksi B Δ dari semua batas atas untuk disebut kerucut atas untuk himpunan B. Koleksi ∇dari semua permukaan bawah untuk B disebut kerucut bawah untuk B.
Setiap bagian PLA juga merupakan PLP sehubungan dengan pesanan yang diwariskan. Jika himpunan berisi elemen terbesar dan / atau terkecil, maka mereka adalah maksimum (minimum, masing-masing). Kebalikannya tidak benar. Boolean memiliki satu elemen terkecil (Ø) dan satu elemen terbesar.
Dalam himpunan yang diberikan, elemen terkecil adalah nol (0) dan bertepatan dengan satu-satunya elemen minimal, dan elemen terbesar tidak ada. Elemen maksimumnya adalah {19, 20, 21}. Batas atas yang tepat untuk B = {6,7,10,11} adalah elemen 21 (ini adalah elemen terkecil di kerucut atas).
Situasi umum. Biarkan satu set diberikan, yang kardinalitasnya adalah *******. Dari semua relasi biner yang dimungkinkan pada himpunan ini, mari kita pilih relasi preferensi biner dan relasi tatanan parsial ketat terkait.
Urutan parsial berbeda dari tatanan parsial ketat hanya karena mereka mengandung elemen tambahan (dalam representasi matriks - diagonal) (i, ai) = 1, i = 1 (1) n, dan jumlah pesanan tersebut serta pesanan lain dalam himpunan lengkap relasi sama. Hingga saat ini, tidak ada dependensi (rumus, algoritme) yang ditemukan yang memungkinkan seseorang menghitung dan menghitung jumlah pesanan parsial untuk setiap n.
Penulis yang berbeda telah menentukan dan menerbitkan hasil berikut dengan perhitungan langsung (Tabel 2.12).
Percobaan komputasi penulis memungkinkan untuk mendapatkan tidak hanya bilangan, tetapi juga bentuk (representasi) dari pesanan parsial pada kekuatan yang berbeda dari pembawa-pengali dari relasi. Pencetak tersedak mencetak daftar besar seperti itu, tetapi tidak hanya keindahan membutuhkan pengorbanan, sains juga tidak menolaknya.
Tabel 2.12 menunjukkan: n = | A | - kardinalitas pembawa-set; baris kedua adalah jumlah semua relasi biner pada himpunan A; dan selanjutnya
| Dalam (n) | - jumlah kelas relasi non-isomorfik;
| (n) | - jumlah hubungan urutan parsial;
| Gn (n) | - jumlah kelas dari hubungan urutan parsial non-isomorfik;
| Gl (n) | = n! - jumlah hubungan orde linier.
Seperti yang Anda lihat, dalam tabel untuk n kecil, misalnya, G (n = 4), hanya ada 219, data diberikan, yang nilainya tumbuh sangat cepat dengan peningkatan n, yang secara signifikan memperumit analisis langsung kuantitatif (dan kualitatif) mereka bahkan dengan komputer.
Tabel di bawah mengilustrasikan kemungkinan menghasilkan Γ (n = 4) dari semua orde parsial dari perpotongan masing-masing orde parsial linier. Tetapi dalam situasi ini, muncul yang berlebihan (berulang), yang untuk n kecil dapat dipotong secara manual (dihitung ulang). Ternyata ada 300 matriks, tapi PL yang ada hanya 219. Rumus umum belum didapat. Di tingkat global, situasinya serupa, meskipun saya belum melihat publikasi tentang transfer PLM oleh penulis Barat. Algoritme kami sepenuhnya orisinal dan perintis.
Saya akan memberikan skema yang mungkin untuk memecahkan masalah enumerasi elemen ruang orde parsial (n = 4).
Himpunan ordo parsial ketat dalam pengurutan leksikografik dari orde linier (n = 4) dihasilkan oleh perpotongan timbal baliknya.
Beberapa definisi penting matematika, untuk konsep yang sering ditemukan dalam teks.
Definisi . Interval tertutup adalah himpunan bentuk {x: a ≤ x ≤ b}; interval terbuka tidak tertutup, dan interval setengah terbuka, yaitu, himpunan bentuk {x: a <x ≤ b}, di mana a <b, atau bentuk {x: a ≤ x <b} tidak terbuka maupun tertutup.
Definisi . Batas interval sembarang dari garis nyata dalam topologi bilangan real yang biasa hanya terdiri dari ujung interval ini, terlepas dari apakah interval ini terbuka, tertutup, atau setengah terbuka. Batas himpunan bilangan rasional, serta batas himpunan semua bilangan irasional, adalah seluruh rangkaian bilangan real.
Definisi... Setiap himpunan berurutan linier, dalam himpunan bagian tidak kosong mana pun yang memiliki elemen terkecil, disebut tertata dengan baik.
Definisi . Sebuah keluarga R disebut rantai (kadang-kadang menara, sarang) jika dan hanya jika, untuk salah satu elemennya A dan B, baik A ⊂ B atau B A.Kondisi ini setara dengan pernyataan bahwa keluarga R diurutkan secara linier dengan inklusi atau, dalam terminologi yang diterima - bahwa keluarga R bersama dengan relasi inklusi adalah sebuah rantai.
P r dan n c dan p m a ke s dan m al n tentang s t dan H a u s d o r f a. Untuk setiap famili dari himpunan A dan setiap sarang R yang dibentuk oleh elemen-elemen dari famili A, terdapat sebuah sarang maksimal M dalam A yang mengandung R.
Teorema penting tentang himpunan dan keluarganya (J.L. Kelly "Topologi umum" hal. 55).
Dalil. (a) PRINTSIpMACKSIMALN tentang ELEMENT. Elemen maksimal dalam keluarga A dari suatu himpunan ada jika, untuk setiap sarang di A, ada elemen di A yang berisi elemen acak dari kumpulan ini.
(b) ELEMEN PRINTSIpMINIMALNO. Elemen terkecil dalam keluarga A ada jika, untuk setiap sarang di A, ada elemen di A yang dimuat di setiap elemen dari sarang ini.
(c) Lemma T yuk dan. Setiap kelompok himpunan karakter hingga memiliki elemen maksimal.
(d) LEMMA KURATOVSKOGO. Setiap rantai dalam set terurut (sebagian) terdapat dalam beberapa rantai maksimal.
(e) lemma Tson. Jika setiap rangkaian dari beberapa himpunan yang diurutkan sebagian dibatasi dari atas, maka himpunan ini memiliki elemen maksimal.
(f) A ke s dan o m dan pilihan. Misalkan Xα adalah himpunan tidak kosong untuk setiap elemen a dari himpunan indeks A. Kemudian di A ada fungsi c sehingga c (a) ∊ Xα untuk setiap a dari A.
(g) Postulat Tserm elo. Untuk setiap kelompok A dari himpunan tidak kosong terputus-putus, ada himpunan C sedemikian rupa sehingga AUC untuk setiap A dari A terdiri dari tepat satu titik.
(h) CETAK dan P dalam urutan pengiriman penuh. Setiap set dapat dipesan sepenuhnya.