Insiemi vuoti, finiti o infiniti?

Polinomi, disuguaglianze, numeri complessi, ...
Rispondi
Nadal21

Insiemi vuoti, finiti o infiniti?

Messaggio da Nadal21 »

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} $.
RiccardoKelso

Re: Insiemi vuoti, finiti o infiniti?

Messaggio da RiccardoKelso »

Primo punto:
Testo nascosto:
$F_{100}$ è infinito, sia infatti $\forall k\in \mathbb{Z}$ dispari, $f_k:\mathbb{Z} \to \mathbb{Z}$ così definita:
$f_k(n)=\left\{\begin{array}{ll}n+50+k& \textrm{ se $n$ è dispari }\\
n+50-k&\textrm{ se $n$ è pari }\end{array}\right.$
Secondo punto:
Testo nascosto:
$F_{101}$ è l'insieme vuoto. Ipotizziamo per assurdo che esista una $g$ che soddisfi. Essendo $g\cdot g$ biunivoca, anche $g$ deve esserlo. Possiamo allora scrivere $g(n)=g(g(g^{-1}(n)))=g^{-1}(n)+101$, e anche $g^{-2}(n)=n-101$, da cui $g^{-1}(n)=g(n-101)$. Si deduce $g(n-101)=g(n)-101$. In particolare è quindi vero che $n\equiv m\space (101) \Leftrightarrow g(n) \equiv g(m)\space (101)$, mentre vale anche ovviamente $n\equiv m\space (101) \Leftrightarrow g^2(n)\equiv g^2(m)\space (101)$. Viene quindi ben definita in modo naturale una funzione $G:\mathbb{Z}/_{101\mathbb{Z}}\to \mathbb{Z}/_{101\mathbb{Z}}$. $G$ deve inoltre essere un'involuzione ed è definita su un insieme di cardinalità dispari, deve quindi ammettere punti fissi. Ma allora $\exists n\in \mathbb{Z} | \exists r\in \mathbb{Z} | g(n)=n+r101$, da cui $n+101=g(n)+r101$, cioè $r=\frac{1}{2}$, assurdo dato che $\frac{101}{2} \notin \mathbb{Z}$.
Avatar utente
Federico II
Messaggi: 230
Iscritto il: 14 mag 2014, 14:56
Località: Roma

Re: Insiemi vuoti, finiti o infiniti?

Messaggio da Federico II »

Bonus: farlo in generale con $f^m(n)=n+k$, dove $m,k$ sono interi fissati, con $m>0$.
Il responsabile della sala seminari
RiccardoKelso

Re: Insiemi vuoti, finiti o infiniti?

Messaggio da RiccardoKelso »

$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 :D
Nadal21

Re: Insiemi vuoti, finiti o infiniti?

Messaggio da Nadal21 »

grazie a tutti e due :D
Avatar utente
Federico II
Messaggi: 230
Iscritto il: 14 mag 2014, 14:56
Località: Roma

Re: Insiemi vuoti, finiti o infiniti?

Messaggio da Federico II »

Buona :D
Il responsabile della sala seminari
Rispondi