Część 0 oraz Część 1
Wstęp
Ze zbioru wszystkich jednomianów (patrz Część 0) wydzielimy tak zwane standardowe, tak by w każdej klasie jednomianów równoważnych znajdował się dokładnie jeden standardowy. Dzięki temu będziemy znali strukturę jednomianów kompletnie, z dokładnością do równoważności.
Zmienne i ich uporządkowanie
Przede wszystkim pamiętajmy, że mamy uporządkowany ciąg zmiennych, będziemy mówić, że coraz cięższych:
[;x'\ x''\ x'''\ x''''\ \ldots;]
Łatwo porównać wagę dwóch zmiennych, na przykład przystawiając jedną do drugiej. Ta która wystaje jest cięższa:
[;x''''''';]
[;x'''';]
Powyżej, wcześniejsza wystaje poza późniejszą, więc wcześniejsza jest cięższa.
Zmienna nie jest cięższa od samej siebie.
UWAGA 0 Uporządkowanie zmiennych nie jest absolutnie potrzebne, ale może być wygodne.
Występowanie zmiennych w jednomianach
Występowanie zmiennej w jednomianie definiujemy następująco:
- Zmienna [;x;] występuje w jednomianie [;x;].
- Zmienna [;x;] występuje w jednomianie [;(A\Upsilon B)\quad\Leftarrow:\Rightarrow\quad x;] występuje w [;A;] lub w [;B;] (lub w obu).
- Zmienna występuje w jednomianie [;\Leftarrow:\Rightarrow;] istnieje ciąg zastosowań powyższych dwóch zasad, prowadzący do takiego wniosku
Oczywiście jedna i ta sama zmienna może występować w jednomianie więcej niż raz. Tak jest na przykład w przypadku jednomianów postaci [;(A\Upsilon A);].
Niech [;x\ y;] będą dwoma różnymi zmiennymi. Powiedzmy, że zmienna [;y;] występuje w jednomianie [;A;]. Wiemy, że [;y;] albo występuje w jednomianie [;y;], i jeżeli [;A;] jest tym jednomianem, to [;A;] nie jest [;x;]. Pozostała możliwość, to występowanie [;y;] w jednomianie [;A;] postaci [;(B\Upsilon C);]. Wtedy jednomian [;A;] znowu nie jest [;x;] (ani żadną inną zmienną), gdyż na przykład zawiera nawiasy. Tym samym zakończyliśmy dowód następującego
TWIERDZENIE 0 Niech [;x\ y;] będą dwoma różnymi zmiennymi. Wtedy zmienna [;y;] nie występuje w jednomianie [;x;].
PRZYKŁAD Pokażmy, że zmienna [;x';] nie występuje w jednomianie [;C;], bedącym [;(x''\Upsilon x''';]. Rzeczywiście, jednomian ten nie jest zmienną, lecz jest postaci [;(A\Upsilon B;], gdzie jednomiany [;A\ B;] są odpowiednio zmiennymi [;x''\ x''';]. Na mocy przepisu 2 występowania w jednomianie, zmienna [;x';], żeby występować w [;C;], musiałaby występować w [;A;] lub w [;B;]. Jednak na mocy Twierdzenia 0 tak nie jest, więc zmienna [;x';] w jednomianie [;C;] nie wystepuje.
A teraz sformułuję i udowodnię dwa twierdzenia nieco poważniejsze od ważnego przecież Twierdzenia 0 :-)
TWIERDZENIE 1 Niech [;\vdash\,A\equiv B;]. Wtedy zmienna [;x;] występuje w [;A;] [;\Leftrightarrow;] [;x;] występuje w [;B;].
DOWÓD Każda równoważność otrzymana jest z reguły dowodzenia (będącej być może aksjomatem). Zatem wystarczy rozpatrzyć wszystkie 7 po kolei, przy tym zakładając (indukcyjnie), że twierdzenie zachodzi dla założeń reguł dowodzenia (dla zdań poprzedzających znaczek [;\vdash;]).
- [;A\equiv A;] — ten przypadek (gdy struny [;A;] i [;B;] są tę samą struną) jest oczywisty; zachodzi masło maślane.
- [;(A\ \equiv\ B)\ \vdash\ (B\ \equiv\ A);] — znowu przypadek oczywisty; bo nie ważne w jakiej kolejności wymieniamy dwa jednomiany, gdy mówimy o jednoczesnej przynależności zmiennej do nich obu lub do żadnego.
- [;(A\equiv B)\ (B\equiv C)\ \vdash\ (A\equiv\ C);] — zmienna występuję w [;A;] [;\Leftrightarrow;] wystepuje w [;B;] [;\Leftrightarrow;] wystepuje w [;C;].
- [;\vdash\ (A\Upsilon A)\ \equiv\ A;] — ten przypadek zachodzi na mocy zasady 2. przynależności zmiennej do jednomianu (patrz powyżej).
- [;\vdash\ (A\Upsilon B)\ \equiv\ (B\Upsilon A);] — rzeczywiście, nie ważne w jakiej kolejności wymieniamy dwa jednomiany, gdy mówimy o przynależności zmiennej do jednego z nich - ważne że do jednego z nich przynależy (lub nie)
- [;\vdash\ ((A\Upsilon B)\Upsilon C)\ \equiv\ (A\Upsilon(B\Upsilon C));] — zmienna występuje w lewym jednomianie [;\Leftrightarrow;] wystepuje w prawym, gdyż w obu wypadkach jest tak, gdy występuje przynajmniej w jednym z trzech jednomianów [;A\ B\ C;].
- [;(A\equiv B)\ \vdash\ ((A\Upsilon C)\, \equiv\, (B\Upsilon C));] — chcemy pokazać, że gdy zachodzi równoważność [;(A\equiv B);], to zmienna występuje w [;(A\Upsilon C)\ \ \Leftrightarrow;] występuje w [;(B\Upsilon C);]. Mamy trzy przypadki. Gdy zmienna występuje w [;C;] to teza zachodzi, bo [;C;] jest częścią obu jednomianów na prawo od [;\vdash;]. Drugi przypadek, gdy zmienna występuje w [;(A\Upsilon B);] na konto występowania w [;A;]. Na mocy założenia [;A\equiv B;], występuje wtedy ta zmienna także w [;B;]. Zatem występuje w jednomianie [;(B\Upsilon C);] (tym po prawej). Podobnie w trzecim wypadku, gdy zmienna występuje w [;(B\Upsilon C);] dzięki temu, że występuje w [;B;], pokazujemy, że występuje także w [;(A\Upsilon C);] (czyli po stronie lewej).
Powyższe twierdzenie mówi nam, że dla dwóch równoważnych jednomianów zbiór występujących w nich zmiennych jest ten sam. W dalszym ciągu niniejszej noty okaże się, że i na odwrót, gdy zbiór zmiennych jest ten sam, to dwa jednomiany są równoważne (innymi słowy, nierównoważne jednomiany różnią się zbiorem występujących w nich zmiennych - pewna zmienna występuje w jednym z nich, ale nie w drugim). Żeby to udowodnić, to pierwszym krokiem, chyba głównym, będzie poniższe Twierdzenie 2. Jeszcze wtrącę uwagę o tym, że mówienie o zbiorach jest tylko dla podtrzymania uwagi czytelnika - ani w teorii operacji {;\Upsilon;}, ani w metateorii tej teorii nie mamy symboli mnogościowych, nie mamy pojęcia zbioru, i w szczególności nie mamy pojęcia skończoności. A żyć trzeba :-) Damy sobie z tym wszystkim radę wkrótce, bo zamiast niepustych, skończonych zbiorów zmiennych będziemy mieć jednomiany standardowe.
TWIERDZENIE 2 Niech [;x\ A;] będą odpowiednio dowolną zmienną i dowolnym jednomianem. Wtedy albo [;x;] nie występuje w [;A;], albo [;A;] jest [;x;], albo istnieje jednomian [;B;], w którym [;x;] nie występuje, i taki, że zachodzi twierdzenie teorii:
[;\vdash\ (B\,\Upsilon\,x)\ \equiv\ A;]
DOWÓD Jeżeli [;x;] nie występuje w [;A;], to Twierdzenie 2 zachodzi. Odtąd będziemy więc rozpatrywać przypadek w którym [;x;] występuje w [;A;].
Jeżeli jednomian [;A;] jest zmienną, to na mocy Twierdzenia 0 wiemy, że [;A;] jest zmienną [;x;], i wtedy Twierdzenie 2 zachodzi.
Pozostał przypadek, w którym zmienna [;x;] występuje w jednomianie [;A;], przy czym jednomian ten nie jest zmienną. Istnieją wtedy jednomiany [;B\ C;] takie, że [;A;] jest [;(B\Upsilon C);] (więc [;x;] musi występować przynajmniej w jednym z jednomianów [;B\ C;]). Wtedy (indukcja) jednomiany [;B\ C;] spełniają Twierdzenie 2, czyli mamy następujące podprzypadki:
- Zmienna [;x;] nie występuje w [;B;], oraz jednomian [;C;] jest [;x;] - wtedy Twierdzenie 2 zachodzi.
- Zmienna [;x;] nie występuje w [;B;], oraz jednomian [;C;] nie jest [;x;] - wtedy (indukcja) istnieje jednomian [;D;], w którym [;x;] nie występuje, przy czym zachodzi
[;\vdash\ (D\,\Upsilon\,x)\ \equiv\ C;]
Wtedy
[;\vdash\ (B\,\Upsilon\,(D\,\Upsilon\,x))\ \equiv\ (B\,\Upsilon\,C);]
Ale prawa strona to po prostu [;A;] (dosłownie, jako struna, znak po znaku). Czyli otrzymaliśmy:
[;\vdash\ (B\,\Upsilon\,(D\,\Upsilon\,x))\ \equiv\ A;]
Ponieważ (łączność operacji [;\Upsilon;])
[;\vdash\ ((B\,\Upsilon\,D)\,\Upsilon\,x)\ \equiv\ (B\,\Upsilon\,(D\,\Upsilon\,x));]
to ostatecznie:
[;\vdash\ ((B\,\Upsilon\,D)\,\Upsilon\,x)\ \equiv\ A;]
Zatem Twierdzenie 2 zachodzi, gdzie istniejące [;B;] jest jednomianem [;(B\,\Upsilon\,D);] - zauważmy, że zmienna [;x;] nie występuję w [;(B\,\Upsilon\,D);], gdyż nie występuje ani w [;B;] ani w [;D;]. - Zmienna [;x;] nie występuję w [;C;] - ponieważ operacja [;\Upsilon;] jest przemienna, to podprzypadek ten sprowadza sie do poprzednich, kiedy to [;x;] nie występowało w [;B;]; mamy bowiem ciąg:
[;\vdash\ (C\Upsilon B)\,\equiv\,(B\Upsilon C);]
[;\vdash\ (E\Upsilon x)\,\equiv\,(B\Upsilon C);]
czyli
[;\vdash\ (E\Upsilon x)\,\equiv\,A;]
dla pewnego jednomianu [;E;], w którym nie występuje [;x;]. - Pozostały (pod)przypadki, kiedy [;x;] występuje w obu jednomianach [;B\ C;]. Wtedy mamy cztery dalsze (pod)podprzypadki (gdyby stosować pustą strunę, to zlałyby się one w jeden):
- Jednomiany [;B\ C;] są oba zmienną [;x;] - Wtedy [;A;] jest jednomianem [;(x\Upsilon x);], który jest równoważny jednomianowi [;x;], czyli Twierdzenie 2 znowu zachodzi.
- Jednomian [;C;] jest [;x;], ale [;B;] nie jest - wtedy istnieje jednomian [;D;], w którym [;x;] nie występuje, taki, że
[;\vdash\ (D\Upsilon x)\ \equiv B;]
tak, że po kolei dostajemy:
[;\vdash\ ((D\Upsilon x)\,\Upsilon\,x)\ \equiv A;]
[;\vdash\ (D\Upsilon\,(x\Upsilon x))\ \equiv A;]
[;\vdash\ (D\Upsilon\,x)\ \equiv A;]
Więc Twierdzenie 2 zachodzi. - Jednomian [;B;] jest [;x;], ale [;C;] nie jest - wtedy istnieje jednomian [;D;], w którym [;x;] nie występuje, taki, że
[;\vdash\ (D\Upsilon x)\ \equiv C;]
tak, że po kolei dostajemy:
[;\vdash\ (x\,\Upsilon\,(D\Upsilon x))\ \equiv A;]
[;\vdash\ ((D\Upsilon x)\,\Upsilon\,x)\ \equiv A;]
[;\vdash\ (D\Upsilon\,(x\Upsilon x))\ \equiv A;]
[;\vdash\ (D\Upsilon x) \equiv A;]
Więc Twierdzenie 2 zachodzi. - Ani [;B;] ani [;C;] nie jest [;x;] - wtedy istnieją jednomiany [;D\ E;], w których [;x;] nie występuje, i takie, że
[;\vdash\ (D\Upsilon x)\ \equiv B;]
[;\vdash\ (E\Upsilon x)\ \equiv C;]
tak, że po kolei dostajemy:
[;\vdash\ ((D\Upsilon x)\,\Upsilon\,(E\Upsilon x))\ \equiv A;]
[;\vdash\ (D\Upsilon\,(x\,\Upsilon\(E\Upsilon x)))\ \equiv A;]
[;\vdash\ (D\Upsilon\,((x\Upsilon\E)\,\Upsilon x)))\ \equiv A;]
[;\vdash\ (D\Upsilon\,((E\Upsilon x)\Upsilon x))\ \equiv A;]
[;\vdash\ (D\Upsilon\,(E\Upsilon\,(x\Upsilon x)))\ \equiv A;]
[;\vdash\ (D\Upsilon\,(E\Upsilon x))\ \equiv A;]
[;\vdash\ ((D\Upsilon\,E)\Upsilon x)\ \equiv A;]
Więc Twierdzenie 2 zachodzi.
No comments:
Post a Comment