Θεωρία μοντέλων

Παράδειγμα

Η βασική σχέση μεταξύ της σύνταξης και της σημασιολογίας σε μη-τετριμμένα μοντέλα, μπορεί αρχικά να δειχθεί στο συντακτικό επίπεδο, με τα κατάλληλα αξιώματα για τους φυσικούς αριθμούς, όπως τα αξιώματα του Πεάνο, και την αντίστοιχη θεωρία. Από σημασιολογικής πλευράς, οι συνηθισμένοι αριθμοί αποτελούν ένα μοντέλο. Στη δεκαετία του 1930 ο Σκόλεμ ανέπτυξε εναλλακτικά μοντέλα που ικανοποιούν τα αξιώματα. Αυτό δείχνει τι σημαίνει μια γλώσσα ή μια θεωρία να ερμηνεύεται σε ένα συγκεκριμένο μοντέλο. Ένα άλλο παραδοσιακό παράδειγμα είναι η ερμηνεία των αξιωμάτων ενός συγκεκριμένου αλγεβρικού συστήματος, όπως μιας ομάδας, σε ένα μοντέλο που δίνεται από μια συγκεκριμένη ομάδα.

Θεωρία μοντέλων και θεωρία συνόλων

Η θεωρία συνόλων (που εκφράζεται σε μια αριθμήσιμη γλώσσα) έχει ένα αριθμήσιμο μοντέλο, κάτι που είναι γνωστό σαν το παράδοξο του Σκόλεμ, επειδή υπάρχουν προτάσεις στη θεωρία συνόλων που υποθέτουν την ύπαρξη μη αριθμήσιμων συνόλων αλλά είναι αληθείς στο αριθμήσιμο αυτό μοντέλο. Ειδικότερα, η απόδειξη της ανεξαρτησίας της υπόθεσης του συνεχούς απαιτεί να ληφθούν υπόψη σύνολα σε μοντέλα που φαίνονται μη αριθμήσιμα μέσα από το μοντέλο, αλλά φαίνονται αριθμήσιμα σε κάποιον έξω από το μοντέλο.
Η μοντελο-θεωρητική άποψη έχει χρησιμεύσει στη θεωρία συνόλων, όπως για παράδειγμα στο έργο του Κουρτ Γκέντελ πάνω στο κατασκευάσιμο σύμπαν (constructible universe), η οποία, μαζί με τη μέθοδο του forcing που αναπτύχθηκε από τον Paul Cohen, μπορούν να αποδειχτούν ότι αποδεικνύουν την (φιλοσοφικά ενδιαφέρουσα) ανεξαρτησία του αξιώματος της επιλογής και της υπόθεσης του συνεχούς από τα άλλα αξιώματα της θεωρίας συνόλων.

Πρώιμη ιστορία

Η θεωρία μοντέλων σαν ξεχωριστό αντικείμενο υπάρχει από περίπου τα μέσα του 20ου αιώνα. Κάποια προγενέστερη έρευνα όμως, ειδικά στη μαθηματική λογική, συνήθως θεωρείται πια ότι έχει μοντελο-θεωρητική υφή. Το πρώτο σημαντικό αποτέλεσμα σε αυτό που σήμερα είναι η θεωρία μοντέλων ήταν μια ειδική περίπτωση του κάτω (downward) θεωρήματος Λέβενχάιμ-Σκόλεμ, που δημοσιεύτηκε από τον Λέβενχάιμ το 1915. Το θεώρημα συμπαγείας υπήρχε στο έργο του Σκόλεμ, αλλά δημοσιεύτηκε πρώτη φορά το 1930, σαν λήμμα στην απόδειξη του θεωρήματος πληρότητας του Γκέντελ. Στο θεώρημα Λέβενχάιμ-Σκόλεμ και στο θεώρημα συμπαγείας δόθηκε η αντίστοιχη γενική τους μορφή τι 1936 και το 1941 αντίστοιχα, από τον Ανατόλι Μάλτσεβ (Anatoly Maltsev).

Χρήση των θεωρημάτων συμπαγείας και πληρότητας

Το θεώρημα πληρότητας του Γκέντελ (που δεν πρέπει να συγχέεται με τα θεωρήματα μη-πληρότητας) λέει ότι μια θεωρία έχει μοντέλο αν και μόνο αν είναι συνεπής (consistent), δηλαδή δε μπορεί να αποδειχτεί κάποια αντίφαση στη θεωρία. Αυτή είναι η καρδιά της θεωρίας μοντέλων, επιτρέποντας να απαντηθούν ερωτήσεις σχετικές με θεωρίες κοιτώντας τα μοντέλα και αντίστροφα. Το θεώρημα πληρότητας δεν πρέπει να συγχέεται με την έννοια της πλήρους θεωρίας. Μια θεωρία είναι πλήρης όταν περιέχει κάθε πρόταση ή την άρνησή της. Κάθε συνεπής θεωρία μπορεί να επεκταθεί σε μια πλήρη θεωρία αλλά, όπως δείχνουν τα θεωρήματα μη πληρότητας του Γκέντελ, μόνο σε απλές περιπτώσεις μια πλήρης και συνεπής θεωρία είναι αναδρομική (δηλ. περιγράφεται από ένα αναδρομικά αριθμήσιμο σύνολο αξιωμάτων). Ειδικότερα, η θεωρία των φυσικών αριθμών δεν έχει αναδρομική πλήρη και συνεπή θεωρία. Οι μη-αναδρομικές θεωρίες δεν είναι πολύ χρήσιμες στην πράξη, γιατί δεν είναι υπολογίσιμο αν ένα πιθανό αξίωμα είναι πραγματικά αξίωμα, και το έργο του ελέγχου των αποδείξεων γίνεται υπερβολικά πολύπλοκο (supertask).
Το θεώρημα της συμπαγείας (compactness theorem) δηλώνει ότι ένα σύνολο από προτάσεις S είναι ικανοποιήσιμο αν κάθε πεπερασμένο υποσύνολό του είναι ικανοποιήσιμο. Το ανάλογο θεώρημα στη θεωρία αποδείξεων είναι τετριμμένο, γιατί κάθε απόδειξη μπορεί να έχει πεπερασμένο αριθμό προηγούμενων που χρησιμοποιούνται στην απόδειξη. Η απόδειξη αυτή όμως στη θεωρία μοντέλων είναι πιο δύσκολη. Υπάρχουν δύο γνωστές αποδείξεις, μία από τον Κουρτ Γκέντελ (που χρησιμοποιεί αποδείξεις) και μια από τον Μάλτσεβ (πιο ευθεία και επιτρέπει τον περιορισμό της πληθικότητας του μοντέλου που προκύπτει).
Η θεωρία μοντέλων συχνά ασχολείται με τη λογική πρώτου βαθμού και πολλά σημαντικά αποτελέσματα (όπως τα θεωρήματα πληρότητας και συμπαγείας) δεν ισχύουν στη λογική δεύτερου βαθμού ή σε άλλες λογικές. Στη λογική πρώτου βαθμού όλοι οι άπειροι πληθικοί αριθμοί δείχνουν το ίδιο σε μια αριθμήσιμη γλώσσα. Αυτό εκφράζεται από το θεώρημα Λέβενχάιμ-Σκόλεμ, που δηλώνει ότι κάθε αριθμήσιμη θεωρία με ένα άπειρο μοντέλο  έχει μοντέλα όλων των άπειρων πληθικοτήτων (τουλάχιστον της γλώσσας) που συμφωνούν με το  σε όλες τις προτάσεις, είναι δηλαδή 'στοιχειωδώς ισοδύναμα' ('elementarily equivalent').