Saltar para o conteúdo

Análise real/Cardinalidade

Origem: Wikilivros, livros abertos por um mundo aberto.

Subconjunto

[editar | editar código-fonte]

Um subconjunto importante dos naturais é o para algum .

  • Exemplo: Caso exista uma bijeção entre A e , então A possui 5 elementos.

Conjuntos finitos e infinitos

[editar | editar código-fonte]

Um conjunto A é finito quando assume uma das opções abaixo:

  • quando ele é vazio. (Neste caso o conjunto não têm elementos)
  • quando existe uma bijeção entre e . (Neste caso o conjunto têm n elementos)
    • escreve-se .

Concluímos que:

  • todo conjunto é finito.
  • Que uma função bijeção entre dois conjuntos finitos ocorre somente quando eles possuem a mesma quantidade de elementos, aí dizemos que eles possuem a mesma cardinalidade. (De forma geral, se existe uma bijeção entre dois conjuntos, eles possuem a mesma cardinalidade, podendo eles serem infinitos).
  • Numa bijeção, se um conjunto é finito, o outro também o é ou se um não for finito o outro também não é.
  • Seja A um conjunto não vazio. Se existe e uma função injetiva diremos que A é finito, caso contrário, A é infinito.
  • O menor número n que verifica esta propriedade é dito número de elementos de A. Escrevemos . Diremos também que o conjunto vazio é finito e que seu número de elementos é 0.

Cardinalidade de um conjunto

[editar | editar código-fonte]
  • : significa Cardinalidade de A. Caso A seja finito, é a quantidade de elementos de um conjunto finito A.
Definição: Sejam A e B dois conjuntos não vazios. Dizemos que A e B têm a mesma cardinalidade ou que a cardinalidade de A é igual à de B e escrevemos , se existe uma bijeção .
  • Caso contrário dizemos que eles não têm a mesma cardinalidade ou que suas cardinalidades são diferentes e escrevemos .
Exemplo:
Prove que o conjunto dos Naturais e dos Pares Naturais têm a mesma cardinalidade.

Prova:

  • Basta exibirmos uma função bijetiva entre os dois. Assim tome
  • Injetividade:
  • Sobrejetividade: Dado , devemos mostrar que existe . Assim Tomemos .
Prove que um conjunto X com n elementos pode ser ordenado de n! modos.

Prova(Por indução):

  • Devemos mostrar que é válido para quando (A ordenação é única).
  • Como fica quando ; Pode ser ordenado como: , isto é vezes.
    • Acontece que o termo foi colocado antes do termo e depois do termo . Então para cada opção que tinhamos antes ficou duplicada.
  • Como fica quando ; Pode ser ordenado como: , isto é 3! = 6 vezes.
    • Aconteceu para cada opção que tinhamos antes com 2 elementos foi triplicada com a inserção de um terceiro elemento.
    • Sendo que no primeiro o termo foi inserido, antes, entre e depois dos termos em e depois antes, entre e depois dos termos em .
  • Suponha ser válida para quando , existem modos de ordenar.
  • Devemos mostrar que para quando , existem modos de ordenar esses elementos.
    • Como para k elementos existem k! modos de ordenar, então para cada uma delas existem k+1 maneiras de ordenar com o k+1-ésimo elemento.
    • Assim dado uma sequência com k elementos: , teremos , onde o elemento vai sendo colocado entre as posições dos elementos, antes e depois, resultando em k+1 lugares para ser colocados em k! elementos, resultando em possibilidades
  • Logo um conjunto com X com k+1 elementos, pode ser ordenado em k+1! modos.
Proposição: Se um conjunto X tem n elementos e possui t subconjuntos, o conjunto  tem n+1 elementos e possui 2t subconjuntos.
Teorema: Um conjunto com n elementos possui  subconjuntos

Prova(indução sobre n):

  • Um conjunto com 1 elemento possui subconjuntos, no caso de , teremos os subconjuntos
  • Um conjunto com 2 elementos possui subconjuntos, no caso de , teremos os subconjuntos
    • Ou seja, foram inseridos os subconjuntos ao inserir o elemento .
  • Um conjunto com 3 elementos possui subconjuntos, no caso de , teremos os subconjuntos
    • Ou seja, foram inseridos os subconjuntos ao inserir o elemento .
  • Vamos supor válido para quando n = k, ou seja, um conjunto com k elementos têm subconjuntos.
  • Devemos mostrar válido para quando n = k+1, isto é, um conjunto com k elementos têm subconjuntos:
    • Um conjunto com k elementos tem subconjuntos. Ao inserir o elemento a quantidade de subconjuntos vai dobrar(segundo a proposição), assim um conjunto com k+1 elementos têm subconjuntos.

Prova (Triângulo de Pascal)

  • um conjunto com n elementos tem subconjuntos
  • um conjunto com 0 elementos tem subconjunto
  • um conjunto com 1 elementos tem subconjuntos
  • um conjunto com 2 elementos tem subconjuntos
  • um conjunto com 3 elementos tem subconjuntos

...

  • um conjunto com k elementos tem subconjuntos
  • onde o é a quantidade de conjuntos nulo, que no caso é sempre 1
  • onde o é quantidade de conjuntos unitários
  • onde o é a quantidade de conjuntos formados de 2 elementos
  • onde o é a quantidade de conjuntos formados com n-1 elementos
  • onde o é a quantidade de conjuntos com n elementos, que no caso é sempre 1

Relações e exemplos de cardinalidade

[editar | editar código-fonte]
  • Sejam A e B conjuntos não vazios.
    • Se existe função injetiva , então dizemos que a cardinalidade de A é menor ou igual à de B e escrevemos .
    • Se existe uma função sobrejetiva , então dizemos que a cardinalidade de A é maior ou igual a de B e escrevemos .
    • Se , então escrevemos (lê-se a cardinalidade de A é menor que a de B).
    • Analogamente, se , então escrevemos (lê-se a cardinalidade de A é maior que a de B).
Feita esta definição, temos que é enumerável se, e somente se, .
Exemplo: Seja A um conjunto não vazio. É evidente que pois a função identidade dada por é uma bijeção.
Exemplo: Sejam A e B dois conjuntos não vazios com . Obviamente pois a função dada por é injetiva.

PROPOSIÇÃO 1

[editar | editar código-fonte]
Uma função  é injetiva se, e somente se, existe uma função  que seja sobrejetiva.”
  • Para provar essa proposição, fazemos em separado:
Tomemos por hipótese que  é injetiva. Vamos provar que  que é sobrejetiva.
  • , não sabemos se
  • Assim vamos considerar que
    • Se ocorresse que , teríamos que e assim essa g é sobrejetiva.
  • Vamos tomar . Assim, construamos . Ao tomarmos .
  • Assim, se , logo , fixemos , um elemento arbitrário, tal que .
  • Da forma que construímos g, , ou seja, g é sobrejetiva.
    • Com efeito, se teríamos ou seja, , que é uma contradição. Mas se , que é uma contradição, logo .
    • Também, se teríamos , que é uma contradição, logo .
Tomemos por hipótese  é uma função sobrejetiva. Vamos provar que qualquer  é injetiva.
  • Suponha que exista uma , de forma que f não seja injetiva.
  • Pela não-injetividade da f, existem
  • Mas, se acontecesse que, dado , g não seria uma função.
  • Portanto f é injetiva.

PROPOSIÇÃO 2

[editar | editar código-fonte]
Prove que uma função  é invertível se, e somente se, f é bijetiva.”
Prova
  • Vamos tomar por hipótese que é invertível.
    • Uma função f é invertível se existe outra função g tal que para todo x em A e y em B.
    • Por g ser uma função,
    • Observando que dado qualquer y em B, existe um único x, tal que f(x) = y, nos diz que f é sobrejetiva e g é injetiva.
    • Observando que dado qualquer x em A, existe um único y, tal que g(y) = x, nos diz que g é sobrejetiva e f é injetiva.
    • Logo f e g são bijetivas.
TEOREMA De Cantor1-Bernstein2-Schroder3)
Se e , então .

Prova:

  • Considere
    • Como temos que só pode ser definida se
    • Como temos que só pode ser definida se
  • Portanto

Propriedades importantes dos conjuntos finitos

[editar | editar código-fonte]

Teorema (Bijeção sobre um subconjunto)

[editar | editar código-fonte]

Seja . Se existir uma bijeção então .

  • Como f é bijetiva
  • Logo

Corolário (unicidade numa bijeção)

[editar | editar código-fonte]

Se existir uma bijeção então . Consequentemente, se existem duas bijeções e , logo .

  • Pela bijeção de f,
  • Pela bijeção de f,

Corolário (bijeção sobre uma parte própria)

[editar | editar código-fonte]

Não pode existir uma de um conjunto finito sobre uma parte própria

Teorema (Propriedades de um subconjunto)

[editar | editar código-fonte]

Se é um conjunto finito então todo subconjunto é finito. O número de elementos de Y não excede o de X e só é igual quando Y = X.

Seja uma função injetora. Se Y for finito então X também será. Além disso, o número de elementos de X não excede o de Y.

Seja X e Y conjuntos finitos, então  é finito e tem-se que 
Prova
  • Primeiro vamos mostrar que
    • . Podemos somar porque a união é disjunta.
  • Assim
  • Assim
  • Logo