Cuvântul „ordine” este adesea folosit într-o varietate de probleme. Ofițerul dă comanda: „Calculează după ordinea numerelor”, operațiile aritmetice sunt efectuate într-o anumită ordine, sportivii sunt clasificați în funcție de înălțime, există o ordine pentru efectuarea operațiilor la realizarea unei piese, există o ordine a cuvintelor într-o propoziție.
Ce este comun în toate cazurile când vorbim despre ordine? Faptul este că cuvântul „ordine” are următorul sens: înseamnă care element din acest sau acel set urmează căruia (sau care element precede pe care).
Atitudine" X urmează la" tranzitiv: dacă " X urmează la" Și " la urmează z", Acea " X urmează z" În plus, această relație trebuie să fie antisimetrică: pentru două diferite XȘi la, Dacă X urmează la, Acea la nu urmează X.
Definiție. Atitudine R pe un platou X numit atitudine ordine strictă , dacă este tranzitivă și antisimetrică.
Să aflăm caracteristicile graficului și graficului relațiilor de ordine strictă.
Să ne uităm la un exemplu. Pe platou X= (5, 7, 10, 15, 12) raport dat R: « X < la" Să definim această relație prin enumerarea perechilor
R = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.
Să-i construim graficul. Vedem că graficul acestei relații nu are bucle. Nu pe grafic săgeți duble. Dacă de la X săgeata merge la la, și de la la- V z, apoi din X săgeata merge la z(Fig. 8).
Graficul construit vă permite să aranjați elementele mulțimii X in aceasta ordine:
{5, 7, 10, 12, 15}.
În Fig. 6 (§ 6 din acest capitol), coloanele VII, VIII sunt grafice ale relațiilor de ordine strictă.
Relație nestrictă
Relația „mai puțin” într-un set numere reale opusul este atitudinea „nu mai puțin”. Nu mai este o relație de ordine strictă. Ideea este, când X = la, relațiile sunt îndeplinite X ³ laȘi la ³ X, adică atitudinea „nu mai puțin” este reflexivă.
Definiție. Atitudine R pe un platou X numit relație nestrictă, dacă este reflexiv, antisimetric și tranzitiv.
Astfel de relații sunt uniuni ale unei relații de ordine strictă cu o relație de identitate.
Luați în considerare relația „nu mai mult” (£) pentru mulțime
X= (5, 7, 10, 15, 12). Să construim graficul acestuia (Fig. 9).
Un grafic de relații de ordine strictă, spre deosebire de un grafic de relații de ordine strictă, are bucle la fiecare vârf.
În fig. 6 (§ 6 din prezentul capitol) coloanele V, VI sunt grafice ale relațiilor de ordine nestrictă.
Seturi comandate
O mulțime se poate dovedi a fi ordonată (de asemenea, se spune complet ordonată) de o relație de ordine, în timp ce o altă mulțime poate fi neordonată sau parțial ordonată de o astfel de relație.
Definiție. O multime de X numit ordonat vreo relație de ordine R, dacă pentru oricare două elemente X y din X:
(X, la) Î R sau ( y, x) Î R.
Dacă R este o relație de ordine strictă, apoi mulțimea X ordonată prin această relaţie prevăzută: dacă X, la oricare două elemente inegale ale mulţimii X, Acea ( X, la) Î R sau ( y, x) Î R, sau oricare două elemente X y seturi X sunt egale.
Din cursul școlar de matematică se știe că mulțimi de numere N , Z , Q , R ordonat după relația „mai puțin decât” (<).
Mulțimea submulțimii unei anumite mulțimi nu este ordonată prin introducerea relației de includere (I), sau de incluziune strictă (S) în sensul de mai sus, deoarece există subseturi, dintre care niciunul nu este inclus în celălalt. În acest caz, spunem că mulțimea dată este parțial ordonată de relația Í (sau Ì).
Luați în considerare setul X= (1, 2, 3, 4, 5, 6) și conține două relații „mai puțin decât” și „împărțit la”. Este ușor de verificat că ambele aceste relații sunt relații de ordine. Graficul relației „mai puțin decât” poate fi reprezentat ca o rază.
Graficul relației „împărțit la” poate fi reprezentat doar pe un plan.
În plus, graficul celei de-a doua relații are vârfuri care nu sunt conectate printr-o săgeată. De exemplu, nu există săgeată care să lege numerele 4 și 5 (Fig. 10).
Prima relatie" X < la„se numește liniar. În general, dacă relația este de ordine R(strict și non-strict) pe platou X are proprietatea: pentru orice X, laÎ X sau xRy, sau yRx, atunci se numește relație de ordin liniar, iar mulțimea X– o mulțime ordonată liniar.
Dacă setul X desigur, și constă din n elemente, apoi ordonarea liniară X se reduce la numerotarea elementelor sale cu numerele 1,2,3, ..., n.
Mulțimile ordonate liniar au o serie de proprietăți:
1°. Lăsa a, b, c– elemente ale ansamblului X, ordonat după relație R. Daca se stie ca aRвȘi în Rс, apoi se spune că elementul V se află între elemente AȘi Cu.
2°. O multime de X, ordonat liniar după relație R, se numește discret dacă între oricare dintre două elemente ale sale se află doar o mulțime finită de elemente ale acestei mulțimi.
3°. O mulțime ordonată liniar se numește densă dacă pentru oricare două elemente distincte ale acestei mulțimi există un element al mulțimii aflat între ele.
Un tip important de relații binare sunt relațiile de ordine. Relație strictă de ordine - o relație binară care este antireflexivă, antisimetrică și tranzitivă:
denumire - (A precedat b). Exemplele includ
relații „mai mult”, „mai puțin”, „mai vechi”, etc. Pentru numere, notația obișnuită este semnele "<", ">".
Relație de ordine nestrictă - relație binară reflexivă, antisimetrică și tranzitivă. Alături de exemplele naturale de inegalități non-strictive pentru numere, un exemplu poate fi relația dintre punctele unui plan sau spațiu „pentru a fi mai aproape de originea coordonatelor”. Inegalitatea nestrictă, pentru numere întregi și reale, poate fi considerată și ca o disjuncție a relațiilor de egalitate și ordine strictă.
Dacă un turneu sportiv nu prevede împărțirea locurilor (adică fiecare participant primește un anumit loc, doar mâncare/premiat), atunci acesta este un exemplu de ordine strictă; altfel, nu este strict.
Relațiile de ordine se stabilesc pe o mulțime atunci când pentru unele sau toate perechile de elemente ale acestuia relația
precedenta . Sarcina - pentru un set de anumite relații de ordine este numită „aranjarea sa, iar „setul însuși” ca urmare a acesteia devine ordonat. Relațiile de ordine pot fi introduse în moduri diferite. Pentru o mulțime finită, orice permutare a elementelor sale „stabilește o ordine strictă O mulțime infinită poate fi ordonată într-un număr infinit de moduri.
Dacă pentru relaţia de comandă R pe un platou .M iar unele elemente diferite deţin cel puţin una dintre relaţii
aRb sau sutien, apoi elementele AȘi b sunt numite comparabil, in caz contrar - incomparabil.
Un set ordonat complet (sau liniar). M -
o mulțime pe care este specificată o relație de ordine și oricare două elemente ale mulțimii M comparabil; set parțial comandat- la fel, dar sunt permise perechi de elemente incomparabile.
Liniar ordonat este mulțimea de puncte de pe o dreaptă cu relația „mai la dreapta”, mulțimea numerelor întregi, numerelor raționale, numerelor reale cu relația „mai mare decât”, etc.
Un exemplu de mulțime parțial ordonată ar fi vectorii tridimensionali, dacă ordinea este dată după cum urmează, dacă
Adică, dacă prioritatea este efectuată de-a lungul tuturor celor trei coordonate, vectorii (2, 8, 5) și (6, 9, 10) sunt comparabili, dar vectorii (2, 8, 5) și (12, 7, 40) nu sunt comparabile. Această metodă de ordonare poate fi extinsă la vectori de orice dimensiune: vector
precede yctorul dacă
Și gata
Putem lua în considerare și alte exemple de ordonare pe mulțimea vectorilor.
1) ordine parțială: 
, Dacă
Acestea. prin lungimea vectorului; vectorii de aceeași lungime sunt incomparabili.
2) ordine liniară: 
, Dacă A
Ultimul exemplu introduce conceptul de ordine alfabetică.
Alfabet este un tuplu de caractere distincte în perechi numite litere ale alfabetului. Un exemplu este alfabetul oricărei limbi europene, precum și alfabetul cu 10 cifre arabe Pe un computer, tastatura și unele instrumente de sprijin determină alfabetul caracterelor valide.
Cuvânt în alfabetA - tuplu de caractere alfabetice A. Cuvântul este scris cu simboluri alfabetice în rând, de la stânga la dreapta, fără spații. Un număr natural este un cuvânt din alfabetul digital superscript (exponenți) și subindice (indici de variabile, baze de logaritmi) simboluri, bară fracțională, semne radicali etc.; totuși, prin unele convenții, poate fi scris într-un șir, care este folosit, de exemplu, în programarea computerelor (de exemplu, semnul exponențiației este scris ca 2 semne de înmulțire la rând: 5**3 înseamnă a treia putere a numarul 5.
Ordinea lexicografică (alfabetică) - pentru diferite cuvinte din alfabet cu ordonate
simbolurile stabilesc ordonarea: , dacă
posibilă prezentare 
, la care fie
(subcuvântul poate fi gol) sau - subcuvânt gol
În această definiție - un prefix (subcuvânt inițial) care este același pentru ambele cuvinte - sau primele din stânga sunt diferite
caractere, fie - ultimul caracter din cuvânt - coada
subcuvinte.
Astfel, ordonarea alfabetică a cuvintelor este determinată de primul simbol din stânga care le deosebește (de exemplu, cuvântul KONUS precede cuvântul COSINE deoarece ele diferă mai întâi în a treia literă, iar N precede S în alfabetul rus). Caracterul spațiu este, de asemenea, considerat ca precede orice caracter al alfabetului - pentru cazul în care unul dintre cuvinte este un prefix al altuia (de exemplu, CON și CON)
Exercițiu. Verificați dacă ordonarea alfabetică a numerelor naturale care au același număr de zecimale coincide cu ordonarea lor după mărime.
Lăsa A - set parțial comandat. Elementul este numit maxim V A, dacă nu există niciun element pentru care A< b. Element A numit cel mai mare V A, dacă pentru fiecare diferit de A element finalizat b<а-
Determinat simetric minimă și cea mai mică elemente. Conceptele de elemente mai mari și maxime (respectiv, cele mai mici și minime) sunt diferite - vezi. exemplu în Fig. 14. Setul din Fig. 14,a are cel mai mare element R, este și maximul, există două elemente minime: s și t, nu există cel mai mic. În Fig. 14b, dimpotrivă, există o mulțime având două elemente maxime / și j, nu există cel mai mare, minim, alias cel mai mic - unul: T.
În general, dacă o mulțime are cel mai mare (respectiv, cel mai mic) element, atunci există doar unul (s-ar putea să nu existe).
Pot exista mai multe elemente maxime și minime (s-ar putea să nu existe deloc - într-un set infinit; în cazul final - trebuie să existe).
Să ne uităm la încă două exemple. - relație pe un set N:
„Y desparte X", sau "X este un divizor al unui număr Y"(De exemplu,
) este reflexiv și tranzitiv. Să o considerăm pe o mulțime finită de divizori ai numărului 30.
Relația este o relație de ordin parțial (nestrict)
și este reprezentată de următoarea matrice de ordinul 8, care conține 31 de caractere
Circuitul corespunzător cu 8 vârfuri trebuie să conțină 31 de legături. . Cu toate acestea, va fi mai convenabil pentru vizualizare dacă excludem 8
conjunctive-bucle care descriu reflexivitatea relației (elementele diagonale ale matricei) și conjunctive tranzitive, i.e. ligamentele
Dacă există un număr intermediar Z astfel încât
(de exemplu, conjunctivul de atunci). Apoi în schemă
vor rămâne 12 ligamente (Fig. 15); legăturile lipsă sunt implicate „prin tranzitivitate”. Numărul 1 este cel mai mic, iar numărul 30
cele mai mari elemente în . Dacă excludem din numărul 30 și
atunci luați în considerare aceeași ordine parțială pe platou
nu există un element maxim, dar există 3 elemente maxime: 6, 10, 15
Acum să construim același circuit pentru o relație pe un boolean
(mulțimea tuturor submulților) a unei mulțimi de trei elemente
Contine 8 elemente:
Verificați dacă potriviți elementele a, b, c, respectiv, numerele 2, 3, 5 și operațiile de combinare a mulțimilor sunt înmulțirea numerelor corespunzătoare (adică, de exemplu, un submult corespunde
produs 2 5 = 10), atunci matricea de relații va fi exact așa
la fel ca și pentru relație; diagrame ale acestor două relaţii cu cele descrise
abrevierile buclelor și conexivelor tranzitive coincid până la notație (vezi Fig. 16). Cel mai mic element este
Și cel mai mare -
Relații binare R pe un platou AȘi S pe un platou ÎN sunt numite izomorf, dacă între A și B este posibil să se stabilească o corespondență unu-la-unu Г, în care, dacă (i.e.
elementele sunt în relație R), apoi (imagini
aceste elemente sunt în relație S).
Astfel, mulțimile parțial ordonate sunt izomorfe.
Exemplul luat în considerare permite generalizarea.
O relație booleană este o ordine parțială. Dacă
Acestea. o multime de E conţine P elemente, apoi fiecare
corespunde submultimii P-vector dimensional cu
componente, unde este funcția caracteristică
set A/ . Mulțimea tuturor acestor vectori poate fi considerată ca o mulțime de puncte P-spațiu aritmetic dimensional cu coordonatele 0 sau 1, sau, cu alte cuvinte, ca vârfuri P-dimensională
cub unitar, notat cu , i.e. cub cu margini de unitate de lungime. Pentru n = 1, 2, 3 puncte indicate reprezintă, respectiv, capetele unui segment, vârfurile unui pătrat și ale unui cub - de unde și denumirea comună. Pentru /7=4, o reprezentare grafică a acestei relații este în Fig. 17. În apropierea fiecărui vârf al unui cub cu 4 dimensiuni, corespunzătoare
submulțime de mulțime de 4 elemente și de patru dimensiuni
un vector reprezentând funcția caracteristică a acestei submulțimi. Vârfurile corespunzătoare submulților care diferă în prezența exact a unui element sunt conectate între ele.
În Fig. 17, un cub cu patru dimensiuni este reprezentat în așa fel încât pe unul
nivel, elementele incomparabile sunt situate în perechi, conținând același număr de unități în înregistrare (de la 0 la 4), sau, cu alte cuvinte, același număr de elemente în submulțimile reprezentate.
În Fig. 18a, b - alte reprezentări vizuale ale unui cub cu 4 dimensiuni;
în Fig. 18a axa primei variabile OHîndreptat în sus (abatere intenționată de la verticală, astfel încât diferitele margini ale cubului să nu se îmbine):
în acest caz subcubul tridimensional corespunzător X= 0 este situat mai jos, iar pentru X= 1 - mai mare. În fig. 186 aceeași axă OHîndreptat din interiorul cubului către exterior; îi corespunde subcubul interior X= Oh, și cel extern este X = 1.
ÎN 
Fișierul de materiale arată o imagine a unui cub de unitate cu 5 dimensiuni (p. 134).
Proprietățile relațiilor:
1) reflexivitate;
2) simetrie;
3) tranzitivitate.
4) conexiunea.
Atitudine R pe un platou X numit reflectorizant, dacă despre fiecare element al mulţimii X putem spune că este într-o relație R Cu mine insumi: XRx. Dacă relația este reflexivă, atunci există o buclă la fiecare vârf al graficului. Dimpotrivă, un graf al cărui vârf conține o buclă este un graf de relații reflexive.
Exemple de relații reflexive sunt relația „multiplu” pe mulțimea numerelor naturale (fiecare număr este un multiplu al lui însuși), și relația de asemănare a triunghiurilor (fiecare triunghi este similar cu el însuși) și relația de „egalitate” ( fiecare număr este egal cu el însuși), etc.
Există relații care nu au proprietatea reflexivității, de exemplu, relația de perpendicularitate a segmentelor: ab, ba(nu există un singur segment despre care se poate spune că este perpendicular pe sine) . Prin urmare, nu există o singură buclă în graficul acestei relații.
Relația „mai lungă” pentru segmente, „mai mult cu 2” pentru numerele naturale etc. nu are proprietatea reflexivității.
Atitudine R pe un platou X numit antireflex, dacă pentru orice element din set X mereu fals XRx: .
Există relații care nu sunt nici reflexive, nici antireflexive. Un exemplu de astfel de relație este relația „punct X simetric la punct la relativ drept l", definită pe un set de puncte ale planului. Într-adevăr, toate punctele unei linii drepte l sunt simetrice față de ei înșiși și punctele care nu se află pe o linie dreaptă eu ele însele nu sunt simetrice.
Atitudine R pe un platou X numit simetric, dacă este îndeplinită condiţia: din faptul că elementul X este în raport cu elementul y, rezultă că elementul y este in relatie R cu element X:xRyyRx.
Graficul relației simetrice are următoarea caracteristică: împreună cu fiecare săgeată care vine de la X La y, graficul conține o săgeată care pleacă de la y La X(Fig. 35).
Exemple de relații simetrice pot fi următoarele: relația de „paralelism” a segmentelor, relația de „perpendicularitate” a segmentelor, relația de „egalitate” a segmentelor, relația de asemănare a triunghiurilor, relația de „egalitate” a fracții etc.
Există relații care nu au proprietatea de simetrie.
Într-adevăr, dacă segmentul X mai lung decât segmentul la, apoi segmentul la nu poate fi mai lung decât segmentul X. Graficul acestei relații are o particularitate: săgeata care leagă vârfurile este îndreptată doar într-o singură direcție.
Atitudine R numit antisimetric, dacă pentru orice elemente XȘi y din adevăr xRy ar trebui să fie fals yRx: : xRyyRx.
Pe lângă relația „mai lungă”, există și alte relații antisimetrice pe multe segmente. De exemplu, relația „mai mare decât” pentru numere (dacă X Mai mult la, Acea la nu poate fi mai mult X), atitudinea „mai mult” etc.
Există relații care nu au nici proprietatea de simetrie, nici proprietatea de antisimetrie.
Relația R pe o mulțime X numit tranzitiv, dacă din acel element X este in relatie R cu element y,și element y este in relatie R cu element z, rezultă că elementul X este in relatie R cu element z: xRyȘi yRzxRz.
Graficul relației tranzitive din care provine fiecare pereche de săgeți X La y iar din y La z, conține o săgeată care pleacă de la X La z.
Relația „mai lungă” pe un set de segmente are și proprietatea de tranzitivitate: dacă segmentul A mai lung decât segmentul b, segment de linie b mai lung decât segmentul Cu, apoi segmentul A mai lung decât segmentul Cu. Relația de „egalitate” pe un set de segmente are și proprietatea tranzitivității: (a=b, b=c)(a=c).
Sunt relaţii care nu au proprietatea tranzitivităţii. O astfel de relație este, de exemplu, relația de perpendicularitate: dacă un segment A perpendicular pe segment b, și segmentul b perpendicular pe segment Cu, apoi segmentele AȘi Cu nu perpendicular!
Există o altă proprietate a relațiilor, care se numește proprietatea conexiunii, iar o relație care o are se numește conectată.
Atitudine R pe un platou X numit conectat, dacă pentru orice elemente XȘi y din acest set este îndeplinită următoarea condiţie: dacă XȘi y sunt diferite, atunci fie X este in relatie R cu element y, sau element y este in relatie R cu element X. Folosind simboluri, aceasta poate fi scrisă astfel: X yxRy sau yRx.
De exemplu, relația „mai mare decât” pentru numerele naturale are proprietatea conexiunii: pentru orice numere distincte x și y se poate afirma, fie x>y, sau y>x.
Într-un grafic de relații conexe, oricare două vârfuri sunt conectate printr-o săgeată. Afirmația opusă este de asemenea adevărată.
Există relații care nu au proprietatea conexiunii. O astfel de relație, de exemplu, este relația de divizibilitate pe mulțimea numerelor naturale: putem numi astfel de numere x și y oricare ar fi numărul X nu este un divizor al unui număr y, fără număr y nu este un divizor al unui număr X(numerele 17 Și 11 , 3 Și 10 etc.) .
Să ne uităm la câteva exemple. Pe platou X=(1, 2, 4, 8, 12) se dă relaţia „număr”. X multiplu al numărului y" Să construim un grafic al acestei relații și să formulăm proprietățile acesteia.
Se spune că relația de egalitate a fracțiilor este o relație de echivalență.
Atitudine R pe un platou X numit relație de echivalență, dacă are simultan proprietăți de reflexivitate, simetrie și tranzitivitate.
Exemple de relații de echivalență includ: relațiile de egalitate ale figurilor geometrice, relațiile de paralelism ale dreptelor (cu condiția ca liniile care coincid să fie considerate paralele).
În relația de „egalitate a fracțiilor” discutată mai sus, mulțimea Xîmpărțit în trei subseturi: ( ; ; }, {; } , (). Aceste submulțimi nu se intersectează, iar unirea lor coincide cu mulțimea X, adică avem o partiție a setului în clase.
Asa de, dacă o relație de echivalență este dată pe o mulțime X, atunci generează o partiție a acestei mulțimi în submulțimi disjunse pe perechi - clase de echivalență.
Astfel, am stabilit că relația de egalitate pe mulțime
X=( ;; ; ; ; ) corespunde împărțirii acestei mulțimi în clase de echivalență, fiecare dintre acestea fiind formată din fracții egale între ele.
Principiul împărțirii unei mulțimi în clase folosind o relație de echivalență este un principiu important al matematicii. De ce?
În primul rând, echivalent înseamnă echivalent, interschimbabil. Prin urmare, elementele aceleiași clase de echivalență sunt interschimbabile. Astfel, fracțiile care sunt în aceeași clasă de echivalență (; ; ), nu se pot distinge din punctul de vedere al relației de egalitate și al fracțiunii poate fi înlocuit cu altul, de exemplu . Și această înlocuire nu va schimba rezultatul calculelor.
În al doilea rând, deoarece clasa de echivalență conține elemente care nu se pot distinge din punctul de vedere al unei relații, se crede că clasa de echivalență este determinată de oricare dintre reprezentanții săi, i.e. un element arbitrar al clasei. Astfel, orice clasă de fracții egale poate fi specificată prin specificarea oricărei fracții aparținând acestei clase. clasa de echivalență de către un reprezentant vă permite să studiați un set de reprezentanți din clasele de echivalență în loc de toate elementele mulțimii. De exemplu, relația de echivalență „a avea același număr de vârfuri”, definită pe un set de poligoane, generează o partiție a acestui set în clase de triunghiuri, patrulatere, pentagoane etc. proprietățile inerente unei anumite clase sunt luate în considerare pe unul dintre reprezentanții acesteia.
În al treilea rând, partiționarea unui set în clase folosind o relație de echivalență este folosită pentru a introduce concepte noi. De exemplu, conceptul de „mănunchi de linii” poate fi definit ca ceea ce liniile paralele au în comun unele cu altele.
Un alt tip important de relație este relația de ordine. Să luăm în considerare problema X={3, 4, 5, 6, 7, 8, 9, 10 ) relația „au același rest atunci când se împarte la 3 " Această relație generează o partiție a mulțimii Xîn clase: toate numerele vor cădea într-unul singur atunci când sunt împărțite la 3 se dovedește a fi restul 0 (acestea sunt numere 3, 6, 9 ). În al doilea - numere, atunci când sunt împărțite cu 3 restul este 1 (acestea sunt numere 4, 7, 10 ). Al treilea va conține toate numerele care, atunci când sunt împărțite la 3 restul este 2 (acestea sunt numere 5, 8 ). Într-adevăr, mulțimile rezultate nu se intersectează și uniunea lor coincide cu mulțimea X. Prin urmare, relația „au același rest atunci când este împărțită la 3 ", definit pe platou X, este o relație de echivalență.
Pentru a lua un alt exemplu, numeroșii elevi dintr-o clasă pot fi ordonați după înălțime sau vârstă. Rețineți că această relație are proprietăți de antisimetrie și tranzitivitate. Sau toată lumea știe ordinea literelor din alfabet. Este oferit de atitudinea „ar trebui”.
Atitudine R pe un platou X numit relație de ordine strictă, dacă are simultan proprietăți de antisimetrie și tranzitivitate. De exemplu, relatia " X< y».
Dacă relația are proprietăți de reflexivitate, antisimetrie și tranzitivitate, atunci așa va fi relație nestrictă. De exemplu, relatia " Xy».
Exemple de relații de ordine includ: relația „mai mică decât” pe un set de numere naturale, relația „mai scurtă” pe un set de segmente. Dacă o relație de ordine are și proprietatea conexiunii, atunci se spune că este relație de ordine liniară. De exemplu, relația „mai puțin decât” pe mulțimea numerelor naturale.
O multime de X numit ordonat, dacă pe el este specificată o relație de ordine.
De exemplu, multe X={2, 8, 12, 32 ) poate fi comandat folosind relația „mai puțin decât” (Fig. 41), sau acest lucru se poate face folosind relația „multiplu” (Fig. 42). Dar, fiind relații de ordine, relațiile „mai puțin decât” și „multiplu” ordonează mulțimea numerelor naturale în moduri diferite. Relația „mai puțin decât” vă permite să comparați oricare două numere dintr-un set X, dar relația „multiplu” nu are această proprietate. Bine, câteva numere. 8 Și 12 nu are legătură cu relaţia „multiplu”: nu se poate spune că 8 multiplu 12 sau 12 multiplu 8.
Nu trebuie să credem că toate relațiile sunt împărțite în relații de echivalență și relații de ordine. Există un număr mare de relații care nu sunt nici relații de echivalență, nici relații de ordine.
X (\displaystyle X) numit relație de ordin parțial nestrict (relație de ordine, relație reflexivă), Dacă existăO multime de X (\displaystyle X), pe care se introduce relația de ordine parțială, se numește parțial comandat. O relație de ordin parțial non-strict este adesea notată cu ≼ (\displaystyle \preccurlyeq ).
Opțiuni
Relație de ordine parțială R (\displaystyle R) numit ordine liniară, dacă condiția este îndeplinită
∀ x ∀ y (x R y ∨ y R x) (\displaystyle \forall x\forall y(xRy\lor yRx)).O multime de X (\displaystyle X), pe care se introduce o relație de ordine liniară, se numește ordonat liniar, sau lanţ.
Atitudine R (\displaystyle R), satisfacerea numai a condițiilor de reflexivitate și tranzitivitate se numește precomandă sau cvasi-comandă.
Ordine strictă
Dacă condiția de reflexivitate este înlocuită cu condiția de antireflexivitate:
∀ x ¬ (x R x) (\displaystyle \forall x\neg (xRx)),atunci obținem definiția strict, sau ordine parțială antireflexivă(indicat de obicei prin simbolul ≺ (\displaystyle \prec )).
Cometariu. Antireflexivitatea și tranzitivitatea simultană a unei relații implică antisimetrie. Prin urmare relația este relație de ordine strictă dacă şi numai dacă este antireflexiv şi tranzitiv.
În general, dacă R (\displaystyle R) este o relație tranzitivă, antisimetrică, atunci
R ≼ = R ∪ ( (x , x) | x ∈ X ) (\displaystyle R_(\preccurlyeq )=R\cup \((x,x)|x\in X\))- ordine reflexivă R ≺ = R ∖ ( (x , x) | x ∈ X ) (\displaystyle R_(\prec )=R\setminus \((x,x)|x\in X\))- ordine strictă.Exemple
- Pe mulțimea numerelor reale, relațiile „mai mult decât” și „mai puțin decât” sunt relații de ordine strictă, iar „mai mult decât sau egal cu” și „mai mic decât sau egal cu” sunt ne-stricte.
- Relația de divizibilitate pe o mulțime de numere întregi este o relație de ordine nestrictă.
Dimensiunea Dushnik-Miller
Poveste
Semne < {\displaystyle <} Și > (\displaystyle >) inventat
Cuvântul „ordine” este adesea folosit într-o mare varietate de probleme. Ofițerul dă comanda: „Calculează în ordine numerică”, operațiile aritmetice sunt efectuate într-o anumită ordine, sportivii sunt clasați în funcție de înălțime, toți jucătorii de șah de frunte sunt aranjați într-o anumită ordine conform așa-numiților coeficienți Elo (profesor american care a dezvoltat coeficienții sistemului, permițându-vă să țineți cont de toate reușitele și eșecurile jucătorilor), după campionat, toate echipele de fotbal sunt amplasate într-o anumită ordine etc. Există o ordine a operațiunilor la fabricarea unei piese, comanda de cuvinte într-o propoziție (încearcă să înțelegi ce înseamnă propoziția „pe bătrânul” nu am plantat măgarul!”
Prin aranjarea elementelor unui anumit set una după alta, le ordonăm sau stabilim o relație între ele în ordine. Cel mai simplu exemplu este ordinea naturală a numerelor naturale. Naturalitatea sa constă în faptul că, pentru oricare două numere naturale, știm care unul urmează celuilalt sau care este mai mare decât celălalt, deci putem aranja numerele naturale într-o succesiune astfel încât numărul mai mare să fie situat, de exemplu, la dreapta celui mai mic: 1, 2, 3, ... . Desigur, succesiunea de elemente poate fi scrisă în orice direcție, nu doar de la stânga la dreapta. Însuși conceptul de numere naturale conține deja ideea de ordine. Prin stabilirea unui aranjament relativ al elementelor oricărei mulțimi, definim astfel pe ea o relație de ordin binar, care în fiecare caz specific poate avea propriul nume, de exemplu, „a fi mai puțin”, „a fi mai vechi”, „a fi mai vechi”. să fie cuprinse în „, „urmări”, etc. Denumirile simbolice de ordine pot fi, de asemenea, variate, de exemplu, Í etc.
Principala trăsătură distinctivă a unei relații de ordine este aceea că are proprietatea tranzitivității. Deci, dacă avem de-a face cu o succesiune a unor obiecte x 1, x 2, ..., x n,..., ordonat, de exemplu, după relație, apoi din ceea ce se realizează x 1x 2... x n..., ar trebui să urmeze asta pentru orice pereche x i, x j elemente ale acestei secvențe este de asemenea îndeplinită x ix j:
Pentru o pereche de elemente x ijîn graficul relației tragem o săgeată de la vârf x iîn partea de sus x j, adică de la elementul mai mic la cel mai mare.
Graficul relației de ordine poate fi simplificat folosind așa-numita metodă Diagrame Hasse. Diagrama Hasse este construită după cum urmează. Elementele mai mici sunt plasate mai jos, iar cele mai mari sunt plasate mai sus. Deoarece o astfel de regulă singură nu este suficientă pentru reprezentare, sunt trasate linii care arată care dintre cele două elemente este mai mare și care este mai mic decât celălalt. În acest caz, este suficient să desenați numai linii pentru elementele imediat următoare. Exemple de diagrame Hasse sunt prezentate în figură:
Nu trebuie să includeți săgeți într-o diagramă Hasse. Diagrama Hasse poate fi rotită într-un plan, dar nu în mod arbitrar. La întoarcere, este necesar să se mențină poziția relativă (sus - dedesubt) a vârfurilor diagramei:
Atitudine R in abundenta X numit atitudine de ordine strictă, dacă este tranzitivă şi asimetrică.
Se numește o mulțime în care este definită o relație de ordine strictă ordonat. De exemplu, mulțimea numerelor naturale este ordonată după relația „mai puțin decât”. Dar același set este ordonat și de o altă relație - „împărțit în” și „mai mult”.
Graficul relației „mai puțin decât” din mulțimea numerelor naturale poate fi reprezentat ca o rază:
Atitudine R V X numită relație ordine nestrictă (parțială)., dacă este tranzitivă și antisimetrică. Orice relație de ordine non-strict este reflexivă.
Epitetul „parțial” exprimă faptul că poate nu toate elementele unui set sunt comparabile într-un anumit punct de vedere.
Exemple tipice de relații de ordine parțială sunt relațiile „nu mai mare decât”, „nu mai puțin decât” și „nu mai mare decât”. Particula „nu” din numele relațiilor servește pentru a exprima reflexivitatea acestora. Relația „nu mai mult decât” coincide cu relația „mai mică decât sau egală”, iar relația „nu mai puțin” este aceeași cu „mai mare decât sau egală”. În acest sens, se mai numește și ordine parțială nu strictîn ordine. Adesea, o relație de ordine parțială (nestrict) este indicată prin simbolul „”.
Relația de includere Í între submulțimile unei anumite mulțimi este, de asemenea, o ordine parțială. Evident, nu fiecare două subseturi sunt comparabile în acest sens. Figura de mai jos arată ordinea de includere parțială pe mulțime a tuturor submulților din mulțime (1,2,3). Săgețile de pe grafic care ar trebui să fie îndreptate în sus nu sunt afișate.
Sunt apelate seturi în care este dată ordinea parțială parțial comandat, sau pur și simplu ordonat seturi.
Elemente XȘi la se numește set parțial ordonat compara cu noi Dacă Xla sau laX. Altfel nu sunt comparabile.
Se numește o mulțime ordonată în care oricare două elemente sunt comparabile ordonat liniar, iar ordinea este ordine liniară. Ordinea liniară se mai numește și ordine perfectă.
De exemplu, mulțimea tuturor numerelor reale cu ordine naturală, precum și toate submulțimile sale, sunt ordonate liniar.
Se pot comanda obiecte de cea mai variată natură ierarhic. Aici sunt cateva exemple.
Exemplul 1: părțile unei cărți sunt aranjate astfel încât o carte să conțină capitole, capitolele să conțină secțiuni, iar secțiunile să conțină subsecțiuni.
Exemplul 2. Folderele din sistemul de fișiere al computerului sunt imbricate unul în celălalt, formând o structură ramificată.
Exemplul 3. Relația dintre părinți și copii poate fi descrisă ca așa-numita arbore genealogic, care arată cine este al cărui strămoș (sau urmaș).
Lasă pe platou A se dă ordine parțială. Element X numit maxim (minimum) element al mulţimii A, dacă din faptul că Xla(laX), urmează egalitatea X= u. Cu alte cuvinte, elementul X este maxim (minim) dacă pentru orice element la sau nu este adevărat că Xla(laX), sau este executat X=u. Astfel, elementul maxim (minim) este mai mare (mai mic) decât toate elementele distincte de el cu care se află în relație.
Element X numit cel mai mare (cel mai mic), dacă pentru oricine laÎ A efectuat la< х (х< у).
Un set parțial ordonat poate avea mai multe elemente minime și/sau maxime, dar nu poate exista mai mult de un element minim și maxim. Cel mai mic (cel mai mare) element este și minim (maxim), dar invers nu este adevărat. Figura din stânga arată o ordine parțială cu două elemente minime și două maxime, iar în dreapta o ordine parțială cu elementele cele mai mici și cele mai mari:
Într-o mulțime finită parțial ordonată există întotdeauna elemente minime și maxime.
Se numește o mulțime ordonată care are cele mai mari și cele mai mici elemente limitat. Figura prezintă un exemplu de mulțime infinită mărginită. Desigur, este imposibil să descrii un set infinit pe o pagină finită, dar poți arăta principiul construcției acestuia. Aici buclele din apropierea vârfurilor nu sunt afișate pentru a simplifica desenul. Din același motiv, arcele care asigură afișarea proprietății tranzitivității nu sunt afișate. Cu alte cuvinte, figura prezintă diagrama Hasse a relației de ordine.
Seturile infinite pot să nu aibă elemente maxime sau minime sau ambele. De exemplu, mulțimea numerelor naturale (1,2, 3, ...) are cel mai mic element de 1, dar nu maxim. Mulțimea tuturor numerelor reale cu ordine naturală nu are nici cel mai mic, nici cel mai mare element. Cu toate acestea, subsetul său este format din toate numerele X< 5, are cel mai mare element (numărul 5), dar nu îl are pe cel mai mic.
