Teoria comenzii

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Teoria ordinelor este o ramură a matematicii care studiază anumite tipuri de relații binare , numite ordine și preordini, care induc pe suportul lor seturi o structură care amintește ideea intuitivă a elementelor de ordonare .

Introducere

Sortarea mai multor obiecte într-o secvență este o operație pe care o facem în fiecare zi, atât atunci când ne organizăm angajamentele zilnice (oferindu-le o ordine temporală), fie când decidem ce acțiune să luăm față de altul (ordonându-le după importanță), sau pur și simplu când punem cărțile pe rafturi (sortându-le de exemplu după an sau autor).

O ordonare între obiecte ne-a fost învățată încă din școala elementară : este ordonarea obișnuită între numerele naturale , care introduce un prim exemplu de mărime. Această ordonare este apoi extinsă la numerele întregi și, cu unele dispozitive teoretice, la numerele reale . Setul de numere tratate în mod normal este astfel complet descris. Un alt exemplu similar este așa-numita ordine lexicografică , care ne permite să scriem cuvintele unui vocabular într-o ordine precisă.

Exemple de acest tip au toate caracteristici comune:

  • nu există elemente distincte „în aceeași poziție”
  • ordinea dată este rațională (sau tranzitivă ): nu există elemente care, într-un anumit sens, inversează ordinea (pentru o explicație precisă vezi tranzitivitatea ).

În abstractizarea teoretică, o ordonare care satisface aceste proprietăți se numește relație de ordine (unde de data aceasta cuvântul „ordine” are un sens precis, nu doar cel intuitiv folosit până acum). Dacă considerăm în continuare că aceste exemple satisfac proprietatea suplimentară că nu există niciun element care să fie lăsat în afara ordinii, atunci acestea sunt ordine totale .

Cu toate acestea, nu există doar mulțimi care pot fi descrise atât de exact: în mulțimi se poate da o ordine naturală, definită de relația de a fi un subset . Se știe că această relație nu îndeplinește ultima proprietate menționată mai sus, adică există perechi de mulțimi pentru care nu este posibil să se judece cu privire la care se află înainte și care după: atunci această relație se numește parțială comandă .

Înainte cu clasificarea, ne putem gândi la un coș de mărfuri , comparat în funcție de prețul lor: această relație este totală (fiecare bun are un preț și acest preț poate fi întotdeauna legat de orice alt preț) și tranzitiv (în sensul de mai sus ), dar nu este adevărat că dacă două bunuri au același preț (adică, în terminologia de mai sus, acestea ocupă aceeași poziție în ordine) coincid: un set care îndeplinește aceste proprietăți se numește pre-comandă .

În cele din urmă, rețineți că, în unele exemple de mai sus, pentru a comanda un set, ne-am bazat pe ordine deja date (în ultimul exemplu, cel al numerelor), asocierea fiecărui element cu un număr și ordonarea elementelor în funcție de modul în care au fost ordonate numerele corespondenți: o operațiune de acest tip, care vă permite să definiți o ordonare prin intermediul unei funcții către un set deja dotat cu ordine, se numește imersiune în ordine .

Tratament formal

Teoria ordinelor studiază relații binare particulare pe același set , dotate cu proprietăți particulare ale „regularității”. Împarte subiectul studiilor sale în două clase mari, chiar dacă una poate fi într-un anumit sens transformată în cealaltă. Aceste două clase sunt comenzi și precomenzi.

Ordin

Pictogramă lupă mgx2.svg Același subiect în detaliu: Relația de comandă .

O relație binară pe un platou (adică un subset al produsului cartezian ) se spune o ordine dacă îndeplinește aceste proprietăți pentru fiecare în :

  • ( reflexivitate )
  • de sine Și , asa de ( antisimetrie )
  • de sine Și , asa de ( tranzitivitate )

se spune un set comandat .

Pre-comanda

Pictogramă lupă mgx2.svg Același subiect în detaliu: precomandă .

O relație binară pe un platou (adică un subset al produsului cartezian ) se spune că este o precomandă dacă îndeplinește aceste proprietăți pentru fiecare în :

  • ( reflexivitate )
  • de sine Și , asa de ( tranzitivitate )

se numește un întreg preordonat .

Comentarii

  • Datorită analogiei lor cu ordonarea numerică clasică (de care sunt de fapt o generalizare) relațiile de ordine și preordine sunt universal denotate de simbolul obișnuit sau cu simboluri similare acestuia, cum ar fi sau .
  • Dacă în definiția comenzii (resp. Pre-comanda) vom înlocui proprietatea reflexiv cu anti - una reflexivă, obținem ceea ce se numește o ordine strictă (resp. Închide precomandă), indicat pentru motive evidente cu . Uneori definițiile care includ proprietatea reflexivă se spune că sunt largi (adică ordine largă, preordine largă) dacă poate exista ambiguitate. Deși cele două definiții sunt distincte, este ușor să treceți de la o ordine largă la una îngustă prin poziționare dacă și numai dacă Și , și invers, prin plasare dacă și numai dacă sau .

Proprietăți suplimentare

Totalitate

Definiția ordinii (respectiv precomanda) nu trebuie să precizeze care sau câte elemente satisfac proprietățile. Dacă în plus, ai nevoie și de asta

  • pentru fiecare în Și sau

atunci se obține o ordine totală (respectiv precomandă totală ) sau liniară .

Se spune că două elemente nu sunt „comparabile” dacă niciuna dintre cele două relații nu se menține. Aceasta înseamnă că într-o ordine totală fiecare pereche de elemente este comparabilă. Dacă o comandă nu este totală, atunci se spune că este parțială . Seturile partial ordonate sunt , de asemenea , numite „poset“, un acronim din limba engleză P artially O rdered Set.

Un exemplu imediat al unei relații non-totale este, așa cum s-a menționat mai sus, cel al subseturilor: pentru cele două seturi Și nu este valabil nici asta nici asta . Un alt exemplu este dat de relația de divizibilitate dintre numerele naturale.

Reprezentare grafică

Pictogramă lupă mgx2.svg Același subiect în detaliu: Rețeaua de divizibilitate .
Rețeaua divizibilității 60.svg

O ordine poate fi vizualizată grafic prin intermediul unei construcții realizate de Helmut Hasse , care identifică elementele ca vârfuri ale unui grafic și conectează două vârfuri Și unul deasupra celuilalt dacă și numai dacă și nu există astfel încât .

Această construcție este foarte convenabilă deoarece, comparativ cu un grafic în care fiecare pereche de elemente în relație este conectată, multe redundanțe sunt eliminate. De exemplu, gândiți-vă la toate arcele care într-o ordine mare ar conecta un element cu el însuși.

Aceeași construcție este potrivită pentru precomenzi, având grijă să plasați elemente astfel încât Și la aceeasi inaltime.

Este evident că singura reprezentare grafică a unei ordine totale este cea a unei singure linii, finite sau infinite, care leagă diferitele vârfuri unul după altul. Acesta este și motivul pentru care un set complet ordonat este numit și lanț .

Construirea unei comenzi dintr-o precomandă

Ordinele sunt adevăratele elemente centrale ale teoriei, având în vedere o precomandă este întotdeauna posibil să faceți referire la o comandă conectată, aplicând următoarea construcție:

Relația este definită , care relatează două elemente dacă și numai dacă Și ; este o relație de echivalență . Setul de coeficient este apoi luat în considerare și este dotat cu relația

.

Cuplul este un set ordonat. Intr-adevar Și implica Și , acesta este . Dar apoi Și prin urmare, se află în aceeași clasă de echivalență .

Elemente particulare în cadrul unei comenzi

Un element într-un întreg ordonat se spune:

  • minimum (resp. maxim ) dacă pentru fiecare în da ai (resp. ),
  • minim dacă singurul în astfel încât Și la fel,
  • maxim dacă este singurul în astfel încât Și la fel,
  • majorant (resp. minoritate ) al unui subset de sine (resp. ) pentru fiecare în ,
  • limita superioară (respectiv limita inferioară ) a subsetului dacă este minimul setului de majorități (respectiv maximul minorilor).

Deși este posibil ca minimul și maximul să nu existe, un set poate avea mai multe elemente minime sau maxime. Chiar și același element ar putea fi minim și maxim. Cele două definiții coincid în cazul unei comenzi totale. Se spune că un subset cu major și minor este limitat .

Dualitate

Pictogramă lupă mgx2.svg Același subiect în detaliu: Dualitatea (teoria ordinelor) .

În paragrafele anterioare vedem că multe definiții similare pot fi obținute pur și simplu prin inversarea direcției inegalității. Această considerație rezultă dintr-un principiu general, numit Principiul Dualității :

Dacă o instrucțiune este valabilă pentru orice set parțial ordonat, atunci instrucțiunea sa duală, obținută prin schimbarea fiecărei inegalități și posibil inversarea fiecărui termen cu simetricitatea sa, este încă valabilă pentru orice set parțial ordonat .

În special, dualul unui set ordonat , identificat cu , este același întreg, totuși, caracterizat de relație

în dacă și numai dacă în .

Grafic, diagrama Hasse a unui ordin dual se obține pur și simplu inversând diagrama ordinii inițiale.

Importanța principiului dualității este văzută mai ales în utilizarea continuă a simbolului , fără a fi nevoie să oferiți o definiție precisă.

Funcții între comenzi

Pictogramă lupă mgx2.svg Același subiect în detaliu: funcția monotonă .

În acest moment este firesc să ne gândim să oferim și funcții între diferite seturi ordonate care își păstrează ordonanțele respective: aceste funcții sunt numite monotone sau să nu se utilizeze un termen deja comun cu analiza matematică , conservarea ordinii și, cu precizie, satisfac următoarea proprietate:

de sine asa de ,

acordând atenție primelor Se referă la elemente ale domeniului , în timp ce al doilea element al codomainului , prin urmare, sunt două sisteme distincte. Pentru a fi mai precis, ar fi mai bine să folosiți două simboluri diferite, de exemplu Și .

Dacă este adevărat și opusul, acesta este implica , atunci funcția se numește o imersiune de ordine și reprezintă o metodă de „reprezentare” a unui set ordonat în cadrul altui sau, de asemenea, așa cum s-a spus în introducere, pentru a defini o ordine în domeniu, plasând condiția de mai sus menționată ca definiție.

O imersie de ordin surjectiv se numește izomorfism de ordine . Importanța sa este evidentă, deoarece reprezintă un izomorfism între cele două structuri în sensul algebric al termenului.

Dual, un antiton este definit ca o funcție astfel încât

implica .

O ușoară slăbire a conceptului de izomorfism de ordine este dată de conexiunea Galois dintre două mulțimi ordonate Și , format din două funcții monotone Și astfel încât pentru fiecare în , în

dacă și numai dacă .

Facilități mai bogate

Majoritatea structurilor studiate în teoria ordinii au și proprietăți suplimentare. Multe dintre aceste proprietăți suplimentare reflectă un fel de completitudine :

  • O ordine bună este o ordine totală cu proprietatea că fiecare subset ne- gol are un element minim
  • O ordine parțială bună este o ordine astfel încât fiecare subset ne-gol să aibă un număr finit de elemente minime
  • Un set direct este un set preordonat astfel încât pentru fiecare pereche de elemente Și în , există un al treilea element care satisface Și .
  • Un set ordonat este local finit dacă orice interval este finit.
  • O rețea este un set ordonat astfel încât fiecare subset finit să aibă limită inferioară și limită superioară
  • O rețea este completă dacă fiecare dintre subsetul său are limita inferioară și superioară

Pornind de la o rețea, pe ea pot fi definite două operații binare :

Având în vedere aceste două operații, o rețea devine o structură algebrică . Se arată că aceste operații satisfac proprietăți particulare. Dimpotrivă, având în vedere o structură algebrică cu două operații cu acele proprietăți, acel set este, de asemenea, o rețea. Dacă cele două operații satisfac o proprietate de distributivitate , atunci se spune că rețeaua este distributivă .

Dacă este necesară limitarea acestei structuri, pot fi definite operații suplimentare, numite 0 și 1 extremele inferioare și superioare:

  • O algebră Heyting este o rețea distributivă limitată astfel încât pentru fiecare există un element , numit pseudocomplementul lui respect , care este elementul maxim astfel încât .
  • O rețea este completată dacă pentru fiecare există un element , numit complement de , astfel încât
Și
  • O algebră booleană este o rețea distributivă complementară sau chiar o algebră Heyting astfel încât pseudocomplementul este complementul său.

Relațiile cu alte domenii ale matematicii

Există multe domenii de studiu în matematică, cu care relația teoriei ordinelor este foarte fructuoasă și mai ales bidirecțională. Pe lângă algebra abstractă , menționată deja mai sus în studiul rețelelor, putem numi:

  • topologia : doar pentru a numi un exemplu, topologia Alexandrov a unei pre-comenzi este astfel încât seturile sale deschise sunt exact seturile „ închise în sus”, adică seturile de tip (într-un anumit sens dreapta " jumătăți de linie ") ca în .

Dimpotrivă, având în vedere un spațiu topologic , se poate defini o precomandă , numită o precomandă de specializare , dată de

dacă și numai dacă ,

unde este reprezintă închiderea topologică a singletului . Această precomandă este o comandă dacă și numai dacă spațiul este T0 . A se vedea, de asemenea, Topologia topologică și Topologia Scott .

Fiecare mulțime ordonată sau preordonată este, de asemenea, o categorie mică , în care obiectele sunt elementele mulțimii, iar morfismele sunt „săgețile” care indică din la de sine . O conexiune Galois în acest sens este doar o pereche de functori adăugați la categoriile relative.

Alte proiecte

Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică