Equipotência de conjuntos

2 março 2010, 14:00 • José Félix Costa

Exercício : Mostre, exibindo a respectiva bijecção, que os seguintes conjuntos são equipotentes:
(a) Os números naturais e os números inteiros;
(b) Os intervalos ]0,1] e ]0,1[;
(c) Os números reais e o intervalo ]0,1[;
(d) Os números reais e o intervalo ]0,1];
(e) Os números reais e o intervalo ]0,+\infty[;
(f) As palavras binárias e os números naturais;
(g) As linguagens binárias infinitas e o intervalo ]0,1];
(h) As linguagens binárias infinitas e os números reais.

Exercício : Mostre que, para qualquer conjunto A, A e P(A) não são equipotentes.

TPC:
Exercício : Mostre, exibindo a respectiva bijecção, que os seguintes conjuntos são equipotentes:
(a) Os pares de números naturais e os números naturais (usando uma bijecção de grau não superior ao segundo);
(b) As sucessões de dígitos decimais e os números reais;
(c) As sequências binárias infinitas e os números reais.

Ordens de magnitude

2 março 2010, 12:30 • José Félix Costa

Ordens de magnitude: O(.), o(.), Ómega_infinito(.), ómega(.), Teta(.).
Caracterização de o(.) por limite.
Proposição : f in Teta(g) se e só se f in O(g) e g in O(f).
Proposição : Um conjunto A tem densidade subexponencial se e só se a sua função de censo C_A verifica C_A(p(n)) in o(2^n), para todo o polinómio não decrescente p.
Definição da função log* --- estudo do seu crescimento.
Proposição : n in o(n.log*n) e n/log*n in o(n).
Ordens de magnitude relativas a classes de funções: O(.), o(.), Ómega_infinito(.), ómega(.), Teta(.).
Absorção de Teta pelas ordens O(.), o(.), Ómega_infinito(.), ómega(.).
Proposição : Para toda a função f, f in Teta(2^|log f|).
Proposição : Para todo o par de funções f e g, f in O(g) ou f in ómega(g), mas não ambos os casos; f in Ómega_infinito(g) ou f in o(g), mas não ambos os casos.
Proposição : Relativização do resultado anterior a classes de funções.

Recenseamento de um conjunto

26 fevereiro 2010, 14:30 • José Félix Costa

Alfabetos e conjuntos ( linguagens).
Conjuntos tally.
Recenseamento de um conjunto. Conjunto esparso. Densidades: linear, polinomial, subexponencial e exponencial --- intuições. Conjunto com densidade simétrica.
Proposição : Todo o conjunto tally é esparso.
Exemplos de conjuntos esparsos.
Classe dos complementos de uma classe. Prop's e co-prop's.
Proposição : Dadas classes de linguagens C_1 e C_2 sobre o mesmo alfabeto, C_1 incl. C_2 se e só se co-C_1 incl. co-C_2; em particular C_1 incl. co-C_1 se e só se C_1 = co-C_1.