forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 25 Νοέμ 2017, 09:41

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 3 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Απορία σχετικά με αριθμήσιμα σύνολα
ΔημοσίευσηΔημοσιεύτηκε: 09 Φεβ 2014, 12:08 
Χωρίς σύνδεση

Εγγραφη: 09 Φεβ 2014, 12:02
Δημοσ.: 1
Καλησπέρα, έχω μια απορία που σχετίζεται με αριθμήσιμα ή μη αριθμήσιμα σύνολα:
Αν έχουμε μια ένα σύνολο από δυαδικές συμβολοσειρές άπειρου μήκους, οι οποίες όμως περιέχουν πεπερασμένο αριθμό από 0 και άπειρο αριθμό από 1, τότε το σύνολο αυτό είναι αριθμήσιμο ή όχι; Έχω μπερδευτεί λιγάκι... :cry:


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Απορία σχετικά με αριθμήσιμα σύνολα
ΔημοσίευσηΔημοσιεύτηκε: 09 Φεβ 2014, 13:22 
Χωρίς σύνδεση
Forum Moderator
Άβαταρ μέλους

Εγγραφη: 09 Φεβ 2012, 22:03
Δημοσ.: 619
Έστω Α το σύνολο που περιέχει δυαδικές συμβολοσειρές άπειρου μήκους, οι οποίες όμως περιέχουν πεπερασμένο αριθμό από 0 και άπειρο αριθμό από 1.

Θα αποδείξω ότι υπάρχει 1-1 αντιστοιχία από το Α στους φυσικούς αριθμούς, και άρα θα είναι αριθμήσιμο.

Έστω a\in A, τότε a=(a_n)_{n \in \mathbb{N}}, όπου για κάθε n \in \mathbb{N}, a_n \in \{0,1\} και από την υπόθεση, το \{i\in \mathbb{N} : a_i = 0\} είναι πεπερασμένο (1).

Έστω f:A\rightarrow \mathbb{N} με:

f(a)= \sum\limits_{i=0}^\infty (1-a_i)*2^i, το οποίο είναι ένα πεπερασμένο άθροισμα, από την (1).

Δηλαδή, f(a)= \sum\limits_{i\in \mathbb{N} : a_i = 0} 2^i και καθώς κάθε a\in A χαρακτηρίζεται μόνο από τις πεπερασμένες σε πλήθος θέσεις που έχει μηδενικά, η f:A\rightarrow \mathbb{N} είναι 1-1 και άρα έχουμε το ζητούμενο.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Απορία σχετικά με αριθμήσιμα σύνολα
ΔημοσίευσηΔημοσιεύτηκε: 09 Φεβ 2014, 14:24 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 16 Ιαν 2009, 01:23
Δημοσ.: 873
Επίσης αν έχει αποδειχθεί πιο πριν (ή αν θεωρείται γνωστό) ότι το σύνολο που περιέχει τα πεπερασμένα υποσύνολα των φυσικών είναι αριθμήσιμο, τότε υπάρχει και μια πιο άμεση αντιστοιχία των παραπάνω δυαδικών ακολουθιών σ'αυτό.


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 3 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group