Skip to content

Instantly share code, notes, and snippets.

@Hepic Hepic/godel.md
Last active Jul 7, 2018

Embed
What would you like to do?
Antony's conjecture

Ορισμος 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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.