Czytam właśnie książkę Eliotta Mendelsona "Introduction to Mathematical Logic" i zatrzymałem się na własności VII. ze strony 58. Nie jestem pewien co do tłumaczenia, ale postaram się to przełożyć.
Własność VII. Dla zadanego języka pierwszego rzędu: Jeżeli formuła \(\displaystyle{ C}\) powstała przez podstawienie w tautologii \(\displaystyle{ A}\) rachunku zdań za zmienne zdaniowe dowolnych formuł (te sama formuła dla każdego wystąpienia danej zmiennej), to \(\displaystyle{ C}\) jest prawdziwa w dowolnym modelu dla tego języka tzn. \(\displaystyle{ \vDash C}\).
Mendelson proponuje dowód przechodzący przez twierdzenie o zupełności (Proposition 1.14), a mnie się wydaje, że potrafię to udowodnić bez tego twierdzenia. Będę wdzięczny, jeśli ktoś zweryfikuje moje rozumowanie. Zacznę od paru moich własnych oznaczeń.
Zakładając, że \(\displaystyle{ (E_n)_{n\in\NN}}\) jest ciągiem formuł (rachunku predykatów), a \(\displaystyle{ A}\) jest formułą rachunku zdań, to symbol \(\displaystyle{ A[E]}\) oznacza u mnie formułę powstałą przez podstawienie w miejsce każdej zmiennej zdaniowej \(\displaystyle{ p_m}\) formuły \(\displaystyle{ E_m}\) (zakładam, że zbiór zmiennych zdaniowych to \(\displaystyle{ \mathcal{Z}=\{p_n:n\in\NN\}}\)).
\(\displaystyle{ \mathcal{F}}\) oznacza zbiór formuł rachunku zdań, a \(\displaystyle{ \mathcal{W}}\) zbiór formuł rachunku predykatów. \(\displaystyle{ \Sigma}\) oznacza zbiór ciągów nieskończonych o wartościach w \(\displaystyle{ D}\), gdzie \(\displaystyle{ D}\) jest uniwersum modelu. \(\displaystyle{ \xi:\mathcal{W}\rightarrow\{0,1\}^{\Sigma}}\) to funkcja taka, że \(\displaystyle{ \xi(B)(s)=1}\) wtedy i tylko wtedy, gdy ciąg \(\displaystyle{ s}\) spełnia formułę \(\displaystyle{ B}\).
Oto zasadnicze rozumowanie:
Ustalmy ciąg formuł \(\displaystyle{ (E_n)_{n\in\NN}}\) i \(\displaystyle{ s\in\Sigma}\). Określam wartościowanie \(\displaystyle{ \nu_0:\mathcal{Z}\rightarrow\{0,1\}}\) wzorem \(\displaystyle{ \nu_0(p_n)=\xi(E_n)(s)}\) i niech \(\displaystyle{ \nu:\mathcal{F}\rightarrow\{0,1\}}\) będzie jego rozszerzeniem. Pokażę, że dla każdego \(\displaystyle{ A\in\mathcal{F}}\): \(\displaystyle{ \xi(A[E])(s)=\nu(A)}\).
indukcja.
1. \(\displaystyle{ A}\) jest zmienną zdaniową. Wtedy \(\displaystyle{ A=p_k}\) da pewnego \(\displaystyle{ k\in\NN}\). Wówczas
\(\displaystyle{ \nu(A)=\nu(p_k)=\nu_0(p_k)=\xi(E_k)(s)=\xi(p_k[E])(s)=\xi(A[E])(s)}\)
2. Załóżmy, że \(\displaystyle{ A}\) jest formułą taką, że \(\displaystyle{ \xi(A[E])(s)=\nu(A)}\). Wówczas
\(\displaystyle{ \nu(\neg A)=1-\nu(A)=1-\xi(A[E])(s)=\xi(\neg A[E])(s)=\xi((\neg A)[E])(s)}\)
3. Załóżmy, że \(\displaystyle{ A, B}\) są takie, że \(\displaystyle{ \xi(A[E])(s)=\nu(A), \xi(B[E])(s)=\nu(B)}\). Wówczas
\(\displaystyle{ \nu(A\rightarrow B)=\max\{1-\nu(A),\nu(B)\}=\max\{1-\xi(A[E])(s),\xi(B[E])(s)\}=\xi(A[E]\rightarrow B[E])(s)=\xi((A\rightarrow B)[E])(s)}\)
Przechodzę do dowodu właności VII. Jeśli \(\displaystyle{ C}\) jest formułą rachunku predykatów powstałą z tautologii \(\displaystyle{ A}\), to istnieje ciąg formuł \(\displaystyle{ (E_n)_{n\in\NN}}\) taki, że \(\displaystyle{ C=A[E]}\). Ustalmy ciąg \(\displaystyle{ s\in\Sigma}\) i niech \(\displaystyle{ \nu}\) będzie wartościowaniem określonym na podstawie \(\displaystyle{ E}\) i \(\displaystyle{ s}\) tak jak wcześniej. Na mocy udowodnionej własności \(\displaystyle{ \xi(C)(s)=\xi(A[E])(s)=\nu(A)=1}\), gdzie \(\displaystyle{ \nu(A)=1}\), bo \(\displaystyle{ A}\) jest tautologią. Dowodzi to, że dowolny ciąg \(\displaystyle{ s\in\Sigma}\) spełnia \(\displaystyle{ C}\), czyli dokładnie \(\displaystyle{ \vDash C}\).
Jest ok?
