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

Στην θεωρία συνόλων, ένα σύνολο $A$ που είναι σε ένα προς ένα αντιστοιχία με το σύνολο των φυσικών αριθμών $\mathbb {N}$ ονομάζεται αριθμήσιμο. Αυτό μας επιτρέπει να απαριθμήσουμε τα στοιχεία του ως $a_{0},a_{1},a_{2},\ldots$.

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

Ορισμός

Ένα σύνολο $A$ λέγεται το πολύ αριθμήσιμο αν υπάρχει επιρρηπτική συνάρτηση $a:\mathbb {N} \to A$, δηλαδή μία συνάρτηση για την οποία ισχύει

$\forall x\in A.~~\exists n.~~a(n)=x$,

δηλαδή κάθε στοιχείο $x$ του $A$ εμφανίζεται κάπου στην ακολουθία $a(0),a(1),a(2),\ldots$.

Ένα σύνολο $A$ λέγεται αριθμήσιμο αν η συνάρτηση $a$ είναι αμφίρριψη, για την οποία ισχύει

$\forall n,m.~~a(n)=a(m)\Rightarrow n=m$,

δηλαδή επιπλέον κάθε στοιχείο του $A$ εμφανίζεται ακριβώς μία φορά στην ακολουθία $a(0),a(1),a(2),\ldots$.

Σημείωση: Η όροι της ακολουθίας συνήθως γράφονται ως $a_{0},a_{1},a_{2},\ldots$.

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

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

Κάθε πεπερασμένο σύνολο είναι το πολύ αριθμήσιμο:

• To σύνολο $\mathbb {Z} _{5}=\{0,1,2,3,4\}$ είναι το πολύ αριθμήσιμο καθώς $a(n)=n{\bmod {5}}$ ορίζει μία επί συνάρτηση.

$n$	0	1	2	3	4	5	6	7	8	9	10	11	12	$\ldots$
$a(n)$	0	1	2	3	4	0	1	2	3	4	0	1	2

Παρατηρήστε ότι κάποια στοιχεία επαναλαμβάνονται και γι'αυτό δεν μας δίνει αμφίρριψη.

• To σύνολο των βασικών αριθμητικών πράεων $A=\{+,-,\times ,\div \}$ είναι το πολύ αριθμήσιμο καθώς η εξής συνάρτηση είναι επίρρηψη

$n$	0	1	2	3	4	5	6	7	8	9	10	11	12	$\ldots$
$a(n)$	$+$	$+$	$-$	$\times$	$\div$	$\times$	$\div$	$\times$	$\times$	$\times$	$\div$	$\div$	$+$

Τα εξής σύνολα είναι αριθμήσιμα (και το πολύ αριθμήσιμα):

• Οι φυσικοί αριθμοί $\mathbb {N} =\{0,1,2,3,\ldots \}$, με την συνάρτηση $a(n)=n$.
• Οι ακέραιοι αριθμοί $\mathbb {Z} =\{\ldots ,-2,-1,0,1,2,\ldots \}$. Για παράδειγμα, με την συνάρτηση

$a(n)={\begin{cases}n/2&{\text{αν }}n{\text{ ζυγός}},\\-(n+1)/2&{\text{αν }}n{\text{ μονός}}.\end{cases}}$

$n$	0	1	2	3	4	5	6	7	8	9	10	11	12	$\ldots$
$a(n)$	0	-1	+1	-2	+2	-3	+3	-4	+4	-5	+5	-6	+6

Το καρτεσιανό γινόμενο $\mathbb {N} \times \mathbb {N}$ είναι αριθμήσιμο σύνολο.

• Το καρτεσιανό γινόμενο $\mathbb {N} \times \mathbb {N}$.

$n$	0	1	2	3	4	5	6	7	8	9	10	11	12	$\ldots$
$a(n)$	$(0,0)$	$(0,1)$	$(1,0)$	$(2,0)$	$(1,1)$	$(0,2)$	$(3,0)$	$(2,1)$	$(1,2)$	$(0,3)$	$(0,4)$	$(1,3)$	$(2,2)$

• Το σύνολο όλων των ρητών αριθμών $\mathbb {Q}$.
• Το σύνολο όλων των πεπερασμένων ακολουθιών φυσικών αριθμών.
• Το σύνολο όλων των προγραμάτων σε μία γλώσσα προγραμματισμού.

Τα εξής σύνολα είναι υπεραριθμήσιμα:

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

Ιδιότητες

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

Δείτε επίσης

• Πεπερασμένο σύνολο
• Άπειρο σύνολο