Cardinalidade dos Conjuntos não Contáveis

- Cardinalidade dos conjuntos não contáveis.

        Nem todos os conjuntos não contáveis têm a mesma cardinalidade.

Estendendo o conceito de contagem ao infinito, pode-se dizer que um conjunto A tem, pelo menos, tantos elementos quanto um conjunto B, ou seja, que: #A  #B, quando existe uma função injetora f:A  B. Para que a relação  entre as cardinalidades seja uma relação de ordem parcial, ela deve ser:[pic 1][pic 2][pic 3]

- reflexiva, ou seja, #A  #A.[pic 4]

- transitiva, ou seja, #A  #B e #B  #C, então #A  #C.[pic 5][pic 6][pic 7]

- antissimétrica, ou seja, se #A  #B e #B  #A, então #A = #B.[pic 8][pic 9]

          Um resultado que garante que existem cardinais não contáveis em quantidade infinita é o fato de que o conjunto das partes de um conjunto tem sempre cardinalidade maior que este. Esse fato é conhecido como teorema de Cantor, apresentado a seguir. Lembrar que: n < m  n  m ˄ n  m.[pic 10][pic 11][pic 12]

- Teorema de Cantor:

        Seja C um conjunto e  o conjunto das partes de C. Então:[pic 13]

        #C < #.[pic 14]

- Cardinal.

          Um cardinal é uma classe de equivalência de conjuntos equipotentes.

Dessa forma, a classe dos cardinais é a classe de todas as classes de equivalência dos conjuntos equipotentes.

Em geral utiliza-se a primeira letra do alfabeto hebraico א (lê-se: “alef”) com índices para indicar cardinais infinitos conhecidos. De especial interesse para ciência da computação é o  cardinal do conjunto dos números naturais N, denotado por . Assim, o cardinal de qualquer conjunto contável (infinito) é . De fato  é o menor cardinal dos conjuntos infinitos.[pic 15][pic 16][pic 17]

- Cardinal do conjunto de todos os problemas solucionáveis.