Wartościowaniem w M nazywamy dowolne przyporządkowanie
: V → |M|
Jeśli (y) = b∈|M|, to możemy myśleć o zmiennej y jako o imieniu własnym dla b.
Trójargumentowa relacja spełniania: M |= φ [ ] czytamy: φ jest spełnione w M przy wartościowaniu .
Ze względu na konstrukcję formuły można zdefiniować indukcyjnie.
Niech - ustalone wartościowanie w M. Określimy Val(t, ) dla dowolnego t∈Trmσ (określona przy ustalonym modelu).
M = (U, (Rp)p∈P, (Fg)g∈F, (ac)c∈C)
Dla y∈V określamy Val(y, ) = (y)
Dla c∈C określamy Val(c, ) = ac - wartość nie zależy w ogóle od wartościowania, to model określa interpretację stałych indywiduowych.
Dla g∈F, i = k(g), t1, ... , ti∈Trmσ Val(g(t1, ... , ti), ) = Fg(Val(t1, ), ... , Val(ti, ))
Dla formuł atomowych
M |= t = t' [ ] ⇔ Val(t, ) = Val(t', )
[= po lewej stronie - znak, symbol, po prawej - wyrażenie użyte, z naszego języka, za pomocą naszej wiedzy podajemy warunek prawdziwości]
p∈P, m(p) = i, t1, ... , ti∈Trmσ M |= p(t1, ... , ti) [ ] ⇔ Rp(Val(t1, ), ... , Val(ti, ))
Iindukcja - przeniesienie na wszystkie formuły.
Formuły złożone - poprzedzenie ~, ⇒ lub ∀.
φ, ψ∈Frmσ.
M |= ~ φ [ ] ⇔ nieprawda, że M |= φ [ ]
M |= (φ ⇒ ψ) [ ] ⇔ (jeśli M |= φ [ ], to M |= ψ [ ]) [można użyć ~ i ⇒]
M |= ∀y φ [ ] ⇔ dla dowolnego b∈|M| zachodzi M |= φ[ (y/b)], gdzie:
( (y/b))(x) = b, jeśli x = y,
(x), w przeciwnym przypadku (p. p.)
Szczególna funkcja , szczególne wartościowanie. To wartościowanie przyjmuje dla x wartość następującą: ... .
M |= ∀y φ [ ] ⇔ dla dowolnego wartościowania w M różniącego się od co najwyżej na y zachodzi M |= φ [ ] (Tarski)
Niech ƒ: X → Y, A ⊆ X. Wówczas ƒ | A = {(x, y)∈ƒ: x∈A}. Funkcja obcięta do A.
Lemat. Niech , wartościowania w M, φ∈Frmσ taka, że | ZW(φ) = | ZW(φ) (tzn. dla dowolnego y∈ZW(φ) zachodzi (y) = (y)). Wówczas M |= φ [ ] ⇔ M |= φ [ ].
Dowód. Niech t∈Trmσ, | ZW(t) = | ZW(t). Wóωczas Val(t, ) = Val(t, ). Dowód przez indukcję po konstrukcji termu.
Jeśli t∈V oraz | ZW(t) = | ZW(t), to Val(t, ) = (t) = (t) = Val(t, ) (z założenia). Podobnie dla przypadku, jeśli t∈C, wtedy Val(t, ) = at = Val(t, ). Niech g∈F, k(g) = i, t1, ... , ti∈Trmσ takie, że teza zachodzi. (*). Wówczas Val(g(t1, ... , ti), ) = Fg(Val(t1, ), ... , Val(ti, )) = Fg(Val(t1, ), ... , Val(ti, )) = Val(g(t1, ... , ti), ), o ile | ZW(t) = | ZW(t). Niech g(t1, ... , ti) =ozn.t. ZW(
(…)
… występują.
Określimy relację T |- φ (wywodliwości, wynikania syntaktycznego, nie odwołujemy się do znaczenia). T |- φ znaczy: istnieje dowód zdania φ z T.
Program Hilberta
Próba odpowiedzi na określone problemy, próba ugruntowania podstaw matematyki. Dążenie do oparcia się o teorię mnogości (ważnej dla nauki i techniki) i usunięcia z niej istotnych sprzeczności.
3 główne koncepcje:
- logicyzm (Frege, Russell) - interpretacja matematyki w odpowiednio rozbudowanym systemie logiki (Frege - logika wchłaniająca teorię mnogości, Russell - rozgałęziona teoria typów); musimy mieć aparat, by z czegoś robić,
- intuicjonizm,
- formalizm.
Wpływ na teorię obliczeń i technikę komputerową.
e = Σn=0∞ 1/n!
ek = Σn=0k 1/n!
Juvil (?) - dowód, że Σi=0∞ 1/10i! jest liczbą niealgebraiczną.
1. matematyka finitystyczna (konkretna) - teoria liczb, kombinatoryka, własności skończonych obiektów, teoria zbiorów dziedzicznie skończonych, kombinatoryka na słowach (algebra słów, wolna grupa z jedynką i własności tej struktury). Nie potrzebuje żadnego ugruntowania, jest dobrze ugruntowana, nie ma problemu z kryterium prawdziwości. Prawdziwa matematyka.
2. matematyka idealna - teoria zbiorów, nieskończone liczby kardynalne…
… nie rozróżnia mocy nieskończonych.
Formuła ξ ma mieć taką postać:
∃ ∃P|= (P|=(/φ, ) ∧ warunki spełniania)
egzystencjalny kwantyfikator 2 rzędu.
P|= - relacja, zmienna 2 rzędu przebiegająca relacje.
Np. ∀ ∀x [P|=(ƒ^(/~, x*), ) ⇔ ~ P|=(x, )] *dowolne słowo, nie /x
M jest σ-modelem - model słownika σ. Słownik określa, jaką strukturę musi mieć model, co musi być w nim zinterpretowane.
Teoria - zbiór zdań.
Pojęcie…
…, jałowe, ale zupełne rozszerzenie matematyki finitystycznej.
Następnie należy środkami matematyki finitystycznej udowodnić, że ~ I |- 0 = 1, czyli niesprzeczności I. Z warunku (1) wynika niesprzeczność, ale nie mówi się nic o środkach.
Gödel - dla logiki 1 rzędu wynikanie syntaktyczne i semantyczne są równoważne.
Twierdzenie Gödla (I). Niech PA ⊆ T - niesprzeczna teoria (zawierająca Arytmetykę Peano…
... zobacz całą notatkę
Komentarze użytkowników (0)