Conjuntos Finitos e Infinitos e Enumerabilidade
6 pág.

Conjuntos Finitos e Infinitos e Enumerabilidade


DisciplinaTeoria da Computação720 materiais17.400 seguidores
Pré-visualização2 páginas
Conjuntos Finitos e Infinitos, Enumerabilidade
Ao estudarmos conjuntos numéricos e seus subconjuntos, muitas vezes, nos deparamos com conjuntos com um número finito de elementos e também com conjuntos com um número infinito de elementos. Neste texto, pretendemos dar uma definição formal sobre esses conceitos bem como deixar mais claro o que significa dizer que dois conjunto têm o mesmo número de elementos. Seguindo nessa direção, vamos ver que o "número de elementos" do conjunto dos números naturais é o mesmo que o do conjunto dos números racionais.
Conjuntos Finitos e Infinitos
Para dar um significado preciso as ideias de conjuntos finitos e infinitos, vamos começar nosso estudo considerando o conjunto N formado por todos os números naturais, ou seja, pelo conjunto N={1,2,3,\u2026}.
Considere os seguintes subconjuntos de N:
i) A o conjunto formado pelos números naturais menores ou iguais a 5. Assim, A={1,2,3,4,5}
Podemos nos perguntar se esse subconjunto de N é finito ou infinito? Nosso senso comum nos diz que ele é finito pois podemos "contar" quantos elementos tem o conjunto A, neste caso, o conjunto possui 5 elementos.
ii) B o conjunto formado pelos números naturais menores ou iguais a 10. Assim, 
B={k\u2208N | 1\u2264k\u226410}={1,2,3,4,5,6,7,8,9,10}
Com base no mesmo raciocínio do exemplo anterior, podemos afirmar que B também é um conjunto finito e que ele possui 10 elementos.
Vamos agora considerar o conjunto In formado por por todos os números naturais menores ou iguais a n. Utilizando a notação de conjuntos podemos escrever In={k\u2208N | 1\u2264k\u2264n} = {1,2,3,\u2026,n}
Dessa forma, retomando os exemplos anteriores, temos que A=5 e B=10.
Assim, no conjunto In o primeiro elemento é o 1, o segundo é o 2, e assim por diante, até que o n-ésimo elemento é o n. Dessa forma, os conjuntos In, onde n\u2208N, são conjuntos com, exatamente, n elementos.
Pensando de uma forma um pouco mais geral, podemos considerar um conjunto formado por letras, como, por exemplo, o conjunto X={d,e,f,g,h}	
Podemos, agora, fazer a mesma pergunta que fizemos para os conjuntos acima: o conjunto X é um conjunto finito ou infinito? Novamente, para respondermos essa pergunta, nos perguntamos se podemos contar seu número de elementos. Contudo, fazer isso equivale a pensar em quem é o primeiro elemento de X, quem é o segundo elemento de X, e assim por diante. 
Matematicamente, isso corresponde a estabelecer uma relação bijetora, ou seja, um-a-um, entre os elementos do conjunto X e algum In. Para esse exemplo, podemos dizer que d é o primeiro elemento, e é o segundo elemento, f é o terceiro elemento, g é o quarto elemento e h é o quinto elemento. O diagrama abaixo para representar essa relação
Veja que ao determinarmos, matematicamente, a quantidade de elementos de um conjunto estamos formalizando o conceito de construção do número de acordo com a teoria de Piaget, ou seja, estamos fornecendo um argumento matemático para uma situação observada na prática.
Como foi possível estabelecer uma relação um-a-um entre o conjunto X e o conjunto A então dizemos que que eles tem o mesmo número de elementos, ou seja, o conjunto X tem 5 elementos. Com base nesses primeiros exemplos, vamos a definição formal de conjuntos finitos e conjuntos infinitos.
Definição: seja X um conjunto qualquer. Dizemos que X é finito se X=\u2205 ou se é possível estabelecer uma relação um-a-um com algum conjunto In para algum n\u2208N. Caso contrário, dizemos que o conjunto X é infinito. No caso em que X=\u2205, dizemos que X possui 0 elementos ou o número de elementos de X é 0 e escrevemos #X=0; no caso que existe uma relação um-a-um com algum In, então dizemos que X possui n elementos ou que o número de elementos de X é n e escrevemos #X=n.
Exemplos
Exemplo 1. 
Considere o conjunto X formado por todos os divisores positivos de 24. O conjunto X é finito ou infinito?	
Ora, o conjunto X pode ser escrito por extenso como X={1,2,3,4,6,8,12,24}
Para podermos dizer que X é finito devemos verificar se X é vazio ou se existe algum conjunto In com o qual podemos estabelecer uma relação um-a-um. Claramente, X não é vazio mas se considerarmos o conjunto I8={1,2,3,4,5,6,7,8} podemos estabelecer a relação que leva 1\u21921, 2\u21922, 3\u21923, 4\u21924, 5\u21926, 6\u21928, 7\u219212 e 8\u219224. (Você pode fazer o diagrama para confirmar que essa relação é um-a-um.) Neste caso, dizemos que X é finito e, mais, que #X=8. (Lê-se: o número de elementos de X é 8.)
Exemplo 2. 
Considere o conjunto P formado por todos os números naturais pares. O conjunto P é finito ou infinito?
Podemos escrever o conjunto P por extenso como P={2,4,6,8,\u2026}
Novamente, para podermos dizer que P é finito então ou P=\u2205 ou P pode ser posto em relação um-a-um com algum conjunto In para algum n\u2208N. Mas, não podemos por P em bijeção com I1 pois "sobram" elementos em P. Da mesma forma, não podemos por P em bijeção com I2, e assim por diante. Logo, P não é finito e daí, pela definição acima, P é infinito.
Enumerabilidade
Definição: dois conjuntos X e Y são ditos equipotentes se eles podem ser postos em correspondência um-a-um.
Com base na definição acima, os conjuntos X e I8, no exemplo 1, são equipotentes.
Definição: um conjunto X é dito enumerável quando ele é finito ou quando ele pode ser posto em correspondência um-a-um com o conjunto dos números naturais.
Com base nessa definição, podemos notar que o conjunto P é enumerável. Uma correspondência um-a-um entre os seus elementos e o conjunto dos números naturais pode ser estabelecida pela relação n\u21922n, ou seja, a relação que associa cada número natural com o seu dobro. Veja o diagrama.
Da mesma forma que nos exemplos acima, quando dois conjuntos estão em correspondência um-a-um, ou seja, quando são equipotentes, dizemos que eles tem o mesmo número de elementos, pelo menos em um certo sentido, para sermos mais precisos vamos dizer que eles possuem o mesmo cardinal. Assim, grosso modo, o conjunto dos números naturais "tem o mesmo número de elementos" que o conjunto dos números naturais pares, ou ainda, o "o infinito de elementos de um conjunto é igual ao infinito de elementos do outro conjunto".
Na verdade, o conceito de enumerabilidade está associada a ideia de podermos colocar os elementos de um conjunto em uma lista onde sabemos quem é o primeiro elemento, quem é o segundo elemento e asssim por diante.
Exemplos
Exemplo 1. 
O conjunto dos númros inteiros é enumerável.
Para vermos que como organizar a lista com todos os números inteiros podemos nos inspirar no diagrama abaixo. Assim, uma enumeração do conjunto dos números inteiros é Z={0,1,\u22121,2,\u22122,3,\u22123,\u2026}
Assim, podemos dizer que existem tantos números inteiros quanto números naturais pois os conjuntos são equipotentes.
Olhando para esse exemplo, será que o conjunto dos números racionais também possui o mesmo tamanho que o conjunto dos números naturais? Será que o conjunto dos números racionais também é enumerável, ou seja, será que podemos por todos os números naturais em uma lista onde sabemos quem é o primeiro número racional, quem é o segundo, e assim por diante?
Para iniciarmos nosso argumento, note que assim como os números inteiros, se soubermos colocar todos os números racionais positivos em uma lista e todos os números racionais negativos em uma lista, depois alternando positivos com negativos conseguimos uma lista completa de todos os números racionais. Para isso, vamos pensar na forma que têm os números racionais positivos, ou seja, o conjunto
Q+={p/q | p,q \u2208 N, q\u22600}
As frações p/q podem ser pensadas como pares ordenados (p,q) e daí podemos identificar Q+ com o conjunto N×N. Representando o produto cartesiano em um plano cartesiano cada ponto de coordenadas naturais representará um número racional. Assim, com base no diagrama abaixo, podemos enumerar os pares de números naturais positivos como:
N×N={(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),(1,4),(2,3),(3,2),(4,1),\u2026}
Assim, uma enumeração dos racionais positivos é dada por	
Q+={1/1,1/2,2/1,1/3,2/2,3/1,1/4,2/3,3/2,4/1,\u2026}={1,1/2,2,1/3,3,1/4,2/3,3/2,4,\u2026}
Note que, no conjunto representado a direita, foram desconsideradas