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