Το διαγώνιο επιχείρημα του Κάντορ

Το παράδειγμα που ακολουθεί χρησιμοποιεί δύο από τα απλούστερα άπειρα σύνολα, αυτό των φυσικών αριθμών και αυτό των θετικών κλασμάτων. Η ιδέα είναι να δείξουμε ότι και τα δύο αυτά σύνολα, N {\displaystyle \mathbb {N} } και Q + {\displaystyle \mathbb {Q^{+}} } έχουν την ίδια καρτελικότητα.

Αρχικά, τα κλάσματα ευθυγραμμίζονται σε έναν πίνακα, ως εξής:

1 1 1 1 2 1 3 1 4 1 5 ⋯ 2 1 2 2 2 2 3 2 4 2 5 ⋯ 3 1 3 2 3 3 3 3 3 3 4 3 5 ⋯ 4 1 4 2 4 3 4 4 4 4 4 5 ⋯ 5 1 5 2 5 3 5 4 4 5 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccccccccccc}{\tfrac {1}{1}}&&{\tfrac {1}{2}}&&{\tfrac {1}{3}}&&{\tfrac {1}{4}}&&{\tfrac {1}{5}}&\cdots \\\&&&&&&&&&\\{\tfrac {2}{1}}&&{\tfrac {2}{2}}&&{\tfrac {2}{3}}&&{\tfrac {2}{4}}&&{\tfrac {2}{5}}&\cdots \\\&&&&&&&&&\\\{\tfrac {3}{1}}&&{\tfrac {3}{2}}&&{\tfrac {3}{3}}&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\\\&&&&&&&&&\\\\{\tfrac {4}{1}}&&{\tfrac {4}{2}}&&{\tfrac {4}{3}}&&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&\cdots \\\&&&&&&&&&\\\{\tfrac {5}{1}}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\\end{array}}}

Στη συνέχεια, οι αριθμοί καταμετρώνται, όπως φαίνεται. Τα κλάσματα που μπορούν να απλοποιηθούν παραλείπονται:

1 1 ( 1 ) → 1 2 ( 2 ) 1 3 ( 5 ) → 1 4 ( 6 ) 1 5 ( 11 ) → ↙ ↙ 2 1 ( 3 ) 2 2 ( ⋅ ) 2 3 ( 7 ) 2 4 ( ⋅ ) 2 5 ⋯ ↓ ↙ 3 1 ( 4 ) 3 2 ( 8 ) 3 3 ( ⋅ ) 3 4 3 5 ⋯ ↙ 4 1 ( 9 ) 4 2 ( ⋅ ) 4 3 4 4 4 4 5 ⋯ ↓ 5 1 ( 10 ) 5 2 5 3 5 4 5 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{lclclclclclclc}{\tfrac {1}{1}}\ _{\color {Blue}(1)}&{\tfrac {1}{2}}\ _{\color {Blue}(2)}&&{\tfrac {1}{3}}\ _{\color {Blue}(5)}&{\tfrac {1}{3}}\ _{\color {Blue}(5)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{4}}\ _{\color {Blue}(6)}&&&{\tfrac {1}{5}}\ _{\color {Blue}(11)}&{\color {MidnightBlue}\rightarrow }\\&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&\\\{\tfrac {2}{1}}\ _{\color {Blue}(3)}&&{\tfrac {2}{2}}\ _{\color {Blue}(\cdot )}&&{\tfrac {2}{3}}\ _{\color {Blue}(7)}&&{\tfrac {2}{4}}\ _{\color {Blue}(\cdot )}&&{\tfrac {2}{5}}&\cdots \\\\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&\\{\tfrac {3}{1}}\ _{\color {Blue}(4)}&&{\tfrac {3}{2}}\ _{\color {Blue}(8)}&&{\tfrac {3}{3}}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\\&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&&&\\\{\tfrac {4}{1}}\ _{\color {Blue}(9)}&&{\tfrac {4}{2}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {4}{3}}&&{\tfrac {4}{4}{4}}&&{\tfrac {4}{5}}&\cdots \\{\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&&&&&&\\\{\tfrac {5}{1}}\ _{\color {Blue}(10)}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\\end{array}}}

Με αυτόν τον τρόπο, τα κλάσματα υπολογίζονται:

1 2 3 4 5 6 7 8 9 10 11 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 2 3 1 3 1 3 1 4 2 3 3 2 4 5 1 5 ⋯ {\displaystyle {\begin{array}{cccccccccccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}\cdots }\\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\\[3pt]1&{\tfrac {1}{2}}&2&3&{\tfrac {1}{3}}&{\tfrac {1}{4}}&{\tfrac {2}{3}}&{\tfrac {3}{2}}&4&5&{\tfrac {1}{5}}&\cdots \\\\\\end{array}}}

Παραλείποντας τα κλάσματα που μπορούν ακόμα να απλοποιηθούν, υπάρχει μια διχοτόμηση που συσχετίζει κάθε στοιχείο των φυσικών αριθμών με ένα στοιχείο των κλασμάτων:

Για να δείξουμε ότι όλοι οι φυσικοί αριθμοί και τα κλάσματα έχουν την ίδια καρδινικότητα, πρέπει να προστεθεί το στοιχείο 0- μετά από κάθε κλάσμα προστίθεται το αρνητικό του,

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 0 1 - 1 1 2 - 1 2 2 - 2 3 - 3 1 3 - 1 3 1 4 - 1 4 2 3 - 2 3 ⋯ {\displaystyle {\begin{array}{cccccccccccccccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}12}&{\color {Blue}13}&{\color {Blue}14}&{\color {Blue}15}&{\color {Blue}\cdots }\\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\\[3pt]0&1&-1&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&&2&-2&3&-3&{\tfrac {1}{3}}&-{\tfrac {1}{3}}&{\tfrac {1}{4}}&-{\tfrac {1}{4}}&{\tfrac {2}{3}}&-{\tfrac {2}{3}}}&\cdots \\\\\\end{array}}}

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

Τα άπειρα σύνολα έχουν συχνά ιδιότητες που αντιβαίνουν στη διαίσθηση: Ο Ντέιβιντ Χίλμπερτ το έδειξε αυτό σε ένα πείραμα που ονομάζεται παράδοξο του Χίλμπερτ στο Grand Hotel.

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

Ξεκινά με μια εποικοδομητική απόδειξη του ακόλουθου θεωρήματος:

Εάν s₁ , s₂ , ... , s_n , ... είναι οποιαδήποτε απαρίθμηση στοιχείων από το T, τότε υπάρχει πάντα ένα στοιχείο s του T που δεν αντιστοιχεί σε κανένα s_n στην απαρίθμηση.

Για να το αποδείξετε αυτό, δεδομένης μιας απαρίθμησης στοιχείων από το T, όπως π.χ.

Η ακολουθία s κατασκευάζεται επιλέγοντας το 1ο ψηφίο ως συμπληρωματικό προς το 1ο ψηφίο της s₁ (αντικαθιστώντας τα 0 με τα 1 και αντίστροφα), το 2ο ψηφίο ως συμπληρωματικό προς το 2ο ψηφίο της s₂ , το 3ο ψηφίο ως συμπληρωματικό προς το 3ο ψηφίο της s₃ και γενικά για κάθε n, το n^th ψηφίο ως συμπληρωματικό προς το n^th ψηφίο της s_n . Στο παράδειγμα, αυτό δίνει:

Κατασκευαστικά, το s διαφέρει από κάθε s_n , αφού τα n^th ψηφία τους διαφέρουν (επισημαίνονται στο παράδειγμα). Ως εκ τούτου, το s δεν μπορεί να εμφανιστεί στην απαρίθμηση.

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

Το σύνολο Τ είναι μη μετρήσιμο.

Υποθέτει για αντιφάσεις ότι το Τ ήταν μετρήσιμο. Σε αυτή την περίπτωση, όλα τα στοιχεία της θα μπορούσαν να γραφούν ως απαρίθμηση s₁ , s₂ , ... , s_n , ... . Η εφαρμογή του προηγούμενου θεωρήματος σε αυτή την απαρίθμηση θα παρήγαγε μια ακολουθία s που δεν ανήκει στην απαρίθμηση. Ωστόσο, η s ήταν στοιχείο του T και επομένως θα έπρεπε να βρίσκεται στην απαρίθμηση. Αυτό έρχεται σε αντίθεση με την αρχική υπόθεση, οπότε το T πρέπει να είναι μη απαριθμήσιμο.