Λογική δευτέρου βαθμού

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

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

Η λογική πρώτης τάξης υπολογίζει ποσοτικά μόνο μεταβλητές οι οποίες είναι διακριτές (στοιχεία από το πεδίο αναφοράς - domain of discourse). Η λογική δεύτερης τάξης, επίσης ποσοτικοποιεί πάνω στις σχέσεις. Για παράδειγμα, η δεύτερης τάξης πρόταση \forall P\,\forall x (x \in P \lor x \notin P) δηλώνει ότι για κάθε μοναδιαία σχέση (ή σύνολο) P από στοιχεία και για κάθε στοιχείο x, είτε x ανήκει στο P είτε δεν ανήκει (αυτή είναι η αρχή principle of bivalence). Η λογική δεύτερης τάξης επίσης περιέχει ποσοτικοποίηση πάνω σε συναρτήσεις, και άλλες μεταβλητές όπως εξηγείτε εδώ Syntax and fragments . Τόσο η πρώτης τάξης λογική όσο και η δεύτερης χρησιμοποιούν την ιδέα του πεδίου αναφοράς (domain of discourse, συχνά λέγεται απλά "πεδίο" ή "σύμπαν"). Το πεδίο είναι το σύνολο των επιμέρους στοιχείων τα οποία μπορούν να ποσοτικοποιηθούν.

Σύνταξη και fragments[Επεξεργασία | επεξεργασία κώδικα]

Η σύνταξη της λογικής δεύτερης τάξης μας λέει ποιες εκφράσεις είναι ορθά δομημένοι τύποι (well-formed formula). Επιπρόσθετα της σύνταξης της λογικής πρώτης τάξης, η λογική δεύτερης τάξης περιλαμβάνει πολλά νέα είδη (μερικές φορές αποκαλούνται τύποι) μεταβλητών. Αυτά είναι:

  • Ένα είδος μεταβλητών που εκτείνονται πάνω από ομάδες στοιχείων. Αν S είναι μια τέτοια μεταβλητή και t είναι ένας πρώτης τάξης όρος τότε η έκφραση tS (επίσης γράφεται S(t), ή St για να γλιτώσουμε τις παρενθέσεις) είναι ένας ατομικός τύπος (atomic formula). Ομάδες από στοιχεία μπορούν επίσης να μελετηθούν ως μοναδιαίες σχέσεις (unary relations) του τομέα.
  • Για κάθε φυσικό αριθμό k υπάρχει ένα είδος μεταβλητών που κυμαίνονται πάνω από τις k σχέσεις των στοιχείων. Αν η R είναι μια τέτοια k-αδική σχέση μεταβλητής και t1,..., tk είναι πρώτης τάξεως όροι τότε η έκφραση R(t1,...,tk) είναι ένας ατομικός τύπος.
  • Για κάθε φυσικό αριθμό k υπάρχει ένα είδος μεταβλητών που κυμαίνεται πάνω από τις δοθέντες συναρτήσεις με k στοιχεία του τομέα και επιστρέφει ένα μοναδικό στοιχείο του τομέα. Αν η f είναι μια τέτοια k-αδική συνάρτηση μεταβλητών και t1,...,tk είναι πρώτης τάξης στοιχεία τότε η έκφραση f(t1,...,tk) είναι ένας πρώτης τάξεως όρος.

Κάθε μια από τις μεταβλητές που ορίσαμε μπορεί να γίνει καθολικά και/ή υπαρξιακά ποσοτικά, ώστε να φτιάξει άλλους τύπους. Για αυτό υπάρχουν πολλών ειδών ποσοδείκτες, δύο για κάθε είδος μεταβλητής. Μια πρόταση σε λογική δεύτερης τάξης, όπως και σε μια πρώτης, είναι ένας ορθά δομημένος τύπος (well-formed formula) χωρίς ανεξάρτητες μεταβλητές (οποιουδήποτε είδους).

Είναι δυνατό να αφήσουμε την εισαγωγή των συναρτήσεων μεταβλητών που δίνεται στον ορισμό παραπάνω (και μερικοί συγγραφείς το κάνουν) καθώς μια n-αδική συνάρτηση μεταβλητών μπορεί να αναπαρασταθεί από μια σχέση μεταβλητών arity n+1 και έναν κατάλληλο τύπο για την μοναδικότητα του "αποτελέσματος" στο n+1 επιχείρημα της σχέσης. (Shapiro 2000, p. 63)

Monadic second-order logic (MSOL) είναι ένας περιορισμός της δεύτερης τάξης λογικής στην οποία μόνο ποσοτικοποιήσεις πάνω σε μοναδιαίες σχέσεις (π.χ σύνολα) είναι επιτρεπτές. Ποσοτικοποιήσεις πάνω σε συναρτήσεις, οφειλόμενες στην ισοδυναμία των σχέσεων όπως περιγράφηκε παραπάνω, είναι μη επιτρεπτές. Η δεύτερης τάξης λογική χωρίς αυτούς τους περιορισμούς αποκαλείτε κάποιες φορές full second-order logic (πλήρης λογική δεύτερης τάξης) ώστε να την ξεχωρίζουμε από την monadic εκδοχή.

Όπως ακριβώς και στην πρώτης τάξεως λογική, η δεύτερης τάξης μπορεί να περιλαμβάνει μη λογικά σύμβολα (non-logical symbols) σε μια συγκεκριμένη δεύτερης τάξης γλώσσα. Αυτά είναι περιορισμένα, όμως, όλοι οι όροι που σχηματίζονται πρέπει να είναι είτε πρώτης τάξεως όροι (το οποίο μπορεί να υποκατασταθεί για μιας πρώτης τάξεως μεταβλητή) είτε δεύτερης (το οποίο μπορεί να υποκατασταθεί με μια δεύτερης τάξης και κατάλληλου είδους μεταβλητή).

Μια σχέση σε μια δεύτερης τάξης λογική λέγεται ότι είναι πρώτης τάξης (και μερικές φορές συμβολίζεται \Sigma^1_0 or \Pi^1_0) εάν οι ποσοδείκτες της (που μπορεί να είναι οποιουδήποτε είδους) καλύπτουν μόνο μεταβλητές πρώτης τάξης, αν και μπορεί να έχει ανεξάρτητες μεταβλητές δεύτερης τάξης. Μια \Sigma^1_1 (υπαρκτή δεύτερης τάξης) μέθοδος είναι ακόμα μια που έχει κάποιους υπαρξιακούς ποσοδείκτες πάνω σε μεταβλητές δεύτερης τάξης, π.χ. \exists R_0\ldots\exists R_m \phi, όπου \phi είναι ένας τύπος πρώτης τάξης. The fragment της δεύτερης λογικής τάξης που αποτελείται μόνο από υπαρξιακή τύπων δεύτερης τάξης ονομάζεται existential second-order logic και με τη συντομογραφία ESO, ως \Sigma^1_1, ή ακόμη και ως ∃SO. The fragment των \Pi^1_1 τύπων ορίζεται διττά, αυτό ονομάζεται καθολική λογική δεύτερης τάξης. Πιο εκφραστικά fragments ορίζονται για κάθε k > 0 με αμοιβαία αναδρομή: \Sigma^1_{k+1} έχει τη μορφή \exists R_0\ldots\exists R_m \phi, όπου \phi είναι μια \Pi^1_k formula, και όμοιαr, \Pi^1_{k+1} έχει τη μορφή \forall R_0\ldots\forall R_m \phi, όπου \phi είναι ένας \Sigma^1_k τύπος. (Δες analytical hierarchy για την ανάλογη κατασκευή του second-order arithmetic.)

Σημασιολογία[Επεξεργασία | επεξεργασία κώδικα]

Η σημασιολογία της λογικής δεύτερης τάξης καθορίζει την σημασία κάθε πρότασης. Αντίθετα με την λογική πρώτης τάξης, η οποία έχει μοναδική σημασιολογία, υπάρχουν δυο ειδών σημασιολογίες που χρησιμοποιούνται συνήθως για τη λογική δεύτερης τάξης: κανονική (standard semantics) και η σημασιολογία Henkin (Henkin semantics). Σε κάθε μια από αυτές, οι ερμηνείες των ποσοδεικτών πρώτης τάξεως και των λογικών συνδέσμων είναι ίδιοι όπως και στην πρώτης τάξης λογική. Μόνο οι σειρές των ποσοδεικτών των μεταβλητών δεύτερης τάξης διαφέρουν ανάμεσα στους δυο τύπους σημασιολογίας (Väänänen 2001).

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

Στην σημασιολογία Henkin, κάθε είδος της μεταβλητής δεύτερης τάξης έχει μια συγκεκριμένη περιοχή να καλύψει, η οποία μπορεί να είναι γνήσιο υποσύνολο από όλα τα σύνολα ή συναρτήσεις αυτού του είδους. Ο Leon Henkin (1950) όρισε αυτήν την σημασιολογία και απέδειξε το θεώρημα πληρότητας του Γκέντελ και θεώρημα του συμπαγούς, που ισχύουν για την πρώτης τάξης λογική, και συνεχίζουν να ισχύουν και στην δεύτερης τάξης λογική με την σημασιολογία Henkin. Αυτό συμβαίνει καθώς η σημασιολογία Henkin είναι σχεδόν ίδια με την πολυτυπική σημασιολογία πρώτης τάξης, όπου επιπλέον είδη μεταβλητών προστίθενται ώστε να προσομοιώσει τις νέες μεταβλητές σε δεύτερης τάξης λογική. Δεύτερης τάξης λογική με σημασιολογία Henkin δεν είναι περισσότερο εκφραστική από την πρώτης τάξης λογική. Η σημασιολογία Henkin χρησιμοποιείται συνήθως στη μελέτη της αριθμητικής δεύτερης τάξης (second-order arithmetic).

Ο Väänänen (2001) συμφώνησε ότι η επιλογή ανάμεσα στα μοντέλα Henkin και στα πλήρη μοντέλα για λογική δεύτερης τάξης είναι ανάλογη με την επιλογή ανάμεσα στο ZFC και στο V ως βάση για τη θεωρία σύνολων: "Όσον αφορά την δεύτερης τάξης λογική, δεν μπορούμε να επιλέξουμε αν θα την αξιωματοποιήσουμε με "V" η με ZFC. Το αποτέλεσμα είναι το ίδιο και στις δύο περιπτώσεις, αφού το ZFC "είναι" η καλύτερη προσπάθεια για να χρησιμοποιήσουμε το "V" ως ένα αξίωμα για τα μαθηματικά.

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

Η λογική δεύτερης τάξης είναι πιο εκφραστική από τη λογική πρώτης τάξης. Για παράδειγμα, αν το πεδίο ορισμού είναι το σύνολο όλων των πραγματικών αριθμών, κάποιος μπορεί να υποστηρίξει σε μιας πρώτης τάξης λογική την ύπαρξη του αντίστροφου αριθμού όσον αφορά την πρόσθεση γράφοντας ∀xy (x + y = 0) αλλά κάποιος χρειάζεται μια δεύτερης τάξης λογική για να υποστηρίξει την ύπαρξη ελάχιστου άνω φράγματος για σύνολα πραγματικών αριθμών, το οποίο αναφέρει ότι κάθε φραγμένο, μη κενό σύνολο πραγματικών αριθμών έχει supremum. Αν το πεδίο ορισμού είναι όλοι οι πραγματικοί αριθμοί, η ακόλουθη δεύτερης τάξης λογική πρόταση (split over two lines) εκφράζει την ιδιότητα του μικρότερου άνω φράγματος:

(∀ A) ([(∃ w) (w ∈ A)(∃ z)(∀ u)(u ∈ A → u ≤ z)]
(∃ x)(∀ y)[(∀ w)(w ∈ A → w ≤ y) ↔ (x ≤ y)])

Αυτή η μέθοδος είναι μια άμεση μορφοποίηση της "κάθε μη κενό, φραγμένο σύνολο A ένα ελάχιστο άνω φράγμα." Η ιδιότητα του ελάχιστου άνω φράγματος δεν μπορεί να εκφραστεί από κανένα σύνολο προτάσεων σε πρώτης τάξεως λογική, καθώς οι πραγματικοί αριθμοί είναι ως ισομορφισμός ο μοναδικός τομέας που ικανοποιεί αυτή την ιδιότητα , ενώ το σύνολο των προτάσεων πρώτης τάξης που ισχύουν στην πραγματικότητα έχουν αυθαίρετα μεγάλα μοντέλα λόγο του compactness theorem (θεώρημα του συμπαγούς). (Στην πραγματικότητα, κάθε real-closed field ικανοποιεί τις ίδιες πρώτης τάξεως προτάσεις στην υπογραφή \langle +,\cdot,\le\rangle όπως οι πραγματικοί αριθμοί.)

Στην δεύτερης τάξης λογική, είναι δυνατό να γράψεις τυπικές προτάσεις οι οποίες λένε "το πεδίο ορισμού είναι πεπερασμένο " ή "το πεδίο ορισμού είναι μετρήσιμης πληθικότητας ."Για να πούμε ότι το πεδίο ορισμού είναι πεπερασμένο , χρησιμοποιουμε την πρόταση surjective συνάρτηση από το πεδίο ορισμού στον εαυτό του injective.Για να πούμε ότι το πεδίο ορισμού έχει μετρήσιμη πληθικότητα , χρησιμοποιούμε την πρόταση που λέει οι υπάρχει bijection ανάμεσα σε κάθε δυο άπειρα υποσύνολα του πεδίου . Προκύπτει από τα compactness theorem και το upward Löwenheim–Skolem theorem ότι είναι αδύνατο να χαρακτηρισεις το κατά πόσο είναι πεπερασμένο ή άπειρο ή την μετρησιμότητα , αντίστοιχα, σε πρώτης τάξης λογική.

Συγκεκριμένα στοιχειά της δεύτερης τάξης λογική όπως το ESO είναι πιο εκφραστικά από πρώτης τάξης λογική αν και είναι αυστηρά λιγότερο εκφραστικά από πλήρης δεύτερης τάξης λογική. Η ESO διαθέτει επίσης τη μετάφραση ισοδύναμα με ορισμένες επεκτάσεις της λογικής πρώτης τάξης που επιτρέπουν σε μη-γραμμική διάταξη των εξαρτήσεων quantifier, όπως πρώτης τάξης λογικές εμπλουτισμένες με Henkin quantifiers, Hintikka και Sandu's ανεξάρτητη λογική , και Väänänen's εξαρτώμενη λογική .

Επαγωγικά Συστήματα[Επεξεργασία | επεξεργασία κώδικα]

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

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

Τα αφαιρετικά συστήματα που θεωρήθηκαν από τους Shapiro (1991) και Henkin (1950) προσθέτουν στο αυξημένο αφαιρετικό σύστημα πρώτης τάξης και τα δύο αξιώματα κατανόησης και αξιώματα επιλογής. Αυτά τα αξιώματα είναι υγιή για τη σημασιολογία δεύτερης τάξης. Είναι ήχος για Henkin σημασιολογία, αν είναι μόνο τα μοντέλα Henkin που ικανοποιούν την κατανόηση και αξιώματα επιλογής.[3]

Μη-υποβαθμισημότητα σε λογική πρώτης τάξης[Επεξεργασία | επεξεργασία κώδικα]

Κάποιος μπορεί να προσπαθήσει να ""μειώσει"" την δεύτερης τάξης λογική των πραγματικών αριθμών, με πλήρη δεύτερης τάξης σημασιολογία,σε πρώτης τάξης θεωρία με τον ακόλουθο τρόπο.Πρώτα επέκτεινε το πεδίο ορισμού από το σύνολο όλων των πραγματικών αριθμών σε ένα διπλής ταξινόμησης τομέα, με ers. Πρόσθεσε ένα νέο binary predicate (δυαδικό κατηγόρημα) στην γλώσσα: την σχέση μέλους . Τότε προτάσεις που ήταν δεύτερης τάξης γίνονται πρώτης τάξης, με τις πρώην ποσοδείκτες δεύτερης τάξης που κυμαίνονται πάνω από το δεύτερο είδος. Αυτή η μείωση-υποβάθμιση μπορεί να επιχειρηθεί σε μια ταξινομημένη θεωρία με την προσθήκη μοναδιαίου κατηγορήματος που αναφέρουν αν ένα στοιχείο είναι αριθμός ή σύνολο, και κάνοντας το πεδίο ορισμού να είναι η ένωση του σύνολου των πραγματικών αριθμών και το δυναμοσύνολο power set των πραγματικών αριθμών.

Αλλά παρατηρούμε ότι το πεδίο ορισμού ήταν τέτοιο ώστε να περιεχέι όλα τα σύνολα των πραγματικών αριθμών all .Αυτός ο περιορισμός δεν μπορεί να αναχθεί σε πρώτης τάξεως πρόταση , όπως το Löwenheim–Skolem theorem δείχνει. Το θεώρημα αυτό αναφέρει πως υπάρχει κάποιο μετρήσιμο άπειρο υποσύνολο των πραγματικών αριθμών, του οποίου τα στοιχειά θα τα αποκαλούμε (εσωτερικούς αριθμούς) internal numbers, και κάποιες μετρήσιμες μη πεπερασμένες συλλογές από σύνολα τέτοιων εσωτερικόν αριθμών, των οποίων τα στοιχειά θα λέμε εσωτερικά σύνολα "internal sets", τέτοια ώστε το πεδίο ορισμού που περιέχει αυτούς τους εσωτερικούς αριθμούς και τα εσωτερικά σύνολα ικανοποιούν ακριβώς την ίδια πρώτης τάξεως πρόταση όπως την ικανοποιεί το πεδίο των πραγματικών αριθμών και τα σύνολα των πραγματικών αριθμών. Ειδικότερα, ικανοποιεί ένα είδος αξιώματος για το ελάχιστο άνω φράγματος οποίο λέει βασικά ότι:

Κάθε μη-κενό (εσωτερικό) internal σύνολο το οποίο έχει (εσωτερικά) internal άνω φράγμα έχει ένα εσωτερικά internal άνω φράγμα.

Η μετρησιμότητα του συνόλου όλων των εσωτερικών αριθμών (σε αντίθεση με το γεγονός ότι αυτοί αποτελούν ένα πυκνά διατεταγμένο σύνολο) σημαίνει ότι το σύνολο αυτό δεν ικανοποιεί το πλήρες αξίωμα ελαχίστου άνω φράγματος. μετρισιμοτητα του συνόλου όλων των εσωτερικών συνόλων σημαίνει ότι δεν είναι το σύνολο όλων των υποσυνόλων του συνόλου όλων των εσωτερικών αριθμών αφού το θεώρημα του cantor (since Cantor's theorem) μας δίνει ότι το σύνολο όλων των υποσυνόλων από ένα μετρήσιμο άλλα άπειρο σύνολο είναι ένα μη μετρήσιμο άπειρο σύνολο . Αυτή η κατασκευή είναι στενά συνδεδεμένη με το Skolem's paradox.

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

Υπάρχουν κάποια ακραία παραδείγματα τα οποία δείχνουν ότι η δεύτερης τάξης λογική με κανονική σημασιολογία είναι πιο εκφραστική από μια πρώτης τάξης λογική. Υπάρχει μια πεπερασμένη δεύτερης τάξης θεωρία της οποίας μοναδικό μοντέλο είναι οι πραγματικοί αριθμοί αν η υπόθεση του συνεχούς ισχύει και δεν έχει κανένα μοντέλο αν η υπόθεση του συνεχούς δεν ισχύει (cf. Shapiro 2000, p. 105). Αυτή η θεωρία αποτελείτε από μια πεπερασμένη θεωρία η οποία χαρακτηρίζει τους πραγματικούς αριθμούς ως πλήρες Αρχιμήδειο διατεταγμένο πεδίο και επίσης ένα αξίωμα που λέει ότι το πεδίο είναι πρώτης μη μετρήσιμης πληθικοτητας. Αυτό το παράδειγμα απεικονίζει ότι η ερώτηση question αν και εφόσον μια πρόταση δεύτερης τάξης λογική είναι συνεπής είναι πολύ λεπτή (subtle).

Επιπλέον περιορισμοί της δεύτερης τάξεως λογικής περιγραφονται σε επόμενο κομμάτι.

Μετά-λογικά αποτελέσματα[Επεξεργασία | επεξεργασία κώδικα]

Είναι πόρισμα του (θεωρήματος της μη-πληρότητας του Godel)Gödel's incompleteness theorem ότι δεν υπάρχει αφαιρετικό σύστημα (ότι , δεν υπάρχει έννοια αποδειξιμότητας) για δεύτερης τάξης formulas που να ικανοποιεί ταυτόχρονα τις τρεις παρακάτω συνθήκες :[4]

  • (Soundness)(σωστό) Κάθε αποδείξιμη δεύτερης τάξης πρόταση ισχύει καθολικά,δηλαδή, ισχύει για όλους τους τομείς στο πλαίσιο της σημασιολογίας.
  • (Completeness)(πλήρες)Κάθε καθολικά ισχύουσα δεύτερης τάξης formula, κάτω από καθορισμένη σημασιολογία, είναι αποδείξιμη .
  • (Effectiveness)(αποτελεσματικό) Υπάρχει αλγόριθμος που ελέγχει την αποδεικτική διαδικασία και μπορεί με επιτυχία να αποφασίσει αν μια δοθείσα ακολουθία από σύμβολα είναι μια δεκτή απόδειξη ή όχι.

Αυτό το πόρισμα κάποιες φορές εκφράζεται λέγοντας ότι η δεύτερης τάξης λογική δεν αποτελεί μια ολοκληρωμένη θεωρία αποδείξεων υπό αυτήν την άποψη η λογική δεύτερης τάξης με καθορισμένη σημασιολογία διαφέρει από την λογική πρώτης τάξης Quine (1970, pp. 90–91) λόγο της έλλειψης ενός πλήρους αποδεικτικού συστήματος και αυτός είναι λόγος να σκεφτόμαστε την λογική δεύτερης τάξης ως μη-(λογική) logic,μιλώντας κυριολεκτικά.

Όπως σημειώθηκε παραπάνω,ο Henkin απέδειξε ότι ένα κανονικό αφαιρετικό σύστημα για λογική πρώτης τάξης σωστό, πλήρες,και αποτελεσματικό για δεύτερης τάξης λογική με την σημασιολογία Henkin , και το αφαιρετικό σύστημα με αρχές κατανόησης και επιλογής είναι σωστό, πλήρες, και αποτελεσματικό για την σημασιολογία henkin χρησιμοποιώντας μοντέλα που ακολουθούν αυτές τις αρχές Το compactness theoremκαι το Löwenheim-Skolem theorem δεν αποτελούν πλήρη μοντέλα για δεύτερης τάξης λογική. Όμως αποτελούν μοντέλα Henkin. (Väänänen 2001)

Ιστορία και αμφησβιτούμενη αξία[Επεξεργασία | επεξεργασία κώδικα]

Κατηγορηματική λογική Κατηγορηματική λογική αρχικά εισήχθη στην μαθηματική κοινότητα από τον C. S. Peirce, ο οποίος επινόησε τον όρο δεύτερης τάξης λογική και του οποίου η σημειογραφία είναι παρεμφερής με την σημερινή (Putnam 1982). Παρ' όλα αυτά , στις μέρες μας οι περισσότεροι σπουδαστές λογικής είναι πιο εξοικειωμένοι με τα έργα του Frege, ο οποίος εξέδωσε το έργο του αρκετά χρονιά πριν από τον Peirce του οποίου όμως το έργο παρέμεινε στην αφάνεια μέχρι οι Bertrand Russell και Alfred North Whitehead να το κάνουν ξακουστό.Ο Frege χρησιμοποιησε διαφορετικές μεταβλητές για να διαφοροποιήσει τις ποσοτικοποησεις πάνω σε αντικείμενα από τις ποσοτικοποιησεις πάνω σε ιδιότητες και σύνολα, άλλα δεν έβλεπε τον ευατό του να κάνει δυο διαφορετικών ειδών λογικές . Μετά την ανακάλυψη του παραδόξου του Russel Russell's paradox έγινε κατανοητό ότι κάτι δεν πηγαίνει όπως θα έπρεπε με το υπάρχον σύστημα.Τελικά οι λογικολόγοι βρήκαν ότι περιορίζοντας την λογική του frege (Frege's logic) με διάφορους τρόπους κάτι το οποίο πλέον αποκαλείτε first-order logic—εξάλειψε αυτό το πρόβλημα : τα σύνολα και οι ιδιότητες δεν μπορούν να ποσοτικοποιηθουν σε πρώτης τάξης λογική μόνο. Η πλέον καθορισμένη now-standard ιεραρχία των τάξεων της λογικής χρονολογείτε από τότε.

Βρέθηκε ότι η (θεωρία σύνολων) set theory μπορούσε να τυποποιηθεί σαν ένα αξιωματικό σύστημα μέσα στο σύστημα της πρώτης τάξης λογικής στο κόστος των διαφόρων ειδών πληρότητας (completeness), άλλα σε καμιά περίπτωση κάτι τόσο σοβαρό όσο το παράδοξο του Russel Παράδοξο του Ράσελ ), και αυτό έγινε καθώς (βλέπε Zermelo-Fraenkel set theory), τα σύνολα είναι απαραίτητα για τα μαθηματικά mathematics. Arithmetic, mereology,και πολλές άλλες σημαντικές λογικές θεωρίες μπορούσαν να τυποποιηθούν αξιωματικά χωρίς προσφυγή σε άλλες λογικές κατασκευές εκτός από πρώτης τάξης ποσοτικοποιησεις , και αυτό , μαζί με την προσκόλληση των Gödel and Skolem's στην πρώτης τάξης λογική , τα παραπάνω οδήγησαν σε μια γενική απαξίωση για την εργασία πάνω σε δεύτερης (ή και υψηλότερων) τάξεων λογικές [εκκρεμεί παραπομπή]

Αυτή η άρνηση προωθήθηκε από κάποιους λογικολόγους, και πιο ειδικά από τον W. V. Quine. Ο Quine προώθησε την ιδέα [εκκρεμεί παραπομπή] ότι σε κατηγορηματικες γλώσσες , προτάσεις όπως οι παρακάτω Fx το "x" πρέπει να λογίζεται σαν μεταβλητή ή κάποιο όνομα που δηλώνει ένα αντικείμενο και ως εκ τούτου μπορεί να ποσοτικοποιηθει , όπως στο "For all things, it is the case that . . ." αλλά το "F" πρέπει να λογιστεί σαν συντομογραφια για μια ημιτελή πρόταση , και όχι το όνομα ενός αντικειμένου (ούτε καν ενός αφηρημένου αντικείμενου abstract object όπως η περιουσία) . Για παράδειγμα μπορεί να σημαίνει " . . . is a dog." Αλλά δεν βγάζει νόημα to να πιστεύεις ότι μπρούμε να ποσοτικοποιήσουμε κάτι σαν αυτό. (Μια τέτοια θέση είναι αρκετά συνεπής με τα επιχειρήματα του Frege στην διαφοροποιηση έννοια-αντικείμενο ). Έτσι για να χρησιμοποιησεις μια έννοια σαν μια μεταβλητή πρέπει να καταλαμβάνει την θέση ενός ονόματος που μόνο ατομικές μεταβλητές πρέπει να καταλαμβανουν .Αυτός ο συλλογισμός έχει απορριφθεί από τον Boolos.

Στα τελευταία χρόνια η δεύτερης τάξης λογική έχει ανακύψει , στηριζόμενη στην George Boolos' ερμηνεία των δεύτερης τάξης ποσοτικοποιήσεων plural quantification πάνω στο ίδιο πεδίο όπως και οι ποσοτικοποιήσεις πρώτης τάξης (Boolos 1984).Ο Boolos επιπρόσθετα επιδεικνύει τον ισχυρισμό της (μη-πρώτο ταξηκοποίησης) nonfirstorderizability προτάσεων όπως οι παρακάτω "Some critics admire only each other" (κάποιο κριτικοί θαυμάζουν μόνο ο ένας τον άλλον) και "Some of Fianchetto's men went into the warehouse unaccompanied by anyone else"(Κάποιοι άντρες του φιαντσέτο πήγαν στην αποθήκη χωρίς την συνοδεία κανενός) οι οποίες όπως υποστηρίζει ο boolos μπορούν να εκφραστούν μόνο μεσώ της δεύτερης τάξης ποσοτικοποίησης. Ωστόσο, (γενικές ποσοτικοποιησεις) generalized quantification και μερικώς διατεταγμενες , ή branching, ποσοτικοποιησεις μπορεί να αρκούν ώστε να εκφραστούν συγκεκριμενες κλάσεις από υποτιθέμενες μη-πρώτο ταξικοποιημενες προτάσεις και επίσης δεν ταιριάζει σε δεύτερης τάξης ποσοτικοποιησεις.

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

Κύριο λήμμα: SO (complexity)

Η εκφραστική δύναμη των διάφορων ειδών δεύτερης τάξης λογικών πάνω σε πεπερασμένες δομές είναι στενά δεμένες με την υπολογιστική θεωρία πολυπλοκότητας computational complexity theory. Ο τομέας της (περιγραφικής πολυπλοκότητας) descriptive complexity μελετά ποια κλάση υπολογιστικής πολυπλοκότητας complexity classes μπορεί να χαρακτηριστεί από την δύναμη της λογικής που χρειάζεται ώστε να εκφράσει κάποιες γλώσσες (σύνολα πεπερασμένων αλυσίδων ) . Η αλυσίδα

 w = w1···wn λέξη σε ενα πεπερασμένο αλφάβητο  A μπορεί να αναπαρασταθεί μέσω μιας πεπερασμένης δομής με πεδίο ορισμού το   D = {1,...,n}, μοναδιαία κατηγορήματα Pa για κάθε  aA η οποία ικανοποιείτε από αυτούς τους δείκτες i τέτοιοι ώστε wi = a,
 και επιπλέον κατηγορήματα που βοηθούν στο να προσδιοριστει μονοσήμαντα ποιοι δείκτες είναι ποιοι (τυπικά, κάποιος θα θεωρούσε the την αναδρομική συνάρτηση πάνω στο D ή την σχέση διάταξης  <, πιθανόν και με διαφορετικά αριθμητικά κατηγορήματα )
Εναλλακτικά ,ο πινάκας κάθε πεπερασμένης δομής μπορεί να  μπορεί να κωδικοποιηθεί  σε μια πεπερασμένη σειρά-αλυσίδα .

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

  • REG το σύνολο των κανονικών γλωσσών regular languages είναι ορισμένο από monadic, δεύτερης τάξης τύποι (Büchi's theorem, 1960)
  • NP είναι το σύνολο των γλωσσώνs ορισμένο από υπαρξιακούς ,δεύτερης τάξης τύπους (Fagin's theorem, 1974).
  • co-NP είναι το σύνολο των γλωσσών ορισμένες από γενικούς-καθολικούς , δεύτερης τάξης τύπους.
  • PH είναι το σύνολο των γλωσσών ορισμένο από δεύτερης τάξης τύπους.
  • PSPACE είναι το σύνολο των γλωσσών ορισμένο από δεύτερης τάξης τύπους μαζί με έναν μεταβατικό τερματικό τελεστή.
  • EXPTIME είναι το σύνολο των γλωσσών ορισμένο από δεύτερης τάξης τύπους μαζί με έναν ελάχιστου σταθερού σημείου τελεστή .

Οι σχέσεις μεταξύ αυτών των κλάσεων άμεσα επηρεάζουν την σχετική εκφραστικότητα των λογικών πάνω σε πεπερασμένες δομές, για παράδειγμα, Αν PH = PSPACE, έπειτα προσθέτοντας μεταβατικό τερματικό τελεστή σε μιας δεύτερης τάξης λογική δεν θα την έκανε πιο εκφραστική πάνω σε πεπερασμένες δομές.

-->

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

  1. Shapiro (1991) and Hinman (2005) give complete introductions to the subject, with full definitions.
  2. Such a system is used without comment by Hinman (2005).
  3. These are the models originally studied by Henkin (1950).
  4. The proof of this corollary is that a sound, complete, and effective deduction system for standard semantics could be used to produce a recursively enumerable completion of Peano arithmetic, which Gödel's theorem shows cannot exist.

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