Set parțial comandat

O mulțime parțial ordonată este un concept matematic care formalizează ideile intuitive de ordonare, aranjarea elementelor într-o anumită succesiune. Informal, o mulțime este ordonată parțial dacă este specificat ce elemente urmează după care (care elemente sunt mai mari decât care). În general, se poate dovedi că unele perechi de elemente nu sunt legate prin relația „ urmează ” .

Ca exemplu abstract, putem da o colecție de submulțimi ale unei mulțimi de trei elemente ( booleanul unei mulțimi date), ordonate după relația de includere. $\{x,y,z\}$

Definiție și exemple

Relația de ordine , sau ordinea parțială , pe o mulțime este o relație binară pe(definită de o mulțime) care îndeplinește următoarele condiții [1] : $M$ $\varphi$ $M$ $R_{{\varphi }}\subset M\time M$

Reflexivitate : $\forall a\;(a\varphi a)$
Tranzitivitate : $\forall a,b,c\;(a\varphi b)\wedge (b\varphi c)\Rightarrow a\varphi c$
Antisimetrie : $\forall a,b\;(a\varphi b)\wedge (b\varphi a)\Rightarrow a=b$

Mulțimea pe care este dată relația de ordine parțială se numește parțial ordonată . Pentru a fi destul de precis [2] , atunci o mulțime parțial ordonată este o pereche , unde este o mulțime și este o relație de ordine parțială pe . $M$ $\langle M,\varphi \rangle$ $M$ $\varphi$ $M$

Dimensiunea unei mulțimi parțial ordonate este egală cu numărul maxim al mulțimii de ordine liniare ( ). Această definiție se bazează pe proprietatea de extensibilitate a unui ordin parțial la unul liniar. $\langle M,\varphi \rangle$ $<_{i)$ $i\în eu$

Terminologie și notație

Relația de ordin parțial este de obicei notă cu simbolul , prin analogie cu relația „mai mică sau egală cu” de pe mulțimea numerelor reale . Mai mult, dacă , atunci spunem că elementul nu depășește , sau că este subordonat . $\leqslant$ $a\leqslant b$ $A$ $b$ $A$ $b$

Dacă și , atunci ei scriu și spun că este mai mic decât , sau că este strict subordonat . $a\leqslant b$ $a \neq b$ $a<b$ $A$ $b$ $A$ $b$

Uneori, pentru a distinge o ordine arbitrară pe o anumită mulțime de relația cunoscută „mai mică sau egală” pe mulțimea numerelor reale, simbolurile speciale și sunt folosite în locul și respectiv . $\leqslant$ $<$ $\preccurlyeq$ $\prec$

Ordine strictă și nestrictă

O relație care satisface condițiile de reflexivitate, tranzitivitate și antisimetrie se mai numește și ordine nonstrict sau reflexiv . Dacă condiția de reflexivitate este înlocuită cu condiția de antireflexivitate (atunci proprietatea de antisimetrie este înlocuită cu asimetrie):

\forall a\;\neg (a\varphi a)

atunci obținem definiția unei ordini stricte sau antireflexive .

Dacă este o ordine nestrictă pe mulțime , atunci relația , definită ca: $\leqslant$ $M$ $<$

a<b\;{\overset {{\mathrm {def}}}{\Longleftrightarrow }}\;(a\leqslant b)\wedge (a\neq b)

este un ordin strict pe . În schimb, dacă este o ordine strictă, atunci relația este definită ca $M$ $<$ $\leqslant$

a\leqslant b\;{\overset {{\mathrm {def}}}{\Longleftrightarrow }}\;(a<b)\vee (a=b)

este o ordine nestrictă.

Prin urmare, este la fel dacă se specifică o comandă nestrictă sau o ordine strictă pe set . Rezultatul este aceeași structură. Diferența este doar în terminologie și notație.

Interval

Pentru un interval închis [ a , b ] este o mulțime de elemente x care satisfac inegalitatea (adică și ). Intervalul conține cel puțin elementele a și b . $a\leqslant b$ $a\leqslant x\leqslant b$ $a\leqslant x$ $x\leqslant b$

Dacă folosim inegalitatea strictă „<”, obținem un interval deschis ( a , b ), o mulțime de elemente x care satisfac inegalitatea a < x < b (adică a < x și x < b ). Un interval deschis poate fi gol chiar dacă a < b . De exemplu, intervalul deschis (1,2) pentru numere întregi este gol deoarece nu există numere întregi i astfel încât 1 < i < 2.

Uneori definiția este extinsă pentru a permite a > b . În acest caz, intervalul este gol.

Intervalele semideschise [ a , b ) și ( a , b ] sunt definite într-un mod similar.

Un poset este local finit dacă fiecare interval este finit. De exemplu, numerele întregi sunt local finite în ordinea lor naturală. Ordinea lexicografică pe produsul direct ℕ×ℕ nu este local finită deoarece, de exemplu, . $(1,2)\leqslant (1,3)\leqslant (1,4)\leqslant (1,5)\leqslant \ldots \leqslant (2,1)$

Conceptul de interval în posete nu trebuie confundat cu o anumită clasă de posete cunoscută sub numele de ordine de interval .

Exemple

Mulțimea numerelor reale este ordonată parțial în funcție de relația „mai mică sau egală cu” - . $\mathbb {R}$ $\leqslant$

Fie mulțimea tuturor funcțiilor cu valori reale definite pe segmentul , adică funcțiile formei $M$ $[a,b]$

f\colon [a,b]\to {\mathbb {R}}

Să introducem relația de ordine pe după cum urmează: , dacă inegalitatea este valabilă pentru toți . Evident, relația introdusă este într-adevăr o relație de ordin parțial. $\leqslant$ $M$ $f\leqslant g$ $x\în[a,b]$ $f(x)\leqslant g(x)$

Să fie niște set. Mulțimea tuturor submulților (așa-numita booleană ) este parțial ordonată prin includere . $M$ ${\mathcal {P}}(M)$ $M$ $M\subseteq N$

Mulțimea tuturor numerelor naturale este parțial ordonată după relația de divizibilitate . $\mathbb {N}$ $m\mid n$

Definiții înrudite

Elemente incomparabile

Dacă și sunt numere reale , atunci doar una dintre următoarele relații este valabilă: $A$ $b$

a<b,\qquad a=b,\qquad b<a

Dacă și sunt elemente ale unei mulțimi arbitrare parțial ordonate, atunci există o a patra posibilitate logică: niciuna dintre cele trei relații de mai sus nu este satisfăcută. În acest caz, elementele și sunt numite incomparabile . De exemplu, dacă este setul de funcții cu valori reale de pe segment , atunci elementele și vor fi incomparabile. Posibilitatea existenței unor elemente incomparabile explică sensul termenului „mulțime parțial ordonată” . $A$ $b$ $A$ $b$ $M$ $[0,1]$ $f(x) = x$ $g(x)=1-x$

Elemente minime/maximale și minime/mai mari

Datorită faptului că într-o mulțime parțial ordonată pot exista perechi de elemente incomparabile, se introduc două definiții diferite: elementul minim și cel mai mic element .

Se spune că un element este minim dacă elementul nu există . Cu alte cuvinte, este elementul minim dacă pentru orice element fie , fie , sau și sunt incomparabile. Un element este numit cel mai mic dacă pentru orice element inegalitatea este valabilă . Evident, orice element cel mai mic este, de asemenea, minim, dar invers nu este adevărat în cazul general: elementul minim poate să nu fie cel mai mic dacă există elemente care nu sunt comparabile cu . $a \în M$ $b<a$ $A$ $b\în M$ $b>a$ $b=a$ $b$ $A$ $A$ $b\în M$ $b\geqslant a$ $A$ $b$ $A$

Evident, dacă există un element cel mai mic într-un set, atunci este unic. Dar pot exista mai multe elemente minime. Ca exemplu, luați în considerare mulțimea numerelor naturale fără unitate, ordonate după relația de divizibilitate . Aici, elementele minime vor fi numere prime , dar cel mai mic element nu există. ${\mathbb {N}}\setminus \{1\}=\{2,3,\ldots \}$ $\mid$

Conceptele de maxim și mai mare elemente sunt introduse în mod similar.

Fețe de sus și de jos

Fie o submulțime a unei mulțimi parțial ordonate . Un element se numește limită superioară dacă niciun element nu depășește . Conceptul de limita inferioară a mulțimii este introdus în mod similar . $A$ $\langle M,\leqslant \rangle$ $u\în M$ $A$ $a\în A$ $u$ $A$

Orice element mai mare decât o față de sus va fi, de asemenea, o față de sus . Și orice element mai mic decât un infimum va fi, de asemenea, un infimum . Aceste considerații conduc la introducerea conceptelor de limită superioară minimă și limită inferioară cea mai mare . $A$ $A$ $A$ $A$

Seturile superioare și inferioare

Pentru un element dintr-o mulțime parțial ordonată, mulțimea superioară este mulțimea tuturor elementelor precedate de ( ). $m$ $\langle M,\leqslant \rangle$ $M\în sus m$ $m$ $\{x\in M\mid m\leqslant x\}$

Mulțimea inferioară este definită dual ca mulțimea tuturor elementelor premergătoare celei date: . $M\downarrow m{\stackrel {{\mathrm {def}}}{=}}\{x\in M\mid x\leqslant m\}$

Condiții de pauză

Se spune că o mulțime parțial ordonată satisface condiția de terminare a lanțului strict crescător dacă nu există o secvență infinită strict crescătoare . Această condiție este echivalentă cu condiția de stabilizare pentru lanțuri care nu cresc strict : orice secvență care nu crește strict a elementelor sale se stabilizează. Adică pentru orice succesiune a formei $M$ $(a_{i}\,<\,a_{i+1})$ $(a_{i}\,\leqslant \,a_{i+1})$

a_{1}\,\leqslant \,a_{2}\,\leqslant \,a_{3}\,\leqslant \,\cdots

există un firesc astfel încât $n,$

a_{n}=a_{{n+1}}=a_{{n+2}}=\cdots .

Definit într-un mod similar pentru lanțurile descrescătoare, atunci în mod evident satisface condiția de terminare a lanțului descendent dacă și numai dacă se stabilizează orice secvență nestrict descrescătoare a elementelor sale. Aceste concepte sunt adesea folosite în algebra generală - vezi, de exemplu, inelul Noetherian , inelul artinian . $M$

Tipuri speciale de seturi parțial ordonate

Seturi ordonate liniar

Fie un set parțial ordonat. Dacă în oricare două elemente sunt comparabile, atunci mulțimea se numește ordonată liniar . O mulțime ordonată liniar se mai numește și o mulțime perfect ordonată sau, pur și simplu, o mulțime ordonată [3] . Astfel, într-o mulțime ordonată liniar, pentru oricare două elemente și , una și numai una dintre relații este valabilă: fie , fie , sau . $\langle M,\leqslant \rangle$ $M$ $M$ $A$ $b$ $a<b$ $a=b$ $b<a$

De asemenea, orice submulțime ordonată liniar a unei mulțimi parțial ordonate se numește lanț , adică un lanț dintr-o mulțime parțial ordonată este submulțimea sa în care oricare două elemente sunt comparabile. $\langle M, \leqslant \rangle$

Dintre exemplele de mulțimi parțial ordonate de mai sus, numai mulțimea numerelor reale este ordonată liniar. Mulțimea de funcții cu valori reale de pe interval (în condiția ), boolean (pentru ), numere naturale cu o relație de divizibilitate nu sunt ordonate liniar. $[a,b]$ $a<b$ ${\mathcal {P}}(M)$ $|M|\geqslant 2$

Într-o mulțime ordonată liniar, conceptele de minim și minim, precum și de cel mai mare și maxim, sunt aceleași.

Seturi bine ordonate

O mulțime ordonată liniar se numește bine ordonată dacă fiecare dintre submulțimile sale nevide are cel puțin element [4] . O astfel de ordine pe o mulţime se numeşte ordine completă , într - un context în care nu poate fi confundată cu o ordine completă în sensul mulţimilor complete parţial ordonate .

Un exemplu clasic de mulțime bine ordonată este mulțimea numerelor naturale . Afirmația că orice submulțime nevidă conține cel mai mic element este echivalentă cu principiul inducției matematice . Un exemplu de mulțime ordonată liniar, dar nu bine ordonată este mulțimea ordonată natural de numere nenegative . Într-adevăr, submulțimea sa nu are cel mai mic element. $\mathbb {N}$ $\mathbb {N}$ ${\mathbb {R}}_{{+}}=\{x:x\geqslant 0\}$ $\{x:x>1\}$

Mulțimile bine ordonate joacă un rol excepțional de important în teoria generală a mulțimilor .

Pozetul complet

Un poset complet este un poset care are un fund — singurul element care precede orice alt element și că fiecare subset direcționat are o limită superioară exactă [5] . În calculul λ și în informatică sunt folosite mulțimi complete parțial ordonate , în special, pe ele este introdusă topologia Scott , pe baza căreia se construiește un model consistent de calcul λ și semantică denotațională . Un caz special al unui set complet ordonat parțial este o rețea completă - dacă orice submulțime, nu neapărat direcționată, are o limită superioară minimă, atunci se dovedește a fi o rețea completă.

O mulțime ordonată este o mulțime completă parțial ordonată dacă și numai dacă fiecare funcție monotonă în raport cu ordinea ( ) are cel puțin un punct fix : . $M$ $f\colon M\rightarrow M$ $a\leqslant b\Rightarrow f(a)\leqslant f(b)$ $\exists _{{x\in M}}f(x)=x$

Orice set poate fi transformat într-unul complet parțial ordonat prin extragerea fundului și definirea ordinii ca pentru toate elementele setului . $M$ $\bot$ $\leqslant$ $\bot \leqslant m$ $m\leqslant m$ $m$ $M$

Teoreme pe mulțimi parțial ordonate

Teoremele fundamentale ale mulțimilor parțial ordonate includ principiul maximului Hausdorff și lema Kuratowski-Zorn . Fiecare dintre aceste teoreme este echivalentă cu axioma de alegere .

În teoria categoriei

Fiecare poset (și fiecare precomandă ) poate fi privit ca o categorie , în care fiecare set de morfisme este format din cel mult un element. De exemplu, această categorie poate fi definită după cum urmează: dacă A ≤ B (și setul gol în caz contrar); regula de compunere a morfismului: ( y , z )∘( x , y ) = ( x , z ). Fiecare categorie de precomandă este echivalentă cu un set parțial ordonat. ${\mathrm {Hom}}(A,B)$ ${\mathrm {Hom}}(A,B)=\{(A,B)\}$

Un functor dintr-o mulțime parțial ordonată de categorii (adică o diagramă a cărei categorie de index este un poset) este o diagramă comutativă .

Note

↑ Kolmogorov, 2004 , p. 36.
↑ Aleksandrov, 1977 , p. 78.
↑ Kolmogorov, 2004 , p. 38.
↑ Kolmogorov, 2004 , p. 40.
↑ Barendregt, 1985 , p. 23.

Literatură

Aleksandrov PS Introducere în teoria mulțimilor și topologia generală. — M .: Nauka , 1977. — 368 p.
Barendregt, Henk. Calcul lambda. Sintaxa și semantica sa = The Lambda Calculus. Sintaxa și semantica sa. — M .: Mir , 1985. — 606 p. - 4800 de exemplare.
Kolmogorov AN, Fomin SV Elemente de teoria funcţiilor şi analiză funcţională. - Ed. a VII-a. — M .: Fizmatlit , 2004. — 572 p. — ISBN 5-9221-0266-4 .
Hausdorff F. Teoria mulţimilor. - a 4-a ed. — M .: URSS , 2007. — 304 p. - ISBN 978-5-382-00127-2 .
Gurov S.I. Algebre booleene, mulțimi ordonate, rețele: Definiții, proprietăți, exemple. - Ed. a II-a. — M .: Librokom , 2013. — 352 p. - ISBN 978-5-397-03899-7 .