Relasi Parsial Order (POSET)

DEFINISI 1: Suatu relasi biner pada sebuah himpunan disebut suatu urutan parsial/ partial ordering pada jika bersifat :

1. REFLEKSI :
jika relasi R terhadap A disebut memiliki sifat refleksif, jika setiap elemen A berhubungan dengan dirinya.

Untuk setiap a∈A, (a,a)∈A
atau
Untuk setiap a ∈A, aRa

2. ANTISIMETRI :
untuk setiap asumsi a dan b berlainan, maka relasi macam ini disebut relasi anti-simetrik.

Untuk setiap a,b∈A, a=/b -> ((a,b)∈R -> (b,a)∈/R)
atau
Untuk setiap a,b∈A, a=/b -> (aRb -> ~(bRa))

Dalam kebanyakan literatur biasanya ditulis sebagai kontraposisinya seperti di bawah ini. Keuntungan bentuk ini adalah tidak mengandung negasi, dan hanya mengandung satu implikasi.

Untuk setiap a,b∈A, (a,b)∈R & (b,a)∈R -> a=b
atau
Untuk setiap a,b∈A, aRb & bRa -> a=b

3. TRANSITIF :
relasi disebut transitif jika memiliki sifat, jika a berhubungan dengan b, dan b berhubungan dengan c, maka a berhubungan dengan c secara langsung.

(a,b)∈R & (b,c)∈R ->(a,c)∈R
atau
untuk setiap a,b,c∈A, aRb & bRc -> aRc

Contoh POSET
Relasi "kurang dari sama dengan" pada Z
Relasi "habis membagi" pada Z
Relasi "subset" pada powerset(himpunan kuasa)
Relasi "lebih dari sama dengan" pada Z


DEFINISI 2: Misalkan (S , ≤) adalah POSET,a dan b∈S , maka :
a dan b comparable jika a ≤b atau b≤a .
a dan b noncomparable jika a≰ b dan b≰ a.


DEFINISI 3: Suatu urutan parsial ≤ pada himpunan disebut suatu urutan total atau urutan linier/ total order atau linear order, jika berlaku: ∀ x,y ∈S |x ≤y atau y ≤x , artinya setiap pasangan di comparable. Pasangan (S , ≤) disebut himpunan terurut linier/ linearly ordered set atau sebuah rantai/ CHAIN.


DEFINISI 4: Jika(S , ≤) adalah sebuah POSET, A⊆S daN A ≠ ∅,maka:
a ∈A disebut elemen minimal dari A jika: tidak ada x∈A sedemikian sehingga x≤a
a∈A disebut elemen maksimal dari A jika: tidak ada x∈A sedemikian sehingga a≤x
a∈A disebut elemen terkecill dari A jika: a≤x , ∀x ∈A
a∈A disebut elemen terbesar dari A jika: x≤a , ∀x ∈A
b∈S disebut batas bawah dari A jika: b≤x , ∀x ∈A
b∈S disebut batas atas dari A jika:x ≤b , ∀x ∈A
b∈S disebut batas bawah terbesar/infimum dariA jika: untuk setiap c yang merupakan batas bawah lain dari A, berlaku c≤b .
b∈S disebut batas atas terkecil/supremum dari A jika: untuk setiap c yang merupakan batas atas lain dari A , berlaku b≤c