Sumários
P11-T2 Décima primeira aula prática (Turma 2)
30 novembro 2012, 08:00 • Francisco Miguel Alves Campos de Sousa Dionísio
Cardinalidade. Resolveram-se os seguints exercícios:
a) Mostre que o conjunto das linguagens binárias não é equipotente a N (Teorema de Cantor depois de ver que {0,1}*~N)
b) Mostre que N*N é equipotente a N
c) Mostre que ]0,1] não é equipotente a N (absurdo com argumento diagonal)
d) Mostre que o conjunto das funções de N em {0,1,...,9} não é equipotente a N
e) Mostre que o conjunto das linguagens binárias infinitas é equipotente a R (feito via ]0,1]).
TURMA 106: Argumentos de cardinalidade
29 novembro 2012, 09:30 • José Félix Costa
Bijeção entre {0,1}* e N, ordem lexicográfica, enumeração de máquinas de Turing, bijeção entre o conjunto das partes infinitas de {0,1}* e R.
Método da diagonalização.
Argumentos de cardinalidade.
TPC
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 números reais e o intervalo ]0,1[;
(c) Os números reais e o intervalo ]0,+\infty[;
(d) Os intervalos ]0,1[ e [0,1[;
(e) Os intervalos ]0,1[ e ]0,1];
(f) Os pares de números naturais e os números naturais (usando uma bijecção de grau não superior ao segundo);
(g) As palavras binárias e os números naturais;
(h) As linguagens binárias infinitas e o intervalo ]0,1];
(i) As linguagens binárias infinitas e os números reais;
(j) As sequências binárias infinitas e os números reais.
P11-T1 Décima primeira aula prática (Turma 1)
29 novembro 2012, 08:00 • Francisco Miguel Alves Campos de Sousa Dionísio
Cardinalidade. Resolveram-se os seguints exercícios:
a) Mostre que o conjunto das linguagens binárias não é equipotente a N (Teorema de Cantor depois de ver que {0,1}*~N)
b) Mostre que N*N é equipotente a N
c) Mostre que ]0,1] não é equipotente a N (absurdo com argumento diagonal)
d) Mostre que o conjunto das funções de N em {0,1,...,9} não é equipotente a N
e) Mostre que o conjunto das linguagens binárias infinitas é equipotente a R (feito via ]0,1]).