Logică și structuri discrete - Exericiții cu mulțimi

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.