Περασμένα ναι, ξεχασμένα όχι(:)!

#1

Καλησπέρα!
Ξέρω ότι είναι περασμένα πράγματα όμως οι τεχνικές που χρησιμοποιούνται πιστεύω πως είναι όμορφες να υπάρχουν ακόμη
και να απασχολούν τη σκέψη μας.
Να αποδείξετε ότι κάθε υποσύνολο ενός πεπερασμένου συνόλου είναι πεπερασμένο.

Tolaso J Kos · #2

chris_gatos έγραψε: ↑
Παρ Ιαν 11, 2019 6:32 pm
Να αποδείξετε ότι κάθε υποσύνολο ενός πεπερασμένου συνόλου είναι πεπερασμένο.

Ορισμός 1: Δύο σύνολα A, B

είναι ισοδύναμα αν υπάρχει bijection μεταξύ τους.

Ορισμός 2: Ορίζουμε $\mathbb{Z}_n =\{ \kappa \in \mathbb{Z}_+: \kappa\leq n \}$ . Ένα σύνολο που είναι υποσύνολο με κάποιο $\mathbb{Z}_n$ είναι πεπερασμένο.

Αποδεικνύουμε τη παρακάτω πρόταση:

Πρόταση: Έστω $g:A\rightarrow B$ bijection. Αν $B \subseteq C$ τότε η $f:A\rightarrow C$ που ορίζεται ως f(a)=g(a)

για κάθε $a\in A$ είναι injection.

Απόδειξη: Υποθέτουμε ότι f(a_1)=f(a_2)

. Από τον ορισμό της

,

και

. Τότε ,

. Οπότε

. Εφόσον η

είναι injection , τότε a_1=a_2

και άρα η

είναι injection.

Πρόταση: Έστω

πεπερασμένο σύνολο και $B \subseteq A$ . Τότε το

είναι πεπερασμένο.

Απόδειξη: Εφόσον το

είναι πεπερασμένο , τότε υπάρχει bijection μεταξύ αυτού και κάποιου υποσυνόλου του $\mathbb{Z}_n$ . Από τη παραπάνω πρόταση υπάρχει injection $f:A\rightarrow \mathbb{Z}_n$ . O περιορισμός της

στο

είναι injection στο $\mathbb{Z}_n$ . Η συνάρτηση $g:B \rightarrow Im (f|B)$ είναι καθαρά bijection. Αρκεί να δείξουμε ότι $Im(f|B) \subseteq \mathbb{Z}_n$ . Καταρχάς, $Im(f|B) \subseteq Im(f)$ . Επιπλέον,

$\displaystyle{Im(f|B)=\{n\in\mathbb{Z}_{n}:\exists b\in B |n=f|B(b)\}}$
Έστω $n \in Im(f|B)$ . Τότε υπάρχει $b \in B : f|B(b)=n$ . Εφόσον f|B(b)=f(b)

για $b \in B$ υπάρχει $b \in B | f(b) =n$ . Επειδή $B \subseteq A$ , τότε υπάρχει $b \in A$ τέτοιο ώστε f(b)=n

. Άρα $n \in Im(f)$ . Συνεπώς $Im(f|B)\subseteq Im(f) \subseteq \mathbb{Z}_n$ . Η απόδειξη ολοκληρώθηκε.

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #3

chris_gatos έγραψε: ↑
Παρ Ιαν 11, 2019 6:32 pm
Καλησπέρα!
Ξέρω ότι είναι περασμένα πράγματα όμως οι τεχνικές που χρησιμοποιούνται πιστεύω πως είναι όμορφες να υπάρχουν ακόμη
και να απασχολούν τη σκέψη μας.
Να αποδείξετε ότι κάθε υποσύνολο ενός πεπερασμένου συνόλου είναι πεπερασμένο.

Θεωρώ ότι υπάρχουν πολλές απαντήσεις.
Σε Πανεπιστημιακές σημειώσεις εισαγωγικής θεωρίας συνόλων (όχι αυστηρής)
θεωρείται προφανές.

Για αυστηρή απόδειξη υπάρχουν δύο προβλήματα.
1) Ο ορισμός του πεπερασμένου συνόλου.

Από ότι βλέπω τα περισσότερα σύγχρονα βιβλία θεωρίας συνόλων έχουν
τον παρακάτω ορισμό.

Το σύνολο

λέγεται πεπερασμένο αν και μόνο αν
υπάρχει $n\in \mathbb{N}$
και 1-1 και επί συνάρτηση $f:A\rightarrow n$

2)Αν δεχθούμε τον παραπάνω ορισμό πρέπει να ξέρουμε τον ακριβή ορισμό του $\mathbb{N}$

Για παράδειγμα είδα τον εξής ορισμό για πεπερασμένο σύνολο

Το σύνολο

λέγεται πεπερασμένο αν και μόνο αν
για κάθε 1-1 συνάρτηση $f:A\rightarrow A$
έχουμε f(A)=A

#4

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε: ↑
Παρ Ιαν 11, 2019 9:49 pm
Για παράδειγμα είδα τον εξής ορισμό για πεπερασμένο σύνολο

Το σύνολο λέγεται πεπερασμένο αν και μόνο αν
για κάθε 1-1 συνάρτηση $f:A\rightarrow A$
έχουμε

Θαυμάσιος ορισμός. Χάριν πληρότητας ας δούμε, αν και απλό, μία απόδειξη της προταθείσας άσκησης με βάση αυτόν τον ορισμό.

Έστω

πεπερασμένο και $B \subset A$ . Έστω ακόμα $g:B\rightarrow B$ μία 1-1 συνάρτηση, την οποία θέλουμε να δείξουμε ότι είναι επί.

Την επεκτείνουμε σε όλο το

θέτοντας

αν $b\in B$ και h(a)=a

για κάθε $a\in A-B$ . Εύκολα βλέπουμε ότι η

είναι 1-1, άρα επί αφού

πεπερασμένο.

Έστω τώρα $b\in B$ . Από το προηγούμενο υπάρχει $c\in A$ με h(c) =b

. Αποκλείεται $c\in A-B$ γιατί τότε $c=h(c)=b\in B$ , άτοπο. Άρα $c\in B$ οπότε b=h(c)=g(c)

δείχνοντας ότι η

είναι επί.

Tolaso J Kos · #5

Ας παραθέσει κάποιος και κάποια απόδειξη με την αρχή της περιστεροφωλιάς.

#6

Mihalis_Lambrou έγραψε: ↑
Παρ Ιαν 11, 2019 11:18 pm

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε: ↑
Παρ Ιαν 11, 2019 9:49 pm
Για παράδειγμα είδα τον εξής ορισμό για πεπερασμένο σύνολο

Το σύνολο λέγεται πεπερασμένο αν και μόνο αν
για κάθε 1-1 συνάρτηση $f:A\rightarrow A$
έχουμε
Θαυμάσιος ορισμός. Χάριν πληρότητας ας δούμε, αν και απλό, μία απόδειξη της προταθείσας άσκησης με βάση αυτόν τον ορισμό.

Είναι ισοδύναμος με τον ορισμό του Dedekind που λέει ότι ένα σύνολο

είναι άπειρο αν και μόνο αν υπάρχει ένα γνήσιο υποσύνολο

του

και μια ένα προς ένα και επί συνάρτηση $f:A \to B$ . Ένα σύνολο

είναι πεπερασμένο αν δεν είναι άπειρο.

Παρεμπιπτόντως ο συγκεκριμένος ορισμός δεν είναι ισοδύναμος στην ZF με τον συνήθη ορισμό που έδωσε ο Τόλης. Για να αποδείξουμε ότι ένα σύνολο είναι πεπερασμένο αν και μόνο αν είναι πεπερασμένο κατά Dedekind χρειάζεται μια μορφή του αξιώματος της επιλογής.

#7

Demetres έγραψε: ↑
Σάβ Ιαν 12, 2019 1:53 pm
Παρεμπιπτόντως ο συγκεκριμένος ορισμός δεν είναι ισοδύναμος στην ZF με τον συνήθη ορισμό που έδωσε ο Τόλης. Για να αποδείξουμε ότι ένα σύνολο είναι πεπερασμένο αν και μόνο αν είναι πεπερασμένο κατά Dedekind χρειάζεται μια μορφή του αξιώματος της επιλογής.

Βρήκα πολύ ωραία σύνοψη αυτής της πανέμορφης θεματολογίας εδώ. Αξίζει να τα δείτε.

Περασμένα ναι, ξεχασμένα όχι(:)!

Περασμένα ναι, ξεχασμένα όχι(:)!

Re: Περασμένα ναι, ξεχασμένα όχι(:)!

Re: Περασμένα ναι, ξεχασμένα όχι(:)!

Re: Περασμένα ναι, ξεχασμένα όχι(:)!

Re: Περασμένα ναι, ξεχασμένα όχι(:)!

Re: Περασμένα ναι, ξεχασμένα όχι(:)!

Re: Περασμένα ναι, ξεχασμένα όχι(:)!

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