Förhållandet mellan strikt och icke-strikt ordning. Deras egenskaper, exempel. Orderrelationer Strikta orderrelationer

Det sista exemplet introducerar begreppet alfabetisk ordning.

Alfabetär en tuppel av parvis distinkta tecken som kallas bokstäver i alfabetet. Ett exempel är alfabetet för alla europeiska språk, samt alfabetet med 10 arabiska siffror. På en dator bestämmer tangentbordet och några stödjande verktyg alfabetet för giltiga tecken.

Ord i alfabetetA - tuppel av alfabetet tecken A. Ordet skrivs i alfabetiska symboler i rad, från vänster till höger, utan mellanslag. Ett naturligt tal är ett ord i det digitala alfabetet. En formel är inte alltid ett ord på grund av det icke-linjära arrangemanget av symboler; förekomsten av upphöjda (exponenter) och nedsänkta (index för variabler, baser av logaritmer) symboler, bråkstaplar, teckenradikaler, etc.; men enligt vissa konventioner kan det skrivas in i en sträng, som används till exempel i datorprogrammering (exponentieringstecknet skrivs till exempel som 2 multiplikationstecken i rad: 5**3 betyder tredje potensen av nummer 5.

Lexikografisk (alfabetisk) ordning - för olika ord i alfabetet med ordnade

symboler anger ordningen: , if

presentation möjlig , vid vilken heller

(underord kan vara tomt), eller - tomt underord

I denna definition - ett prefix (initial underord) som är samma för båda orden - eller de första till vänster är olika

tecken, antingen - det sista tecknet i ordet - svans

underord.

Således bestäms den alfabetiska ordningen av ord av den första symbolen till vänster som särskiljer dem (till exempel ordet KONUS föregår ordet COSINE eftersom de först skiljer sig åt i den tredje bokstaven, och N föregår S i det ryska alfabetet). Mellanslagstecknet anses också föregå alla tecken i alfabetet - för fallet när ett av orden är ett prefix till ett annat (till exempel CON och CONE)

Träning. Kontrollera att den alfabetiska ordningen för naturliga tal som har samma antal decimaler sammanfaller med deras storleksordning.

Låta A - delvis beställt set. Elementet kallas maximal V A, om det inte finns något element för vilket A< b. Element A kallad den största V A, om för alla olika A element färdigt b<а-

Bestäms symmetriskt minimala och minsta element. Begreppen största och maximala (respektive minsta och minsta) element är olika - se. exempel i fig. 14. Uppsättningen i fig. 14,a har det största elementet R, det är också max, det finns två minimielement: s och t, det finns ingen minsta. I fig. 14b, tvärtom, finns det en uppsättning som har två maximala element / och j, det finns ingen störst, minimal, aka den minsta - en: T.

I allmänhet, om en uppsättning har det största (respektive minsta) elementet, så finns det bara ett (det kan inte finnas någon).

Det kan finnas flera maximi- och minimumelement (det kanske inte finns några alls - i en oändlig mängd; i det sista fallet - måste det finnas).

Låt oss titta på ytterligare två exempel. - relation på en uppsättning N:

"Y delar upp X", eller "Xär en divisor av ett tal Y"(Till exempel,

) är reflexiv och transitiv. Låt oss betrakta det på en ändlig uppsättning delare av talet 30.

Relationen är en partiell ordningsrelation (icke-strikt)

och representeras av följande matris av ordning 8, innehållande 31 tecken

Motsvarande krets med 8 hörn måste innehålla 31 länkar. . Det kommer dock att vara bekvämare för visning om vi utesluter 8

connectives-loops som skildrar relationens reflexivitet (diagonala element i matrisen) och transitiva connectives, d.v.s. ligament

Om det finns ett mellantal Z så att

(till exempel kopplingen sedan). Sedan i schemat

12 ligament kommer att finnas kvar (fig. 15); saknade länkar antyds "av transitivitet". Siffran 1 är den minsta och siffran 30

största inslagen i . Om vi ​​utesluter från siffran 30 och

överväg samma delordning på uppsättningen, då

det finns inget maxelement, men det finns 3 maxelement: 6, 10, 15

Låt oss nu bygga samma krets för en relation på en Boolean

(mängden av alla delmängder) av en treelementsmängd

Innehåller 8 element:

Kontrollera att om du matchar elementen a, b, c, siffrorna 2, 3, 5 och operationerna för att kombinera mängder är multiplikation av motsvarande siffror (dvs., till exempel, delmängden motsvarar

produkt 2 5 = 10), så blir relationsmatrisen exakt så här

samma som för relation ; diagram över dessa två samband med de som beskrivs

förkortningar av loopar och transitiva kopplingar sammanfaller upp till notation (se fig. 16). Det minsta elementet är

Och den största -

Binära relationer R på ett set A Och S på ett set I kallas isomorf, om mellan A och B det är möjligt att upprätta en en-till-en-korrespondens Г, där, om (dvs.

element är i relation R), sedan (bilder

dessa element är i relation S).

Således är partiellt ordnade uppsättningar isomorfa.

Det övervägda exemplet tillåter generalisering.

En boolesk relation är en delordning. Om

De där. ett gäng E innehåller P element, sedan var och en

motsvarar delmängden P-dimensionell vektor med

komponenter , var är den karakteristiska funktionen

ställ in A/ . Uppsättningen av alla sådana vektorer kan betraktas som en uppsättning punkter P-dimensionellt aritmetiskt utrymme med koordinaterna 0 eller 1, eller med andra ord som hörn P-dimensionell

enhetskub, betecknad med , d.v.s. kub med kanter av enhetslängd. För n = 1, 2, 3 indikerade punkter representerar respektive ändarna på ett segment, hörnen på en kvadrat och en kub - därav det vanliga namnet. För /7=4 finns en grafisk representation av detta förhållande i fig. 17. Nära varje hörn av en 4-dimensionell kub motsvarande

delmängd av 4-elementuppsättning och fyrdimensionell

en vektor som representerar den karakteristiska funktionen för denna delmängd. De hörn som motsvarar delmängder som skiljer sig i närvaro av exakt ett element är anslutna till varandra.

I fig. 17 är en fyrdimensionell kub avbildad på ett sådant sätt att på en

nivå, ojämförbara element är placerade i par, som innehåller samma antal enheter i posten (från 0 till 4), eller, med andra ord, samma antal element i de representerade delmängderna.

I fig. 18a, b - andra visuella representationer av en 4-dimensionell kub;

i fig. 18a axeln för den första variabeln ÅH riktad uppåt (avsiktlig avvikelse från vertikalen så att olika kanter på kuben inte smälter samman):

i detta fall den 3-dimensionella subkuben som motsvarar X= 0 finns nedanför, och för X= 1 - högre. I fig. 186 samma axel ÅH riktad från insidan av kuben till utsidan, den inre subkuben motsvarar X= Åh, och den externa är X = 1.

I
Materialfilen visar en bild av en 5-dimensionell enhetskub (s. 134).

Ordet "ordning" används ofta i en mängd olika frågor. Officeren ger kommandot: "Räkna i numerisk ordning", aritmetiska operationer utförs i en viss ordning, idrottare rangordnas efter höjd, alla ledande schackspelare är ordnade i en viss ordning enligt de så kallade Elo-koefficienterna (amerikansk professor vem utvecklade systemkoefficienterna, så att du kan ta hänsyn till spelarnas alla framgångar och misslyckanden), efter mästerskapet är alla fotbollslag placerade i en viss ordning, etc. Det finns en operationsordning när man tillverkar en del, ordföljd i en mening (försök att förstå vad meningen "på den gamle mannen" betyder att jag inte planterade åsnan!"

Genom att arrangera elementen i en viss uppsättning efter varandra, ordnar vi dem eller upprättar någon relation mellan dem i ordning. Det enklaste exemplet är den naturliga ordningen för de naturliga talen. Dess naturlighet ligger i det faktum att vi för två naturliga tal vet vilket som följer efter det andra eller vilket som är större än det andra, så vi kan ordna de naturliga talen i en sekvens så att det större talet är placerat, till exempel till höger om den mindre: 1, 2, 3, ... . Naturligtvis kan sekvensen av element skrivas i vilken riktning som helst, inte bara från vänster till höger. Själva begreppet naturliga tal innehåller redan idén om ordning. Genom att etablera ett relativt arrangemang av elementen i vilken mängd som helst, definierar vi därigenom en binär ordningsrelation på den, som i varje specifikt fall kan ha sitt eget namn, till exempel "att vara mindre", "att vara äldre", "att vara äldre", ingå i ", "följa" etc. Symboliska ordningsbeteckningar kan också varieras, till exempel Í osv.

Det främsta utmärkande draget för en ordningsrelation är att den har egenskapen transitivitet. Så, om vi har att göra med en sekvens av några objekt x 1, x 2, ..., x n,..., ordnade till exempel efter relation, sedan från det som utförs x 1x 2... x n..., det bör följa det för vilket par som helst x i, x j delar av denna sekvens är också uppfyllda x ix j:

För ett par element x ij i relationsgrafen ritar vi en pil från vertexet x i till toppen x j, dvs från det mindre elementet till det större.

Ordningsrelationsgrafen kan förenklas genom att använda den så kallade metoden Hasse diagram. Hasse-diagrammet är konstruerat enligt följande. Mindre element placeras lägre och större placeras högre. Eftersom en sådan regel inte ensam räcker för avbildning, ritas linjer som visar vilket av de två elementen som är större och vilket som är mindre än det andra. I det här fallet räcker det att bara rita linjer för elementen omedelbart efter varandra. Exempel på Hasse-diagram visas i figuren:

Du behöver inte inkludera pilar i ett Hasse-diagram. Hasse-diagrammet kan roteras i ett plan, men inte godtyckligt. Vid svängning är det nödvändigt att bibehålla den relativa positionen (ovanför - nedan) för diagrammets hörn:

Attityd R i överflöd X kallad attityd av strikt ordning, om den är transitiv och asymmetrisk.

En uppsättning där en strikt ordningsrelation definieras kallas beordrade. Till exempel är mängden naturliga tal ordnad efter relationen "mindre än". Men samma uppsättning är också ordnad efter en annan relation - "delad i" och "mer".

Grafen för relationen "mindre än" i uppsättningen naturliga tal kan avbildas som en stråle:

Attityd R V X kallas relation icke-strikt (partiell) ordning, om den är transitiv och antisymmetrisk. Varje förhållande av icke-strikt ordning är reflexivt.

Epitetet "partiell" uttrycker det faktum att kanske inte alla delar av en uppsättning är jämförbara i ett givet avseende.

Typiska exempel på partiella ordningsrelationer är relationerna "inte större än", "inte mindre än" och "inte större än". Partikeln "inte" i relationernas namn tjänar till att uttrycka deras reflexivitet. Relationen "inte mer än" sammanfaller med relationen "mindre än eller lika", och relationen "inte mindre" är detsamma som "större än eller lika". I detta avseende kallas också partiell ordning inte strikt i ordning. Ofta betecknas en partiell (icke-strikt) ordningsrelation med symbolen "".

Inklusionsrelationen Í mellan delmängder av en viss mängd är också en partiell ordning. Uppenbarligen är inte varannan delmängd jämförbar i detta avseende. Figuren nedan visar den partiella inkluderingsordningen på uppsättningen av alla delmängder av uppsättningen (1,2,3). Pilarna på grafen som ska peka uppåt visas inte.

Uppsättningar på vilka delordning ges anropas delvis beställd, eller bara beordrade set.

Element X Och på delvis beställt set kallas jämför med oss Om Xpå eller påX. Annars är de inte jämförbara.

En ordnad uppsättning där två valfria element är jämförbara kallas linjärt ordnade, och ordningen är linjär. Linjär ordning kallas också perfekt ordning.

Till exempel är mängden av alla reella tal med naturlig ordning, såväl som alla dess delmängder, linjärt ordnade.

Föremål av mest varierande karaktär kan beställas hierarkiskt. Här är några exempel.

Exempel 1: Delarna i en bok är ordnade så att en bok innehåller kapitel, kapitel innehåller avsnitt och avsnitt innehåller underavsnitt.

Exempel 2. Mappar i datorns filsystem är kapslade inuti varandra och bildar en grenstruktur.

Exempel 3. Relationen mellan föräldrar och barn kan skildras som den sk släktträd, som visar vem som är vems förfader (eller avkomma).

Släpp på uppsättningen A delorder ges. Element X kallad maximum (minimum) element i mängd A, om från det faktum att Xpå(påX), jämställdhet följer X= u. Med andra ord, elementet Xär max (minimum) om för något element på eller är det inte sant det Xpå(påX), eller exekveras X=u. Således är det maximala (minsta) elementet större (mindre) än alla element som skiljer sig från det som det är i relation till.

Element X kallad störst (minst), om för någon påÎ A genomförde på< х (х< у).

En delbeställd uppsättning kan ha flera minimi- och/eller maximumelement, men det kan inte finnas mer än ett minimum- och maximumelement. Det minsta (största) elementet är också minimum (maximum), men det omvända är inte sant. Bilden till vänster visar en delordning med två minsta och två maximala element, och till höger en delordning med de minsta och största elementen:

I en ändlig, delvis ordnad uppsättning finns det alltid minimum- och maximumelement.

En beställd uppsättning som har de största och minsta elementen kallas begränsad. Figuren visar ett exempel på en oändlig avgränsad mängd. Naturligtvis är det omöjligt att avbilda en oändlig uppsättning på en ändlig sida, men du kan visa principen för dess konstruktion. Här visas inte slingorna nära hörnen för att förenkla ritningen. Av samma anledning visas inte bågarna som ger visningen av transitivitetsegenskapen. Figuren visar med andra ord Hasse-diagrammet för ordningsrelationen.

Oändliga uppsättningar kanske inte har max- eller minimumelement, eller båda. Till exempel har uppsättningen naturliga tal (1,2, 3, ...) ett minsta element på 1, men inget maximum. Mängden av alla reella tal med naturlig ordning har varken ett minsta eller största element. Men dess delmängd består av alla siffror X< 5, har det största elementet (talet 5), men har inte det minsta.

Ett gäng X (\displaystyle X), på vilken den partiella ordningsrelationen introduceras, kallas delvis beställd. En icke-strikt partiell ordningsrelation betecknas ofta med ≼ (\displaystyle \preccurlyeq ).

alternativ

Partiell orderrelation R (\displaystyle R) kallad linjär ordning, om villkoret är uppfyllt

Ett gäng X (\displaystyle X), på vilken en linjär ordningsrelation introduceras, kallas linjärt ordnade, eller kedja.

Attityd R (\displaystyle R), att uppfylla endast villkoren för reflexivitet och transitivitet kallas förbeställning eller kvasibeställning.

Strikt ordning

Om villkoret reflexivitet ersätts med villkoret antireflexivitet:

då får vi definitionen sträng, eller antireflexiv delordning(vanligtvis indikerat med symbolen ≺ (\displaystyle \prec )).

Kommentar. En relations samtidiga antireflexivitet och transitivitet innebär antisymmetri. Därför är relationen förhållande av en strikt ordning om och bara om det är antireflexivt och transitivt.

I allmänhet, om R (\displaystyle R)är alltså en transitiv, antisymmetrisk relation

Exempel

• På uppsättningen av reella tal är relationerna "mer än" och "mindre än" relationer av strikt ordning, och "mer än eller lika med" och "mindre än eller lika med" är icke-strikta.
• Delbarhetsrelationen på en uppsättning heltal är en relation av icke-strikt ordning.

Dushnik-Miller dimension

Berättelse

Tecken < {\displaystyle <} Och > (\displaystyle >) uppfunnit

Egenskaper för relationer:

1) reflexivitet;

2) symmetri;

3)transitivitet.

4) anknytning.

Attityd R på ett set X kallad reflekterande, om varje element i uppsättningen X vi kan säga att han är i ett förhållande R Med mig själv: XRx. Om relationen är reflexiv, så finns det en slinga vid varje hörn av grafen. Omvänt är en graf vars varje hörn innehåller en loop en reflexiv relationsgraf.

Exempel på reflexiva relationer är relationen "multipel" på mängden naturliga tal (varje tal är en multipel av sig själv), och likhetsrelationen mellan trianglar (varje triangel liknar sig själv), och relationen "likhet" ( varje tal är lika med sig själv), etc.

Det finns relationer som inte har egenskapen reflexivitet, till exempel förhållandet mellan segmentens vinkelräta: ab, ba(det finns inte ett enda segment som kan sägas vara vinkelrätt mot sig självt) . Därför finns det inte en enda slinga i grafen för detta förhållande.

Relationen "längre" för segment, "mer med 2" för naturliga tal, etc. har inte egenskapen reflexivitet.

Attityd R på ett set X kallad antireflekterande, om för något element från uppsättningen X alltid falskt XRx: .

Det finns relationer som varken är reflexiva eller antireflexiva. Ett exempel på ett sådant förhållande är förhållandet ”punkt X symmetrisk i sak på relativt rak l", definierad på en uppsättning punkter i planet. Ja, alla punkter på en rak linje lär symmetriska till sig själva och punkter som inte ligger på en rak linje jag, själva är inte symmetriska.

Attityd R på ett set X kallad symmetrisk, om villkoret är uppfyllt: från det faktum att elementet X står i relation till elementet y, det följer att elementet yär i relation R med element X:xRyyRx.

Den symmetriska relationsgrafen har följande funktion: tillsammans med varje pil som kommer från X Till y, innehåller grafen en pil som går från y Till X(Fig. 35).

Exempel på symmetriska relationer kan vara följande: förhållandet mellan "parallellism" av segment, förhållandet mellan "vinkelrätt" av segment, förhållandet mellan "likhet" av segment, förhållandet mellan likhet mellan trianglar, förhållandet mellan "likhet" av bråk etc.

Det finns relationer som inte har egenskapen symmetri.

Ja, om segmentet X längre än segmentet på, sedan segmentet på kan inte vara längre än segmentet X. Grafen för detta förhållande har en egenhet: pilen som förbinder hörnen är endast riktad i en riktning.

Attityd R kallad antisymmetrisk, om för några element X Och y från sanningen xRy ska vara falskt yRx: : xRyyRx.

Förutom den "längre" relationen finns det andra antisymmetriska relationer på många segment. Till exempel, relationen "större än" för tal (if X Mer på, Den där på det kan inte bli mer X), "mer om"-attityden osv.

Det finns relationer som varken har egenskapen symmetri eller egenskapen antisymmetri.

Relation R på en uppsättning X kallad transitiv, om från det elementet Xär i relation R med element y, och element yär i relation R med element z, det följer att elementet Xär i relation R med element z: xRy Och yRzxRz.

Transitiv relationsgraf med varje par av pilar som kommer från X Till y och från y Till z, innehåller en pil som går från X Till z.

Relationen "längre" på en uppsättning segment har också transitivitetsegenskapen: om segmentet A längre än segmentet b, linjesegmentet b längre än segmentet Med, sedan segmentet A längre än segmentet Med. Relationen "jämlikhet" på en uppsättning segment har också egenskapen transitivitet: (a=b, b=c)(a=c).

Det finns relationer som inte har egenskapen transitivitet. En sådan relation är till exempel relationen vinkelräthet: om ett segment A vinkelrätt mot segmentet b och segmentet b vinkelrätt mot segmentet Med, sedan segmenten A Och Med inte vinkelrät!

Det finns en annan egenskap av relationer, som kallas egenskapen för anknytning, och en relation som har den kallas sammankopplad.

Attityd R på ett set X kallad ansluten, om för några element X Och y från denna uppsättning är följande villkor uppfyllt: if X Och yär olika då heller Xär i relation R med element y, eller element yär i relation R med element X. Med hjälp av symboler kan detta skrivas så här: xyxRy eller yRx.

Till exempel har relationen "större än" för naturliga tal egenskapen att vara ansluten: för alla distinkta tal x och y kan man ange antingen x>y, eller y>x.

I en sammankopplad relationsgraf är två valfria hörn sammankopplade med en pil. Det motsatta påståendet är också sant.

Det finns relationer som inte har egenskapen anknytning. En sådan relation, till exempel, är relationen mellan delbarhet på mängden naturliga tal: vi kan namnge sådana tal x och y oavsett antal Xär inte en divisor av ett tal y, inget nummer yär inte en divisor av ett tal X(tal 17 Och 11 , 3 Och 10 etc.) .

Låt oss titta på några exempel. På set X=(1, 2, 4, 8, 12) relationen "antal" ges X multipel av talet y" Låt oss konstruera en graf över detta förhållande och formulera dess egenskaper.

Relationen mellan bråklikhet sägs vara en ekvivalensrelation.

Attityd R på ett set X kallad ekvivalensförhållande, om den samtidigt har egenskaperna reflexivitet, symmetri och transitivitet.

Exempel på ekvivalensrelationer inkluderar: likhetsrelationer för geometriska figurer, relationer av parallellitet mellan linjer (förutsatt att sammanfallande linjer anses vara parallella).

I förhållandet "jämlikhet av bråk" som diskuterats ovan, uppsättningen X delas upp i tre delmängder: ( ; ; }, {; } , (). Dessa delmängder skär inte varandra, och deras förening sammanfaller med mängden X, dvs. vi har en uppdelning av uppsättningen i klasser.

Så, om en ekvivalensrelation ges på en mängd X, genererar den en partition av denna mängd i parvis disjunkta delmängder - ekvivalensklasser.

Således har vi fastställt att jämställdhetsrelationen på uppsättningen
X=( ;; ; ; ; ) motsvarar uppdelningen av denna mängd i ekvivalensklasser, som var och en består av bråkdelar lika med varandra.

Principen att dela upp en uppsättning i klasser med hjälp av någon ekvivalensrelation är en viktig princip inom matematiken. Varför?

För det första betyder likvärdig likvärdig, utbytbar. Därför är element av samma ekvivalensklass utbytbara. Således, fraktioner som är i samma ekvivalensklass (; ; ), är omöjliga att särskilja ur synvinkeln av förhållandet mellan jämlikhet och bråkdelen kan till exempel ersättas av en annan . Och denna ersättning kommer inte att ändra resultatet av beräkningarna.

För det andra, eftersom ekvivalensklassen innehåller element som inte går att särskilja ur någon relations synvinkel, tror man att ekvivalensklassen bestäms av någon av dess representanter, dvs. ett godtyckligt element i klassen. Således kan vilken klass som helst av lika fraktioner specificeras genom att specificera vilken fraktion som helst som tillhör denna klass. ekvivalensklass av en representant låter dig studera en uppsättning representanter från ekvivalensklasser istället för alla delar av uppsättningen. Till exempel genererar ekvivalensrelationen "att ha samma antal hörn", definierad på en uppsättning polygoner, en partition av denna uppsättning i klasser av trianglar, fyrkanter, femhörningar, etc. fastigheter som ingår i en viss klass anses på en av dess representanter.

För det tredje, partitionering av en uppsättning i klasser med hjälp av en ekvivalensrelation används för att introducera nya begrepp. Till exempel kan begreppet "bunt av linjer" definieras som vad parallella linjer har gemensamt med varandra.

En annan viktig typ av relation är ordningsförhållandet. Låt oss överväga problemet. På uppsättningen X={3, 4, 5, 6, 7, 8, 9, 10 ) relationen ”har samma rest när de divideras med 3 " Denna relation genererar en partition av uppsättningen X in i klasser: alla tal kommer att falla i en, när de divideras med 3 det visar sig vara resten 0 (detta är siffror 3, 6, 9 ). I den andra - siffror, när de divideras med 3 resten är 1 (detta är siffror 4, 7, 10 ). Den tredje kommer att innehålla alla siffror som, när de divideras med 3 resten är 2 (detta är siffror 5, 8 ). Faktum är att de resulterande uppsättningarna inte skär varandra och deras förening sammanfaller med mängden X. Därför har relationen "samma återstod när den divideras med 3 ", definieras på setet X, är en ekvivalensrelation.

För att ta ett annat exempel kan de många eleverna i en klass sorteras efter längd eller ålder. Observera att denna relation har egenskaperna antisymmetri och transitivitet. Eller så vet alla ordningen på bokstäverna i alfabetet. Det tillhandahålls av "bör"-attityden.

Attityd R på ett set X kallad förhållande av en strikt ordning, om den samtidigt har egenskaperna antisymmetri och transitivitet. Till exempel relationen " X< y».

Om relationen har egenskaperna reflexivitet, antisymmetri och transitivitet, så kommer den att vara sådan icke-strikt förhållande. Till exempel relationen " Xy».

Exempel på ordningsrelationer inkluderar: "mindre än"-relationen på en uppsättning naturliga tal, den "kortare" relationen på en uppsättning segment. Om en ordningsrelation också har egenskapen anknytning, så sägs den vara det linjär ordningsrelation. Till exempel relationen "mindre än" på mängden naturliga tal.

Ett gäng X kallad ordnad, om en orderrelation anges på den.

Till exempel många X={2, 8, 12, 32 ) kan beställas med hjälp av "mindre än"-relationen (fig. 41), eller så kan detta göras med "multipel"-relationen (fig. 42). Men eftersom de är ordningsrelationer, ordnar relationerna "mindre än" och "multipel" mängden naturliga tal på olika sätt. Relationen "mindre än" låter dig jämföra två valfria tal från en uppsättning X, men relationen "multipel" har inte denna egenskap. Okej, ett par siffror. 8 Och 12 är inte relaterat till relationen "multipel": det kan inte sägas så 8 flera olika 12 eller 12 flera olika 8.

Man ska inte tro att alla relationer är uppdelade i ekvivalensförhållanden och ordningsförhållanden. Det finns ett stort antal relationer som varken är ekvivalensrelationer eller ordningsrelationer.

Ekvivalensförhållande. Sambandet mellan ekvivalensrelationen och uppdelningen av en mängd i klasser

Definition. Attityd R på ett set X kallas en ekvivalensrelation om den är reflexiv, symmetrisk och transitiv.

Exempel. Tänk på förhållandet" X klasskamrat på"på många studenter vid pedagogiska fakulteten. Den har följande egenskaper:

1) reflexivitet, eftersom varje elev är sin egen klasskamrat;

2) symmetri, eftersom om en student X på, sedan studenten påär en klasskamrat till en student X;

3) transitivitet, eftersom om en student X- klasskamrat på, och studenten på– klasskamrat z, sedan studenten X kommer att vara elevens klasskamrat z.

Således har denna relation egenskaperna reflexivitet, symmetri och transitivitet, och är därför en ekvivalensrelation. Samtidigt kan många studenter vid Pedagogiska fakulteten delas in i delmängder bestående av studenter som läser i samma kurs. Vi får 5 delmängder.

Ekvivalensrelationer är också t.ex. förhållandet mellan linjers parallellitet, förhållandet mellan figurernas likhet. Varje sådan relation är associerad med att partitionera uppsättningen i klasser.

Sats. Om på set X givet en ekvivalensrelation, delar den upp denna mängd i parvis disjunkta delmängder (ekvivalensklasser).

Det omvända påståendet är också sant: om någon relation definieras i mängden X, genererar en partition av denna uppsättning i klasser, då är det en ekvivalensrelation.

Exempel. På set X= (1; 2; 3; 4; 5; 6; 7; 8) relationen "ha samma återstod när dividerad med 3" specificeras. Är det ett ekvivalensförhållande?

Låt oss bygga en graf över detta förhållande: (oberoende)

Denna relation har egenskaperna reflexivitet, symmetri och transitivitet, därför är den en ekvivalensrelation och delar upp mängden X till ekvivalensklasser. I varje ekvivalensklass kommer det att finnas tal som, när de divideras med 3, ger samma återstod: X 1 = {3; 6}, X 2 = {1; 4; 7}, X 3 = {2; 5; 8}.

Man tror att ekvivalensklassen bestäms av någon av dess representanter, dvs. ett godtyckligt inslag i denna klass. Således kan en klass med lika bråk specificeras genom att specificera vilken bråkdel som helst som tillhör denna klass.

I matematikens inledande kurs möter man även ekvivalensrelationer, till exempel "uttryck X Och på har samma numeriska värden", "figur X lika med figuren på».

Definition. Attityd R på ett set X kallas en ordningsrelation om den är transitiv och asymmetrisk eller antisymmetrisk.

Definition. Attityd R på ett set X kallas en strikt ordningsrelation om den är transitiv och asymmetrisk.

Exempel relationer av strikt ordning: "mer" på uppsättningen naturliga tal, "högre" på uppsättningen av människor, etc.

Definition. Attityd R på ett set X kallas en icke-strikt ordningsrelation om den är transitiv och antisymmetrisk.

Exempel relationer av en icke-strikt ordning: "inte mer" på mängden reella tal, "vara en divisor" på mängden naturliga tal, etc.

Definition. Ett gäng X kallas ordered om en orderrelation anges på den.

Exempel. På set X= (1; 2; 3; 4; 5) två relationer ges: " X £ på"och" X- avdelare på».

Båda dessa relationer har egenskaperna reflexivitet, antisymmetri och transitivitet (konstruera grafer och kontrollera egenskaperna själv), d.v.s. är relationer av icke strikt ordning. Men det första förhållandet har egenskapen att vara förenat, medan det andra inte har det.

Definition. Beställningsförhållande R på ett set X kallas en linjär ordningsrelation om den har egenskapen anknytning.

I grundskolan studeras många ordningsrelationer. Redan i första klass finns det relationer "mindre", "mer" på uppsättningen naturliga tal, "kortare", "längre" på uppsättningen av segment, etc.

Kontrollfrågor

1. Definiera en binär relation på en mängd X.

2. Hur man skriver ett påstående om att elementen X Och påär i ett förhållande R?

3. Lista sätt att definiera relationer.

4. Formulera de egenskaper som relationer kan ha. Hur återspeglas dessa egenskaper i grafen?

5. Vilka egenskaper måste en relation ha för att den ska vara en ekvivalensrelation?

6. Hur är ekvivalensrelationen relaterad till uppdelningen av en mängd i klasser?

7. Vilka egenskaper måste en relation ha för att den ska vara en ordningsrelation?