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ă

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:

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

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ă.

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ă provenită din 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, nici 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 sunt 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. Pe platoul de filmare 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, mulți elevi dintr-o clasă pot fi sortaț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 non-strictă. 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.

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 elevul 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 ordin nestrict 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 întâ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?