海口“懂事娃”摔伤住院两月未苏醒 民政补助1....

百度 不料，邓某和徐某不听劝阻，在飞机上大声喧哗，其中邓某还使用手机拨打东航客服电话进行投诉。

Η μαθηματικ? λογικ? ε?ναι ?να? κλ?δο? των μαθηματικ?ν και τη? επιστ?μη? υπολογιστ?ν, με στεν? σχ?ση και με τη φιλοσοφικ? λογικ?. Το πεδ?ο περιλαμβ?νει τη μαθηματικ? μελ?τη τη? λογικ?? και τι? εφαρμογ?? τη? τυπικ?? λογικ?? σε ?λλε? περιοχ?? των μαθηματικ?ν. Οι βασικ?τερε? ιδ?ε? στη μαθηματικ? λογικ? περιλαμβ?νουν τη μελ?τη τη? εκφραστικ?? ισχ?ο? των τυπικ?ν συστημ?των και τη? συμπερασματικ?? ισχ?ο? των συστημ?των τυπικ?ν αποδε?ξεων.

Η μαθηματικ? λογικ? διαιρε?ται συχν? στα υποπεδ?α θεωρ?α συν?λων, θεωρ?α μοντ?λων, θεωρ?α αναδρομ??, θεωρ?α αποδε?ξεων και κατασκευαστικ? μαθηματικ?. Οι περιοχ?? αυτ?? μοιρ?ζονται βασικ? αποτελ?σματα π?νω στη λογικ?, και ειδικ? στην λογικ? πρ?του βαθμο? και την ορισιμ?τητα.

Απ? τη γ?ννησ? τη?, η μαθηματικ? λογικ? ?χει συμβ?λλει αλλ? και ωθε?ται απ? τη μελ?τη των θεμελ?ων των μαθηματικ?ν. Η μελ?τη αυτ? ξεκ?νησε στο τ?λο? του 19ου αι?να με την αν?πτυξη των αξιωματικ?ν πλαισ?ων για τη γεωμετρ?α, την αριθμητικ? και την αν?λυση. Στην αρχ? του 20ο? αι?να διαμορφ?θηκε απ? το πρ?γραμμα του Ντ?βιντ Χ?λμπερτ για την απ?δειξη τη? συν?πεια? των θεμελιακ?ν θεωρι?ν. Η εργασ?α π?νω στη θεωρ?α συν?λων ?δειξε ?τι σχεδ?ν ?λα τα συνηθισμ?να μαθηματικ? μπορο?ν να διατυπωθο?ν με β?ση τα σ?νολα, αν και υπ?ρχουν κ?ποια θεωρ?ματα που δεν μπορο?ν να αποδειχθο?ν στα συν?θη αξιωματικ? συστ?ματα για τη θεωρ?α συν?λων. Η σ?γχρονη μελ?τη στα θεμ?λια των μαθηματικ?ν συχν? εστι?ζει στο να θεσπ?σει ποια κομμ?τια των μαθηματικ?ν μπορο?ν να διατυπωθο?ν σε συγκεκριμ?να τυπικ? συστ?ματα, και ?χι στο να αναπτ?ξει θεωρ?ε? απ? ?που αναπτ?σσονται ?λα τα μαθηματικ?.

Ιστορ?α

Μαθηματικ? λογικ? ονομ?στηκε απ? τον Τζουζ?πε Πε?νο αυτ? που αργ?τερα ονομ?στηκε συμβολικ? λογικ?. Στην κλασσικ? τη? ?κδοση, οι βασικ?? αρχ?? θυμ?ζουν τη λογικ? του Αριστοτ?λη, γραμμ?νε? ?μω? με συμβολικ? τρ?πο αντ? για φυσικ? γλ?σσα. Ορισμ?νοι απ? του? πιο φιλοσοφικο?? μαθηματικο?? ?καναν προσπ?θειε? να χειριστο?ν τι? πρ?ξει? τη? τυπικ?? λογικ?? με συμβολικ? ? αλγεβρικ? τρ?πο, ?πω? ο Λ?ιμπνιτ? και ο Λ?μπερτ, αλλ? οι προσπ?θει?? του? ?μειναν ?γνωστε? και απομονωμ?νε?. ?ταν ο Τζορτζ Μπουλ και ο Α?γουστο? Ντε Μ?ργκαν, στο μ?σο του 19ου αι?να που παρουσ?ασαν ?να συστηματικ? τρ?πο μελ?τη? τη? λογικ??. Το παραδοσιακ? Αριστοτ?λειο δ?γμα τη? λογικ?? αναμορφ?θηκε και συμπληρ?θηκε, και απ? αυτ? την εξ?λιξη προ?κυψε ?να επαρκ?? εργαλε?ο για τη μελ?τη των θεμελιακ?ν ιδε?ν των μαθηματικ?ν. Θα ?ταν παραπλανητικ? να ισχυριστε? κανε?? ?τι οι θεμελιακ?? διαμ?χε? που υπ?ρχαν την περ?οδο 199-1925 ?χουν ?λε? λυθε?, αλλ? η φιλοσοφ?α των μαθηματικ?ν ?χει διευκρινιστε? σε μεγ?λο βαθμ? απ? τη ?ν?α? λογικ?.

Η αρχικ? Ελληνικ? αν?πτυξη τη? λογικ?? ?δωσε μεγ?λη ?μφαση στι? μορφ?? των ισχυρισμ?ν, εν? η συμπεριφορ? τη? τρ?χουσα? μαθηματικ?? λογικ?? μπορε? να συνοψιστε? ω? η συνδυαστικ? μελ?τη του περιεχομ?νου. Αυτ? καλ?πτει τ?σο το συντακτικ? ?σο και την ερμηνε?α, δηλαδ? τ?σο τη μορφ? των εκφρ?σεων ?σο και το ν?ημ? του?. Στην επιστ?μη υπολογιστ?ν, εντελ?? συντακτικ? μελ?τη επιτρ?πει σε μια συμβολοσειρ? απ? μια τυπικ? γλ?σσα να μετασχηματιστε? απ? ?να μεταγλωττιστ? σε μια σειρ? εντολ?ν μηχαν??. Η εννοιολογικ? μελ?τη επιτρ?πει σε ?ναν προγραμματιστ? να επιλ?ξει ποιε? συμβολοσειρ?? να χρησιμοποι?σει για να επιτ?χει ?να συγκεκριμ?νο στ?χο.

Κ?ποιε? σημαντικ?? δημοσιε?σει? στη μαθηματικ? λογικ? περι?χουν το Begriffsschrift του Γκ?τλομπ Φρ?γκε, τι? Studies in Logic του Τσαρλ? Π?ιρ? την Principia Mathematica του Μπ?ρτραντ Ρ?σσελ και του ?λφρεντ Νορθ Γου?ιτχεντ και το On Formally Undecidable Propositions of Principia Mathematica and Related Systems του Κουρτ Γκ?ντελ.

Υποπεδ?α και ε?ρο?

Η σ?γχρονη μαθηματικ? λογικ? διαιρε?ται περ?που σε τ?σσερι? περιοχ??: θεωρ?α συν?λων, θεωρ?α μοντ?λων, θεωρ?α αναδρομ??, και θεωρ?α αποδε?ξεων και κατασκευαστικ? μαθηματικ?. Κ?θε μια απ? αυτ?? τι? περιοχ?? ?χει ιδια?τερο αντικε?μενο μελ?τη?, αν και πολλ?? τεχνικ?? και αποτελ?σματα ε?ναι κοιν?. Τα σ?νορα μεταξ? των πεδ?ων αυτ?ν, και ακ?μα μεταξ? τη? μαθηματικ?? λογικ?? και ?λλων πεδ?ων των μαθηματικ?ν δεν ε?ναι π?ντα καθαρ?. Για παρ?δειγμα, το θε?ρημα μη-πληρ?τητα? του Γκ?ντελ ?χι μ?νο αποτελε? σταθμ? στη θεωρ?α αναδρομ?? και τη θεωρ?α αποδε?ξεων, αλλ? και ?χει οδηγ?σει στο θε?ρημα Λ?εμπ, το οπο?ο ε?ναι σημαντικ? στην τροπικ? λογικ?. Το μαθηματικ? πεδ?ο τη? θεωρ?α? κατηγορι?ν χρησιμοποιε? πολλ?? τυπικ?? αξιωματικ?? μεθ?δου? που θυμ?ζουν αυτ?? που χρησιμοποιο?νται στη μαθηματικ? λογικ?, αλλ? η θεωρ?α κατηγορι?ν δεν θεωρε?ται συν?θω? υποπεδ?ο τη? μαθηματικ?? λογικ??.

Τυπικ? λογικ?

Στον πυρ?να τη?, η μαθηματικ? λογικ? χειρ?ζεται μαθηματικ?? ?ννοιε? που εκφρ?ζονται χρησιμοποι?ντα? τυπικ? συστ?ματα λογικ??. Τα συστ?ματα αυτ?, αν και διαφ?ρουν σε πολλ?? λεπτομ?ρειε?, μοιρ?ζονται την κοιν? ιδι?τητα του να εξετ?ζουν μ?νο εκφρ?σει? σε κ?ποια συγκεκριμ?νη τυπικ? γλ?σσα. Το σ?στημα τη? λογικ?? πρ?του βαθμο? (first-order logic) ?χει μελετηθε? περισσ?τερο λ?γω τη? εφαρμογ?? του στα θεμ?λια των μαθηματικ?ν και λ?γω των επιθυμητ?ν του ιδιοτ?των. Μελετ?νται επ?ση? εκφραστικ?τερε? κλασσικ?? λογικ?? ?πω? η λογικ? δευτ?ρου βαθμο? (second-order logic) ? η απειρικ? λογικ? (infinitary logic), αλλ? και μη κλασσικ?? λογικ?? ?πω?, η διαισθητικ? λογικ? (intuitionistic logic).

Λογικ? πρ?του βαθμο?

Η λογικ? πρ?του βαθμο? ε?ναι ?να συγκεκριμ?νο λογικ? σ?στημα. Η σ?νταξ? τη? περι?χει μ?νο πεπερασμ?νε? εκφρ?σει? ω? καλ? ορισμ?νε? προτ?σει?, εν? η σημασιολογ?α τη? χαρακτηρ?ζονται απ? τον περιορισμ? ?λων των ποσοδεικτ?ν σε κ?ποιο συγκεκριμ?νο πεδ?o.

Αρχικ? αποτελ?σματα για την τυπικ? λογικ? θ?σπισαν περιορισμο?? για την πρωτοβ?θμια λογικ?. το θε?ρημα Λ?βενχ?ιμ-Σκ?λεμ (1919) ?δειξε ?τι αν ?να σ?νολο προτ?σεων σε μια αριθμ?σιμη πρωτοβ?θμια γλ?σσα ?χει ?να ?πειρο μοντ?λο, τ?τε ?χει τουλ?χιστον ?να μοντ?λο απ? κ?θε ?πειρη πληθικ?τητα. Αυτ? δε?χνει ?τι ε?ναι αδ?νατο για ?να σ?νολο απ? πρωτοβ?θμια αξι?ματα να χαρακτηρ?ζουν του? φυσικο?? αριθμο??, του? πραγματικο??, ? οποιαδ?ποτε ?λλη ?πειρη δομ? διαφ?ρει μ?χρι ?να ισομορφισμ?. Δεδομ?νου ?τι ο στ?χο? των αρχικ?ν θεμελιακ?ν μελετ?ν ?ταν να παραχθο?ν αξιωματικ?? θεωρ?ε? για ?λα τα κομμ?τια των μαθηματικ?ν, αυτ? καθιστο?σε ιδια?τερα ?καμπτο περιορισμ?.

Το θε?ρημα πληρ?τητα? του Γκ?ντελ (G?del 1929) θ?σπισε την ισοδυναμ?α μεταξ? σημασιολογικ?ν και συντακτικ?ν ορισμ?ν τη? λογικ?? συν?πεια? στην πρωτοβ?θμια λογικ?. Δε?χνει ?τι αν μια συγκεκριμ?νη πρ?ταση ε?ναι αληθ?? σε κ?θε μοντ?λο που ικανοποιε? ?να συγκεκριμ?νο σ?νολο αξιωμ?των, τ?τε θα πρ?πει να υπ?ρχει πεπερασμ?νο? συλλογισμ?? που συμπερα?νει την πρ?ταση απ? τα αξι?ματα. Το θε?ρημα συμπαγε?α? (compactness theorem) πρ?τα εμφαν?στηκε ω? λ?μμα στην απ?δειξη του θεωρ?ματο? πληρ?τητα? του Γκ?ντελ, και χρει?στηκαν αρκετ? χρ?νια μ?χρι να κατανοηθε? η σημασ?α του και να φτ?σει να εφαρμ?ζεται τακτικ?. Αναφ?ρει ?τι ?να σ?νολο προτ?σεων ?χει μοντ?λο αν και μ?νο αν κ?θε πεπερασμ?νο υποσ?νολο ?χει μοντ?λο, ? με ?λλα λ?για ?τι ?να ασυνεπ?? σ?νολο απ? προτ?σει? θα πρ?πει να ?χει κ?ποιο πεπερασμ?νο ασυνεπ?? υποσ?νολο. Τα θεωρ?ματα πληρ?τητα? και συμπαγε?α? επιτρ?πουν εξελιγμ?νη αν?λυση τη? λογικ?? συν?πεια? στην πρωτοβ?θμια λογικ?, και την αν?πτυξη τη? θεωρ?α? μοντ?λων, και αποτελο?ν βασικ? λ?γο για την δι?δοση τη? λογικ?? πρ?του βαθμο? στα μαθηματικ?.

Τα θεωρ?ματα μη-πληρ?τητα? του Γκ?ντελ (G?del 1931) θεσπ?ζουν περετα?ρω ?ρια στι? πρωτοβ?θμιε? αξιωματικοποι?σει?. Το πρ?το θε?ρημα μη πληρ?τητα? αναφ?ρει ?τι καν?να επαρκ?? ισχυρ?, αποτελεσματικ? λογικ? σ?στημα δεν μπορε? να αποδε?ξει την συν?πεια του εαυτο? του, παρ? μ?νο αν δεν ε?ναι στην πραγματικ?τητα συνεπ??. Λ?γοντα? αποτελεσματικ? εννοο?με ?τι ε?ναι δυνατ? να αποφασιστε?, δεδομ?νη? μια? πρ?ταση? στη γλ?σσα του συστ?ματο?, αν αυτ? η πρ?ταση ε?ναι αξ?ωμα. ?ταν εφαρμ?ζεται στην πρωτοβ?θμια λογικ?, το πρ?το θε?ρημα μη πληρ?τητα? συνεπ?γεται ?τι κ?θε πρωτοβ?θμια θεωρ?α που ε?ναι αρκετ? ισχυρ?, συνεπ??, και αποτελεσματικ? ?χει μοντ?λα που δεν ε?ναι στοιχειωδ?? ισοδ?ναμα. Αυτ? ε?ναι ισχυρ?τερο? περιορισμ?? απ? αυτ?ν που τ?θεται λ?γω του θεωρ?ματο? Λ?βενχ?ιμ-Σκ?λεμ. Το δε?τερο θε?ρημα μη-πληρ?τητα? εκφρ?ζει ?τι καν?να επαρκ?? ισχυρ?, συνεπ??, αποτελεσματικ? αξιωματικ? σ?στημα για την αριθμητικ? δεν μπορε? να αποδε?ξει την συν?πεια του εαυτο? του, πρ?γμα που σημα?νει ?τι το πρ?γραμμα του Χ?λμπερτ δεν γ?νεται να υλοποιηθε?.

Θεωρ?α συν?λων

Η Θεωρ?α συν?λων ε?ναι η μελ?τη των συν?λων, τα οπο?α ε?ναι αφηρημ?νε? συλλογ?? απ? αντικε?μενα. Πολλ?? απ? τι? βασικ?? ?ννοιε? τη? θεωρ?α? συν?λων ?πω? οι τακτικο? και οι πληθικο? αριθμο?, αναπτ?χθηκαν ?τυπα απ? τον Καντ?ρ πριν αναπτυχθο?ν τυπικ?? αξιωματικοποι?σει? τη? θεωρ?α? συν?λων. Η πρ?τη τ?τοια αξιωματικοπο?ηση, απ? τον Ζερμ?λο (1908), επεκτ?θηκε ελαφρ?? για να γ?νει η θεωρ?α συν?λων Ζερμ?λο-Φρ?νκελ (ZF), η οπο?α ε?ναι η πιο διαδεδομ?νη θεμελι?δη? θεωρ?α για τα μαθηματικ?.

?χουν προταθε? και ?λλε? τυποποι?σει? τη? θεωρ?α? συν?λων, ?πω? η θεωρ?α συν?λων φον Ν?ιμαν-Μπερν?ι?-Γκ?ντελ (NBG), η θεωρ?α συν?λων Μ?ρ?-Κ?λλυ (MK) και τα ν?α θεμ?λια (NF). Απ? αυτ??, οι ZF, NBG και MK ε?ναι παρ?μοιε? στην περιγραφ? μια? συσσωρευτικ?? ιεραρχ?α? συν?λων. Τα ν?α θεμ?λια ?χουν διαφορετικ? προσ?γγιση, επιτρ?πουν να διατυπωθο?ν σ?νολα ?πω? το σ?νολο ?λων των συν?λων, αλλ? με αντ?τιμο τον περιορισμ? στα αξι?ματα ?παρξ?? του?. Το σ?στημα θεωρ?α συν?λων Κρ?πκε-Πλ?τεκ ε?ναι στεν? σχετιζ?μενο με την γενικ? θεωρ?α αναδρομ??.

Δ?ο δι?σημε? προτ?σει? στη θεωρ?α συν?λων ε?ναι το αξ?ωμα τη? επιλογ?? και η υπ?θεση του συνεχο??. Το αξ?ωμα επιλογ??, αρχικ? διατυπωμ?νο απ? τον Ζερμ?λο (1904), αποδε?χθηκε ανεξ?ρτητο τη? θεωρ?α? ZF απ? τον Φρ?νκελ (1922), αλλ? ε?ναι πλ?ον ευρ?ω? αποδεκτ? απ? του? μαθηματικο??. Διατυπ?νει ?τι δεδομ?νη? μια? συλλογ?? απ? μη κεν? σ?νολα, υπ?ρχει ?να μοναδικ? σ?νολο C που περι?χει ακριβ?? ?να στοιχε?ο απ? κ?θε σ?νολο στη συλλογ?. Το σ?νολο C λ?γεται ?τι ?επιλ?γει? ?να στοιχε?ο απ? κ?θε σ?νολο στη συλλογ?. Αν και η δυνατ?τητα να γ?νει μια τ?τοια επιλογ? φα?νεται προφαν?? σε κ?ποιου?, αφο? κ?θε σ?νολο στη συλλογ? ε?ναι μη-κεν?, η ?λλειψη εν?? γενικο?, συγκεκριμ?νου καν?να με β?ση τον οπο?ο γ?νεται η επιλογ? κ?νει το αξ?ωμα μη κατασκευαστικ?. Οι Στ?φαν Μπαν?χ και ?λφρεντ Τ?ρσκι (1924) ?δειξαν ?τι το αξ?ωμα τη? επιλογ?? μπορε? να χρησιμοποιηθε? για να αποσυνθ?σει μια στερε? σφα?ρα σε πεπερασμ?νο αριθμ? κομματι?ν, τα οπο?α μπορο?ν στη συν?χεια να επαναδιαταχθο?ν, χωρ?? αλλαγ? στο μ?γεθο?, για να σχηματ?σουν δ?ο στερε?? σφα?ρε? του αρχικο? μεγ?θου?. Το θε?ρημα αυτ?, γνωστ? και ω? παρ?δοξο Μπαν?χ-Τ?ρσκι ε?ναι ?να απ? αρκετ? αντιδιαισθητικ? αποτελ?σματα του αξι?ματο? επιλογ??.

Η υπ?θεση του συνεχο??, που αρχικ? προτ?θηκε ω? εικασ?α απ? τον Καντ?ρ, τ?θηκε απ? τον Χ?λμπερτ ω? ?να απ? τα 23 του προβλ?ματα το 1900. Ο Γκ?ντελ ?δειξε ?τι η υπ?θεση του συνεχο?? δεν μπορε? να διαψευσθε? απ? τα αξι?ματα τη? θεωρ?α? ZF (με ? χωρ?? το αξ?ωμα επιλογ??), αναπτ?σσοντα? το κατασκευ?σιμο σ?μπαν τη? θεωρ?α? συν?λων, στο οπο?ο η υπ?θεση του συνεχο?? πρ?πει να ισχ?ει. Το 1963, ο Πωλ Κο?ν ?δειξε ?τι η υπ?θεση του συνεχο?? δε μπορε? να αποδειχθε? απ? τα αξι?ματα τη? θεωρ?α? συν?λων Ζερμ?λο-Φρ?νκελ (Cohen 1966). Αυτ? το αποτ?λεσμα ανεξαρτησ?α? δεν ?λυσε τελε?ω? την ερ?τηση του Χ?λμπερτ, αφο? θα μπορο?σε ν?α αξι?ματα για τη θεωρ?α συν?λων να επιλ?σουν την υπ?θεση. Πρ?σφατη εργασ?α στο αντικε?μενο γ?νεται π? τον Χιο? Γο?ντιν, αν και η σημασ?α τη? δεν ε?ναι ακ?μα ξεκ?θαρη (Woodin 2001).

Η σ?γχρονη ?ρευνα στη συνολοθεωρ?α περιλαμβ?νει τη μελ?τη των μεγ?λων πληθικ?ν και προσδιορισμ?ν. Οι μεγ?λοι πληθικο? ε?ναι πληθικο? αριθμο? με συγκεκριμ?νε? ιδι?τητε? τ?σο ισχυρ?? ?στε η ?παρξ? του? δεν αποδεικν?εται στην ZFC. Η ?παρξη του μικρ?τερου δυνατο? μεγ?λου πληθικο? που μελετ?ται συν?θω?, εν?? απροσπ?λαστου πληθικο?, ?δη συνεπ?γεται την συν?πεια τη? ZFC. Παρ'?λο το ?τι οι μεγ?λοι πληθικο? ?χουν υπερβολικ? υψηλ? πληθικ?τητα, η ?παρξ? του? ?χει πολλ?? δυσχερε?? συν?πειε? για τη δομ? τη? γραμμ?? των πραγματικ?ν. Ο προσδιορισμ?? (determinacy) αναφ?ρεται στην πιθαν? ?παρξη επιτυχ?ν στρατηγικ?ν σε συγκεκριμ?να πα?γνια δ?ο παικτ?ν (τα πα?γνια τ?τε λ?γονται προσδιορισμ?να). Η ?παρξη των στρατηγικ?ν αυτ?ν επηρε?ζει δομικ?? ιδι?τητε? τη? γραμμ?? των πραγματικ?ν και ?λλων Πολωνικ?ν χ?ρων.

Θεωρ?α μοντ?λων

Η Θεωρ?α μοντ?λων μελετ? τα μοντ?λα δι?φορων τυπικ?ν θεωρι?ν. Εδ? θεωρ?α λ?γεται το σ?νολο απ? προτ?σει? σε κ?ποια δεδομ?νη τυπικ? λογικ? και οπλισμ? (signature), εν? ?να μοντ?λο ε?ναι μια δομ? που δ?νει μια συγκεκριμ?νη ερμηνε?α τη? θεωρ?α?. Η θεωρ?α μοντ?λων ε?ναι στεν? συνδεδεμ?νη με την καθολικ? ?λγεβρα, και αλγεβρικ? γεωμετρ?α, αν και οι μ?θοδοι τη? θεωρ?α? μοντ?λων εστι?ζουν περισσ?τερο σε λογικ?? ανησυχ?ε? απ? αυτ? τα πεδ?α.

Το σ?νολο ?λων τον μοντ?λων μια? δεδομ?νη? θεωρ?α? λ?γεται στοιχει?δη? κλ?ση. Η κλασσικ? θεωρ?α μοντ?λων επιχειρε? να ανακαλ?ψει τι? ιδι?τητε? των μοντ?λων σε κ?ποια στοιχει?δη κλ?ση, ? να ανακαλ?ψει ε?ν κ?ποιε? κλ?σει? απ? δομ?? αποτελο?ν στοιχει?δει? κλ?σει?.

Η μ?θοδο? απ?λειψη? ποσοδεικτ?ν μπορε? να χρησιμοποιηθε? για να δε?ξει ?τι ορ?σιμα σ?νολα σε συγκεκριμ?νε? θεωρ?ε? δεν μπορε? να ε?ναι πολ? περ?πλοκα. Ο Τ?ρσκι (1948) θ?σπισε την απαλοιφ? ποσοδεικτ?ν για real-closed πεδ?α, αποτ?λεσμα που επ?ση? δε?χνει ?τι η θεωρ?α πεδ?ων των πραγματικ?ν αριθμ?ν ε?ναι αποκρ?σιμο. (Παρατ?ρησε ακ?μα ?τι οι μ?θοδο? του ε?ναι εξ?σου εφαρμ?σιμε? σε αλγεβρικ? κλειστ? πεδ?α με οποιουδ?ποτε χαρακτηριστικο?.) ?να υποπεδ?ο που αναπτ?χθηκε απ? αυτ?, ασχολε?ται με ο-ελ?χιστε? δομ??.

Το θε?ρημα κατηγορικ?τητα? του Μ?ρλευ, που αποδε?χθηκε απ? τον Μ?ρλευ το 1965, εκφρ?ζει ?τι αν μια θεωρ?α πρ?του βαθμο? σε μια αριθμ?σιμη γλ?σσα ε?ναι κατηγορικ? με μη μετρ?σιμη πληθικ?τητα, δηλαδ? ?λα τα μοντ?λα αυτ?? τη? πληθικ?τητα? ε?ναι ισομορφικ?, τ?τε ε?ναι κατηγορικ? σε ?λε? τη? μη μετρ?σιμε? πληθικ?τητε?.

Μια προφαν?? συν?πεια τη? υπ?θεση? του συνεχο?? ε?ναι ?τι μια πλ?ρη? θεωρ?α με λιγ?τερο απ? συνεχ?? πολλ? μη ισομορφικ? αριθμ?σιμα μοντ?λα μπορε? να ?χει μ?χρι αριθμ?σιμο αριθμ? μοντ?λων. Η εικασ?α του Β?τ, λ?ει ?τι αυτ? ε?ναι αληθ?? ακ?μα και ανεξ?ρτητα απ? την υπ?θεση του συνεχο??. Πολλ?? υποπεριπτ?σει? τη? εικασ?α? αυτ?? ?χουν αποδειχθε?.

Θεωρ?α αναδρομ??

Η Θεωρ?α αναδρομ??, ? θεωρ?α υπολογισιμ?τητα?, μελετ? τι? ιδι?τητε? των υπολογ?σιμων συναρτ?σεων, και του? βαθμο?? Το?ρινγκ, που διαιρο?ν τι? μη-υπολογ?σιμε? συναρτ?σει? σε σ?νολα που ?χουν το ?διο επ?πεδο μη-υπολογισιμ?τητα?. Η θεωρ?α αναδρομ?? επ?ση? περι?χει τη μελ?τη τη? γενικ?? υπολογισιμ?τητα? και ορισιμ?τητα?. Αναπτ?χθηκε απ? την εργασ?α των Αλ?νζο Τσερτ? και ?λαν Το?ρινγκ στη δεκαετ?α του 1930, η οπο?α επεκτ?θηκε σημαντικ? απ? τον Κλ?ινι και τον Ποστ τη δεκαετ?α του 1940.

Η κλασσικ? θεωρ?α αναδρομ?? εστι?ζει στην υπολογισιμ?τητα των συναρτ?σεων απ? φυσικο?? αριθμο?? σε φυσικο?? αριθμο??. Τα βασικ? αποτελ?σματα θεμελι?νουν μια ε?ρωστη κλ?ση απ? υπολογ?σιμε? συναρτ?σει? με πολλο?? ανεξ?ρτητου? και ισοδ?ναμου? χαρακτηρισμο??, με μηχαν?? Το?ρινγκ, με λογισμ? λ?μδα, και ?λλα συστ?ματα. Πιο προχωρημ?να αποτελ?σματα αφορο?ν την δομ? των βαθμ?ν Το?ρινγκ και το πλ?γμα των αναδρομικ? αριθμ?σιμων συν?λων.

Η γενικευμ?νη θεωρ?α αναδρομ?? επεκτε?νει τι? ιδ?ε? τη? θεωρ?α? αναδρομ?? σε υπολογισμο?? που δεν ε?ναι πλ?ον απαρα?τητα πεπερασμ?νοι. Περιλαμβ?νει τη μελ?τη τη? υπολογισιμ?τητα? σε υψηλ?τερου? τ?που? αλλ? και σε περιοχ?? ?πω? η υπεραριθμητικ? θεωρ?α και η θεωρ?α αναδρομ?? ?λφα.

Η σ?γχρονη ?ρευνα στη θεωρ?α αναδρομ?? περιλαμβ?νει τη μελ?τη εφαρμογ?ν ?πω? η αλγοριθμικ? τυχαι?τητα και θεωρ?α υπολογ?σιμων μοντ?λων, καθ?? και ν?α αποτελ?σματα στην αμιγ? θεωρ?α αναδρομ??.

Αλγοριθμικ? μη επιλ?σιμα προβλ?ματα

?να σημαντικ? υποπεδ?ο τη? θεωρ?α? αναδρομ?? μελετ? την αλγοριθμικ? μη επιλυσιμ?τητα. ?να πρ?βλημα απ?φαση? ε?ναι αλγοριθμικ? ?λυτο αν δεν υπ?ρχει υπολογ?σιμη συν?ρτηση η οπο?α, για οποιαδ?ποτε ?κφανση του προβλ?ματο?, επιστρ?φει τη σωστ? απ?φαση. Τα αρχικ? αποτελ?σματα για την μη επ?λυση, ανεπτυγμ?να ανεξ?ρτητα απ? του? Τσερτ? και Το?ρινγκ το 1936, ?δειξαν ?τι το γενικ? πρ?βλημα απ?φαση? (Entscheidungsproblem) ε?ναι μη επιλ?σιμο αλγοριθμικ?. Ο Το?ρινγκ το απ?δειξε δε?χνοντα? τη μη επιλυσιμ?τητα του προβλ?ματο? τερματισμο?, αποτ?λεσμα που ε?χε τερ?στιε? επιπτ?σει? τ?σο στη θεωρ?α αναδρομ?? ?σο και στην επιστ?μη υπολογιστ?ν

Υπ?ρχουν πολλ? γνωστ? παραδε?γματα μη αποφασ?σιμων προβλημ?των απ? τα συν?θη μαθηματικ?. Το πρ?βλημα λ?ξη? για ομ?δε? αποδε?χθηκε μη επιλ?σιμο αλγοριθμικ? απ? τον Ν?βικοβ το 1955 και ανεξ?ρτητα απ? τον Μπουν το 1959. Το πρ?βλημα του εργατικο? κ?στορα, διατυπωμ?νο απ? τον Ραντ? το 1962, ε?ναι ?λλο ?να γνωστ? παρ?δειγμα.

Το δ?κατο πρ?βλημα του Χ?λμπερτ ζητο?σε ?ναν αλγ?ριθμο που αποφασ?ζει αν μια πολυμεταβλητ? πολυωνυμικ? εξ?σωση με ακ?ραιου? συντελεστ?? ?χει ακ?ραια λ?ση. Περιορισμ?νη πρ?οδο? σ' αυτ? επιτε?χθηκε απ? την Τζο?λια Ρ?μπινσον, τον Μ?ρτιν Ντ?ιβι? και την Χ?λαρι Πο?τναμ. Η αλγοριθμικ? μη επιλυσιμ?τητα του προβλ?ματο? αποδε?χθηκε τελικ? απ? τον Γιο?ρι Ματιγιασ?βιτ? το 1970.

Θεωρ?α αποδε?ξεων και κατασκευαστικ? μαθηματικ?

Θεωρ?α αποδε?ξεων ε?ναι η μελ?τη τυπικ?ν αποδε?ξεων σε δι?φορα συστ?ματα λογικ?? αναγωγ??. Οι αποδε?ξει? αυτ?? αναπαριστ?νται σαν τυπικ?? μαθηματικ?? οντ?τητε?, διευκολ?νοντα? την αν?λυσ? του? με μαθηματικ?? τεχνικ??. Αρκετ? συμπερασματικ? συστ?ματα εξετ?ζονται συν?θω?, ?πω? το συμπερασματικ? σ?στημα Χ?λμπερτ, συστ?ματα φυσικ?? παραγωγ?? και ο λογισμ?? ακολουθητ?ν που αναπτ?χθηκε απ? τον Γκ?ντζεν.

Η μελ?τη των κατασκευαστικ?ν μαθηματικ?ν, στο πλα?σιο τη? μαθηματικ?? λογικ??, περιλαμβ?νει τη μελ?τη συστημ?των σε μη κλασσικ?? λογικ?? ?πω? η διαισθητικ? λογικ?, ?πω? και η μελ?τη κατηγορηματικ?ν συστημ?των. Απ? του? αρχικο?? υποστηρικτ?? τη? κατηγορηματικ?τητα? ?ταν ο Χ?ρμαν Β?ιλ, που ?δειξε ?τι ε?ναι δυνατ? να αναπτυχθε? ?να μεγ?λο μ?ρο? τη? πραγματικ?? αν?λυση? μ?νο με κατηγορηματικ?? μεθ?δου? (1918).

Δεδομ?νου ?τι οι αποδε?ξει? ε?ναι εντελ?? πεπερασμ?νε? εν? η αλ?θεια σε μια δομ? ?χι, συνηθ?ζεται τα κατασκευαστικ? μαθηματικ? να δ?νουν ?μφαση στην αποδειξιμ?τητα. Η σχ?ση μεταξ? αποδειξιμ?τητα? στα κλασσικ? (μη κατασκευαστικ?) συστ?ματα και αποδειξιμ?τητα? σε διαισθητικ? (? κατασκευαστικ? αντ?στοιχα) συστ?ματα, ε?ναι ειδικο? ενδιαφ?ροντο?. Αποτελ?σματα ?πω? η αρνητικ? μετ?φραση Γκ?ντελ-Γκ?τζεν δε?χνουν ?τι ε?ναι δυνατ? να μεταφραστε? η κλασσικ? λογικ? σε διαισθητικ? λογικ?, επιτρ?ποντα? κ?ποιε? ιδι?τητε? τη? διαισθητικ?? λογικ?? να μεταφερθο?ν σε κλασσικ?? αποδε?ξει?.

Σχ?ση με την επιστ?μη υπολογιστ?ν

Υπ?ρχει μεγ?λη σχ?ση μεταξ? τη? μαθηματικ?? λογικ?? και τη? επιστ?μη? υπολογιστ?ν. Αρχικο? πρωτοπ?ροι τη? επιστ?μη? υπολογιστ?ν, ?πω? ο ?λαν Το?ρινγκ, ?ταν επ?ση? μαθηματικο? και λογικο?.

Η μελ?τη τη? θεωρ?α? υπολογισιμ?τητα? στην επιστ?μη υπολογιστ?ν σχετ?ζεται στεν? με τη μελ?τη τη? υπολογισιμ?τητα? στη μαθηματικ? λογικ?. Διαφ?ρουν ?μω? ω? προ? την ?μφαση. Οι επιστ?μονε? υπολογιστ?ν συχν? εστι?ζουν σε πραγματικ?? γλ?σσε? προγραμματισμο? και την εφικτ? υπολογισιμ?τητα (feasible computability), εν? οι ερευνητ?? στη μαθηματικ? λογικ? συχν? εστι?ζουν στην υπολογισιμ?τητα ω? θεωρητικ? ?ννοια, και στη μη-υπολογισιμ?τητα.

Η μελ?τη τη? σημασιολογ?α? (semantics) γλωσσ?ν προγραμματισμο? σχετ?ζεται με την τροπικ? λογικ? (modal logic), ?πω? και την τυπικ? επαλ?θευση (formal verification) και πιο συγκεκριμ?να τον ?λεγχο μοντ?λων (model checking). Ο ισομορφισμ?? Κ?ρρυ-Χ?ουαρντ μεταξ? αποδε?ξεων και προγραμμ?των σχετ?ζεται με τη θεωρ?α αποδε?ξεων. Η ενορατικ? λογικ? και η γραμμικ? λογικ? ε?ναι σημαντικ?? σ' αυτ?. Λογισμο? ?πω? ο λ?μδα λογισμ?? και η συνδυαστικ? λογικ? (combinatory logic) μελετ?νται τελευτα?α ω? ιδεατ?? γλ?σσε? προγραμματισμο?.

Η επιστ?μη υπολογιστ?ν συμβ?λλει ακ?μα στα μαθηματικ? με την αν?πτυξη τεχνικ?ν για τον αυτ?ματο ?λεγχο ? και ε?ρεση αποδε?ξεων, ?πω? η αυτοματοποιημ?νη απ?δειξη θεωρημ?των (automated theorem proving) και ο λογικ?? προγραμματισμ??.

Σημαντικ? αποτελ?σματα

• Το θε?ρημα Λ?βενχαιμ-Σκ?λεμ (1919) ?δειξε ?τι αν ?να σ?νολο απ? προτ?σει? σε μια μετρ?σιμη γλ?σσα πρ?του βαθμο? ?χει ?να ?πειρο μοντ?λο, τ?τε ?χει τουλ?χιστον ?να μοντ?λο απ? κ?θε ?πειρη πληθικ?τητα (infinite cardinality).
• Το θε?ρημα πληρ?τητα? του Γκ?ντελ (1929) εδρα?ωσε την ισοδυναμ?α μεταξ? συντακτικ?ν και εννοιολογικ?ν ορισμ?ν με λογικ? σημασ?α στη λογικ? πρ?του βαθμο?.
• Τα Θεωρ?ματα Μη-Πληρ?τητα? του Γκ?ντελ (1931) ?δειξε ?τι καν?να αρκετ? ισχυρ? τυπικ? σ?στημα δεν μπορε? να αποδε?ξει την συν?πεια του εαυτο? του.
• Η μη ?παρξη αλγοριθμικ?? λ?ση? του προβλ?ματο? απ?φαση? (Entscheidungsproblem) του Ντ?βιντ Χ?λμπερτ, που δε?χθηκε ανεξ?ρτητα απ? τον ?λαν Το?ρινγκ και τον Αλ?νζο Τσερτ? το 1936, ?δειξε ?τι δεν υπ?ρχει πρ?γραμμα υπολογιστ? που μπορε? να αποφασ?σει σωστ? αν κ?ποια αυθα?ρετη μαθηματικ? πρ?ταση ε?ναι αληθ??.
• Η λογικ? ανεξαρτησ?α τη? υπ?θεση? του συνεχο?? (continuum hypothesis) τη? Ζερμ?λο-Φρ?νκελ θεωρ?α? συν?λων (ZFC) ?δειξε ?τι μια στοιχει?δει? απ?δειξη ? ανταπ?δειξη τη? υπ?θεση? αυτ?? ε?ναι αδ?νατη. Το γεγον?? ?τι η υπ?θεση του συνεχο?? ε?ναι συνεπ?? με τη ZFC (αν η ZFC ε?ναι συνεπ?? απ? μ?νη τη?) αποδε?χθηκε απ? τον Κουρτ Γκ?ντελ το 1940. Το γεγον?? ?τι η ?ρνηση τη? υπ?θεση? του συνεχο?? ε?ναι συνεπ?? με τη ZFC (αν η ZFC ε?ναι συνεπ??) αποδε?χθηκε απ? τον Πωλ Κο?ν το 1963.
• Η μη ?παρξη αλγοριθμικ?? λ?ση? για το δ?κατο πρ?βλημα του Χ?λμπερτ, που δε?χθηκε απ? τον Γιο?ρι Ματιγι?σεβιτ? το 1970, ?δειξε ?τι δεν ε?ναι δυνατ? για οποιοδ?ποτε πρ?γραμμα υπολογιστ? να αποφασ?σει σωστ? αν πολυ?νυμα πολλ?ν μεταβλητ?ν με ακ?ραιου? συντελεστ?? ?χουν ακ?ραιε? λ?σει?.

Αναφορ??

• Andrews, Peter B., 2002. An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof, 2nd ed. Kluwer Academic Publishers.
• Barwise, Jon, ed. (1977) Handbook of Mathematical Logic, Amsterdam: North-Holland. ISBN 0-444-86388-5
• George Boolos, John Burgess, and Richard Jeffrey (2002) Computability and Logic, 4th ed. Cambridge University Press. ISBN 0-521-00758-5.
• Enderton, Herbert (2002) A mathematical introduction to logic, 2nd ed. Academic Press.
• Hamilton, A. G. (1988) Logic for Mathematicians Cambridge University Press.
• Wilfrid Hodges, 1997. A Shorter Model Theory. Cambridge University Press.
• Mendelson, Elliott (1997) Introduction to Mathematical Logic, 4th ed. Chapman & Hall. ISBN 0-412-80830-7
• A. S. Troelstra & H. Schwichtenberg (2000) Basic Proof Theory, 2nd. ed. (Cambridge Tracts in Theoretical Computer Science). Cambridge University Press. ISBN 0-521-77911-1.
• John L. Bell & Alan B. Slomson (1969) Models and Ultraproducts: An Introduction, North-Holland (re-printed in 2006 by Dover publications). ISBN 0-486-44979-3.

Εξωτερικο? σ?νδεσμοι

• Mathematical Logic around the world
• Polyvalued logic Αρχειοθετ?θηκε 2025-08-14 στο Wayback Machine.
• forall x: an introduction to formal logic, by P.D. Magnus, is a free textbook.
• Detlovs, Vilnis, and Podnieks, Karlis (University of Latvia) Introduction to Mathematical Logic. A hyper-textbook.
• Stanford Encyclopedia of Philosophy: Classical Logic -- by Stewart Shapiro.
• Stanford Encyclopedia of Philosophy: First-order Model Theory -- by Wilfred Hodges.