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

MathSc
Δημοσιεύσεις: 5
Εγγραφή: Παρ Αύγ 31, 2018 5:46 pm

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

#1

Μη αναγνωσμένη δημοσίευση από MathSc » Κυρ Οκτ 14, 2018 9:50 pm

Καλησπέρα σας! Έχω ξεκινήσει να μελετάω Σύνολα. Προσπαθώ μια άσκηση που φαίνεται βασική αλλά έχω κολλήσει. Θα ήθελα τη βοήθειά σας.
α) Δείξτε ότι το σύνολο όλων των θετικών ρητών αριθμών είναι αριθμήσιμο σύνολο.
β) Δείξτε ότι η ένωση αριθμήσιμου πλήθους αριθμήσιμων συνόλων είναι αριθμήσιμο σύνολο.

Το α νομίζω πως το έλυσα σχεδόν, αν και ο τρόπος γραφής δεν μου αρέσει ιδιαίτερα. Θα ήθελα μια καλύτερη προσέγγιση από εσάς. Έκανα το εξής:
Σκέφτομαι " Είναι αριθμήσιμο το σύνολο των θετικών ρητών, δηλαδή των κλασμάτων \displaystyle{ \frac{p}{q}, } με \displaystyle{ p,q \in \mathbb{N} } ; "
Προσπάθησα να βάλω όλα τα κλάσματα σε σειρά ως εξής :
\displaystyle{ \frac{1}{1}, \frac{1}{2}, \frac{1}{3}, ..., \frac{2}{1}, \frac{2}{2}, \frac{2}{3}, ... , \frac{3}{1},... }
Όμως αυτή η σειρά δε δείχνει ότι το σύνολο των θετικών ρητών είναι αριθμήσιμο.
Παρατηρούμε ότι ένα σύνολο είναι αριθμήσιμο, εάν, ξεκινώντας από ένα συγκεκριμένο στοιχείο μπορούμε σειριακά να καταγράψουμε όλα τα στοιχεία του συνόλου, το ένα μετά το άλλο.
Οπότε ψάχνω κατάλληλη ακολουθία. Μία είναι η εξής:
\displaystyle{ \frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{2}{2}, \frac{3}{1}, \frac{1}{4},... }
Πρώτα τα κλάσματα με άθροισμα αριθμητή και παρονομαστή ίσο με 2, μετά ίσο με 3, κτλ.
Ένα κλάσμα \displaystyle{ \frac{p}{q} } θα εμφανιστεί όταν απαριθμούμε τα κλάσματα με άθροισμα αριθμητή και παρονομαστή ίσο με \displaystyle{ p + q }.
_______________________________________
Μέχρι εκεί έχω φτάσει. Το β ερώτημα, αν και υπάρχει γραμμένο μες το βιβλίο, δεν αποδεικνύεται πουθενά.
Ευχαριστώ εκ των προτέρων!



Λέξεις Κλειδιά:
ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 2001
Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ

Re: αριθμήσιμο σύνολο

#2

Μη αναγνωσμένη δημοσίευση από ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ » Κυρ Οκτ 14, 2018 9:57 pm

MathSc έγραψε:
Κυρ Οκτ 14, 2018 9:50 pm
Καλησπέρα σας! Έχω ξεκινήσει να μελετάω Σύνολα. Προσπαθώ μια άσκηση που φαίνεται βασική αλλά έχω κολλήσει. Θα ήθελα τη βοήθειά σας.
α) Δείξτε ότι το σύνολο όλων των θετικών ρητών αριθμών είναι αριθμήσιμο σύνολο.
β) Δείξτε ότι η ένωση αριθμήσιμου πλήθους αριθμήσιμων συνόλων είναι αριθμήσιμο σύνολο.

Το α νομίζω πως το έλυσα σχεδόν, αν και ο τρόπος γραφής δεν μου αρέσει ιδιαίτερα. Θα ήθελα μια καλύτερη προσέγγιση από εσάς. Έκανα το εξής:
Σκέφτομαι " Είναι αριθμήσιμο το σύνολο των θετικών ρητών, δηλαδή των κλασμάτων \displaystyle{ \frac{p}{q}, } με \displaystyle{ p,q \in \mathbb{N} } ; "
Προσπάθησα να βάλω όλα τα κλάσματα σε σειρά ως εξής :
\displaystyle{ \frac{1}{1}, \frac{1}{2}, \frac{1}{3}, ..., \frac{2}{1}, \frac{2}{2}, \frac{2}{3}, ... , \frac{3}{1},... }
Όμως αυτή η σειρά δε δείχνει ότι το σύνολο των θετικών ρητών είναι αριθμήσιμο.
Παρατηρούμε ότι ένα σύνολο είναι αριθμήσιμο, εάν, ξεκινώντας από ένα συγκεκριμένο στοιχείο μπορούμε σειριακά να καταγράψουμε όλα τα στοιχεία του συνόλου, το ένα μετά το άλλο.
Οπότε ψάχνω κατάλληλη ακολουθία. Μία είναι η εξής:
\displaystyle{ \frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{2}{2}, \frac{3}{1}, \frac{1}{4},... }
Πρώτα τα κλάσματα με άθροισμα αριθμητή και παρονομαστή ίσο με 2, μετά ίσο με 3, κτλ.
Ένα κλάσμα \displaystyle{ \frac{p}{q} } θα εμφανιστεί όταν απαριθμούμε τα κλάσματα με άθροισμα αριθμητή και παρονομαστή ίσο με \displaystyle{ p + q }.
_______________________________________
Μέχρι εκεί έχω φτάσει. Το β ερώτημα, αν και υπάρχει γραμμένο μες το βιβλίο, δεν αποδεικνύεται πουθενά.
Ευχαριστώ εκ των προτέρων!
Δεν είναι ασκήσεις αυτές.Είναι θεωρήματα και βρίσκονται μαζί με την απόδειξη τους σε όλα τα σοβαρά βιβλία.

Επίσης μπορείς να τα βρεις στο διαδίκτυο.


MathSc
Δημοσιεύσεις: 5
Εγγραφή: Παρ Αύγ 31, 2018 5:46 pm

Re: αριθμήσιμο σύνολο

#3

Μη αναγνωσμένη δημοσίευση από MathSc » Κυρ Οκτ 14, 2018 10:00 pm

Θα σας ήταν εύκολο να προσθέσετε κάποιον σύνδεσμο ώστε να το διαβάσω; Συγγνώμη για την ταλαιπωρία αλλά στο βιβλίο που διαβάζω δεν υπάρχει.


Άβαταρ μέλους
Tolaso J Kos
Δημοσιεύσεις: 3522
Εγγραφή: Κυρ Αύγ 05, 2012 10:09 pm
Τοποθεσία: Λάρισα
Επικοινωνία:

Re: αριθμήσιμο σύνολο

#4

Μη αναγνωσμένη δημοσίευση από Tolaso J Kos » Κυρ Οκτ 14, 2018 10:01 pm

Γνωρίζεις ότι το \mathbb{Q} είναι ένα άπειρο σύνολο. Ένα άπειρο σύνολο είναι αριθμήσιμο αν έχει μία injection στο \mathbb{Z}. Μία τέτοια , ας πούμε , είναι αυτή:


\displaystyle{\Phi(q) =  
\begin{cases} 
0 & \quad q = 0 \\ 
1 & \quad q = 1 \\ 
-1 & \quad q = -1 \\ 
2^m (2n + 1) & \quad q = \frac{m}{n} \text{ simplest form } \\ 
- 2^m(2n + 1) & \quad q = - \frac{m}{n} \text{ simplest form} 
\end{cases}}
ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε:
Κυρ Οκτ 14, 2018 9:57 pm
Δεν είναι ασκήσεις αυτές.Είναι θεωρήματα και βρίσκονται μαζί με την απόδειξη τους σε όλα τα σοβαρά βιβλία.

Επίσης μπορείς να τα βρεις στο διαδίκτυο.
Συμφωνώ .


Η φαντασία είναι σημαντικότερη από τη γνώση !
\displaystyle{{\color{blue}\mathbf{Life=\int_{birth}^{death}\frac{happiness}{time}\Delta time} }}
Άβαταρ μέλους
Tolaso J Kos
Δημοσιεύσεις: 3522
Εγγραφή: Κυρ Αύγ 05, 2012 10:09 pm
Τοποθεσία: Λάρισα
Επικοινωνία:

Re: αριθμήσιμο σύνολο

#5

Μη αναγνωσμένη δημοσίευση από Tolaso J Kos » Κυρ Οκτ 14, 2018 10:03 pm

Και μία εποπτεία ( χωρίς λόγια ):

Jbr1M.png
Jbr1M.png (53.52 KiB) Προβλήθηκε 359 φορές


Η φαντασία είναι σημαντικότερη από τη γνώση !
\displaystyle{{\color{blue}\mathbf{Life=\int_{birth}^{death}\frac{happiness}{time}\Delta time} }}
Άβαταρ μέλους
Tolaso J Kos
Δημοσιεύσεις: 3522
Εγγραφή: Κυρ Αύγ 05, 2012 10:09 pm
Τοποθεσία: Λάρισα
Επικοινωνία:

Re: αριθμήσιμο σύνολο

#6

Μη αναγνωσμένη δημοσίευση από Tolaso J Kos » Κυρ Οκτ 14, 2018 10:07 pm

MathSc έγραψε:
Κυρ Οκτ 14, 2018 9:50 pm
β) Δείξτε ότι η ένωση αριθμήσιμου πλήθους αριθμήσιμων συνόλων είναι αριθμήσιμο σύνολο.

Επιτρέπεται το αξίωμα επιλογής; Αν ναι, έχει καλώς και δύο αποδείξεις βρίσκονται εδώ , αλλιώς ... κλάφτα Χαράλαμπε.


Η φαντασία είναι σημαντικότερη από τη γνώση !
\displaystyle{{\color{blue}\mathbf{Life=\int_{birth}^{death}\frac{happiness}{time}\Delta time} }}
Άβαταρ μέλους
Tolaso J Kos
Δημοσιεύσεις: 3522
Εγγραφή: Κυρ Αύγ 05, 2012 10:09 pm
Τοποθεσία: Λάρισα
Επικοινωνία:

Re: αριθμήσιμο σύνολο

#7

Μη αναγνωσμένη δημοσίευση από Tolaso J Kos » Τρί Νοέμ 06, 2018 9:47 pm

Με μία κουβέντα που είχα χθες με τον κ. Νίκο Μαυρογιάννη διαπίστωσα πως δε χρειάζεται το αξίωμα επιλογής. Αντ' αυτού μπορούμε να χρησιμοποιήσουμε το διαγώνιο επιχείρημα Cantor-Schroeder-Bernstein και να σχηματίσουμε injections μεταξύ του \mathbb{N} και του \mathbb{N}\times \mathbb{N}.


Κάποια στιγμή θα συμπληρώσω τις λεπτομέρειες.


Η φαντασία είναι σημαντικότερη από τη γνώση !
\displaystyle{{\color{blue}\mathbf{Life=\int_{birth}^{death}\frac{happiness}{time}\Delta time} }}
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7884
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: αριθμήσιμο σύνολο

#8

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Νοέμ 07, 2018 10:39 am

Tolaso J Kos έγραψε:
Τρί Νοέμ 06, 2018 9:47 pm
Με μία κουβέντα που είχα χθες με τον κ. Νίκο Μαυρογιάννη διαπίστωσα πως δε χρειάζεται το αξίωμα επιλογής. Αντ' αυτού μπορούμε να χρησιμοποιήσουμε το διαγώνιο επιχείρημα Cantor-Schroeder-Bernstein και να σχηματίσουμε injections μεταξύ του \mathbb{N} και του \mathbb{N}\times \mathbb{N}.


Κάποια στιγμή θα συμπληρώσω τις λεπτομέρειες.

Όχι! Μια μορφή του αξιώματος της επιλογής χρειάζεται. Η πρόταση «Η ένωση αριθμήσιμου πλήθους αριθμήσιμων συνόλων είναι αριθμήσιμο σύνολο» αποδεικνύει εύκολα την πρόταση «Κάθε αριθμήσιμο σύνολο από μη κενά αριθμήσιμα σύνολα έχει συνάρτηση επιλογής».

Το τελευταίο είναι μια πιο αδύναμη μορφή του αξιώματος της επιλογής. Είναι η μορφή 5 εδώ. Στο άρθρο του Sageev που παραπέμπει (πρώτη παράγραφος στην σελίδα 3) λέει ότι "...it is shown that not even for a countable set of disjoint countable sets of reals does a choice set generally exist." Με άλλα λόγια δεν μπορούμε να αποδείξουμε την μορφή 5.


ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 2001
Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ

Re: αριθμήσιμο σύνολο

#9

Μη αναγνωσμένη δημοσίευση από ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ » Τετ Νοέμ 07, 2018 11:50 am

Εκείνο που μπορούμε να αποδείξουμε εύκολα είναι ότι το \mathbb{Q}^{+}

είναι ισοπληθικό με ένα A\subseteq \mathbb{N}.

Το \mathbb{Q}^{+}=\left \{ \frac{m}{n} :m,n\in \mathbb{N}-\left \{ 0 \right \}, (m,n)=1 \right \}

Αν πάρουμε την f:\mathbb{Q}^{+}\rightarrow \mathbb{N}

με f(\frac{m}{n})=2^{m}(2n-1)

τότε προφανώς η f είναι 1-1 οπότε το \mathbb{Q}^{+} είναι ισοπληθικό με το

A=f(\mathbb{Q}^{+})\subseteq \mathbb{N}


Τέτοιες f υπάρχουν πολλές.
π.χ οι f(\frac{m}{n})=p^{m}q^{n} με p,q διαφορετικούς πρώτους μας κάνουν.


Ερώτηση .Που χρησιμοποιήθηκε το αξίωμα της επιλογής;


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7884
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: αριθμήσιμο σύνολο

#10

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Νοέμ 07, 2018 1:18 pm

Σταύρο, μάλλον δεν ήμουν ξεκάθαρος. Όταν έλεγα ότι χρειάζεται μια μορφή του αξιώματος της επιλογής μιλούσα για το (β).


Άβαταρ μέλους
nsmavrogiannis
Επιμελητής
Δημοσιεύσεις: 4203
Εγγραφή: Σάβ Δεκ 20, 2008 7:13 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: αριθμήσιμο σύνολο

#11

Μη αναγνωσμένη δημοσίευση από nsmavrogiannis » Τετ Νοέμ 07, 2018 2:17 pm

Demetres έγραψε:
Τετ Νοέμ 07, 2018 10:39 am
Tolaso J Kos έγραψε:
Τρί Νοέμ 06, 2018 9:47 pm
Με μία κουβέντα που είχα χθες με τον κ. Νίκο Μαυρογιάννη διαπίστωσα πως δε χρειάζεται το αξίωμα επιλογής. Αντ' αυτού μπορούμε να χρησιμοποιήσουμε το διαγώνιο επιχείρημα Cantor-Schroeder-Bernstein και να σχηματίσουμε injections μεταξύ του \mathbb{N} και του \mathbb{N}\times \mathbb{N}.


Κάποια στιγμή θα συμπληρώσω τις λεπτομέρειες.

Όχι! Μια μορφή του αξιώματος της επιλογής χρειάζεται. Η πρόταση «Η ένωση αριθμήσιμου πλήθους αριθμήσιμων συνόλων είναι αριθμήσιμο σύνολο» αποδεικνύει εύκολα την πρόταση «Κάθε αριθμήσιμο σύνολο από μη κενά αριθμήσιμα σύνολα έχει συνάρτηση επιλογής».

Το τελευταίο είναι μια πιο αδύναμη μορφή του αξιώματος της επιλογής. Είναι η μορφή 5 εδώ. Στο άρθρο του Sageev που παραπέμπει (πρώτη παράγραφος στην σελίδα 3) λέει ότι "...it is shown that not even for a countable set of disjoint countable sets of reals does a choice set generally exist." Με άλλα λόγια δεν μπορούμε να αποδείξουμε την μορφή 5.
Demetres έγραψε:
Τετ Νοέμ 07, 2018 1:18 pm
Σταύρο, μάλλον δεν ήμουν ξεκάθαρος. Όταν έλεγα ότι χρειάζεται μια μορφή του αξιώματος της επιλογής μιλούσα για το (β).
Γεια σας. Γράφω κάπως βιαστικά εν μέσω ενός διαλείμματος για φαγητό.
Στην συζήτηση που είχαμε με τον Τόλη τον παρέπεμψα σε μια απόδειξη που έχω υπ΄όψιν και προέρχεται από το βιβλίο του Ι. Kaplansky Set Theory and Metric spaces. Στην σελίδα 22 αποδεικνύει το
Theorem 1. A countable union of countable sets is countable.
Το αξίωμα της επιλογής στο συγκεκριμένο βιβλίο υπάρχει στο κεφάλαιο 3 που αρχίζει από την σελίδα 49.
Επίσης ο Γιάννης Μοσχοβάκης στο βιβλίο του Σημειώσεις στην Συνολοθεωρία παραθέτει στην σελίδα 9 απόδειξη του θεωρήματος
2.10 Θεώρημα (Cantor) Για κάθε ακολουθία A_0, A_1, ...απαριθμητών συνόλων, η ένωση A=\cup ^{\infty}_{n=0}A_{n}=A_{0}\cup A_{1}\cup ... είναι επίσης απαριθμητό σύνολο.
Το αξίωμα της επιλογής και σε αυτό το βιβλίο εμφανίζεται πολυ μετά (κεφάλαιο 8 σελίδα 121).
Τελος και ο Kelley στο General Topology στην σελίδα 26 έχει το
17 Theorem If a is a countable family of countable sets, then \cup \{ A:A \in a \} is countable.
Στο βιβλίο του Kelley το αξίωμα της επιλογής και ισοδύναμα του εμφανίζονται στην σελίδα 31.

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


Αν κανείς δεν ελπίζει, δεν θα βρεί το ανέλπιστο, οι δρόμοι για το ανεξερεύνητο θα είναι κλειστοί.
Ηράκλειτος
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7884
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: αριθμήσιμο σύνολο

#12

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Νοέμ 07, 2018 3:42 pm

Νίκο, είναι λογικό να κάνουν τις αποδείξεις πριν να μιλήσουν για το αξίωμα της επιλογής. Η αριθμησιμότητα είναι πιο απλή έννοια και η χρήση του αξιώματος της επιλογής στην απόδειξη του (β) είναι τόσο αθώα που κανείς δεν πρόκειται να το παρατηρήσει. Ακόμη και ιστορικά να το δούμε έτσι έγινε. O Cantor τα απέδειξε αυτά προτού προταθεί προς χρήση το Αξίωμα της Επιλογής.


Ο Μοσχοβάκης μάλιστα το εξηγεί και στο κεφάλαιο 8. Αντιγράφω και μεταφράζω από την αγγλική έκδοση:
Less amusing but more significant for mathematics is the proof of the basic theorem 2.10, where we considered a sequence A_0, A_1 ,\ldots of countable sets and began with the phrase
<...>
but the rest of the proof needs a function (n \to \pi_n) which associates a specific enumeration \pi_n with each n
<...>
the Axiom of Choice guarantees precisely that there exists a function <...> such that for each n \in \mathbb{N} <...> it enumerates A_n.

Such “silent” appeals to the Axiom of Choice, masked by the notation, are very common in mathematics and especially in analysis <...>

Μεταφρασμένο από εμένα:

Λιγότερο διασκεδαστική αλλά πιο σημαντική για τα μαθηματικά είναι η απόδειξη του βασικού θεωρήματος 2.10, όπου θεωρήσαμε μια ακολουθία A_0, A_1 ,\ldots αριθμήσιμων συνόλων και ξεκινήσαμε με την φράση
<...>
αλλά η υπόλοιπη απόδειξη χρειάζεται μια συνάρτηση (n \to \pi_n) η οποία αντιστοιχίζει μια συγκεκριμένη απαρίθμηση \pi_n με κάθε n
<...>
το Αξίωμα της Επιλογής εγγυάται ακριβώς την ύπαρξη συνάρτησης <...> η οποία για κάθε n \in \mathbb{N} <...> απαριθμεί το A_n.

Τέτοιες «σιωπηλές» επικλήσεις στο Αξίωμα της Επιλογής, μεταμφιεσμένες από τους συμβολισμούς, είναι πολύ συχνές στα μαθηματικά και ειδικά στην ανάλυση <...>

\rule{500pt}{1pt}

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


Άβαταρ μέλους
nsmavrogiannis
Επιμελητής
Δημοσιεύσεις: 4203
Εγγραφή: Σάβ Δεκ 20, 2008 7:13 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: αριθμήσιμο σύνολο

#13

Μη αναγνωσμένη δημοσίευση από nsmavrogiannis » Πέμ Νοέμ 08, 2018 12:58 am

Δημήτρη διάβασα το επιχείρημα σου όπως και το επιχείρημα του Μοαχοβάκη το οποίο αν και το είχα δει παλαιότερα το είχα ξεχάσε (την παραπομπή στο οικείο κεφάλαιο "ΕΠΙΛΟΓΕΣ" την έκανα βιαστικά από τον πίνακα περιεχομένων του pdf). Όντας σπίτι και έχοντας το βιβλίο διάβασα προσεκτικά το μέρος στο οποίο αναφέρεσαι. Υπάρχει ακόμη ένα σημείο που δεν καταλαβαίνω. Γιατί πρέπει να καταφύγουμε στο αξίωμα της (έστω αριθμήσιμης) επιλογής και να μην ορίσουμε την επιθυμητή αντιστοίχιση n\rightarrow \pi _{n} με επαγωγή αφού στο βήμα n\rightarrow n+1 μπορούμε να επικαλεσθούμε, κάθε φορά, την ύπαρξη μιας \pi _{n}; Κάτι που φαντάζει βέβαια προφανές. Μήπως και αυτό είναι ο λόγος που οι συγγραφείς που δεν χρησιμοποιούν το αξίωμα της επιλογής δεν κάνουν κάποια σαφή μνεία; Βλέπω ότι ο Halmos στο βιβλίο του "Αφελής Συνολοθεωρία" (Κεφ. 23 σελίδα 136 της Ελληνικής έκδοσης) μολονότι έχει προηγηθεί το Αξίωμα της επιλογής δεν το αναφέρει ρητά. Πάντως θα το ξανακοιτάξω το θέμα. Σε αυτά τα ζητήματα είμαι πάντα ανήσυχος μήπως κάνω λάθος. Ήδη έχω κάνει τρία τέτοια λάθη σε αυτή την περιοχή στο mathematica την δεκαετία που μας πέρασε και τα θυμάμαι. :wallbash: Το ένα μάλιστα ήταν με αφορμή μια λύση που είχες δώσει εσύ.


Αν κανείς δεν ελπίζει, δεν θα βρεί το ανέλπιστο, οι δρόμοι για το ανεξερεύνητο θα είναι κλειστοί.
Ηράκλειτος
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7884
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: αριθμήσιμο σύνολο

#14

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Νοέμ 08, 2018 10:28 am

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

Ας πάμε στην πιο «απλή» περίπτωση όπου θέλουμε να αποδείξουμε την αριθμήσιμη επιλογή. Έχουμε δηλαδή μη κενά σύνολα A_1,A_2,\ldots και θέλουμε να δείξουμε ότι υπάρχει συνάρτηση f:\mathbb{N} \to \cup A_i ώστε f(n) \in A_n για κάθε n \in \mathbb{N}.

Ο λόγος που δεν μπορώ να χρησιμοποιήσω επαγωγή, τουλάχιστον όχι με τον προφανή τρόπο, είναι ότι δεν μπορώ να βρω μια πρόταση P(n) ώστε αν δείξω ότι «για κάθε n \in \mathbb{N} ισχύει η P(n)» τότε θα έχω το ζητούμενο.

Π.χ. αν η P(n) είναι η πρόταση «Υπάρχει a_n \in \cup A_i ώστε a_n \in A_n» τότε το \forall n \, P(n) δεν μου δίνει την ύπαρξη συνάρτησης αλλά ότι όλα τα A_n είναι μη κενά.

Μπορώ να πάρω ως P(n) την πρόταση «Υπάρχει f:\{1,2,\ldots,n\} \to \cup A_i ώστε f(k) \in A_k για κάθε k \in \{1,2,\ldots,n\}»

Αυτό αποδεικνύεται επαγωγικά όπως εξήγησες αλλά πάλι το \forall n \, P(n) δεν δίνει μία συνάρτηση που ορίζεται στο \mathbb{N} αλλά πολλές συναρτήσεις οι οποίες ορίζονται σε πεπερασμένα σύνολα.

Θα θέλαμε να πούμε: «Ναι αλλά αν ονομάσω με f_n την συνάρτηση στο \{1,2,\ldots,n\} όχι μόνο υπάρχουν συναρτήσεις αλλά μπορώ να τις πάρω με τέτοιο τρόπο ώστε f_n(k) = f_m(k) για κάθε k \leqslant m,n. Και μετά μπορώ να ορίσω την συνάρτηση f στο \mathbb{N} ώστε f(k) = f_k(k).» Δυστυχώς όμως ούτε αυτό δουλεύει. Διότι πάλι δεν μπορώ να βρω κατάλληλη πρόταση P(n) η οποία να περικλείει το «f_n(k) = f_m(k) για κάθε k \leqslant m,n».

Η μη εύρεση κατάλληλης P(n) δεν είναι απλά αδυναμία δική μας. Έχει αποδειχθεί ότι το αξίωμα της αριθμήσιμης επιλογής είναι ανεξάρτητο του ZF.

Παρεμπιπτόντως το επιχείρημα που χρησιμοποίησες (αφού βρήκα αυτό που θέλω για το n=k βρίσκω μετά για το n=k+1 και εν τέλει τα παίρνω όλα μαζί) είναι ουσιαστικά το Axiom of Dependent Choice το οποίο είναι πιο ισχυρό από το Axiom of Countable Choice και λέει το εξής:

Έστω ότι έχουμε ένα μη κενό σύνολο A και μια σχέση R στο A. Έστω επίσης ότι για κάθε x \in A υπάρχει y \in A ώστε xRy. Τότε μπορώ να βρω μια ακολουθία (a_n) από στοιχεία του A ώστε a_nRa_{n+1} για κάθε n \in \mathbb{N}.


Απάντηση

Επιστροφή σε “Μαθηματική Λογική & Θεμέλια Μαθηματικών”

Μέλη σε σύνδεση

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