Relacija poretka

#fax #math #ds1 #a1 [deo poglavlja "relacija"]

Def. Binarna relacija je relacija strogog (parcijalnog) poretka ako je (AR), (S) i (T). Oznaka: .
Def. Binarna relacija je relacija nestrogog (parcijalnog) poretka ako je (R), (S) i (T). Oznaka: .

Def. Ako je u skupu uvedena relacija parcijalnog poretka, tada je taj skup uređen ili se zove poset.

Def. su uporedivi ako važi ili

Def. Ako su u skupu svaka dva elementa uporediva, tada je taj skup totalno uređen i relacija je totalnog (umesto da bude parcijalnog) poretka.

Def. Podskup skupa je lanac ako su u njemu svaka dva elementa uporediva.
Def. Podskup skupa je antilanac ako u njemu svaka dva elementa nisu uporediva.
Neki podskup može biti ni lanac ni antilanac.

Primer



Relacija u skupu

  • (R)
    (AS)
    (T)
    jeste relacija nestrogog poretka.
  • i nisu uporedivi nije totalno uređen.
  • Lanac:
  • Antilanac: - svaka dva nisu uporediva

Haseov dijagram:
haseov dijagram primer 1.png
Svaka linija predstavlja relaciju između dva elementa tako da (donji element) (gornji element). Ali relacije kao na primer se ne označavaju jer "prolaze" kroz drugi element

Najmanji, najveći, minimalni, maksimalni

Def. Neka je relacija nestrogog parcijalnog poretka u skupu , . Tada:

  • je najmanji element u ako
  • je najveći element u ako
  • je minimalni element u ako
  • je maksimalni element u ako

Na haseovom dijagramu:

  • Najmanji — jedinstven donji element, koji je povezan sa svim ostalim elementima.
  • Najveći — jedinstven gornji element, koji je povezan sa svim ostalim elementima.
  • Minimalni — element koji nema veza sa elementima dole od sebe.
  • Maksimalni — element koji nema veza sa elementima gore od sebe.

Primer 1:

Relacija je zadata dijagramom
haseov dijagram primer 2.png
je najmanji i minimalni
i su maksimalni
najveći ne postoji

Primer 2:

Relacija je zadata dijagramom
haseov dijagram primer 3.png
je najmanji i minimalni
je maksimalni
najveći ne postoji

Teorema. Ako najmanji (najveći) element, tada

  1. je jedinstven najmanji (najveći) element
  2. je jedinstven minimalni (maksimalni) element

Napomena: U totalno uređenom skupu pojmove najmanji i minimalni, najveći i maksimalni se poklapaju.

Donje i gornje ograničenje. Infinum i supremum

Def. Neka je relacija nestrogog parcijalnog poretka u skupu , . Tada:

  • je donje ograničenje (minoranta) skupa ako
  • je ograničen odozdo ako takvo postoji
  • Skup donjih ograničenja je č
  • Najveće donje ograničenje skupa ako postoji zove se infinum:
  • je gornje ograničenje (majoranta) skupa ako
  • je ograničen odozgo ako takvo postoji
  • Skup gornjih ograničenja je č
  • Najmanje gornje ograničenje skupa ako postoji zove se supremum:
  • je ograničen ako je ograničen odozdo i odozgo.

Primer:

- skup donjih ograničenja;
- skup gornjih ograničenja;

Relacija u skupu

Stav.

  • je minimum (najmanji el) skupa akko je
  • je maksimum (najveći el) skupa akko je

Stav.

Dokaz za , za analagno

  1. je majoranta
  2. pps nije najmanja majoranta
    , gde je majoranta (tj. )
    kontradikcija

Stav.

Dokazivanje da je supremum (infinum) skupa :

  1. je majoranta:
    • Ako
    • Ako , treba pokazati

      (Za proizvoljno naći koristeći (ARH))