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) { c1, c2, ... }.
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.