Ricorsività di un insieme
Devo studiare la ricorsività dell'insieme:
$C=\{x\in\mathbb{N}: x=7^m+5n+3$ per qualche $m,n\in\mathbb{N}\}$
credo che dovrei dire se l'insieme è ricorsivo o ricorsivamente enumerabile, ma non ho molte idee su come si faccia..
Si può intuire a occhio la natura di questo insieme? Se si come?
Altrimenti potete spiegarmi quali sono le verifiche che devo fare? Per esempio per dire se è ricorsivo dovrei vedere se la sua funzione caratteristica è una funzione ricorsiva totale?
Grazie per l'aiuto!
$C=\{x\in\mathbb{N}: x=7^m+5n+3$ per qualche $m,n\in\mathbb{N}\}$
credo che dovrei dire se l'insieme è ricorsivo o ricorsivamente enumerabile, ma non ho molte idee su come si faccia..
Si può intuire a occhio la natura di questo insieme? Se si come?
Altrimenti potete spiegarmi quali sono le verifiche che devo fare? Per esempio per dire se è ricorsivo dovrei vedere se la sua funzione caratteristica è una funzione ricorsiva totale?
Grazie per l'aiuto!
Risposte
Vediamo di studiare un po' la funzione
$g(m, n) = 7^m + 5n + 3$.
Non è ovviamente suriettiva, ma vediamo se è iniettiva:
$g(m, n) = g(m', n')$,
$7^m + 5n + 3 = 7^{m'} + 5n' + 3$,
$7^m + 5n = 7^{m'} + 5n'$.
Proiettiamo questa uguaglianza in $ZZ/(5 ZZ)$ ottenendo
$7^m - 7^{m'} mod 5 = 0$
e supponendo che sia $m' - m = r > 0$ si ottiene
$7^m(1 - 7^r) mod 5 = 0$.
Siccome $7^m mod 5$ non può essere nulla, deve essere per forza
$1 = 7^r mod 5$.
Questa equazione è verificata se $r$ è un multiplo di $4$. Tornando ai numeri naturali possiamo allora affermare che se $m$ e $m'$ differiscono da un multiplo di $4$, allora la loro differenza è uguale a zero in $ZZ/(5 ZZ)$ ed esiste quindi un $k$ tale che (suppongo come prima $m' > m$)
$7^m + 5k = 7^{m'}$.
La funzione $g$ non è quindi iniettiva e varrà la relazione $g(m, n) = g(m mod 4, n + k)$ per $k = (7^m - 7^(m mod 4))/5$.
Viceversa, se $m$ ed $m'$ non differiscono da un multiplo di quattro deve per forza valere $g(m,n) != g(m', n')$. L'insieme $C$ è quindi unione disgiunta dei $4$ insiemi:
$C_0 = {x \in NN : x = 5n + 4, n \in NN}$,
$C_1 = {x \in NN : x = 5n + 10, n \in NN}$,
$C_2 = {x \in NN : x = 5n + 52, n \in NN}$,
$C_3 = {x \in NN : x = 5n + 346, n \in NN}$.
Dovrebbe essere ora evidente che esiste una funzione ricorsiva in grado di stabilire se $x \in C$.
$g(m, n) = 7^m + 5n + 3$.
Non è ovviamente suriettiva, ma vediamo se è iniettiva:
$g(m, n) = g(m', n')$,
$7^m + 5n + 3 = 7^{m'} + 5n' + 3$,
$7^m + 5n = 7^{m'} + 5n'$.
Proiettiamo questa uguaglianza in $ZZ/(5 ZZ)$ ottenendo
$7^m - 7^{m'} mod 5 = 0$
e supponendo che sia $m' - m = r > 0$ si ottiene
$7^m(1 - 7^r) mod 5 = 0$.
Siccome $7^m mod 5$ non può essere nulla, deve essere per forza
$1 = 7^r mod 5$.
Questa equazione è verificata se $r$ è un multiplo di $4$. Tornando ai numeri naturali possiamo allora affermare che se $m$ e $m'$ differiscono da un multiplo di $4$, allora la loro differenza è uguale a zero in $ZZ/(5 ZZ)$ ed esiste quindi un $k$ tale che (suppongo come prima $m' > m$)
$7^m + 5k = 7^{m'}$.
La funzione $g$ non è quindi iniettiva e varrà la relazione $g(m, n) = g(m mod 4, n + k)$ per $k = (7^m - 7^(m mod 4))/5$.
Viceversa, se $m$ ed $m'$ non differiscono da un multiplo di quattro deve per forza valere $g(m,n) != g(m', n')$. L'insieme $C$ è quindi unione disgiunta dei $4$ insiemi:
$C_0 = {x \in NN : x = 5n + 4, n \in NN}$,
$C_1 = {x \in NN : x = 5n + 10, n \in NN}$,
$C_2 = {x \in NN : x = 5n + 52, n \in NN}$,
$C_3 = {x \in NN : x = 5n + 346, n \in NN}$.
Dovrebbe essere ora evidente che esiste una funzione ricorsiva in grado di stabilire se $x \in C$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo