Kompakt element - Compact element
I det matematiske område med ordre teori er de kompakte elementer eller endelige elementer i et delvist ordnet sæt de elementer, der ikke kan underkastes et supremum af ethvert ikke-tomt rettet sæt , der ikke allerede indeholder medlemmer over det kompakte element. Denne opfattelse af kompakthed generaliserer samtidig forestillingerne om endelige sæt i sætteori , kompakte sæt i topologi og finit genererede moduler i algebra . (Der er andre forestillinger om kompakthed i matematik.)
Formel definition
I et delvist ordnet sæt ( P , ≤) kaldes et element c kompakt (eller endeligt ), hvis det opfylder en af følgende ækvivalente betingelser:
- For hver rettet delmængde D af P , hvis D har en supremum sup D og c ≤ sup D derefter c ≤ d for nogle element d af D .
- For hver ideal jeg af P , hvis jeg har en supremum sup jeg og c ≤ sup jeg så c er et element af jeg .
Hvis poset P desuden er et sammenføjnings-semilattice (dvs. hvis det har binært suprema), svarer disse betingelser til følgende udsagn:
- For hver delmængde S af P , hvis S har en supremum sup S og c ≤ sup S , derefter c ≤ sup T for nogle begrænsede delmængde T af S .
Navnlig hvis c = sup S , derefter c er supremum af et finit delmængde af S .
Disse ækvivalenser kan let verificeres ud fra definitionerne af de involverede begreber. I tilfælde af et sammenføjnings-semilattice kan ethvert sæt omdannes til et rettet sæt med samme overherredømme ved at lukke under endeligt (ikke-tomt) suprema.
Når man overvejer rettet fuldstændig delvis ordre eller komplette gitter, kan de yderligere krav, som det angivne overordnede eksisterer, naturligvis bortfalde. Et sammenføjnings-semilattice, der er rettet komplet, er næsten et komplet gitter (muligvis mangler mindst element ) - se fuldstændighed (ordre teori) for detaljer.
Eksempler
- Det mest grundlæggende eksempel opnås ved at overveje strømsættet til noget sæt A , bestilt ved inkludering af delmængde . Inden for denne komplette gitter, de kompakte elementer er nøjagtig de begrænsede delmængder af A . Dette retfærdiggør navnet "endeligt element".
- Udtrykket "kompakt" er inspireret af definitionen af (topologisk) kompakte delmængder af en topologisk rum T . Et sæt Y er kompakt, hvis for hver samling af åbne sæt S , hvis unionen løbet S omfatter Y som en delmængde, så Y indgår som en delmængde af foreningen af en finite undersamling af S . I betragtning af kraftsættet af T som et komplet gitter med delmængdens inklusionsrækkefølge, hvor overhøjden af en samling af sæt er givet af deres forening, efterligner den topologiske betingelse for kompaktitet betingelsen for kompakthed i sammenføjningshalvgitter, men for det yderligere krav af åbenhed.
- Hvis det findes, er det mindste element i en poset altid kompakt. Det kan være, at dette er det eneste kompakte element, som eksemplet på det reelle enhedsinterval [0,1] (med standardrækkefølgen nedarvet fra de reelle tal) viser.
- Hvert helt sammenføjningselement i et gitter er kompakt.
Algebraiske posets
En poset, hvor hvert element er supremum for de kompakte elementer under det kaldes en algebraisk poset . Sådanne posets, der er dcpos, bruges meget i domæne teori .
Som et vigtigt specielt tilfælde er et algebraisk gitter et komplet gitter L, hvor hvert element x af L er supremum for de kompakte elementer under x .
Et typisk eksempel (som tjente som motivation for navnet "algebraisk") er følgende:
For enhver algebra A (for eksempel en gruppe, en ring, et felt, et gitter osv .; eller endda et simpelt sæt uden nogen operationer), lad Sub ( A ) være sættet med alle underkonstruktioner af A , dvs. af alle undergrupper af A, som er lukket under alle operationer i A (gruppetilføjelse, ringtilsætning og multiplikation osv.). Her inkluderer begrebet underkonstruktion den tomme underkonstruktion, hvis algebra A ikke har nogen ugyldige operationer.
Derefter:
- Sættet Sub ( A ), bestilt efter sætindeslutning, er et gitter.
- Den største del af Sub ( A ) er det sæt A selv.
- For enhver S , T i under ( A ) er den største nedre grænse for S og T den indstillede teoretiske skæring af S og T ; den mindste øvre grænse er subalgebra genereres af foreningen af S og T .
- Sættet Sub ( A ) er endda et komplet gitter. Den største nedre grænse for enhver familie af underkonstruktioner er deres kryds (eller A, hvis familien er tom).
- De kompakte elementer Sub ( A ) er nøjagtigt de finitely genererede substrukturer af A .
- Hver underkonstruktion er foreningen af dets finit genererede underkonstruktioner; derfor er Sub ( A ) et algebraisk gitter.
Også, en slags omvendt holder: Hver algebraisk gitter er isomorf til Sub ( A ) for nogle algebra A .
Der er en anden algebraisk gitter, der spiller en vigtig rolle i universel algebra : For hver algebra En vi lader Con ( A ) være mængden af alle kongruens relationer på A . Hver kongruens på A er en subalgebra af produktalgebra A x A , så Con ( A ) ⊆ Sub ( A x A ). Igen har vi det
- Con ( A ), bestilt efter sæt inkludering, er et gitter.
- Det største element i Con ( A ) er sættet A x A , som er kongruensen svarende til den konstante homomorfisme. Den mindste kongruens er diagonalen af A x A svarende til isomorfier.
- Con ( A ) er et komplet gitter.
- De kompakte elementer i Con ( A ) er nøjagtigt de endeligt genererede kongruenser.
- Con ( A ) er et algebraisk gitter.
Igen er der et omvendt: Ved en sætning af George Gratzer og ET Schmidt, hver algebraisk gitter er isomorf til Con ( A ) for nogle algebra A .
Ansøgninger
Kompakte elementer er vigtige inden for datalogi i den semantiske tilgang, der kaldes domæne teori , hvor de betragtes som en slags primitivt element: informationen repræsenteret af kompakte elementer kan ikke opnås ved nogen tilnærmelse, der ikke allerede indeholder denne viden. Kompakte elementer kan ikke tilnærmes af elementer, der ligger under dem. På den anden side kan det ske, at alle ikke-kompakte elementer kan opnås som instrueret suprema for kompakte elementer. Dette er en ønskelig situation, da sættet med kompakte elementer ofte er mindre end den oprindelige poset - eksemplerne ovenfor illustrerer dette.
Litteratur
Se litteraturen angivet for ordre teori og domæne teori .
