Αρίθμηση Γκέντελ
Στη θεωρία των τυπικών αριθμών, η αρίθμηση Gödel είναι μια συνάρτηση που αποδίδει σε κάθε σύμβολο και τύπο κάποιας τυπικής γλώσσας έναν μοναδικό φυσικό αριθμό που ονομάζεται αριθμός Gödel (GN). Η έννοια χρησιμοποιήθηκε για πρώτη φορά από τον Kurt Gödel για την απόδειξη του θεωρήματος της μη πληρότητας.
Μια αρίθμηση Gödel μπορεί να ερμηνευθεί ως μια κωδικοποίηση όπου ένας αριθμός αποδίδεται σε κάθε σύμβολο μιας μαθηματικής σημειογραφίας και μια ροή φυσικών αριθμών μπορεί στη συνέχεια να αναπαραστήσει κάποια μορφή ή συνάρτηση. Μια αρίθμηση του συνόλου των υπολογίσιμων συναρτήσεων μπορεί στη συνέχεια να αναπαρασταθεί από μια ροή αριθμών Gödel (που ονομάζονται επίσης αποτελεσματικοί αριθμοί). Το θεώρημα ισοδυναμίας του Rogers δηλώνει κριτήρια για το ποια από αυτές τις αριθμήσεις του συνόλου των υπολογίσιμων συναρτήσεων είναι αριθμήσεις Gödel.
Ορισμός
Δεδομένου ενός μετρήσιμου συνόλου S, μια αρίθμηση Gödel είναι μια εγχυτική συνάρτηση
f : S → N {\displaystyle f:S\to \mathbb {N} } 
με f και f - 1{\displaystyle f^{-1}} 
(το αντίστροφο της f) είναι υπολογίσιμες συναρτήσεις.
Παραδείγματα
Βασική σημειογραφία και συμβολοσειρές
Ένα από τα απλούστερα συστήματα αρίθμησης Gödel χρησιμοποιείται καθημερινά: Η αντιστοιχία μεταξύ των ακεραίων αριθμών και των αναπαραστάσεών τους ως σειρές συμβόλων. Για παράδειγμα, η ακολουθία 2 3 κατανοείται, με ένα συγκεκριμένο σύνολο κανόνων, ότι αντιστοιχεί στον αριθμό είκοσι τρία. Ομοίως, συμβολοσειρές συμβόλων από κάποιο αλφάβητο Ν συμβόλων μπορούν να κωδικοποιηθούν ταυτίζοντας κάθε σύμβολο με έναν αριθμό από το 0 έως το Ν και διαβάζοντας τη συμβολοσειρά ως την αναπαράσταση ενός ακέραιου αριθμού στη βάση Ν+1.
Ερωτήσεις και απαντήσεις
Ερ: Τι είναι η αρίθμηση Γκέντελ;
A: Η αρίθμηση Γκέντελ είναι μια συνάρτηση που αποδίδει έναν μοναδικό φυσικό αριθμό σε κάθε σύμβολο και τύπο μιας τυπικής γλώσσας, ο οποίος ονομάζεται αριθμός Γκέντελ (GN).
Ερ: Ποιος χρησιμοποίησε πρώτος την έννοια της αρίθμησης Γκέντελ;
Α: Ο Kurt Gödel χρησιμοποίησε για πρώτη φορά την έννοια της αρίθμησης Gödel για την απόδειξη του θεωρήματος της μη πληρότητας.
Ερ: Πώς μπορούμε να ερμηνεύσουμε την αρίθμηση Gödel;
Α: Μπορούμε να ερμηνεύσουμε την αρίθμηση Gödel ως μια κωδικοποίηση όπου σε κάθε σύμβολο μιας μαθηματικής σημειογραφίας αποδίδεται ένας αριθμός και μια ροή φυσικών αριθμών μπορεί να αναπαριστά κάποια μορφή ή συνάρτηση.
Ερ: Πώς ονομάζουμε τους φυσικούς αριθμούς που αποδίδονται από μια αρίθμηση Gödel;
Α: Οι φυσικοί αριθμοί που αποδίδονται από μια αρίθμηση Gödel ονομάζονται αριθμοί Gödel ή αποτελεσματικοί αριθμοί.
Ερ: Τι δηλώνει το θεώρημα ισοδυναμίας του Rogers;
Α: Το θεώρημα ισοδυναμίας του Rogers δηλώνει κριτήρια για τα οποία οι αριθμήσεις του συνόλου των υπολογίσιμων συναρτήσεων είναι αριθμήσεις Gödel.
Ερ: Τι αναπαριστά μια ροή αριθμών Gödel;
Α: Μια αρίθμηση του συνόλου των υπολογίσιμων συναρτήσεων μπορεί να αναπαρασταθεί από μια ροή αριθμών Gödel.
Ερ: Γιατί η αρίθμηση Gödel είναι σημαντική στην τυπική θεωρία αριθμών;
Α: Η αρίθμηση Gödel είναι σημαντική στην τυπική θεωρία αριθμών καθώς παρέχει έναν τρόπο αναπαράστασης μαθηματικών τύπων και συναρτήσεων ως φυσικών αριθμών, γεγονός που επιτρέπει την απόδειξη σημαντικών θεωρημάτων όπως το θεώρημα της μη πληρότητας.
