Αριθμήσιμο σύνολο

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

Ένα σύνολο  που είναι είτε πεπερασμένο είτε αριθμήσιμο ονομάζεται το πολύ αριθμήσιμο. Ένα σύνολο  που δεν είναι το πολύ αριθμήσιμο ονομάζεται υπεραριθμήσιμο. 

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

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

Σημείωση: Η όροι της ακολουθίας συνήθως γράφονται ως . 

Ένα σύνολο  που δεν είναι το πολύ αριθμήσιμο ονομάζεται υπεραριθμήσιμο. 

 Παραδείγματα 

Κάθε πεπερασμένο σύνολο είναι το πολύ αριθμήσιμο:
 To σύνολο  είναι το πολύ αριθμήσιμο καθώς  ορίζει μία επί συνάρτηση.
{| class="wikitable"
|-
|  || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 
|-
|  || 0 || 1 || 2 || 3 || 4 || 0 || 1 || 2 || 3 || 4 || 0 || 1 || 2
|}
Παρατηρήστε ότι κάποια στοιχεία επαναλαμβάνονται και γι'αυτό δεν μας δίνει αμφίρριψη.
 To σύνολο των βασικών αριθμητικών πράεων  είναι το πολύ αριθμήσιμο καθώς η εξής συνάρτηση είναι επίρρηψη
{| class="wikitable"
|-
|  || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 
|-
|  ||  ||  ||  ||  ||  ||  ||  ||  ||  ||  ||  ||  || 
|}

Τα εξής σύνολα είναι αριθμήσιμα (και το πολύ αριθμήσιμα):
 Οι φυσικοί αριθμοί , με την συνάρτηση .
 Οι ακέραιοι αριθμοί . Για παράδειγμα, με την συνάρτηση 

{| class="wikitable"
|-
|  || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 
|-
|  || 0 || -1 || +1 || -2 || +2 || -3 || +3 || -4 || +4 || -5 || +5 || -6 || +6
|}
 Το καρτεσιανό γινόμενο .
{| class="wikitable"
|-
|  || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 
|-
|  ||  ||  ||  ||  ||  ||  ||  ||  ||  ||  ||  ||  || 
|}
 Το σύνολο όλων των ρητών αριθμών .
 Το σύνολο όλων των πεπερασμένων ακολουθιών φυσικών αριθμών. 
 Το σύνολο όλων των προγραμάτων σε μία γλώσσα προγραμματισμού.

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

 Ιδιότητες 
 Κάθε αριθμήσιμο σύνολο είναι το πολύ αριθμήσιμο. 
 Κάθε μη-πεπερασμένο σύνολο που είναι το πολύ αριθμήσιμο είναι αριθμήσιμο.
 Κάθε υποσύνολο ενός αριθμήσιμου συνόλου είναι το πολύ αριθμήσιμο.
 Η τομή δύο αριθμήσιμων συνόλων είναι αριθμήσιμο σύνολο.
 Η ένωση δύο αριθμήσιμων συνόλων είναι αριθμήσιμο σύνολο.
 Η ένωση πεπερασμένου πλήθους από αριθμήσιμα σύνολα είναι επίσης αριθμήσιμο σύνολο.
 Η ένωση αριθμήσιμου πλήθους από αριθμήσιμα σύνολα είναι επίσης αριθμήσιμο σύνολο.
 Το Καρτεσιανό γινόμενο δύο αριθμήσιμων συνόλων είναι αριθμήσιμο σύνολο.
 Το Καρτεσιανό γινόμενο πεπερασμένου πλήθους αριθμήσιμων συνόλων είναι αριθμήσιμο.
 Το δυναμοσύνολο ενός αριθμήσιμου συνόλου είναι υπεραριθμήσιμο.

 Δείτε επίσης 
 Πεπερασμένο σύνολο
 Άπειρο σύνολο

Κατηγορία:Θεωρία συνόλων