Θεωρία (μαθηματική λογική)

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

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

Θεωρίες εκφρασμένες σε τυπική γλώσσα γενικά[Επεξεργασία | επεξεργασία κώδικα]

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

Η κατασκευή μιας θεωρίας αρχίζει με το να προδιαγράψουμε μία καθορισμένη μη-κενή εννοιολογική κλάση \Sigma, τα στοιχεία της οποίας καλούνται δηλώσεις. Αυτές οι αρχικές δηλώσεις συχνά καλούνται πρωτόγονα στοιχεία ή στοιχειώδεις δηλώσεις της θεωρίας, για να τις ξεχωρίζουμε από τις άλλες δηλώσεις οι οποίες μπορεί να παραχθούν από αυτές.

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

Αυτός ο γενικός τρόπος καθορισμού μιας θεωρίας συνομολογεί πως η αλήθεια οποιασδήποτε από τις στοιχειώδεις δηλώσεις της δεν είναι γνωστή χωρίς αναφορά στην \Theta. Έτσι, η ίδια στοιχειώδης δήλωση μπορεί να είναι αληθής σε σχέση με μια θεωρία και να μην είναι σε σχέση με μία άλλη. Αυτό είναι όπως και στην συνήθη γλώσσα, όπου δηλώσεις όπως «Αυτός είναι ένας τρομερός άνθρωπος.» δεν μπορούν να κριθούν αν είναι αληθείς ή ψευδείς χωρίς αναφορά σε κάποια ερμηνεία του ποιος είναι «Αυτός» και τι σημαίνει να είσαι «τρομερός άνθρωπος» ως προς αυτή τη θεωρία.[1]

Υποθεωρίες και επεκτάσεις[Επεξεργασία | επεξεργασία κώδικα]

Μπορούμε να ορίσουμε μια θεωρία \Theta' ώστε να είναι μια υποθεωρία μίας άλλης \Theta ή ώστε να είναι μια επέκταση ή υπερθεωρία μιας άλλης χρησιμοποιώντας το συμβολισμό της θεωρίας συνόλων. Για παράδειγμα, για την περίπτωση της υποθεωρίας έχουμε \Theta' \subseteq \Theta αν κάθε στοιχειώδης δήλωση της \Theta' είναι επίσης και της \Theta.[1]

Συνεπαγωγικές θεωρίες[Επεξεργασία | επεξεργασία κώδικα]

Μια θεωρία λέγεται πως είναι μια συνεπαγωγική θεωρία αν η \Theta είναι επαγωγική κλάση. Αυτό σημαίνει ότι το περιεχόμενό της βασίζεται σε κάποιο τυπικό επαγωγικό σύστημα και ότι μερικές από τις στοιχειώδεις της δηλώσεις παίρνονται ως αξιώματα. Σε μια συνεπαγωγική θεωρία, οποιαδήποτε πρόταση είναι λογική συνέπεια ενός ή περισσοτέρων από τα αξιώματα είναι επίσης και πρόταση εκείνης της θεωρίας.[1]

Συνέπεια και πληρότητα[Επεξεργασία | επεξεργασία κώδικα]

Κύρια λήμματα: Συνέπεια και Πληρότητα

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

Μία ικανοποιήσιμη θεωρία είναι μια θεωρία που έχει ένα μοντέλο. Αυτό σημαίνει ότι υπάρχει μία δομή \Delta που ικανοποιεί κάθε πρόταση στη θεωρία. Κάθε ικανοποιήσιμη θεωρία είναι και συντακτικά συνεπής, επειδή η δομή που ικανοποιεί την θεωρία θα ικανοποιεί ακριβώς μία εκ των \Pi και άρνηση της \Pi για κάθε πρόταση \Pi.

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

Μία πλήρης συνεπής θεωρία (ή απλά μία πλήρης θεωρία) είναι μία συνεπής θεωρία \Theta τέτοια ώστε για κάθε πρόταση \Pi στη γλώσσα της, ή η \Pi είναι αποδείξιμη από την \Theta ή η \Theta \cup {\Pi} είναι ασυνεπής. Για τις θεωρίες που είναι κλειστές ως προς τη λογική συνέπεια, αυτό σημαίνει πως για κάθε πρόταση \Pi, ή η \Pi ή η άρνησή της περιέχονται στη θεωρία. Μια μη-πλήρης θεωρία είναι μια συνεπής θεωρία που δεν είναι πλήρης.

Δείτε επίσης το άρθρο ω-συνεπής θεωρία για μια ισχυρότερη αντίληψη της συνέπειας.

Ερμηνεία μιας θεωρίας[Επεξεργασία | επεξεργασία κώδικα]

Κύριο λήμμα: Ερμηνεία (λογική)

Ερμηνεία μιας θεωρίας είναι η σχέση ανάμεσα σε μια θεωρία και κάποιο υποκειμενικό περιεχόμενο, στην οποία περίπτωση υπάρχει μια αντιστοιχία πολλά-προς-ένα ανάμεσα σε συγκεκριμένες προτάσεις περιεχομένου που σχετίζονται με το υποκειμενικό περιεχόμενο. Αν κάθε στοιχειώδης πρόταση στη θεωρία έχει μια αντιστοίχιση περιεχομένου, η σχέση καλείται ολική ερμηνεία, αλλιώς καλείται μερική ερμηνεία.[2]

Κατά άλλη κοινή ορολογία, οι θεωρίες μπορούν να συνδέονται με μια δομή. Η πλήρης θεωρία μιας δομής \Delta είναι το σύνολο όλων των προτάσεων πρώτης τάξης πάνω στην υπογραφή της \Delta οι οποίες ικανοποιούνται από την \Delta. Αυτό σημειώνεται με \Theta(\Delta). Γενικότερα, η θεωρία της \Kappa, μιας κλάσης από σ-δομές, είναι το σύνολο όλων των σ-προτάσεων πρώτης τάξης που ικανοποιούνται από όλες τις δομές στην \Kappa, και σημειώνεται με \Theta(\Kappa). Σαφώς \Theta(\Delta) = \Theta({\Delta}). Αυτές οι έννοιες μπορούν επίσης να οριστούν σε σχέση και με άλλες λογικές.

Για μια σ-δομή \Delta, υπάρχουν αρκετές θεωρίες που συνδέονται με αυτήν σε μια μεγαλύτερη υπογραφή σ' που επεκτείνει την σ προσθέτοντας ένα καινούργιο σταθερό σύμβολο για κάθε στοιχείο της επικράτειας της \Delta. (Εαν τα νέα σταθερά σύμβολα ταυτοποιούνται με τα στοιχεία της \Delta τα οποία αντιπροσωπεύουν, η σ' μπορεί να θεωρηθεί ως σ \cup \Delta.) Η πληθικότητα (cardinality) της σ' τότε είναι η μεγαλύτερη από τις πληθικότητες της σ και της \Delta.

Το διάγραμμα της \Delta αποτελείται από όλες τις ατομικές ή αρνηθείς ατομικές σ'-προτάσεις που ικανοποιούνται από την \Delta και σημειώνεται ως \Gamma\Delta. Το θετικό διάγραμμα της \Delta είναι το σύνολο όλων των ατομικών σ'-προτάσεων τις οποίες ικανοποιεί η \Delta. Αυτό σημειώνεται με \Gamma+\Delta. Το στοιχειώδες διάγραμμα της \Delta είναι το σύνολο \Gamma*\Delta από όλες τις σ'-προτάσεις πρώτης τάξης που ικανοποιούνται από την \Delta ή, ισοδύναμα, η πλήρης θεωρία (πρώτης τάξης) της φυσικής επέκτασης της \Delta στην υπογραφή σ'.

Παραδείγματα[Επεξεργασία | επεξεργασία κώδικα]

Ένας τρόπος να προδιαγράψουμε μια θεωρία είναι να ορίσουμε ένα σύνολο από αξιώματα σε μια συγκεκριμένη γλώσσα. Η θεωρία μπορεί να θεωρηθεί πως περιέχει μόνο εκείνα τα αξιώματα ή και τις λογικές ή αποδείξιμές τους συνέπειες, όπως εμείς επιθυμούμε. Θεωρίες που αποκτήθηκαν με αυτόν τον τρόπο αποτελούν η ZFC και η αριθμητική του Πεάνο.

Ένας δεύτερος τρόπος να προδιαγράψουμε μια θεωρία είναι να αρχίσουμε με μία δομή και μετά να θέσουμε τη θεωρία ως το σύνολο των τύπων που ικανοποιούνται από τη δομή. Αυτή είναι μια μέθοδος για την παραγωγή πλήρων θεωριών. Παραδείγματα των θεωριών αυτής της μορφής αποτελούν τα σύνολα των αληθών προτάσεων στις δομές (\mathbb{N}, +, ×, 0, 1, =) και (\mathbb{R}, +, ×, 0, 1, =), όπου \mathbb{N} είναι το σύνολο των φυσικών αριθμών και \mathbb{R} είναι το σύνολο των των πραγματικών αριθμών. Η πρώτη από αυτές, που καλείται η θεωρία της αληθινής αριθμητικής, δεν μπορεί να γραφτεί ως ένα σύνολο από λογικές συνέπειες από κάποιο απαριθμήσιμο σύνολο από αξιώματα. Η θεωρία του (\mathbb{R}, +, ×, 0, 1, =) δείχθηκε από τον Τάρσκι πως είναι αποφασίσιμη — είναι η θεωρία των πραγματικών κλειστών πεδίων.

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. 1,0 1,1 1,2 Curry, Haskell, Foundations of Mathematical Logic
  2. Curry, Haskell, Foundations of Mathematical Logic σελ.48

Βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]

  • Hodges, Wilfrid (1997). A shorter model theory. Cambridge University Press. ISBN 0-521-58713-1. 
Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα theory (mathematical logic) της Αγγλόγλωσσης Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).