Funkcje ancestralne wielu zmiennych

W rozdziale poprzednim zajmowaliśmy się wyłącznie funkcjami ancestralnymi jednej zmiennej. Funkcje takie budujemy przy pomocy dwóch sądów wyjściowych, przy czym sąd A zawiera zawsze jedną tylko wyróżnioną zmienną λ. W sądzie B wyróżniamy dwie zmienne: α, λ trzy zmienne: α, β, λ lub też większą ich ilość. Rozważane zatem dotąd sądy wyjściowe miały kształt:

A(λ), B1, χ 2,... χ n, λ).

Należy tutaj podkreślić, że sądy powyższe mogą, prócz zmiennych wyszczególnionych w nawiasach, zawierać dalsze zmienne, które nazywamy parametrami. Widzieliśmy, że sądy wyjściowe pozwalają nam w każdym konkretnym wypadku skonstruować funkcję ancestralną jednej zmiennej Φ (λ), która oprócz zmiennej λ może zawierać parametry występujące w sądach wyjściowych. Wykazaliśmy wreszcie, że funkcja Φ (λ) czyni zadość układowi czterech podstawowych twierdzeń o charakterze indukcyjnym. Twierdzenia te udowodniliśmy jedynie w wypadku n = 1, ale zupełnie analogiczne dowody możemy przeprowadzić dla każdej liczby naturalnej n > 1.

W zastosowaniach praktycznych spotykamy się często z funkcjami ancestralnymi 2, 3 i większej ilości zmiennych. W wypadku najogólniejszym sądy wyjściowe mają kształt:

A1, λ m), B11.. χ 1m, χ 21.. χ 2m,... χ n1.. χ nm; λ 1.. λ m)

Sądy te wyznaczają znów pewną funkcję ancestralną Φ 1, λ m). Wykażemy, że konstrukcja tej funkcji, zarówno jak i dowody czterech podstawowych twierdzeń dadzą się sprowadzić do wypadku prostszego, który rozważaliśmy w § 3. Ponieważ metoda redukcji, którą przeprowadzimy, daje się zastosować dla dowolnej zupełnie pary liczb naturalnej n, m (m >1), ograniczymy się tutaj do najprostszego wypadku: n = 1, m = 2. Sądy wyjściowe mają w tym wypadku kształt:

A1, λ 2), B11, λ 2)

Oznaczamy przez A'(λ) sąd: "istnieją wyrażenia L1, L2 spełniające związki: =λ ∗ ∗0L1 L2, A(L1 L2)"

Podobnie określamy sąd B'(α,λ): "istnieją wyrażenia A1, A2, L1, L2 spełniające związki: =α ∗ ∗0 A1 A2, = λ ∗ ∗0 L1 L2 B(A1, A2; L1, L2)

Na podstawie rozważań § 3 potrafimy zbudować funkcję ancestralną Φ'(λ) dla sądów wyjściowych A'(λ), B'(α, λ). Określamy teraz funkcję Φ1, λ 2) jako sąd Φ'(∗ ∗0λ 1 λ 2). Widzimy z łatwością, że pomiędzy wprowadzonymi sądami zachodzą związki:

⊦≣A(λ 1 λ 2) A'(∗∗0λ 1 λ 2)
⊦≣B(α1α21 λ 2) B'(∗∗0α1α2,∗∗0λ 1 λ 2)

Wykażemy, że funkcja Φ(λ1, λ2) czyni zadość układowi czterech podstawowych twierdzeń zupełnie analogicznych do układu twierdzeń 1a - 4a.

Tw. 1c. Wyrażenia U1, U2 spełniające związek A(U1 U2) posiadają własność Φ (U1 U2) (symbolicznie: ⊦ ⊃ A(λ12) Φ (λ12))

Dowód: Na mocy twierdzeń (1) założenie A(U1 U2) pociąga za sobą A' (∗ ∗ 0 U1 U2), a stąd na podstawie Tw. 1a. wnioskujemy, że zachodzi Φ '(∗ ∗ 0 U1 U2) czyli Φ (U1 U2).

Tw. 2c. Jeśli wyrażenia X1 X2 , U1,U2 spełniają związki Φ (X1 X2) B(X1 X2; U1 U2, to wyrażenia U1, U2 posiadają własność "Φ (U1 U2)
(symbolicznie: ⊦⊃∧Φ(α1α2)B(α1α212)Φ(λ12)).

Dowód: Na mocy twierdzeń (1) założenia nasze pociągają za sobą związki: Φ( ∗∗0X1 X2), B'(∗ ∗ 0 X1 X2,∗ ∗ 0 U1 U2), a stąd na podstawie Tw. 2 a. wnioskujemy, że zachodzi Φ'( ∗ ∗0 U1 U2) czyli Φ( U1 U2).

Tw. 3c. Jeśli wyrażenia U1, U2 posiadają własność Φ (U1 U2), to U1, U2 spełniają warunek A(U1 U2) lub tez istnieją wyrażenia X1, X2 spełniające związki: Φ (X1 X2), B (X1 X2; U1U1)
(symbolicznie: ⊦ ⊃ Φ(λ1λ2)∨ A(λ1λ2)∃a1a2∧Φ(a1a2)B(a1a21λ2)).

Dowód: Z założenia naszego wynika Φ '(∗ ∗ 0 U1 U2), a więc na mocy Tw. 3a. zachodzi A'(∗ ∗ 0 U1 U2) lub też istnieje wyrażenie X spełniające związki: Φ ' (X), B (X, ∗ ∗ 0 U1 U2). W wypadku pierwszym twierdzenie nasze jest słuszne, gdyż mamy A (U1 U2). W wypadku drugim wyrażenie X musi posiadać kształt ∗ ∗ 0 X1 X2 na podstawie definicji sądu B'. Wynika stąd, że zachodzą związki: Φ (∗ ∗ 0 U1 U2), B' (∗∗ 0X1 X2 ∗ ∗ 0 U1 U2), a zatem mamy również: Φ(X1 X2), B(X1 X2 U1 U2).

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

1) dowolne wyrażenia U1 U2spełniające związek A(U1 U2) posiadają własność .

2) jeśli układ wyrażeń X1, X2, U1, U2 spełnia związki: Ψ (X1 X2), B (X1 X2; U1 U2), to wyrażenia U1 U2 posiadają własność Ψ (U1 U2).

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

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

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

Dowód: Oznaczmy przez Ψ '(λ) sąd : "istnieją wyrażenia L1 L2, spełniające związki = λ ∗ ∗ 0 L1 L2, Ψ(L1 L2)". Otrzymujemy natychmiast twierdzenie: ⊦≣ Ψ(λ1λ2) Ψ'(∗∗0λ1λ2) (2).

Na podstawie twierdzeń (1), (2) sprawdzamy łatwo, że sądy A', B'. Ψ' czynią zadość założeniom Tw. 4 a. Stąd wniosek, że wszystkie wyrażenia spełniające związek Φ (U) posiadają własność Ψ (U). W szczególności dla wyrażeń kształtu ∗ ∗0U1 U2 mamy twierdzenie;

Metoda redukcji, którą zastosowaliśmy, pozwoliła nam układ twierdzeń podstawowych 1c - 4c (n = 1, m = 2) sprowadzić do układu twierdzeń 1a-4a (n= 1, m = 1). W sposób zupełnie analogiczny z układu twierdzeń 1b 4b (n = 2, m = 1) otrzymujemy twierdzenia 1d-4d(n = 2, m = 2), które dla, zwięzłości podajemy tylko w postaci symbolicznej. Sądy wyjściowe i funkcja ancestralna mają w tym wypadku kształt: ⊦ ⊃ Φ'(∗∗0U1U2)Ψ'(∗∗0U1U2) czyli ⊦ ⊃ Φ(U1U2)Ψ(U1U2)

A(λ12),B(α1α21β212),Φ(λ12) Tw. 1d. ⊦⊃A(λ12) Φ(λ12)

Tw. 2d ⊦⊃∧Φ(α1α2)∧Φ(β1β2)B(α1α21β212)Φ(λ12)

Tw. 3d. ⊦⊃∧Φ(λ12)∨A(λ12)∃a1a2b1b2 Φ(a1a2)∧Φ(b1b2)B(a1a2,b1b212)

Tw. 4d. Jeśli zachodzą twierdzenia: ⊦ ⊃A(λ12)Ψ(λ12) ,
⊦⊃∧Ψ(α1α2)∧Ψ(β1β2)B(α1α21β212)Ψ(λ12) to zachodzi również twierdzenie
⊦⊃Φ(λ12)Ψ(λ12).

Dla m > 2 sądy pomocnicze A',B', budujemy w sposób zupełnie podobny. Tak np. dla m = B'(λ) oznacza sąd: "istnieją wyrażenia L 1, L 2, L 3 spełniające związki:= λ∗∗∗0 L 1 L 2L 3, A(L 1 L 2 L 3)"; dla m = 4 A'(λ) ma kształt: "istnieją wyrażenia L 1, L 2, L 3, L 4 spełniające związki: = λ∗∗∗∗0 L 1 L 2L 3, A(L 1 L 2 L 3 L 4)"; itd. Widzimy zatem, że dla dowolnej pary liczb naturalnych n, m, gdy sądy wyjściowe mają kształt:

A(λ 1, λ m), B (χ 11.. χ 1m, χ 21.. χ 2m,... χ n1.. χ nm; λ 1.. λ m)

potrafimy zawsze zbudować funkcję ancestralną Φ (λ 1.. λ m) i udowodnić cztery podstawowe twierdzenia, którym ona czyni zadość.