Мрежа је апстрактна структура која се проучава у математичким поддисциплинама теорије уређења и апстрактне алгебре. Састоји се од парцијално уређеног скупа у којем сваки пар елемената има јединствен супремум (који се такође назива најмање горње ограничење или спој) и јединствен инфимум (који се такође назива највеће доње ограничење или пресек). Пример је партитивни скуп неког скупа, парцијално уређен инклузијом, за који је супремум унија, а инфимум пресек. Други пример дају природни бројеви, парцијално уређени по дељивости, за које је супремум најмањи заједнички садржалац, а инфимум највећи заједнички делилац.

Мреже се такође могу окарактерисати као алгебарске структуре које задовољавају одређене аксиоматске идентитете. Пошто су ове две дефиниције еквивалентне, теорија мрежа се ослања и на теорију уређења и на универзалну алгебру. Класа мрежа се може генерализовати на полумреже, а неке значајне поткласе мрежа су Хејтингове алгебре, Булове алгебре, дистрибутивне мреже и геометријске мреже (матроиди). Све ове структура налик на мреже допуштају како описе из теорије уређења, тако и алгебарске описе.

Подобласт која проучава мреже назива се теорија мрежа.

Дефиниција Мрежа се може дефинисати или преко теорије уређења као парцијално уређен скуп, или као алгебарска структура.

Као парцијално уређен скуп Парцијално уређен скуп (поскуп) назива се мрежа ако је истовремено и полумрежа супремума и полумрежа инфимума, тј. сваки двоелементни подскуп има свој супремум (најмање горње ограничење, које се означава са ) и дуално свој инфимум (највеће доње ограничење, које се означава са ). Ова дефиниција чини и бинарним операцијама. Обе операције су монотоне у односу на дато уређење: и имплицира да је и

Из аргумента индукције следи да сваки непразан коначан подскуп мреже има најмање горње ограничење и највеће доње ограничење. Уз додатне претпоставке, могући су и даљи закључци; за више детаља о овој теми погледајте чланак Комплетност (теорија уређења). Тај чланак такође разматра како се горња дефиниција може преформулисати у смислу постојања одговарајућих Галоаових веза између повезаних парцијално уређених скупова — приступ од посебног интереса за категоријски приступ мрежама и за анализу формалних концепата.

С обзиром на подскуп мреже, инфимум и супремум се ограничавају на парцијалне функције — оне су недефинисане ако њихова вредност није у подскупу Добијена структура на се назива парцијална мрежа. Поред ове спољашње дефиниције као подскупа неке друге алгебарске структуре (мреже), парцијална мрежа се такође може интринзично дефинисати као скуп са две парцијалне бинарне операције које задовољавају одређене аксиоме.

Као алгебарска структура Мрежа је алгебарска структура , која се састоји од скупа и две бинарне, комутативне и асоцијативне операције и на које задовољавају следеће аксиоматске идентитете (понекад зване закони апсорпције) за све елементе :

Следећа два идентитета се такође обично сматрају аксиомама, иако следе из два закона апсорпције заједно.. „пошто је и дуално”. Биркхоф ово приписује Ови закони се називају закони идемпотенције.

Ове аксиоме тврде да су и и полумреже. Закони апсорпције, једине аксиоме изнад у којима се појављују и инфимум и супремум, разликују мрежу од произвољног пара полумрежних структура и осигуравају да две полумреже правилно интерагују. Конкретно, свака полумрежа је дуална оној другој. Закони апсорпције се могу посматрати као захтев да полумреже инфимума и супремума дефинишу исто парцијално уређење.

Веза између две дефиниције Теоријско-уређајна мрежа доводи до две бинарне операције и Пошто се комутативни, асоцијативни и закони апсорпције лако могу проверити за ове операције, они чине мрежом у алгебарском смислу.

Обрнуто такође важи. Датој алгебарски дефинисаној мрежи може се дефинисати парцијално уређење на постављањем

за све елементе Закони апсорпције осигуравају да су обе дефиниције еквивалентне:

и дуално за други смер.

Сада се може проверити да релација уведена на овај начин дефинише парцијално уређење унутар којег су бинарни инфимуми и супремуми дати кроз оригиналне операције и

Пошто су две дефиниције мреже еквивалентне, може се слободно позивати на аспекте било које од њих на било који начин који одговара тренутној сврси.

Ограничена мрежа

Ограничена мрежа је мрежа која додатно има највећи елемент (такође зван максимум или врх, означен са или и најмањи елемент (такође зван минимум или дно, означен са или који задовољавају

Ограничена мрежа се такође може дефинисати као алгебарска структура облика тако да је мрежа, (дно мреже) је неутрални елемент за операцију супремума а (врх мреже) је неутрални елемент за операцију инфимума

Парцијално уређен скуп је ограничена мрежа ако и само ако сваки коначан скуп елемената (укључујући и празан скуп) има супремум и инфимум. Свака коначна мрежа је ограничена.

Свака мрежа се може уградити у ограничену мрежу додавањем највећег и најмањег елемента. Штавише, свака непразна коначна мрежа је ограничена, узимањем супремума (односно инфимума) свих елемената, што се означава са (односно ) где је скуп свих елемената.

Веза са другим алгебарским структурама Мреже имају одређене везе са породицом алгебарских структура налик групи. Пошто инфимум и супремум комутирају и асоцирају, мрежа се може посматрати као да се састоји од две комутативне полугрупе које имају исти домен. За ограничену мрежу, ове полугрупе су заправо комутативни моноиди. Закон апсорпције је једини дефинишући идентитет који је специфичан за теорију мрежа. Ограничена мрежа се такође може сматрати комутативним полупрстеном без дистрибутивне аксиоме.

Због комутативности, асоцијативности и идемпотенције може се размишљати о супремуму и инфимуму као о операцијама на непразним коначним скуповима, а не на паровима елемената. У ограниченој мрежи супремум и инфимум празног скупа се такође могу дефинисати (као и респективно). Ово чини ограничене мреже нешто природнијим од општих мрежа, и многи аутори захтевају да све мреже буду ограничене.

Алгебарска интерпретација мрежа игра суштинску улогу у универзалној алгебри.

Примери

За било који скуп колекција свих подскупова од (названа партитивни скуп од ) може се уредити преко скуповне инклузије како би се добила мрежа ограничена самим и празним скупом. У овој мрежи, супремум је обезбеђен скуповном унијом, а инфимум скуповним пресеком (види Сл. 1). За било који скуп колекција свих коначних подскупова од уређених по инклузији, такође је мрежа, и биће ограничена ако и само ако је коначан. За било који скуп колекција свих партиција од уређених по рафинирању, јесте мрежа (види Сл. 3). Позитивни цели бројеви у свом уобичајеном уређењу формирају неограничену мрежу, под операцијама „min” и „max”. 1 је дно; нема врха (види Сл. 4). Декартов квадрат природних бројева, уређен тако да ако је Пар је најмањи елемент; нема врха (види Сл. 5). Природни бројеви такође формирају мрежу под операцијама узимања највећег заједничког делиоца и најмањег заједничког садржаоца, са дељивошћу као релацијом уређења: ако дели је дно; је врх. Сл. 2 приказује коначну подмрежу. Свака комплетна мрежа (такође види испод) је (прилично специфична) ограничена мрежа. Ова класа даје широк спектар практичних примера. Скуп компактних елемената аритметичке комплетне мреже је мрежа са најмањим елементом, где су операције мреже дате ограничавањем одговарајућих операција аритметичке мреже. Ово је специфично својство које разликује аритметичке мреже од алгебарских мрежа, за које компактни елементи чине само полумрежу супремума. Обе ове класе комплетних мрежа се проучавају у теорији домена.

Даљи примери мрежа су дати за свако од додатних својстава о којима се говори у наставку.

Примери скупова који нису мреже мини|x150px|Сл. 8: Поскуп који није мрежа: и имају заједничка доња ограничења и али ниједно од њих није највеће доње ограничење. мини|x150px|Сл. 7: Поскуп који није мрежа: и имају заједничка горња ограничења и али ниједно од њих није најмање горње ограничење. мини|x150px|Сл. 6: Поскуп који није мрежа: и немају заједничко горње ограничење.

Већина парцијално уређених скупова нису мреже, укључујући следеће. Дискретни поскуп, што значи поскуп такав да имплицира је мрежа ако и само ако има највише један елемент. Посебно, двоелементни дискретни поскуп није мрежа. Иако је скуп парцијално уређен по дељивости мрежа, скуп уређен на исти начин није мрежа јер пар 2, 3 нема супремум; слично, пар 2, 3 нема инфимум у Скуп парцијално уређен по дељивости није мрежа. Сваки пар елемената има горње и доње ограничење, али пар 2, 3 има три горња ограничења, наиме 12, 18 и 36, од којих ниједно није најмање међу та три под дељивошћу (12 и 18 не деле једно друго). Слично, пар 12, 18 има три доња ограничења, наиме 1, 2 и 3, од којих ниједно није највеће међу та три под дељивошћу (2 и 3 не деле једно друго).

Морфизми мрежа мини|Сл. 9: Монотоно пресликавање између мрежа које не чува ни супремуме ни инфимуме, пошто је и Одговарајући појам морфизма између две мреже лако произилази из горенаведене алгебарске дефиниције. Дате две мреже и хомоморфизам мрежа са L у M је функција таква да за све

Тако је хомоморфизам двеју основних полумрежа. Када се разматрају мреже са више структуре, морфизми би требало да „поштују” и додатну структуру. Конкретно, хомоморфизам ограничених мрежа (обично се назива само „хомоморфизам мрежа”) између две ограничене мреже и такође треба да има следеће својство:

У формулацији теорије уређења, ови услови само наводе да је хомоморфизам мрежа функција која чува бинарне инфимуме и супремуме. За ограничене мреже, очување најмањег и највећег елемента је само очување супремума и инфимума празног скупа.

Сваки хомоморфизам мрежа је нужно монотон у односу на придружену релацију уређења. Обрнуто није тачно: монотоност нипошто не имплицира потребно очување инфимума и супремума (види Сл. 9), иако је бијекција која чува уређење хомоморфизам ако је њој инверзна функција такође монотона (чува уређење).

Имајући у виду стандардну дефиницију изоморфизама као инвертибилних морфизама, изоморфизам мрежа је само бијективни хомоморфизам мрежа. Слично, ендоморфизам мрежа је хомоморфизам мреже у саму себе, а аутоморфизам мрежа је бијективни ендоморфизам мрежа. Мреже и њихови хомоморфизми чине категорију.

Нека су и две мреже са 0 и 1. Хомоморфизам са у се назива 0,1-раздвајајућим ако и само ако ( раздваја 0) и ( раздваја 1).

Подмреже Подмрежа мреже је подскуп од који је мрежа са истим операцијама инфимума и супремума као То јест, ако је мрежа и је подскуп од такав да су за сваки пар елемената и и у онда је подмрежа од

Подмрежа мреже је конвексна подмрежа од ако и имплицира да припада за све елементе

Својства мрежа

Сада уводимо низ важних својстава која доводе до занимљивих специјалних класа мрежа. Једно, ограниченост, већ је разматрано.

Комплетност

Поскуп се назива комплетном мрежом ако сви његови подскупови имају и супремум и инфимум. Посебно, свака комплетна мрежа је ограничена мрежа. Док хомоморфизми ограничених мрежа уопштено чувају само коначне супремуме и инфимуме, од хомоморфизама комплетних мрежа се захтева да чувају произвољне супремуме и инфимуме.

Сваки поскуп који је комплетна полумрежа такође је и комплетна мрежа. С овим резултатом је повезан занимљив феномен да постоје различити конкурентни појмови хомоморфизма за ову класу поскупова, зависно од тога да ли се посматрају као комплетне мреже, комплетне полумреже супремума, комплетне полумреже инфимума или као мреже комплетне у односу на супремум или инфимум.

„Парцијална мрежа” није супротност „комплетној мрежи” — напротив, „парцијална мрежа”, „мрежа” и „комплетна мрежа” су све рестриктивније дефиниције.

Условна комплетност Условно комплетна мрежа је мрежа у којој сваки непразан подскуп који има горње ограничење има супремум (најмање горње ограничење). Такве мреже пружају најдиректнију генерализацију аксиоме комплетности реалних бројева. Условно комплетна мрежа је или комплетна мрежа, или комплетна мрежа без свог максимума свог минимума или оба.