Uredni odnosi. Odnos reda

Riječ "naredba" se često koristi u raznim pitanjima. Oficir daje komandu: „Prema redosledu brojeva računaj“, aritmetičke radnje se izvode određenim redosledom, sportisti se rangiraju po visini, postoji redosled izvođenja radnji prilikom izrade dela i redosled reči. u rečenici.

Šta je zajedničko u svim slučajevima kada se govori o redu? Činjenica je da riječ „red“ ima sljedeće značenje: označava koji element datog skupa slijedi nakon kojeg (ili koji element prethodi kome).

stav " X slijedi at" tranzitivno: ako " X slijedi at" i " at slijedi z", to" x slijedi z" Osim toga, ovaj odnos mora biti antisimetričan: za dva različita X I at, Ako X slijedi at, To at ne prati X.

Definicija. Stav R na setu X pozvao odnos strogog reda, ako je tranzitivan i antisimetričan.

Otkrijmo karakteristike grafa i grafa relacija strogog reda.

Pogledajmo primjer. Na snimanju X= (5, 7, 10, 15, 12) dati omjer R: « X < at" Definirajmo ovu relaciju navođenjem parova
R = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.

Napravimo njegov graf. Vidimo da graf ove relacije nema petlje. Na grafikonu nema dvostrukih strelica. Ako od X strelica ide na at, i od at- V z, zatim od X strelica ide na z(Sl. 8).

Konstruisani graf vam omogućava da rasporedite elemente skupa X ovim redoslijedom:

{5, 7, 10, 12, 15}.

Na slici 6 (§ 6 ovog poglavlja), kolone VII, VIII su grafovi relacija strogog reda.

Nestrogi odnos

Suprotnost odnosu „manje od“ u skupu realnih brojeva je relacija „ne manje“. To više nije odnos strogog reda. Poenta je kada X = at, odnosi su ispunjeni X ³ at I at ³ X, tj. “ne manje” stav je refleksivan.

Definicija. Stav R na setu X pozvao nestriktnog odnosa, ako je refleksivan, antisimetričan i tranzitivan.

Takvi odnosi su zajednice odnosa strogog poretka sa odnosom identiteta.

Razmotrimo relaciju “nema više” (£) za skup

X= (5, 7, 10, 15, 12). Napravimo njegov graf (slika 9).

Graf odnosa nestrogog reda, za razliku od grafa relacija strogog reda, ima petlje na svakom vrhu.

Na sl. 6 (§ 6 ovog poglavlja) kolone V, VI su grafovi relacija nestrogog reda.

Naručeni setovi

Skup se može pokazati uređenim (također kažu potpuno uređen) nekom relacijom reda, dok drugi skup može biti neuređen ili djelomično uređen takvom relacijom.

Definicija. Gomila X pozvao naredio neki odnos poretka R, ako za bilo koja dva elementa x, y od X:

(X, at) Î R ili ( y, x) Î R.

Ako R je odnos strogog reda, zatim skup X naređeno ovim odnosom pod uslovom: ako X, at bilo koja dva nejednaka elementa skupa X, To ( X, at) Î R ili ( y, x) Î R, ili bilo koja dva elementa x, y setovi X su jednaki.

Iz školskog predmeta matematike se zna da su skupovi brojeva N , Z , Q , R poredano relacijom "manje od" (<).

Skup podskupova određenog skupa nije uređen uvođenjem inkluzivne relacije (I), odnosno stroge inkluzije (S) u gornjem smislu, jer postoje podskupovi od kojih nijedan nije uključen u drugi. U ovom slučaju kažemo da je dati skup djelimično uređen relacijom Í (ili Ì).

Razmotrite set X= (1, 2, 3, 4, 5, 6) i sadrži dvije relacije “manje od” i “podijeljeno”. Lako je provjeriti da su oba ova odnosa odnosi poretka. Graf relacije “manje od” može se prikazati kao zraka.

Grafikon relacije “podijeljeno sa” može se prikazati samo na ravni.

Osim toga, graf druge relacije ima vrhove koji nisu povezani strelicom. Na primjer, ne postoji strelica koja povezuje brojeve 4 i 5 (slika 10).

Prva relacija" X < at"zove se linearna. Općenito, ako je odnos uredan R(strogi i nestrogi) na setu X ima svojstvo: za bilo koje X, atÎ X ili xRy, ili yRx, tada se naziva linearna relacija reda, a skup X– linearno uređen skup.

Ako je set X naravno i sastoji se od n elemenata, zatim linearnog reda X svodi se na numerisanje njegovih elemenata brojevima 1,2,3, ..., n.

Linearno uređeni skupovi imaju niz svojstava:

1°. Neka a, b, c– elementi skupa X, poredano po relaciji R. Ako se to zna aRv I u Rs, onda kažu da je element V leži između elemenata A I With.

2°. Gomila X, linearno poredano relacijom R, naziva se diskretnim ako između bilo koja dva njegova elementa leži samo konačan skup elemenata ovog skupa.

3°. Linearno uređen skup naziva se gust ako za bilo koja dva različita elementa ovog skupa postoji element skupa koji leži između njih.

Relacija ekvivalencije. Veza između relacije ekvivalencije i podjele skupa na klase

Definicija. Stav R na setu X se naziva relacija ekvivalencije ako je refleksivna, simetrična i tranzitivna.

Primjer. Razmotrite odnos " X drug iz razreda at„na mnogim studentima Pedagoškog fakulteta. Ima sljedeća svojstva:

1) refleksivnost, jer svaki učenik je sam sebi drug iz razreda;

2) simetrija, jer ako je student X at, zatim student at je učenik iz razreda X;

3) tranzitivnost, jer ako je student X- drugarica iz razreda at, i student at– drugarica iz razreda z, zatim student Xće biti učenikov drug iz razreda z.

Dakle, ova relacija ima svojstva refleksivnosti, simetrije i tranzitivnosti, te je stoga relacija ekvivalencije. Istovremeno, mnogi studenti Pedagoškog fakulteta mogu se podijeliti u podskupove koje se sastoje od studenata koji studiraju na istom predmetu. Dobijamo 5 podskupova.

Relacije ekvivalencije su i, na primjer, odnos paralelnosti pravih, odnos jednakosti figura. Svaki takav odnos povezan je sa dijeljenjem skupa na klase.

Teorema. Ako je na setu X ako je data relacija ekvivalencije, onda ovaj skup dijeli na parno disjunktne podskupove (klase ekvivalencije).

Obrnuti iskaz je također istinit: ako je bilo koja relacija definirana na skupu X, generiše particiju ovog skupa na klase, onda je to relacija ekvivalencije.

Primjer. Na snimanju X= (1; 2; 3; 4; 5; 6; 7; 8) specificira se relacija „imati isti ostatak kada se podijeli sa 3“. Da li je to relacija ekvivalencije?

Napravimo graf ovog odnosa: (nezavisno)

Ova relacija ima svojstva refleksivnosti, simetrije i tranzitivnosti, stoga je relacija ekvivalencije i dijeli skup X na klase ekvivalencije. U svakoj klasi ekvivalencije biće brojevi koji, kada se podijele sa 3, daju isti ostatak: X 1 = {3; 6}, X 2 = {1; 4; 7}, X 3 = {2; 5; 8}.

Smatra se da klasu ekvivalencije određuje bilo koji njen predstavnik, tj. proizvoljan element ove klase. Dakle, klasa jednakih razlomaka može biti specificirana specificiranjem bilo kojeg razlomka koji pripada ovoj klasi.

U početnom kursu matematike susreću se i odnosi ekvivalencije, na primjer, „izrazi X I at imaju iste numeričke vrijednosti", "slika X jednaka figuri at».

Definicija. Stav R na setu X naziva se relacija reda ako je tranzitivna i asimetrična ili antisimetrična.

Definicija. Stav R na setu X naziva se relacija strogog reda ako je tranzitivna i asimetrična.

Primjeri odnosi strogog reda: "više" na skupu prirodnih brojeva, "više" na skupu ljudi, itd.

Definicija. Stav R na setu X naziva se relacija nestriktnog reda ako je tranzitivna i antisimetrična.

Primjeri relacije nestrogog reda: “nema više” na skupu realnih brojeva, “budi djelitelj” na skupu prirodnih brojeva, itd.

Definicija. Gomila X naziva se uređenim ako je na njemu specificiran odnos reda.

Primjer. Na snimanju X= (1; 2; 3; 4; 5) date su dvije relacije: “ X £ at" i " X- razdjelnik at».

Oba ova odnosa imaju svojstva refleksivnosti, antisimetrije i tranzitivnosti (konstruirajte grafove i sami provjerite svojstva), tj. su odnosi nestrogog reda. Ali prva relacija ima svojstvo povezanosti, dok druga nema.

Definicija. Odnos reda R na setu X naziva se linearna relacija reda ako ima svojstvo povezanosti.

U osnovnoj školi se izučavaju mnogi odnosi reda. Već u prvom razredu postoje relacije “manje”, “više” na skupu prirodnih brojeva, “kraće”, “duže” na skupu segmenata itd.

Kontrolna pitanja

1. Definirajte binarnu relaciju na skupu X.

2. Kako napisati izjavu da elementi X I at su u vezi R?

3. Navedite načine za definiranje odnosa.

4. Formulirajte svojstva koja veze mogu imati. Kako se ova svojstva odražavaju na grafikonu?

5. Koja svojstva mora imati relacija da bi bila relacija ekvivalencije?

6. Kako je relacija ekvivalencije povezana sa podjelom skupa na klase?

7. Koja svojstva mora imati odnos da bi bio odnos reda?

X (\displaystyle X) pozvao odnos nestrogog parcijalnog poretka (odnos poretka, refleksivni odnos), ako postoje

Gomila X (\displaystyle X), na kojoj je uvedena relacija parcijalnog reda, se zove djelimično naručeno. Nestrogi odnos parcijalnog poretka se često označava sa ≼ (\displaystyle \preccurlyeq ).

Opcije

Parcijalni odnos poretka R (\displaystyle R) pozvao linearni poredak, ako je uslov ispunjen

∀ x ∀ y (x R y ∨ y R x) (\displaystyle \forall x\forall y(xRy\lor yRx)).

Gomila X (\displaystyle X), na kojem je uvedena relacija linearnog reda, se zove linearno uređeno, ili lanac.

Stav R (\displaystyle R), koji zadovoljava samo uslove refleksivnosti i tranzitivnosti naziva se prednarudžba ili kvazi narudžba.

Strogi red

Ako se uvjet refleksivnosti zamijeni uvjetom antirefleksivnosti:

∀ x ¬ (x R x) (\displaystyle \forall x\neg (xRx)),

onda dobijamo definiciju strog, ili antirefleksivni parcijalni poredak(obično označeno simbolom ≺ (\displaystyle \prec )).

Komentar. Istovremena antirefleksivnost i tranzitivnost odnosa povlači antisimetriju. Stoga je odnos odnos strogog reda ako i samo ako je antirefleksivan i tranzitivan.

Općenito, ako R (\displaystyle R) je onda tranzitivna, antisimetrična relacija

R ≼ = R ∪ ( (x , x) | x ∈ X ) (\displaystyle R_(\preccurlyeq)=R\cup \((x,x)|x\in X\))- refleksivni poredak R ≺ = R ∖ ( (x , x) | x ∈ X ) (\displaystyle R_(\prec )=R\setminus \((x,x)|x\in X\))- strogi red.

Primjeri

• Na skupu realnih brojeva, relacije “više od” i “manje od” su relacije strogog reda, a “više od ili jednako” i “manje od ili jednako” nisu stroge.
• Relacija djeljivosti na skupu cijelih brojeva je relacija nestrogog reda.

Dushnik-Miller dimenzija

Priča

Znakovi < {\displaystyle <} I > (\displaystyle >) izumio

Neka je R binarna relacija na skupu A.

DEFINICIJA. Binarna relacija R na skupu A naziva se relacija reda na A ili red na A ako je tranzitivna i antisimetrična.

DEFINICIJA. Relacija reda R na skupu A naziva se nestrogom ako je refleksivna na A, odnosno za svaki od A.

Relacija reda R naziva se stroga (na A) ako je antirefleksivna na A, odnosno za bilo koji od A. Međutim, iz antirefleksivnosti tranzitivne relacije R slijedi da je antisimetrična. Stoga se može dati sljedeća ekvivalentna definicija.

DEFINICIJA. Binarna relacija R na skupu A naziva se strogim redom na A ako je tranzitivna i antirefleksivna na A.

Primjeri. 1. Neka je skup svih podskupova skupa M. Relacija uključivanja na skup je relacija nestrogog reda.

2. Relacije na skupu realnih brojeva su, respektivno, relacije strogog i nestrogog reda.

3. Relacija djeljivosti u skupu prirodnih brojeva je relacija nestrogog reda.

DEFINICIJA. Binarna relacija R na skupu A naziva se relacija predreda ili predred na A ako je refleksivna na i tranzitivna.

Primjeri. 1. Relacija djeljivosti u skupu cijelih brojeva nije red. Međutim, on je refleksivan i tranzitivan, što znači da je prednarudžbina.

2. Relacija logičke implikacije je predured na skupu propozicionih logičkih formula.

Linearni poredak. Važan poseban slučaj reda je linearni poredak.

DEFINICIJA. Relacija poretka na skupu naziva se linearna relacija poretka ili linearna poredak ako je povezana na , tj. za bilo koje x, y iz A

Relacija poretka koja nije linearna obično se naziva relacija parcijalnog poretka ili parcijalna relacija.

Primjeri. 1. Relacija “manje od” na skupu realnih brojeva je relacija linearnog reda.

2. Odnos reda usvojen u rječnicima ruskog jezika naziva se leksikografski. Leksikografski poredak na skupu riječi u ruskom jeziku je linearan.

Riječ "naredba" se često koristi u raznim pitanjima. Oficir daje komandu: „Izračunaj brojčanim redom“, aritmetičke radnje se izvode određenim redom, sportisti se rangiraju po visini, svi vodeći šahisti su raspoređeni u određenom redosledu prema tzv. Elo koeficijentima (američki profesor koji je razvio sistemske koeficijente, omogućavajući vam da uzmete u obzir sve uspjehe i neuspjehe igrača), nakon prvenstva svi fudbalski timovi se nalaze određenim redoslijedom, itd. Postoji redoslijed operacija prilikom proizvodnje dijela, redosled reči u rečenici (pokušajte da shvatite šta znači rečenica „na starca“ nisam posadio magarca!)

Ređajući elemente određenog skupa jedan za drugim, na taj način ih poredamo ili uspostavljamo neki odnos među njima u redu. Najjednostavniji primjer je prirodni poredak prirodnih brojeva. Njegova prirodnost leži u činjenici da za bilo koja dva prirodna broja znamo koji slijedi iza drugog ili koji je veći od drugog, pa možemo poredati prirodne brojeve u nizu tako da se veći broj nalazi, npr. desno od manjeg: 1, 2, 3, ... . Naravno, redoslijed elemenata se može pisati u bilo kojem smjeru, ne samo s lijeva na desno. Sam koncept prirodnih brojeva već sadrži ideju reda. Uspostavljanjem nekog relativnog rasporeda elemenata bilo kojeg skupa, na njemu definišemo neki binarni odnos poretka, koji u svakom konkretnom slučaju može imati svoje ime, na primjer, "biti manji", "biti stariji", "da biti sadržan u ", "prati" itd. Simboličke oznake reda također mogu varirati, na primjer, Í, itd.

Glavna karakteristika relacije poretka je da ima svojstvo tranzitivnosti. Dakle, ako imamo posla sa nizom nekih objekata x 1, x 2, ..., x n,..., poredano, na primjer, po relaciji, zatim prema onome što se izvodi x 1x 2... x n..., to bi trebalo slijediti za bilo koji par x i, x j elementi ovog niza su takođe ispunjeni x ix j:

Za par elemenata x ij u grafu odnosa crtamo strelicu iz vrha x i na vrhu x j, odnosno od manjeg elementa do većeg.

Graf odnosa poretka može se pojednostaviti korištenjem metode tzv Hasse dijagrami. Hasseov dijagram je konstruiran na sljedeći način. Manji elementi se postavljaju niže, a veći više. Budući da samo takvo pravilo nije dovoljno za prikaz, crtaju se linije koje pokazuju koji je od dva elementa veći, a koji manji od drugog. U ovom slučaju, dovoljno je nacrtati samo linije za elemente koji slijede jedan za drugim. Primjeri Hasse dijagrama prikazani su na slici:

Ne morate uključiti strelice u Hasseov dijagram. Hasseov dijagram se može rotirati u ravni, ali ne proizvoljno. Prilikom okretanja potrebno je održavati relativni položaj (iznad - ispod) vrhova dijagrama:

Stav R u izobilju X pozvao stav strogog reda, ako je tranzitivan i asimetričan.

Poziva se skup u kojem je definirana relacija striktnog reda naredio. Na primjer, skup prirodnih brojeva uređen je relacijom “manje od”. Ali ovaj isti skup je takođe poređan drugom relacijom – „podeljeno na“ i „više“.

Graf relacije “manje od” u skupu prirodnih brojeva može se prikazati kao zraka:

Stav R V X zove odnos nestrogi (parcijalni) poredak, ako je tranzitivan i antisimetričan. Svaki odnos nestriktnog poretka je refleksivan.

Epitet "djelomičan" izražava činjenicu da možda nisu svi elementi skupa uporedivi u datom pogledu.

Tipični primjeri odnosa parcijalnog poretka su odnosi „ne veći od“, „ne manji od“ i „ne veći od“. Čestica “ne” u nazivima odnosa služi za izražavanje njihove refleksivnosti. Relacija “ne više od” poklapa se sa relacijom “manje ili jednako”, a relacija “ne manje” je isto što i “veće od ili jednako”. U tom smislu se naziva i parcijalni poredak nije stroga u redu. Često se parcijalni (nestrogi) odnos poretka označava simbolom "".

Relacija uključivanja Í između podskupova određenog skupa je također parcijalni poredak. Očigledno, nisu svaka dva podskupa uporediva u ovom pogledu. Na slici ispod je prikazan redoslijed djelomičnog uključivanja na skup svih podskupova skupa (1,2,3). Strelice na grafikonu koje bi trebale biti usmjerene prema gore nisu prikazane.

Pozivaju se skupovi na kojima je zadan parcijalni red djelimično naručeno, ili jednostavno naredio setovi.

Elementi X I at djelimično uređeni skup se poziva uporedite sa nama Ako Xat ili atX. Inače nisu uporedivi.

Poziva se uređeni skup u kojem su bilo koja dva elementa uporediva linearno uređeno, a redoslijed je linearni. Linearni poredak se takođe naziva savršenim redom.

Na primjer, skup svih realnih brojeva prirodnog reda, kao i svi njegovi podskupovi, su linearno uređeni.

Mogu se naručiti objekti najrazličitije prirode hijerarhijski. Evo nekoliko primjera.

Primer 1: Delovi knjige su raspoređeni tako da knjiga sadrži poglavlja, poglavlja sadrže odeljke, a odeljci sadrže pododeljke.

Primjer 2. Fascikle u kompjuterskom sistemu datoteka su ugniježđene jedna unutar druge, formirajući granastu strukturu.

Primjer 3. Odnos roditelja i djece može se prikazati kao tzv porodično stablo, koji pokazuje ko je čiji predak (ili potomak).

Pustite na set A dat je djelimični red. Element X pozvao maksimum (minimum) element skupa A, ako iz činjenice da Xat(atX), slijedi jednakost X= u. Drugim riječima, element X je maksimum (minimum) ako za bilo koji element at ili to nije tačno Xat(atX), ili se izvršava X=u. Dakle, maksimalni (minimalni) element je veći (manji) od svih elemenata koji se razlikuju od njega sa kojima je u vezi.

Element X pozvao najveći (najmanji), ako za bilo koga atÎ A izvedeno at< х (х< у).

Djelomično uređen skup može imati nekoliko minimalnih i/ili maksimalnih elemenata, ali ne može biti više od jednog minimalnog i maksimalnog elementa. Najmanji (najveći) element je ujedno i minimum (maksimum), ali obrnuto nije tačno. Slika lijevo prikazuje djelomični poredak sa dva minimalna i dva maksimalna elementa, a desno djelomični poredak s najmanjim i najvećim elementom:

U konačnom djelimično uređenom skupu uvijek postoje minimalni i maksimalni elementi.

Uređeni skup koji ima najveće i najmanje elemente naziva se ograničeno. Na slici je prikazan primjer beskonačnog ograničenog skupa. Naravno, nemoguće je prikazati beskonačan skup na konačnoj stranici, ali možete pokazati princip njegove konstrukcije. Ovdje petlje u blizini vrhova nisu prikazane kako bi se pojednostavilo crtanje. Iz istog razloga, lukovi koji daju prikaz svojstva tranzitivnosti nisu prikazani. Drugim riječima, slika prikazuje Hasseov dijagram odnosa reda.

Beskonačni skupovi možda nemaju maksimalne ili minimalne elemente, ili oboje. Na primjer, skup prirodnih brojeva (1,2, 3, ...) ima najmanji element od 1, ali nema maksimum. Skup svih realnih brojeva prirodnog reda nema ni najmanji ni najveći element. Međutim, njegov podskup koji se sastoji od svih brojeva X< 5, ima najveći element (broj 5), ali nema najmanji.