Relacije urejenosti

Relacije urejenosti

Definicija: Relacija R ⊆ A × A je:

Za relacije urejenosti ponavadi uporabljamo simbole, ki spominjajo na znak , kot so , , , ...

Primeri urejenosti

  1. Relacija deljivosti na naravnih številih je delna urejenost.
  2. Relacija deljivosti na celih številih je šibka urejenost, ni pa delna urejenost.
  3. Relacija na realnih številih je linearna urejenost.
  4. Relacija na P(A) je delna urejenost. Za katere množice A je linearna?
  5. Relacija = je delna urejenost.

Hassejev diagram

Končno delno ureditev (A, ≤) lahko predstavimo s Hassejevim diagramom: elemente množice A narišemo tako, da je x pod y, kadar velja x ≤ y. Nato povežemo vozlišči x in y, če je y neposredni naslednik x, se pravi, da velja x ≠ y, x ≤ y in iz x ≤ z ≤ y sledi x = z ∨ z = y.

Primer: kakšen je Hassejev diagram relacije deljivosti na množici {0, 1, ..., 10}?

Primer: kakšen je Hassejev diagram relacije na množici P({a,b,c})?

Operacije na urejenostih

Obratna urejenost

Če je delna urejenost na P potem je tudi transponirana relacija , definirana z

x ≥ y ⇔ x ≤ y

delna urejenost na P. Če je linearna, je linearna.

Produktna in leksikografska urejenost

Naj bosta (P, ≤) in (Q, ⊑) delni urejenosti. Na kartezičnem produktu P × Q lahko definiramo dve urejenosti:

Obse sta delni urejenosti. Če sta P in Q linearno urejena, je tudi leksikografska urejenost linearna.

Primer: Kako si predstavljamo produktno in leksikografsko ureditev na [0,1] × [0,1], če [0,1] uredimo z običajno relacijo ?

Vsota urejenosti

Naj bosta (P, ≤) in (Q, ⊑) delni urejenosti. Na vsoti P + Q lahko definiramo urejenost s predpisom:

u ≼ v ⇔ (∃ x, y ∈ P . u = ι_1(x) ∧ v = ι_1(y) ∧ x ≤ y) ∨
        (∃ s, t ∈ Q . u = ι_2(s) ∧ v = ι_2(t) ∧ s ⊑ t)

Potenca urejenosti

Naj bo (P, ≤) delna urejenost in A množica. Na P^A lahko definiramo urejenost s predpisom:

f ≼ g ⇔ ∀ x ∈ A . f(x) ≤ g(x)

Delna urejenost, inducirana s šibko ureditvijo

Naj bo (P, ≤) šibka ureditev. Relacija na P, definirana s predpisom

x ∼ y ⇔ x ≤ y ←and y ≤ x

je ekvivalenčna relacija. Na kvocienty P/∼ lahko definiramo relacijo s predpisom

[x] ≼ [y] ⇔ x ≤ y

Relacija je delna ureditev.

Primer: Obravnavajmo cela števila Z in deljivost |, ki je šibka ureditev. Za vse k, m ∈ Z velja

k ∼ m ⇔ k | m ∧ m | k ⇔ |k| = |m|

Torej je Z/∼ ≅ N, kjer izomorfizem preslika [k] ↦ |k|. Delna ureditev na Z/∼ inducirana z deljivostjo je spet deljivost (ko jo prenesemo iz Z/∼ na N s pomočjo izomorfizma).

Monotone preslikave

Definicija: Preslikava f : P → Q med delnima urejenostma (P, ≼) in (Q, ⊑) je monotona (ali naraščajoča), ko velja ∀ x, y ∈ P . x ≼ y ⇒ f(x) ⊑ f(y).

Definicija: Preslikava f : P → Q med delnima urejenostma (P, ≼) in (Q, ⊑) je antitona (ali padajoča), ko velja ∀ x, y ∈ P . x ≼ y ⇒ f(y) ⊑ f(x).

Opozorilo: v analizi "monotona" pomeni "monotona ali antitona". To ni nič čudnega, ker "dan" tudi pomeni "dan in noč".

Izrek: Kompozicija monotonih preslikav je monotona. Identita je monotona.

Dokaz. Naj bosta f : P → Q in g : Q → R monotoni preslikavi med delnimi urejenostmi (P, ≤_P), (Q, ≤_Q) in (R, ≤_R). Če je x ≤_P y, potem je zaradi monotonisti f tudi f(x) ≤_Q f(y), nato pa je zaradi monotonisti g spet g(f(x)) ≤_R g(f(y)). Identiteta je očitno monotona.

Primeri

Meje

Definicija: Naj bo (P, ≤) delna urejenost, S ⊆ P in x ∈ P:

Opozorilo: minimalni element ni isto kot minimum (in maksimalni element ni isto kot maksimum).

Kadar govorimo o "prvem elementu" ali "maksimalnem elementu" in ne povemo, na katero podmnožico se nanaša element, imamo običajno v mislih kar celotno delno ureditev.

Izrek: Naj bo (P, ≤) delna urejenost in S ⊆ P. Tedaj ima S največ en infimum in največ en supremum, ki ju zapišemo inf S in sup S, kadar obstajata.

Dokaz. Denimo, da sta x in y oba infimum S. Ker je y spodnja meja za S in x njen infimum, velja y ≤ x. Podobno velja x ≤ y, torej x = y. Za supremum je dokaz podoben. □

Primer: Supremum končne neprazne množice S ⊆ N za relacijo deljivosti | je namanjši skupni večkratnik elementov iz S. Infimum je navečji skupni delitelj. Kaj pa, če je S prazna ali neskončna?

Mreže

Definicija: Naj bo (P, ≤) delna urejenost:

  1. (P, ≤) je mreža, ko imata vsaka dva elementa x, y ∈ P infimum in supremum.
  2. (P, ≤) je omejena mreža, ko ima vsaka končna podmnožica P infimum in supremum.
  3. (P, ≤) je polna mreža, ko ima vsaka podmnožica P infimum in supremum.

Infimum in supremum elementov x in y pišemo x ∧ y in x ∨ y.

Izrek: Delna urejenost (P, ≤) je omejena mreža natanko tedaj, ko ima najmanši in največji element, ter imata vsaka sva elementa infimum in supremum.

Dokaz.

Denimo, da je (P, ≤) omejana mreža. Tedaj P ima najmanši element, namreč sup ∅, in največji element, namreč inf ∅. Infimum in supremum x in y sta seveda inf {x, y} in sup {x, y}.

Denimo, da ima P najmanši element ⊥_P in največji element ⊤_P, vsaka dva elementa pa imata infimum in supremum. Naj bo S ⊆ P končna množica:

Primeri: