Τι είναι η μαθηματική λογική

Περίληψη

Το μάθημα αυτό οριοθετεί το αντικείμενο της μαθηματικής λογικής: όχι την αλήθεια των επιμέρους αποφάνσεων, που ανήκει σε κάθε επιστήμη, αλλά τη μορφή των συλλογισμών και την εγκυρότητα, δηλαδή τη σχέση ανάμεσα στις υποθέσεις και στο συμπέρασμα που εγγυάται ότι η αλήθεια των πρώτων περνά στο δεύτερο. Ορίζει την πρόταση, το επιχείρημα, την υπόθεση, το συμπέρασμα, τη μορφή και το αντιπαράδειγμα· διακρίνει την εγκυρότητα από την αλήθεια με έγκυρα επιχειρήματα με ψευδές συμπέρασμα και άκυρα επιχειρήματα με αληθές συμπέρασμα· δείχνει γιατί η φυσική γλώσσα, αμφίσημη και ικανή να μιλά για τον εαυτό της, δεν αρκεί για να μελετηθεί αυστηρά η εγκυρότητα, και θεμελιώνει τη διάκριση ανάμεσα στη γλώσσα-αντικείμενο και στη μεταγλώσσα, που διέπει ολόκληρο τον κύκλο μαθημάτων. Εκθέτει έπειτα, με τις παραδοχές τους ρητά διατυπωμένες και με τις αποδείξεις τους, τα παράδοξα του ψεύτη, του Μπέρι και του κουρέα, καθώς και το παράδοξο του Ράσελ, που ο κουρέας προαναγγέλλει, και εξηγεί πώς μια τυπική γλώσσα τα αποφεύγει ή τα μετατρέπει σε θεωρήματα. Κλείνει με τους τέσσερις πυλώνες της μαθηματικής λογικής και με τον χάρτη του κύκλου μαθημάτων.

Μαθησιακοί στόχοι

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

Τι μελετά η λογική

Κάθε γνώση που δεν αποκτάται με άμεση παρατήρηση αποκτάται με συλλογισμό: από ορισμένους ισχυρισμούς που γίνονται δεκτοί περνάμε σε έναν άλλον που έπεται από αυτούς. Στη γεωμετρία, όποιος ξέρει ότι οι γωνίες ενός τριγώνου έχουν άθροισμα δύο ορθές συμπεραίνει ότι κανένα τρίγωνο δεν έχει δύο αμβλείες γωνίες· στην ιατρική, όποιος ξέρει ότι μια ορισμένη ασθένεια προκαλεί πυρετό, και ότι το πρόσωπο που εξετάζεται δεν έχει πυρετό, αποκλείει αυτή την ασθένεια. Η λογική είναι ο κλάδος που μελετά πότε αυτό το πέρασμα είναι θεμιτό, και η μαθηματική λογική είναι εκείνη που το μελετά με τις μεθόδους των μαθηματικών: ορίζοντας με ακρίβεια τα αντικείμενά της, που είναι γλώσσες, τύποι και παραγωγές, και αποδεικνύοντας θεωρήματα γι' αυτά.

Για να διατυπώσουμε με ακρίβεια τι μελετά, πρέπει πρώτα να καθορίσουμε το λεξιλόγιο. Μια πρόταση, με τη λογική σημασία της λέξης, είναι μια δηλωτική πρόταση για την οποία έχει νόημα να πούμε ότι είναι αληθής ή ότι είναι ψευδής: η «ο $7$ είναι πρώτος αριθμός» είναι αληθής πρόταση· η «κάθε άρτιος αριθμός είναι μεγαλύτερος από το $5$ », ψευδής πρόταση. Αντίθετα, δεν είναι προτάσεις με αυτή τη σημασία οι ερωτήσεις («τι ώρα είναι;»), οι εντολές («κλείσε την πόρτα») ούτε οι εκφράσεις με ελεύθερες μεταβλητές, όπως η «ο $x$ είναι άρτιος», της οποίας η τιμή εξαρτάται από το τι δηλώνει το $x$ .

Ένα επιχείρημα είναι μια λίστα προτάσεων, οι υποθέσεις, μαζί με μια άλλη πρόταση, το συμπέρασμα, που παρουσιάζεται ως συνέπεια εκείνων. Οι υποθέσεις μπορεί να είναι οποιεσδήποτε προτάσεις: αληθείς, ψευδείς, γνωστές ή απλές εικασίες· το μόνο που τις ξεχωρίζει είναι η θέση που κατέχουν στο επιχείρημα. Θα γράφουμε τα επιχειρήματα με τις υποθέσεις σε διαδοχικές γραμμές και το συμπέρασμα με τη λέξη «επομένως» μπροστά του:

ΠαράδειγμαΈνα επιχείρημα

Αν ένας αριθμός είναι πολλαπλάσιο του $4$ , είναι άρτιος. Ο αριθμός $28$ είναι πολλαπλάσιο του $4$ . Επομένως, ο $28$ είναι άρτιος.

Οι υποθέσεις του είναι «αν ένας αριθμός είναι πολλαπλάσιο του $4$ , είναι άρτιος» και «ο $28$ είναι πολλαπλάσιο του $4$ »· το συμπέρασμά του, «ο $28$ είναι άρτιος».

Η λογική δεν είναι θεωρία της αλήθειας

Αν αυτό ισχύει, η λογική δεν έχει ως έργο να εξακριβώνει αν οι υποθέσεις ενός επιχειρήματος είναι αληθείς. Το αν ο $28$ είναι πολλαπλάσιο του $4$ το αποφασίζει η αριθμητική· το αν ένα πρόσωπο έχει πυρετό, το θερμόμετρο· το αν μια μάχη έγινε σε ορισμένο έτος, η ιστορία. Ούτε της αναλογεί να ορίσει τι είναι η αλήθεια, ζήτημα που ανήκει στη φιλοσοφία. Η λογική δέχεται ότι οι προτάσεις έχουν μια τιμή αλήθειας, όποια κι αν είναι, και μελετά πώς σχετίζονται μεταξύ τους αυτές οι τιμές: ειδικότερα, πότε η αλήθεια κάποιων προτάσεων επιβάλλει την αλήθεια μιας άλλης. Με άλλα λόγια, η λογική δεν είναι θεωρία της αλήθειας, αλλά θεωρία της μετάδοσης της αλήθειας.

Όμως αυτό που μεταδίδει την αλήθεια δεν εξαρτάται από το θέμα του επιχειρήματος, αλλά από τη δομή του. Ας συγκριθεί το προηγούμενο επιχείρημα με το εξής: «αν ένα ζώο είναι θηλαστικό, αναπνέει αέρα· η φάλαινα είναι θηλαστικό· επομένως, η φάλαινα αναπνέει αέρα». Και τα δύο έχουν την ίδια μορφή: «αν κάτι είναι $A$ , είναι $B$ · το $c$ είναι $A$ · επομένως, το $c$ είναι $B$ ». Μορφή ενός επιχειρήματος είναι ό,τι απομένει όταν αντικαταστήσουμε τους μη λογικούς όρους του (αριθμούς, ζώα, ιδιότητες) με γράμματα, διατηρώντας τις λογικές λέξεις: «όχι», «και», «ή», «αν… τότε», «κάθε», «κάποιος». Κάθε επιχείρημα που προκύπτει από μια μορφή όταν δώσουμε περιεχόμενο στα γράμματά της είναι ένα στιγμιότυπο της μορφής.

Μια μορφή είναι έγκυρη όταν κανένα από τα στιγμιότυπά της δεν έχει όλες τις υποθέσεις αληθείς και το συμπέρασμα ψευδές· ένα επιχείρημα είναι έγκυρο όταν η μορφή του είναι έγκυρη. Ένα στιγμιότυπο με αληθείς υποθέσεις και ψευδές συμπέρασμα λέγεται αντιπαράδειγμα της μορφής· από όπου μια μορφή είναι άκυρη ακριβώς όταν έχει αντιπαράδειγμα.

Στις αποδείξεις αυτού του μαθήματος θα χρησιμοποιούμε μια στενογραφία των ελληνικών: το $V(A)$ συντομεύει το «η $A$ είναι αληθής» και το $F(A)$ το «η $A$ είναι ψευδής»· το $\neg$ συντομεύει το «όχι», το $\wedge$ το «και», το $\vee$ το «ή», το $\Rightarrow$ το «αν… τότε» και το $\Leftrightarrow$ το «αν και μόνο αν»· το $\forall$ διαβάζεται «για κάθε» και το $\exists$ «υπάρχει». Τα σύμβολα αυτά είναι εδώ απλές συντομογραφίες λέξεων της μεταγλώσσας, και τα διπλά βέλη προορίζονται σε όλο τον κύκλο μαθημάτων γι' αυτή τη χρήση. Στο επόμενο μάθημα θα εμφανιστούν τα σύμβολα με μία γραμμή, $\rightarrow$ και $\leftrightarrow$ , μαζί με τα $\neg$ , $\wedge$ και $\vee$ , ως συντομογραφίες μιας τυπικής γλώσσας, με νόημα που ο κύκλος μαθημάτων θα καθορίσει με ακρίβεια· η διαφορά στη χάραξη των βελών θα υπενθυμίζει σε ποιο επίπεδο μιλάμε.

ΠρότασηΤι εγγυάται η εγκυρότητα

Αν ένα επιχείρημα είναι έγκυρο και όλες οι υποθέσεις του είναι αληθείς, το συμπέρασμά του είναι αληθές. Κατά συνέπεια, αν ένα έγκυρο επιχείρημα έχει ψευδές συμπέρασμα, κάποια από τις υποθέσεις του είναι ψευδής.

Απόδειξη

$\dato{p}{V(A_1) \wedge \cdots \wedge V(A_n)}$
Έστω ένα έγκυρο επιχείρημα με υποθέσεις $A_1, \ldots, A_n$ και συμπέρασμα $C$ , και ας υποθέσουμε ότι όλες οι υποθέσεις είναι αληθείς.
$\resaltar{A_1, \ldots, A_n, C}$
Κάθε επιχείρημα είναι στιγμιότυπο της δικής του μορφής: αρκεί να δώσουμε στα γράμματα της μορφής το περιεχόμενο που είχαν στο επιχείρημα.
$\dato{v}{\neg\left( V(A_1) \wedge \cdots \wedge V(A_n) \wedge \resaltar{\neg V(C)} \right)}$
Από τον ορισμό της εγκυρότητας, κανένα στιγμιότυπο αυτής της μορφής δεν έχει τις υποθέσεις αληθείς και το συμπέρασμα ψευδές· ειδικότερα, δεν το έχει το ίδιο το επιχείρημα.
$\resaltar{V(C)}$
Αφού οι υποθέσεις είναι αληθείς, το μόνο που μπορεί να αποτύχει στην αρνημένη σύζευξη είναι η ψευδότητα του συμπεράσματος: το συμπέρασμα είναι αληθές.
$\neg V(C) \Rightarrow \neg\left( V(A_1) \wedge \cdots \wedge V(A_n) \right)$
Αν, αντίθετα, το συμπέρασμα είναι ψευδές, δεν μπορούν να είναι αληθείς όλες οι υποθέσεις, γιατί τότε θα ήταν αληθές και το συμπέρασμα.

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

ΠαράδειγμαΈγκυρο, με ψευδές συμπέρασμα

Κάθε πρώτος αριθμός είναι περιττός. Ο αριθμός $2$ είναι πρώτος. Επομένως, ο $2$ είναι περιττός.

Η μορφή είναι η ίδια με εκείνη του πρώτου επιχειρήματος του μαθήματος, ώστε το επιχείρημα είναι έγκυρο· κι όμως, το συμπέρασμά του είναι ψευδές. Η προηγούμενη πρόταση δείχνει πού βρίσκεται το ελάττωμα: κάποια υπόθεση είναι ψευδής, και πράγματι είναι η πρώτη, γιατί ο $2$ είναι πρώτος και άρτιος. Ένα έγκυρο επιχείρημα δεν παράγει αλήθειες· διατηρεί μόνο όσες δέχεται.

ΠαράδειγμαΆκυρο, με αληθές συμπέρασμα

Αν ένας αριθμός είναι πολλαπλάσιο του $4$ , είναι άρτιος. Ο αριθμός $8$ είναι άρτιος. Επομένως, ο $8$ είναι πολλαπλάσιο του $4$ .

Υποθέσεις και συμπέρασμα είναι αληθή, κι όμως το επιχείρημα είναι άκυρο. Η μορφή του, «αν κάτι είναι $A$ , είναι $B$ · το $c$ είναι $B$ · επομένως, το $c$ είναι $A$ », έχει αντιπαράδειγμα: με τον αριθμό $6$ στη θέση του $8$ , οι υποθέσεις παραμένουν αληθείς («αν ένας αριθμός είναι πολλαπλάσιο του $4$ , είναι άρτιος»· «ο $6$ είναι άρτιος») και το συμπέρασμα, «ο $6$ είναι πολλαπλάσιο του $4$ », είναι ψευδές. Η αλήθεια του αρχικού συμπεράσματος δεν προέρχεται από τις υποθέσεις, αλλά από την αριθμητική: $8 = 4 \cdot 2$ . Αυτή η άκυρη μορφή, συχνή στον καθημερινό συλλογισμό, λέγεται κατάφαση του επομένου.

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

Φυσική γλώσσα και τυπική γλώσσα

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

Λεξική αμφισημία: μια λέξη έχει πολλές σημασίες. Η «άφησε το βιβλίο στο γραφείο» μπορεί να αναφέρεται σε ένα έπιπλο ή σε έναν χώρο εργασίας.
Συντακτική αμφισημία: μια πρόταση δέχεται πολλές δομές. «Το διπλάσιο του τρία συν τέσσερα» μπορεί να είναι $2 \cdot 3 + 4 = 10$ ή $2 \cdot (3 + 4) = 14$ .
Αμφισημία εμβέλειας: δεν είναι σαφές σε ποιο μέρος της πρότασης επιδρά μια λογική λέξη. Η «όλοι οι μαθητές δεν πέρασαν» μπορεί να σημαίνει ότι κανείς δεν πέρασε ή ότι δεν πέρασαν όλοι.
Ασαφείς σύνδεσμοι: το «ή» άλλοτε επιτρέπει να ισχύουν και οι δύο εναλλακτικές («ζητείται πτυχίο ή εμπειρία») και άλλοτε το αποκλείει («καφέ ή τσάι»)· το «αν… τότε» άλλοτε εκφράζει αιτία, άλλοτε κανόνα, άλλοτε απλή διαδοχή.

Στην αμφισημία προστίθεται ένα βαθύτερο γνώρισμα: η φυσική γλώσσα μπορεί να μιλά για τον εαυτό της. Περιέχει τις λέξεις «πρόταση», «αληθής» και «ορίζω», και με αυτές μπορεί να σχηματίσει προτάσεις που αναφέρονται στον εαυτό τους, όπως η «αυτή η πρόταση έχει έξι λέξεις». Αυτή η αυτοαναφορά είναι, γενικά, αβλαβής· όμως, όπως θα φανεί, σε συνδυασμό με την έννοια της αλήθειας παράγει προτάσεις που δεν μπορούν να είναι ούτε αληθείς ούτε ψευδείς.

Μια τυπική γλώσσα σχεδιάζεται για να εξαλείψει και τις δύο πηγές δυσκολίας. Ορίζεται ένα αλφάβητο, μια συλλογή συμβόλων, και ορισμένοι κανόνες σχηματισμού που λένε, χωρίς να αφήνουν περιθώριο ερμηνείας, ποιες ακολουθίες συμβόλων είναι καλά σχηματισμένες εκφράσεις· η σημασία κάθε έκφρασης καθορίζεται έπειτα με εξίσου ακριβείς ορισμούς. Έτσι, το ερώτημα αν μια ακολουθία συμβόλων ανήκει στη γλώσσα λύνεται μηχανικά, ελέγχοντας κανόνες, και κάθε έκφραση διαβάζεται με έναν μόνο τρόπο. Η γλώσσα αυτού του κύκλου μαθημάτων, που την κατασκευάζει το μάθημα για τη γλώσσα της προτασιακής λογικής, έχει αλφάβητο μόνο δύο συμβόλων, τον κύκλο $\sigO$ και τον δίσκο $\sigI$ , και έναν μόνο κανόνα σχηματισμού.

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

Γλώσσα-αντικείμενο και μεταγλώσσα

Για να μελετήσουμε μια γλώσσα πρέπει να μιλήσουμε γι' αυτήν, και για να μιλήσουμε γι' αυτήν χρειαζόμαστε μια άλλη γλώσσα. Η γλώσσα-αντικείμενο είναι η γλώσσα που μελετάμε· η μεταγλώσσα είναι η γλώσσα με την οποία τη μελετάμε. Σε μια γραμματική της λατινικής γραμμένη στα ελληνικά, τα λατινικά είναι η γλώσσα-αντικείμενο και τα ελληνικά η μεταγλώσσα. Σε αυτόν τον κύκλο μαθημάτων, γλώσσα-αντικείμενο θα είναι η τυπική γλώσσα των κύκλων και των δίσκων, και μεταγλώσσα θα είναι τα ελληνικά, εμπλουτισμένα με μαθηματικά σύμβολα και με ελληνικά γράμματα, $\varphi$ , $\psi$ , που θα δηλώνουν οποιουσδήποτε τύπους της γλώσσας-αντικειμένου χωρίς να ανήκουν σε αυτήν.

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

Μια στοιχειώδης μορφή της διάκρισης είναι εκείνη που χωρίζει τη χρήση μιας έκφρασης από την αναφορά της. Στην «η Ρώμη είναι πόλη» χρησιμοποιούμε τη λέξη για να μιλήσουμε για την πόλη· στην «η “Ρώμη” έχει τέσσερα γράμματα» αναφέρουμε τη λέξη, και τα εισαγωγικά το δείχνουν: η πρόταση μιλά για τη λέξη, όχι για την πόλη. Η σύγχυση των δύο παράγει παράλογες αποφάνσεις, όπως η «η Ρώμη έχει τέσσερα γράμματα», ή σοφιστικά επιχειρήματα, όπως το «η Ρώμη είναι πόλη· η “Ρώμη” είναι λέξη τεσσάρων γραμμάτων· επομένως, μια πόλη είναι λέξη τεσσάρων γραμμάτων».

ΠαράδειγμαΤρία επίπεδα

Ας πάρουμε ως γλώσσα-αντικείμενο τα λατινικά. Η πρόταση «Roma aeterna est» ανήκει στη γλώσσα-αντικείμενο. Η πρόταση «η “Roma aeterna est” έχει τρεις λέξεις» ανήκει στη μεταγλώσσα, τα ελληνικά, και είναι αληθής. Η πρόταση «η προηγούμενη πρόταση είναι γραμμένη στα ελληνικά» μιλά για μια πρόταση της μεταγλώσσας: ανήκει σε ένα τρίτο επίπεδο, τη μεταγλώσσα της μεταγλώσσας, αν και είναι γραμμένη στην ίδια γλώσσα. Τίποτα δεν εμποδίζει μια ίδια γλώσσα να υπηρετεί σε πολλά επίπεδα· αυτό που έχει σημασία είναι να μη χάνουμε από τα μάτια μας για τι μιλάμε.

Τα παράδοξα της γλώσσας

Μια αντίφαση είναι ένας ισχυρισμός μαζί με την άρνησή του, όπως η $V(A) \wedge \neg V(A)$ . Ένα παράδοξο είναι ένας συλλογισμός που, ξεκινώντας από παραδοχές που φαίνονται αποδεκτές και προχωρώντας με βήματα που φαίνονται έγκυρα, καταλήγει σε αντίφαση. Από την πρόταση «Τι εγγυάται η εγκυρότητα», αν τα βήματα είναι πράγματι έγκυρα, κάποια παραδοχή είναι ψευδής: η λύση ενός παραδόξου συνίσταται στο να βρούμε ποια. Δεν πρέπει να συγχέουμε το παράδοξο με την αμφισημία, που είναι μόνο η πολλαπλότητα των αναγνώσεων, ούτε με το απλώς εκπληκτικό.

Ο ψεύτης

Το αρχαιότερο παράδοξο αυτού του είδους αποδίδεται στον Ευβουλίδη τον Μιλήσιο, τον 4ο αιώνα π.Χ. Στην ακριβή του μορφή δεν μιλά για ψέμα, που προϋποθέτει την πρόθεση της εξαπάτησης, αλλά για ψευδότητα: έστω $m$ η πρόταση «η πρόταση $m$ είναι ψευδής». Για να φτάσουμε στην αντίφαση αρκούν δύο παραδοχές, που αξίζει να γραφτούν ρητά.

Διτιμία (B): κάθε πρόταση είναι αληθής ή ψευδής, και όχι και τα δύο· το να είναι ψευδής ισοδυναμεί με το να μην είναι αληθής.
Σχήμα της αλήθειας (T): μια πρόταση είναι αληθής αν και μόνο αν αυτό που λέει ισχύει. Για παράδειγμα, η «το χιόνι είναι λευκό» είναι αληθής αν και μόνο αν το χιόνι είναι λευκό.

ΘεώρημαΤο παράδοξο του ψεύτη

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

Απόδειξη

$\dato{B}{F(m) \Leftrightarrow \neg V(m)}$
Από τη διτιμία, η $m$ είναι αληθής ή ψευδής, και όχι και τα δύο: το να είναι ψευδής είναι το να μην είναι αληθής.
$\dato{T}{V(m) \Leftrightarrow \resaltar{F(m)}}$
Αυτό που λέει η $m$ είναι ότι η $m$ είναι ψευδής. Από το σχήμα της αλήθειας, η $m$ είναι αληθής ακριβώς όταν αυτό που λέει ισχύει.
$V(m) \Leftrightarrow \resaltar{\neg V(m)}$
Αν συνδέσουμε τις δύο ισοδυναμίες, η αλήθεια της $m$ ισοδυναμεί με την ίδια της την άρνηση.
$V(m) \Rightarrow \neg V(m), \quad \resaltar{\neg V(m)}$
Αν η $m$ ήταν αληθής, από την ισοδυναμία διαβασμένη από αριστερά προς τα δεξιά δεν θα ήταν: η παραδοχή ανατρέπει τον εαυτό της, και η $m$ δεν είναι αληθής.
$\resaltar{V(m) \wedge \neg V(m)}$
Αλλά τότε, από την ισοδυναμία διαβασμένη από δεξιά προς τα αριστερά, η $m$ είναι αληθής: έχουμε ταυτόχρονα έναν ισχυρισμό και την άρνησή του.

Το θεώρημα δεν λέει ότι η λογική είναι αντιφατική, αλλά ότι οι δύο παραδοχές δεν μπορούν να ισχύουν ταυτόχρονα για μια γλώσσα που περιέχει την πρόταση $m$ . Υπάρχουν, επομένως, τρεις διέξοδοι: να εγκαταλείψουμε τη διτιμία και να δεχτούμε προτάσεις χωρίς τιμή αλήθειας· να περιορίσουμε το σχήμα της αλήθειας· ή να εμποδίσουμε τη γλώσσα να σχηματίσει την πρόταση $m$ . Η τρίτη είναι η διέξοδος του Άλφρεντ Τάρσκι, το 1933: το κατηγόρημα «είναι αληθής» μιας γλώσσας δεν ανήκει σε αυτή τη γλώσσα, αλλά στη μεταγλώσσα της. Σε μια τέτοια γλώσσα, η $m$ δεν είναι καλά σχηματισμένη πρόταση, και το παράδοξο δεν μπορεί να διατυπωθεί.

Το παράδοξο του Μπέρι

Το παράδοξο αυτό, που το δημοσίευσε ο Μπέρτραντ Ράσελ το 1906 και το απέδωσε στον Τζορτζ Μπέρι, βιβλιοθηκάριο της Οξφόρδης, δεν χρησιμοποιεί τη λέξη «αληθής», αλλά τη λέξη «ορίζω». Λέμε ότι μια έκφραση των ελληνικών ορίζει έναν φυσικό αριθμό όταν τον περιγράφει έτσι ώστε να μπορεί να ταυτιστεί χωρίς αμφισημία: η «ο μικρότερος πρώτος αριθμός που είναι μεγαλύτερος από το δέκα» ορίζει τον $11$ . Ας θεωρήσουμε την έκφραση «ο ελάχιστος φυσικός που δεν μπορεί να οριστεί με λιγότερες από είκοσι λέξεις», που πρέπει να διαβαστεί όπως ακριβώς είναι γραμμένη, και ας ονομάσουμε $b$ τον αριθμό που επιχειρεί να ορίσει. Οι φυσικοί αριθμοί, σε αυτόν τον κύκλο μαθημάτων, είναι οι $1, 2, 3, \ldots$

ΘεώρημαΤο παράδοξο του Μπέρι

Αν το λεξιλόγιο των ελληνικών είναι πεπερασμένο και η σχέση «η έκφραση ορίζει τον αριθμό» είναι καλά καθορισμένη, καταλήγουμε σε αντίφαση: ο αριθμός $b$ υπάρχει, και ταυτόχρονα μπορεί και δεν μπορεί να οριστεί με λιγότερες από είκοσι λέξεις. Στην εικόνα, οι σύντομες εκφράσεις στέλνονται στους αριθμούς που ορίζουν, που είναι λίγοι· ο πρώτος αριθμός που μένει ελεύθερος είναι ο $b$ .

Απόδειξη

$\dato{N}{N \leq k + k^2 + \cdots + k^{19}}$
Έστω $k$ το πλήθος των λέξεων του λεξικού. Οι εκφράσεις μίας λέξης είναι το πολύ $k$ · οι εκφράσεις δύο λέξεων, το πολύ $k^2$ · και ούτω καθεξής ως τις εκφράσεις δεκαεννέα λέξεων. Οι εκφράσεις με λιγότερες από είκοσι λέξεις είναι, επομένως, πεπερασμένου πλήθους $N$ .
$\dato{D}{D = \{ d_1, \ldots, d_r \}, \quad r \leq N}$
Κάθε έκφραση ορίζει το πολύ έναν αριθμό. Έστω $D$ το σύνολο των φυσικών που ορίζει κάποια έκφραση με λιγότερες από είκοσι λέξεις: έχει το πολύ $N$ στοιχεία.
$(\exists n \leq N + 1)\,(n \notin D), \quad \resaltar{b \notin D}$
Ανάμεσα στους $N + 1$ αριθμούς $1, 2, \ldots, N + 1$ υπάρχει κάποιος που δεν ανήκει στο $D$ . Αν τους διατρέξουμε με τη σειρά, ο πρώτος που δεν ανήκει στο $D$ είναι ο ελάχιστος φυσικός που δεν μπορεί να οριστεί με λιγότερες από είκοσι λέξεις: όλοι οι προηγούμενοι ανήκουν στο $D$ .
$13 < 20, \quad \resaltar{b \in D}$
Όμως η έκφραση «ο ελάχιστος φυσικός που δεν μπορεί να οριστεί με λιγότερες από είκοσι λέξεις» έχει δεκατρείς λέξεις, και ορίζει ακριβώς τον $b$ .
$\resaltar{b \in D \wedge b \notin D}$
Έχουμε ταυτόχρονα έναν ισχυρισμό και την άρνησή του.

Η συνήθης παρουσίαση, που περιορίζεται να παρατηρήσει ότι η έκφραση έχει λιγότερες από είκοσι λέξεις, παραλείπει το μισό επιχείρημα: ότι ο αριθμός $b$ υπάρχει, πράγμα που απαιτεί το πεπερασμένο του λεξιλογίου και την επιλογή του πρώτου που λείπει. Η παραδοχή που αποτυγχάνει είναι η δεύτερη: το «ορίζω» δεν είναι ακριβής σχέση των ελληνικών, γιατί η έκφραση που ορίζει τον $b$ χρησιμοποιεί την ίδια τη λέξη «ορίζω», και η σημασία της εξαρτάται από το ποιες εκφράσεις μετρούν ως ορισμοί. Σε μια τυπική γλώσσα $L$ μπορεί να γίνει ακριβές τι σημαίνει «ορίσιμος στην $L$ », αλλά αυτή η έννοια εκφράζεται μόνο στη μεταγλώσσα· η έκφραση που ορίζει τον $b$ δεν ανήκει στην $L$ , και η αντίφαση εξαφανίζεται: ο $b$ δεν είναι ορίσιμος στην $L$ με λίγα σύμβολα, αν και είναι ορίσιμος στη μεταγλώσσα.

Ο κουρέας και το σύνολο του Ράσελ

Το παράδοξο του κουρέα το διηγούνται συνήθως έτσι: σε ένα χωριό υπάρχει ένας κουρέας, άνδρας του χωριού, που ξυρίζει όλους τους άνδρες του χωριού που δεν ξυρίζονται μόνοι τους, και μόνο αυτούς. Ξυρίζει ο κουρέας τον εαυτό του; Οι λέξεις «και μόνο αυτούς» είναι ουσιώδεις: ένας κουρέας που θα ξύριζε όλους όσους δεν ξυρίζονται μόνοι τους, χωρίς τον περιορισμό, θα μπορούσε να ξυρίζει και τον εαυτό του χωρίς καμία αντίφαση. Το παράδοξο είναι ειδική περίπτωση ενός γενικού λήμματος, διαγώνιας μορφής, που αξίζει να αποδειχθεί μία φορά για πάντα.

ΛήμμαΤο διαγώνιο λήμμα

Έστω $D$ μια συλλογή αντικειμένων και $R$ μια σχέση ανάμεσά τους, τέτοια ώστε, για κάθε ζεύγος $x$ , $y$ αντικειμένων του $D$ , ο ισχυρισμός $R(x, y)$ να είναι αληθής ή ψευδής. Τότε δεν υπάρχει κανένα αντικείμενο $b$ του $D$ τέτοιο ώστε, για κάθε $x$ του $D$ , να ισχύει $R(b, x)$ αν και μόνο αν δεν ισχύει $R(x, x)$ . Στην εικόνα, κάθε γραμμή είναι ένα αντικείμενο $x$ και κάθε στήλη ένα αντικείμενο $y$ , και ένα τετραγωνάκι είναι γεμάτο όταν ισχύει $R(x, y)$ · η γραμμή που αναζητούμε για το $b$ θα έπρεπε να αντιστρέφει τη διαγώνιο, και γι' αυτό διαφέρει από κάθε γραμμή στο διαγώνιο τετραγωνάκι εκείνης.

Απόδειξη

$\dato{b}{(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)}$
Ας υποθέσουμε ότι υπάρχει ένα τέτοιο $b$ στο $D$ .
$R(b, \resaltar{b}) \Leftrightarrow \neg R(\resaltar{b}, \resaltar{b})$
Η συνθήκη ισχύει για κάθε $x$ του $D$ , και το $b$ είναι ένα από αυτά: μπορούμε να πάρουμε $x = b$ .
$R(b, b) \Rightarrow \resaltar{\neg R(b, b)}$
Αν ισχύει $R(b, b)$ , από την ισοδυναμία δεν ισχύει: αντίφαση.
$\neg R(b, b) \Rightarrow \resaltar{R(b, b)}$
Αν δεν ισχύει $R(b, b)$ , από την ισοδυναμία ισχύει: πάλι αντίφαση.
$\neg (\exists b \in D)\,(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
Αφού μία από τις δύο περιπτώσεις πρέπει να συμβαίνει, η παραδοχή είναι αβάσιμη: δεν υπάρχει τέτοιο $b$ .

ΠόρισμαΟ κουρέας δεν υπάρχει

Σε κανένα χωριό δεν υπάρχει άνδρας του χωριού που να ξυρίζει όλους τους άνδρες του χωριού που δεν ξυρίζονται μόνοι τους, και μόνο αυτούς.

Απόδειξη

$(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
Έστω $D$ η συλλογή των ανδρών του χωριού και $R(x, y)$ η σχέση «ο $x$ ξυρίζει τον $y$ ». Ο κουρέας $b$ είναι άνδρας του χωριού, ώστε ανήκει στο $D$ · το ότι είναι κουρέας όπως ο περιγραφόμενος σημαίνει ότι ξυρίζει κάθε άνδρα του χωριού ακριβώς όταν αυτός ο άνδρας δεν ξυρίζεται μόνος του.
$\resaltar{\neg (\exists b \in D)}\,(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
Από το διαγώνιο λήμμα, κανένας άνδρας του χωριού δεν πληροί αυτή τη συνθήκη: ο περιγραφόμενος κουρέας δεν υπάρχει. Η ιστορία δεν είναι παράδοξο, αλλά η απόδειξη ότι ο πρωταγωνιστής της είναι αδύνατος.

Το συμπέρασμα για τον κουρέα είναι αβλαβές: κανείς δεν είχε ισχυριστεί ότι υπάρχει τέτοιος κουρέας. Δεν συμβαίνει το ίδιο με την εκδοχή του στη θεωρία συνόλων. Το 1902, ο Ράσελ έγραψε στον Γκότλομπ Φρέγκε ότι το σύστημά του, που φιλοδοξούσε να θεμελιώσει την αριθμητική στη λογική, δεχόταν την εξής αρχή της περιγραφής: για κάθε ιδιότητα υπάρχει ένα σύνολο του οποίου τα στοιχεία είναι ακριβώς τα αντικείμενα που την έχουν. Εφαρμοσμένη στην ιδιότητα του να μην ανήκει κάτι στον εαυτό του, η αρχή βεβαιώνει ότι υπάρχει το σύνολο

Z = \{ x : x \notin x \}

ΠόρισμαΤο παράδοξο του Ράσελ

Η αρχή της περιγραφής, χωρίς περιορισμούς, είναι αντιφατική.

Απόδειξη

$\dato{Z}{(\forall x \in D)\,\left( x \in Z \Leftrightarrow x \notin x \right)}$
Έστω $D$ η συλλογή όλων των συνόλων και $R(x, y)$ η σχέση «το $y$ ανήκει στο $x$ ». Η αρχή της περιγραφής, εφαρμοσμένη στην ιδιότητα $x \notin x$ , βεβαιώνει ότι υπάρχει ένα σύνολο $Z$ του οποίου τα στοιχεία είναι τα σύνολα που δεν ανήκουν στον εαυτό τους.
$(\forall x \in D)\,\left( \resaltar{R(Z, x)} \Leftrightarrow \resaltar{\neg R(x, x)} \right)$
Με τη σχέση που επιλέξαμε, η συνθήκη του $Z$ είναι ακριβώς εκείνη του διαγώνιου λήμματος, με το $Z$ στη θέση του $b$ : το $x \in Z$ είναι το $R(Z, x)$ , και το $x \notin x$ είναι το $\neg R(x, x)$ .
$\resaltar{Z \in Z \Leftrightarrow Z \notin Z}$
Το σύνολο $Z$ είναι σύνολο, ώστε ανήκει στο $D$ · από το διαγώνιο λήμμα, τέτοιο $Z$ δεν υπάρχει, και θέτοντας $x = Z$ προκύπτει η αδύνατη ισοδυναμία. Όμως η αρχή βεβαιώνει ότι υπάρχει. Η αρχή συνεπάγεται, επομένως, αντίφαση.

Σε αντίθεση με τον κουρέα, εδώ η ύπαρξη του $Z$ δεν ήταν παραδοχή μιας ιστορίας, αλλά αρχή της θεωρίας. Το παράδοξο του Ράσελ δεν λύνεται με τη δήλωση ότι το $Z$ δεν υπάρχει, αλλά με τη μεταρρύθμιση της θεωρίας: η αξιωματική θεωρία συνόλων του Τσερμέλο, του 1908, επιτρέπει να σχηματίζονται, με μια ιδιότητα, μόνο υποσύνολα ενός ήδη δοσμένου συνόλου, και με αυτόν τον περιορισμό η αντίφαση δεν συνάγεται.

Τι δεν είναι παράδοξο

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

Πώς τα χειρίζεται μια τυπική γλώσσα

Από τα προηγούμενα έπεται ότι μια τυπική γλώσσα δεν αποφεύγει τα παράδοξα ως διά μαγείας, αλλά με δύο ακριβείς τρόπους. Ο πρώτος είναι ότι μπορεί να στερείται τα μέσα που τα παράγουν. Η γλώσσα της προτασιακής λογικής, που κατασκευάζει αυτός ο κύκλος μαθημάτων, δεν έχει προτάσεις που αναφέρονται στον εαυτό τους ούτε κατηγόρημα αλήθειας: σε αυτήν δεν μπορεί να γραφτεί η πρόταση του ψεύτη, και η σημασιολογία της αποδίδει σε κάθε τύπο, σε κάθε αποτίμηση των μεταβλητών, μία μοναδική τιμή αλήθειας. Ο δεύτερος είναι ότι, σε πλουσιότερες γλώσσες, το παράδοξο μετατρέπεται σε θεώρημα: ο συλλογισμός του ψεύτη, γινωμένος με αυστηρότητα, αποδεικνύει ότι η αλήθεια μιας αρκετά εκφραστικής γλώσσας δεν είναι ορίσιμη στην ίδια αυτή γλώσσα (Τάρσκι)· ο συλλογισμός του κουρέα και του Ράσελ αποδεικνύει ότι ορισμένες συλλογές δεν είναι σύνολα· και επιχειρήματα συγγενικά με εκείνο του Μπέρι βρίσκονται στην καρδιά των θεωρημάτων μη πληρότητας του Κουρτ Γκέντελ, του 1931. Έτσι, ό,τι στη φυσική γλώσσα είναι αμηχανία, σε μια τυπική γλώσσα είναι πληροφορία.

Οι τέσσερις πυλώνες της μαθηματικής λογικής

Η μαθηματική λογική γεννήθηκε στα τέλη του 19ου και στις αρχές του 20ού αιώνα, με τον Φρέγκε, τον Πεάνο, τον Ράσελ και τον Ντάβιντ Χίλμπερτ, ως απάντηση σε ένα ακριβές ερώτημα: σε ποια θεμέλια στηρίζονται τα μαθηματικά και αν αυτά τα θεμέλια είναι απαλλαγμένα από αντιφάσεις. Σήμερα διαιρείται σε τέσσερις μεγάλους κλάδους, που διαπλέκονται συνεχώς.

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

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

Ο χάρτης του κύκλου μαθημάτων

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

Γλώσσα: η σύνταξη. Κατασκευάζεται η γλώσσα-αντικείμενο με το αλφάβητο των δύο συμβόλων και τον κανόνα σχηματισμού της, αποδεικνύεται ότι κάθε τύπος διαβάζεται με έναν μόνο τρόπο, μαθαίνουμε να αποδεικνύουμε με επαγωγή και μεταφράζονται στην τυπική γλώσσα αποφάνσεις και επιχειρήματα της φυσικής γλώσσας, με επισήμανση του τι διατηρεί η μετάφραση και τι χάνει.
Συμπερασμός: καθορίζεται ένα σύστημα αξιωμάτων και κανόνων συμπερασμού, και ορίζεται τι σημαίνει ότι ένας τύπος $\varphi$ παράγεται από ένα σύνολο τύπων $\Gamma$ , πράγμα που γράφεται $\Gamma \vdash \varphi$ . Είναι η συντακτική όψη της εγκυρότητας: χειρισμός συμβόλων σύμφωνα με κανόνες, χωρίς να λαμβάνεται υπόψη η σημασία τους.
Σημασιολογία: αποδίδεται σε κάθε τύπο μια τιμή αλήθειας σε κάθε αποτίμηση, και ορίζεται τι σημαίνει ότι ο $\varphi$ είναι συνέπεια του $\Gamma$ , πράγμα που γράφεται $\Gamma \models \varphi$ : κάθε αποτίμηση που κάνει αληθείς τους τύπους του $\Gamma$ κάνει αληθή τον $\varphi$ . Είναι η σημασιολογική όψη της εγκυρότητας, ο ορισμός αυτού του μαθήματος σε ακριβή μορφή.
Μεταθεωρία: αποδεικνύεται ότι οι δύο όψεις συμπίπτουν. Η ορθότητα λέει ότι ό,τι είναι παραγώγιμο είναι συνέπεια, και η πληρότητα ότι κάθε συνέπεια είναι παραγώγιμη. Μελετώνται έπειτα η συμπάγεια και μια μηχανική μέθοδος, η επίλυση, για να αποφασίζεται αν ένα σύνολο τύπων μπορεί να ικανοποιηθεί.

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

Λυμένα προβλήματα

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

Λυμένο πρόβλημα 1Όλα αληθή, κι όμως άκυρο

Να δειχθεί ότι το ακόλουθο επιχείρημα είναι άκυρο, αν και οι υποθέσεις και το συμπέρασμά του είναι αληθή: «κάθε πολλαπλάσιο του $6$ είναι άρτιο· ο αριθμός $12$ είναι άρτιος· επομένως, ο $12$ είναι πολλαπλάσιο του $6$ ».

Λύση

$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(12), \quad S(12)$
Συντομεύουμε το «ο $x$ είναι πολλαπλάσιο του $6$ » με $S(x)$ και το «ο $x$ είναι άρτιος» με $P(x)$ . Οι υποθέσεις και το συμπέρασμα είναι αληθή, γιατί $12 = 6 \cdot 2$ .
$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(\resaltar{c}), \quad S(\resaltar{c})$
Η μορφή προκύπτει αν αντικαταστήσουμε το όνομα $12$ με ένα γράμμα $c$ : δύο υποθέσεις και ένα συμπέρασμα.
$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(\resaltar{4})$
Αναζητούμε ένα στιγμιότυπο με αληθείς υποθέσεις: η πρώτη δεν εξαρτάται από το $c$ , και η δεύτερη ζητά έναν άρτιο αριθμό. Παίρνουμε $c = 4$ .
$\neg S(\resaltar{4})$
Το συμπέρασμα αυτού του στιγμιότυπου είναι ψευδές, γιατί ο $4$ δεν είναι πολλαπλάσιο του $6$ .
$\resaltar{12 = 6 \cdot 2}$
Η μορφή έχει αντιπαράδειγμα: είναι άκυρη, και το επιχείρημα επίσης. Η αλήθεια του συμπεράσματός του προέρχεται από την αριθμητική, όχι από τις υποθέσεις.

Λυμένο πρόβλημα 2Μια αμφισημία εμβέλειας

Έστω $L$ η λίστα των αριθμών $4$ , $6$ , $7$ . Να δειχθεί ότι η πρόταση «όλοι οι αριθμοί του $L$ δεν είναι πρώτοι» έχει δύο αναγνώσεις, και ότι με αυτή τη λίστα η μία είναι αληθής και η άλλη ψευδής.

Λύση

$\dato{a}{\neg Q(4) \wedge \neg Q(6) \wedge \neg Q(7)}$
Συντομεύουμε το «ο $x$ είναι πρώτος» με $Q(x)$ . Πρώτη ανάγνωση: η άρνηση επιδρά σε κάθε αριθμό, και η πρόταση λέει ότι κανένας δεν είναι πρώτος.
$\dato{n}{\neg\left( Q(4) \wedge Q(6) \wedge Q(7) \right)}$
Δεύτερη ανάγνωση: η άρνηση επιδρά σε ολόκληρο τον ισχυρισμό, και η πρόταση λέει ότι δεν είναι όλοι πρώτοι.
$Q(7), \quad \neg\left( \neg Q(4) \wedge \neg Q(6) \wedge \resaltar{\neg Q(7)} \right)$
Αφού ο $7$ είναι πρώτος, ο τελευταίος όρος της πρώτης ανάγνωσης είναι ψευδής, και μαζί του ολόκληρη η σύζευξη: η πρώτη ανάγνωση είναι ψευδής.
$\neg Q(4), \quad \neg\left( \resaltar{Q(4)} \wedge Q(6) \wedge Q(7) \right)$
Αφού ο $4$ δεν είναι πρώτος, η σύζευξη της δεύτερης ανάγνωσης είναι ψευδής, και η άρνησή της αληθής: η δεύτερη ανάγνωση είναι αληθής.
$\resaltar{\neg Q(4) \wedge \neg Q(6) \wedge \neg Q(7)} \Rightarrow \neg\left( Q(4) \wedge Q(6) \wedge Q(7) \right)$
Οι δύο αναγνώσεις δεν είναι ισοδύναμες: η πρώτη συνεπάγεται τη δεύτερη, αλλά όχι αντίστροφα, και αυτή η λίστα το δείχνει. Στα μαθηματικά, η δεύτερη γράφεται «δεν είναι όλοι οι αριθμοί του $L$ πρώτοι», και η πρώτη «κανένας αριθμός του $L$ δεν είναι πρώτος».

Λυμένο πρόβλημα 3Γλώσσα-αντικείμενο και μεταγλώσσα

Ας πάρουμε ως γλώσσα-αντικείμενο τις ακολουθίες των συμβόλων $\sigO$ και $\sigI$ , και ως μεταγλώσσα τα ελληνικά, με ελληνικά γράμματα που δηλώνουν οποιεσδήποτε ακολουθίες. Να ταξινομηθεί καθεμία από τις ακόλουθες εκφράσεις και να αποφασιστεί, όπου έχει νόημα, αν είναι αληθής: (α) $\sigO\sigO\sigI$ · (β) «η $\sigO\sigO\sigI$ έχει τρία σύμβολα»· (γ) «για κάθε ακολουθία $\varphi$ , η ακολουθία $\sigI\varphi$ αρχίζει με δίσκο»· (δ) «η $\sigO\sigO\sigI$ είναι αληθής».

Λύση

$\resaltar{\sigO\sigO\sigI}$
Η έκφραση (α) ανήκει στη γλώσσα-αντικείμενο: είναι ακολουθία συμβόλων, όχι πρόταση των ελληνικών, και δεν είναι ούτε αληθής ούτε ψευδής· γι' αυτήν μιλάμε, αλλά η ίδια δεν ισχυρίζεται τίποτα.
$\sigO \; \sigO \; \sigI \quad (3)$
Η έκφραση (β) είναι πρόταση της μεταγλώσσας που αναφέρει την ακολουθία (α) και μετρά τα σύμβολά της: είναι αληθής.
$\resaltar{\sigI}\varphi$
Η έκφραση (γ) είναι πρόταση της μεταγλώσσας. Το γράμμα $\varphi$ δεν είναι σύμβολο της γλώσσας-αντικειμένου, αλλά μεταβλητή της μεταγλώσσας που διατρέχει τις ακολουθίες της· η πρόταση είναι αληθής, γιατί η $\sigI\varphi$ αρχίζει, εκ κατασκευής, με τον δίσκο.
$v_2 = \sigO\sigO\sigI$
Η έκφραση (δ) ανήκει στη μεταγλώσσα, αλλά δεν έχει ακόμη τιμή αλήθειας: η ακολουθία $\sigO\sigO\sigI$ θα είναι μια μεταβλητή της γλώσσας του κύκλου μαθημάτων, και μια μεταβλητή δεν είναι αληθής ούτε ψευδής από μόνη της, αλλά μόνο όταν μια αποτίμηση, στην ενότητα της σημασιολογίας, της δίνει τιμή. Στο επόμενο μάθημα θα ονομαστεί $v_2$ .

Λυμένο πρόβλημα 4Ο Επιμενίδης δεν είναι ο ψεύτης

Σε έναν πίνακα είναι γραμμένη η πρόταση $e$ , ίσως μαζί με άλλες: «κάθε πρόταση γραμμένη σε αυτόν τον πίνακα είναι ψευδής». Δεχόμενοι τη διτιμία και το σχήμα της αλήθειας, να αποδειχθεί ότι η $e$ είναι ψευδής και ότι στον πίνακα υπάρχει κάποια άλλη αληθής πρόταση· και να συναχθεί ότι παράδοξο υπάρχει ακριβώς όταν καμία άλλη πρόταση του πίνακα δεν είναι αληθής, όπως συμβαίνει αν η $e$ είναι η μόνη.

Λύση

$\dato{T}{V(e) \Leftrightarrow (\forall x \in O)\,F(x)}$
Έστω $O$ το σύνολο των προτάσεων του πίνακα· η $e$ είναι μία από αυτές. Από το σχήμα της αλήθειας, η $e$ είναι αληθής αν και μόνο αν όλες οι προτάσεις του $O$ είναι ψευδείς.
$V(e) \Rightarrow \resaltar{F(e)} \Rightarrow \neg V(e)$
Αν η $e$ ήταν αληθής, όλες οι προτάσεις του $O$ θα ήταν ψευδείς, και η $e$ ανήκει στο $O$ : η $e$ θα ήταν ψευδής, και από τη διτιμία δεν θα ήταν αληθής. Η παραδοχή ανατρέπει τον εαυτό της.
$\resaltar{F(e)}$
Επομένως, η $e$ δεν είναι αληθής· από τη διτιμία, είναι ψευδής.
$(\exists x \in O)\,\left( x \neq e \wedge V(x) \right)$
Από το σχήμα της αλήθειας, το ότι η $e$ είναι ψευδής σημαίνει ότι δεν είναι όλες οι προτάσεις του $O$ ψευδείς: κάποια είναι αληθής, και δεν είναι η $e$ , που είναι ψευδής.
$\neg (\exists x \in O)\,\left( x \neq e \wedge V(x) \right) \Rightarrow \resaltar{V(e) \wedge \neg V(e)}$
Αν στον πίνακα υπάρχει άλλη αληθής πρόταση, όλα είναι συνεπή: η $e$ είναι απλώς ψευδής. Αν, αντίθετα, καμία άλλη δεν είναι αληθής, δεν υπάρχει κανένα $x$ διαφορετικό από την $e$ στο $O$ που να είναι αληθές, και προκύπτει αντίφαση, όπως στον ψεύτη· αυτό συμβαίνει ειδικότερα όταν η $e$ είναι η μόνη πρόταση του πίνακα. Το αν εμφανίζεται το παράδοξο εξαρτάται, επομένως, από ένα εμπειρικό γεγονός: τι είναι γραμμένο στον πίνακα.

Λυμένο πρόβλημα 5Το ετερολογικό

Ένα επίθετο είναι αυτολογικό αν εφαρμόζεται στον εαυτό του (το «ελληνικός» είναι ελληνική λέξη· το «πολυσύλλαβος» είναι πολυσύλλαβο) και ετερολογικό αν όχι (το «μονοσύλλαβος» δεν είναι μονοσύλλαβο· το «αγγλικός» δεν είναι αγγλική λέξη). Να αποδειχθεί ότι, αν το «ετερολογικός» είναι επίθετο και η σχέση «εφαρμόζεται σε» είναι καλά καθορισμένη για όλα τα επίθετα, καταλήγουμε σε αντίφαση· και να αποφασιστεί ποια παραδοχή πρέπει να εγκαταλειφθεί.

Λύση

$\dato{R}{R(x, x)}$
Έστω $D$ η συλλογή των επιθέτων των ελληνικών και $R(x, y)$ η σχέση «το επίθετο $x$ εφαρμόζεται στη λέξη $y$ ». Ένα επίθετο $x$ είναι αυτολογικό αν $R(x, x)$ και ετερολογικό αν $\neg R(x, x)$ .
$\dato{h}{(\forall x \in D)\,\left( R(h, x) \Leftrightarrow \neg R(x, x) \right)}$
Έστω $h$ το επίθετο «ετερολογικός». Από τον ορισμό του, εφαρμόζεται σε ένα επίθετο ακριβώς όταν αυτό το επίθετο δεν εφαρμόζεται στον εαυτό του.
$R(\resaltar{h}, \resaltar{h}) \Leftrightarrow \neg R(\resaltar{h}, \resaltar{h})$
Αν το $h$ είναι επίθετο, ανήκει στο $D$ , και η συνθήκη του είναι εκείνη του διαγώνιου λήμματος. Θέτοντας $x = h$ , προκύπτει η αδύνατη ισοδυναμία.
$h \in D \Rightarrow \resaltar{h \notin D}$
Από το διαγώνιο λήμμα, κανένα αντικείμενο του $D$ δεν πληροί τη συνθήκη του $h$ . Αν το $h$ ανήκει στο $D$ , υπάρχει αντίφαση.
$\resaltar{h \notin D}$
Η παραδοχή που αποτυγχάνει είναι η δεύτερη: το «εφαρμόζεται σε» δεν είναι ακριβής σχέση για επίθετα που, όπως το «ετερολογικός», ορίζονται με τη σειρά τους μέσω αυτής της ίδιας σχέσης. Σε μια τυπική γλώσσα, η σχέση $R$ θα οριζόταν στη μεταγλώσσα, και το επίθετο $h$ δεν θα ανήκε στη γλώσσα-αντικείμενο, ώστε η συνθήκη $h \in D$ θα ήταν ψευδής και δεν θα υπήρχε αντίφαση.

Προτεινόμενα προβλήματα

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

Προτεινόμενο πρόβλημα 1Δύο παρόμοιες μορφές

Ας θεωρηθούν οι δύο ακόλουθες μορφές: (α) «αν $p$ , τότε $q$ · όχι $q$ · επομένως, όχι $p$ »· (β) «αν $p$ , τότε $q$ · όχι $p$ · επομένως, όχι $q$ ». Να αποφασιστεί ποια είναι έγκυρη και ποια όχι· για την άκυρη, να κατασκευαστεί αντιπαράδειγμα με αποφάνσεις για αριθμούς, και για την έγκυρη, να εξηγηθεί γιατί κανένα στιγμιότυπο δεν μπορεί να είναι αντιπαράδειγμα.

Υπόδειξη

Για τη μορφή (β), αναζήτησε μια αληθή συνεπαγωγή ανάμεσα σε ιδιότητες αριθμών, όπως η «αν ο $n$ είναι πολλαπλάσιο του $4$ , είναι άρτιος», και έναν αριθμό που δεν έχει την πρώτη ιδιότητα αλλά έχει τη δεύτερη. Για την (α), υπόθεσε ότι οι υποθέσεις είναι αληθείς και αναρωτήσου τι θα συνέβαινε αν η $p$ ήταν αληθής.

Απάντηση

Η μορφή (α), που λέγεται modus tollens, είναι έγκυρη: αν οι υποθέσεις είναι αληθείς και η $p$ ήταν αληθής, θα ήταν αληθής και η $q$ , αντίθετα με τη δεύτερη υπόθεση. Η μορφή (β), η άρνηση του ηγουμένου, είναι άκυρη: η «αν ο $6$ είναι πολλαπλάσιο του $4$ , ο $6$ είναι άρτιος· ο $6$ δεν είναι πολλαπλάσιο του $4$ · επομένως, ο $6$ δεν είναι άρτιος» έχει αληθείς υποθέσεις και ψευδές συμπέρασμα.

Προτεινόμενο πρόβλημα 2Διαβατήριο, ταυτότητα και βίζα

Μια ανακοίνωση λέει: «για την είσοδο απαιτείται διαβατήριο ή ταυτότητα και βίζα». Να γραφτούν οι δύο αναγνώσεις της με τα γράμματα $p$ (διαβατήριο), $d$ (ταυτότητα) και $v$ (βίζα), και να περιγραφεί ένα πρόσωπο που η μία ανάγνωση το αφήνει να μπει και η άλλη όχι.

Υπόδειξη

Το ερώτημα είναι αν η βίζα συνοδεύει μόνο την ταυτότητα ή οποιοδήποτε από τα δύο έγγραφα. Δοκίμασε με ένα πρόσωπο που έχει ένα μόνο έγγραφο.

Απάντηση

Οι αναγνώσεις είναι $p \vee (d \wedge v)$ και $(p \vee d) \wedge v$ . Ένα πρόσωπο με διαβατήριο και χωρίς βίζα μπορεί να μπει σύμφωνα με την πρώτη και όχι σύμφωνα με τη δεύτερη.

Προτεινόμενο πρόβλημα 3Εισαγωγικά

Να αποφασιστεί αν κάθε πρόταση μιλά για την πόλη ή για τη λέξη, και αν είναι αληθής ή ψευδής: (α) «η Ρώμη έχει τέσσερα γράμματα»· (β) «η “Ρώμη” έχει τέσσερα γράμματα»· (γ) «η “Ρώμη” είναι η πρωτεύουσα της Ιταλίας»· (δ) «η πρόταση “η Ρώμη είναι η πρωτεύουσα της Ιταλίας” περιέχει τη λέξη “Ρώμη”».

Υπόδειξη

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

Απάντηση

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

Προτεινόμενο πρόβλημα 4Οι δύο όψεις μιας κάρτας

Στη μία όψη μιας κάρτας είναι γραμμένη η πρόταση $A$ : «η πρόταση $B$ είναι αληθής»· στην άλλη όψη, η πρόταση $B$ : «η πρόταση $A$ είναι ψευδής». Δεχόμενοι τη διτιμία και το σχήμα της αλήθειας, να αποδειχθεί ότι δεν υπάρχει τρόπος να αποδοθούν τιμές αλήθειας στην $A$ και στη $B$ . Τι συμβαίνει αν η $B$ λέει, αντίθετα, «η πρόταση $A$ είναι αληθής»;

Υπόδειξη

Γράψε το σχήμα της αλήθειας για κάθε πρόταση, και σύνδεσε τις ισοδυναμίες ώσπου να πάρεις μία που συσχετίζει την $V(A)$ με τον εαυτό της. Στην παραλλαγή, κάνε το ίδιο και έλεγξε ποιες αποδόσεις τιμών την ικανοποιούν.

Απάντηση

Στην πρώτη εκδοχή προκύπτει $V(A) \Leftrightarrow \neg V(A)$ , όπως στον ψεύτη, χωρίς καμία πρόταση να μιλά για τον εαυτό της. Στην παραλλαγή, η $V(A) \Leftrightarrow V(B)$ δέχεται δύο αποδόσεις τιμών, και οι δύο αληθείς ή και οι δύο ψευδείς: δεν υπάρχει αντίφαση, αλλά τίποτα δεν αποφασίζει ανάμεσά τους.

Αναλυτική λύση

Λύση

$\dato{A}{V(A) \Leftrightarrow V(B)}$
Από το σχήμα της αλήθειας, η $A$ είναι αληθής ακριβώς όταν η $B$ είναι αληθής.
$\dato{B}{V(B) \Leftrightarrow F(A) \Leftrightarrow \neg V(A)}$
Από το σχήμα της αλήθειας, η $B$ είναι αληθής ακριβώς όταν η $A$ είναι ψευδής· από τη διτιμία, το να είναι ψευδής είναι το να μην είναι αληθής.
$V(A) \Leftrightarrow \resaltar{\neg V(A)}$
Αν συνδέσουμε τις δύο ισοδυναμίες, η αλήθεια της $A$ ισοδυναμεί με την ίδια της την άρνηση, και συλλογιζόμαστε όπως στον ψεύτη: αν η $A$ είναι αληθής, δεν είναι, και αν δεν είναι, είναι.
$V(A) \Leftrightarrow V(B) \Leftrightarrow V(A)$
Στην παραλλαγή, το σχήμα της αλήθειας για τη $B$ δίνει $V(B) \Leftrightarrow V(A)$ , που μαζί με την πρώτη ισοδυναμία απαιτεί μόνο να έχουν και οι δύο την ίδια τιμή: υπάρχουν δύο συνεπείς αποδόσεις τιμών και καμία αντίφαση.

Προτεινόμενο πρόβλημα 5Η διαγώνιος του Κάντορ

Έστω $s_1, s_2, s_3, \ldots$ μια οποιαδήποτε λίστα άπειρων ακολουθιών από μηδενικά και μονάδες, και ας γράφουμε $s_x(y)$ για τον $y$ -οστό όρο της ακολουθίας $s_x$ . Να αποδειχθεί, με το διαγώνιο λήμμα, ότι η ακολουθία $d$ που ορίζεται με $d(y) = 1$ όταν $s_y(y) = 0$ , και $d(y) = 0$ όταν $s_y(y) = 1$ , δεν εμφανίζεται στη λίστα. Να συναχθεί ότι καμία αριθμημένη λίστα δεν περιέχει όλες τις ακολουθίες από μηδενικά και μονάδες.

Υπόδειξη

Πάρε ως συλλογή $D$ τους φυσικούς αριθμούς και ως σχέση $R(x, y)$ τον ισχυρισμό $s_x(y) = 1$ . Ποια συνθήκη θα πληρούσε ένας αριθμός $b$ τέτοιος ώστε $s_b = d$ ;

Απάντηση

Αν ήταν $d = s_b$ , ο αριθμός $b$ θα πληρούσε $R(b, y) \Leftrightarrow \neg R(y, y)$ για κάθε $y$ , πράγμα που το διαγώνιο λήμμα απαγορεύει. Επομένως η $d$ διαφέρει από κάθε $s_b$ τουλάχιστον στον $b$ -οστό όρο, και καμία λίστα δεν περιέχει όλες τις ακολουθίες.

Αναλυτική λύση

Λύση

$\dato{R}{R(x, y) \Leftrightarrow s_x(y) = 1}$
Έστω $D$ το σύνολο των φυσικών αριθμών και $R(x, y)$ ο ισχυρισμός ότι ο $y$ -οστός όρος της $s_x$ ισούται με $1$ .
$\dato{d}{d(y) = 1 \Leftrightarrow \neg\left( s_y(y) = 1 \right)}$
Από τον ορισμό της, η $d(y)$ ισούται με $1$ ακριβώς όταν η $s_y(y)$ δεν ισούται με $1$ .
$(\forall y \in D)\,\left( R(\resaltar{b}, y) \Leftrightarrow \neg R(y, y) \right)$
Ας υποθέσουμε ότι η $d$ εμφανίζεται στη λίστα στη θέση $b$ , δηλαδή $d = s_b$ . Τότε, για κάθε $y$ , το $R(b, y)$ ισοδυναμεί με $d(y) = 1$ , που ισοδυναμεί με $\neg R(y, y)$ .
$d(b) \neq s_b(b)$
Από το διαγώνιο λήμμα, κανένα $b$ δεν πληροί αυτή τη συνθήκη: η ακολουθία $d$ δεν εμφανίζεται στη λίστα. Συγκεκριμένα, διαφέρει από την $s_b$ στον $b$ -οστό όρο.
$(\forall b \in \mathbb{N})\,(d \neq s_b)$
Αφού η λίστα ήταν οποιαδήποτε, καμία αριθμημένη λίστα δεν περιέχει όλες τις ακολουθίες από μηδενικά και μονάδες: σε κάθε λίστα λείπει, τουλάχιστον, η διαγώνια ακολουθία του.