7738996297

Twierdzenie 8 (Ramseya). Mamy dany pełny graf nieskierowany, którego wierzchołkami są liczby naturalne. Ponadto każda krawędź (i,j) (ponieważ krawędzie są nieskierowane, to zakładamy, że i < j) jest pokolorowana kolorem a(i,j) € K, gdzie K jest skończonym zbiorem kolorów. Wówczas istnieje zbiór nieskończony XCN oraz kolor k € K takie, że

Vijex a(i,j) = k.

Dowód (kluczowego lematu)

Niech w = a\a2a^.... Zdefiniujmy a : [N]² —» M następująco:

a({i < j}) = M_ai..._aj-, dla i < j

Na mocy tw. Ramseya istnieją: nieskończony zbiór I C N oraz macierz N € M takie, że:

Vije7, i<ja(i,j) = N

Niech / = {ii,*2, *3,...}. Zdefiniujmy skończone słowa

Vo = ai • • -ań-i Ui = a,,...aj₂_i U2 =    .. .<łi₃_i    •••

Niech Ni macierz opisująca słowo u,. Wiemy, że wszystkie macierze Nj są równe dla i > 1. Wybierzmy sobie

M = N₀ -Ni N = Ni = N₂ = • • •

Macierze te odpowiadają podziałowi

W = W0W1W2 ■ ■ ■ dla Wo = VoVi W\ = V2 U>2 = «3 Aby zakończyć dowód, trzeba jescze pokazać warunki na mnożenie macierzy z tezy lematu:

N • N = Ni ■ N2 = N z tezy tw. Ramseya

□

Powiemy, że para macierzy N,M spełnia warunek (*) jeśli istnieje q € Q takie, że:

•    M(qj,q) ,^-L dla stanu inicjalnego qi automatu A

•    N{q,q) = 1

Lemat 9 (Charakteryzujący). Ustalmy niedeterministyczny automat z warunkiem Biichiego A oraz słowo w € A^u. Niech macierze M,N i podział w = WqW\W2-.. będą takie, jak w dowodzie kluczowego lematu. Wówczas słowo w jest akceptowane przez automat A wtedy i tylko wtedy gdy macierze M, N dodatkowo spełniają warunek (*).

Dowód

Dowód implikacji (4=) jest oczywisty — warunek (*) wprost przekłada się na istnienie biegu akceptującego. Przejdźmy więc do implikacji (=>).

Rozważmy bieg akceptujący automatu A na słowie w. Niech ę, oznacza stan automatu w tym biegu po przeczytaniu prefiksu wowi.. .Wj. Ponieważ macierz opisująca ten prefiks to M (z założenia MN = M), wnioskujemy, że M(qi,qi) j=- -L dla każdego i > 1. Wówczas istnieje taki stan q, że q = ę, dla nieskończenie wielu i (niech I będzie zbiorem takich właśnie i). W szczególności M(qj,q) ^ więc spełniona jest pierwsza część warunku (*). Ponieważ jest to też bieg akceptujący, to nieskończenie często pojawia się w tym automacie pewien stan akceptujący /. Zatem można wybrać taki nieskończony zbiór J C /, J = {jo, ji, J2, • • ■}, że dla każdego k stan akceptujący / pojawia się podczas czytania przez automat podsłowa Wj_h+1... Wj_k+1. Innymi słowy, macierz słowa u>j_k+1.. -Wj_k+l ma 1 w komórce (q,q). Ponieważ ta macierz to N, mamy N(q,q) = 1, więc spełniona jest druga część warunku (*). □

16