Teoria Ramseya

Teoria Ramseya – dział matematyki, nazwany tak na cześć brytyjskiego matematyka i filozofa Franka Ramseya. Teoria ta bada warunki, pod którymi porządek musi się pojawić. Zajmuje się poszukiwaniem regularności, które pojawiają się w przypadkowych nieuporządkowanych obiektach, jeśli te zwiększają się, ogólnych warunków istnienia pod-struktur z regularnymi własnościami^[1].

Typowymi problemami tej teorii są odpowiedzi na pytania: „jak wiele elementów pewnej struktury musi wystąpić, aby zaszła poszczególna własność.” Z teorii tej wynika wniosek przypisywany Theodore’owi Motzkinowi: „zupełny nieporządek jest niemożliwy”^[2].

Kluczowe twierdzenia

• Twierdzenie Ramseya (1930)
• Twierdzenie Van der Waerdena (1927) – Dla każdej danej dodatniej całkowitej liczby c oraz n, istnieje liczba V, taka że jeśli ciąg złożony z następujących po sobie V liczb jest pokolorowany na c różnych kolorów, wówczas ciąg ten musi zawierać podciąg o postępie arytmetycznym o długości n, taki, że jego elementy są tego samego koloru. Oznacza to, że kolorując kolejne liczby na pewną liczbę kolorów, przy pewnej (być może znacznej) długości ciągu uzyskamy pewien rodzaj regularności (nie ma „ucieczki w idealny chaos” przed tym specyficznym porządkiem, jeśli odpowiednio zwiększymy V).
• Twierdzenie Halesa–Jewitta (1963)
• Twierdzenia Schura (1916)
• Twierdzenie Rado (1943)

Wyniki

Wyniki w teorii Ramseya mają zwykle dwie główne cechy:

• Po pierwsze są niekonstruktywne: mogą wykazać, że pewna struktura istnieje, ale nie przedstawiają procesu, w jaki ta struktura mogłaby zostać odnaleziona (innego niż przeszukiwanie „brute force”). Przykład: zasada szufladkowa Dirichleta.
• Po drugie, mimo że wyniki teorii Ramseya stwierdzają, że wystarczająco wielki obiekt musi koniecznie zawierać daną strukturę, to jednak często dowód tych wyników wymaga, by te obiekty były niezwykle wielkie – ograniczenia rosną wykładniczo, a nawet nierzadko tak szybko, jak funkcja Ackermanna. W wielu przypadkach ograniczenia te uzyskuje się z dowodów twierdzeń i nie jest wiadomo, czy mogą być znacząco poprawione. W innych przypadkach jest wiadomo, że jakiekolwiek istniejące ograniczenie musi być niezwykle wielkie, czasem nawet większe niż jakakolwiek funkcja pierwotnie rekurencyjna. Liczba Grahama, która jest jedną z największych liczb kiedykolwiek użytych w poważnym matematycznym dowodzie, jest górnym ograniczeniem problemu związanego z teorią Ramseya.

Zobacz też

• Bartel Leendert van der Waerden
• kombinatoryka

Przypisy

Linki zewnętrzne

• Największa liczba na świecie Portal popularnonaukowy miesięcznika „Delta” [dostęp 2021-09-01].