Teoria operacji łącznej, przemiennej i idempotentnej (Cz.3)

Niniejsza Część 3 jest kontynuacją poprzednich - oto linki:

Część 0   Część 1   Część 2

Skończoność

Teoria operacji [;\Upsilon;] jest tak prosta, że nie zawiera teorii mnogości (ani nawet pełnej logiki). Mimo to teoria ta pozwala rozważać kwestie skończoności. Jest tak dlatego, że zawiera nieskończony ciąg zmiennych:

                [;x'\ x''\ \x'''\ \ldots;]

gdzie każda następna zmienna jest cięższa od poprzedniej (ma więcej primów, co można stwierdzić fizycznie). Gdyby na przykład w pewnym jednomianie występowało nieskończenie wiele zmiennych, to żadna nie byłaby wśród nich najcięższa. Za chwilę zobaczymy, że tak jednak nie jest, czyli liczba zmiennych występujących w jednomianie jest skończona:

TWIERDZENIE 0  Wśród zmiennych występujących w dowolnym jednomianie [;A;] istnieje zmienna najcięższa.

DOWÓD  Jeżeli jednomian [;A;] jest zmienną, powiedzmy zmienną [;x;], to w [;A;] występuje dokładnie jedna zmienna (właśnie [;x;]), i jest ona najcięższa (nie ma konkurencji).

Pozostał przypadek jednomianu [;A;] postaci  [;(B\Upsilon C);].   Wtedy (indukcja) mają one swoje najcięższe zmienne, odpowiednio [;x;] w [;B;] oraz [;y;] w [;C;]. Niech [;z;] będzie tą z nich, która nie jest lżejsza od pozostałej. Zatem [;z;] występuje w [;A;] - t.zn. w  [;(B\Upsilon C);],  przy czym jest cięższe od każdej innej zmiennej, występującej w [;A;].

KONIEC DOWODU

W świetle powyższego wyniku wolno nam sformułować następujące, jednoznaczne pojęcie (będzie poprawne):

DEFINICJA 0  Ciężarem jednomianu nazywamy jego najcięższą zmienną.

UWAGA 0  Jednomiany równoważne mają tę samą wagę; patrz Część 2, Twierdzenie 1.

Na przykład ciężarem zmiennej jest ona sama.

Jednomiany standardowe

Jednomiany zostały zdefiniowane w Części 0. Jednomiany standardowe definiujemy następująco:

1. Zmienna jest jednomianem standardowym


2. Jeżeli [;A;] jest jednomianem standardowym oraz [;x;] jest zmienną cięższą od każdej zmiennej występującej w [;A;], to jednomian  [;(A\Upsilon x);]  jest standardowy.


3. Wszystkie jednomiany standardowe otrzymane są przez stosowanie powyższych dwóch metod (ich skończonych iteracji) - innych jednomianów standardowych nie ma.

Widzimy, że jednomiany standardowe są albo zmiennymi albo kończą się na pojedynczą zmienną, stanowiącą jeden z dwóch głównych członów jednomianu. Z tego powodu jednomian

            [;(x'\,\Upsilon\,(x''\Upsilon x'''));]

nie jest standardowy. Podobnie nie jest standardowy jednomian

            [;((x'\Upsilon x''')\,\Upsilon\,x'');]

Tym razem dlatego, że zmienna na zakończeniu struny nie jest najcięższa. Natomiast standardowym jest jednomian:

        [;(((x'' \Upsilon x''''')\,\Upsilon\,x'''''')\,\Upsilon\,x''''''''');]

Ogólnie, w jednomianach standardowych, od lewej do prawej, każda następna zmienna jest cięższa od poprzedniej; więc w standardowym jednomianie żadna zmienna nie występuje dwa razy.

TWIERDZENIE 1  Niech  [;A\ B;]  będą dwoma dowolnymi jednomianami standardowymi. Wtedy następujące warunki są równoważne:

1. Jednomiany  [;A\ B;]  są identyczne (jako struny, znak po znaku);


2. [;\vdash\ A\,\equiv\,B;]


3. W jednomianach  [;A\ B;]  występują dokładnie te same zmienne.

DOWÓD  Implikacja  [;1.\Rightarrow 2.;]  zachodzi na mocy aksjomatu 1.; patrz Część 0.

Implikacja  [;2.\Rightarrow 3.;]  zachodzi na mocy Twierdzenia 1 z Części 1.

Udowodnię implikację  [;3.\Rightarrow 1.;]  Gdy [;A;] jest zmienną, to [;B;], będąc standartdowe i mając te same zmienne, jest tę samą zmienną, czyli jednommiany  [;A\ B;]  są identyczne.

Zastosujmy teraz indukcję po ciężarze [;A;]. Gdy jest najlżejsze, czyli jest zmienną [;x';], to implikacja zachodzi. I ogólnie, gdy [;A;] jest zmienną. Gdy nie jest zmienną, to jest postaci  [;C\Uspilon x;], gdzie [;x;] jest zmienną, [;C;] jest jednomianem standardowym, oraz [;x;] jest cięższe od każdej zmiennej występującej w [;C;]. Ale [;B;] ma te same zmienne, więc też jest postaci  [;D\Uspilon x;], gdzie [;D;] jest jednomianem standardowym, oraz [;x;] jest cięższe od każdej zmiennej występującej w [;D;]. Ponieważ w jednomianach  [;A\ B;]  występują dokładnie te same zmienne, to także w jednomianach  [;C\ D;]  występują dokładnie te same zmienne (te co w [;A;], tylko bez [;x;]). Zatem na mocy indukcji jednomiany  [;C\ D;]  są identyczne. Zatem jednomiany  [;A\ B;]  są identyczne.

KONIEC DOWODU

Twierdzenie podstawowe

Już pora:

TWIERDZENIE 2  Dla dowolnego jednomianu istnieje dokładnie jeden równoważny mu jednomian standardowy.

DOWÓD  Niech [;A;] będzie dowolnym jednomianem. Mamy pokazać istnienie i jedyność jednomianu standardowego [;B;], takiego że

                [;A\ \equiv\ B;]

Jedyność wynika z Twierdzenia 1, powyżej. Skupmy się więc na istnieniu.

Gdy [;A;] jest zmienną, powiedzmy [;x;], to samo [;A;] jest standardowe, czyli standardowe [;B;] istnieje, jest samym [;A;].

W pozostałym przypadku, gdy [;A;] nie jest zmienną, to [;A;] jest równoważne pewnemu jednomianowi  [;(C\Upsilon x);],  gdzie [;x;] jest najcięższą zmienną, występującą w [;A;], oraz [;C;] jest jednomianem, w którym [;x;] nie występuje; patrz Część 2, Twierdzenie 2. Czyli mamy

                [;(C\,\Upsilon\,x)\ \equiv\ A;]

Przy tym jednomian [;C;] jest lżejszy od [;A;]. Istnieje więc (indukcja) jednomian standardowy [;D;], równoważny z [;C;]. Zatem:

                [;(D\,\Upsilon\,x)\ \equiv\ A;]

Więc jednomian standardowy  [;(D\,\Upsilon\,x);]  jest pożądanym jednomianem [;B;].

KONIEC DOWODU

Widzimy, że klasy równoważności jednomianów są we wzajemnie jednoznacznej odpowiedniości z niepustymi podzbiorami ciągu zmiennych

                [;x'\ x''\ \x'''\ \ldots;]

Można uważać teorię operacji [;\Upsilon;] za teorię zbiorów skończonych. Może ona jednak także sł¨żyć za odskocznię do wielu bogatszych teorii, jak logika, arytmetyka, algebra, itd.