Logika prof dr hab. Bogdan WĘglorz rachunek zdań, algebry uniwersalne. Systemy relacyjne



Pobieranie 6.74 Mb.
Strona19/57
Data25.10.2017
Rozmiar6.74 Mb.
1   ...   15   16   17   18   19   20   21   22   ...   57

TWIERDZENIE 6.1. [Łoś] Jeśli A/F jest ultraproduktem rodziny systemów Ai , i  I , względem ultrafiltru F , to dla każdej formuły  mamy:

A/F ╞ [u] iff {i  I : Ai ╞ [u(i)]}  F .



Dowód. Udowodnimy to przez indukcje ze względu na budowę formuły  . Na mocy naszych uwag, twierdzenie zachodzi dla formuł atomowych.

Przypuśćmy, że  jest postaci  oraz, że dla  twierdzenie jest prawdziwe. Przypuśćmy, że A/F ╞ [u] . To oznacza, że nie jest prawdą aby A/F ╞ [u] i konsekwentnie, z założenia indukcyjnego, Z = {i  I : Ai ╞ [u(i)]}  F . Na mocy 2.10, to daje Z = {i  I : Ai ╞ [u(i)]}  F .

Jeśli {i  I : Ai ╞ [u(i)]}  F , to Z = {i  I : Ai ╞ [u(i)]}  F . A więc z założenia indukcyjnego, nie jest prawdą, że A/F ╞ [u] , a więc A/F ╞ [u] .

Przypuśćmy więc, że  jest postaci 1  2 oraz zarówno dla 1 jak i 2 twierdzenie jest prawdziwe. Przypuśćmy, że A/F ╞ [u] . Wtedy jednak zarówno A/F ╞ 1[u] jak też A/F ╞ 2[u] . Na mocy założenia indukcyjnego, oznacza to, że Zs = {i  I : Ai ╞ s[u(i)]}  F , dla s = 1 , 2 . Ale z definicji filtru, mamy wtedy Z = Z1  Z2  F . Czyli Z = {i  I : Ai ╞ [u(i)]}  F .

Odwrotnie, niech Z = {i  I : Ai ╞ [u(i)]}  F . Oznaczmy teraz Zs = {i  I : Ai ╞ s[u(i)]}, dla s = 1 , 2 . Ponieważ Z  Zs , więc z definicji filtru Zs  F . To jednak, z założenia indukcyjnego, daje

A/F ╞ s[u] , dla s = 1 , 2 . A więc A/F ╞ [u] .

Niech w końcu  będzie postaci x0  . Załóżmy, że A/F ╞ [u] . To oznacza, że istnieje modyfikacja u = u(a0x0) wartościowania u w punkcie x0 taka, że A/F ╞ [u] . Z założenia indukcyjnego oznacza to, że Z = {i  I : Ai ╞ [u(i)]}  F . Ale oczywiście

{i  I : Ai ╞ [u(i)]}  {i  I : Ai ╞ x0 [u(i)]} .

Więc {i  I : Ai ╞ x0 [u(i)]}  {i  I : Ai ╞ [u(i)]}  F .

Odwrotnie, przypuśćmy, że Z = {i  I : Ai ╞ [u(i)]}  F . Dla każdego iZ mamy więc



Ai ╞ [u(i)] . Ponieważ  jest formułą x0  , więc istnieje modyfikacja u(i)(dix0) wartościowania u(i) taka, że Ai ╞ [u(i) (dix0)] . Niech a będzie taka, że a(i) = di dla i  Z . Wtedy mamy Z = {i  I : Ai ╞ [u(ax0)(i)]} więc z założenia indukcyjnego A/F ╞ [u(ax0)] , czyli, z definicji spełniania A/F ╞ [u] .

To kończy dowód twierdzenia.



Pierwszym zastosowaniem Twierdzenia Łosia jest następujące Twierdzenie o Zwartości (semantycznej).

TWIERDZENIE 6.2. Niech  będzie nieskończonym zbiorem zdań i przypuśćmy, że każdy skończony podzbiór 0   ma model. Wtedy  ma model.

Dowód. Niech I będzie rodzina wszystkich skończonych podzbiorów zbioru  . Wtedy dla każdego i  I istnieje system Ai będący modelem wszystkich zdań z i   . Dla każdego zdania    niech I = {i  I : Ai╞ } . Zauważmy, że wtedy dla każdego zbioru i  I , mamy i  {I :   i} . Niech więc E będzie filtrem generowanym przez {I :   } i niech F  E będzie dowolnym ultrafiltrem. Rozważmy ultraprodukt / F .

Jeśli    , to {i  I : Ai╞ } = I  F , więc na mocy twierdzenia Łosia / F ╞  . Czyli

/ F jest modelem dla  .

Bezpośrednim wnioskiem jest Górne Twierdzenie Löwenheima – Skolema.



TWIERDZENIE 6.3. Jeśli  ma model nieskończony, to  ma model dowolnie dużej mocy.

Dowód. Niech A będzie nieskończonym modelem zbioru  . Niech m będzie dowolną mocą nieskończoną. Rozszerzmy język, w którym zapisane są zdania z  przez dodanie m zupełnie nowych stałych {dz : z  Z} , gdzie Z = m . Rozważmy zbiór zdań  =   { dx = dy : x , y  Z , xy} . Jeśli 0   jest skończony, to 0  1 =   { dx = dy : x , y  Z1 , xy} dla pewnego skończonego Z1  Z . Ponieważ Z0 jest skończony, a system A jest nieskończony, więc wybierając Z1 różnych elementów {d : z  Z1} z A otrzymamy system A = (A , {d : z  Z1}) będący modelem 1 . To pokazuje, że każdy skończony podzbiór  ma model. Na mocy Twierdzenia o Zwartości istnieje model całego zbioru  . Jest to system postaci B = (B , {d : z  Z}) , gdzie B jest modelem zbioru  , natomiast elementy {d : z  Z} spełniają zdania { dx = dy : x , y  Z , xy} . Są więc różne, co pokazuje, że B  Z = m . A więc  ma model mocy  m .



Pobieranie 6.74 Mb.

Share with your friends:
1   ...   15   16   17   18   19   20   21   22   ...   57




©operacji.org 2020
wyślij wiadomość

    Strona główna