Cardinalidade

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Definição do número de elementos num conjunto

O conjunto

S

de todos os sólidos platônicos tem 5 elementos. Assim a cardinalidade de

S

é 5 ou, em símbolos,

{displaystyle |S|=5}

Em matemática, o cardinalidade de um conjunto é uma medida do número de elementos do conjunto. Por exemplo, o conjunto ${displaystyle A={2,4,6}}$ contém 3 elementos, e portanto $A$ tem uma cardinalidade de 3. A partir do final do século XIX, este conceito foi generalizado para conjuntos infinitos, o que permite distinguir entre diferentes tipos de infinito e realizar aritmética sobre eles. Há duas abordagens para a cardinalidade: uma que compara conjuntos diretamente usando bijeções e injeções, e outra que usa números cardeais. A cardinalidade de um conjunto também é chamada de sua tamanho, quando nenhuma confusão com outras noções de tamanho é possível.

A cardinalidade de um conjunto $A$ é geralmente denotado $|A|$ , com uma barra vertical de cada lado; esta é a mesma notação que o valor absoluto, e o significado depende do contexto. A cardinalidade de um conjunto $A$ pode, alternativamente, ser denunciado por $n(A)$ , $A$ , ${displaystyle operatorname {card} (A)}$ ou ${displaystyle #A}$ .

História

Um senso grosseiro de cardinalidade, uma consciência de que grupos de coisas ou eventos se comparam com outros grupos por conterem mais, menos ou o mesmo número de instâncias, é observado em uma variedade de espécies animais atuais, sugerindo uma origem milhões de anos atrás. A expressão humana da cardinalidade é vista desde 40000 anos atrás, igualando o tamanho de um grupo com um grupo de entalhes gravados ou uma coleção representativa de outras coisas, como gravetos e conchas. A abstração da cardinalidade como um número é evidente por volta de 3000 aC, na matemática suméria e na manipulação de números sem referência a um grupo específico de coisas ou eventos.

Desde o século VI aC, os escritos dos filósofos gregos mostram os primeiros indícios da cardinalidade de conjuntos infinitos. Embora considerassem a noção de infinito como uma série infinita de ações, como adicionar 1 a um número repetidamente, eles não consideravam o tamanho de um conjunto infinito de números uma coisa. A antiga noção grega de infinito também considerava a divisão das coisas em partes repetidas sem limites. Nos Elementos de Euclides, a comensurabilidade foi descrita como a capacidade de comparar o comprimento de dois segmentos de linha, a e b, como uma proporção, desde que haja um terceiro segmento, não importa quão pequeno, que possa ser colocado de ponta a ponta um número inteiro de vezes em a e b. Mas com a descoberta dos números irracionais, viu-se que mesmo o conjunto infinito de todos os números racionais não era suficiente para descrever o comprimento de cada segmento de linha possível. Ainda assim, não havia o conceito de conjuntos infinitos como algo que tivesse cardinalidade.

Para entender melhor os conjuntos infinitos, uma noção de cardinalidade foi formulada por volta de 1880 por Georg Cantor, o criador da teoria dos conjuntos. Ele examinou o processo de igualar dois conjuntos com bijeção, uma correspondência um-para-um entre os elementos de dois conjuntos com base em uma relação única. Em 1891, com a publicação do argumento da diagonal de Cantor, ele demonstrou que existem conjuntos de números que não podem ser colocados em correspondência biunívoca com o conjunto dos números naturais, ou seja, conjuntos incontáveis que contêm mais elementos do que estão no conjunto infinito dos números naturais.

Comparação de conjuntos

Função bijetiva de N para o conjunto E de números pares. Embora E é um subconjunto adequado de N, ambos os conjuntos têm a mesma cardinalidade.

N não tem a mesma cardinalidade que seu conjunto de poder P(N): Para cada função f a partir de N para P(N), o conjunto T Não.n∈N: n∉f(n)} discorda de cada conjunto na gama de f, consequentemente f não pode ser subjetivo. A imagem mostra um exemplo f e o correspondente T; vermelho: n∈f(n)T, azul:n∈Tf(n).

Embora a cardinalidade de um conjunto finito seja apenas o número de seus elementos, estender a noção para conjuntos infinitos geralmente começa com a definição da noção de comparação de conjuntos arbitrários (alguns dos quais são possivelmente infinitos).

Definição 1: |A| = |B|

Dois conjuntos A e B ter a mesma cardinalidade se houver uma bijeção (a.k.a., uma a uma correspondência) de A para B, isto é, uma função de A para B que é injetivo e surjetivo. Tais conjuntos são ditos para ser equipar., equipamentoou equinumeroso. Esta relação também pode ser denotada A ? B ou A ~ B.

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

Para conjuntos finitos A e B, se alguns bijeção existe a partir de A para B, então cada um função injetiva ou subjetiva de A para B é uma bijeção. Isso não é mais verdade para infinito A e B. Por exemplo, a função g a partir de N para E, definido por g(n) = 4n é injetivo, mas não subjetivo, e h a partir de N para E, definido por h(n) = n - Não.n mod 2) é surjetivo, mas não injetivo. Nem sequer. g nem h pode desafiar |E|N|, que foi estabelecido pela existência de f.

Definição 2: |A| ≤ |B|

A tem cardinalidade inferior ou igual à cardinalidade de B, se houver uma função injetiva de A para dentro B.

Definição 3: |A| < |B|

A tem cardinalidade estritamente menos do que a cardinalidade de B, se houver uma função injetiva, mas nenhuma função bijetiva, de A para B.

Por exemplo, o conjunto N de todos os números naturais tem cardinalidade estritamente menos do que seu conjunto de poder P(N), porque g(n) = { n } é uma função injetiva de N para P(N), e pode ser mostrado que nenhuma função de N para P(N) pode ser bijetivo (ver imagem). Por um argumento semelhante, N tem cardinalidade estritamente menos do que a cardinalidade do conjunto R de todos os números reais. Para provas, veja o argumento diagonal de Cantor ou a primeira prova de incontabilidade de Cantor.

Se |A| ≤ |B| e |B| ≤ |A|, então |A| = |B| (um fato conhecido como teorema de Schröder-Bernstein). O axioma da escolha é equivalente à afirmação de que |A| ≤ |B| ou |B| ≤ |A| para cada A, B.

Números cardinais

Na seção acima, "cardinalidade" de um conjunto foi definido funcionalmente. Em outras palavras, não foi definido como um objeto específico em si. No entanto, esse objeto pode ser definido da seguinte maneira.

A relação de ter a mesma cardinalidade é chamada de equinumerosidade, e esta é uma relação de equivalência na classe de todos os conjuntos. A classe de equivalência de um conjunto A sob esta relação, então, consiste em todos aqueles conjuntos que têm a mesma cardinalidade que A. Existem duas maneiras de definir a "cardinalidade de um conjunto":

A cardinalidade de um conjunto A é definida como sua classe de equivalência sob equinumerosidade.
Um conjunto representativo é designado para cada classe de equivalência. A escolha mais comum é o ordinal inicial nessa classe. Isto é geralmente tomado como a definição do número cardinal na teoria dos conjuntos axiomáticos.

Assumindo o axioma da escolha, as cardinalidades dos conjuntos infinitos são denotadas

<math alttext="{displaystyle aleph _{0}<aleph _{1}<aleph _{2}? ? 0<? ? 1<? ? 2<...... .{displaystyle aleph _{0}<aleph _{1}<aleph _{2}<ldots.}<img alt="aleph _{0}<aleph _{1}<aleph _{2}

Para cada ordinal $alpha$ , $aleph _{alpha +1}$ é o número menos cardinal maior do que $aleph _{alpha }$ .

A cardinalidade dos números naturais é denotada aleph-null ( $aleph _{0}$ ), enquanto a cardinalidade dos números reais é denotada por " ${mathfrak {c}}$ " (um script fraktur minúsculo "c"), e também é referido como a cardinalidade do continuum. Cantor mostrou, usando o argumento diagonal, que $aleph _{0}}" xmlns="http://www.w3.org/1998/Math/MathML">c>? ? 0{displaystyle {mathfrak {c}}>aleph _{0}}aleph _{0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7e71a63bff0cd0b51207e326da9a4c785b77c58a" style="vertical-align: -0.671ex; width:6.478ex; height:2.509ex;"/>$ . Podemos mostrar que ${mathfrak {c}}=2^{aleph _{0}}$ , este também é a cardinalidade do conjunto de todos os subconjuntos dos números naturais.

A hipótese de continuidade diz que $aleph _{1}=2^{aleph _{0}}$ , i.e. $2^{aleph _{0}}$ é o menor número cardinal maior do que $aleph _{0}$ , ou seja, não há nenhum conjunto cuja cardinalidade é estritamente entre o dos inteiros e o dos números reais. A hipótese de continuidade é independente do ZFC, uma axiomatização padrão da teoria dos conjuntos; isto é, é impossível provar a hipótese de continuidade ou sua negação do ZFC, desde que o ZFC seja consistente. Para mais detalhes, veja § cardinalidade do continuum abaixo.

Conjuntos finitos, contáveis e incontáveis

Se o axioma da escolha é válido, a lei da tricotomia é válida para a cardinalidade. Assim podemos fazer as seguintes definições:

Qualquer conjunto X com cardinalidade menor do que o dos números naturais, ou |X| < |N|, é dito ser um conjunto finito.
Qualquer conjunto X que tem a mesma cardinalidade que o conjunto dos números naturais, ou |X|N|= $aleph _{0}$ , é dito ser um conjunto contável infinito.
Qualquer conjunto X com cardinalidade maior do que o dos números naturais, ou |X| > |N|, por exemplo |R|= ${mathfrak {c}}$ > | | | | | | | |N|, é dito ser incontável.

Conjuntos infinitos

Nossa intuição obtida a partir de conjuntos finitos quebra ao lidar com conjuntos infinitos. No final do século XIX, Georg Cantor, Gottlob Frege, Richard Dedekind e outros rejeitaram a visão de que o todo não pode ser o mesmo tamanho da peça. Um exemplo disso é o paradoxo de Hilbert do Grand Hotel. De fato, Dedekind definiu um conjunto infinito como aquele que pode ser colocado em uma correspondência one-to-one com um subconjunto estrito (isto é, tendo o mesmo tamanho no sentido de Cantor); esta noção de infinito é chamada infinita Dedekind. Cantor introduziu os números cardeais, e mostrou -de acordo com sua definição de tamanho baseada em bijeção - que alguns conjuntos infinitos são maiores do que outros. A menor cardinalidade infinita é a dos números naturais ( $aleph _{0}$ ).

Cardinalidade do continuum

Um dos resultados mais importantes de Cantor foi que a cardinalidade do continuum ( ${mathfrak {c}}$ ) é maior do que o dos números naturais ( $aleph _{0}$ ); isto é, há mais números reais R do que números naturais N. Nomeadamente, Cantor mostrou que ${displaystyle {mathfrak {c}}=2^{aleph _{0}}=beth _{1}}$ (veja Beth um) satisfaz:

aleph _{0}}" xmlns="http://www.w3.org/1998/Math/MathML">2? ? 0>? ? 0{displaystyle 2^{aleph _{0}}>aleph _{0}}aleph _{0}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/97e1bf33bdecaecb7f6d9030c3c5e2d0e3830732" style="vertical-align: -0.671ex; width:8.804ex; height:3.009ex;"/>

(veja o argumento diagonal de Cantor ou a primeira prova de incontabilidade de Cantor).

A hipótese do contínuo afirma que não há número cardinal entre a cardinalidade dos reais e a cardinalidade dos números naturais, ou seja,

2^{aleph _{0}}=aleph _{1}

No entanto, esta hipótese não pode ser provada nem refutada dentro da teoria de conjunto axiomática ZFC amplamente aceita, se ZFC for consistente.

A aritmética cardinal pode ser usada para mostrar não apenas que o número de pontos em uma linha numérica real é igual ao número de pontos em qualquer segmento dessa linha, mas que isso é igual ao número de pontos em um plano e, de fato, em qualquer espaço de dimensão finita. Esses resultados são altamente contra-intuitivos, porque implicam que existem subconjuntos e superconjuntos próprios de um conjunto infinito S que têm o mesmo tamanho que S, embora S contém elementos que não pertencem a seus subconjuntos, e os superconjuntos de S contêm elementos que não estão incluídos nele.

O primeiro desses resultados é aparente considerando, por exemplo, a função tangente, que fornece uma correspondência biunívoca entre o intervalo (−½π, ½π) e R (veja também O paradoxo de Hilbert do Grand Hotel).

O segundo resultado foi demonstrado pela primeira vez por Cantor em 1878, mas tornou-se mais evidente em 1890, quando Giuseppe Peano introduziu as curvas de preenchimento de espaço, linhas curvas que torcem e giram o suficiente para preencher a totalidade de qualquer quadrado ou cubo, ou hipercubo, ou espaço de dimensão finita. Essas curvas não são uma prova direta de que uma linha tem o mesmo número de pontos que um espaço de dimensão finita, mas podem ser usadas para obter essa prova.

Cantor também mostrou que conjuntos com cardinalidade estritamente maior do que ${mathfrak {c}}$ existir (veja seu argumento diagonal generalizado e teorema). Eles incluem, por exemplo:

o conjunto de todos os subconjuntos de R, i.e., o conjunto de energia de R, escrito P(R) ou 2^R
o conjunto R^R de todas as funções R para R

Ambos têm cardinalidade

{mathfrak {c}}}" xmlns="http://www.w3.org/1998/Math/MathML">2c= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =? ? 2>c{displaystyle 2^{mathfrak} {c}=beth _{2}>{mathfrak {c}}}{mathfrak {c}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1aa03eebbeb146c03d8dd83c3ed3a3af47c521b0" style="vertical-align: -0.671ex; width:11.741ex; height:2.676ex;"/>

(veja Beth dois).

A igualdade cardinal ${mathfrak {c}}^{2}={mathfrak {c}},$ ${mathfrak {c}}^{aleph _{0}}={mathfrak {c}},$ e ${mathfrak {c}}^{mathfrak {c}}=2^{mathfrak {c}}$ pode ser demonstrado usando aritmética cardinal:

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

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

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

Exemplos e propriedades

Se X Não.um, b), ce Y Onde? um, b)e c são distintos, então |X|Y| porque {um, maçãs), (b), laranjas), (c, peaches)} é uma bijeção entre os conjuntos X e Y. A cardinalidade de cada um de X e Y é 3.
Se |X| ≤ |Y|, então existe Z. tal que |X|Z.| e Z. ⊆ Y.
Se |X| ≤ |Y| e |Y| ≤ |X|, then |X|Y|. Isso mantém até mesmo para cardeais infinitos, e é conhecido como teorema Cantor-Bernstein-Schroeder.
Conjuntos com cardinalidade do continuum incluem o conjunto de todos os números reais, o conjunto de todos os números irracionais e o intervalo $[0,1]$ .

União e intersecção

Se A e B são conjuntos disjuntos, então

leftvert Acup Brightvert =leftvert Arightvert +leftvert Brightvert.

A partir disso, pode-se mostrar que, em geral, as cardinalidades de uniões e interseções estão relacionadas pela seguinte equação:

{displaystyle leftvert Ccup Drightvert +leftvert Ccap Drightvert =leftvert Crightvert +leftvert Drightvert.}

Más resultados...