ένα προς ένα και επί συναρτήσεις

Συντονιστές: achilleas, emouroukos, silouan

Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 11231
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

ένα προς ένα και επί συναρτήσεις

#1

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Σάβ Ιουν 09, 2018 4:07 pm

Έστω f,g: \mathbb N \rightarrow \mathbb N δύο συναρτήσεις με f επί και g 1-1. Αν f(n) \ge g(n) για κάθε n\in \mathbb N, δείξτε ότι f=g.

Ισχύει το ίδιο αν στην θέση του  \mathbb N είχαμε το  \mathbb Z;

Ισχύει το ίδιο αν η ανισότητα ήταν ανάποδα;

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



Λέξεις Κλειδιά:
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 790
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: ένα προς ένα και επί συναρτήσεις

#2

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Σάβ Ιουν 09, 2018 11:16 pm

1) Θα χρησιμοποιήσουμε επαγωγή.

Λόγω του ότι η f είναι επί, έχουμε πως υπάρχει s_0, ώστε f(s_0)=0. Θα είναι g(s_0)\leq 0, επομένως g(s_0)=0=f(s_0) αναγκαστικά, αφού η τελευταία παίρνει μόνο μη αρνητικές ακέραιες τιμές.

Θα υπάρχει ακόμη s_1, ώστε f(s_1)=1. Προφανώς θα είναι s_1\ne s_0 (αφού η f είναι συνάρτηση). Θα είναι g(s_1)\leq 1, επομένως g(s_1)=1 ή g(s_1)=0. Αν ήταν όμως g(s_1)=0, θα έπρεπε s_1=s_0, άτοπο. Άρα g(s_1)=1=f(s_1).

Έστω τώρα πως ισχύει g(s_i)=i=f(s_i) με 0\leq i<k.

Προφανώς θα υπάρχει s_k, με f(s_k)=k, με s_k διάφορο με κάθε s_j, όπου 0\leq j<k. Έστω πως δεν ισχύει ότι g(s_k)=k. Λόγω του ότι g(s_k)\leq k, Θα ισχύει ότι g(s_k)=l, με l<k. Όμως g(s_l)=l, άρα από το γεγονός ότι η g είναι 1-1 συμπεραίνουμε πως s_k=s_l, άτοπο.

Ταυτόχρονα η f πρέπει να είναι 1-1. Έστω πως υπήρχε m, ώστε f(s_m)=m και f(s'_m)=m, με s_m\neq s'_m. Τότε θα ήταν g(s_m)=m=g(s'_m) , άρα s_m=s'_m, άτοπο.

Αφού λοιπόν η f είναι και 1-1 και επί, το σύνολο όλων των s_i ταυτίζεται με αυτό των μη αρνητικών ακεραίων, επομένως f(n)=g(n) για όλα τα n, όπου n\geq 0.

2) Όχι. Ένα αντιπαράδειγμα είναι f(n)=n και g(n)=n-1 με n ακέραιο. Ισχύει προφανώς ότι f(n)>g(n).

3) Υποθέτω ότι το πεδίο ορισμού και το σύνολο τιμών είναι το \mathbb N. Η απάντηση είναι όχι. Ένα αντιπαράδειγμα είναι g(n)=n για n μη αρνητικό ακέραιο και f(n)=n αν n άρτιος μη αρνητικός ακέραιος και f(n)=n-1 αν n περιττός μη αρνητικός ακέραιος. Ισχύει ότι g(n)\geq f(n), αλλά δεν είναι f=g.


Houston, we have a problem!
Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 11231
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: ένα προς ένα και επί συναρτήσεις

#3

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Σάβ Ιουν 09, 2018 11:38 pm

:10sta10:

Ένα πιο απλό παράδειγμα για το
Διονύσιος Αδαμόπουλος έγραψε:
Σάβ Ιουν 09, 2018 11:16 pm
...
3) Υποθέτω ότι το πεδίο ορισμού και το σύνολο τιμών είναι το \mathbb N. Η απάντηση είναι όχι. Ένα αντιπαράδειγμα είναι g(n)=n για n μη αρνητικό ακέραιο και f(n)=n αν n άρτιος μη αρνητικός ακέραιος και f(n)=n-1 αν n περιττός μη αρνητικός ακέραιος. Ισχύει ότι g(n)\geq f(n), αλλά δεν είναι f=g.
είναι το f(n)=n, \, g(n)=n+1 για κάθε n.


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

Re: ένα προς ένα και επί συναρτήσεις

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Ιουν 10, 2018 11:09 am

Κάπως πιο σύντομα για το πρώτο:

Έστω ότι δεν ισχύει το ζητούμενο. Άρα υπάρχει ελάχιστος φυσικός k, ώστε για κάποιο φυσικό n να είναι f(n) = k αλλά g(n) \neq k. Επειδή η f είναι επί, για κάθε \ell < k, υπάρχει φυσικός n_{\ell} ώστε f(n_{\ell}) = \ell. Από τον ορισμό του k πρέπει και g(n_{\ell}) = \ell. Όμως n_{\ell} \neq n, και επειδή η g είναι ένα προς ένα, έχουμε g(n) \neq g(n_{\ell}) = \ell. Είναι και g(n) \neq k. Άρα g(n) > k = f(n), άτοπο.


Απάντηση

Επιστροφή σε “Άλγεβρα - Επίπεδο Θαλή/Ευκλείδη (Seniors)”

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

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