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



Pobieranie 6.74 Mb.
Strona56/57
Data25.10.2017
Rozmiar6.74 Mb.
1   ...   49   50   51   52   53   54   55   56   57
, ... , ) . Ponieważ A był dowolnym modelem dla T   , więc T   ├ ( , ... , ) . Z Twierdzenia o zwartości, istnieje skończony podzbiór 0   , że T  0 ├ ( , ... , ) . Jeśli teraz  jest koniunkcją wszystkich formuł z 0 , to mamy T  {}├ ( , ... , ) . Ostatecznie eliminując zmienne i sprowadzając  do postaci preneksowej, dzięki Twierdzeniu o Dedukcji mamy T├    . Ponieważ odwrotna implikacja jest oczywista z konstrukcji  , ostatecznie mamy  T  .

Odwrotnie, przypuśćmy, że dla każdej formuły egzystencjalnej  istnieje uniwersalna  taka, że  T  . Zauważmy najpierw, że przez indukcję ze względu na budowę  (np. patrząc na ilość kwantyfikatorów w preneksowej postaci ) , dla każdej formuły  istnieje uniwersalna formuła  taka, że  T  . Niech teraz A i B będą modelami T oraz niech A  B . Niech  będzie dowolną formułą i przypuśćmy, że dla pewnych a1 , ... , am  A , mamy B╞ [ a1 , ... , am] . Z założenia istnieje uniwersalna  taka, że  T  . To daje B╞ [ a1 , ... , am] . Ponieważ  jest uniwersalna, więc na mocy Zadania 52.b, A╞ [ a1 , ... , am] i w konsekwencji A╞ [ a1 , ... , am] . Ponieważ rozumowanie powyższe możemy równie dobrze stosować do  , więc widzimy, że dla każdego  i każdego wartościowania



Pobieranie 6.74 Mb.

Share with your friends:
1   ...   49   50   51   52   53   54   55   56   57




©operacji.org 2020
wyślij wiadomość

    Strona główna