Λογική ανώτερου βαθμού

Στα μαθηματικά και τη λογική, μία λογική ανώτερου βαθμού ή λογική ανώτερης τάξης (higher-order logic) διακρίνεται από μία λογική πρώτου βαθμού με βάση αρκετά χαρακτηριστικά. Ένα από αυτά είναι ο τύπος των μεταβλητών που εμφανίζονται στους ποσοδείκτες: γενικά, στην πρωτοβάθμια λογική, απαγορεύεται οι ποσοδείκτες να αναφέρονται σε κατηγορήματα, ενώ αυτό επιτρέπεται στη λογική δεύτερου βαθμού. Η λογική ανώτερου βαθμού διαφέρει επίσης από τη λογική πρώτου βαθμού στις δομές που η θεωρία τύπων της επιτρέπει να κατασκευάζονται. Ένα κατηγόρημα ανώτερου βαθμού είναι ένα κατηγόρημα που δέχεται σαν παραμέτρους κατηγορήματα. Γενικά, ένα κατηγόρημα βαθμού n παίρνει ένα ή περισσότερα κατηγορήματα βαθμού n − 1 σαν παραμέτρους, όπου n > 1. Παρόμοια ισχύουν και για τις συναρτήσεις ανώτερης τάξης.

Ο όρος λογική ανώτερης τάξης (Higher-order logic, συντομογραφία HOL), συχνά χρησιμοποιείται για απλές λογικές κατηγορημάτων ανώτερου βαθμού, δηλαδή λογικές των οποίων η θεωρία τύπων είναι απλή, όχι πολυμορφική ή με εξαρτώμενους τύπους.^[1]

Οι λογικές ανώτερου βαθμού είναι πιο εκφραστικές, αλλά οι ιδιότητές τους, ειδικά όσον αφορά τη θεωρία μοντέλων, τις κάνουν δυσκολότερες στο χειρισμό για πολλές εφαρμογές. Λόγω ενός αποτελέσματος του Γκέντελ, η κλασική λογική ανώτερου βαθμού δεν επιδέχεται ενός (αναδρομικού και αξιωματικού) λογισμού αποδείξεων που να είναι συνεπής (sound) και πλήρης (complete) - ένας τέτοιος λογισμός όμως υπάρχει και είναι συνεπής και πλήρης όσον αφορά τα μοντέλα Χένκιν (Henkin models).

Παραδείγματα λογικών ανώτερου βαθμού είναι ο λ-λογισμός με απλούς τύπους του Τσερτς (Απλή Θεωρία των Τύπων), ο λογισμός των κατασκευών (calculus of constructions) του Κοκάν, που επιτρέπει εξαρτώμενους και πολυμορφικούς τύπους, και φυσικά η HOL.

Δείτε επίσης

• λ-λογισμός με τύπους
• Λογική με πολλούς τύπους (Many-sorted logic)

Παραπομπές

1. Jacobs, 1999, κεφάλαιο 5

Αναφορές

• Andrews, Peter B. (2002). An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof, 2nd ed, Kluwer Academic Publishers, ISBN 1402007639
• Stewart Shapiro, 1991, "Foundations Without Foundationalism: A Case for Second-Order Logic". Oxford University Press., ISBN 0198250290
• Stewart Shapiro, 2001, "Classical Logic II: Higher Order Logic," in Lou Goble, ed., The Blackwell Guide to Philosophical Logic. Blackwell, ISBN 0631206930
• Lambek, J. and Scott, P. J., 1986. Introduction to Higher Order Categorical Logic, Cambridge University Press, ISBN 0521356539
• Jacobs, Bart (1999). Categorical Logic and Type Theory. Studies in Logic and the Foundations of Mathematics 141. North Holland, Elsevier. ISBN 0-444-50170-3.

Εξωτερικοί σύνδεσμοι

• Miller, Dale, 1991, "Logic: Higher-order," Encyclopedia of Artificial Intelligence, 2nd ed.
• Herbert B. Enderton, Second-order and Higher-order Logic in Stanford Encyclopedia of Philosophy.