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

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

Σημασιολογία

Η σημασιολογία της λογικής δεύτερης τάξης καθορίζει την σημασία κάθε πρότασης. Αντίθετα με την λογική πρώτης τάξης, η οποία έχει μοναδική σημασιολογία, υπάρχουν δυο ειδών σημασιολογίες που χρησιμοποιούνται συνήθως για τη λογική δεύτερης τάξης: κανονική (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" ως ένα αξίωμα για τα μαθηματικά.

Επαγωγικά Συστήματα

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

Ιστορία και αμφησβιτούμενη αξία

Κατηγορηματική λογική Κατηγορηματική λογική αρχικά εισήχθη στην μαθηματική κοινότητα από τον 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, ποσοτικοποιησεις μπορεί να αρκούν ώστε να εκφραστούν συγκεκριμενες κλάσεις  από υποτιθέμενες  μη-πρώτο ταξικοποιημενες προτάσεις  και επίσης  δεν  ταιριάζει σε δεύτερης τάξης ποσοτικοποιησεις.