Granica Fraïsségo

W logice matematycznej , szczególnie w dyscyplinie teorii modeli , granica Fraïsségo (zwana także konstrukcją Fraïsségo lub amalgamacją Fraïsségo ) jest metodą stosowaną do konstruowania (nieskończonych) struktur matematycznych z ich (skończonych) podstruktur . Jest to szczególny przykład bardziej ogólnej koncepcji bezpośredniej granicy w kategorii . Technika ta została opracowana w latach pięćdziesiątych XX wieku przez jej imiennika, francuskiego logika Rolanda Fraïssé .

Głównym celem konstrukcji Fraïsségo jest pokazanie, w jaki sposób można aproksymować ( przeliczalną ) strukturę za pomocą jej skończenie generowanych podstruktur. Biorąc pod uwagę klasę skończonych $struktur$ relacyjnych , jeśli spełnia pewne właściwości ( $)$ , to istnieje unikalna struktura ${ \ displaystyle \ operatorname {Flim} (\ mathbf {K})}$ , zwany granicą Fraïsségo $}}$ $mathbf {$ , który zawiera wszystkie elementy jako podstruktury .

Ogólne badanie granic Fraïsségo i związanych z nimi pojęć jest czasami nazywane teorią Fraïsségo . Dziedzina ta znalazła szerokie zastosowanie w innych częściach matematyki, w tym w dynamice topologicznej , analizie funkcjonalnej i teorii Ramseya .

Skończenie generowane podstruktury i wiek

Napraw język ${\ displaystyle {\ mathcal {L}}}$ . Przez \ displaystyle {\mathcal {L $-strukturę$ rozumiemy strukturę logiczną mającą sygnaturę $}}$ .

Biorąc pod uwagę $}$ M $\ Displaystyle$ ${\ mathcal {M}}}$ z domeną i podzbiorem $M$ $\ Displaystyle A \ subseteq$ , używamy do oznaczenia najmniejszej $domena$ M $\ Displaystyle {\ mathcal {M}}}$ $,$ zawiera $A}$ \ $funkcjami$ . zamknięcie pod wszystkimi i stałymi symbolami $)$ .

podstruktura z ${\ Displaystyle {$ $\ mathcal {M}}}$ jest generowana w sposób skończony , jeśli $} = \ langle A \ rangle ^ {\ mathcal {M}}}$ ${\ Displaystyle {\ mathcal {N$ dla pewnego skończonego podzbioru ${\ Displaystyle A \ subseteq M}$ . Wiek _ $,$ oznaczony _ ${\ Displaystyle \ operatorname {Wiek} ({\ mathcal {M}})}$ jest klasą wszystkich skończenie generowanych podstruktur ${\ displaystyle {\ mathcal {M}}}$ .

Można udowodnić, że każda klasa , która jest wiekiem jakiejś struktury, spełnia następujące dwa warunki: ${\ displaystyle \ mathbf {K}}$

Własność dziedziczna (HP)

Jeśli i

jest

{\ Displaystyle \ mathbf {K}}

wygenerowaną

podstrukturą

.

to

jest

w .

Wspólna właściwość osadzania (JEP)

Jeśli

{\ Displaystyle A, B \ in \ mathbf {K}}

{\ Displaystyle A

to istnieje takie, że zarówno

,

i

{ \ displaystyle

można osadzić w do

}

.

Twierdzenie Fraïsségo

Diagram przemienny ilustrujący właściwość amalgamacji.

Jak wyżej, zauważyliśmy, że dla dowolnego -structure ${\ Displaystyle {$ $\ mathcal {M}}}$ $\mathcal {M}})}$ ${\ Displaystyle \ operatorname {Wiek} ($ } spełnia HP i JEP. Fraïssé udowodnił $że$ wynik jest w pewnym sensie odwrotny: kiedy jest dowolnym $niepustym$ , policzalnym zbiorem skończenie generowanych struktur które mają powyższe dwie właściwości, to jest to wiek jakiejś przeliczalnej struktury.

Ponadto załóżmy, że zdarza się $,$ spełnia następujące dodatkowe właściwości.

Własność fuzji (AP)

{\ Displaystyle A, B, C \ in \ mathbf {K}}

do , g : ZA , b , do ∈ K. $}$ $, B, C \ in \ mathbf$ } istnieje struktura

{\ Displaystyle D \ in \ mathbf {K}}

i osadzenie ${\ Displaystyle f ': B \ do D}$ $\ Displaystyle g': C \ do D}$ : takie, że

{\ Displaystyle f'\ circ f = g '\circ g}

(tj. pokrywają się na obrazie A w obu strukturach).

Podstawowa policzalność (EC)

policzalnie wiele struktur w

istnieje .

W takim przypadku mówimy, że K jest klasą Fraïsségo i istnieje unikalna (z dokładnością do izomorfizmu), policzalna, jednorodna struktura, której $mathbf {K})}$ \ wiek jest dokładnie ${\ Displaystyle \ mathbf {K}}$ . Ta $.$ nazywana jest granicą Fraïsségo

Tutaj jednorodny oznacza, że każdy izomorfizm między $do B}$ skończenie wygenerowanymi podstrukturami można rozszerzyć . $Displaystyle \ pi:$ do automorfizmu całej struktury.

Przykłady

Archetypowym przykładem jest klasa wszystkich skończonych porządków liniowych, dla których granica Fraïsségo jest gęstym $bez$ liniowym punktów końcowych . bez najmniejszego ani największego elementu ). Zgodnie z twierdzeniem Cantora o izomorfizmie , aż do izomorfizmu, jest to zawsze równoważne strukturze , tj. Liczbom wymiernym $\ rangle}$ < ze zwykłym zamówieniem.

Jako przykład, zauważ, że ani ${\ Displaystyle \ langle \ mathbb {N}, <\ rangle}$ ani ${\ Displaystyle \ langle \ mathbb {Z}, <\ rangle}$ to granica Fraïsségo . fa $\ displaystyle \ mathbf {FCh}}$ . Dzieje $ponieważ$ chociaż oba są policzalne i mają jako swój wiek, żadne z nich nie jest jednorodne Aby to zobaczyć, rozważ podstruktury ${\ Displaystyle {\ duży \ langle} \ {1,3 \}, <{\ duży \ rangle}}$ i $\},<{\big \rangle$ ${\ Displaystyle {\ duży \langle}$ ${$ izomorfizm . Nie można tego rozszerzyć na automorfizm ${\ Displaystyle \ langle \ mathbb {N}, <\ rangle}$ lub ${\ Displaystyle \ langle \ mathbb {Z}, <\ rangle}$ , ponieważ nie ma elementu, do którego moglibyśmy odwzorować ${\ displaystyle 2}$ , zachowując jednocześnie porządek.

Innym przykładem jest klasa wszystkich grafów $skończonych$ , której granicą wykres .

ω-kategoryczność

Załóżmy, że nasza rozważana klasa $spełnia$ dodatkową właściwość bycia jednostajnie lokalnie skończonym , co oznacza, że dla każdego $displaystyle n}$ jednolita granica rozmiaru an $displaystyle n}$ ${$ -generowana podstruktura. Ten warunek jest równoważny z granicą Fraïsségo, $jest$ ω -kategoryczna .

Na przykład klasa skończonych wymiarowych przestrzeni wektorowych nad ustalonym polem jest zawsze klasą Fraïsségo, ale jest jednolicie lokalnie skończona tylko wtedy, gdy pole jest skończone.

Zobacz też