Το θεώρημα της συμπάγειας

Τι χρησιμοποιείται από τα προηγούμενα μαθήματα

Το μάθημα αυτό εργάζεται σχεδόν εξ ολοκλήρου στη σημασιολογία, και χρησιμοποιεί από αυτήν τα εξής. Μια αποτίμηση είναι μια συνάρτηση $v\colon V \to \{0, 1\}$ πάνω στο σύνολο $V$ των μεταβλητών $v_1, v_2, v_3, \ldots$, που επεκτείνεται με μοναδικό τρόπο σε όλους τους τύπους· μια αποτίμηση ικανοποιεί ένα σύνολο $\Gamma$ τύπων, $v \models \Gamma$, αν δίνει την τιμή $1$ σε καθέναν από αυτούς, και το $\Gamma$ είναι ικανοποιήσιμο αν κάποια αποτίμηση το ικανοποιεί, και μη ικανοποιήσιμο στην αντίθετη περίπτωση. Όλα αυτά βρίσκονται στο μάθημα για τη σημασιολογία της προτασιακής λογικής, μαζί με το κεντρικό εργαλείο αυτού του μαθήματος, το λήμμα σύμπτωσης: αν δύο αποτιμήσεις συμπίπτουν στις μεταβλητές του $\varphi$, που αποτελούν ένα πεπερασμένο σύνολο $V(\varphi)$, δίνουν στον $\varphi$ την ίδια τιμή.

Από το μάθημα για τη σημασιολογική συνέπεια και ισοδυναμία χρησιμοποιούνται ο ορισμός του $\Gamma \models \varphi$ (κάθε αποτίμηση που ικανοποιεί το $\Gamma$ ικανοποιεί τον $\varphi$), οι δομικές ιδιότητές της, ιδίως η μονοτονία (αν $\Gamma \subseteq \Delta$ και $\Gamma \models \varphi$, τότε $\Delta \models \varphi$) και η πέμπτη (ένα μη ικανοποιήσιμο σύνολο έχει ως συνέπεια κάθε τύπο), και το θεώρημα «Συνέπεια και μη ικανοποιησιμότητα»: $\Gamma \models \varphi$ αν και μόνο αν το $\Gamma \cup \{\neg\varphi\}$ είναι μη ικανοποιήσιμο. Από το μάθημα για τους γενικευμένους νόμους του Ντε Μόργκαν και τους επιμεριστικούς νόμους χρησιμοποιείται το λήμμα της τιμής: ο $\bigwedge_{i=1}^{n} \varphi_i$ έχει τιμή $1$ αν και μόνο αν όλοι οι όροι του έχουν τιμή $1$, και ο $\bigvee_{i=1}^{n} \varphi_i$, αν και μόνο αν κάποιος έχει τιμή $1$. Τέλος, ο $\top := (v_1 \rightarrow v_1)$ είναι ταυτολογία και ο $\bot := \neg\top$ αντίφαση.

Από την πλευρά της παραγωγής, το μάθημα για τα τυπικά παραγωγικά συστήματα απέδειξε τη μονοτονία (Μον: αν $\Gamma \subseteq \Delta$ και $\Gamma \vdash \varphi$, τότε $\Delta \vdash \varphi$) και τον πεπερασμένο χαρακτήρα (Πεπ: αν $\Gamma \vdash \varphi$, κάποιο πεπερασμένο υποσύνολο $\Gamma_0$ του $\Gamma$ πληροί $\Gamma_0 \vdash \varphi$), και το μάθημα για τις τέσσερις τεχνικές παραγωγής επιβεβαίωσε ότι και οι δύο ισχύουν στο σύστημα του κύκλου μαθημάτων (τα σχήματα A1, A2 και A3, ο modus ponens και η αντικατάσταση της διπλής άρνησης, ΑΔΑ), στο οποίο αναφέρεται στο εξής το σύμβολο $\vdash$. Τέλος, το μάθημα για την ορθότητα και πληρότητα απέδειξε το θεώρημα ορθότητας (το $\Gamma \vdash \varphi$ συνεπάγεται το $\Gamma \models \varphi$, για κάθε $\Gamma$) και την πληρότητα για πεπερασμένα σύνολα υποθέσεων: αν $\{\gamma_1, \ldots, \gamma_k\} \models \varphi$, τότε $\{\gamma_1, \ldots, \gamma_k\} \vdash \varphi$.