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

.

Στα μαθηματικά, η θεωρία μοντέλων (αγγλ. model theory) μελετά (κλάσεις από) μαθηματικές δομές όπως οι ομάδες, τα πεδία, οι γράφοι, ακόμα και τα universes της θεωρίας συνόλων, χρησιμοποιώντας εργαλεία της μαθηματικής λογικής. Μια δομή που αποδίδει σημασία στις προτάσεις μιας τυπικής γλώσσας ονομάζεται μοντέλο για αυτήν τη γλώσσα. Αν ένα μοντέλο μιας γλώσσας ικανοποιεί μια συγκεκριμένη πρόταση ή θεωρία (σύνολο από προτάσεις), τότε λέγεται μοντέλο της πρότασης ή θεωρίας. Η θεωρία μοντέλων έχει στενή σχέση με την άλγεβρα και την καθολική άλγεβρα.

Το παρακάτω άρθρο ασχολείται με την περιορισμένη (finitary) πρωτοβάθμια θεωρία μοντέλων των άπειρων δομών. Η θεωρία πεπερασμένων μοντέλων, που επικεντρώνεται στις πεπερασμένες δομές, αποκλίνει σημαντικά από τη μελέτη των άπειρων δομών, τόσο όσον αφορά τα προβλήματα που μελετώνται, όσο και στις τεχνικές που χρησιμοποιούνται. Η θεωρία μοντέλων λογικών ανώτερου βαθμού ή απεριόριστων λογικών (infinitary logics) εμποδίζεται από το γεγονός ότι η πληρότητα δεν ισχύει σε αυτές τις λογικές. Παρά τα παραπάνω, έχει γίνει σημαντική μελέτη πάνω σε τέτοιες γλώσσες.

Εισαγωγή

Η θεωρία μοντέλων αναγνωρίζει και ασχολείται με μια δυικότητα (duality): Εξετάζει τα σημασιολογικά στοιχεία μέσω των συντακτικών στοιχείων μιας γλώσσας. Όπως αναφέρεται και στην πρώτη σελίδα του Chang and Keisler (1990):

καθολική άλγεβρα + λογική = θεωρία μοντέλων.

Όμοια με τη θεωρία αποδείξεων, η θεωρία μοντέλων βρίσκεται σε μια περιοχή που συνδυάζει τα μαθηματικά, τη φιλοσοφία και την επιστήμη υπολογιστών. Ο σημαντικότερος επαγγελματικός οργανισμός του πεδίου της θεωρίας μοντέλων είναι η Association for Symbolic Logic.

Η θεωρία μοντέλων μπορεί να υποδιαιρεθεί (λίγο αυθαίρετα και όχι πλήρως) στην κλασική θεωρία μοντέλων, τη θεωρία μοντέλων που εφαρμόζεται σε ομάδες και πεδία και στη θεωρία γεωμετρικών μοντέλων. Μια υποδιαίρεση που λείπει είναι η θεωρία υπολογίσιμων μοντέλων (computable model theory), η οποία όμως θα μπορούσε να θεωρηθεί σαν ξεχωριστό υπο-πεδίο της λογικής. Παραδείγματα πρώιμων θεωρημάτων της κλασικής θεωρίας μοντέλων είναι το θεώρημα πληρότητας του Γκέντελ, τα θεωρήματα Λέβενχάιμ-Σκόλεμ, το θεώρημα two-cardinal του Βοτ, το θεώρημα ισομορφισμού του Σκοτ, το θεώρημα παράλειψης τύπων (omitting types), και το θεώρημα Ryll-Nardzewski. Παραδείγματα πρώιμων αποτελεσμάτων της εφαρμοσμένης σε πεδία θεωρίας μοντέλων είναι η απαλοιφή ποσοδεικτών του Τάρσκι για κλειστά πεδία πραγματικών, το θεώρημα του Αξ για ψευδο-πεπερασμένα πεδία και η ανάπτυξη από τον Ρόμπινσον της nonstandard ανάλυσης.

Ένα σημαντικό βήμα στην εξέλιξη της κλασικής θεωρίας μοντέλων συνέβη με τη γέννηση της θεωρίας σταθερότητας (stability theory), μέσω του θεωρήματος του Μόρλεϊ, για τις θεωρίες κατηγοριών που δεν αριθμούνται, και του προγράμματος ταξινόμησης του Σέλα, με αποτέλεσμα την ανάπτυξη ενός λογισμού ανεξαρτησίας και τάξης, που βασίστηκε σε συντακτικές συνθήκες που ικανοποιούνται από θεωρίες. Κατά τη διάρκεια των τελευταίων δεκαετιών, η εφαρμοσμένη θεωρία μοντέλων έχει συνδεθεί επανειλημμένα με την αμιγή θεωρία σταθερότητας. Το αποτέλεσμα αυτής της σύνθεσης αποκαλείται γεωμετρική θεωρία μοντέλων (που θεωρείται ότι περιέχει την o-minimality, για παράδειγμα, καθώς και την κλασική γεωμετρική θεωρία σταθερότητας). Παράδειγμα θεωρήματος μιας γεωμετρικής θεωρίας μοντέλων είναι η απόδειξη του Χρουσόφσκι της Εικασίας Mordell–Lang για πεδία συναρτήσεων. Η πρόθεση της γεωμετρικής θεωρίας μοντέλων είναι να παρέχει μια γεωγραφία των μαθηματικών, μέσω της λεπτομερούς μελέτης συνόλων που μπορούν να οριστούν σε διάφορες μαθηματικές δομές, με τη βοήθεια των σημαντικών εργαλείων που αναπτύχθηκαν κατά τη μελέτη της αμιγούς θεωρίας μοντέλων.

Παράδειγμα

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

Καθολική άλγεβρα

Κύριο λήμμα: Καθολική άλγεβρα

Οι βασικές έννοιες στην καθολική άλγεβρα είναι οι υπογραφές (επίσης οπλισμοί, αγγλ. signatures) σ και οι σ-άλγεβρες. Τα παρακάτω αποτελούν μια σύντομη εισαγωγή με παραδείγματα για το πώς χρησιμοποιούνται.

Η υπογραφή των δακτυλίων (rings) είναι σ_ring = {×,+,−,0,1}, όπου τα × και + είναι δυαδικά, το − μοναδιαίο, και το 0 και το 1 μηδενικά.

Η υπογραφή των ημι-δακτυλίων είναι σ_smr = {×,+,0,1}, με τις πολλαπλότητες των συμβόλων να είναι όπως στην προηγούμενη περίπτωση.

Η υπογραφή των (πολλαπλασιαστικών) ομάδων είναι σ_grp = {×,⁻¹,1}, όπου το × είναι δυαδικό, το ⁻¹ μοναδιαίο και το 1 μηδενικό.

Η υπογραφή των μονοειδών (monoids) είναι σ_mnd = {×,1}.

Ένας δακτύλιος είναι μια σ_ring-δομή που ικανοποιεί τις ταυτότητες u + (v + w) = (u + v) + w, u + v = v + u, u + 0 = u, u + (−u) = 0, u × (v × w) = (u × v) × w, u × 1 = u, 1 × u = u, u × (v + w) = (u × v) + (u × w) και (v + w) × u = (v × u) + (w × u).

Μια ομάδα είναι μια σ_grp-δομή που ικανοποιεί τις ταυτότητες u × (v × w) = (u × v) × w, u × 1 = u, 1 × u = u, u × u⁻¹ = 1 και u⁻¹ × u = 1.

Ένα μονοειδές είναι μια σ_mnd-δομή που ικανοποιεί τις ταυτότητες u × (v × w) = (u × v) × w, u × 1 = u και 1 × u = u.

Μια ημι-ομάδα (semigroup) είναι μια σ_mnd-δομή που ικανοποιεί την ταυτότητα u × (v × w) = (u × v) × w.

Ένα μάγμα (magma) είναι απλά μια {×}-δομή.

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

Όροι όπως ο σ_ring-όρος t(u,v,w) που δίνεται από την (u + (v × w)) + (−1) χρησιμοποιούνται για να ορίζονται ταυτότητες t = t', αλλά και για να κατασκευάζονται ελεύθερες άλγεβρες. Μια κλάση ισοδυναμίας είναι μια κλάση από δομές, η οποία, όπως στα παραπάνω παραδείγματα, ορίζεται σαν την κλάση όλων των σ-δομών που ικανοποιούν ένα συγκεκριμένο σύνολο από ταυτότητες. Σύμφωνα με το θεώρημα του Μπίρκοφ:

Μια κλάση από σ-δομές είναι μια κλάση ισοδυναμίας αν και μόνο αν δεν είναι κενή και είναι κλειστή όσον αφορά τις υπο-άλγεβρες, τις ομομορφικές εικόνες και τα απευθείας γινόμενα (direct products).

Ένα σημαντικό και μη τετριμμένο εργαλείο της καθολικής άλγεβρας είναι τα υπεργινόμενα\( \Pi_{i\in I}A_i/U \), όπου το I είναι ένα άπειρο σύνολο που δεικτοδοτεί ένα σύστημα από σ-δομές Ai, και το U είναι ένα υπερφίλτρο (ultrafilter) στο I.

Αν και η θεωρία μοντέλων γενικά θεωρείται μέρος της μαθηματικής λογικής, η καθολική άλγεβρα, που προήλθε από το έργο του Άλφρεντ Νορθ Ουάιτχεντ (1898) στην αφηρημένη άλγεβρα, είναι μέρος της άλγεβρας. Επίσης η θεωρία μοντέλων μπορεί να θεωρηθεί σαν επέκταση της καθολικής άλγεβρας.

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

Κύριο λήμμα: Θεωρία πεπερασμένων μοντέλων

Η θεωρία πεπερασμένων μοντέλων (αγγλ. finite model theory) είναι η περιοχή της θεωρίας μοντέλων που είναι πιο κοντά στην καθολική άλγεβρα. Όπως και κάποιες περιοχές της καθολικής άλγεβρας, και σε αντίθεση με τις άλλες περιοχές της θεωρίας μοντέλων, ασχολείται κυρίως με πεπερασμένες άλγεβρες, ή γενικότερα με πεπερασμένες σ-δομές για υπογραφές σ που μπορούν να περιέχουν σύμβολα σχέσεων όπως στο εξής παράδειγμα:

Η υπογραφή των γράφων είναι σgrph={E}, όπου το E είναι δυαδικό σύμβολο σχέσης.
Ένας γράφος είναι μια σgrph-δομή που ικανοποιεί τις προτάσεις \( \forall u \forall v(uEv \rightarrow vEu) \) και \( \forall u\neg(uEu). \)

Ένας σ-ομομορφισμός είναι μια απεικόνιση που αντιμετατίθεται στις πράξεις και διατηρεί τις σχέσεις στη σ. Σε αυτόν τον ορισμό οφείλεται η συνήθης έννοια του ομομορφισμού γράφων, που έχει την ενδιαφέρουσα ιδιότητα ότι ένας αμφιμονότιμος ομομορφισμός δε χρειάζεται να είναι αντιστρέψιμος. Οι δομές είναι επίσης μέρος της καθολικής άλγεβρας - κάποιες αλγεβρικές δομές όπως οι διατεταγμένες ομάδες έχουν μια δυαδική σχέση <. Αυτό που διαφοροποιεί τη θεωρία πεπερασμένων μοντέλων από την καθολική άλγεβρα είναι η χρήση από μέρους της γενικότερων λογικών προτάσεων (όπως στο παραπάνω παράδειγμα) αντί για ταυτότητες. (Σε ένα μοντελο-θεωρητικό πλαίσιο μια ταυτότητα t=t' γράφεται σαν μια πρόταση \( \forall u_1u_2\dots u_n(t=t'). \))

Οι λογικές που χρησιμοποιούνται από τη θεωρία πεπερασμένων μοντέλων είναι συνήθως αρκετά πιο εκφραστικές από τη λογική πρώτου βαθμού, την λογική που χρησιμοποιείται συνήθως στη θεωρία μοντέλων των άπειρων δομών.
Λογική πρώτου βαθμού

Κύριο λήμμα: Λογική πρώτου βαθμού

Αν και η καθολική άλγεβρα παρέχει τη σημασιολογία μιας υπογραφής, η λογική παρέχει τη σύνταξη. Ακόμα και η καθολική άλγεβρα έχει κάποια περιορισμένα συντακτικά εργαλεία, με τους όρους, τις ταυτότητες και τις μερικές ταυτότητες (quasi-identities), αλλά η λογική πρώτου βαθμού προκύπτει αν οι ποσοδείκτες γίνουν ρητοί και προστεθεί η άρνηση.

Ένας τύπος (formula) πρώτου βαθμού κατασκευάζεται από ατομικούς τύπους όπως ο R(f(x,y),z) ή ο y = x + 1 μέσω των συνδέσμων Μπουλ \( \neg,\land,\lor,\rightarrow \) και προσθέτοντας στην αρχή τους ποσοδείκτες \( \forall v \) ή \( \exists v \). Μια πρόταση είναι ένας τύπος στον οποίο κάθε εμφάνιση μιας μεταβλητής βρίσκεται στην εμβέλεια ενός αντίστοιχου ποσοδείκτη. Παραδείγματα τύπων είναι οι φ (ή φ(x) για να φαίνεται ότι το πολύ το x είναι ελεύθερη μεταβλητή στο φ) και ψ που ορίζονται ως εξής:

\( {\phi \;=\; \forall u\forall v(\exists w (x\times w=u\times v)\rightarrow(\exists w(x\times w=u)\lor\exists w(x\times w=v)))\land x\ne 0\land x\ne1,}
\psi \;=\; \forall u\forall v((u\times v=x)\rightarrow (u=x)\lor(v=x))\land x\ne 0\land x\ne1. \)

(Το σύμβολο της ισότητας έχει διπλή σημασία εδώ.) Φαίνεται διαισθητικά πώς μεταφράζονται αυτοί οι τύποι σε μαθηματική σημασία. Στη σsmr-δομή \( \mathcal N \) των φυσικών αριθμών, για παράδειγμα, ένα στοιχείο n ικανοποιεί τον τύπο φ αν και μόνο αν το n είναι πρώτος αριθμός. Όμοια ο τύπος ψ ορίζει την αδυναμία αναγωγής (irreducibility). Ο Τάρσκι έδωσε έναν αυστηρό ορισμό, που κάποιες φορές ονομάζεται "ο ορισμός του Τάρσκι για την αλήθεια", για την σχέση ικανοποίησης \( \models \), ώστε να είναι εύκολο να αποδειχτεί:

\( \( \mathcal N\models\phi(n) \iff n \) είναι πρώτος αριθμός.
\mathcal N\models\psi(n) \iff n \) δεν ανάγεται.

Ένα σύνολο T από προτάσεις ονομάζεται θεωρία (πρώτης τάξης ή πρώτου βαθμού). Μια θεωρία είναι ικανοποιήσιμη αν έχει ένα μοντέλο \( \mathcal M\models T \), δηλ. μια δομή (με την κατάλληλη υπογραφή) που ικανοποιεί όλες της προτάσεις του συνόλου T. Η συνέπεια (consistency) μιας θεωρίας συνήθως ορίζεται συντακτικά, αλλά στην πρωτοβάθμια λογική, λόγω του θεωρήματος πληρότητας του Γκέντελ, δε χρειάζεται να διακρίνει κανείς μεταξύ ικανοποιησιμότητας και συνέπειας. Αυτό έχει σαν συνέπεια οι επιστήμονες της θεωρίας μοντέλων να χρησιμοποιούν τους όρους "συνεπές" και "ικανοποιήσιμο" σαν συνώνυμα.

Μια θεωρία ονομάζεται κατηγορκή (categorical) αν ορίζει μια δομή μέχρι ισομορφισμού, αλλά ο ορισμός αυτός τελικά δεν είναι χρήσιμος, λόγω σημαντικών περιορισμών στην εκφραστικότητα της πρωτοβάθμιας λογικής. Το θεώρημα Λέβενχάιμ-Σκόλεμ δείχνει ότι για κάθε θεωρία T[1] που έχει ένα άπειρο μοντέλο και για κάθε άπειρο πληθικό αριθμό κ, υπάρχει ένα μοντέλο \( \mathcal M\models T \), τέτοιο ώστε ο αριθμός των στοιχείων του \( \mathcal M \) να είναι ακριβώς κ. Επομένως μόνο πεπερασμένες δομές μπορούν να περιγραφούν από μια κατηγορική θεωρία.

Η έλλειψη εκφραστικότητας (σε σύγκριση με λογικές ανώτερου βαθμού, όπως η λογική δεύτερου βαθμού) έχει όμως και κάποια πλεονεκτήματα. Το θεώρημα Λέβενχάιμ-Σκόλεμ για τους επιστήμονες της θεωρίας μοντέλων αποτελεί ένα σημαντικό πρακτικό εργαλείο και όχι την αιτία του παραδόξου του Σκόλεμ. Η λογική πρώτου βαθμού είναι κατά κάποια έννοια (για λεπτομέρειες δείτε το θεώρημα του Lindström) η πιο εκφραστική λογική για την οποία ισχύουν ταυτόχρονα και το θεώρημα Λέβενχάιμ-Σκόλεμ και το θεώρημα της συμπάγειας:

Θεώρημα συμπαγείας
Κάθε μη ικανοποιήσιμη θεωρία πρώτου βαθμού έχει ένα πεπερασμένο μη ικανοποιήσιμο υποσύνολο.

Το σημαντικό αυτό θεώρημα, που οφείλεται στο Γκέντελ, είναι βασικής σημασίας στη θεωρία άπειρων μοντέλων, όπου η φράση "λόγω συμπαγείας" είναι συνηθισμένη. Ένας τρόπος να αποδειχτεί αυτό είναι μέσω των υπεργινομένων (ultraproducts). Μια εναλλακτική απόδειξη χρησιμοποιεί το θεώρημα της πληρότητας, το οποίο συνήθως παίζει δευτερεύοντα ρόλο στο μεγαλύτερο μέρος της σύγχρονης θεωρίας μοντέλων.
Αξιωματικοποίηση, απαλοιφή ποσοδεικτών και πληρότητα μοντέλων

Το πρώτο και συνήθως τετριμμένο βήμα για την εφαρμογή της θεωρίας μοντέλων σε μια κλάση μαθηματικών αντικειμένων όπως οι ομάδες ή τα δένδρα (στη θεωρία γράφων), είναι η επιλογή μιας υπογραφής σ και η αναπαράσταση των αντικειμένων σαν σ-δομές. Το επόμενο βήμα είναι να δειχτεί ότι η κλάση είναι μια στοιχειώδης κλάσης (elementary class), δηλ. αξιωματικοποιείται στην πρωτοβάθμια λογική (υπάρχει μια θεωρία T τέτια ώστε μια σ-δομή να ανήκει στην κλάση αν και μόνο αν ικανοποιεί την T). Για παράδειγμα, αυτό το βήμα αποτυγχάνει για τα δένδρα, επειδή η ιδιότητας της σύνδεσης (connectedness) δε μπορεί να εκφραστεί στην πρωτοβάθμια λογική. Η αξιωματικοποίηση βεβαιώνει ότι η θεωρία μοντέλων μπορεί να χειριστεί τα κατάλληλα αντικείμενα. Η απαλοιφή των ποσοδεικτών μπορεί να θεωρηθεί σαν συνθήκη που εξασφαλίζει ότι η θεωρία μοντέλων δεν παρέχει περισσότερη πληροφορία για τα αντικείμενα από όση χρειάζεται.

Μια θεωρία T έχει απαλοιφή ποσοδεικτών αν κάθε πρωτοβάθμιος τύπος φ(x₁,...,x_n) στην υπογραφή της είναι ισοδύναμος κατά T με έναν πρωτοβάθμιο τύπο ψ(x₁,...,x_n) χωρίς ποσοδείκτες, δηλ ο \( \forall x_1\dots\forall x_n(\phi(x_1,\dots,x_n)\leftrightarrow \psi(x_1,\dots,x_n)) \) ισχύει σε όλα τα μοντέλα του T. Για παράδειγμα η θεωρία των αλγεβρικά κλειστών πεδίων στην υπογραφή σring=(×,+,−,0,1) έχει απαλοιφή ποσοδεικτών γιατί κάθε τύπος είναι ισοδύναμος με ένα συνδυασμό Μπουλ από εξισώσεις μεταξύ πολυωνύμων.

Μια υπο-δομή (substructure) μιας σ-δομής είναι ένα υποσύνολο του πεδίου ορισμού της, κλειστό κάτω από όλες τις συναρτήσεις της υπογραφής σ, που θεωρείται σ-δομή με τον περιορισμό όλων των συναρτήσεων και των σχέσεων της σ στο υποσύνολο. Μια ενσωμάτωση (embedding) μιας σ-δομής \mathcal A σε μια άλλη σ-δομή \mathcal B είναι μια αντιστοίχιση f: A → B ανάμεσα στα πεδία ορισμού και μπορεί να γραφεί σαν ισομορφισμός από \( \mathcal A \) με μια υπο-δομή από \( \mathcal B \). Κάθε ενσωμάτωση είναι ένα-προς-ένα ομομορφισμός αλλά το αντίθετο ισχύει μόνο αν η υπογραφή δεν περιέχει σύμβολα σχέσεων.

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

Μια θεωρία T ονομάζεται μοντελο-πλήρης (model-complete) αν κάθε υπο-δομή ενός μοντέλου της T που είναι η ίδια μοντέλο της T είναι στοιχειώδης υπο-δομή. Ένα χρήσιμο κριτήριο για τον έλεγχο αν μια υπο-δομή είναι στοιχειώδης υπο-δομή είναι η δοκιμή Τάρσκι-Βοτ. Σύμφωνα με αυτό το κριτήριο, μια θεωρία T είναι μοντελο-πλήρης αν και μόνο αν κάθε πρωτοβάθμιος τύπος φ(x₁,...,x_n) στην υπογραφή της είναι ισοδύναμος κατά T με έναν υπαρξιακό πρωτοβάθμιο τύπο, δηλ. έναν τύπο της ακόλουθης μορφής:

\( \exists v_1\dots\exists v_m\psi(x_1,\dots,x_n,v_1,\dots,v_m), \)

όπου ο ποσοδείκτης ψ είναι ελεύθερος. Μια θεωρία που δεν είναι μοντελο-πλήρης ίσως έχει μια συμπλήρωση μοντέλου (model completion), η οποία είναι μια σχετική θεωρία μοντέλων, η οποία γενικά δεν είναι επέκταση της αρχικής θεωρίας. Μια γενικότερη έννοια είναι αυτή των συνοδευτικών μοντέλου (model companions).

Κατηγορικότητα

Οι θεωρίες πρώτου βαθμού δε μπορούν να είναι κατηγορικές (categorical), δηλ. δε μπορούν να περιγράψουν ένα μοναδικό μοντέλο μέχρι ισομορφισμού, εκτός και αν αυτό το μοντέλο είναι πεπερασμένο. Δύο διάσημα μοντελο-θεωρητικά θεωρήματα όμως αναφέρονται στην ασθενέστερη έννοια της κ-κατηγορικότητας (κ-categoricity) για έναν πληθικό αριθμό κ. Μια θεωρία T ονομάζεται κ-κατηγορική αν οποιαδήποτε δύο μοντέλα της T που έχουν πληθικό αριθμό κ είναι ισομορφικά. Όπως προκύπτει, το ερώτημα της κ-κατηγορικότητας εξαρτάται από το αν ο κ είναι μεγαλύτερος από την πληθικότητα της γλώσσας (π.χ.. \( \aleph_0 \)+ |σ|, όπου |σ| είναι η πληθικότητα της υπογραφής). Αυτό σημαίνει ότι για πεπερασμένες ή αριθμήσιμες υπογραφές υπάρχει μια βασική διαφορά μεταξύ \( \aleph_0 \)-πληθικότητας και κ-πληθικότητας για μη μετρήσιμο κ.

Ο παρακάτω χαρακτηιρσμός της \( \aleph_0 \)-κατηγορικότητας είναι κατά τους Ryll-Nardzewski, Engeler και Svenonius:

Θεώρημα Ryll-Nardzewski
Για μια πλήρη θεωρία πρώτου βαθμού T σε μια πεπερασμένη ή αριθμήσιμη υπογραφή, οι παρακάτω συνθήκες είναι ισοδύναμες:

Η T είναι \( \aleph_0 \)-κατηγορική.
Για κάθε φυσικό αριθμό n, ο χώρος Stone (Stone space) Sn(T) είναι πεπερασμένος.
Για κάθε φυσικό αριθμό n, ο αριθμός των τύπων φ(x1, ..., xn) σε n ελεύθερες μεταβλητές, μέχρι την ισοδυναμία κατά T, είναι πεπερασμένος.

Οι \( \aleph_0\)-κατηγορικές θεωρίες και τα αριθμήσιμα μοντέλα τους έχουν ισχυρή σχέση με τις ολιγομορφικές ομάδες (oligomorphic groups). Συχνά κατασκευάζονται σαν όρια Fraïssé.

Το μη-τετριμμένο αποτέλεσμα του Michael Morley ότι (για αριθμήσιμες γλώσσες) υπάρχει μόνο μια έννοια μη αριθμήσιμης κατηγορικότητας, ήταν το αρχικό σημείο για τη σύγχρονη θεωρία μοντέλων, και ειδικότερα για τη θεωρία κατάταξης και σταθερότητας:

Θεώρημα κατηγορικότητας του Morley
Αν μια θεωρία πρώτου βαθμού T σε μια πεπερασμένη και αριθμήσιμη υπογραφή είναι κ-κατηγορική για κάποιο μη αριθμήσιμο πληθικό αριθμό κ, τότε η T είναι κ-κατηγορική για όλους τους μη αριθμήσιμους πληθικούς αριθμούς κ.

Οι μη αριθμήσιμα κατηγορικές (Uncountably categorical) θεωρίες, δηλ. που είναι κ-κατηγορικές για όλους τους μη αριθμήσιμους πληθικούς αριθμούς κ, είναι από πολλές απόψεις οι θεωρίες με την πιο καλή συμπεριφορά. Μια θεωρία που είναι \( \aleph_0 \)-κατηγορική και ταυτόχρονα μη αριθμήσιμα κατηγορική ονομάζεται ολικά κατηγορική (totally categorical).
Θεωρία μοντέλων και θεωρία συνόλων

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

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

Άλλες βασικές έννοιες της θεωρίας μοντέλων
Μειώσεις και επεκτάσεις

Κύριο λήμμα: Μείωση (μαθηματικά)

Ένα πεδίο ή ένα διανυσματικό πεδίο μπορούν να θεωρηθούν (αντιμεταθετικές) ομάδες, απλά αγνοώντας μέρος της δομής τους. Η αντίστοιχη έννοια στη θεωρία μοντέλων είναι η μείωση (reduct) μιας δομής σε ένα υποσύνολο της αρχικής της υπογραφής. Η αντίστροφη σχέση ονομάζεται επέκταση (expansion) - π.χ. η (προσθετική) ομάδα των πραγματικών αριθμών, θεωρούμενη σαν δομή στην υπογραφή {+,0} μπορεί να επεκταθεί σε ένα πεδίο με την υπογραφή {×,+,1,0} ή σε μια διατεταγμένη ομάδα με την υπογραφή {+,0,<}.

Όμοια, αν σ' είναι μια υπογραφή που επεκτείνει μια άλλη υπογραφή σ, τότε μια πλήρης σ'-θεωρία μπορεί να περιοριστεί στη σ με την τομή του συνόλου των προτάσεών της με το σύνολο των σ-τύπων. Αντίστροφα, μια πλήρης σ-θεωρία μπορεί να θεωρηθεί σ'-θεωρία και μπορεί να επεκταθεί (με διάφορους τρόπους) σε μια πλήρη σ'-θεωρία. Οι όροι μείωση και επέκταση κάποιες φορές χρησιμοποιούνται και για αυτήν τη σχέση.
Τύποι[2]

Κύριο λήμμα: Τύπος (θεωρία μοντέλων)

Έστω μια L-δομή M, και ένας φυσικός αριθμός n. Το σύνολο των οριζόμενων υποσυνόλων του M^n σε κάποιες παραμέτρους A είναι μια άλγεβρα Μπουλ. Από το θεώρημα αναπαράστασης του Στόουν για τις άλγεβρες Μπουλ προκύπτει μια φυσική δυική (dual) έννοια. Μπορεί να θεωρηθεί τοπολογικός χώρος που αποτελείται από μέγιστα σύνολα από τύπους (formulae) στο A. Αυτό αποκαλείται ο χώρος των (πλήρων) n-τύπων (n-types) στο A και γράφεται σαν \( S_n(A) \).

Έστω ένα στοιχείο \(m \in M^n \). Τότε το σύνολο όλων των \(\phi \) με παραμέτρους που ανήκουν στο A σε ελεύθερες μεταβλητές \( x_1,\ldots,x_n \) ώστε \( M \models \phi(m) \) είναι συνεπές και μέγιστο. Ονομάζεται ο τύπος (type) του m στο A.

Μπορεί να δειχτεί ότι για κάθε n-τύπο p, υπάρχει κάποια στοιχειώδης επέκταση N του M και κάποιος \( a \in N^n \) τέτοιο ώστε ο p να είναι ο τύπος του a στο A.

Πολλές σημαντικές ιδιότητες της θεωρίας τύπων μπορούν να εκφραστούν με τους τύπους. Επιπλέον, πολλές αποδείξεις κατασκευάζουν μοντέλα με στοιχεία που περιέχουν στοιχεία συγκεκριμένων τύπων, τα οποία και στη συνέχεια χρησιμοποιούν.

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

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

Ερμηνεία

Κύριο λήμμα: Ερμηνεία (θεωρία μοντέλων)

Δεδομένης μιας μαθηματικής δομής, πολλές φορές υπάρχουν σχετικές δομές που να μπορούν να κατασκευαστούν σαν υπόλοιπο μέρους της αρικής δομής, μέσω μιας σχέσης ισοδυναμίας. Σημαντικό παράδειγμα αποτελεί η υπόλοιπη ομάδα (quotient group) μιας ομάδας.

Κατά μια άποψη, η κατανόηση της πλήρους δομής απαιτεί την κατανόηση αυτών των υπολοίπων. Όταν μπορεί να οριστεί η σχέση ισοδυναμίας, μπορεί να δοθεί ακριβές περιεχόμενο στην προηγούμενη πρόταση και οι δομές αυτές ονομάζονται ερμηνεύσιμες (interpretable).

Ένα σημαντικό γεγονός είναι ότι προτάσεις από τη γλώσσα των δομών που ερμηνεύονται μπορούν να μεταφραστούν στη γλώσσα της αρχικής δομής. Με αυτόν τον τρόπο, μπορεί να δειχτεί ότι αν μια δομή M ερμηνεύει κάποια άλλη δομή, της οποίας η θεωρία είναι μη-υπολογίσιμη, τότε η ίδια η M είναι μη-υπολογίσιμη.
Χρήση των θεωρημάτων συμπαγείας και πληρότητας

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

Το θεώρημα της συμπαγείας (compactness theorem) δηλώνει ότι ένα σύνολο από προτάσεις S είναι ικανοποιήσιμο αν κάθε πεπερασμένο υποσύνολό του είναι ικανοποιήσιμο. Το ανάλογο θεώρημα στη θεωρία αποδείξεων είναι τετριμμένο, γιατί κάθε απόδειξη μπορεί να έχει πεπερασμένο αριθμό προηγούμενων που χρησιμοποιούνται στην απόδειξη. Η απόδειξη αυτή όμως στη θεωρία μοντέλων είναι πιο δύσκολη. Υπάρχουν δύο γνωστές αποδείξεις, μία από τον Κουρτ Γκέντελ (που χρησιμοποιεί αποδείξεις) και μια από τον Μάλτσεβ (πιο ευθεία και επιτρέπει τον περιορισμό της πληθικότητας του μοντέλου που προκύπτει).

Η θεωρία μοντέλων συχνά ασχολείται με τη λογική πρώτου βαθμού και πολλά σημαντικά αποτελέσματα (όπως τα θεωρήματα πληρότητας και συμπαγείας) δεν ισχύουν στη λογική δεύτερου βαθμού ή σε άλλες λογικές. Στη λογική πρώτου βαθμού όλοι οι άπειροι πληθικοί αριθμοί δείχνουν το ίδιο σε μια αριθμήσιμη γλώσσα. Αυτό εκφράζεται από το θεώρημα Λέβενχάιμ-Σκόλεμ, που δηλώνει ότι κάθε αριθμήσιμη θεωρία με ένα άπειρο μοντέλο \( \mathfrak{A} \) έχει μοντέλα όλων των άπειρων πληθικοτήτων (τουλάχιστον της γλώσσας) που συμφωνούν με το \( \mathfrak{A} \) σε όλες τις προτάσεις, είναι δηλαδή 'στοιχειωδώς ισοδύναμα' ('elementarily equivalent').

Δείτε επίσης

Θεώρημα Λέβενχάιμ-Σκόλεμ
Θεώρημα συμπαγείας
Θεωρία αποδείξεων
Σημασιολογία του Κρίπκε

Παραπομπές

Σε μια αριθμήσιμη υπογραφή. Το θεώρημα μπορεί να επεκταθεί εύλογα σε μη αριθμήσιμες υπογραφές.
Ο όρος "τύπος" αντιστοιχεί στον αγγλικό όρο "type" και έχει διαφορετική σημασία από την παραπάνω χρήση της λέξης "τύπος" σαν μετάφραση του "formula". Δυστυχώς ο ελληνικός όρος "τύπος" απαντάται στην ελληνική βιβλιογραφία και με τις δύο σημασίες, ανάλογα με τα συμφραζόμενα.

All three commentators [i.e. Vaught, van Heijenoort and Dreben] agree that both the completeness and compactness theorems were implicit in Skolem 1923 [...], Dawson (1993).

Αναφορές
Βασικά βιβλία

Chang, Chen Chung; Keisler, H. Jerome (1990) [1973]. Model Theory. Studies in Logic and the Foundations of Mathematics (3rd έκδοση). Elsevier. ISBN 978-0-444-88054-3
Hodges, Wilfrid (1997). A shorter model theory. Cambridge: Cambridge University Press. ISBN 978-0-521-58713-6

Επιπλέον βιβλία

Bell, John L.; Slomson, Alan B. (2006) [1969]. Models and Ultraproducts: An Introduction (reprint of 1974 έκδοση). Dover Publications. ISBN 0-486-44979-3.
Ebbinghaus, Heinz-Dieter; Flum, Jörg; Thomas, Wolfgang (1994). Mathematical Logic. Springer. ISBN 0-38794258-0.
Hinman, Peter G. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1-568-81262-0.
Hodges, Wilfrid (1993). Model theory. Cambridge University Press. ISBN 0-521-30442-3.
Marker, David (2002). Model Theory: An Introduction. Graduate Texts in Mathematics 217. Springer. ISBN 0-387-98760-6.
Poizat, Bruno (2000). A Course in Model Theory. Springer. ISBN 0-387-98655-3.
Rothmaler, Philipp (2000). Introduction to Model Theory (new έκδοση). Taylor & Francis. ISBN 9056993135.

Ελεύθερα κείμενα στο διαδίκτυο

Chatzidakis, Zoe (2001). Introduction to Model Theory, σελ. 26 σε μορφή DVI.
Pillay, Anand (2002). Lecture Notes – Model Theory, σελ. 61.
Hodges, Wilfrid, First-order Model theory. The Stanford Encyclopedia Of Philosophy, E. Zalta (ed.).
Simmons, Harold (2004), An introduction to Good old fashioned model theory. Σημειώσεις εισαγωγικου μαθήματος για μεταπτυχιακούς φοιτητές (με ασκήσεις).
J. Barwise and S. Feferman (editors), Model-Theoretic Logics, Perspectives in Mathematical Logic, Volume 8, New York: Springer-Verlag, 1985.

Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Model theory της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).

Εγκυκλοπαίδεια Μαθηματικών

Κόσμος

Αλφαβητικός κατάλογος

Hellenica World - Scientific Library

Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License