Kata “tatanan” sering digunakan dalam berbagai persoalan. Petugas memberi perintah: “Sesuai urutan angka, hitung,” operasi hitung dilakukan dengan urutan tertentu, atlet diurutkan berdasarkan tinggi badan, ada urutan melakukan operasi saat membuat bagian, dan urutan kata-kata. dalam sebuah kalimat.
Apa persamaannya dalam semua kasus ketika berbicara tentang keteraturan? Faktanya adalah bahwa kata "urutan" memiliki arti sebagai berikut: artinya elemen mana dari himpunan ini atau itu yang mengikuti yang mana (atau elemen mana yang mendahului yang mana).
Sikap " X berikut pada"transitif: jika" X berikut pada" Dan " pada berikut z", Itu " X berikut z" Selain itu, hubungan ini harus antisimetris: untuk dua orang yang berbeda X Dan pada, Jika X berikut pada, Itu pada tidak mengikuti X.
Definisi. Sikap R di satu set X ditelepon sikap perintah yang ketat , jika bersifat transitif dan antisimetris.
Mari kita cari tahu ciri-ciri graf dan grafik relasi tatanan ketat.
Mari kita lihat sebuah contoh. Di lokasi syuting X= (5, 7, 10, 15, 12) perbandingan tertentu R: « X < pada" Mari kita definisikan hubungan ini dengan membuat daftar pasangannya
R = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.
Mari kita buat grafiknya. Kita melihat bahwa grafik relasi ini tidak memiliki loop. Tidak pada grafik panah ganda. Jika dari X panah mengarah ke pada, dan dari pada- V z, lalu dari X panah mengarah ke z(Gbr. 8).
Grafik yang dibangun memungkinkan Anda mengatur elemen-elemen himpunan X dalam urutan ini:
{5, 7, 10, 12, 15}.
Pada Gambar 6 (§ 6 bab ini), kolom VII, VIII adalah grafik hubungan tatanan ketat.
Hubungan yang tidak ketat
Relasi “kurang” dalam suatu himpunan bilangan real sebaliknya adalah sikap “tidak kurang”. Ini bukan lagi hubungan ketertiban yang ketat. Intinya adalah, kapan X = pada, hubungan terpenuhi X ³ pada Dan pada ³ X, yaitu sikap “tidak kurang” bersifat refleksif.
Definisi. Sikap R di satu set X ditelepon hubungan yang tidak ketat, jika bersifat refleksif, antisimetris, dan transitif.
Relasi-relasi tersebut merupakan gabungan dari relasi keteraturan yang ketat dengan relasi identitas.
Pertimbangkan relasi “tidak lebih” (£) untuk himpunan tersebut
X= (5, 7, 10, 15, 12). Mari kita buat grafiknya (Gbr. 9).
Graf relasi orde tak ketat, tidak seperti graf relasi orde ketat, memiliki loop di setiap titik.
Pada Gambar. 6 (§ 6 bab ini) kolom V, VI adalah grafik hubungan tatanan tidak ketat.
Set yang dipesan
Suatu himpunan mungkin menjadi terurut (mereka juga mengatakan terurut seluruhnya) oleh suatu relasi keteraturan, sedangkan himpunan lain mungkin tidak terurut atau terurut sebagian oleh relasi tersebut.
Definisi. Sekelompok X ditelepon dipesan beberapa hubungan keteraturan R, jika untuk dua elemen apa pun x, kamu dari X:
(X, pada) Î R atau ( kamu, x) Î R.
Jika R adalah relasi tatanan ketat, maka himpunan X dipesan oleh relasi ini dengan ketentuan: jika X, pada dua elemen himpunan yang tidak sama X, Itu ( X, pada) Î R atau ( kamu, x) Î R, atau dua elemen apa pun x, kamu set X adalah sama.
Dari pelajaran matematika sekolah diketahui himpunan bilangan N , Z , Q , R diurutkan berdasarkan relasi “kurang dari” (<).
Himpunan himpunan bagian dari suatu himpunan tertentu tidak diurutkan dengan memperkenalkan relasi inklusi (I), atau inklusi tegas (S) dalam pengertian di atas, karena ada himpunan bagian, tidak ada satupun yang termasuk dalam himpunan bagian lainnya. Dalam hal ini, kita mengatakan bahwa himpunan tertentu diurutkan sebagian oleh relasi Í (atau Ì).
Pertimbangkan setnya X= (1, 2, 3, 4, 5, 6) dan berisi dua relasi “kurang dari” dan “dibagi”. Sangat mudah untuk memverifikasi bahwa kedua hubungan ini adalah hubungan keteraturan. Grafik relasi “kurang dari” dapat digambarkan sebagai sinar.
Grafik relasi “dibagi” hanya dapat digambarkan pada bidang datar.
Selain itu, grafik relasi kedua memiliki simpul-simpul yang tidak dihubungkan oleh panah. Misalnya, tidak ada panah yang menghubungkan angka 4 dan 5 (Gbr. 10).
Hubungan pertama " X < pada"disebut linier. Secara umum, jika hubungannya teratur R(ketat dan tidak ketat) di lokasi syuting X memiliki properti: untuk apa pun X, padaÎ X atau xRy, atau tahunRx, maka disebut relasi tatanan linier, dan himpunan X– himpunan terurut linier.
Jika set X tentu saja, dan terdiri dari N elemen, lalu pemesanan linier X turun ke penomoran elemen-elemennya dengan angka 1,2,3, ..., N.
Himpunan yang diurutkan secara linier memiliki sejumlah properti:
1°. Membiarkan a, b, c– elemen himpunan X, dipesan oleh relasi R. Jika diketahui hal tersebut aRв Dan di RC, lalu mereka mengatakan bahwa elemen tersebut V terletak di antara unsur-unsurnya A Dan Dengan.
2°. Sekelompok X, diurutkan secara linier berdasarkan relasi R, disebut diskrit jika di antara dua elemennya hanya terdapat himpunan berhingga dari elemen himpunan tersebut.
3°. Suatu himpunan yang terurut linier disebut padat jika untuk dua elemen berbeda dari himpunan ini terdapat elemen himpunan yang terletak di antara keduanya.
Jenis relasi biner yang penting adalah relasi keteraturan. Hubungan ketertiban yang ketat - relasi biner yang anti-refleksif, antisimetris, dan transitif:
penamaan - (A sebelumnya B). Contohnya termasuk
hubungan “lebih”, “kurang”, “lebih tua”, dll. Untuk bilangan, notasi yang biasa digunakan adalah tanda “<", ">".
Hubungan ketertiban yang tidak ketat - hubungan biner refleksif, antisimetris dan transitif. Selain contoh alami dari pertidaksamaan bilangan yang tidak ketat, contohnya adalah hubungan antara titik-titik pada suatu bidang atau ruang “agar lebih dekat dengan titik asal koordinat”. Pertidaksamaan tidak tegas, untuk bilangan bulat dan bilangan real, juga dapat dianggap sebagai disjungsi relasi persamaan dan keteraturan tegas.
Jika turnamen olahraga tidak mengatur pembagian tempat (yaitu, setiap peserta menerima tempat makan/penghargaan tertentu saja), maka ini adalah contoh perintah yang ketat; jika tidak, ini tidak ketat.
Relasi keteraturan terbentuk pada suatu himpunan ketika untuk beberapa atau semua pasangan elemennya terdapat relasi
diutamakan. Tugas - untuk himpunan suatu relasi keteraturan disebut itu "mengatur, dan "himpunan itu sendiri" sebagai hasilnya menjadi dipesan. Relasi keteraturan dapat diperkenalkan dengan cara yang berbeda-beda. Untuk himpunan berhingga, setiap permutasi elemen-elemennya “menetapkan suatu keteraturan yang ketat. Suatu himpunan tak hingga dapat diurutkan dalam jumlah tak terhingga cara yang menarik.
Jika untuk hubungan pesanan R di satu set .M dan beberapa elemen berbeda memiliki setidaknya satu relasi
arb atau BH lalu elemennya A Dan B disebut sebanding, jika tidak - tak tertandingi.
Himpunan terurut penuh (atau linier). M -
suatu himpunan yang relasi keteraturannya ditentukan, dan dua elemen himpunan mana pun M sebanding; set yang dipesan sebagian- sama, tetapi pasangan elemen yang tidak dapat dibandingkan diperbolehkan.
Berurutan linier adalah himpunan titik-titik pada suatu garis dengan relasi “lebih ke kanan”, himpunan bilangan bulat, bilangan rasional, bilangan real dengan relasi “lebih besar dari”, dan seterusnya.
Contoh himpunan terurut sebagian adalah vektor tiga dimensi, jika urutannya diberikan sebagai berikut, jika
Artinya, jika prioritas dilakukan pada ketiga koordinat, maka vektor (2, 8, 5) dan (6, 9, 10) sebanding, tetapi vektor (2, 8, 5) dan (12, 7, 40) tidak sebanding. Metode pengurutan ini dapat diperluas ke vektor dengan dimensi apa pun: vektor
mendahului vektor jika
Dan selesai
Kita dapat memperhatikan contoh pengurutan himpunan vektor lainnya.
1) urutan sebagian: 
, Jika
Itu. berdasarkan panjang vektor; vektor-vektor yang panjangnya sama tidak dapat dibandingkan.
2) urutan linier: 
, Jika A
Contoh terakhir memperkenalkan konsep urutan abjad.
Alfabet adalah kumpulan karakter berbeda berpasangan yang disebut huruf alfabet. Contohnya adalah alfabet bahasa Eropa apa pun, serta alfabet 10 angka Arab. Di komputer, keyboard dan beberapa alat pendukung menentukan alfabet karakter yang valid.
Kata dalam alfabetA - kumpulan karakter alfabet A. Kata ditulis dalam simbol alfabet secara berurutan, dari kiri ke kanan, tanpa spasi. Bilangan asli adalah kata dalam alfabet digital simbol superskrip (eksponen) dan subskrip (indeks variabel, basis logaritma), batang pecahan, tanda radikal, dsb.; namun, menurut beberapa konvensi, tanda ini dapat ditulis ke dalam sebuah string, yang digunakan, misalnya, dalam pemrograman komputer (misalnya, tanda eksponensial ditulis sebagai 2 tanda perkalian berturut-turut: 5**3 berarti pangkat ketiga dari nomor 5.
Urutan leksikografis (menurut abjad) - untuk kata-kata yang berbeda dalam alfabet dengan berurutan
simbol mengatur urutan: , jika
kemungkinan perkenalan 
, di mana juga
(subkata boleh kosong), atau - subkata kosong
Dalam definisi ini - awalan (subkata awal) yang sama untuk kedua kata - atau kata pertama di sebelah kiri berbeda
karakter, baik - karakter terakhir dalam kata - ekor
subkata.
Jadi, urutan kata menurut abjad ditentukan oleh simbol pertama di sebelah kiri yang membedakannya (misalnya, kata KONUS mendahului kata COSINE karena huruf ketiganya berbeda terlebih dahulu, dan N mendahului S dalam alfabet Rusia). Karakter spasi juga dianggap mendahului karakter alfabet apa pun - jika salah satu kata merupakan awalan kata lain (misalnya, CON dan CONE)
Latihan. Periksa apakah urutan abjad dari bilangan asli yang memiliki jumlah tempat desimal yang sama bertepatan dengan urutan berdasarkan besarnya.
Membiarkan A - set yang dipesan sebagian. Elemen tersebut disebut maksimum V A, jika tidak ada elemen yang mana A< b. Elemen A ditelepon terbesar V A, jika untuk setiap orang berbeda dari A elemen selesai B<а-
Ditentukan secara simetris minimal dan terkecil elemen. Konsep elemen terbesar dan maksimum (masing-masing, terkecil dan minimal) berbeda - lihat. contoh pada Gambar 14. Himpunan pada Gambar. 14,a memiliki elemen terbesar R, itu juga maksimal, ada dua elemen minimum: s dan t, tidak ada yang terkecil. Sebaliknya, pada Gambar 14b, terdapat himpunan yang mempunyai dua elemen maksimal / dan J, tidak ada yang terbesar, minimal alias terkecil – satu : T.
Secara umum, jika suatu himpunan memiliki elemen terbesar (masing-masing terkecil), maka hanya ada satu (mungkin tidak ada).
Mungkin ada beberapa elemen maksimum dan minimum (mungkin tidak ada sama sekali - dalam himpunan tak terbatas; dalam kasus terakhir - harus ada).
Mari kita lihat dua contoh lagi. - relasi pada suatu himpunan N:
"Y membagi X", atau "X adalah pembagi suatu bilangan kamu"(Misalnya,
) bersifat refleksif dan transitif. Mari kita pertimbangkan pada himpunan pembagi berhingga dari bilangan 30.
Relasi tersebut merupakan relasi tatanan parsial (tidak ketat)
dan diwakili oleh matriks orde 8 berikut, yang berisi 31 karakter
Sirkuit yang bersesuaian dengan 8 simpul harus berisi 31 tautan. . Namun, akan lebih mudah untuk melihatnya jika kita mengecualikan 8
simpul-simpul yang menggambarkan refleksivitas hubungan (elemen diagonal matriks) dan simpul transitif, yaitu ligamen
Jika ada bilangan tengah Z sedemikian rupa sehingga
(misalnya, kata penghubung sejak). Kemudian dalam skema
12 ligamen akan tersisa (Gbr. 15); mata rantai yang hilang tersirat "oleh transitivitas". Angka 1 adalah yang terkecil, dan angka 30
elemen terbesar di . Jika kita mengecualikan dari angka 30 dan
pertimbangkan urutan parsial yang sama di set, lalu
tidak ada elemen maksimal, tetapi ada 3 elemen maksimal: 6, 10, 15
Sekarang mari kita membangun sirkuit yang sama untuk suatu relasi pada Boolean
(himpunan semua himpunan bagian) dari himpunan tiga elemen
Berisi 8 elemen:
Periksa apakah Anda cocok dengan elemennya a,b,c, masing-masing, bilangan 2, 3, 5, dan operasi penggabungan himpunan adalah perkalian dari bilangan-bilangan yang bersesuaian (yaitu, misalnya, himpunan bagian bersesuaian
hasil kali 2 5 = 10), maka matriks relasinya akan persis seperti ini
sama seperti untuk relasi ; diagram dari dua hubungan ini dengan yang dijelaskan
singkatan dari loop dan penghubung transitif bertepatan hingga notasi (lihat Gambar 16). Elemen terkecil adalah
Dan yang terbesar -
Hubungan biner R di satu set A Dan S di satu set DI DALAM disebut isomorfis, jika antara A dan B dimungkinkan untuk membuat korespondensi satu-satu Г, di mana, jika (yaitu.
elemen-elemennya berhubungan R), lalu (gambar
elemen-elemen ini saling berhubungan S).
Jadi, himpunan terurut sebagian bersifat isomorfik.
Contoh yang dipertimbangkan memungkinkan terjadinya generalisasi.
Relasi Boolean merupakan relasi parsial. Jika
Itu. sekelompok E mengandung P elemen, lalu masing-masing
sesuai dengan subset P vektor -dimensi dengan
komponen, dimana fungsi karakteristiknya
atur A/ . Himpunan semua vektor tersebut dapat dianggap sebagai himpunan titik P-ruang aritmatika berdimensi dengan koordinat 0 atau 1, atau dengan kata lain sebagai simpul P-dimensi
kubus satuan, dilambangkan dengan , yaitu. kubus yang rusuknya mempunyai satuan panjang. Untuk n = 1, 2, 3 titik yang ditunjukkan masing-masing mewakili ujung suatu segmen, simpul persegi dan kubus - itulah nama umumnya. Untuk /7=4, representasi grafis dari hubungan ini ada pada Gambar 17. Di dekat setiap titik sudut kubus 4 dimensi terdapat titik yang bersesuaian
bagian dari himpunan 4 elemen dan empat dimensi
sebuah vektor yang mewakili fungsi karakteristik dari himpunan bagian ini. Simpul-simpul yang berkorespondensi dengan himpunan bagian yang berbeda dengan adanya tepat satu elemen dihubungkan satu sama lain.
Pada Gambar 17, sebuah kubus empat dimensi digambarkan sedemikian rupa sehingga pada satu kubus
level, elemen yang tidak dapat dibandingkan ditempatkan berpasangan, berisi jumlah unit yang sama dalam rekaman (dari 0 hingga 4), atau, dengan kata lain, jumlah elemen yang sama dalam himpunan bagian yang diwakili.
Pada Gambar 18a, b - representasi visual lainnya dari kubus 4 dimensi;
pada Gambar 18a sumbu variabel pertama OH diarahkan ke atas (penyimpangan yang disengaja dari vertikal agar tepi kubus yang berbeda tidak menyatu):
dalam hal ini subkubus 3 dimensi yang sesuai dengan X= 0 terletak di bawah, dan untuk X= 1 - lebih tinggi. Pada Gambar. 186 sumbu yang sama OH diarahkan dari dalam kubus ke luar; sesuai dengan subkubus bagian dalam X= Oh, dan yang eksternal adalah X = 1.
DI DALAM 
File bahan menunjukkan gambar kubus satuan 5 dimensi (hlm. 134).
Properti hubungan:
1) refleksivitas;
2) simetri;
3)transitivitas.
4) keterhubungan.
Sikap R di satu set X ditelepon reflektif, jika tentang setiap elemen himpunan X kita dapat mengatakan bahwa dia sedang menjalin hubungan R Dengan diriku sendiri: XRx. Jika relasinya refleksif, maka terdapat loop pada setiap titik pada grafik. Sebaliknya, graf yang setiap simpulnya memuat loop merupakan graf relasi refleksif.
Contoh relasi refleksif adalah relasi “kelipatan” pada himpunan bilangan asli (setiap bilangan merupakan kelipatan dirinya sendiri), dan relasi kesebangunan segitiga (setiap segitiga sebangun), dan relasi “persamaan” ( setiap angka sama dengan dirinya sendiri), dst.
Ada relasi yang tidak mempunyai sifat refleksivitas, misalnya relasi tegak lurus ruas: ab, ba(tidak ada satupun ruas yang dapat dikatakan tegak lurus terhadap dirinya sendiri) . Oleh karena itu, tidak ada satu pun loop dalam grafik hubungan ini.
Relasi “lebih panjang” untuk segmen, “lebih banyak 2” untuk bilangan asli, dll. tidak memiliki sifat refleksivitas.
Sikap R di satu set X ditelepon anti-reflektif, jika untuk elemen apa pun dari himpunan X selalu salah XRx: .
Ada hubungan yang tidak refleksif dan tidak anti-refleksif. Contoh hubungan seperti itu adalah hubungan “titik X simetris pada intinya pada relatif lurus aku", didefinisikan pada sekumpulan titik pada bidang. Memang semua titik satu garis lurus aku simetris terhadap dirinya sendiri, dan titik-titik yang tidak terletak pada suatu garis lurus aku, sendiri tidak simetris.
Sikap R di satu set X ditelepon simetris, jika kondisinya terpenuhi: dari fakta bahwa elemen tersebut X berhubungan dengan elemen tersebut kamu, maka elemen tersebut kamu ada hubungannya R dengan elemen X:xRyyRx.
Grafik relasi simetris mempunyai ciri-ciri sebagai berikut: beserta setiap anak panah yang datang X Ke kamu, grafik berisi panah yang berangkat dari kamu Ke X(Gbr. 35).
Contoh relasi simetris adalah: relasi “paralelisme” ruas-ruas, relasi “tegak lurus” ruas-ruas, relasi “persamaan” ruas-ruas, relasi keserupaan segitiga, relasi “persamaan” ruas-ruas, pecahan, dll.
Ada hubungan yang tidak memiliki sifat simetri.
Memang kalau segmennya X lebih panjang dari segmennya pada, lalu segmennya pada tidak boleh lebih panjang dari segmennya X. Grafik hubungan ini memiliki kekhasan: panah yang menghubungkan simpul-simpul diarahkan hanya ke satu arah.
Sikap R ditelepon antisimetris, jika untuk elemen apa pun X Dan kamu dari kebenaran xRy seharusnya salah tahunRx: : xRyyRx.
Selain relasi “lebih panjang”, terdapat relasi antisimetris lainnya di banyak segmen. Misalnya, relasi "lebih besar dari" untuk bilangan (jika X lagi pada, Itu pada tidak mungkin ada lagi X), sikap “lebih aktif”, dll.
Ada relasi yang tidak memiliki sifat simetri maupun antisimetri.
Relasi R pada suatu himpunan X ditelepon transitif, jika dari elemen itu X ada hubungannya R dengan elemen kamu, dan elemen kamu ada hubungannya R dengan elemen z, maka elemen tersebut X ada hubungannya R dengan elemen z: xRy Dan tahunRzxRz.
Grafik hubungan transitif dengan setiap pasang anak panah yang berasal X Ke kamu dan dari kamu Ke z, berisi panah yang berasal X Ke z.
Relasi “lebih panjang” pada sekumpulan segmen juga mempunyai sifat transitivitas: jika segmen A lebih panjang dari segmennya B, segmen garis B lebih panjang dari segmennya Dengan, lalu segmennya A lebih panjang dari segmennya Dengan. Relasi “kesetaraan” pada sekumpulan segmen juga memiliki sifat transitivitas: (sebuah=b, b=c)(a=c).
Ada hubungan yang tidak memiliki sifat transitivitas. Relasi seperti itu, misalnya, adalah relasi tegak lurus: jika suatu segmen A tegak lurus terhadap segmen tersebut B, dan segmennya B tegak lurus terhadap segmen tersebut Dengan, lalu segmennya A Dan Dengan tidak tegak lurus!
Ada sifat lain dari relasi, yang disebut sifat keterhubungan, dan relasi yang memiliki sifat tersebut disebut terhubung.
Sikap R di satu set X ditelepon terhubung, jika untuk elemen apa pun X Dan kamu dari himpunan ini kondisinya terpenuhi: jika X Dan kamu berbeda, maka keduanya X ada hubungannya R dengan elemen kamu, atau elemen kamu ada hubungannya R dengan elemen X. Dengan menggunakan simbol, hal ini dapat ditulis seperti ini: xyxRy atau tahunRx.
Misalnya, relasi “lebih besar dari” untuk bilangan asli memiliki sifat keterhubungan: untuk setiap bilangan berbeda x dan y, seseorang dapat menyatakan, baik x>y, atau kamu>x.
Dalam graf relasi terhubung, dua simpul mana pun dihubungkan oleh sebuah panah. Pernyataan sebaliknya juga benar.
Ada hubungan yang tidak memiliki sifat keterhubungan. Relasi seperti itu, misalnya, adalah relasi pembagian pada himpunan bilangan asli: kita dapat menamai bilangan tersebut x dan kamu berapa pun nomornya X bukan merupakan pembagi suatu bilangan kamu, atau nomor kamu bukan merupakan pembagi suatu bilangan X(angka 17 Dan 11 , 3 Dan 10 dll.) .
Mari kita lihat beberapa contoh. Di lokasi syuting X=(1, 2, 4, 8, 12) relasi "angka" diberikan X kelipatan dari nomor tersebut kamu" Mari kita buat grafik hubungan ini dan rumuskan propertinya.
Relasi persamaan pecahan dikatakan relasi ekivalen.
Sikap R di satu set X ditelepon hubungan kesetaraan, jika sekaligus mempunyai sifat refleksivitas, simetri dan transitivitas.
Contoh relasi ekivalen antara lain: relasi persamaan bangun ruang, relasi paralelisme garis (asalkan garis-garis yang berhimpitan dianggap sejajar).
Dalam hubungan “persamaan pecahan” yang dibahas di atas, himpunan X dibagi menjadi tiga himpunan bagian: ( ; ; }, {; } , (). Himpunan bagian ini tidak berpotongan, dan penyatuannya bertepatan dengan himpunan tersebut X, yaitu kami memiliki partisi himpunan ke dalam kelas.
Jadi, jika relasi ekuivalen diberikan pada himpunan X, maka relasi tersebut menghasilkan partisi himpunan ini menjadi himpunan bagian yang saling lepas berpasangan - kelas ekivalensi.
Jadi, kita telah menetapkan bahwa hubungan kesetaraan di himpunan
X=( ;; ; ; ; ) berhubungan dengan pembagian himpunan ini ke dalam kelas-kelas ekivalensi, yang masing-masing terdiri dari pecahan-pecahan yang sama satu sama lain.
Prinsip mempartisi suatu himpunan ke dalam kelas-kelas dengan menggunakan beberapa relasi ekuivalen merupakan prinsip penting dalam matematika. Mengapa?
Pertama, setara berarti setara, dapat dipertukarkan. Oleh karena itu, elemen-elemen dari kelas kesetaraan yang sama dapat dipertukarkan. Jadi, pecahan yang berada pada kelas ekuivalen yang sama (; ; ), tidak dapat dibedakan dari sudut pandang hubungan persamaan, dan pecahan bisa diganti dengan yang lain, misalnya . Dan penggantian ini tidak akan mengubah hasil perhitungan.
Kedua, karena kelas kesetaraan mengandung unsur-unsur yang tidak dapat dibedakan dari sudut pandang hubungan tertentu, maka diyakini bahwa kelas kesetaraan ditentukan oleh salah satu perwakilannya, yaitu. elemen sewenang-wenang dari kelas. Jadi, setiap kelas pecahan yang sama dapat ditentukan dengan menentukan pecahan mana pun yang termasuk dalam kelas tersebut. kelas kesetaraan oleh satu perwakilan memungkinkan Anda mempelajari sekumpulan perwakilan dari kelas kesetaraan alih-alih semua elemen himpunan. Misalnya, relasi ekivalensi “memiliki jumlah simpul yang sama”, yang didefinisikan pada suatu himpunan poligon, menghasilkan partisi himpunan ini ke dalam kelas-kelas segitiga, segi empat, segi lima, dll. properti yang melekat pada kelas tertentu dipertimbangkan pada salah satu perwakilannya.
Ketiga, mempartisi suatu himpunan ke dalam kelas-kelas menggunakan relasi ekuivalen digunakan untuk memperkenalkan konsep-konsep baru. Misalnya, konsep “kumpulan garis” dapat didefinisikan sebagai persamaan garis sejajar satu sama lain.
Jenis hubungan penting lainnya adalah hubungan keteraturan. Mari kita pertimbangkan masalahnya X={3, 4, 5, 6, 7, 8, 9, 10 ) relasi “memiliki sisa yang sama jika dibagi 3 " Relasi ini menghasilkan partisi dari himpunan X ke dalam kelas: semua bilangan akan menjadi satu, jika dibagi 3 ternyata sisanya 0 (ini adalah angka 3, 6, 9 ). Yang kedua - angka ketika dibagi 3 sisanya adalah 1 (ini adalah angka 4, 7, 10 ). Yang ketiga akan berisi semua angka itu, jika dibagi 3 sisanya adalah 2 (ini adalah angka 5, 8 ). Memang, himpunan yang dihasilkan tidak berpotongan dan kesatuannya berimpit dengan himpunan tersebut X. Oleh karena itu, relasi “memiliki sisa yang sama jika dibagi 3 ", ditentukan di set X, adalah relasi ekuivalen.
Contoh lain, banyaknya siswa dalam suatu kelas dapat diurutkan berdasarkan tinggi badan atau usia. Perhatikan bahwa hubungan ini memiliki sifat antisimetri dan transitivitas. Atau semua orang mengetahui urutan huruf dalam alfabet. Hal ini diwujudkan dengan sikap “seharusnya”.
Sikap R di satu set X ditelepon hubungan perintah yang ketat, jika sekaligus memiliki sifat antisimetri dan transitivitas. Misalnya, relasi " X< kamu».
Jika relasi tersebut mempunyai sifat refleksivitas, antisimetri, dan transitivitas, maka relasi tersebut akan menjadi seperti itu hubungan yang tidak ketat. Misalnya, relasi " Xkamu».
Contoh relasi keteraturan antara lain: relasi “kurang dari” pada himpunan bilangan asli, relasi “lebih pendek” pada himpunan segmen. Jika suatu relasi keteraturan juga mempunyai sifat keterhubungan, maka dikatakan demikian hubungan urutan linier. Misalnya relasi “kurang dari” pada himpunan bilangan asli.
Sekelompok X ditelepon tertib, jika hubungan pesanan ditentukan di atasnya.
Misalnya saja banyak X={2, 8, 12, 32 ) dapat diurutkan menggunakan relasi “kurang dari” (Gbr. 41), atau dapat dilakukan dengan menggunakan relasi “kelipatan” (Gbr. 42). Namun, sebagai relasi keteraturan, relasi “kurang dari” dan “kelipatan” mengurutkan himpunan bilangan asli dengan cara yang berbeda. Relasi “kurang dari” memungkinkan Anda membandingkan dua angka apa pun dari suatu himpunan X, tetapi relasi “kelipatan” tidak memiliki sifat ini. Oke, beberapa angka. 8 Dan 12 tidak berhubungan dengan relasi “kelipatan”: tidak dapat dikatakan demikian 8 banyak 12 atau 12 banyak 8.
Kita tidak boleh berpikir bahwa semua hubungan terbagi menjadi hubungan kesetaraan dan hubungan keteraturan. Ada sejumlah besar relasi yang bukan merupakan relasi ekivalensi maupun relasi keteraturan.
X (\gaya tampilan X) ditelepon hubungan tatanan parsial yang tidak ketat (hubungan pesanan, hubungan refleksif), jika adaSekelompok X (\gaya tampilan X), di mana relasi urutan parsial diperkenalkan, disebut dipesan sebagian. Relasi tatanan parsial yang tidak ketat sering dilambangkan dengan ≼ (\displaystyle \preccurlyeq ).
Pilihan
Hubungan pesanan parsial R (\gaya tampilan R) ditelepon urutan linier, jika syaratnya terpenuhi
∀ x ∀ y (x R y ∨ y R x) (\displaystyle \untuk semua x\untuk semua y(xRy\lor yRx)).Sekelompok X (\gaya tampilan X), di mana relasi tatanan linier diperkenalkan, disebut dipesan secara linear, atau rantai.
Sikap R (\gaya tampilan R), hanya memenuhi kondisi refleksivitas dan transitivitas saja yang disebut pre-order, atau quasi-order.
Perintah yang ketat
Jika kondisi refleksivitas digantikan oleh kondisi anti-refleksivitas:
∀ x ¬ (x R x) (\displaystyle \untuk semua x\neg (xRx)),maka kita mendapatkan definisinya ketat, atau tatanan parsial anti-refleksif(biasanya ditunjukkan dengan simbol ≺ (\displaystyle \prec )).
Komentar. Anti-refleksivitas dan transitivitas suatu hubungan secara simultan memerlukan antisimetri. Oleh karena itu hubungannya adalah hubungan perintah yang ketat jika dan hanya jika bersifat anti-refleksif dan transitif.
Secara umum, jika R (\gaya tampilan R) adalah relasi transitif dan antisimetris
R ≼ = R ∪ ( (x , x) | x ∈ X ) (\displaystyle R_(\preccurlyeq )=R\cup \((x,x)|x\in X\))- perintah refleksif R ≺ = R ∖ ( (x , x) | x ∈ X ) (\displaystyle R_(\prec )=R\setminus \((x,x)|x\in X\))- perintah ketat.Contoh
- Pada himpunan bilangan real, relasi “lebih dari” dan “kurang dari” merupakan relasi dengan tatanan ketat, dan “lebih dari atau sama dengan” dan “kurang dari atau sama dengan” adalah relasi non-ketat.
- Relasi keterbagian pada himpunan bilangan bulat merupakan relasi dengan tatanan tidak ketat.
Dimensi Dushnik-Miller
Cerita
Tanda-tanda < {\displaystyle <} Dan > (\gaya tampilan >) ditemukan
Kata “ketertiban” sering digunakan dalam berbagai macam masalah. Petugas memberi perintah: “Hitung dalam urutan numerik,” operasi aritmatika dilakukan dalam urutan tertentu, atlet diberi peringkat berdasarkan tinggi badan, semua pemain catur terkemuka disusun dalam urutan tertentu sesuai dengan apa yang disebut koefisien Elo (profesor Amerika yang mengembangkan sistem koefisien yang memungkinkan Anda memperhitungkan semua keberhasilan dan kegagalan para pemain), setelah kejuaraan, semua tim sepak bola disusun dalam urutan tertentu, dll. urutan kata dalam sebuah kalimat (coba pahami apa arti kalimat “on he old man” Saya tidak menanam keledai!”
Dengan menyusun unsur-unsur suatu himpunan tertentu satu demi satu, dengan demikian kita mengurutkannya atau menjalin hubungan di antara unsur-unsur tersebut dalam urutan. Contoh paling sederhana adalah orde natural bilangan asli. Kealamiannya terletak pada kenyataan bahwa untuk dua bilangan asli kita mengetahui mana yang mengikuti yang lain atau mana yang lebih besar dari yang lain, sehingga kita dapat menyusun bilangan-bilangan asli tersebut dalam suatu barisan sedemikian rupa sehingga letak bilangan yang lebih besar, misalnya ke sebelah kanan yang lebih kecil: 1, 2, 3, ... . Tentu saja urutan elemen dapat ditulis ke segala arah, tidak hanya dari kiri ke kanan. Konsep bilangan asli sendiri sudah mengandung gagasan tentang keteraturan. Dengan menetapkan beberapa susunan relatif dari elemen-elemen suatu himpunan, dengan demikian kita mendefinisikan beberapa relasi tatanan biner, yang dalam setiap kasus tertentu mungkin memiliki namanya sendiri, misalnya, “menjadi lebih kecil”, “menjadi lebih tua”, “menjadi terkandung dalam ", "ikuti", dst. Sebutan simbolis keteraturan juga bisa bermacam-macam, misalnya Í, dst.
Ciri pembeda utama dari suatu relasi keteraturan adalah bahwa ia mempunyai sifat transitivitas. Jadi, jika kita berhadapan dengan rangkaian beberapa objek x 1, x 2, ..., xn,..., diurutkan, misalnya berdasarkan relasi, lalu dari apa yang dilakukan x 1x 2... xn..., hal itu harus diikuti untuk pasangan mana pun x saya, xj elemen urutan ini juga terpenuhi x sayaxj:
Untuk sepasang elemen x sayaJ dalam grafik relasi kita menggambar panah dari titik x saya ke atas xj, yaitu dari elemen yang lebih kecil ke elemen yang lebih besar.
Grafik relasi keteraturan dapat disederhanakan dengan menggunakan apa yang disebut metode diagram Hasse. Diagram Hasse dibangun sebagai berikut. Elemen yang lebih kecil ditempatkan lebih rendah, dan elemen yang lebih besar ditempatkan lebih tinggi. Karena aturan seperti itu saja tidak cukup untuk menggambarkannya, garis-garis digambar untuk menunjukkan elemen mana yang lebih besar dan mana yang lebih kecil dari elemen lainnya. Dalam hal ini, cukup menggambar garis saja untuk elemen-elemen yang saling mengikuti satu sama lain. Contoh diagram Hasse ditunjukkan pada gambar:
Anda tidak harus menyertakan panah dalam diagram Hasse. Diagram Hasse dapat diputar pada suatu bidang, tetapi tidak sembarangan. Saat memutar, perlu untuk mempertahankan posisi relatif (atas - bawah) dari simpul diagram:
Sikap R dalam kelimpahan X ditelepon sikap ketertiban yang ketat, jika bersifat transitif dan asimetris.
Himpunan yang relasi keteraturannya terdefinisi disebut dipesan. Misalnya, himpunan bilangan asli diurutkan berdasarkan relasi “kurang dari”. Tetapi himpunan yang sama ini juga diurutkan oleh relasi lain - "dibagi menjadi" dan "lebih".
Grafik relasi “kurang dari” pada himpunan bilangan asli dapat digambarkan sebagai sinar:
Sikap R V X disebut relasi tatanan tidak ketat (sebagian)., jika bersifat transitif dan antisimetris. Setiap hubungan dengan tatanan yang tidak ketat bersifat refleksif.
Julukan "parsial" mengungkapkan fakta bahwa mungkin tidak semua elemen suatu himpunan dapat dibandingkan dalam suatu hal tertentu.
Contoh umum dari relasi tatanan parsial adalah relasi “tidak lebih besar dari”, “tidak kurang dari”, dan “tidak lebih besar dari”. Partikel “tidak” dalam nama hubungan berfungsi untuk mengekspresikan refleksivitasnya. Relasi “tidak lebih dari” bertepatan dengan relasi “kurang dari atau sama dengan”, dan relasi “tidak kurang” sama dengan “lebih besar dari atau sama”. Dalam hal ini, tatanan parsial disebut juga tidak tegas dalam urutan. Seringkali relasi tatanan parsial (tidak ketat) dilambangkan dengan simbol "".
Relasi penyertaan Í antara himpunan bagian dari himpunan tertentu juga merupakan tatanan parsial. Jelasnya, tidak setiap dua himpunan bagian dapat dibandingkan dalam hal ini. Gambar di bawah menunjukkan urutan penyertaan sebagian pada himpunan semua himpunan bagian (1,2,3). Panah pada grafik yang seharusnya mengarah ke atas tidak ditampilkan.
Himpunan yang urutan parsialnya diberikan disebut dipesan sebagian, atau sederhananya dipesan set.
Elemen X Dan pada himpunan terurut sebagian disebut bandingkan dengan kita Jika Xpada atau padaX. Kalau tidak, mereka tidak bisa dibandingkan.
Himpunan terurut yang dua elemennya sebanding disebut dipesan secara linear, dan urutannya adalah urutan linier. Tatanan linier disebut juga tatanan sempurna.
Misalnya, himpunan semua bilangan real dengan tatanan alami, serta semua himpunan bagiannya, diurutkan secara linier.
Objek dengan sifat paling bervariasi dapat dipesan secara hierarkis. Berikut beberapa contohnya.
Contoh 1: Bagian-bagian buku disusun sedemikian rupa sehingga buku berisi bab, bab berisi bagian, dan bagian berisi subbagian.
Contoh 2. Folder dalam sistem file komputer bertumpuk satu sama lain, membentuk struktur percabangan.
Contoh 3 Hubungan antara orang tua dan anak dapat digambarkan sebagai apa yang disebut pohon keluarga, yang menunjukkan siapa nenek moyang (atau keturunannya).
Biarkan di lokasi syuting A urutan parsial diberikan. Elemen X ditelepon maksimum (minimum) elemen himpunan A, jika dari fakta itu Xpada(padaX), kesetaraan mengikuti X= kamu. Dengan kata lain, elemennya X adalah maksimum (minimum) jika untuk elemen apa pun pada atau tidak benar itu Xpada(padaX), atau dijalankan X=kamu. Jadi, elemen maksimum (minimum) lebih besar (lebih kecil) dari semua elemen yang berbeda dengannya yang ada hubungannya.
Elemen X ditelepon terbesar (terkecil), jika untuk siapa pun padaÎ A dilakukan pada< х (х< у).
Himpunan terurut sebagian dapat mempunyai beberapa elemen minimum dan/atau maksimum, tetapi tidak boleh lebih dari satu elemen minimum dan maksimum. Unsur terkecil (terbesar) juga merupakan unsur minimum (maksimum), namun tidak berlaku sebaliknya. Gambar di sebelah kiri menunjukkan urutan parsial dengan dua elemen minimum dan dua maksimum, dan di sebelah kanan menunjukkan urutan parsial dengan elemen terkecil dan terbesar:
Dalam himpunan terurut sebagian berhingga selalu terdapat elemen minimum dan maksimum.
Himpunan terurut yang mempunyai anggota terbesar dan terkecil disebut terbatas. Gambar tersebut menunjukkan contoh himpunan berbatas tak hingga. Tentu saja, tidak mungkin menggambarkan himpunan tak hingga pada halaman berhingga, tetapi Anda dapat menunjukkan prinsip konstruksinya. Di sini loop di dekat simpul tidak ditampilkan untuk menyederhanakan gambar. Untuk alasan yang sama, busur yang memberikan tampilan properti transitivitas tidak ditampilkan. Dengan kata lain, gambar tersebut menunjukkan diagram Hasse dari relasi keteraturan.
Himpunan tak hingga mungkin tidak mempunyai elemen maksimum atau minimum, atau keduanya. Misalnya, himpunan bilangan asli (1,2, 3, ...) mempunyai elemen terkecil 1, tetapi tidak ada maksimum. Himpunan semua bilangan real berorde natural tidak mempunyai unsur terkecil maupun terbesar. Namun, subsetnya terdiri dari semua angka X< 5, mempunyai unsur terbesar (angka 5), tetapi tidak mempunyai unsur terkecil.
