Strukturalna teoria Ramseya

W matematyce strukturalna teoria Ramseya jest kategorycznym uogólnieniem teorii Ramseya , zakorzenionym w założeniu, że wiele ważnych wyników teorii Ramseya ma „podobną” strukturę logiczną. Kluczową obserwacją jest zauważenie, że te twierdzenia typu Ramseya można wyrazić jako stwierdzenie, że pewna kategoria (lub klasa struktur skończonych) ma właściwość Ramseya ( zdefiniowaną poniżej).

Strukturalna teoria Ramseya rozpoczęła się w latach siedemdziesiątych XX wieku wraz z pracami Nešetřila i Rödla i jest ściśle powiązana z teorią Fraïsségo . W połowie 2000 roku ponownie zainteresowano się nim w związku z odkryciem korespondencji Kechrisa – Pestowa – Todorčevicia , która łączyła teorię strukturalną Ramseya z dynamiką topologiczną .

Historia

Leebowi przypisuje się wynalezienie idei własności Ramseya na początku lat 70., a pierwszą publikacją tego pomysłu wydaje się być artykuł Grahama , Leeba i Rothschilda z 1972 roku na ten temat. Kluczowego rozwinięcia tych idei dokonali Nešetřil i Rödl w swoich seriach artykułów z 1977 i 1983 roku, w tym słynne twierdzenie Nešetřila – Rödla. Wynik ten został niezależnie odrzucony przez Abramsona i Harringtona , a następnie uogólniony przez Prömela . Niedawno Mašulović i Solecki wykonali pionierskie prace w tej dziedzinie.

Motywacja

W tym artykule wykorzystamy konwencję teorii mnogości, zgodnie z którą każdą liczbę naturalną ${\ Displaystyle n = \ {0,1, \ ldots, n-1 \}}$ zbiór wszystkich liczb naturalnych mniejszych od niej: $in \ mathbb {N$ . Dla każdego zestawu $przypisaniem$ jest jednego z ZA $A}$$\$${\ displaystyle r}$ etykiety do każdego elementu ${\ displaystyle A}$ . $odwzorowującą$ funkcję każdy element na jego etykietę w $displaystyle r = \ {$ (which this article will use), or equivalently as a partition of ${\ Displaystyle A = A_ {0} \ sqcup \ cdots \ sqcup A_ {r-1}}$ na kawałki ${\ displaystyle r}$ .

Oto niektóre z klasycznych wyników teorii Ramseya:

• (Skończone) $Displaystyle n \ w \ mathbb$ Ramseya : dla każdego $\$ n tak, że dla każdego $-kolorystyka$${\ Displaystyle \ Delta: [n] ^ {(k)} \ do r}$ k { $displaystyle k}$ -elementowe podzbiory ${\ Displaystyle n = \ {0,1 \ ldots, n-1 \}}$ istnieje podzbiór ${\ Displaystyle A \ subseteq n}$ , z $= m}$$Displaystyle$ tak, że $[A] ^ {(k)}}$ jest -monochromatyczny.
• (Skończone) $\ Displaystyle n \ in \ mathbb {N$ van der Waerdena : dla każdego ${$ takie, dla każdy ${\ displaystyle r}$ -kolorystyka ${\ Displaystyle \ Delta: n \ do r}$ z ${\ displaystyle n}$ istnieje -monochromatyczny postęp arytmetyczny ${\ displaystyle \ Delta}$${\ Displaystyle \ {a, a + d, a + 2d, \ ldots, a + (m-1) d \} \ subseteq n}$ długości ${\ displaystyle m}$ .
• Twierdzenie Grahama-Rothschilda : napraw skończony alfabet ${\ Displaystyle L = \ {a_ {0}, a_ {1}, \ ldots, a_ {d-1} \}}$ . ZA ${\ Displaystyle k}$ - parametr słowo o długości $Displaystyle$ L $L}$ jest elementem ${\ Displaystyle w \ w (L \ kubek \ {x_ {0}, x_ {1}, \ ldots, x_ {k-1} \}) ^ {n}} , tak że$$pojawiają się$ wszystkie , a ich pierwsze występy są w porządku Zbiór wszystkich $-parametrowych$ słów o długości $jest$$Displaystyle L}$ oznaczony przez [ ${\ Displaystyle \ textstyle [L] {\ binom {n} {k}}}$ . w ${\ Displaystyle \ textstyle w \ w [L] {\ binom {n} {m}}}$ i $[L]{\binom {m}{k}}}$${\ Displaystyle \ textstyle v \$ , tworzymy ich skład
  ${\ Displaystyle \ textstyle w \ circ v \ in [L] {\ binom {n} {k}}}$ zastępując każde wystąpienie ${\ displaystyle x_ {i}}$ w ${\ displaystyle w}$ z ${\ displaystyle i}$ th wpis z ${\ displaystyle v}$ . Następnie twierdzenie Grahama-Rothschilda stwierdza, że ​​dla każdego istnieje ${\ Displaystyle k \ równoważnik m, r \ in \ mathbb {N}} n$$\ Displaystyle n \ in \ mathbb { N} }$ takie, że dla każdego $Δ$$\ Displaystyle \ textstyle \ Delta: [L] {\ binom {n} {k}} \ do r$ } wszystkich k ${\ displaystyle k}$ -parametrowe słowa o długości ${\ displaystyle n}$ istnieje $Displaystyle \ textstyle w \ w [L] {\ binom {n} {m} }}$ , takie, że ${\ Displaystyle \ textstyle w \ circ [L] {\ binom {m} {k}} = \ {w \ circ v: v \ in [L] {\ binom {m} {k}} \}}$ (tj. wszystkie podsłowa $-parametr$ z ${\ displaystyle w}$ ) jest ${\ displaystyle \ Delta }$ -monochromatyczny.
• (Skończone) $\ in \ mathbb {N$ Folkmana : dla każdego ${\ displaystyle r}$ takie że dla każdego r ${\ Displaystyle m, r$ -colouring ${\ Displaystyle \ Delta: n \ do r}$ z ${\ displaystyle n}$ istnieje podzbiór ${\ Displaystyle A \ subseteq n}$ z ${\ Displaystyle | A | = m}$ , tak że ${\ Displaystyle \ textstyle {\ duży (} \ suma _ {k \ w A} k {\ duży) <n }$ , i ${\ Displaystyle \ textstyle \ operatorname {FS} (A) = \ {\ suma _ {k \ in B} k: B \ in {\ mathcal {P}} (A) \ setminus \ varnothing \}}$ jest ${ \displaystyle \Delta}$ -monochromatyczny.

$pomysł$ : ustalamy dwie liczby całkowite $i$ { $displaystyle m}$ oraz zbiór . Następnie chcemy pokazać, że istnieje $-kolorystyki$ duży, taki, że dla każdego ${\ displaystyle$$”$ o rozmiarze wewnątrz $n}$ , możemy znaleźć odpowiednią „strukturę” ${\ displaystyle A}$ wewnątrz ${\ displaystyle n}$$,$ o rozmiarze tak że wszystkie „konstrukcje” ${\ displaystyle B}$ z ${\ displaystyle A}$ o rozmiarze ${\ displaystyle k}$ mieć ten sam kolor.

To, jakie typy struktur są dozwolone, zależy od danego twierdzenia i okazuje się, że jest to praktycznie jedyna różnica między nimi. Ta idea „twierdzenia typu Ramseya” prowadzi do dokładniejszego pojęcia właściwości Ramseya (poniżej).

Własność Ramseya

Niech będzie kategorią $do {\ displaystyle \ mathbf {C}$ . ${\ Displaystyle \ mathbf {C}}$ ma właściwość Ramseya , jeśli dla każdej liczby naturalnej i wszystkich obiektów $Displaystyle$$A, B}$ w do { $}}$ , istnieje inny obiekt $displaystyle$ taki , że dla każdego $\ mathbf {C}$ ${\ Displaystyle r}$ -kolorowanie ${\ Displaystyle \ Delta: \ operatorname {Hom} (A, D) \ do r}$ istnieje morfizm ${\ displaystyle f: B \ do D}$ , który jest -monochromatyczny, tj. zestaw ${\ displaystyle \ Delta}$

${\ Displaystyle f \ circ \ operatorname {Hom} (A, B) = {\ duży \ {} f \ circ g:g\in \nazwa_operatora {Hom} (A,B){\big \}}}$

jest ${\ displaystyle \ Delta}$ -monochromatyczny.

Często przyjmuje się, $że$ jest to klasa skończonych struktur nad pewnym ustalonym $}}$ L $\ Displaystyle { \ mathcal {L$ , z osadzaniami jako morfizmami. W ${\$ przypadku, zamiast kolorowania morfizmów, można pomyśleć o kolorowaniu „kopii” w $displaystyle$$}$ następnie znalezieniu kopii w $}$$D$$w$ tak że wszystkie kopie tej kopii $są$ . Może to bardziej intuicyjnie pasować do wcześniejszej idei „twierdzenia typu Ramseya”.

Istnieje również pojęcie podwójnej własności Ramseya; $C}}$$podwójna$ ma podwójną właściwość Ramseya, jeśli jej właściwość Ramseya jak powyżej. Mówiąc dokładniej, $C}}$ podwójną właściwość Ramseya jeśli dla każdej liczby naturalnej $do$ wszystkich obiektów C $\ mathbf$ ${\ Displaystyle \ mathbf {C}}$$}$ istnieje inny obiekt ${\ Displaystyle \ Delta: \ operatorname {Hom} (D, A) \ do r}$$.$ taki, że dla każdego -colouring ${\ displaystyle r$ Hom istnieje morfizm ${\ displaystyle f: D \ do B}$ dla którego ${\ Displaystyle \ operatorname {Hom} (B, A) \ circ f}$ jest ${\ Displaystyle \ Delta}$ -monochromatyczny.

Przykłady

• Twierdzenie Ramseya: klasa wszystkich skończonych łańcuchów , z mapami zachowującymi porządek jako morfizmami, ma własność Ramseya.
• twierdzenie van der Waerdena : w kategorii, której obiektami są skończone liczby porządkowe i której morfizmy są mapami afinicznymi ${\ Displaystyle x \ mapsto a + dx}$ dla za $\ Displaystyle a, d \ in \mathbb {N}}$ , ${\ Displaystyle d \ neq 0}$ , właściwość Ramseya obowiązuje dla ${\ Displaystyle A = 1}$ .
• $Displaystyle$ – Jewetta : niech będzie skończonym alfabetem i dla każdego $k \ in \ mathbb {N}}$ niech $, x_ {k-1} \}}$$ldots$ będzie zbiorem . Niech będzie kategorią, której obiektami są ${\ displaystyle \ mathbf {GR}}$${\ Displaystyle A_ {k} = L \ kubek X_ {k}}$ dla każdego ${\ Displaystyle k \ in \ mathbb {N}}$ i którego morfizmy ${\ displaystyle A_ {n} \ do A_ {k}}$ , dla ${\ Displaystyle n \ geq k}$ są funkcjami ${\ Displaystyle f: X_ {n} \ do A_ {k} }$ które są sztywne i surjektyw na ${\ Displaystyle X_ {k} \ subseteq A_ {k} = \ operatorname {codom} f}$ . Następnie ma podwójną właściwość Ramseya dla (i ${\ Displaystyle B$$R {\ Displaystyle \$$= A_ {1}}$ zależności od sol na formulacji).
• $zdefiniowana powyżej$ kategoria ma podwójną właściwość Ramseya.

Korespondencja Kechris – Pestov – Todorčević

W 2005 roku Kechris , Pestov i Todorčević odkryli następującą zgodność (zwaną dalej korespondencją KPT ) między teorią strukturalną Ramseya, teorią Fraïsségo i ideami dynamiki topologicznej.

Niech będzie grupą $topologiczną$ . $}$$przypadku$ przestrzeni przepływ ( $oznaczony$$)$ \ jest ciągłym działaniem na $_ X}$ . Mówimy, że niezwykle podatny, $G$ jakikolwiek ${\ Displaystyle G}$ -flow ${\ Displaystyle G \ curvearrowright X}$ na zwartej przestrzeni ${ \displaystyle x}$$\ Displaystyle X}$ przyznaje stały punkt ${\ Displaystyle x \ in X}$ , tj. stabilizator x to sam $G$ .

W przypadku struktury Fraïssé $)$ jej grupę automorfizmów ${\ Displaystyle \ operatorname {Aut} (\ mathbf {F})} można uznać$ grupę topologiczną, biorąc pod uwagę topologię zbieżność punktowa równoważnie topologia podprzestrzeni przez przestrzeń ${\ Displaystyle \ operatorname {Aut} (\ mathbf {F}$${\ Displaystyle \ mathbf {F} ^ {\ mathbf {F}} = \ {f: \ mathbf {F} \ do \ mathbf {F} \}} z$ topologią produktu . Poniższe twierdzenie ilustruje zgodność KPT:

Twierdzenie (KPT). W przypadku struktury Fraïssé następujące elementy są równoważne: ${\ displaystyle \ mathbf {F}}$

1. Grupa ${\ Displaystyle \ operatorname {Aut} (\ mathbf {F})}$$jest$ niezwykle podatna.
2. Klasa ${\ Displaystyle \ operatorname {Wiek} (\ mathbf {F})}$ ma właściwość Ramseya.

Zobacz też

• Teoria Ramseya
• Twierdzenie Fraïsségo
• Wiek (teoria modeli)