Range korra suhe. Range järjekorra seos Rangel lineaarsel järjestussuhtel on omadused

Sõna "tellimus" kasutatakse sageli kõige erinevamates küsimustes. Ohvitser annab käsu: “Arvutage arvude järjekorras”, sooritatakse aritmeetilised tehted kindlas järjekorras, sportlased tõusevad pikkuseks, kõik juhtivad maletajad järjestatakse nn Elo koefitsientide järgi kindlasse järjekorda (Ameerika professor kes töötas välja süsteemi koefitsiendid, mis võimaldab arvesse võtta kõiki mängijate õnnestumisi ja ebaõnnestumisi), pärast meistrivõistlusi on kõik jalgpallimeeskonnad paigutatud kindlasse järjekorda jne istutas eesli mitte "!).

Järjestades teatud hulga elemente üksteise järel, järjestame need seeläbi või loome nende vahele mingi seose. järjest. Lihtsaim näide on naturaalarvude loomulik järjekord. Selle loomulikkus seisneb selles, et mistahes kahe naturaalarvu puhul teame, kumb neist järgneb teisele või kumb neist on teisest suurem, nii et saame naturaalarvud järjestada nii, et suurem arv paikneks, sest näiteks väiksemast paremal: 1, 2, 3, ... . Loomulikult saab elementide jada kirjutada igas suunas ja mitte ainult vasakult paremale. Naturaalarvude mõiste sisaldab juba järjestuse ideed. Määrates mistahes hulga elementide suhtelise paigutuse, paneme sellega paika mingi kahendjärjestuse seose, millel võib igal konkreetsel juhul olla oma nimi, näiteks "ole vähem", "ole vanem", "sisaldub " , "jälgi" jne. Järjestamise sümbolid võivad olla ka mitmesugused, näiteks Í jne.

Järjekorrasuhte peamiseks eristavaks tunnuseks on see, et sellel on transitiivsuse omadus. Niisiis, kui meil on tegemist mõne objekti jadaga x 1, x 2, ..., x n,... , tellitud näiteks suhtes , siis sooritatavast x 1x 2... x n..., see peaks järgnema sellele iga paari puhul x i , x j teostatakse ka selle jada elemente x ixj:

Paari elemendi jaoks x ij seosgraafikus joonistame ülalt noole x i tippu xj, st väiksemast elemendist suuremaks.

Järjekordade seose graafikut saab lihtsustada kasutades nn Hasse diagrammid. Hasse diagramm on üles ehitatud järgmiselt. Väiksemad elemendid on paigutatud alla ja suured on ülal. Kuna pildi jaoks ühest sellisest reeglist ei piisa, joonistatakse jooned, mis näitavad, kumb kahest elemendist on teisest suurem ja milline väiksem. Sel juhul piisab, kui joonistada ainult jooned üksteisele elementide koheseks järgimiseks. Hasse diagrammide näited on näidatud joonisel:

Hasse diagrammil võib nooled ära jätta. Hasse diagrammi saab tasapinnal pöörata, kuid mitte suvaliselt. Pööramisel on vaja säilitada diagrammi tippude suhteline asukoht (üleval - all):

Suhtumine R hulgaliselt X helistas range korra suhe, kui see on transitiivne ja asümmeetriline.

Kutsutakse hulka, milles on määratletud range järjekorra seos korrastatud. Näiteks naturaalarvude hulk on järjestatud seosega "vähem kui". Kuid sama komplekti järjestab ka teine ​​​​seos - "jagatakse" ja "suurem".

Naturaalarvude hulga "vähem kui" seose graafikut saab esitada kiirena:

Suhtumine R sisse X nimetatakse suhteks mitterange (osaline) järjekord, kui see on transitiivne ja antisümmeetriline. Iga mitterange järjestusega seos on refleksiivne.

Epiteet "osaline" väljendab tõsiasja, et võib-olla ei ole kõik komplekti elemendid selles suhtes võrreldavad.

Osalise järjestuse seose tüüpilised näited on "pole enam", "ei vähem", "pole vanem". Osake "mitte" suhete nimedes väljendab nende refleksiivsust. Suhe "mitte rohkem" langeb kokku suhtega "vähem või võrdne" ja suhe "mitte vähem" on sama mis "suurem või võrdne". Sellega seoses nimetatakse ka osalist järjekorda lõtv korras. Sageli tähistatakse osalist (mitteranget) järjestuse seost sümboliga "".

Kaasamise seos U mõne hulga alamhulkade vahel on samuti osaline järjestus. Ilmselgelt ei ole selles suhtes kaks alamhulka võrreldavad. Alloleval joonisel on kujutatud osaline järjestus komplekti kõigi alamhulkade (1,2,3) hulka kaasamise teel. Graafikul olevaid nooli, mis peaksid näitama ülespoole, ei kuvata.

Kutsutakse komplekte, millele antakse osaline korraldus osaliselt tellitud, või lihtsalt korrastatud komplektid.

Elemendid X ja juures osaliselt tellitud komplekti kutsutakse võrdlema, kui Xjuures või juuresX. Muidu pole need võrreldavad.

Nimetatakse järjestatud hulk, milles kaks elementi on võrreldavad lineaarselt järjestatud, ja järjekord on lineaarne. Lineaarset järjestust nimetatakse ka täiuslikuks korraks.

Näiteks kõigi loomuliku järjestusega reaalarvude hulk ja kõik selle alamhulgad on järjestatud lineaarselt.

Tellida saab kõige erinevama iseloomuga esemeid hierarhiliselt. Siin on mõned näidised.

Näide 1: Raamatu osad on järjestatud nii, et raamat sisaldab peatükke, peatükid sisaldavad jaotisi ja jaotised koosnevad alajaotistest.

Näide 2. Arvuti failisüsteemi kaustad on üksteise sisse pesastatud, moodustades hargneva struktuuri.

Näide 3. Suhet vanemad - lapsed saab kujutada kujul nn sugupuu, mis näitab, kes on kelle esivanem (või järglane).

Lase võtteplatsile AGA andis osalise korralduse. Element X helistas maksimaalne (minimaalne) hulga A element, kui sellest, et Xjuures(juuresX), järgneb võrdsus X= y. Teisisõnu element X on mis tahes elemendi maksimum (minimaalne). juures või pole see tõsi Xjuures(juuresX) või tehakse X=y. Seega on maksimaalne (minimaalne) element suurem (vähem) kui kõik teised elemendid, millega see on seotud.

Element X helistas suurim (väikseim), kui mõne jaoks juuresÎ AGA sooritatud juures< х (х< у).

Osaliselt järjestatud komplektis võib olla mitu miinimum- ja/või maksimumelementi, kuid miinimum- ja maksimumelementi ei saa olla rohkem kui üks. Väikseim (suurim) element on ka minimaalne (maksimaalne), kuid vastupidine pole tõsi. Vasakpoolne joonis näitab osalist järjestust kahe minimaalse ja kahe maksimaalse elemendiga ning paremal - osalist järjestust väikseima ja suurima elemendiga:

Lõplikus osaliselt järjestatud komplektis on alati minimaalsed ja maksimaalsed elemendid.

Nimetatakse järjestatud komplekt, millel on suurimad ja väikseimad elemendid piiratud . Joonisel on näide lõpmatu piiriga hulga kohta. Muidugi on võimatu kujutada lõpmatut kogumit piiratud lehel, kuid on võimalik näidata selle ülesehituse põhimõtet. Siin ei näidata tippude lähedal olevaid silmuseid joonise lihtsustamiseks. Samal põhjusel ei kuvata kaare, mis pakuvad transitiivsuse omaduse kuvamist. Teisisõnu, joonisel on järjekorra seose Hasse diagramm.

Lõpmatul hulgal ei pruugi olla maksimumi, miinimumi või mõlemat. Näiteks naturaalarvude hulgas (1,2, 3, ...) on väikseim element 1, kuid mitte maksimum. Kõigi loomuliku järjestusega reaalarvude hulgal pole ei väikseimat ega suurimat elementi. Kuid selle alamhulk, mis koosneb kõigist numbritest X< 5 on suurim element (number 5), kuid mitte väikseim element.

Olgu R binaarne seos hulgal A.

MÄÄRATLUS. binaarne seos R-d hulgal A nimetatakse järjestusseosteks A-s või järjestuseks A-s, kui see on transitiivne ja antisümmeetriline.

MÄÄRATLUS. Järjestusseost R hulgal A nimetatakse mitterangeks, kui see on A suhtes refleksiivne, st mis tahes A puhul.

Järjestusseost R nimetatakse rangeks (A-l), kui see on antirefleksiivne A-le, st mis tahes A-le. Transitiivse suhte R antisümmeetria tuleneb aga sellest, et see on refleksivastane. Seetõttu saame anda järgmise samaväärse definitsiooni.

MÄÄRATLUS. Binaarset seost R hulgal A nimetatakse rangeks järjestuseks A-s, kui see on transitiivne ja antirefleksiivne A-s.

Näited. 1. Olgu hulga M kõigi alamhulkade hulk. Hulgi kaasamise seos on mitterange järjekorra seos.

2. Reaalarvude hulga seosed on vastavalt range ja mitterange järjekorra seos.

3. Jaguvusseos naturaalarvude hulgas on mitteranget järku seos.

MÄÄRATLUS. Binaarset relatsiooni R hulgal A nimetatakse eeljärjestuse relatsiooniks või A eeljärjestuseks, kui see on refleksiivne ja transitiivne.

Näited. 1. Täisarvude hulga jaguvuse suhe ei ole järjekord. See on aga refleksiivne ja transitiivne, mis tähendab, et tegemist on ettetellimisega.

2. Loogilise tagajärje seos on propositsiooniloogika valemite hulga eeltellimus.

Lineaarne järjekord. Tellimuse oluline erijuhtum on lineaarne tellimus.

MÄÄRATLUS. Järjestusseost hulgal nimetatakse lineaarseks järjekorraks või lineaarseks järjestuseks, kui see on ühendatud punktiga , st mis tahes x, y korral A-st

Järjestusseotust, mis ei ole lineaarne, nimetatakse tavaliselt osalise järjestuse suhteks või osajärjekorraks.

Näited. 1. Reaalarvude hulga seos "vähem kui" on lineaarse järjekorra seos.

2. Vene keele sõnaraamatutes aktsepteeritud järjestusseost nimetatakse leksikograafiliseks. Vene keele sõnade kogumi leksikograafiline järjekord on lineaarne.

Sõna "tellimus" kasutatakse sageli mitmesugustes küsimustes. Ohvitser annab käsu: “Arvutage arvude järjekorras”, aritmeetilised tehted sooritatakse kindlas järjekorras, sportlased tõusevad pikkuseks, on korraldus detaili valmistamisel tehte tegemiseks, lauses sõnade järjekord.

Mis on kõigil juhtudel ühine, kui tegemist on tellimisega? Asjaolu, et sõnal “järjekord” on selline tähendus: see tähendab, milline selle või teise hulga element millele järgneb (või milline element millele eelneb).

Suhtumine" X järgneb juures» transitiivselt: kui « X järgneb juures" ja " juures järgneb z", siis" x järgneb z". Lisaks peab see suhe olema antisümmeetriline: kahe erineva jaoks X ja juures, kui X järgneb juures, siis juures ei järgi X.

Definitsioon. Suhtumine R võtteplatsil X helistas range korra suhe, kui see on transitiivne ja antisümmeetriline.

Selgitame välja graafiku ja range järjekorra suhete graafiku tunnused.

Kaaluge näidet. Võtteplatsil X= (5, 7, 10, 15, 12) seos R: « X < juures". Me määratleme selle seose paaride loendamisega
R = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.

Koostame selle graafiku. Näeme, et selle seose graafikul pole silmuseid. Graafikul pole topeltnooli. Kui alates X nool läheb juures, ja alates juures- sisse z, siis alates X nool läheb z(joonis 8).

Ehitatud graafik võimaldab järjestada komplekti elemente X selles järjekorras:

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

Joonisel 6 (käesoleva peatüki § 6) on VII, VIII veerud range järjekorra suhete graafikud.

Mitterange tellimuse seos

Seos "vähem kui" reaalarvude hulgas on vastupidine seosele "mitte vähem". See pole enam range kord. Asi on selles, et X = juures, suhted X ³ juures ja juures ³ X, st. seos "mitte vähem" on refleksiivne.

Definitsioon. Suhtumine R võtteplatsil X helistas mitterange korra seos, kui see on refleksiivne, antisümmeetriline ja transitiivne.

Sellised suhted on range järjekorra ühendused identiteedisuhtega.

Mõelge hulga seosele "no more" (£).

X= (5, 7, 10, 15, 12). Koostame selle graafiku (joonis 9).

Erinevalt range järjekorra relatsioonigraafikust on mitterange järjekorra seoste graafikul igas tipus silmused.

Joonisel fig. 6 (käesoleva peatüki § 6) graafikud V, VI on mitteranget järjekorda suhete graafikud.

Tellitud komplektid

Hulk võib osutuda järjestatuks (öeldakse ka täiesti järjestatuks) mõne järjestussuhte tõttu, samas kui mõni muu võib sellise seose tõttu olla järjestamata või osaliselt järjestatud.

Definitsioon. Palju X helistas korrastatud mingi korra seos R kui kahe elemendi puhul x, y alates X:

(X, juures) Î R või ( y, x) Î R.

Kui a R on range järjestuse seos, siis komplekt X tellitud selle seosega tingimusel: kui X, juures hulga mis tahes kaks ebavõrdset elementi X, siis ( X, juures) Î R või ( y, x) Î R või mis tahes kaks elementi x, y komplektid X on võrdsed.

Kooli matemaatika kursusest on teada, et arvukomplektid N , Z , K , R järjestatud suhtega "vähem kui" (<).

Teatud hulga alamhulkade hulk ei ole järjestatud kaasamisrelatsiooni (U) ega ülaltoodud tähenduses range kaasamisseose (T) kasutuselevõtuga, sest on alamhulki, millest ükski ei kuulu teise hulka. Sel juhul öeldakse, et antud hulk on suhtega Í (või Ì) osaliselt järjestatud.

Kaaluge komplekti X= (1, 2, 3, 4, 5, 6) ja sellel on kaks seost "vähem kui" ja "jagutav". Lihtne on kontrollida, kas need mõlemad seosed on järjekordsed suhted. Vähem kui seose graafikut saab esitada kiirena.

Seose "jagatakse" graafikut saab esitada ainult tasapinnal.

Lisaks on teise seose graafikul tipud, mis pole noolega ühendatud. Näiteks ei ole numbreid 4 ja 5 ühendavat noolt (joonis 10).

Esimene suhe X < juures' nimetatakse lineaarseks. Üldiselt, kui tellimuse seos R(ranged ja mitteranged) võtteplatsil X omab vara: mis tahes X, juuresÎ X või xRy, või yRx, siis nimetatakse seda lineaarse järjestuse seoseks ja hulgaks X on lineaarselt järjestatud hulk.

Kui komplekt X loomulikult ja koosneb n elemendid, seejärel lineaarne järjestus X taandab oma elementide loetlemiseks numbritega 1,2,3, ..., n.

Lineaarselt järjestatud komplektidel on mitmeid omadusi:

1°. Lase a, b, c- seadke elemendid X, tellitud suhte järgi R. Kui on teada, et aRv ja vRc, siis ütleme, et element sisse asub elementide vahel a ja Koos.

2°. Palju X, lineaarselt järjestatud suhte järgi R, nimetatakse diskreetseks, kui selle mis tahes kahe elemendi vahel asub ainult selle hulga elementide lõplik hulk.

3°. Lineaarselt järjestatud hulka nimetatakse tihedaks, kui selle hulga mis tahes kahe erineva elemendi vahel on hulga element, mis asub nende vahel.

Binaarsete suhete oluline tüüp on järjestussuhted. Range järjekorra suhe - binaarne seos, mis on refleksivastane, antisümmeetriline ja transitiivne:

määramine - (a eelnenud b). Näited on

seosed "suurem kui", "vähem kui", "vanem" jne. Numbrite puhul on tavaline tähistus märgid "<", ">".

Mitterange järjekorra seos - binaarne refleksiivne, antisümmeetriline ja transitiivne seos. Koos arvude mitterangete ebavõrdsuste loomulike näidetega on näiteks tasapinna või ruumi punktide vaheline seos "olema algpunktile lähemal". Täis- ja reaalarvude mitteranget ebavõrdsust võib pidada ka võrdsuse ja range järjekorra suhete disjunktsiooniks.

Kui sporditurniiril ei ole ette nähtud kohtade jagamist (st iga osaleja saab kindla, ainult söögikoha / auhinnatud koha), siis on see näide rangest järjekorrast; muidu mitte ranged.

Järjestusseosed luuakse hulgal siis, kui mõne või kõigi selle.elementide paaride puhul on seos

ülimuslikkus . Setting-hulga jaoks nimetatakse mingit järjestuse seost tema käsk, ja "ise. seatud selle tulemusena muutub korrastatud. Järjestussuhteid saab sisse viia erineval viisil. Lõpliku hulga jaoks määrab selle elementide igasugune permutatsioon "mingi range järjekorra. Lõpmatut hulka saab järjestada lõpmatul arvul viisil. Huvi pakuvad ainult need järjestused, millel on tähenduslik tähendus.

Kui tellimuse suhte jaoks R võtteplatsil .M ja mõned erinevad elemendid, kehtib vähemalt üks seostest

aRb või b Ra , siis elemendid a ja b helistas võrreldav muidu - võrreldamatu.

Täielikult (või lineaarselt) tellitud komplekt M -

hulk, millel järjekord on antud, ja hulga mis tahes kaks elementi M võrreldav; osaliselt tellitud komplekt- sama, kuid võrreldamatute elementide paarid on lubatud.

Lineaarselt järjestatud hulk on punktide kogum sirgel, mille seos on "paremale", täisarvude hulk, ratsionaalne, reaalarvude hulk "suuremast" jne.

Osaliselt järjestatud hulga näiteks on kolmemõõtmelised vektorid, kui järjekord on antud justkui

See tähendab, et kui kõigi kolme koordinaadi eelistus on täidetud, on vektorid (2, 8, 5) ja (6, 9, 10) võrreldavad ning vektorid (2, 8, 5) ja (12, 7, 40) ) ei ole võrreldavad. Sellist järjestamisviisi saab laiendada mis tahes dimensiooniga vektoritele: vektor

eelneb vektorile, kui

Ja tehtud

Vektorite hulgal võib kaaluda ka muid järjestuse näiteid.

1) osaline tellimus: , kui

Need. vektorite pikkuse järgi; sama pikkusega vektorid on võrreldamatud.

2) lineaarne järjekord: , kui a kui a-d, siis b< е ; kui jed \u003d c? u6 \u003d e, siis