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, gabungan dari himpunan bagian S dari himpunan terurut parsial P adalah supremum (batas atas terkecil) dari S dirumuskan sebagai ⋁S, untuk bertemu dari S adalah infimum (batas bawah terbesar), dirumuskan sebagai ⋀S. Secara umum, gabungan dan bertemu dari himpunan bagian adalah himpunan berurutan parsial. Gabungan dan bertemu adalah dualitas dengan relasi untuk inversi urutan.

Himpunan berurutan parsial dimana semua relasi menggunakan gabungan adalah semikisi gabungan. Dualitas, himpunan berurutan parsial dimana semua relasi menggunakan bertemu adalah semikisi bertemu. Himpunan terurut parsial merupakan semikisi gabungan dan semikisi bertemu adalah kisi. Kisi dimana setiap himpunan bagian, untuk relasi menggunakan bertemu dan gabungan adalah kisi kompleks. Mendefinisikan kisi 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 berurutan parsial P merupakan (atas) himpunan terarah, maka gabungan disebut gabungan terarah atau supremum terarah. Dualitas, jika S adalah himpunan terarah bawah, maka bertemu adalah bertemu 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 bertemu (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 bertemu 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 bertemu diatas tersebut dirumuskan sebagai x ∧ y. Beberapa relasi elemen dalam A tidak menggunakan bertemu, 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 semikisi bertemu. 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 bertemu dan gabungan menggunakan definisi ini: beberapa operasi bertemu dan gabungan 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 bertemu (yang memberi urutan yang sama) dan dimana adalah gabungan (yang lain).

Pendekatan ekuivalen

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 bertemu dalam pendekatan aljabar universal bertepatan dengan urutan parsial asli.

Sebaliknya, jika (A, ∧) adalah semikisi bertemu, 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.

Bertemu himpunan bagian umum

Jika (A, ∧) adalah semikisi bertemu, maka bertemu diperluas ke bertemu yang ditentukan dengan baik dari setiap himpunan himpunan tidak-kosong, 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 kisi kompleks; 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.