Sia $ \mathbb{Z} $ l'insieme dei numeri interi.
$ 1. $ Sia $ F_{100} $ l'insieme delle funzioni $ f : \mathbb{Z} \to \mathbb{Z} \quad $ tali che
$ f(f(n)) = n + 100 \quad $ per ogni $ n \in \mathbb{Z} $.
L'insieme $ F_{100} $ è vuoto? Oppur non è vuoto ed ha un numero finito di elementi? Oppure è infinito?
$ 2. $ Sia $ F_{101} $ l'insieme delle funzioni $ g : \mathbb{Z} \to \mathbb{Z} \quad $ tali che
$ g(g(n)) = n + 101 \quad $ per ogni $ n \in \mathbb{Z} $.
Rispondere alle stesse domande poste per $ F_{100} $.
Insiemi vuoti, finiti o infiniti?
Re: Insiemi vuoti, finiti o infiniti?
Primo punto:
Secondo punto:
Testo nascosto:
Testo nascosto:
- Federico II
- Messaggi: 230
- Iscritto il: 14 mag 2014, 14:56
- Località: Roma
Re: Insiemi vuoti, finiti o infiniti?
Bonus: farlo in generale con $f^m(n)=n+k$, dove $m,k$ sono interi fissati, con $m>0$.
Il responsabile della sala seminari
Re: Insiemi vuoti, finiti o infiniti?
$m \mid k$. Sia $r \in \mathbb{Z}|r\equiv 1\space (m)$. Si ha che $f_{m,k,r}(n)=\left\{\begin{array}{ll}n+k-r(m-1)&\textrm{ se $n \equiv 0 \space (m) $}\\n+r&\textrm{ se $n\not\equiv 0 \space (m) $}\end{array}\right.$ soddisfa, e ce ne sono ovviamente infinite.
$m\nmid k$. Ipotizziamo per assurdo che esista una $f_{m,k}$ verificante. Deve essere bigettiva, possiamo quindi scrivere $\forall s \in \mathbb{Z} , f^s(n)=f^m(f^{s-m}(n))=f^{s-m}(n)+k$. Ed anche, da $f^m(n)=n+k$, $f^{s-m}(n)=f^{-2m}(f^s(n+k))=f^s(n+k)-2k$. Si ricava allora $f^s(n)+k=f^s(n+k)$. Da cui $n_1\equiv n_2\space (k) \Leftrightarrow f^s(n_1) \equiv f^s(n_2)\space (k)$, insieme alla ovvia $n\equiv f^m(n)\space (k)$. Otteniamo quindi in modo naturale una funzione $F:\mathbb{Z}/_{k\mathbb{Z}}\to \mathbb{Z}/_{k\mathbb{Z}}$ che soddisfa $F^m=Id_{\mathbb{Z}/_{k\mathbb{Z}}}$. Definiamo su $A=\mathbb{Z}/_{k\mathbb{Z}}$ la seguente relazione d'equivalenza: $a_1,a_2\in A, a_1\sim a_2 \Leftrightarrow \exists t\in \mathbb{Z}, 0 \leq t<m | F^t(a_1)=a_2$. Le classi d'equivalenza hanno cardinalità che divide $m$, ma visto che $m\nmid k$ dev'essere che $\exists z\in \mathbb{Z}|\exists t\in \mathbb{Z}, 0\leq t<m|\exists r\in \mathbb{Z}|f^t(z)=z+rk$. Si vede facilmente che allora $\forall j\in \mathbb{N}, f^{jt}(z)=z+jrk$. Ma $z+mrk=f^{mt}(z)=z+tk$, da cui $mr=t$, assurdo.
Ringrazio per lo spunto
$m\nmid k$. Ipotizziamo per assurdo che esista una $f_{m,k}$ verificante. Deve essere bigettiva, possiamo quindi scrivere $\forall s \in \mathbb{Z} , f^s(n)=f^m(f^{s-m}(n))=f^{s-m}(n)+k$. Ed anche, da $f^m(n)=n+k$, $f^{s-m}(n)=f^{-2m}(f^s(n+k))=f^s(n+k)-2k$. Si ricava allora $f^s(n)+k=f^s(n+k)$. Da cui $n_1\equiv n_2\space (k) \Leftrightarrow f^s(n_1) \equiv f^s(n_2)\space (k)$, insieme alla ovvia $n\equiv f^m(n)\space (k)$. Otteniamo quindi in modo naturale una funzione $F:\mathbb{Z}/_{k\mathbb{Z}}\to \mathbb{Z}/_{k\mathbb{Z}}$ che soddisfa $F^m=Id_{\mathbb{Z}/_{k\mathbb{Z}}}$. Definiamo su $A=\mathbb{Z}/_{k\mathbb{Z}}$ la seguente relazione d'equivalenza: $a_1,a_2\in A, a_1\sim a_2 \Leftrightarrow \exists t\in \mathbb{Z}, 0 \leq t<m | F^t(a_1)=a_2$. Le classi d'equivalenza hanno cardinalità che divide $m$, ma visto che $m\nmid k$ dev'essere che $\exists z\in \mathbb{Z}|\exists t\in \mathbb{Z}, 0\leq t<m|\exists r\in \mathbb{Z}|f^t(z)=z+rk$. Si vede facilmente che allora $\forall j\in \mathbb{N}, f^{jt}(z)=z+jrk$. Ma $z+mrk=f^{mt}(z)=z+tk$, da cui $mr=t$, assurdo.
Ringrazio per lo spunto
- Federico II
- Messaggi: 230
- Iscritto il: 14 mag 2014, 14:56
- Località: Roma