Funkcje ancestralne jednej zmiennej

Niech będą dane dwa dowolne sądy A(λ), B(α, λ), które zawierają wyszczególnione w nawiasach zmienne. Wszystkie pojęcia, które w dalszym ciągu wprowadzimy, będą zależne od tych sądów i dlatego przy ich określaniu powinniśmy zawsze dodawać: "względem sądów A(λ), B(α, λ)". Uzupełnienie to będziemy jednak stale pomijać, jeśli nie zachodzić będzie obawa o dwuznaczność.

Df. 1a. Jeśli wyrażenie U spełnia warunek A(U), to wyrażenie ∗ U0 nazywać będziemy wyrażeniem zerowym.

Df. 2a. Jeśli wyrażenia X, U spełniają warunek B(X,U), a N jest zupełnie dowolnym wyrażeniem, to powiemy, że wyrażenie ∗U∗0N jest pochodnym od wyrażenia ∗XN.

Przypuśćmy, że np., zachodzą związki: A(X0), B (X0,X1) B(X1,X2), B(X2,X3). Utwórzmy ciąg wyrażeń: ∗X00, ∗X1∗00, ∗X2∗0∗00, ∗X3∗0∗0∗00. Widzimy, że pierwsze z wyrażeń tego ciągu jest wyrażeniem zerowym, a każde następne jest wyrażeniem pochodnym od poprzedniego.

Df. 3a. Wyrażenie E nazywać będziemy wyrażeniem lub zbiorem regularnym, jeśli każdy jego element jest wyrażeniem zerowym lub pochodnym od innego elementu wyrażenia E. Tak np. zbiór utworzony z czterech wyrażeń naszego ciągu jest zbiorem regularnym.

Df. 4a. Powiemy, że wyrażenie U ma wykładnik ancestralny N, jeśli istnieje zbiór regularny, którego elementem jest wyrażenie ∗ U N. Tak np. wyrażenia X0, X1 X2, X3 mają kolejno wykładniki ancestralne: 0, ∗00, 0 ∗00, ∗0∗0 ∗00. Dane wyrażenie może mieć oczywiście na ogół kilka lub nawet nieskończenie wiele wykładników ancestralnych.

Df. 5a. Funkcję ancestralną Φ (λ) określamy jako sąd: wyrażenie λ posiada przynajmniej jeden wykładnik ancestralny. Przechodzimy do dowodu czterech podstawowych twierdzeń o funkcji ancestralnej Φ (λ).

Tw. 1a. Wyrażenie U spełniające związek A (U) posiada własność Φ (U) (symbolicznie ⊦ ⊃ A(λ)Φ(λ)).

Dowód: Założenie nasze pozwała stwierdzić, że wyrażenie ι' ∗U0 jest zbiorem regularnym. Wyrażenie U posiada zatem wykładnik ancestralny 0, a stąd wnioskujemy, że zachodzi Φ (U).

Tw. 2a. Jeśli wyrażenia X, U spełniają związki: Φ (X), B (X, U), to wyrażenie U posiada własność Φ (U) (symbolicznie: ⊦ ⊃ ∧Φ(α)B(α,λ)Φ(λ)).

Dowód: Z założenia naszego wynika, że X posiada przynajmniej jeden wykładnik ancestralny. Oznaczmy go przez N. Istnieje zatem zbiór regularny E, którego elementem jest wyrażenie ∗ XN. Oznaczamy przez F sumę zbiorów: E, ι' ∗ U ∗ 0N. Suma taka istnieje na mocy twierdzenia § 2 Widzimy natychmiast, że F jest zbiorem regularnym, a wyrażenie ∗ U ∗ ON jego elementem. Stąd wniosek, że U posiada wykładnik ancestralny ∗ 0N, a więc zachodzi Φ (U).

Tw. 3a. Jeśli wyrażenie U posiada własność Φ (U), to U spełnia warunek A (U) lub też istnieje wyrażenie X spełniające wiązki Φ (X), B (X, U)

(symbolicznie: ⊦ ⊃ Φ (λ)∨A(λ)∃α∧Φ(α)B(α,λ).

Dowód: Z założenia naszego wynika, że U posiada przynajmniej jeden wykładnik ancestralny. Oznaczmy go przez N. Istnieje zatem zbiór regularny E, którego elementem jest wyrażenie ∗UN. Wyrażenie to jest albo pierwotnym (gdy = N0) i wówczas mamy A (U), albo też zbiór E posiada element kształtu ∗ XM spełniający związek B (X, U), = N∗0M. W tym drugim wypadku mamy oczywiście Φ (X) gdyż X posiada wykładnik ancestralny M.

Tw. 4 a. Zakładamy, ze sąd Ψ (λ) spełnia następujące dwa warunki: 1) każde wyrażenie U spełniające związek A (U) posiada własność Ψ (U), 2) jeśli układ wyrażeń X, U spełnia związki: Ψ (X), B(X, U), to wyrażenie U posiada własność Ψ (U), Twierdzimy, że wszystkie wyrażenia spełniające związek Φ (U) posiadają własność Ψ (U).

W postaci symbolicznej twierdzenie nasze przybiera kształt następującej reguły postępowania.

Jeśli zachodzą twierdzenia: F ⊦ ⊃ A(λ) Ψ (λ), ⊦ ⊃ ∧ Ψ(α) (α,λ) Ψ (λ), to zachodzi również twierdzenie ⊦ ⊃ Φ(λ) Ψ (λ).

Dowód: Oznaczamy przez F (ν) sąd: "wszystkie wyrażenia U o wykładniku ancestralnym zawartym w ν mają własność Ψ (U)" Posługując się regułą indukcji semantycznej wykażemy najpierw, że sąd F(ν) zachodzi dla każdego wyrażenia ν.

I. Aby udowodnić F(0) przypuszczamy, że wyrażenie U posiada wykładnik ancestralny zawarty w wyrażeniu 0, a więc równy 0. Istnieje zatem zbiór regularny E, którego elementem jest wyrażenie ∗UO. Ponieważ wyrażenie to nie może być wyrażeniem pochodnym, więc musi zachodzić A (U) a na mocy założenia 1) Ψ (U).

II. Przypuszczamy teraz, że zachodzą związki: F(M) , F(N). Aby wykazać, że mamy także F(∗MN) zakładamy, że wyrażenie U posiada wykładnik ancestralny W spełniający warunek { ∗MNW}, Są zatem możliwe 3 wypadki: a) {MW}, b) {NW}, c)= W ∗MN.

W dwóch pierwszych stwierdzamy Ψ (U) na podstawie założeń F(M), F(N). W wypadku c) wyrażenie ∗U ∗MN jest elementem pewnego regularnego zbioru E. Ponieważ ∗ U ∗ MN nie jest wyrażeniem zerowym, możemy znaleźć w E element kształtu ∗XN spełniający związek B(X,U). Wynika stąd, że wyrażenie X posiada wykładnik ancestralny zawarty w N, a więc mamy Ψ (X) ze względu na założenie F(N). Jeśli uwzględnimy ponadto związek B(X,U) to na mocy założenia 2) otrzymamy w końcu Ψ (U).

Wykazaliśmy w ten sposób, że wszystkie wyrażenia U o wykładniku ancestralnym zawartym w ν mają własność Ψ (U), przy czym ν jest zupełnie dowolnym wyrażeniem. Aby wykazać słuszność Tw. 4 a. zakładamy teraz, że zachodzi Φ (U). Wyrażenie U posiada zatem przynajmniej jeden wykładnik ancestralny. Oznaczmy go przez N. Korzystając ze związków F (N), {NN}, wnioskujemy natychmiast Ψ (U).

Zajmiemy się teraz uogólnieniem naszej metody konstrukcji. Rozważymy najpierw wypadek gdy dane sądy wyjściowe mają kształt: A(λ), B (αβ,λ). Definicje wszystkich pojęć poprzednio wprowadzonych ulegną w tym wypadku nieznacznym zmianom:

Df. 1b. Jeśli wyrażenie U spełnia warunek A(U), to wyrażenie ∗U0 nazywać będziemy wyrażeniem zerowym.

Df. 2b. Jeśli wyrażenia X,Y,U spełniają warunek B (X Y, U) , a M, N są zupełnie dowolnymi wyrażeniami, to powiemy, że wyrażenie ∗ U ∗ ∗0MN jest pochodnym od wyrażeń ∗XM, ∗ YN.

Df. 3b. Wyrażenie E nazywać będziemy wyrażeniem lub zbiorem regularnym, jeśli każdy jego element jest wyrażeniem zerowym lub pochodnym od dwóch innych elementów wyrażenia E.

Df. 4b. Powiemy, że wyrażenie U ma wykładnik ancestralny N jeśli istnieje zbiór regularny, którego elementem jest wyrażenie ∗U N.

Df. 5b, Funkcję ancestralną Φ(λ)określamy jako sąd: wyrażenie λ posiada przynajmniej jeden wykładnik ancestralny.

Widzieliśmy już poprzednio, że w konstrukcji funkcji ancestralne podstawową rolę odgrywa pojęcie wykładnika ancestralnego, który mieści w sobie całą "historię" danego wyrażenia. Dokładnie to samo możemy powiedzieć o wypadku rozważanym obecnie. Tak np. wyrażenie X o wykładniku ancestralnym

∗ ∗0∗ ∗000∗ ∗0∗ ∗0000;
musi spełniać związek B (X1 X2, X), przy czym X1, X2 są wyrażeniami o wykładnikach ∗ ∗ 000, ∗ ∗ 0∗ ∗ 0000. Prowadząc dalej powyższe rozumowanie dojdziemy w końcu do wyrażeń o wykładniku 0. Rozumowanie całe możemy ująć w przejrzysty schemat:


Zdjęcie zrobione bezpośrednio z broszury

z którego można odczytać, że wyrażenia dolnego wiersza spełniają warunek A(λ), a każde inne wyrażenie czyni zadość warunkowi B(αβ,λ) z dwoma wyrażeniami znajdującymi się niżej z którymi jest na rysunku połączone, n. p. B (X211X212, X21).

Zbiór utworzony ze wszystkich wyrażeń umieszczonych na rysunku jest zbiorem regularnym. Widzimy łatwo, że straci on natychmiast tę własność jeśli usuniemy z niego choć jedno wyrażenie za wyjątkiem wyrażenia X.

Zajmiemy się teraz układem czterech podstawowych twierdzeń, którym czyni zadość wprowadzona funkcja ancestralna Φ(λ). Ponieważ dowody tych twierdzeń uzyskujemy na drodze zupełnie analogicznej jak w wypadku poprzednio dyskutowanym (gdy funkcje wyjściowe miały kształt; A(λ), B(αλ) więc ograniczymy się tutaj do samego sformułowania naszych twierdzeń:

Tw: 1b. Wyrażenie U spełniające związek A (U) posiada własność Φ (U) (symbolicznie: ⊦ ⊃ A(λ) Φ (λ)).

Tw. 2b. Jeili wyrażenia X, Y, U, spełniają związki: Φ (X), Φ (Y), B (X Y, U) , to wyrażenie U posiada własność Φ (U). (symbolicznie: ⊦ ⊃ ∧Φ(α)∧Φ(β)B(αβ,λ Φ(λ)).

Tw. 3b. Jeśli wyrażenie U posiada własność Φ(U), to U spełnia warunek A (U) lub też istnieją wyrażenia X,Y spełniające związki: Φ(X), Φ (Y) , B(XY, U) (symbolicznie: ⊦ ⊃ Φ(λ)∨ A(λ)⋿ab∧Φ(α)∧Φ(b)B(ab,λ)).

Tw. 4 b. Zakładamy, że sąd Ψ (X) spełnia następujące dwa warunki:

1) każde wyrażenie U spełniające związek A (U) posiada własność Φ (U),

2) jeśli układ wyrażeń X ,Y, U spełnia związki: Φ (X), Φ (Y), B(XY, U), to wyrażenie U posiada własność Φ (U).

Twierdzimy, że wszystkie wyrażenia spełniające związek Ψ(U) posiadają własność Φ (U).

Z punktu widzenia formalnego systemu Tw. 4b. stanowi następującą regułą postępowania:

Jeśli zachodzą twierdzenia: ⊦ ⊃ A(λ) Ψ (λ), ⊦ ⊃ ∧ Ψ(α)∧Ψ(β)B(αβ,λ) Ψ(λ), to zachodzi również twierdzenie ⊦ ⊃ Φ (λ) Ψ (λ).

Dalsze uogólnienia naszej metody nie nastręczają żadnych trudności. Pozwala nam ona zbudować funkcję ancestralną Φ (λ) dla układów sądów wyjściowych: A (λ), B(αβγ,λ) ; A (λ), B(αβγδ,λ) itd.

Dla każdego z takich układów wprowadzamy w sposób zupełnie analogiczny pięć podstawowych definicji i udowadniamy cztery podstawowe twierdzenia, którym czyni zadość funkcja ancestralna Φ (λ).