Teoria Ramseya

Wygląd przypnij ukryj

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.

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”.

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

1. ↑ Eric W.E.W. Weisstein Eric W.E.W., Ramsey Theory, MathWorld, Wolfram Research   (ang.).
2. ↑ Hans Jürgen Prömel (2005). „Complete Disorder is Impossible: The Mathematical Work of Walter Deuber”. Combinatorics, Probability and Computing (Cambridge University Press) 14: 3–16.

Linki zewnętrzne

• Największa liczba na świecie Portal popularnonaukowy miesięcznika „Delta” .

Działy matematyki dyskretnej

kombinatoryka	teoria Ramseya
teoria grafów	algebraiczna geometryczna spektralna topologiczna
inne	geometria dyskretna geometria kombinatoryczna geometria skończona kryptologia logika matematyczna teoria gier działy algebry abstrakcyjnej działy algorytmiki działy teorii liczb

Działy matematyki

działy ogólne	według trudności matematyka elementarna matematyka wyższa według celu matematyka czysta matematyka stosowana inne matematyka doświadczalna matematyka parakonsystentna supermatematyka
działy czyste	algebra elementarna liniowa i wieloliniowa abstrakcyjna algebra przemienna algebra lokalna teoria Galois różniczkowa teoria Galois teoria grup geometryczna teoria grup teoria Liego homologiczna różniczkowa uniwersalna teoria reprezentacji analiza matematyczna analiza algebraiczna analiza funkcjonalna teoria spektralna analiza geometryczna analiza globalna analiza harmoniczna analiza mikrolokalna analiza na rozmaitościach analiza niestandardowa analiza numeryczna nomografia analiza p-adyczna analiza rzeczywista analiza wektorowa analiza wielowymiarowa analiza wypukła analiza zespolona rachunek różniczkowy i całkowy rachunek wariacyjny teoria dystrybucji teoria miary teoria potencjału arytmetyka elementarna teoretyczna lub wyższa, in. teoria liczb algebraiczna algorytmiczna analityczna elementarna geometryczna teoria sit geometria absolutna afiniczna algebraiczna analityczna arytmetyczna diofantyczna dyskretna euklidesowa planimetria stereometria fraktalna inwersyjna kombinatoryczna konforemna metryczna nieeuklidesowa eliptyczna hiperboliczna sferyczna nieprzemienna obliczeniowa różniczkowa symplektyczna rzutowa skończona syntetyczna tropikalna uporządkowania wykreślna zespolona trygonometria sferyczna matematyka dyskretna kombinatoryka teoria Ramseya teoria grafów algebraiczna geometryczna spektralna topologiczna podstawy logika matematyczna algebraiczna mereologia rachunek zdań teoria dowodu teoria modeli teoria rekursji teoria typów metamatematyka metalogika teoria kategorii teoria mnogości opisowa arytmetyka liczb kardynalnych arytmetyka liczb porządkowych teoria PCF teoria obliczeń teoria obliczalności teoria złożoności teoria układów dynamicznych teoria chaosu teoria katastrof teoria ergodyczna topologia algebraiczna teoria homotopii geometryczna mnogościowa ogólna różniczkowa teoria Morse’a teoria położenia teoria węzłów teoria warkoczy teoria wymiaru pozostałe K-teoria probabilistyka rachunek różnicowy teoria osobliwości teoria porządku teoria punktu stałego
działy stosowane	nauki przyrodnicze biomatematyka chemia matematyczna fizyka matematyczna nauki społeczne ekonomia matematyczna lingwistyka matematyczna matematyka finansowa matematyka ubezpieczeniowa psychologia matematyczna socjologia matematyczna teoria głosowań nauki techniczne kryptologia teoria informacji teoria kolejek teoria sterowania statystyka matematyczna rachunek wyrównawczy statystyka nieparametryczna teoria estymacji inne teoria gier teoria decyzji
powiązane dyscypliny	ściśle naukowe dydaktyka matematyki historia matematyki inne filozofia matematyki matematyka rekreacyjna numerologia pseudomatematyka