Relații ordonate. Relația de comandă

Cuvântul „ordine” este adesea folosit într-o varietate de probleme. Ofițerul dă comanda: „După ordinea numerelor, calculează”, 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 și ordinea 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 înțeles: înseamnă ce element dintr-o mulțime dată 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 relație de 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 există săgeți duble pe grafic. 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 strictă ordine.

Relație nestrictă

Opusul relației „mai puțin decât” în mulțimea numerelor reale este relația „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 non-strictă, 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ție de ordine strictă, spre deosebire de un grafic de relație de ordine strictă, are bucle la fiecare vârf.

În fig. 6 (§ 6 din acest 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 spun 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 elementele 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.

Relația de echivalență. Legătura dintre relația de echivalență și împărțirea unei mulțimi în clase

Definiție. Atitudine R pe un platou X se numește relație de echivalență dacă este reflexivă, simetrică și tranzitivă.

Exemplu. Luați în considerare relația " X colega de clasa la„pe mulți studenți ai Facultății de Educație. Are următoarele proprietăți:

1) reflexivitate, deoarece fiecare elev este propriul său coleg de clasă;

2) simetrie, deoarece dacă un student X la, apoi studentul la este coleg de clasă cu un elev X;

3) tranzitivitatea, deoarece dacă un student X- colega de clasa la, și studentul la- colega de clasa z, apoi studentul X va fi colegul de clasă al elevului z.

Astfel, această relație are proprietăți de reflexivitate, simetrie și tranzitivitate și, prin urmare, este o relație de echivalență. În același timp, mulți studenți ai Facultății de Educație pot fi împărțiți în subseturi formate din studenți care studiază în același curs. Obținem 5 subseturi.

Relațiile de echivalență sunt și, de exemplu, relația de paralelism a liniilor, relația de egalitate a figurilor. Fiecare astfel de relație este asociată cu partiționarea setului în clase.

Teorema. Dacă pe platou X dată fiind o relație de echivalență, apoi împarte această mulțime în submulțimi disjunse în perechi (clase de echivalență).

Afirmația inversă este de asemenea adevărată: dacă există vreo relație definită pe mulțime X, generează o partiție a acestui set în clase, atunci este o relație de echivalență.

Exemplu. Pe platou X= (1; 2; 3; 4; 5; 6; 7; 8) este specificată relația „au același rest când se împarte la 3”. Este o relație de echivalență?

Să construim un grafic al acestei relații: (independent)

Această relație are proprietăți de reflexivitate, simetrie și tranzitivitate, prin urmare, este o relație de echivalență și împarte mulțimea X la clase de echivalenţă. În fiecare clasă de echivalență vor exista numere care, împărțite la 3, dau același rest: X 1 = {3; 6}, X 2 = {1; 4; 7}, X 3 = {2; 5; 8}.

Se crede că clasa de echivalență este determinată de oricare dintre reprezentanții săi, i.e. un element arbitrar al acestei clase. Astfel, o clasă de fracții egale poate fi specificată prin specificarea oricărei fracții aparținând acestei clase.

În cursul inițial de matematică se întâlnesc și relații de echivalență, de exemplu, „expresii XȘi la au aceleași valori numerice”, „figura X egal cu cifra la».

Definiție. Atitudine R pe un platou X se numeste relatie de ordine daca este tranzitiva si asimetrica sau antisimetrica.

Definiție. Atitudine R pe un platou X se numește relație de ordine strictă dacă este tranzitivă și asimetrică.

Exemple relații de ordine strictă: „mai mult” pe mulțimea numerelor naturale, „mai mare” pe mulțimea oamenilor etc.

Definiție. Atitudine R pe un platou X se numește relație de ordine non-strict dacă este tranzitivă și antisimetrică.

Exemple relații de ordin nestrict: „nu mai mult” pe mulțimea numerelor reale, „fii divizor” pe mulțimea numerelor naturale etc.

Definiție. O multime de X se numește ordonat dacă pe el este specificată o relație de ordine.

Exemplu. Pe platou X= (1; 2; 3; 4; 5) sunt date două relații: „ X £ la" Și " X- separator la».

Ambele relații au proprietăți de reflexivitate, antisimetrie și tranzitivitate (construiți grafice și verificați singur proprietățile), adică. sunt relaţii de ordine non-strict. Dar prima relație are proprietatea conexiunii, în timp ce a doua nu.

Definiție. Relația de comandă R pe un platou X se numește relație de ordin liniar dacă are proprietatea conexiunii.

În școala elementară sunt studiate multe relații de ordine. Deja în clasa I există relații „mai puțin”, „mai mult” pe setul de numere naturale, „mai scurt”, „mai lung” pe setul de segmente etc.

Întrebări de control

1. Definiți o relație binară pe o mulțime X.

2. Cum se scrie o afirmație conform căreia elementele XȘi la sunt într-o relație R?

3. Enumeraţi modalităţi de definire a relaţiilor.

4. Formulați proprietățile pe care le pot avea relațiile. Cum sunt reflectate aceste proprietăți în grafic?

5. Ce proprietăți trebuie să aibă o relație pentru ca aceasta să fie o relație de echivalență?

6. Cum este relația de echivalență legată de împărțirea unei mulțimi în clase?

7. Ce proprietăți trebuie să aibă o relație pentru ca aceasta să fie o relație 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

Fie R o relație binară pe mulțimea A.

DEFINIȚIE. O relație binară R pe o mulțime A se numește relație de ordin pe A sau ordin pe A dacă este tranzitivă și antisimetrică.

DEFINIȚIE. O relație de ordin R pe o mulțime A se numește nestrict dacă este reflexivă pe A, adică pentru fiecare dintre A.

O relație de ordine R se numește strictă (pe A) dacă este antireflexivă pe A, adică pentru oricare dintre A. Totuși, din antireflexivitatea relației tranzitive R rezultă că este antisimetrică. Prin urmare, poate fi dată următoarea definiție echivalentă.

DEFINIȚIE. O relație binară R pe o mulțime A se numește ordine strictă pe A dacă este tranzitivă și antireflexivă pe A.

Exemple. 1. Fie multimea tuturor submultimii multimii M. Relatia de includere pe o multime este o relatie de ordine nestrict.

2. Relațiile pe mulțimea numerelor reale sunt, respectiv, relații de ordine strictă și nestrict.

3. Relația de divizibilitate în mulțimea numerelor naturale este o relație de ordine nestrict.

DEFINIȚIE. O relație binară R pe o mulțime A se numește relație de preordine sau preordine pe A dacă este reflexivă și tranzitivă.

Exemple. 1. Relația de divizibilitate în mulțimea numerelor întregi nu este o ordine. Cu toate acestea, este reflexiv și tranzitiv, ceea ce înseamnă că este o precomandă.

2. Relația de implicare logică este o preordonare a setului de formule logice propoziționale.

Ordine liniară. Un caz special important de ordine este ordinea liniară.

DEFINIȚIE. O relație de ordine pe o mulțime se numește relație de ordine liniară sau ordine liniară pe dacă este conectată pe , adică pentru orice x, y din A

O relație de ordine care nu este liniară este de obicei numită relație de ordine parțială sau ordine parțială.

Exemple. 1. Relația „mai mică decât” pe mulțimea numerelor reale este o relație de ordin liniar.

2. Relația de ordine adoptată în dicționarele de limbă rusă se numește lexicografic. Ordinea lexicografică pe setul de cuvinte în limba rusă este o ordine liniară.

Cuvântul „ordine” este adesea folosit într-o mare varietate de probleme. Ofițerul dă comanda: „Calculați î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 în funcție de așa-numiții 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 de operațiuni la fabricarea unei piese, ordinea cuvintelor într-o propoziție (încercați să înțelegeți ce înseamnă propoziția „pe bătrânul” nu am plantat măgarul!”

Prin aranjarea elementelor unui anumit set unul după altul, 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”. fi conținute în „, „urmează”, 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 de 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.