Urejeni odnosi. Razmerje reda

Beseda "vrstni red" se pogosto uporablja v različnih vprašanjih. Častnik izda ukaz: »Izračunaj po vrstnem redu številk«, aritmetične operacije se izvajajo v določenem vrstnem redu, tekmovalci so razvrščeni po višini, obstaja vrstni red za izvajanje operacij pri izdelavi dela, obstaja vrstni red besed v stavku.

Kaj je skupno v vseh primerih, ko govorimo o redu? Dejstvo je, da ima beseda »vrstni red« naslednji pomen: pomeni, kateri element danega niza sledi kateremu (ali kateri element je pred katerim).

odnos " X sledi pri" prehodno: če " X sledi pri"in" pri sledi z", to" x sledi z" Poleg tega mora biti ta odnos antisimetričen: za dva različna X in pri, Če X sledi pri, To pri ne sledi X.

Opredelitev. Odnos R na setu X klical razmerje strogega reda, če je tranzitiven in antisimetričen.

Ugotovimo značilnosti grafa in grafa odnosov strogega reda.

Poglejmo si primer. Na snemanju X= (5, 7, 10, 15, 12) dano razmerje R: « X < pri" Definirajmo to relacijo z naštevanjem parov
R = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.

Zgradimo njegov graf. Vidimo, da graf te relacije nima zank. Na grafu ni dvojnih puščic. Če iz X puščica gre na pri, in od pri- V z, nato od X puščica gre na z(slika 8).

Konstruiran graf omogoča razporeditev elementov množice X v tem vrstnem redu:

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

Na sliki 6 (§ 6 tega poglavja) sta stolpca VII, VIII grafa razmerij strogega reda.

Nestriktna relacija

Nasprotje relacije "manj kot" v nizu realnih števil je relacija "ne manj". Ne gre več za razmerje strogega reda. Bistvo je, kdaj X = pri, odnosi so izpolnjeni X ³ pri in pri ³ X, tj. "nič manj" odnos je refleksiven.

Opredelitev. Odnos R na setu X klical nestrogo razmerje, če je refleksivna, antisimetrična in tranzitivna.

Takšna razmerja so zveze razmerja strogega reda z razmerjem identitete.

Razmislite o razmerju "nič več" (£) za množico

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

Graf nestroge relacije reda ima za razliko od grafa relacije strogega reda zanke na vsakem vozlišču.

Na sl. 6 (§ 6 tega poglavja) stolpci V, VI so grafi relacij nestriktnega reda.

Naročeni kompleti

Neka množica se lahko izkaže za urejeno (pravijo tudi povsem urejeno) z neko relacijo reda, medtem ko je druga množica lahko neurejena ali delno urejena s takšno relacijo.

Opredelitev. Mnogi X klical naročeno neko razmerje reda R, če za katera koli dva elementa x, y od X:

(X, pri) Î R ali ( y, x) Î R.

če R je relacija strogega reda, potem množica X urejeno s to relacijo pod pogojem: če X, pri poljubna dva neenaka elementa množice X, to ( X, pri) Î R ali ( y, x) Î R, ali katera koli dva elementa x, y kompleti X so enaki.

Iz šolskega tečaja matematike je znano, da številski nizi n , Z , Q , R urejeno z relacijo "manj kot" (<).

Množica podmnožic neke množice ni urejena z uvedbo inkluzijske relacije (I) ali stroge inkluzije (S) v zgornjem smislu, ker obstajajo podmnožice, od katerih nobena ni vključena v drugo. V tem primeru pravimo, da je dana množica delno urejena z relacijo Í (ali Ì).

Razmislite o kompletu X= (1, 2, 3, 4, 5, 6) in vsebuje dve relaciji "manj kot" in "deljeno s". Enostavno je preveriti, da sta ti razmerji razmerja reda. Relacijski graf »manj kot« lahko prikažemo kot žarek.

Graf relacije "deljeno z" je mogoče prikazati le na ravnini.

Poleg tega ima graf druge relacije vozlišča, ki niso povezana s puščico. Na primer, ni puščice, ki bi povezovala številki 4 in 5 (slika 10).

Prvo razmerje" X < pri"se imenuje linearna. Na splošno, če je razmerje urejeno R(strogi in nestrogi) na snemanju X ima lastnost: za katerokoli X, priÎ X oz xRy, oz yRx, potem se imenuje linearna relacija reda in niz X– linearno urejena množica.

Če nastavite X seveda, in je sestavljen iz n elementov, nato linearno urejanje X se zmanjša na oštevilčenje njegovih elementov s številkami 1,2,3, ..., n.

Linearno urejene množice imajo številne lastnosti:

1°. Naj a, b, c– elementi kompleta X, urejeno z relacijo R. Če se ve, da aRв in v Rc, potem pravijo, da element V leži med elementi A in z.

2°. Mnogi X, linearno urejen z relacijo R, se imenuje diskretna, če med katerima koli dvema njenima elementoma leži le končna množica elementov te množice.

3°. Linearno urejena množica se imenuje gosta, če za katera koli dva različna elementa te množice obstaja element množice, ki leži med njima.

Ekvivalenčna relacija. Povezava med ekvivalenčno relacijo in razdelitvijo množice na razrede

Opredelitev. Odnos R na setu X imenujemo ekvivalenčna relacija, če je refleksivna, simetrična in tranzitivna.

Primer. Razmislite o razmerju " X sošolka pri"na številne študente Pedagoške fakultete. Ima naslednje lastnosti:

1) refleksivnost, ker vsak dijak je sam svoj sošolec;

2) simetrija, ker če študent X pri, nato študent pri je sošolka dijaka X;

3) prehodnost, ker če študent X- sošolec pri, in študent pri– sošolec z, nato študent X bo študentov sošolec z.

Tako ima ta relacija lastnosti refleksivnosti, simetrije in tranzitivnosti, zato je ekvivalenčna relacija. Hkrati lahko številne študente Pedagoške fakultete razdelimo v podskupine, ki jih sestavljajo študenti istega predmeta. Dobimo 5 podmnožic.

Ekvivalenčne relacije so tudi na primer relacije vzporednosti premic, relacije enakosti likov. Vsako takšno razmerje je povezano z razdelitvijo nabora na razrede.

Izrek.Če na snemanju X glede na ekvivalenčno relacijo, nato to množico razdeli na po parih nepovezane podmnožice (ekvivalenčni razredi).

Velja tudi obratna izjava: če je katera koli relacija definirana na množici X generira particijo te množice v razrede, potem je to ekvivalenčna relacija.

Primer. Na snemanju X= (1; 2; 3; 4; 5; 6; 7; 8) določena je relacija "imajo enak ostanek pri deljenju s 3". Je to ekvivalenčna relacija?

Zgradimo graf tega odnosa: (neodvisno)

Ta relacija ima lastnosti refleksivnosti, simetrije in tranzitivnosti, zato je ekvivalenčna relacija in razcepi množico X do enakovrednih razredov. V vsakem ekvivalenčnem razredu bodo številke, ki pri deljenju s 3 dajo enak ostanek: X 1 = {3; 6}, X 2 = {1; 4; 7}, X 3 = {2; 5; 8}.

Menijo, da razred enakovrednosti določa kateri koli od njegovih predstavnikov, tj. poljuben element tega razreda. Tako je mogoče določiti razred enakih ulomkov z določitvijo katerega koli ulomka, ki pripada temu razredu.

V začetnem tečaju matematike se srečujemo tudi z ekvivalenčnimi razmerji, na primer »izrazi X in pri imajo enake številske vrednosti", "slika X enako sliki pri».

Opredelitev. Odnos R na setu X se imenuje relacija reda, če je tranzitivna in asimetrična ali antisimetrična.

Opredelitev. Odnos R na setu X se imenuje stroga relacija reda, če je tranzitivna in asimetrična.

Primeri relacije strogega reda: »več« na množici naravnih števil, »višje« na množici ljudi itd.

Opredelitev. Odnos R na setu X se imenuje nestriktna relacija reda, če je tranzitivna in antisimetrična.

Primeri relacije nestriktnega reda: »ne več« na množici realnih števil, »biti delitelj« na množici naravnih števil itd.

Opredelitev. Mnogi X se imenuje urejeno, če je na njem podana relacija reda.

Primer. Na snemanju X= (1; 2; 3; 4; 5) sta podani dve relaciji: “ X £ pri"in" X- delilnik pri».

Obe relaciji imata lastnosti refleksivnosti, antisimetričnosti in tranzitivnosti (sestavite grafe in lastnosti preverite sami), tj. so razmerja nestriktnega reda. Toda prva relacija ima lastnost povezanosti, druga pa ne.

Opredelitev. Razmerje reda R na setu X se imenuje linearna relacija reda, če ima lastnost povezanosti.

V osnovni šoli se preučuje veliko vrstnih odnosov. Že v prvem razredu so relacije “manj”, “več” na množici naravnih števil, “krajše”, “daljše” na množici odsekov itd.

Varnostna vprašanja

1. Definirajte binarno relacijo na množici X.

2. Kako napisati izjavo, da elementi X in pri sta v razmerju R?

3. Naštejte načine za definiranje odnosov.

4. Formulirajte lastnosti, ki jih imajo lahko razmerja. Kako se te lastnosti odražajo v grafu?

5. Katere lastnosti mora imeti relacija, da je ekvivalenčna relacija?

6. Kako je ekvivalenčna relacija povezana z razdelitvijo množice na razrede?

7. Katere lastnosti mora imeti relacija, da je relacija reda?

X (\displaystyle X) klical razmerje nestriktnega delnega reda (razmerje reda, refleksivno razmerje), če obstajajo

Mnogi X (\displaystyle X), na katerem je uvedena relacija delnega reda, se imenuje delno urejeno. Relacija nestriktnega delnega reda je pogosto označena z ≼ (\displaystyle \preccurlyeq ).

Možnosti

Relacija delnega reda R (\displaystyle R) klical linearni red, če je pogoj izpolnjen

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

Mnogi X (\displaystyle X), na katerem je uvedena linearna relacija reda, se imenuje linearno urejeno, oz veriga.

Odnos R (\displaystyle R), ki izpolnjuje samo pogoje refleksivnosti in tranzitivnosti, se imenuje prednaročilo ali kvazinaročilo.

Strog red

Če pogoj refleksivnosti nadomestimo s pogojem antirefleksivnosti:

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

potem dobimo definicijo stroga, oz antirefleksni delni red(običajno označeno s simbolom ≺ (\displaystyle \prec )).

Komentiraj. Hkratna antirefleksivnost in tranzitivnost relacije potegne za seboj antisimetričnost. Zato je odnos razmerje strogega redače in samo če je antirefleksivna in tranzitivna.

Na splošno, če R (\displaystyle R) je torej tranzitivna, antisimetrična relacija

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

Primeri

• Na množici realnih števil so relacije "več kot" in "manj kot" relacije strogega reda, "več kot ali enako" in "manj kot ali enako" pa nestrogi.
• Relacija deljivosti na množici celih števil je relacija nestriktnega reda.

Dushnik-Millerjeva dimenzija

Zgodba

Znaki < {\displaystyle <} in > (\displaystyle >) izumil

Naj bo R binarna relacija na množici A.

OPREDELITEV. Binarno relacijo R na množici A imenujemo relacija reda na A ali relacija reda na A, če je tranzitivna in antisimetrična.

OPREDELITEV. Relacija reda R na množici A se imenuje nestroga, če je refleksivna na A, to je za vsakega od A.

Relacija reda R se imenuje stroga (na A), če je antirefleksivna na A, to je za katerega koli od A. Vendar pa iz antirefleksivnosti tranzitivne relacije R sledi, da je antisimetrična. Zato je mogoče podati naslednjo enakovredno definicijo.

OPREDELITEV. Binarno relacijo R na množici A imenujemo strogi red na A, če je na A tranzitivna in antirefleksivna.

Primeri. 1. Naj bo množica vseh podmnožic množice M. Inkluzijska relacija na množici je relacija nestriktnega reda.

2. Relacije na množici realnih števil so relacije strogega in nestriktnega reda.

3. Relacija deljivosti v množici naravnih števil je relacija nestriktnega reda.

OPREDELITEV. Binarno relacijo R na množici A imenujemo predvrstna relacija ali predvrstnost na A, če je refleksivna na in tranzitivna.

Primeri. 1. Relacija deljivosti v množici celih števil ni vrstni red. Je pa refleksiven in prehoden, kar pomeni, da je prednaročilo.

2. Relacija logične implikacije je prednaročilo na množici propozicionalnih logičnih formul.

Linearni red. Pomemben poseben primer reda je linearni red.

OPREDELITEV. Relacija reda na množici se imenuje linearna relacija reda ali linearna relacija na , če je povezana na , tj. za vsak x, y iz A

Relacija reda, ki ni linearna, se običajno imenuje relacija delnega reda ali delni red.

Primeri. 1. Relacija »manj kot« na množici realnih števil je relacija linearnega reda.

2. Vrstni red, sprejet v slovarjih ruskega jezika, se imenuje leksikografski. Leksikografski vrstni red na množici besed v ruskem jeziku je linearni vrstni red.

Beseda "vrstni red" se pogosto uporablja v najrazličnejših vprašanjih. Častnik izda ukaz: »Izračunaj po številčnem vrstnem redu«, računske operacije se izvajajo v določenem vrstnem redu, tekmovalci so razvrščeni po višini, vsi vodilni šahisti so razvrščeni v določen vrstni red po tako imenovanih koeficientih Elo (ameriški profesor, ki razvili sistemske koeficiente, ki vam omogočajo, da upoštevate vse uspehe in neuspehe igralcev), po prvenstvu so vse nogometne ekipe nameščene v določenem vrstnem redu itd. Obstaja vrstni red operacij pri izdelavi dela, vrstni red besed v stavku (poskusite razumeti, kaj pomeni stavek »na starega« nisem osla podsadil!«

S tem, ko elemente določene množice razporedimo enega za drugim, jih s tem uredimo ali med njimi vzpostavimo neko razmerje v redu. Najenostavnejši primer je naravni vrstni red naravnih števil. Njegova naravnost je v tem, da za poljubni dve naravni števili vemo, katero sledi drugemu ali katero je večje od drugega, zato lahko naravna števila razvrstimo v zaporedje tako, da se večje število nahaja npr. desno od manjšega: 1, 2, 3, ... . Seveda lahko zaporedje elementov pišemo v kateri koli smeri, ne samo od leve proti desni. Sam koncept naravnih števil že vsebuje idejo reda. Z vzpostavitvijo neke relativne razporeditve elementov katere koli množice s tem definiramo na njej neko binarno relacijo reda, ki ima lahko v vsakem konkretnem primeru svoje ime, na primer »biti manj«, »biti starejši«, »biti biti vsebovan v ", "slediti" itd. Simbolne oznake reda so lahko tudi različne, na primer Í itd.

Glavna značilnost razmerja reda je, da ima lastnost tranzitivnosti. Torej, če imamo opravka z zaporedjem nekaterih predmetov x 1, x 2, ..., x n,..., urejeno npr. po relaciji, nato pa po izvajanem x 1x 2... x n..., bi moralo slediti temu za vsak par x i, x j elementi tega zaporedja so tudi izpolnjeni x ix j:

Za par elementov x ij v relacijskem grafu narišemo puščico iz vrha x i do vrha x j, torej od manjšega elementa k večjemu.

Graf razmerja reda lahko poenostavimo s tako imenovano metodo Hassejevi diagrami. Hassejev diagram je sestavljen na naslednji način. Manjše elemente postavimo nižje, večje pa višje. Ker samo takšno pravilo ni dovolj za upodobitev, so narisane črte, ki kažejo, kateri od obeh elementov je večji in kateri manjši od drugega. V tem primeru je dovolj, da narišete samo črte za elemente, ki sledijo drug drugemu. Primeri Hassejevih diagramov so prikazani na sliki:

V Hassejev diagram vam ni treba vključiti puščic. Hassejev diagram lahko vrtimo v ravnini, vendar ne poljubno. Pri obračanju je potrebno ohraniti relativni položaj (zgoraj - spodaj) oglišč diagrama:

Odnos R v izobilju X klical odnos strogega reda,če je prehodna in nesimetrična.

Množica, v kateri je definirana stroga relacija reda, se imenuje naročeno. Na primer, množica naravnih števil je urejena z razmerjem "manj kot". Toda ta isti niz je urejen tudi z drugo relacijo - "razdeljeno na" in "več".

Graf relacije "manj kot" v množici naravnih števil lahko prikažemo kot žarek:

Odnos R V X imenovano razmerje nestrogi (delni) red, če je tranzitiven in antisimetričen. Vsaka relacija nestriktnega reda je refleksivna.

Epitet "delno" izraža dejstvo, da morda niso vsi elementi niza primerljivi v določenem pogledu.

Tipični primeri relacij delnega reda so relacije "ne večje od", "ne manj kot" in "ne večje od". Delček »ne« v imenih razmerij služi za izražanje njihove refleksivnosti. Relacija »ne več kot« sovpada z relacijo »manj kot ali enako«, relacija »ne manj kot« pa je enaka kot »večje kot ali enako«. V zvezi s tem se imenuje tudi delni red ni stroga v redu. Pogosto je delna (nestroga) relacija reda označena s simbolom "".

Delni red je tudi vključitvena relacija Í med podmnožicami določene množice. Očitno nista vsaki dve podmnožici primerljivi v tem pogledu. Spodnja slika prikazuje delni vrstni red vključitve na množici vseh podmnožic množice (1,2,3). Puščice na grafu, ki bi morale biti usmerjene navzgor, niso prikazane.

Množice, na katerih je podan delni vrstni red, se imenujejo delno naročeno, ali samo naročeno kompleti.

Elementi X in pri imenujemo delno urejena množica primerjaj z namiče Xpri oz priX. Sicer pa niso primerljivi.

Imenuje se urejena množica, v kateri sta katera koli dva elementa primerljiva linearno urejeno in vrstni red je linearen. Linearni red se imenuje tudi popolni red.

Na primer, množica vseh realnih števil z naravnim redom, kot tudi vse njene podmnožice, so linearno urejene.

Naročiti je mogoče predmete najrazličnejše narave hierarhično. Tukaj je nekaj primerov.

Primer 1: Deli knjige so razporejeni tako, da knjiga vsebuje poglavja, poglavja razdelke in razdelki pododdelke.

Primer 2. Mape v računalniškem datotečnem sistemu so ugnezdene druga v drugo in tvorijo razvejano strukturo.

Primer 3. Odnos med starši in otroki lahko prikažemo kot t.i družinsko drevo, ki pokaže, kdo je čigav prednik (ali potomec).

Naj na snemanju A podan delni red. Element X klical največ (najmanj) element množice A, če iz dejstva, da Xpri(priX), sledi enakopravnost X= u. Z drugimi besedami, element X je največji (najmanjši), če je za katerikoli element pri ali to ni res Xpri(priX), ali se izvrši X=u. Tako je največji (minimalni) element večji (manjši) od vseh elementov, ki se razlikujejo od njega, s katerimi je v razmerju.

Element X klical največji (najmanjši),če za koga priÎ A teče pri< х (х< у).

Delno urejena množica ima lahko več minimalnih in/ali maksimalnih elementov, ne more pa biti več kot en minimalni in maksimalni element. Najmanjši (največji) element je tudi najmanjši (največji), vendar obratno ne drži. Slika na levi prikazuje delni vrstni red z dvema najmanjšima in dvema največjima elementoma, na desni pa delni vrstni red z najmanjšim in največjim elementom:

V končni delno urejeni množici sta vedno najmanjši in največji element.

Imenuje se urejena množica, ki ima največji in najmanjši element omejeno. Slika prikazuje primer neskončne omejene množice. Seveda je nemogoče upodobiti neskončno množico na končni strani, vendar lahko pokažete načelo njegove konstrukcije. Tukaj zanke v bližini oglišč niso prikazane zaradi poenostavitve risbe. Iz istega razloga niso prikazani loki, ki zagotavljajo prikaz lastnosti prehodnosti. Z drugimi besedami, slika prikazuje Hassejev diagram relacije reda.

Neskončni nizi ne smejo imeti največjih ali najmanjših elementov ali obojega. Na primer, množica naravnih števil (1,2, 3, ...) ima najmanjši element 1, največjega pa nima. Množica vseh realnih števil z naravnim redom nima niti najmanjšega niti največjega elementa. Vendar pa je njegova podmnožica sestavljena iz vseh števil X< 5, ima največji element (število 5), nima pa najmanjšega.