Ορισμος godel αριθμών: Ένας godel αριθμός μιας συμβολοσειράς είναι μια αντιστοιχηση κάθε χαρακτηρα σε ενα μοναδικο φυσικο αριθμο.
Εικασία: Το σύνολο που περιέχει του godel αριθμούς είναι μη αριθμήσιμα άπειρο.
Αποδειξη: Έστω S = {x | δυαδικός με άπειρο μέγεθος} Το συνολο αυτο ειναι μη αριθμησιμο. (1) Για κάθε στοιχείο του S παίρνουμε εναν καινουργιο αριθμό godel (2). Έστω G το σύνολο των godel αριθμων.
Από (1), (2) έχουμε οτι G >= S.
Αποδειξη για το (2): Έστω x ο δυαδικός που ανήκει στο S και g ένας πίνακας απείρου μεγέθους. Σαρώνουμε τον x απο την αρχή. Αν στην ith θέση ο x έχει την τιμή 0, πάμε απλώς στην i+1 θέση. Αν στην ith θέση ο x έχει την τιμή 1, προσθέτουμε στο τέλος του g το i και πάμε στην i+1 θέση. Ο πίνακας g είναι ένας godel αριθμός αν ανάμεσα στα στοιχεία του βάλουμε τον χαρακτήρα '-'. Πχ για g = [2, 5, 16], ο godel αριθμός ειναι ο 2-5-16.
Οπότε αν x1 != x2, τοτε υπαρχει μια θέση i στην οποια χ.β.τ.γ x1(i) = 0 και x2(i) = 1. Άρα ο g1 έχει έναν αριθμό που δεν έχει ο g2.