Setul 4

Exercițiul 1: Demonstrați că mulțimea tuturor șirurilor finite formate cu un alfabet numărabil e numărabilă.

Un alfabet numărabil e o mulțime numărabilă de simboluri (caractere) { c₁, c₂, ... }.

Indicație: Găsiți o modalitate de a da un număr fiecărui șir, astfel încât să existe doar un număr finit de șiruri are au un număr dat. Descrieți apoi ordinea în care enumerați șirurile.

Alternativă: arătați (prin inducție după n) că mulțimea șirurilor de lungime n e numărabilă. Apoi arătați (folosind un tabel bidimensional ca la numerele raționale) că reuniunea unei mulțimi numărabile de mulțimi numărabile e numărabilă.

Exercițiul 2 Scrieți o funcție care returnează mulțimea tuturor divizorilor unui număr pozitiv n dat ca argument.

Folosiți o funcție auxiliară care acumulează într-un parametru mulțimea divizorilor găsiți și mai are ca parametru divizorul încercat la pasul curent.

Evitați teste de divizibilitate inutile (cu numere > radical din n)

Scrieți apoi funcția de cel mai mare divizor comun în două feluri: cu algoritmul lui Euclid, și obținând maximul dintre divizorii comuni. Verificați pe câteva exemple că dă același rezultat.