Sambungan dan pertemuan (matematika)

Relasi biner
Simetrik Antisimetrik Connex Ditemukan baik Telah bersambung Telah bertemu Relasi ekuivalen ✓ ✗ ✗ ✗ ✗ ✗ Praurutan (Kuasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Urutan parsial ✗ ✓ ✗ ✗ ✗ ✗ Praurutan total ✗ ✗ ✓ ✗ ✗ ✗ Urutan total ✗ ✓ ✓ ✗ ✗ ✗ Pra-urutan rapi ✗ ✗ ✓ ✓ ✗ ✗ Kuasi urutan rapi ✗ ✗ ✗ ✓ ✗ ✗ Urutan rapi ✗ ✓ ✓ ✓ ✗ ✗ Kisi ✗ ✓ ✗ ✗ ✓ ✓ Sambungan-semikekisi ✗ ✓ ✗ ✗ ✓ ✗ Pertemuan-semikekisi ✗ ✓ ✗ ✗ ✗ ✓
Simbol "✓" menunjukkan bahwa sifat kolom diperlukan dalam definisi baris. Misalnya, definisi relasi ekuivalen diperlukan menjadi simetris. Semua definisi secara diam-diam memerlukan ketransitifan dan refleksivitas.

Diagram Hasse menggambarkan himpunan yang tersusun sebagian dengan empat elemen: a, b, elemen maksimal sama dengan gabungan dari a dan b yaitu (a ∨ b) dan elemen minimal sama dengan pertemuan a dan b yaitu (a ∧ b). Gabungan/bertemu elemen maksimal/minimal dan elemen lainnya adalah elemen maksimal/minimal dan sebaliknya bertemu/gabungan suatu elemen maksimal/minimal dengan elemen lainnya adalah elemen lainnya. Jadi setiap pasangan dalam poset ini memiliki pertemuan dan gabungan dan poset dapat diklasifikasikan sebagai kisi (teori order).

Dalam matematika, khususnya teori order, sambungan dari himpunan bagian S dari himpunan terurut parsial P adalah supremum (batas atas terkecil) dari S dirumuskan sebagai ⋁S, untuk pertemuan dari S adalah infimum (batas bawah terbesar), dirumuskan sebagai ⋀S. Secara umum, sambungan dan pertemuan dari himpunan bagian adalah himpunan terurut parsial. Sambungan dan pertemuan adalah ganda dengan relasi untuk balikan urutan.

Himpunan terurut parsial dimana semua relasi menggunakan sambungan adalah sambungan semikekisi. Secara ganda, himpunan terurut parsial dimana semua relasi menggunakan pertemuan adalah semikekisi bertemu. Himpunan terurut parsial merupakan sambungan semikekisi dan semikekisi bertemu adalah kekisi. Sebuah kekisi yang mana setiap himpunan bagian, untuk relasi menggunakan pertemuan dan sambungan adalah kekisi lengkap. Mendefinisikan kekisi parsial, dimana tidak semua relasi bertemu atau bergabung, operasi (jika ditentukan) memenuhi aksioma tertentu.

Gabungan/bertemu himpunan bagian dari himpunan terurut total adalah elemen maksimal/minimal, jika elemen tersebut tersedia.

Jika himpunan S dari himpunan terurut parsial P merupakan (atas) himpunan terarah, maka gabungan disebut gabungan terarah atau supremum terarah. Secara ganda, jika S adalah himpunan terarah ke bawah, maka pertemuan adalah pertemuan terarah atau infimum terarah.

Pendekatan

Pendekatan urutan parsial

Misalkan A adalah himpunan dengan urutan parsial ≤, dan misalkan x dan y adalah dua elemen dalam A. Elemen z dari A adalah pertemuan (atau batas bawah terbesar atau paling kecil) dari x dan y, jika dua kondisi berikut:

• z ≤ x dan z ≤ y: z adalah batas bawah dari x dan y).
• Untuk setiap w dalam A adalah w ≤ x dan w ≤ y, menggunakan w ≤ z: z lebih besar dari atau sama dengan batas bawah lainnya dari x dan y).

Jika pertemuan x dan y, karena z dan z′ adalah batas bawah terbesar dari x dan y, maka z ≤ z′ dan z′ ≤ z, dan z = z′. Jika pertemuan diatas tersebut dirumuskan sebagai x ∧ y. Beberapa relasi elemen dalam A tidak menggunakan pertemuan, baik karena tidak memiliki batas bawah sama sekali, atau karena tidak ada batas bawah yang lebih besar dari yang lainnya. Jika semua relasi elemen dari A bertemu adalah operasi biner pada A, dan mudah untuk melihat bahwa operasi memenuhi tiga kondisi berikut: untuk elemen x, y, dan z dalam A,

a. x ∧ y = y ∧ x (komutatif),

b. x ∧ (y ∧ z) = (x ∧ y) ∧ z (asosiatif), dan

c. x ∧ x = x (idempotensi).

Gabungan didefinisikan dua kali, dan gabungan dari x dan y dalam A dirumuskan dengan x ∨ y. Jika tidak semua relasi elemen dari A bertemu, maka bertemu masih bisa dilihat sebagai operasi biner parsial dari A.

Pendekatan aljabar universal

Menurut definisi, operasi biner ∧ pada himpunan A adalah bertemu jika memenuhi tiga kondisi a, b, dan c. Relasi (A, ∧) kemudian menjadi pertemuan semikekisi. Selain itu, mendefinisikan relasi biner ≤ atas A, dengan x ≤ y jika dan hanya jika x ∧ y = x. Faktanya, relasi ini adalah urutan parsial pada A. Untuk elemen x, y, dan z dalam A adalah

• x ≤ x, karena x ∧ x = x by c;
• jika x ≤ y dan y ≤ x, maka

x = x ∧ y = y ∧ x = y oleh a; dan

• jika x ≤ y dan y ≤ z, maka x ≤ z, dari x ∧ z = (x ∧ y) ∧ z = x ∧ (y ∧ z) = x ∧ y = x oleh b.

Perhatikan bahwa dua pertemuan dan sambungan menggunakan definisi ini: beberapa operasi pertemuan dan sambungan yang terkait menghasilkan pesanan parsial yang merupakan kebalikan dari satu sama lain. Memilih salah satu dari urutan sebagai yang utama, satu memperbaiki operasi dimana adalah pertemuan (yang memberi urutan yang sama) dan dimana adalah sambungan (yang lain).

Kesetaraan pendekatan

Jika (A, ≤) adalah himpunan terurut parsial, setiap relasi elemen dalam A menggunakan pertemuan, maka x ∧ y = x jika dan hanya jika x ≤ y, karena dalam kasus terakhir memang x adalah batas bawah dari x dan y, karena jelas x adalah batas bawah terbesar jika dan hanya jika adalah batas bawah. Jadi, urutan parsial yang ditentukan oleh pertemuan dalam pendekatan aljabar universal bertepatan dengan urutan parsial asli.

Sebaliknya, jika (A, ∧) adalah pertemuan semikekisi, dan urutan parsial ≤ didefinisikan dalam pendekatan aljabar universal, dan z = x ∧ y untuk beberapa elemen x dan y dalam A, maka z adalah batas bawah terbesar dari x dan y dengan ≤, maka

z ∧ x = x ∧ z = x ∧ (x ∧ y) = (x ∧ x) ∧ y = x ∧ y = z

dan oleh karena itu z ≤ x. Demikian pula, z ≤ y, dan jika w adalah batas bawah lain dari x dan y, maka w ∧ x = w ∧ y = w, adalah

w ∧ z = w ∧ (x ∧ y) = (w ∧ x) ∧ y = w ∧ y = w.

Jadi, bertemu yang ditentukan oleh urutan parsial yang ditentukan oleh pertemuan awal, dan keduanya bertemu bertepatan.

Dengan kata lain, kedua pendekatan tersebut pada dasarnya menghasilkan konsep ekuivalen, himpunan dengan relasi biner dan operasi biner, dari struktur menentukan yang lainnya, dan menggunakan persyaratan untuk urutan parsial.

Pertemuan mengenai himpunan bagian umum

Jika (A, ∧) adalah pertemuan semikekisi, maka pertemuan diperluas ke pertemuan yang didefinisikan dengan baik dari suatu himpunan hingga takkosong, dengan teknik yang dijelaskan dalam operasi biner teriterasi. Atau, jika bertemu menentukan atau ditentukan oleh urutan parsial, beberapa himpunan bagian dari A menggunakan infimum dengan relasi, dan untuk mempertimbangkan sedikit mungkin bertemu himpunan bagian tersebut. Untuk himpunan bagian hingga tidak kosong, dua pendekatan tersebut menghasilkan hasil yang sama, maka dua pendekatan tersebut sebagai definisi pertemuan. Dalam kasus dimana setiap himpunan bagian dari bertemu A, maka (A, ≤) adalah kekisi lengkap; untuk detailnya, lihat kelengkapan (teori order).

Referensi

• Davey, B.A.; Priestley, H.A. (2002). Introduction to Lattices and Order (edisi ke-2nd). Cambridge: Cambridge University Press. ISBN 0-521-78451-4. Zbl 1002.06001. 
• Vickers, Steven (1989). Topology via Logic. Cambridge Tracts in Theoretic Computer Science. 5. ISBN 0-521-36062-5. Zbl 0668.54001.