Теория на наредбите

Шаблон:Експерт Теорията на наредбите е дял от математиката, в който се изучават различните релации на наредба. Неформално казано, всяка релация на наредба показва кога един елемент на множество предхожда друг елемент, тоест кога е по-малък от него.

Наредбите се делят на строги (като $<$ и $>$) и нестроги (като $\le$ и $\ge$).

Наредбите могат да бъдат частични или пълни (линейни). Пълната наредба определя за всеки два елемента кой от тях предхожда другия. Когато наредбата е частична, може да има несравними двойки от елементи. Пример за пълна (линейна) наредба е наредбата на целите числа. Частична е например наредбата на поколенията (кой на кого е потомък): при нея братята и сестрите са несравними (никой не е потомък на другия).

Добра наредба се нарича такава пълна наредба на дадено множество, относно която всяко негово непразно подмножество притежава най-малък елемент. Например стандартната наредба $\le$ в множеството на естествените числа е добра наредба. Според теоремата на Цермело всяко непразно множество може да се снабди с добра наредба.

По-формално, всяка нестрога наредба е рефлексивна, антисиметрична и транзитивна бинарна релация, а всяка строга наредба е антирефлексивна, антисиметрична и транзитивна бинарна релация. Пълните наредби (строги сили нестроги) са напълно антисиметрични.

Съвременното развитие на теорията на наредбите започва от XIX век с трудовете на Джордж Бул, Рихард Дедекинд и Ърнст Шрьодер. През 1940 г. Гарет Биркхоф публикува книгата Теория на решетките, където отделя значително внимание на различните видове наредби.

Лема на Цорн

Нека $S$ е частично наредено множество. Верига в $S$ е подмножество $K\subset S$, в което $\mathrm{\forall }x,y\in K$ е изпълнено $x\le y$ или $y\le x$. Горна граница (мажоранта или супремум) за веригата $K$ в множеството $S$ е такъв елемент $s\in S$, че $k\le s,\mathrm{\forall }k\in K$. В множеството $S$ съществува максимален елемент $m$, ако е изпълнено: $m\le x\Rightarrow m=x,\mathrm{\forall }x\in S$.

Лема на Цорн: Всяко частично наредено множество, в което всяка верига има горна граница, притежава максимален елемент.

Литература

• G. Birkhoff, Lattice Theory, Providence, RI: AMS, 1940.
• B. A. Davey, H. A. Priestley, Introduction to Lattices and Order, Cambridge: Cambridge University Press, 1990.