Μία 1-1 και επί απεικόνιση

#1

Δεν είνα άγνωστη. Αλλά είναι ενδιαφέρουσα.

'Εστω $S=\left\{ \left( x,y\right) \in \mathbb{N}^{\ast }\times \mathbb{N}^{\ast }|x\geq y\right\}$ και $\varphi :S\rightarrow \mathbb{N}^{\ast }$ με
$\dispalystyle \varphi \left( n,m\right) =\frac{n\left( n-1\right) }{2}+m$ .
Να αποδειχθεί ότι η $\varphi$ είναι 1-1 και επί.

#2

nsmavrogiannis έγραψε: ↑
Κυρ Νοέμ 21, 2021 12:26 am
Δεν είνα άγνωστη. Αλλά είναι ενδιαφέρουσα.

'Εστω $S=\left\{ \left( x,y\right) \in \mathbb{N}^{\ast }\times \mathbb{N}^{\ast }|x\geq y\right\}$ και $\varphi :S\rightarrow \mathbb{N}^{\ast }$ με
$\dispalystyle \varphi \left( n,m\right) =\frac{n\left( n-1\right) }{2}+m$ .
Να αποδειχθεί ότι η $\varphi$ είναι 1-1 και επί.

Θυμίζει το επιχείρημα Cantor.

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

....

(κόκκινη γραμματοσειρά) πηγαίνοντας από πάνω δεξιά προς τα κάτω αριστερά.

Η κόκκινη γραμμή με την ένδειξη k περιέχει βέβαια k όρους.

Tο στοιχείο (n,m)

βρίσκεται εκ κατασκευής στην

κόκκινη γραμμή και μάλιστα

θέσεις κάτω. 'Αρα α) προηγούνται οι $1+2+...+(n-1) = \frac {1}{2}(n-1)n$ αριθμοί στις προηγούμενες n-1

κόκκινες γραμμές, β) ο ίδιος είναι

οστός στην γραμμή του. Άρα η αρίθμηση του (n,m)

στην διάταξη είναι $\frac {1}{2}(n-1)n+m$ .

Με την διάταξη αυτή είναι σαφές ότι κάθε ζεύγος (n,m)

με $n\ge m$ έχει απαριθμηθεί, και μάλιστα ακριβώς μία φορά. Με άλλα λόγια η απεικόνιση $\dispalystyle \varphi \left( n,m\right) =\frac{n\left( n-1\right) }{2}+m$ είναι α) επί (αφού η απαρίθμηση είναι 1,2,3,...

χωρίς να λείπει κανείς) και β) 1-1

αφού κάθε ζεύγος (n,m)

με $n\ge m$ είναι σε άλλη θέση στην απαρίθμηση.

#3

Δίνω και αλγεβρική λύση.

Έστω $\frac {1}{2} n(n-1) +m = \frac {1}{2} n'(n'-1) +m'$ όπου $n\ge m$ και $n'\ge m'$ . Θα δείξουμε ότι $n=n',\, m=m'$ (αυτο είναι το 1-1

.

Πράγματι, αν $n\ne n'$ θα ήταν χωρίς βλάβη n>n'

, οπότε και $n\ge n'+1$ . Aλλά τότε

$\frac {1}{2} n(n-1) +m > \frac {1}{2} n(n-1) \ge \frac {1}{2} (n'+1)n' = \frac {1}{2} (n'-1)n'+ n' \ge \frac {1}{2} (n'-1)n'+m'$ , που αντιβαίνει στην υπόθεση.

Για το επί: Έστω $N\in \mathbb N^*$ . Ο

αυτός βρίσκεται σε κάποιο από τα διαδοχικά διαστήματα $(0,\, 1], \, (1,\, 1+2], \, (1+2,\, 1+2+3] ,\, ...$ . Έστω στο $(1+2+...+n-1,\, 1+2+...+n]$ , δηλαδή ισχύει $1+2+...+n-1<N \le 1+2+...+n$ . Είναι λοιπόν $N - (1+2+...+n-1) \le n$ . Θέτουμε m= N - (1+2+...+n-1)

, οπότε $0<m \le n$ και βέβαια $N= (1+2+...+n-1)+m= \frac {1}{2}n(n-1) +m$ , όπως θέλαμε.

#4

Γεια σας

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

Έστω $\left( a_{n}\right)$ μια γνησίως αύξουσα ακολουθία φυσικών αριθμών με $a_{1}=0$ . Προφανώς $a_{n}\rightarrow +\infty$ και η κλάση διαστημάτων $(a_{n},a_{n+1}]$ αποτελεί διαμέριση του $\mathbb{N}^{\ast }$ . Κάθε θετικός ακέραιος

γράφεται κατά μοναδικό τρόπο $y=a_{n}+m$ όπου $m=y-a_{n}$ και επομένως $1 \leq m \leq a_{n+1}-a_{n}$ . Αν πάρουμε $a_n=\frac{n(n-1)}{2}$ έχουμε $a_{n+1}-a_{n}=n$ και επομένως για κάθε θετικό ακέραιο

υπάρχουν μοναδικοί θετικοί ακέραιοι

και $m \leq m$ ώστε $\frac{n(n-1)}{2}+m=y$ που αποδεικνύει το ζητούμενο.

Βρίσκω ενδιαφέρον ότι αν αλλάξουμε την $a_{n}$ βρίσκουμε αμφεικονίσεις διαφόρων υποσυνόλων του $\mathbb{N}^{\ast }\times \mathbb{N}^{\ast }$ επί του $\mathbb{N}^{\ast }$ .

Πυθαγόρεια Τριάδα · #5

Πράγματι, το θέμα αυτό είναι ενδιαφέρον.

Θεωρούμε τη ακολουθία ${(x_{n})}^{\infty}_{n=1} \subset \mathbb{N}$ , όπου $x_{n} = \frac{n(n+1)}{2}$ .Είναι προφανές ότι η ακολουθία αυτή είναι γνησίως αύξουσα. Για $n \geq 2}$ ορίζουμε $y_{n} = \frac{n(n-1)}{2} - \frac{(n-1)(n-2)}{2}$ .

Μετά από πράξεις καταλήγουμε στο ότι $y_{n} = n-1$ , που σημαίνει ότι η διαφορά μεταξύ δύο διαδοχικών όρων της ακολουθίας $x_{n}$ δεν είναι άνω φραγμένη.

Σύμφωνα λοιπόν με τα παραπάνω, αν ορίσουμε

$X_{n} = [x_{n}, x_{n+1}) \cap \mathbb{N}$

η οικογένεια $\{X_{n} : n \in \mathbb{N}\}$ ορίζει μια διαμέριση του $\mathbb{N}$ , για την οποία κάθε μέλος της διαμέρισης είναι πεπερασμένα αριθμήσιμο, και η ακολουθία ${(|X_{n}|)}^{\infty}_{n = 1}$ είναι μια γνησίως αύξουσα ακολουθία φυσικών αριθμών, με $|X_{n}| \geq 2$ για κάθε $n \geq 2$ . Θεωρούμε τώρα $k \in \mathbb{N}$ τυχόν. Θα διακρίνουμε τις ακόλουθες περιπτώσεις.

Έστω ότι $k \notin \{x_{n} : n\in \mathbb{N}\}$ . Τότε, υπάρχει φυσικός αριθμός $n_{0} \geq 2$ τέτοιο ώστε $k \in X_{n_{0}}$ . Από γνωστές ιδιότητες της διαμέρισης ${X_{n}}$ έχουμε ότι η απόσταση του από το $x_{n_{0}}$ είναι ένας μη μηδενικός φυσικός αριθμός, ο οποίος είναι μικρότερος του $x_{n_{0}}$ (προκύπτει άμεσα ως ιδιότητα της ακολουθίας ${y_{n}}$ που ορίσαμε προηγουμένως). Αν είναι η απόσταση αυτή. 'Εχουμε λοιπόν ότι $k = x_{n_{0}} + m$ όπου $x_{n_{0}} > m$ . Άρα $\phi(x_{n_{0}},m) = k$ .

Έστω ότι $\exists n_{0} \in \mathbb{N}(k = x_{n_{0}})$ . Στην περίπτωση όπου $n_{0} = 1$ είναι προφανές ότι $\phi(1,1) = k=1$ . Ας υποθέσουμε λοιπόν, για την αποφυγή τετριμμένων καταστάσεων, ότι $n_{0} \geq 2$ . Τότε, σύμφωνα με τον ορσιμό της ακολουθίας ${x_{n}}$ έχουμε ότι $k = x_{n_{0} - 1} + (n_{0}-1)$ , όπου όπως επισημάναμε στη προηγούμενη περίπτωση έχουμε ότι $x_{n_{0} -1} \geq n_{0} - 1$ . Άρα $\phi(x_{n_{0} - 1}, n_{0} - 1) = k$ .

Σύμφωνα λοιπόν με τα παραπάνω διαπιστώνουμε ότι

$\forall k \in \mathbb{N^{*}} \exists!(n,m) \in S(\phi(n,m) = k)$

Δηλαδή, η συνάρτηση $\phi$ είναι αμφιμονοσήμαντη.