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:
- Zmienna jest jednomianem standardowym
- 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.
- 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:
- Jednomiany [;A\ B;] są identyczne (jako struny, znak po znaku);
- [;\vdash\ A\,\equiv\,B;]
- 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.
