Αξιώματα Πεάνο

Στη μαθηματική λογική τα Αξιώματα Πεάνο, γνωστά και ως Αξιώματα Ντέντεκιντ-Πεάνο, είναι ένα σύνολο μαθηματικών προτάσεων που αφορούν στους φυσικούς αριθμούς και πρώτη φορά παρουσιάστηκαν τον 19ο αιώνα από τον Ιταλό μαθηματικό Τζουζέπε Πεάνο (ιταλικά: Giuseppe Peano). Τα αξιώματα αυτά έχουν χρησιμοποιηθεί σχεδόν αναλλοίωτα σε αρκετές μαθηματικές έρευνες που αφορούν θεμελιώδη ερωτήματα πάνω στη συμβατότητα και την πληρότητα της Θεωρίας των αριθμών.

Η ανάγκη για φορμαλισμό στην αριθμητική δεν ήταν κοινώς αποδεκτή μέχρι που ο Χέρμαν Γκράσσμαν (Hermann Grassmann) έδειξε, τη δεκαετία του 1860, ότι πολλά αποτελέσματα της αριθμητικής μπορούσαν να παραχθούν από βασικότερες διαπιστώσεις πάνω στη "συνάρτηση επόμενο" και τη μαθηματική επαγωγή. Το 1881 ο Τσαρλς Σάντερς Πιρς (Charles Sanders Peirce) παρουσίασε ένα αξίωμα για τους φυσικούς αριθμούς. Το 1888 ο Ρίτσαρντ Ντέντεκιντ (Richard Dedekind) πρότεινε μια σειρά από αξιώματα, ώσπου το 1889 ο Πεάνο δημοσίευσε μια ακριβέστερη εκδοχή αυτών των αξιωμάτων, στο βιβλίο του: " Οι αρχές της Αριθμητικής παρουσιασμένες με νέα μέθοδο". (Λατινικά: "Arithmetices principia, nova methodo exposita").

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

Τα αξιώματα

Όταν ο Πεάνο διατύπωσε τα αξιώματά του, η "γλώσσα" της λογικής δεν ήταν ακόμη πλήρης. Το σύστημα των συμβολισμών που δημιούργησε για να παρουσιάσει τα αξιώματά του δεν αποδείχθηκε δημοφιλές, αν και ήταν ο πρόδρομος για ορισμένους συμβολισμούς της σύγχρονης σημειογραφίας της λογικής, όπως: το σύμβολο "ανήκει" (∈, που προήλθε από το ε του Πεάνο) και το σύμβολο "⊃" (για το οποίο ο Πεάνο χρησιμοποιούσε ένα αντεστραμμένο "C"). Ο Πεάνο διατήρησε μια σαφή διάκριση μεταξύ των μαθηματικών και λογικών συμβόλων, η οποία δεν ήταν ακόμη γνωστή στα μαθηματικά. Ένας τέτοιος διαχωρισμός είχε πρώτα εισαχθεί στο βιβλίο του Γκότλομπ Φρέγκε (Gottlob Frege), "Begriffsschrift", που δημοσιεύθηκε το 1879. Ο Πεάνο χωρίς να γνωρίζει το έργο του Φρέγκε, αναδημιούργησε ανεξάρτητα μια λογική του, με βάση το έργο των Μπουλ (Boole) και Σρέντερ (Schröder).

Τα αξιώματα Πεάνο καθορίζουν τις αριθμητικές ιδιότητες των φυσικών αριθμών, οι οποίοι συνήθως συμβολίζονται με N ή $\mathbb {N} .$ . Τα σύμβολα που δεν ανήκουν στη "γλώσσα" που χρησιμοποιεί, είναι ένα σταθερό σύμβολο 0 και ένα μοναδικό σύμβολο συνάρτησης S.

Το σταθερό 0 υποτίθεται πως είναι φυσικός αριθμός.

1. Το 0 είναι φυσικός αριθμός.

Τα επόμενα τέσσερα αξιώματα περιγράφουν τη σχέση ισότητας.

2. Για κάθε φυσικό αριθμό x, x = x. Δηλαδή η ισότητα είναι ανακλαστική.
3. Για κάθε φυσικό αριθμό x και y, αν x = y, τότε y = x. Δηλαδή η ισότητα είναι συμμετρική.
4. Για κάθε φυσικό αριθμό x, y και z, αν x = y και y = z, τότε x = z. Δηλαδή η ισότητα είναι μεταβατική.
5. Για κάθε α και β, αν α φυσικός αριθμός και α = β, τότε ο β είναι επίσης φυσικός αριθμός. Δηλαδή οι φυσικοί αριθμοί είναι κλειστοί ως προς την ισότητα.

Τα υπόλοιπα αξιώματα καθορίζουν τις αριθμητικές ιδιότητες των φυσικών αριθμών. Υποθέτουμε ότι οι φυσικοί είναι κλειστοί ως προς τη "συνάρτηση επόμενο" S.

6. Για κάθε φυσικό αριθμό n, ο S(n) είναι φυσικός.

Στην αρχική διατύπωση των αξιωμάτων ο Πεανό είχε χρησιμοποιήσει το 1 αντί για το 0 ως πρώτο στοιχείο των φυσικών αριθμών. Αυτή η επιλογή είναι αυθαίρετη, αφού στο 1ο αξίωμα δεν δίδεται καμία προσθετική ιδιότητα στο σταθερό 0. Παρ' όλα αυτά, επειδή το 0 είναι το ουδέτερο στοιχείο της πρόσθεσης, στη Θεωρία των Αριθμών οι νεότερες αναδιατυπώσεις των αξιωμάτων του Πεανό ξεκινούν από το 0. Τα αξιώματα 1 και 6 ορίζουν μια μοναδιαία αναπαράσταση των φυσικών αριθμών: το νούμερο 1 μπορεί να οριστεί ως S(0), το 2 ως S(S(0)) (το οποίο είναι και το S(1)) και γενικά, κάθε φυσικός αριθμός n ορίζεται ως Sⁿ(0). Τα επόμενα δύο αξιώματα ορίζουν τις ιδιότητες αυτής της αναπαράστασης.

7. Για κάθε φυσικό αριθμό n, S(n) ≠ 0 . Επειδή δεν υπάρχει φυσικός αριθμός που ο επόμενός του να είναι το μηδέν 0.
8. Για κάθε φυσικό αριθμό m and n, αν S(m) = S(n), τότε m = n. Αυτό γιατί η συνάρτηση S είναι "1-1" (αμφιμονότιμη).

Από τα αξιώματα 1, 6, 7 και 8 συνεπάγεται ότι το σύνολο των φυσικών αριθμών περιέχει τα διακριτά στοιχεία 0, S(0), S(S(0)) και ότι {0, S(0), S(S(0)), …} ⊆ N. Αυτό δείχνει ότι το σύνολο των φυσικών αριθμών είναι άπειρο. Για να δείξουμε όμως ότι N = {0, S(0), S(S(0)), …}, πρέπει πρώτα να δείξουμε ότι N ⊆ {0, S(0), S(S(0)), …}. π.χ. πρέπει να δειχτεί ότι κάθε φυσικός αριθμός ανήκει στο σύνολο {0, S(0), S(S(0)), …}. Για να το καταφέρουμε αυτό χρειάζεται ένα πρόσθετο αξίωμα, το οποίο συχνά αποκαλείται αξίωμα της επαγωγής. Αυτό το αξίωμα παρέχει μια μέθοδο αιτιολόγησης του συνόλου όλων των φυσικών αριθμών.

9. Αν K είναι ένα σύνολο τέτοιο ώστε:
   • 0 ανήκει στο K,
   • για κάθε αριθμό n, αν n ανήκει στο K, τότε S(n) (ο επόμενος του n) ανήκει στο K,
   τότε το K περιέχει κάθε φυσικό αριθμό.

Το αξίωμα της επαγωγής κάποιες φορές ορίζεται ως εξής:

9. Αν φ είναι μια συνάρτηση της οποίας οι τιμές είναι είτε "αληθής" είτε "ψευδής" (αγγλικά: "predicade" -συνάρτηση που κατασκεύασε ο Τζορτζ Μπουλ- P: X→ {αληθής,ψευδής} ):
   • φ(0) είναι αληθής, και
   • για κάθε φυσικό αριθμό n, αν φ(n) είναι αληθές, τότε φ(S(n)) είναι αληθές,
   τότε φ(n) είναι αληθές για κάθε n.

Θεωρία Αριθμών

Τα αξιώματα του Πεάνο μπορούν να επαυξηθούν με τις διαδικασίες της πρόσθεσης και του πολλαπλασιασμού, αλλά και με τη σχέση διάταξής στο σύνολο N. Οι αντίστοιχες συναρτήσεις και σχέσεις είναι κατασκευασμένες σε δεύτερης τάξης λογική (αγγλικά: "second-order logic") ενώ φαίνεται να είναι μοναδικές χρησιμοποιώντας τα αξιώματα του Πεάνο.

Πρόσθεση

Πρόσθεση είναι η συνάρτηση + : N × N → N η οποία ορίζεται αναδρομικά ως:

${\begin{aligned}a+0&=a,\\a+S(b)&=S(a+b).\end{aligned}}$

Για παράδειγμα:

a + 1 = a + S(0) = S(a + 0) = S(a).

Η δομή(αγγλικά: structure) (N, +) είναι μία αντιμεταθετική ημιομάδα με ουδέτερο στοιχείο το 0. Επίσης είναι διαγραφικό μονοειδές και συνεπώς εμβυθίσιμο σε ομάδα. Η μικρότερη ομάδα που περιέχει το N είναι οι ακέραιοι.

Πολλαπλασιασμός

Ο Πολλαπλασιασμός είναι η συνάρτηση · : N × N → N και ορίζεται αναδρομικά ως:

${\begin{aligned}a\cdot 0&=0,\\a\cdot S(b)&=a+(a\cdot b).\end{aligned}}$

Εύκολα παρατηρούμε ότι αν θέσουμε το b να είναι ίσο με 0 παίρνουμε το ουδέτερο στοιχείο του πολλαπλασιασμού: a · 1 = a · S(0) = a + (a · 0) = a + 0 = a Επιπλέον ο πολλαπλασιασμός είναι επιμεριστικός ως προς την πρόσθεση:

a · (b + c) = (a · b) + (a · c).

Οπότε, η δόμη (N, +, 0, ·, 1) είναι αντιμεταθετικός ημιδακτύλιος.

Θεωρία Αριθμητικής Πρώτης Τάξεως

Ισοδύναμα Αξιώματα

Υπάρχουν πολλά διαφορετικά,αλλά ισοδύναμα,αξιώματα της αριθμητικής του Πεάνο.Ενώ κάποια αξιώματα,όπως αυτό που μόλις περιγράψαμε,χρησιμοποιούν μόνο τους συμβολισμούς για το 0 και τον διαδοχικό αριθμό,την πράξη της πρόσθεσης και του πολλαπλασιασμού,άλλα αξιώματα χρησιμοποιούν τους διατεταγμένους ημιδακτύλιους , περιλαμβάνοντας και ένα επιπρόσθετο σύμβολο για τη σχέση διάταξης.Ένα τέτοιο αξίωμα ξεκινά με τα ακόλουθα αξιώματα που περιγράφουν έναν διακριτά διατεταγμένο ημιδακτύλιο.

1. $\forall x,y,z\in N$. $(x+y)+z=x+(y+z)$, δηλαδή η πρόσθεση είναι προσεταιριστική.
2. $\forall x,y\in N$. $x+y=y+x$,δηλαδή η πρόσθεση είναι αντιμεταθετική.
3. $\forall x,y,z\in N$. $(x\cdot y)\cdot z=x\cdot (y\cdot z)$, δηλαδή ο πολλαπλασιασμός είναι προσεταιριστικός.
4. $\forall x,y\in N$. $x\cdot y=y\cdot x$, δηλαδή ο πολλαπλασιασμός είναι αντιμεταθετικός.
5. $\forall x,y,z\in N$. $x\cdot (y+z)=(x\cdot y)+(x\cdot z)$, δηλαδή η επιμεριστική ιδιότητα.
6. $\forall x\in N$. $x+0=x\land x\cdot 0=0$, δηλαδή το μηδέν είναι το ουδέτερο στοιχείο της πρόσθεσης.
7. $\forall x\in N$. $x\cdot 1=x$, δηλαδή η μονάδα είναι το ουδέτερο στοιχείο του πολλαπλασιασμού.
8. $\forall x,y,z\in N$. $x<y\land y<z\supset x<z$, δηλαδή ο τελεστής '<' είναι μεταβατικός.
9. $\forall x\in N$. $\neg (x<x)$, δηλαδή ο τελεστής '<' είναι αντανακλαστικός.
10. $\forall x,y\in N$. $x<y\lor x=y\lor y<x$.
11. $\forall x,y,z\in N$. $x<y\supset x+z<y+z$.
12. $\forall x,y,z\in N$. $0<z\land x<y\supset x\cdot z<y\cdot z$.
13. $\forall x,y\in N$. $x<y\supset \exists z\in N$. $x+z=y$.
14. $0<1\land \forall x\in N$. $x>0\supset x\geq 1$.
15. $\forall x\in N$. $x\geq 0$.

Η θεωρία που ορίζει αυτά τα αξιώματα είναι γνωστή σαν PA^–: PA προκύπτει προσθέτοντας το σχήμα επαγωγής πρώτης τάξης.

Μια σημαντική ιδιότητα της PA^– είναι το γεγονός ότι κάθε δομή M που ικανοποιεί αυτή την θεωρία έχει ένα αρχικό τμήμα (με σχέση διάταξης ≤) ισομορφικό με το N. Τα στοιχεία του M \ N είναι γνωστά σαν άτυπα στοιχεία.

Μοντέλα

Ένα μοντέλο των αξιωμάτων Πεάνο ειναι η τριάδα (N, 0, S), όπου N είναι ένα (αναγκαία άπειρο) σύνολο, 0 ∈ N και S : N → N ικανοποιεί τα παραπάνω αξιώματα. Ο Dedekind απέδειξε το 1888 στο βιβλίο του ‘Τί είναι οι αριθμοί και τι θα έπρεπε να είναι’( What are numbers and what should they be) (γερμανικά: Was sind und was sollen die Zahlen‎‎) ότι οποιαδήποτε δυο μοντέλα των αξιωμάτων Πεάνο (συμπεριλαμβάνοντας το δεύτερης τάξης αξίωμα της επαγωγής) είναι ισομορφικά.Συγκεκριμένα, με δεδομένα δυο μοντέλα (N_A, 0_A, S_A) και (N_B, 0_B, S_B) των αξιωμάτων Πεάνο, υπάρχει μοναδικός ομομορφισμός f : N_A → N_B που ικανοποιεί τις σχέσεις

${\begin{aligned}f(0_{A})&=0_{B}\\f(S_{A}(n))&=S_{B}(f(n))\end{aligned}}$

και είναι αμφιμονοσήμαντη απεικόνιση. Τα δεύτερης τάξης αξιώματα Πεάνο είναι επομένως κατηγορικά(αγγλικά:categorical) : αυτό δεν είναι, ωστόσο, η περίπτωση αναδιατύπωσης οποιουδήποτε πρώτης τάξης αξιώματος Πεάνο.

Άτυπα Μοντέλα (αγγλικά: Nonstandard models)

Παρόλο που οι συνήθεις φυσικοί αριθμοί ικανοποιούν τα αξιώματα PA, υπάρχουν άλλα άτυπα μοντέλα όπως : το θεώρημα του συμπαγούς που αναφέρει ότι η ύπαρξη άτυπων στοιχείων δεν μπορεί να εξαιρεθεί από την πρώτης τάξης λογική.Το παραπάνω θεώρημα των Löwenheim–Skolem δείχνει ότι υπάρχουν άτυπα μοντέλα PA για άπειρους πληθικούς αριθμούς. Αυτή δεν είναι η περίπτωση του πρωτότυπου (δεύτερης τάξης) αξιώματος Πεάνο,το οποίο έχει ένα μοναδικό μοντέλο, για τον ισομορφισμό. Αυτό δείχνει ότι κατά μία έννοια το πρώτης τάξης σύστημα αξιωμάτων PA είναι ασθενέστερο του συστήματος αξιωμάτων Πεάνο δεύτερης τάξης.

Ενώ ερμηνεύεται σαν απόδειξη στο σύνολο θεωρίας πρώτης τάξης, όπως το ZFC, η απόδειξη κατηγοριοποίησης(αγγλικα:categoricity) του Dedekind για το PA δείχνει ότι κάθε μοντέλο της θεωρίας συνόλων έχει ένα μοναδικό μοντέλο για τα αξιώματα Πεάνο, για τον ισομορφισμό, που ενσωματώνει σαν αρχικό τμήμα όλων των άλλων μοντέλων PA που περιλαμβάνεται στα μοντέλα της θεωρίας συνόλων.Στο τυποποιημένο μοντέλο της θεωρίας συνόλων,αυτό το ελάχιστο μοντέλο PA είναι το καθιερωμένο μοντέλο PA: ωστόσο,σε ένα άτυπο μοντέλο της θεωρίας συνόλων,μπορεί να είναι ένα άτυπο μοντέλο PA.Αυτό δεν μπορεί να αποφευχθεί με οποιαδήποτε τυποποίηση της θεωρίας συνόλων. Είναι φυσικό να αναρωτηθεί κανείς αν ένα αριθμήσιμο άτυπο μοντέλο μπορεί να οριστεί ρητά. Το θεώρημα του Tennenbaum,που αποδείχτηκε το 1959,δείχνει ότι δεν υπάρχει αριθμήσιμο άτυπο μοντέλο PA,στο οποίο είτε η πρόσθεση είτε ο πολλαπλασιασμός να είναι υπολογίσιμα. Αυτό δείχνει ότι είναι δύσκολο να είναι είμαστε απόλυτα σαφείς στην περιγραφή της πράξης της πρόσθεσης και του πολλαπλασιασμού ενός μετρήσιμου άτυπου μοντέλου PA. Παρολ’αυτά, υπάρχει μόνο ένας δυνατός τύπος διάταξης ενός μετρήσιμου άτυπου μοντέλου.Θεωρώντας ω τον τύπο διάταξης των φυσικών αριθμών,ζ τον τύπο διάταξης των ακεραίων, και η τον τύπο διάταξης των ρητών, ο τύπος διάταξης ενός οποιουδήποτε μετρήσιμου άτυπου μοντέλου PA είναι ω + ζ•η, το οποίο μπορεί να απεικονιστεί σαν εικόνα των φυσικών αριθμών ακολουθούμενων από μια γραμμική διάταξη εικόνων των ακεραίων.

Μοντέλα βασισμένα στη Θεωρία Συνόλων

Όταν τα αξιώματα Πεάνο προτάθηκαν για πρώτη φορά, ο Bertrand Russell και άλλοι συμφώνησαν ότι αυτά τα αξιώματα όριζαν έμμεσα τι είναι οι "φυσικοί αριθμοί". Ο Henri Poincaré ήταν περισσότερο επιφυλακτικός, λέγοντας ότι απλά προσδιορίζουν τους φυσικούς αριθμούς εφόσον αυτοί ήταν συνεπείς : αν υπάρχει απόδειξη που να ξεκινά από αυτά ακριβώς τα αξιώματα και καταλήγει σε μια αντίφαση όπως 0 = 1, τότε τα αξιώματα είναι ασυνεπή, και δεν ορίζουν τίποτα. Το 1900,ο David Hilbert έθεσε το πρόβλημα της απόδειξης της συνέπειάς τους χρησιμοποιώντας μόνο finitistic μεθόδους όπως το δεύτερο από τα εικοσιτρία προβλήματά του. Το 1931, ο Kurt Gödel απέδειξε το δεύτερο θεώρημα της μη πληρότητας, το οποίο δείχνει ότι αυτή η απόδειξη της συνέπειας δεν μπορεί τυποποιηθεί στην ίδια την αριθμητική του Πεάνο.

Παρόλο που είναι ευρέως γνωστό το γεγονός ότι το θεώρημα του Gödel αποκλείει την πιθανότητα μιας finitistic απόδειξης της συνέπειας για την αριθμητική του Πεάνο, αυτό εξαρτάται από την ακριβή έννοια που δίνει ο καθένας στην finitistic απόδειξη.Ο ίδιος ο Gödel τόνισε την πιθανότητα να δωθεί μια finitistic απόδειξη της συνέπειας της αριθμητικής του Πεάνο ή ισχυρότερων συστημάτων χρησιμοποιώντας finitistic μεθόδους που δεν είναι τυποποιήσιμες στην αριθμητική Πεάνο, και το 1958 ο Gödel δημοσίευσε μια μέθοδο για την απόδειξη της συνέπειας της αριθμητικής χρησιμοποιώντας θεωρία τύπου. Το 1936, ο Gerhard Gentzen έδωσε μια απόδειξη της συνέπειας των αξιωμάτων Πεάνο,χρησιμοποιώντας υπερπεπερασμένη επαγωγή σε έναν τακτικό αριθμό ε₀.Ο Gentzen εξήγησε ότι: "Ο σκοπός αυτής της εργασίας είναι να αποδείξω την συνέπεια των στοιχειωδών αριθμών ή καλύτερα να μειώσω τις αμφιβολίες με ορισμένες θεμελιώδεις αρχές". Η απόδειξη του Gentzen είναι αμφισβητήσιμα finitistic,αφού ο υπερπεπερασμένος τακτικός ε₀ μπορεί να κωδικοποιηθεί ως προς πεπερασμένα αντικείμενα (για παράδειγμα,όπως μια μηχανή Turing περιγράφει μια κατάλληλη σειρά των ακεραίων,ή πιο αφηρημένα σαν αποτελούμενη από πεπερασμένα δέντρα, κατάλληλα γραμμικά διατεταγμένη). Το αν η απόδειξη του Gentzen συμφωνεί με τις προϋποθέσεις του Χίλμπερτ είναι ασαφές: δεν υπάρχει ένας γενικά αποδεκτός ορισμός του τι ακριβώς είναι η finitistic απόδειξη, και ο Χίλμπερτ δεν έδωσε ποτέ έναν ακριβή ορισμό.

Η συντριπτική πλειοψηφία των σύγχρονων μαθηματικών πιστεύει ότι τα αξιώματα Πεάνο είναι συνεπή, βασιζόμενοι είτε στη διαίσθησή τους είτε στην αποδοχή μιας απόδειξης της συνέπειας όπως αυτή του Gentzen.Το μικρό ποσοστό των μαθηματικών που υποστηρίζουν τον ultrafinitism απορρίπτουν τα αξιώματα Πεάνο επειδή τα αξιώματα απαιτούν ένα άπειρο σύνολο φυσικών αριθμών.

Εξωτερικές Συνδέσεις

http://mathbooksgr.files.wordpress.com/2012/02/mlexiko2012.pdf