Cardinalidade

Na matemática, a cardinalidade de um conjunto é uma medida do "número de elementos do conjunto". Por exemplo, o conjunto A={2,4,6} contém 3 elementos e por isso possui cardinalidade 3. Existem duas abordagens para cardinalidade - uma que compara conjuntos diretamente, usando funções bijetoras e funções injetoras, e outra que usa números cardinais^[1].

A cardinalidade de um conjunto A é usualmente denotada |A|, com uma barra vertical de cada lado; trata-se da mesma notação usada para valor absoluto, por isso o significado depende do contexto. A cardinalidade de um conjunto pode ser denotada ainda ${\displaystyle {\overline {\overline {A}}}\,}$ ou # A.

Dois conjuntos A e B possuem a mesma cardinalidade se existe uma bijeção, ou seja, uma função que seja simultaneamente injetora e sobrejetora, entre eles.

Por exemplo, o conjunto E={0, 2, 4, 6, ...} dos números pares não-negativos tem a mesma cardinalidade do conjunto N={0, 1, 2, 3, ...} dos números naturais, uma vez que a função f(n)=2n é uma bijeção de N para E.

A tem cardinalidade maior ou igual que a cardinalidade de B se existe uma função injetora de B para A.

A tem cardinalidade estritamente maior do que a cardinalidade de B se existe uma função injetora de B para A, mas não existe nenhuma função bijetora de B para A.

Por exemplo, o conjunto R de todos os números reais tem cardinalidade estritamente maior do que a cardinalidade do conjunto N de todos os números naturais pois a função identidade i:N→R, definida como i(x)=x, é injetora. Por outro lado, é possível demonstrar a inexistência de uma função bijetora de N para R (veja Argumento de Diagonalização de Cantor ou a Primeira Prova da Incontabilidade de Cantor).

Ver artigo principal: Número cardinal

Acima, "cardinalidade" foi definida de forma funcional. ou seja, a "cardinalidade" de um conjunto não foi definida como um objeto específico independente. No entanto, tal objeto pode ser definido como segue.

A relação de possuir a mesma cardinalidade é chamada equipotência, e ela é uma relação de equivalência sobre a classe de todos os conjuntos. A classe de equivalência de um conjunto A sob essa relação consiste, então, de todos os conjuntos que possuem a mesma cardinalidade de A. Existem duas formas de definir a "cardinalidade de um conjunto":

1. A cardinalidade de um conjunto A é definida como a sua classe de equivalência sob a equipotência.
2. Um conjunto representativo é designado para cada classe de equivalência. A escolha mais comum recai sobre o ordinal inicial da classe. Esta consiste, usualmente, na definição de número cardinal na teoria dos conjuntos.

As cardinalidades de conjuntos infinitos são denotadas:

${\displaystyle \aleph _{0}<\aleph _{1}<\aleph _{2}<\ldots .}$

Para cada ordinal α, ℵ_{α + 1} é o menor número cardinal maior do que ℵ_α.

A cardinalidade dos números inteiros é denotada aleph-zero (ℵ₀), enquanto que a cardinalidade dos números reais é denotada c, e também conhecida como cardinalidade do contínuo. É possível mostrar que c = 2^ℵ₀ ; esta também é a cardinalidade do conjunto de todos os subconjuntos dos números inteiros. A Hipótese do Contínuo diz que ℵ₁ = 2^ℵ₀, isto é, que 2^ℵ₀ é o menor número cardinal maior que ℵ₀, ou seja, que não existe conjunto cuja cardinalidade esteja situada estritamente entre a dos números inteiros e a dos números reais. A hipótese do contínuo permanece não-solucionada num sentido "absoluto"^[2]. Veja abaixo para mais detalhes sobre a cardinalidade do contínuo.

Caso o axioma da escolha seja verdadeiro, então a Lei da Tricotomia é verdadeira para a cardinalidade. Portanto, é possível fazer as seguintes definições:

• Qualquer conjunto X com cardinalidade menor que a do conjunto dos números naturais, ou | X | < | N |, é dito conjunto finito.
• Qualquer conjunto X que tenha a mesma cardinalidade do conjunto dos números naturais, ou | X | = | N | = ℵ₀, é denominado conjunto infinitamente contável.
• Qualquer conjunto X com cardinalidade maior que a do conjunto dos números naturais, ou | X | > | N |, por exemplo | R | = c > | N |, é denominado incontável.

A intuição obtida com os conjuntos finitos desaparece quando se lida com conjuntos infinitos. No final do século dezenove, Georg Cantor, Gottlob Frege, Richard Dedekind e outros, rejeitaram a ideia de Galileu (por sua vez derivada de Euclides) de que o todo não pode ter o mesmo tamanho da parte. Um exemplo disso é o Paradoxo do Hotel de Hilbert.

A razão disso é que as várias caracterizações do significado de um conjunto A ser maior do que um conjunto B, ou de ter o mesmo tamanho que um conjunto B, e que são todas equivalentes para conjuntos finitos, não são mais equivalentes para conjuntos infinitos. Diferentes caracterizações podem produzir resultados diferentes. Por exemplo, na caracterização popular de tamanho escolhida por Cantor, pode acontecer de um conjunto infinito A ser maior (nesse sentido) do que um conjunto infinito B; outras caracterizações podem dar como resultado que um conjunto infinito A tem sempre o mesmo tamanho de um conjunto infinito B.

Para conjuntos finitos, a contagem é apenas uma bijeção (correspondência um-para-um) entre o conjunto sendo contado e um segmento inicial dos inteiros positivos. Portanto, não existe noção equivalente para a contagem de conjuntos infinitos. Enquanto que, aplicada aos conjuntos finitos, a contagem produz um resultado único, um conjunto infinito pode ser colocado numa correspondência um-para-um com muitos números ordinais diferentes, dependendo de como se escolhe "contar" (ordenar) o mesmo.

Adicionalmente, diferentes caracterizações de tamanho, quando estendidas para conjuntos infinitos, irão violar diferentes regras válidas para conjuntos finitos. Quais regras serão violadas varia de caracterização para caracterização. Por exemplo, a caracterização de Cantor, que por um lado preserva a regra de que às vezes um conjunto é maior do que outro, viola a regra de que a exclusão de um elemento torna o conjunto menor. Outra caracterização poderia preservar a regra de que a exclusão de um elemento torna o conjunto menor, mas violaria outra regra. Além disso, uma caracterização pode não violar uma regra diretamente, mas ela pode também não sustentá-la diretamente, no sentido de que qualquer que seja o caso se dependa de um axioma controverso tal como o axioma da escolha ou a hipótese do contínuo. Portanto, existem três possibilidades. Cada caracterização violará algumas regras, manterá outras e será inconclusiva em relação a outras.

Se forem considerados os multiconjuntos, outras regras, válida para multiconjuntos finitos, serão violadas (considerando-se a abordagem de Cantor). Dados dois multiconjuntos A e B, A não sendo maior do que B, e B não sendo maior do que A, não necessariamente implica que A tem o mesmo tamanho de B. Essa regra é válida para multiconjuntos que sejam finitos. A lei de tricotomia é explicitamente violada nesse caso, em oposição ao caso dos conjuntos, onde ela é equivalente ao axioma da escolha.

Dedekind simplesmente definiu um conjunto infinito como sendo aquele que possui o mesmo tamanho (no sentido de Cantor) de pelo menos um subconjunto próprio seu. Essa noção de infinitude é denominada Infinito de Dedekind. Essa definição, no entanto, é válida apenas na presença de alguma forma do axioma da escolha, por isso ela não é considerada válida por alguns matemáticos.

Cantor introduziu os acima-mencionados números cardinais, e mostrou (no sentido de Cantor) que alguns conjuntos infinitos são maiores do que outros. A menor cardinalidade infinita é aquela dos números naturais (ℵ₀).

Um dos resultados mais importantes do trabalho de Cantor foi a demonstração de que a cardinalidade do contínuo (${\displaystyle {\mathfrak {c}}}$) é maior do que aquela dos números naturais (ℵ₀); ou seja, existem mais números reais em R do que números inteiros em N. Cantor provou que

${\displaystyle {\mathfrak {c}}=2^{\aleph _{0}}>{\aleph _{0}}}$

(veja Argumento de diagonalização de Cantor).

A Hipótese do Continuum diz que não existe número cardinal entre a cardinalidade dos números reais e a cardinalidade dos números naturais, ou seja,

${\displaystyle {\mathfrak {c}}=\aleph _{1}=\beth _{1}}$

(veja Número Beth 1)

No entanto, essa hipótese não pode ser nem provada nem refutada dentro da amplamente aceita Teoria Axiomática dos Conjuntos de ZFC, se ela for consistente.

A aritmética de cardinais pode ser usada para mostrar não apenas que o número de pontos na reta real é igual ao número de pontos em qualquer segmento dessa reta, mas também que esse número é igual ao número de pontos num plano e, também, em qualquer espaço dimensional finito. Esses resultados são altamente contra-intuitivos, pois eles implicam a existência de subconjuntos próprios e superconjuntos próprios de um conjunto infinito S que possuem o mesmo tamanho de S, apesar de S conter elementos que não pertencem aos seus subconjuntos e os superconjuntos de S conterem elementos que não estão incluídos nele.

O primeiro desses resultados é aparente considerando-se, por exemplo, a função tangente, que estabelece uma correspondência um-para-um entre o intervalo (−½p, ½p) e R (veja também o Paradoxo do Hotel de Hilbert).

O segundo resultado foi demonstrado pela primeira por Cantor em 1878, mas ficou mais aparente em 1890, quando Giuseppe Peano introduziu as curvas de preenchimento de espaço, linhas curvas que se torcem e dobram o suficiente para preencher a totalidade de um quadrado, um cubo, um hipercubo ou espaço dimensional finito. Essas curvas não são uma prova direta de que a linha tem o mesmo número de pontos que um espaço dimensional finito, mas elas podem ser facilmente usadas para obter tal prova.

Cantor também mostrou a existência de conjuntos com cardinalidade estritamente maior do que ${\displaystyle {\mathfrak {c}}}$ (veja o seu argumento diagonal generalizado e teorema). Eles incluem, por exemplo:

• o conjunto de todos os subconjuntos de R, i.e., o conjunto potência de R, denotado P(R) ou 2^R
• o conjunto R^R de todas as funções de R para R

Ambos possuem cardinalidade

${\displaystyle 2^{\mathfrak {c}}=\beth _{2}>{\mathfrak {c}}}$

(veja Número Beth 2).

As igualdades cardinais ${\displaystyle {\mathfrak {c}}^{2}={\mathfrak {c}},}$ ${\displaystyle {\mathfrak {c}}^{\aleph _{0}}={\mathfrak {c}},}$ e ${\displaystyle {\mathfrak {c}}^{\mathfrak {c}}=2^{\mathfrak {c}}}$ podem ser demonstradas usando-se a aritmética cardinal:

${\displaystyle {\mathfrak {c}}^{2}=\left(2^{\aleph _{0}}\right)^{2}=2^{2\times {\aleph _{0}}}=2^{\aleph _{0}}={\mathfrak {c}},}$

${\displaystyle {\mathfrak {c}}^{\aleph _{0}}=\left(2^{\aleph _{0}}\right)^{\aleph _{0}}=2^{{\aleph _{0}}\times {\aleph _{0}}}=2^{\aleph _{0}}={\mathfrak {c}},}$

${\displaystyle {\mathfrak {c}}^{\mathfrak {c}}=\left(2^{\aleph _{0}}\right)^{\mathfrak {c}}=2^{{\mathfrak {c}}\times \aleph _{0}}=2^{\mathfrak {c}}.}$

• Se X = {a, b, c} e Y = {maçãs, laranjas, pêssegos}, então | X | = | Y | pois {(a, maçãs), (b, laranjas), (c, pêssegos)} é uma bijeção entre os conjuntos X e Y. A cardinalidade de ambos os conjuntos é 3.
• Se | X | < | Y |, então existe Z tal que | X | = | Z | e Z ⊆ Y.
• Conjuntos com a cardinalidade do contínuo

O Grupo de Montagem é um exemplo de organização que sempre mantém a cardinalidade.

O Commons possui uma categoria com imagens e outros ficheiros sobre Cardinalidade

• Número Aleph
• Número Beth
• Tipo de ordem
• Conjunto contável