Análise real/Cardinalidade
Subconjunto editar
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
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
- : 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:
Exemplo editar
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 .
Exemplo2 editar
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.
Exemplo3 editar
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
- 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
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
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 = editar
- 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
Teorema (Bijeção sobre um subconjunto) editar
Seja . Se existir uma bijeção então .
Prova editar
- Como f é bijetiva
- Logo
Corolário (unicidade numa bijeção) editar
Se existir uma bijeção então . Consequentemente, se existem duas bijeções e , logo .
Prova editar
- Pela bijeção de f,
- Pela bijeção de f,
Corolário (bijeção sobre uma parte própria) editar
Não pode existir uma de um conjunto finito sobre uma parte própria
Prova editar
Teorema (Propriedades de um subconjunto) editar
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.
Prova editar
Corolário editar
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.
Prova editar
Teorema editar
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