Θεωρία τύπων

Στα Μαθηματικά, στη Λογική και στη Επιστήμη των Υπολογιστών, η Θεωρία Τύπων είναι ένα από τα τυπικά συστήματα τα οποία χρησιμοποιούνται στην Απλοϊκή Θεωρία Συνόλων, ή στη μελέτη τέτοιων φορμαλισμών γενικότερα.  Στη Θεωρία των Γλωσσών Προγραμματισμού, ενός κλάδου της Επιστήμης των Υπολογιστών, η Θεωρία Τύπων μπορεί να αναφέρεται στο σχεδιασμό, στην ανάλυση και στη μελέτη των Συστημάτων Τύπων, παρόλο που κάποιοι επιστήμονες της Πληροφορικής περιορίζουν τη σημασία του όρου στη μελέτη των αφηρημένων φορμαλισμών όπως ο λ-λογισμός με τύπους.
Ο Μπέρτραντ Ράσελ εφηύρε την πρώτη θεωρία τύπων μετά την ανακάλυψή του πως η εκδοχή της Απλοϊκής Θεωρίας Συνόλων του Γκότλομπ Φρέγκε υπόκειντο στο Παράδοξο του Ράσελ.  Αυτή η θεωρία τύπων βρίσκεται σε περίοπτη θέση στο Principia Mathematica των Άλφρεντ Νορθ Γουάιτχεντ και Ράσελ. Αποφεύγει το Παράδοξο του Ράσελ με το να δημιουργεί πρώτα μία ιεραρχία τύπων, και κατόπιν να αναθέτει κάθε μαθηματική (και πιθανώς άλλη) οντότητα σε έναν τύπο. Τα αντικείμενα ενός δοσμένου τύπου δημιουργούνται αποκλειστικά από αντικείμενα προηγούμενων τύπων (αυτών που είναι χαμηλότερα στην ιεραρχία), αποφεύγοντας έτσι τις επαναλήψεις.
Ο Αλόνσο Τσερτς, εφευρέτης του λ-λογισμού, ανέπτυξε μια Λογική Υψηλής Τάξης γνωστότερη ως Θεωρία Τύπων του Church, με σκοπό να αποφύγει το Παράδοξο Kleene–Rosser που ταλαιπωρούσε τον αρχικό αμιγή λ-λογισμό.  Η θεωρία τύπων του Church είναι μια παραλλαγή του λ-λογισμού στην οποία οι εκφράσεις (που επίσης καλούνται φόρμουλες ή λ-όροι) κατηγοριοποιούνται σε τύπους, και οι τύποι των εκφράσεων περιορίζουν τους τρόπους με τους οποίους μπορούν να συνδυαστούν. Με άλλα λόγια, είναι ένας λ-λογισμός με τύπους.
Το άρθρο Η Θεωρία Τύπων του Church
στην Εγκυκλοπαίδεια την Φιλοσοφίας του Stanford
είναι αφιερωμένο σε αυτό το θέμα.
Σήμερα χρησιμοποιούνται πολλοί άλλοι παρόμοιοι λογισμοί, συμπεριλαμβανομένης της Ιντουισιονιστικής θεωρίας τύπων του Περ Μάρτιν-Λέφ , του Συστήματος F του Ζαν-Ιβ Ζιράρ και του Λογισμoύ των κατασκευών.  Στον λ-λογισμό με τύπους, οι τύποι παίζουν ένα ρόλο παρόμοιο με αυτό των συνόλων στη Θεωρία Συνόλων.

1900 - 1927

Η Προέλευση της Θεωρίας Τύπων του Ράσελ: Σε ένα γράμμα του προς τον Γκότλομπ Φρέγκε (1902) ο Ράσελ ανακοίνωσε την ανακάλυψη του παραδόξου στο Begriffsschrift του Frege. Ο Frege απάντησε τάχιστα, αναγνωρίζοντας το πρόβλημα και προτείνοντας μια λύση σε μια τεχνική συζήτηση επιπέδων (levels). Παραθέτοντας τον Frege:
Παρεμπιπτόντως, μου φαίνεται ότι η έκφραση «ένα κατηγόρημα δηλώνει τον εαυτό του» δεν είναι ακριβής. Ένα κατηγόρημα είναι κατά κανόνα μια συνάρτηση πρώτου επιπέδου, και αυτή η συνάρτηση χρειάζεται ένα αντικείμενο ως παράμετρο και δεν μπορεί να έχει τον εαυτό της ως παράμετρο (subject). Συνεπώς, θα προτιμούσα να πω «μια έννοια δηλώνεται από την έκτασή της».
Συνεχίζει δείχνοντας πως θα μπορούσε αυτό να δουλέψει αλλά φαίνεται πως τελικά κάνει πίσω. (Σε μια υποσημείωση, ο van Heijenoort σημειώνει πως στο Frege 1893 ο Frege είχε χρησιμοποιήσει ένα σύμβολο (horseshoe) «για την αναγωγή συναρτήσεων δεύτερου επιπέδου σε συναρτήσεις πρώτου επιπέδου»). Ως συνέπεια αυτού που έχει γίνει γνωστό ως το Παράδοξο του Ράσελ τόσο ο Frege όσο και ο Ράσελ έπρεπε να διορθώσουν γρήγορα τα έργα τους που είχαν προς εκτύπωση. Στο Παράρτημα Β που ο Ράσελ πρόσθεσε στο βιβλίο του Principles of Mathematics του 1903,  μπορεί κανείς να βρει την «διστακτική» του «θεωρία τύπων».
Το θέμα στοίχειωνε τον Ράσελ για περίπου πέντε χρόνια (1903–1908). Ο Γουίλαρντ Κιν στον πρόλογό του για το Η Μαθηματική λογική βασισμένη στην θεωρία των τύπων (1908) του Ράσελ παρουσιάζει μια ιστορική σύνοψη για την προέλευση της θεωρίας των τύπων και της «διακλαδιζόμενης» θεωρίας των τύπων. Ο Ράσελ πρότεινε με σειρά του κάποιες εναλλακτικές: (i) εγκαταλείποντας την θεωρία των τύπων (1905) και προτείνοντας  τρεις θεωρίες το 1905: (ii.1) την θεωρία ζιγκ ζαγκ (zigzag theory), (ii.2) την θεωρία του περιορισμού του μεγέθους (theory of limitation of size), (ii.3) την θεωρία χωρίς κλάσεις (no-class theory) (1905–1906), και κατόπιν (iii) επανέφερε την θεωρία των τύπων (1908).
Ο Quine παρατηρεί ότι η εισαγωγή της έννοιας της «προφανούς μεταβλητής» από τον Ράσελ είχε το ακόλουθο αποτέλεσμα: «η διάκριση μεταξύ του 'όλα' ('all') και του 'κάποιο' ('any'): Το 'όλα' εκφράζεται από την δεσμευμένη ('προφανή') μεταβλητή της καθολικής ποσοτικοποίησης, που εκτείνεται πάνω σε έναν τύπο, και το 'κάποιο' εκφράζεται από την ελεύθερη ('πραγματική') μεταβλητή που αναφέρεται σχηματικά σε οτιδήποτε ανεξαρτήτως τύπου». Ο Quine απορρίπτει αυτή την ιδέα της «δεσμευμένης μεταβλητής» ως «άσκοπη εκτός μια συγκεκριμένη πτυχή της θεωρίας των τύπων».

Η «διακλαδιζόμενη» θεωρία τύπων του 1908

Ο Quine εξηγεί την διακλαδιζόμενη θεωρία ως εξής: «Ονομάζεται έτσι επειδή ο τύπος μιας συνάρτησης εξαρτάται τόσο από τους τύπους των παραμέτρων της όσο και από τους τύπους των προφανών μεταβλητών που περιέχονται σε αυτήν (ή στην έκφρασή της), σε περίπτωση που αυτές υπερβαίνουν τους τύπους των παραμέτρων». Ο Στίβεν Κλέινι στο βιβλίο του Εισαγωγή στα Μετα-Μαθηματικά του 1952 περιγράφει την διακλαδιζόμενη θεωρία τύπων ως εξής:
Τα πρωτογενή αντικείμενα ή άτομα (δηλ. τα δοσμένα αντικείμενα που δεν υποβάλλονται σε λογική ανάλυση) αποδίδονται σε έναν τύπο (π.χ. τύπο 0), οι ιδιότητες των ατόμων στον τύπο 1, οι ιδιότητες των ιδιοτήτων των ατόμων στον τύπο 2, κλπ. Και δεν αναγνωρίζονται ιδιότητες που δεν εμπίπτουν σε έναν από αυτούς τους λογικούς τύπους (π.χ. αυτό βάζει τις ιδιότητες 'προβλέψιμο' και 'μη προβλέψιμο' ... εκτός του πεδίου της λογικής). Μία πιο λεπτομερής έκθεση θα περιέγραφε τους αποδεκτούς τύπους για άλλα αντικείμενα ως σχέσεις και κλάσεις. Στη συνέχεια για να αποκλείσει μη κατηγορηματικές δηλώσεις μέσα σε έναν τύπο, οι τύποι πάνω από τον τύπο 0 διαχωρίζονται περαιτέρω σε τάξεις. Συνεπώς για τον τύπο 1, οι ιδιότητες που ορίζονται χωρίς την αναφορά πληρότητας ανήκουν στον τύπο 0 και ιδιότητες που ορίζονται χρησιμοποιώντας όλες τις ιδιότητες μιας τάξης  ανήκουν στην επόμενη μεγαλύτερη τάξη. Αλλά αυτός ο διαχωρισμός σε τάξεις κάνει αδύνατη την οικεία ανάλυση, η οποία όπως είδαμε περιέχει μη κατηγορηματικούς ορισμούς. Για να αποφύγουμε το παραπάνω αποτέλεσμα ο Ράσελ εισήγαγε το αξίωμα της αναγωγής το οποίο λέει ότι για κάθε ιδιότητα που ανήκει σε τάξη μεγαλύτερη της μηδενικής υπάρχει μια συνεκτατική (coextensive) ιδιότητα (που ανήκει στα ίδια αντικείμενα) τάξης 0. Αν υποθέσουμε ότι υπάρχουν μόνο ιδιότητες που μπορούν να οριστούν, τότε το αξίωμα ουσιαστικά λέει ότι για κάθε μη κατηγορηματικό ορισμό μέσα σε ένα τύπο υπάρχει ένας ισοδύναμος κατηγορηματικός (Kleene 1952:44-45)

Το αξίωμα της αναγωγής και η ιδέα της «μήτρας»

Αλλά επειδή οι παραδοχές της διακλαδιζόμενης θεωρίας θα αποδεικνύονταν (παραθέτοντας τον Quine) «επαχθείς», ο Ράσελ το 1908 στο έργο του Η Μαθηματική λογική βασισμένη στην θεωρία των τύπων θα πρότεινε επίσης το αξίωμα της αναγωγής. Ως το 1910, οι Whitehead και ο Ράσελ στο έργο τους Principia Mathematica θα επαύξαναν περαιτέρω αυτό το αξίωμα με την ιδέα μιας μήτρας, η οποία ήταν μια πλήρως επεκτάσιμη προδιαγραφή μιας συνάρτησης. Από την μήτρα της μια συνάρτηση θα μπορούσε να παραχθεί μέσω της διαδικασίας της «γενίκευσης» και αντίστροφα, δηλ. οι δύο διεργασίες είναι αντιστρέψιμες -- (i) γενίκευση από μήτρα σε συνάρτηση (με χρήση προφανών μεταβλητών)  και (ii) η αντίστροφη διαδικασία της αναγωγής τύπου με κλάσεις-τιμών αντικατάσταση των ορισμάτων για την προφανή μεταβλητή. Με αυτή τη μέθοδο αποφεύγουμε το να είμαστε μη κατηγορηματικοί.

Οι αμφιβολίες του Ράσελ

Ο Ράσελ στην Εισαγωγή στη Μαθηματική Φιλοσοφία(1920) αφιερώνει ένα κεφάλαιο στο «Αξίωμα του Απείρου και των λογικών τύπων» στο οποίο λέει τα εξής:
Πλέον η θεωρία τύπων δεν ανήκει στο τελειωμένο και βέβαιο κομμάτι της δουλειάς μας: μεγάλο μέρος της θεωρίας είναι ακόμη ελλιπές, μπερδεμένο και θολό. Αλλά η ανάγκη για κάποια αρχή των τύπων είναι λιγότερο αμφισβητήσιμη από την ακριβή μορφή που θα πάρει αυτή η αρχή. Και σε σύνδεση με το αξίωμα του απείρου είναι ιδιαίτερα εύκολο να δούμε την αναγκαιότητα μια τέτοιας αρχής.
Ο Ράσελ εγκαταλείπει το αξίωμα της αναγωγής: Στη δεύτερη έκδοση του Principia Mathematica (1927) αναγνωρίζει το επιχείρημα του Βιτγκενστάιν. Στην αρχή της εισαγωγής παραδέχεται: «δεν υπάρχει αμφιβολία... ότι δε χρειάζεται η διαφοροποίηση των εννοιών πραγματική και προφανής μεταβλητή». Οικειοποιείται την έννοια της μήτρας και δηλώνει «Μια συνάρτηση μπορεί να εμφανιστεί σε μια μήτρα μόνο μέσω των τιμών της» (αλλά συμπληρώνει σε μια υποσημείωση: «Αντικαθιστά (όχι αρκετά ικανοποιητικά) το αξίωμα της αναγωγής.») Επιπλέον εισάγει τη νέα (συντομευμένη, γενική) έννοια της «μήτρας», αυτή της «λογικής μήτρας .. που δεν περιέχει σταθερές. Επομένως το p|q είναι μια λογική μήτρα». Βλέπουμε ότι ο Ράσελ εγκατέλειψε την ιδέα του αξιώματος της αναγωγής αλλά στις τελευταίες παραγράφους δηλώνει ότι «από τις παρούσες πρωταρχικές έννοιες» δεν μπορεί να παράγει «σχέσεις του Dedekind και σχέσεις καλώς διατεταγμένες» και παρατηρεί ότι αν υπάρχει κάποιο καινούριο αξίωμα να αντικαταστήσει το αξίωμα της αναγωγής «μένει να ανακαλυφθεί».

Θεωρία των απλών τύπων

Στη δεκαετία του 20 οι Λέον Τσβίστεκ και Φρανκ Π. Ράμσεϊ παρατήρησαν ότι αν κάποιος θέλει να εγκαταλείψει την αρχή του φαύλου κύκλου, η ιεραρχία των επιπέδων των τύπων στην «διακλαδιζόμενη θεωρία των τύπων» (δείτε το ιστορικό σημείωμα πριν) μπορεί να καταρρεύσει.
Η προϊούσα περιορισμένη λογική ονομάζεται θεωρία των απλών τύπων ή πιο  απλά θεωρία των τύπων. Λεπτομερείς εκθέσεις της απλής θεωρίας των τύπων εκδόθηκαν στα τέλη του 1920 και στις αρχές του 30 από τους R. Carnap, F. Ramsey, W.V.O. Quine, and A. Tarski. Το 1940 ο Αλόνσο Τσέρτς την επανασχεδίασε ως λ-λογισμό με απλούς τύπους. και εξετάστηκε και από τον Γκέντελ το 1944.

Γκέντελ 1944

Ο Κουρτ Γκέντελ στην Μαθηματική Λογική του Ράσελ του το 1944 έδωσε σε μια υποσημείωση τον ακόλουθο ορισμό της «θεωρίας των απλών τύπων»:
Ως θεωρία των απλών τύπων εννοώ το δόγμα που λέει ότι τα αντικείμενα της σκέψης (ή, κατά μια άλλη ερμηνεία, οι συμβολικές εκφράσεις) είναι διαχωρισμένα σε τύπους, ήτοι: άτομα, ιδιότητες ατόμων, σχέσεις μεταξύ ατόμων, ιδιότητες τέτοιων σχέσεων, κλπ. (με μια παρόμοια ιεραρχία για επεκτάσεις), και ότι οι προτάσεις της μορφής: «Το a έχει τη ιδιότητα φ», «το b έχει τη σχέση R με το c», κλπ. είναι δίχως νόημα, αν τα a, b, c, R, φ δεν είναι τύποι συμβατοί μεταξύ τους. Εξαιρούνται οι μικτοί τύποι (όπως οι κλάσεις που περιέχουν άτομα και κλάσεις ως στοιχεία) και συνεπώς και οι υπερπεπερασμένοι τύποι (όπως η κλάση όλων των κλάσεων από πεπερασμένους τύπους). Το ότι αυτή η θεωρία των απλών τύπων αρκεί για την αποφυγή επίσης των επιστημονικών παραδόξων φαίνεται μετά από μια ενδελεχέστερη ανάλυση αυτών (Cf. Ramsey 1926 και Tarski 1935, σελ. 399).
Κατέληξε ότι η Θεωρία των Απλών Τύπων και η Αξιωματική Θεωρία Συνόλων, «επιτρέπουν την παραγωγή των σύγχρονων μαθηματικών και ταυτόχρονα αποφεύγουν όλα τα γνωστά παράδοξα» (Γκέντελ 1944:126). Επιπροσθέτως, η θεωρία των απλών τύπων «είναι το σύστημα του ''Principia Mathematica'' σε μια κατάλληλη ερμηνεία... Ωστόσο, πολλά από τα συμπτώματα δείχνουν ξεκάθαρα ότι οι βασικές έννοιες χρειάζονται περαιτέρω διευκρίνιση» (Γκέντελ 1944:126).

Φόρμουλες βασισμένες στην ισότητα

Η θεωρία τύπων του Church έχει μελετηθεί εκτενώς από δύο μαθητές του, τον Λέον Χένκιν και τον Πίτερ Μπρους Άντριους. Καθώς η ST είναι μια λογική υψηλής τάξης, και στις λογικές υψηλής τάξης μπορεί κανείς να ορίσει προτασιακούς συνδέσμους από την άποψη της λογικής ισοδυναμίας και των ποσοδεικτών, το 1963 ο Ηenkin ανέπτυξε μια μορφοποίηση της ST βασισμένη στην ισότητα, αλλά στην οποία περιόρισε την προσοχή του στους κατηγορηματικούς τύπους. Το παραπάνω απλοποιήθηκε αργότερα τον ίδιο χρόνο από τον Άντριους στη θεωρία Q₀. Κάτω από αυτό το πρίσμα η ST μπορεί να θεωρηθεί ως ένα είδος λογικής υψηλής τάξης, η οποία χαρακτηρίστηκε από τον Π.Τ. Τζόνστον στο Sketches of an Elephant ότι έχει μια λάμδα-υπογραφή η οποία είναι μια υψηλής-τάξης υπογραφή που δεν περιέχει σχέσεις και χρησιμοποιεί μόνο γινόμενα και βέλη (τύποι συναρτήσεων) ως κατασκευαστές τύπων. Επιπλέον, όπως το έθεσε ο Τζόντστον η ST είναι «χωρίς λογική» με την έννοια ότι δεν περιέχει λογικές συνδέσεις ή ποσοδείκετες στον ορισμό της.

Κοινωνικές επιστήμες

Ο Gregory Bateson εισήγαγε μια θεωρία λογικών τύπων στις κοινωνικές επιστήμες; οι ιδέες του της διπλής δέσμευσης και των λογικών επιπέδων βασίζονται στη θεωρία τύπων του Ράσελ.