forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 20 Σεπ 2017, 07:46

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 10 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Προτάσεις Godel
ΔημοσίευσηΔημοσιεύτηκε: 19 Ιαν 2007, 19:56 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφή: 01 Δεκ 2006, 00:05
Δημοσ.: 2268
Συγχωρέστε με αν κανω τραγικα λαθη αλλα δεν το γνωριζω καλα το αντικειμενο.
Εστω οτι εχουμε μια θεωρια για την οποια ισχυει το θεωρημα της μη-πληροτητας, δηλαδη υπαρχει προταση Ρ (προταση Godel νομιζω λεγεται) η οποια ειναι αληθης αλλα δεν αποδεικνυεται(μεσα στα πλαισια του συγκεκριμενου αξιωματικου συστηματος). Θα θελαμε προφανως να υπηρχε ενας αλγοριθμος που να αποφαινοταν αν μια προταση ειναι προταση Godel ή οχι. Ακομα θα θελαμε κι εναν αλγοριθμο που να μας δινει, δεδομενου ενος αξιωμ.συστηματος, τις αναποδεικτες αυτες προτασεις. Απ'οσο ξερω δεν υπαρχουν τετοιοι αλγοριθμοι. Το ερωτημα μου ειναι: εχει αποδειχθει πως δεν κατασκευαζονται τετοιοι αλγοριθμοι ή απλα δεν εχουμε βρει καποιον ακομα;


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Προτάσεις Godel
ΔημοσίευσηΔημοσιεύτηκε: 19 Ιαν 2007, 20:09 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφή: 02 Ιούλ 2006, 21:08
Δημοσ.: 2095
Τοποθεσια: Βριλησσια
πιο απλα ρωτας αν μπορουμε να ειμαστε, με καποιο τροπο, σίγουροι περα απο καθε αμφιβολία οτι μια πρόταση ενός αξιωματικού συστήματος ειναι αναπόδεικτη?
Αν είναι αυτό νομίζω οτι ο αγαπητός Kurt απέδειξε ότι δυστυχώς δεν γίνεται. :cry: :cry: αλλα δεν ειμαι απόλυτα σίγουρος


zozef έγραψε:
Συγχωρέστε με αν κανω τραγικα λαθη αλλα δεν το γνωριζω καλα το αντικειμενο.
Εστω οτι εχουμε μια θεωρια για την οποια ισχυει το θεωρημα της μη-πληροτητας,

Για την ακρίβεια νομίζω οτι η σωστη εκφραση ειναι "εχουμε ενα αξιωματικό σύστημα" (πανω σε αυτα στιριζονται οι θεωριες).Και νομιζω οτι ο Godel απεδειξε οτι αυτο ισχυει για ολα τα λογικα αξιωματικα συστηματα(αλλα και παλι δεν κωβο το κεφαλι μου
:P )

_________________
Τι εννοείτε ακριβώς?
Those who can, do. Those who can't, teach...
Εικόνα


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 20 Ιαν 2007, 00:33 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφή: 01 Μαρ 2006, 21:16
Δημοσ.: 459
Τοποθεσια: Νέος Κόσμος
Μερικές σκέψεις σε αυτό που ρωτάς:

Ένας αλγόριθμος που θα εξέταζε αν μια οποιαδήποτε πρόταση είναι αποδείξιμη σε ένα ΑΣ, θα έπρεπε να ελέγξει όλες τις δυνατές αποδείξεις που μπορεί να προέλθουν από αυτό, ώστε κάποια στιγμή να βρεί την πρόταση που θέλουμε. Όμως αυτή η διαδικασία δεν είναι αλγόριθμος γιατί δεν τερματίζει, πχ όταν η πρόταση δεν είναι αποδείξιμη.

Για να απαντήσει ένας αλγ. αν μια πρόταση δεν αποδεικνύεται στο ΑΣ, θα πρέπει να ελέγξει όλες τις δυνατές αποδείξεις στο σύστημα, το οποίο δεν τερματίζει ποτέ.

Επίσης, αν υπήρχε τέτοιος αλγόριθμος, τότε αυτό θα αποτελούσε απόδειξη ότι η πρόταση είναι αληθής, και θα είχαμε μια απόδειξη για αυτήν μέσα στο ΑΣ: τον ίδιο τον αλγόριθμο που αποφάνθηκε για αυτή, άτοπο.

Αυτά βέβαια είναι δικές μου απλοϊκές σκέψεις, αλλά νομίζω είναι αποδεδειγμένο ότι δεν υπάρχει τέτοιος αλγόριθμος.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 20 Ιαν 2007, 17:14 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφή: 01 Δεκ 2006, 00:05
Δημοσ.: 2268
Εχεις δικιο, δεν το ειχα σκεφτει, αν αποδεικνυαμε οτι μια προταση ειναι μη-αποδειξιμη ταυτοχρονα δειχναμε οτι ειναι αληθης(για τις μη-αληθεις προτασεις βρισκεται παντα αποδειξη οτι δεν ισχυουν, σωστα?), ατοπο. Angelo λες πως για να ελεγχθει μια προταση θα επρεπε να ελεγχθουν ολες οι αποδειξεις στο συστημα αυτο, και πως ο αλγοριθμος δεν θα τερματιζε ποτε. Η αληθεια ειναι πως δεν ειμαι πεπεισμενος πως αυτος ειναι ο μοναδικος τροπος, αλλα απ'την αλλη δεν γνωριζω και καποιον εναλλακτικο.. Ακομα, ειμαστε σιγουροι πως δεν θα τερματιζε ποτε? Δηλαδη οι προτασεις σε ολα τα αξιωματικα συστηματα ειναι απειρες? Ισοδυναμα (νομιζω) θα υπαρχει παντα καποια προταση απτην οποια θα επαγονται απειρες? Τελος αν οντως σε ενα αξιωματικο συστημα δυνατοτητα ελεγχου των προτασεων Godel δεν υπαρχει, αν βγουμε απ'το συστημα, ή παρουμε καποιο πιο γενικο, μπορουμε να ελενξουμε με τα εργαλεια του γενικου τις προτασεις του αρχικου μας συστηματος για να βρουμε αυτες που μας ενδιαφερουν,τις μη-αποδειξιμες, ή για να ελενξουμε μια συγκεκριμενη προταση του αρχικου αν ειναι Godel?


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 20 Ιαν 2007, 20:32 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφή: 01 Μαρ 2006, 21:16
Δημοσ.: 459
Τοποθεσια: Νέος Κόσμος
για τις μη-αληθεις προτασεις βρισκεται παντα αποδειξη οτι δεν ισχυουν, σωστα?

δε νομίζω. Αν η \phi είναι μια αληθής πρόταση για την οποία δεν υπάρχει απόδειξη, τότε η \not\phi είναι μια ψευδής πρόταση, αλλά αν αποδυκνύαμε ότι η \not\phi είναι ψευδής, θα συμπεραίναμε ότι η \phi είναι αληθής. Άρα οι προτάσεις που λες είναι αυτές τις οποίες δεν μπορούμε να αποδείξουμε ούτε αυτές(που είναι αληθείς) ούτε τις αρνήσεις τους(που είναι ψευδείς).

οι προτασεις σε ολα τα αξιωματικα συστηματα ειναι απειρες?

σε αυτό η απάντηση είναι ναι. για οποιαδήποτε αληθή πρόταση κάνε συνδυασμούς με συνδέσμους(πχ συνεπαγωγές ισοδυναμίες) μεταξύ αυτής και μιας άλλης αληθής πρότασης ώστε να πάρεις μια καινούρια.. και ου το καθεξής με την καινούρια.

για το τελυταίο δε σου απαντάω κατηγορηματικά, αλλά νομίζω όχι. Αν βρεις μια απόδειξη στο γενικότερο σύστημα, δεν μπορείς να ξέρεις αν υπάρχει απόδειξη στο μικρότερο.. Ο μόνος τρόπος να μάθεις αν υπάρχει απόδειξη στο μικρότερο είναι να βρεις την απόδειξη αυτή. Όμως ο Γκέντελ μας τα χάλασε εδώ.. γιατί θα ψάχνεις κάτι που δεν υπάρχει!

Επίσης αν καταφέρεις να βγάλεις τα παραπάνω αξιώματα του γενικού συστήματος ώστε να έχεις μια απόδειξη μέσα στο μικρότερο, τότε στην πορεία θα έχεις αποδείξει τα παραπάνω Αξιώματα του γενικότερου συστήματος, δηλαδή στην ουσία δεν έχεις αλλάξει ποτέ ΑΣ! απλά θεώρησες ως αξιώματα μερικές αληθείς προτάσεις, για τις οποίες υπήρχαν αποδείξεις στο μικρό σύστημα, απλώς δεν τις είχες βρει ως τώρα!


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 22 Ιαν 2007, 00:36 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφή: 01 Δεκ 2006, 00:05
Δημοσ.: 2268
Αν βρεις μια αποδειξη στο γενικο συστημα, σιγουρα δεν θα ξερεις αν ειναι και αποδειξη στο αλλο αξιωμ.συστ.
Αυτο που αναρωτιωμουνα ειναι αν μπορεις στο "γενικο" να δειξεις οτι στα πλαισια του "ειδικου" η συγκεκριμενη προταση φ δεν αποδεικνυεται αλλα ειναι αληθης, οχι αν μπορεις να βρεις αποδειξη συγκεκριμενη.
Για τα προηγουμενα εχεις απολυτο δικιο


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 23 Ιαν 2007, 13:47 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφή: 01 Μαρ 2006, 21:16
Δημοσ.: 459
Τοποθεσια: Νέος Κόσμος
Ok για να δείξεις κάτι τέτοιο θα πρέπει να μιμηθείς μια απόδειξη του θεωρήματος μη-πληρότητας του Γκέντελ. Η απόδειξη που έχω δει είναι κατασκευαστική, δηλαδή δίνει μια τέτοια πρόταση, η οποία κατασκευάζεται με συγκεκριμένη μέθοδο. Άρα αν καταφέρεις να μιμηθείς τη μέθοδο αυτή ώστε να καταλήξεις στην πρόταση που θέλεις, αποδεικνύεις αυτό που λες.

Το πρόβλημα είναι ότι μπορεί η πρότασή σου να μην κατασκευάζεται από τη συγκεκριμένη μέθοδο, πχ να εμπίπτει σε μια άλλη κατασκευή μιας άλλης απόδειξης του θεωρήματος μη-πληρότητας(ή σε καμία γνωστή μέχρι σήμερα). Εικάζω πως τέτοια προβλήματα είναι ανοικτά ερευνητικά και δεν υπάρχει ολοκληρωμένη απάντηση, πχ αλγόριθμος για τη λύση τους.

* Εξέλαβέ τα όλα αυτά σα δικές μου εκτιμήσεις! :D


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 23 Ιαν 2007, 18:55 
Χωρίς σύνδεση

Εγγραφή: 13 Ιούλ 2006, 13:49
Δημοσ.: 29
Λογική ερώτηση, η απάντηση νομίζω είναι όχι δεν υπάρχει τέτοιος αλγόριθμος.

Η απόδειξη είναι όμοια με την απόδειξη του θεωρήματος του Goedel. Θυμίζω πως
πάει η απόδειξη του Θ. Goedel. Θεωρούμε την πρόταση:

P η οποία λέει: H P δεν αποδεικνύεται από τα αξιώματα του Peano

Φυσικά το κατόρθωμα του Goedel ήταν να δείξει ότι μία τέτοια πρόταση μπορεί
να γραφεί στη γλώσσα της αριθμοθεωρίας. Ήδη στην καθημερινή γλώσσα αν κάποιος
μας έλεγε κάτι τέτοιο θα τον κοιτάγαμε καχύποπτα. Μοιάζει πάρα πολύ
με το παράδοξο του ψεύτη του Επιμενίδη.

Τώρα αν υποθέσουμε ότι η P αποδεικνύεται από τα αξιώματα του Peano καταλήγουμε σε άτοπο.
Όμοια καταλήγουμε σε άτοπο αν υποθέσουμε ότι δεν αποδεικνύεται από τα αξιώματα του Peano.
Άρα καταλήγουμε ότι είναι ανεξάρτητη από αυτά τα αξιώματα.

Τώρα για να επιστρέψω στο αρχικό ερώτημα ας υποθέσουμε ότι υπάρχει μία θεωρία
M πιο ισχυρή από την αριθμοθεωρία που να μας λέει αν μια πρόταση είναι ανεξάρτητη.
Με άλλα λόγια αν μία πρόταση της αριθμοθεωρίας είναι ανεξάρτητη
τότε είτε η πρόταση είτε η άρνησή της αποδεικνύεται στη θεωρία M.

Τότε μπορούμε να γράψουμε (στη γλώσσα της αριθμοθεωρίας!) την πρόταση:

Q η οποία λέει: είτε η Q είναι ψευδής στην θεωρία Μ είτε η Q είναι ανεξάρτητη
της θεωρίας Μ.

Έχουμε 3 περιπτώσεις:

1. Q ψευδής στην Μ: τότε η Q είναι αληθής στην Μ, άτοπο

2. Q είναι αληθής στην Μ: τότε είτε η Q είναι ψευδής στην θεωρία Μ είτε η Q είναι ανεξάρτητη της θεωρίας Μ, άτοπο

3. Q είναι ανεξάρτητη της θεωρίας Μ: τότε η Q είναι ανεξάρτητη από τα αξιώματα
του Peano. Αλλά τότε από τις ιδιότητες της θεωρίας Μ η Q είναι είτε αληθής είτε
ψευδής στην M, άτοπο


Καταλήγουμε λοιπόν στο συμπέρασμα ότι δεν υπάρχει θεωρία Μ που να μας δίνει
ένα αλγόριθμο να αποφασίσουμε αν μία πρόταση είναι ανεξάρτητη από τα αξιώματα
του Peano.

Φυσικά ο λόγος που μπορούμε να γράψουμε την πρόταση Q στη γλώσσα της
αριθμοθεωρίας είναι ότι υποθέτουμε ότι η M μας δίνει ένα αλγόριθμο (είναι
'πεπερασμένη' θεωρία).


Για περισσότερα μία καλή αναφορά είναι το βιβλίο του Podnieks:
http://www.ltn.lv/~podnieks/gt6.html#BM6_2


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Προτάσεις Godel
ΔημοσίευσηΔημοσιεύτηκε: 18 Ιαν 2010, 10:06 
Χωρίς σύνδεση

Εγγραφή: 10 Ιαν 2010, 19:14
Δημοσ.: 48
Πάντως, αν δεν με απατά η μνήμη μου,έχει αποδειχθεί ότι δέν υπάρχει αλγόριθμος που να αποφαίνεται για την αποδειξιμότητα η μη μιας πρότασης απο έναν μαθητή του Turing.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Προτάσεις Godel
ΔημοσίευσηΔημοσιεύτηκε: 28 Ιούλ 2017, 00:34 
Χωρίς σύνδεση
Regular Forumer

Εγγραφή: 21 Σεπ 2006, 00:20
Δημοσ.: 299
Καπου αναφερεται οτι δεν μπορουμε να ξερουμε αν μια προταση ειναι μη αποδειξιμη.Αυτο ειναι λαθος.Για παραδειγμα ξερουμε οτι η υποθεση του συνεχους ειναι μη αποδειξιμη απο τη ZFC.Σε τετοιου ειδους προτασεις αναφερεται το θεωρημα μη πληροτητας του Godel.

_________________
The real part of the non-trivial zeros of the zeta function is 1/2


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 10 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group