08.pdf

(186 KB) Pobierz
c:\3\8.dvi
3. DEFINIOWANIE
3.0. POJĘCIEDEFINIOWANIA
Wjęzykupierwszegorzędu,czyliwjęzykurachunkupredykatów
takjakgoopisaliśmy,definiowaćmożnaliterypredykatowe,stałein-
dywiduoweiliteryfunkcyjne.Wnaszychrozważaniachograniczymy
sięprzedewszystkimdodefinicji,któreznaczeniasymbolidefiniowa-
nychcharakteryzująwjęzykuteorii,awięcszczegółowiejrozważymy
wypadekwprowadzanianowychsymbolijakowygodnychskrótówdla
złożonychwyrażeń 74 .
Przezteoriębędziemyturozumielidowolnyzbiórformułjęzyka
pierwszegorzędudomkniętynareguływynikania,czylitakizbiór,do
którego należą wszystkie i tylko te formuły, które mają w nim do-
wód.Wszczególności takim zbiorem jestzbiór formułprawdziwych
przy jakiejś interpretacji tego języka, czyli zbiór zdań prawdziwych
wokreślonymmodelu 75 . Tam,gdziemówisięomodeluteoriizwykle
ma się na uwadze zdania, czyli formuły nie zawierające zmiennych
wolnych. Każdej formule odpowiada zdanie, które z niej otrzymu-
jemypoprzezpoprzedzeniejejkwantyfikatoramiogólnymiwiążącymi
wszystkiewystępującewniejzmiennewolne.
Teoriamożebyćokreślonaprzezpodaniejejaksjomatów.Wów-
czas elementami teorii są wszystkie i tylko te formuły, które mają
74 Wartoodnotować,żeporazpierwszyregułydefiniowaniazostałysformuło-
waneprzezpolskiegologikaStanisławaLeśniewskiego[1931].
75 Zbiórwszystkichformułprawdziwychwjakiejśdziedziniejestdomkniętyna
reguływynikania.Jesttakdlatego,żewynikaniesyntaktycznezachowujestosunek
wynikania semantycznego (twierdzenie o pełności) – z prawdziwych formuł nie
możnapoprawnieudowodnićzdaniafałszywego.
1716891.003.png
206
3. DEFINIOWANIE
dowódzjejaksjomatów.Aksjomattowięcelementpewnejwyróżnio-
nejklasyzdań(formuł)określonegojęzyka.
Mającjakąśteorię,np.scharakteryzowanąjakozbiórwszystkich
itylkozdańprawdziwychwokreślonejdziedzinie,możnapytaćsięo
jejaksjomatyzowalność, czylitakizbiórzdań-aksjomatów,zktórego
dałobysięudowodnićwszystkieitylkoformułyskładającesięnatę
teorię.Zwyklechodzioto,abyrozstrzygalnebyłopytanie,czyjakieś
zdanie jest aksjomatem. Na zbiór aksjomatów można też nakładać
innewarunki,np.skończoność.
3.1. DEFINIOWANIELITER PREDYKATOWYCH
≤ i , j ≤ n ;
(b) ϕ jest formułą języka teorii T (czyli nie występuje w niej
literapredykatowa P );
(c) zmienne występujące w ϕ jako wolne znajdują się wśród
zmiennych v 0 ,...,v n (odwrotnieniemusizachodzić).
Wtradycyjnejterminologi Pv 0 ...v n określasięjako definiendum
a ϕ jako definiens .
PRZYKŁAD
Zartytmetykiznamyliterępredykatową„ ≤ ”.Wjęzyku,wktó-
rymwystępująliterypredykatowe„ < ”i„ = ”definiujemyjąnastępu-
jąco
(
x ≤ y
)
⇔
[(
x<y
∨
(
x
=
y
)] .
REGUŁADEFINIOWANIALITERPREDYKATOWYCH
Niech T będzieteorią,zaś P ( n +1) -argumentowąliterąpredyka-
towąnienależącądojęzykatejteorii.Równoważność
Pv 0 ...v n ⇔ ϕ
nagruncieteorii T jestpoprawnądefinicją ( n +1) -argumentowej
literypredykatowej P wtedyitylkowtedy,gdy
(a) wformule(atomowej) Pv 0 ...v n żadnazezmiennych v 0 ,...,v n
niewystępujewięcejniżjednokrotnie,czyli v i = v j ,jeśli i = j ,
0
)
1716891.004.png
3.1. DEFINIOWANIE LITER PREDYKATOWYCH
207
Definicja
)]
jestdefinicjąniepoprawną,naruszapkt.(a).Nieokreślabowiemzna-
czenialiterypredykatowej„ ≤ ”np.wkontekście,„ 3 ≤ 4 ”.
Jestjasne,żewmatematyce możemy sięobyć bezlitery predy-
katowej „ ≤ ”. Wszystko to, co da się powiedzieć w języku z literą
predykową P , może być – jeżeli tylko litera P została zdefiniowana
poprawnie–wsposóbrównoważny wypowiedzianewjęzykubeztej
litery. Taka jest treść twierdzenia o eliminowalności zdefiniowanych
literpredykatowych.
(
x ≤ x
⇔
x<x
)
∨
(
x
=
x
TWIERDZENIE1.(OELIMINOWALNOŚCIZDEFINIOWANYCH
LITERPREDYKATOWYCH)
Jeżelirównoważność
(a) Pv 0 ...v n ⇔ ϕ
jestpoprawnąnagruncieteorii T definicją ( n +1) -argumentowej
litery predykatowej P , to dla każdej formuły ψ języka teorii T
wzbogaconego o literę predykatową P istnieje formuła φ języka
teorii T (awięcbezliterypredykatowej P )taka,żerównoważność
ψ ⇔ φ
jesttwierdzeniemteorii T ,gdzie T jestteoriąwyrażonąwjęzyku
teorii T wzbogaconym o literę predykatową P i powstałą z teorii
T przezdołączenie doniejjakoaksjomatu formuły
∀ v 0 ,...,v n .
[
Pv 0 ...v n ⇔ ϕ
] .
DOWÓD
Twierdzenia dowodzi się przez indukcję po złożoności formuły.
Pokazać należy, że twierdzenie zachodzi dla formuł atomowych, a
następnie–dokonującstosownegozałożeniaindukcyjnego–pokazać
trzeba,żetwierdzenietozachodzirównieżdlaformułzłożonych.
Niech ψ będzieformułąatomową. ψ mawięcpostać
Qt 0 ...t m
– Q jestliterąpredykatową,a t 0 ,...,t m sątermami.
)
[(
1716891.005.png
208
3. DEFINIOWANIE
Gdy Q jestróżneod P ,towarunkinałożonenaformułę φ spełnia
formuła Qt 0 ...t m –jesttobowiemwówczasformułajęzykateorii T .
Gdy literą predykatową Q jest P ,tobierzemy formułę ϕ zrów-
noważności(a).Przemianowujemywystępującewniejzmiennezwią-
zanetak,abywotrzymanejformule ϕ ’żadnazmiennazwiązananie
byłazmiennąwystępującą(jakozmiennawolna)wktórymśztermów
t 0 ,...,t m .
Formuła ϕ ’jestrównoważna ϕ ,czylizachodzi: ϕ ’ ⇔ ϕ .
Twierdzeniemteorii T jestwięc
(a’) Pv 0 ...v n ⇔ ϕ ’.
W formule (a’) podstawiamy termy t 0 ,...,t m ( m = n ) wmiej-
sce zmiennych wolnych v 0 ,...,v n . Podstawienie jest przeprowadzone
poprawnie, bowiem zgodnie z warunkiem (a) reguły definiowania
wszystkie te zmienne wolne są paramiróżne a formuła ϕ ’ jest taka,
żetermy t 0 ,...,t n sąwniejpodstawialne.
Ponieważrównoważność(a’)jesttwierdzeniemteorii T ,więcfor-
mułabędącawynikiempoprawnegowniejpodstawieniajestrównież
twierdzeniem teorii T . Lewym argumentem otrzymanej równoważ-
ności jest Pt 0 ...t m , czyli formuła ψ . Jej prawym argumentem jest
formuła języka teorii T . Ta formuła spełnia więc warunki nałożone
naformułę φ .
ZAŁOŻENIEINDUKCYJNE:Niechtwierdzeniezachodzidlaformuł
ψ 1 , ψ 2 .Istniejąwięcformuły φ 1 i φ 2 języka teorii T takie, że twier-
dzeniamiteorii T sąformuły
ψ 1 ⇔ φ 1 ; ψ 2 ⇔ φ 2 .
Należypokazać,żeodpowiednierównoważnościistniejądlaformuł
¬ ψ 1 , ψ 1 ∨ ψ 2 , ψ 1 ∧ ψ 2 , ψ 1 ⇒ ψ 2 , ψ 1 ⇔ ψ 2 , ∀ v.ψ 1 , ∃ v.ψ 1 .
Wtymceluwystarczyskorzystać znastępującychtezrachunku
predykatów
(
ψ 1 ⇔ φ 1 )
⇒
¬ ψ 1 ⇔¬ φ 1 ) ,
(
ψ 1 ⇔ φ 1 )
⇒
[(
ψ 2 ⇔ φ 2 )
⇒
(
ψ 1 ∨ ψ 2 ⇔ φ 1 ∨ φ 2 )] ,
(
ψ 1 ⇔ φ 1 )
⇒
[(
ψ 2 ⇔ φ 2 )
⇒
(
ψ 1 ∧ ψ 2 ⇔ φ 1 ∧ φ 2 )] ,
(
1716891.006.png
3.1. DEFINIOWANIE LITER PREDYKATOWYCH
209
(
ψ 1 ⇔ φ 1 )
⇒{
(
ψ 2 ⇔ φ 2 )
⇒
[(
ψ 1 ⇒ ψ 2 )
⇔
(
φ 1 ⇒ φ 2 )]
} ,
(
ψ 1 ⇔ φ 1 )
⇒{
(
ψ 2 ⇔ φ 2 )
⇒
[(
ψ 1 ⇔ ψ 2 )
⇔
(
φ 1 ⇔ φ 2 )]
} ,
∀ v.
(
ψ 1 ⇔ φ 1 )
⇒
(
∀ v.ψ 1 ⇔∀ v.φ 1 ) ,
∃ v.
(
ψ 1 ⇔ φ 1 )
⇒
(
∃ v.ψ 1 ⇔∃ v.φ 1 )
.
Zgodnie z twierdzeniem o eliminowalności zdefiniowanych liter
predykatowychkażdaformuła,wktórejwystępujezdefiniowanalitera
predykatowamożebyćwsposóbrównoważnyzastąpionaformułą,w
której tej litery nie ma. W szczególności dotyczy to twierdzeń. Dla
każdego twierdzenia ϕ teorii T ’istnieje równoważne mu twierdzenie
φ teorii T ’niezawierającezdefiniowanejliterypredykatowej.
Powstajejednakpytanie,czytwierdzenie φ teorii T ,niezawiera-
jące zdefiniowanej litery predykatowej P , jest również twierdzeniem
teorii T . Czy nie jest być może tak, że dołączając do teorii T jako
aksjomatdefinicjęliterypredykatowej P wsposóbistotnyniewzbo-
gaciliśmyzasobujejtwierdzeń?Czywteorii T niepojawiłysiętwier-
dzeniabędąceformułamijęzykateorii T ,aleniebędącetwierdzeniami
teorii T ?Chodziwięcoto,czydefinicjaliterypredykatowej P niejest
twórcza.Odpowiedzinatopytaniedostarczakolejnetwierdzenie.
TWIERDZENIE 2. (O NIETWÓRCZOŚCI DEFINICJI LITERY
PREDYKATOWEJ)
Jeżelirównoważność
(a) Pv 0 ...v n ⇔ ϕ
jestpoprawnąwteorii T definicją ( n +1) -argumentowejliterypre-
dykatowej P ,ateoria T jestwyrażonawjęzykuteorii T wzboga-
conymoliterępredykatową P ipowstałązteorii T przezdodanie
doniejjakoaksjomatu formuły
∀ v 0 ,...,v n .
[
Pv 0 ...v n ⇔ ϕ
DOWÓD
Niech φ będzie nie zawierającym litery predykatowej P twier-
dzeniem teorii T . φ mawięcdowód wteorii T wyrażonej w języku
] ,
tokażdetwierdzenieteorii T niezawierająceliterypredykatowej
P (będąceformułąjęzykateoriiT)jesttwierdzeniemteorii T .
1716891.001.png 1716891.002.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin