Conjuntos Finitos e Infinitos
Neste capítulo, será estabelecida com precisão a diferença entre conjunto finito e infinito. será feita também a distinção entre conjunto enumerável e conjunto não-enumerável. O ponto de partida é o conjunto dos números naturais.
1 Números naturais
O conjunto IN dos números naturais é caracterizado pelos seguintes fatos:
1. Existe uma função injetiva s: IN -> IN. A imagem s(n) de cada número natural n Î IN chama-se o sucessor de n.
2. Existe um único número natural 1 Î IN tal que 1 ¹ s(n) para todo n Î IN.
3. Se um conjunto X Ì IN tal que 1 Î X e s(X) Ì X (isto é, n Î X Þ s(n) Î X) então X = IN.
Estas afirmações podem ser reformuladas assim:
1'. Todo número natural tem um sucessor, que ainda é um número natural; números diferentes tem sucessores diferentes.
2'. Existe um único número natural 1 que não é sucessor de nenhum outro.
3'. Se um conjunto de números naturais contém o número 1 e contém também o sucessor de cada um dos seus elementos, então esse conjunto contém todos os números naturais.
Neste capítulo, será estabelecida com precisão a diferença entre conjunto finito e infinito. será feita também a distinção entre conjunto enumerável e conjunto não-enumerável. O ponto de partida é o conjunto dos números naturais.
1 Números naturais
O conjunto IN dos números naturais é caracterizado pelos seguintes fatos:
1. Existe uma função injetiva s: IN -> IN. A imagem s(n) de cada número natural n Î IN chama-se o sucessor de n.
2. Existe um único número natural 1 Î IN tal que 1 ¹ s(n) para todo n Î IN.
3. Se um conjunto X Ì IN tal que 1 Î X e s(X) Ì X (isto é, n Î X Þ s(n) Î X) então X = IN.
Estas afirmações podem ser reformuladas assim:
1'. Todo número natural tem um sucessor, que ainda é um número natural; números diferentes tem sucessores diferentes.
2'. Existe um único número natural 1 que não é sucessor de nenhum outro.
3'. Se um conjunto de números naturais contém o número 1 e contém também o sucessor de cada um dos seus elementos, então esse conjunto contém todos os números naturais.
As propriedades 1, 2, 3 acima chamam-se os axiomas de Peano. o Axioma 3 é conhecido como o princípio da indução. Intuitivamente, ele significa que todo número natural n pode ser obtido a partir de 1, tomando-se seu sucessor s(1), o sucessor deste, s(s(1)), e assim por diante, com um número finito de etapas. (Evidentemente "número finito" é uma expressão que, neste momento, não tem ainda significado. A formulação do axioma 3 é uma maneira extremamente hábil de evitar a petição de princípio até que a noção de conjunto finito seja esclarecida).
O princípio da indução serve de base para um método de demonstração de teoremas sobre números naturais, conhecido como o método de indução (ou recorrência), o qual funciona assim: "se uma propriedade P é válida para o número 1 e se, supondo P válida para o número n daí resultar que P é válida também para seu sucessor s(n), então P é válida para todos os números naturais".
Como exemplo de demonstração por indução, provemos que, para todo n Î IN, tem-se s(n) ¹ n. Esta afirmação é verdadeira para n=1 porque, pelo axioma 2, tem-se 1 ¹ s(n) para todo n logo, em particular, 1 ¹ s(1). Supondo-a verdadeira para um certo n Î IN, vale n ¹ s(n). Como a função s é injetiva, daí resulta s(n) ¹ s(s(n)), isto é, a afirmação é verdadeira para s(n).
No conjunto IN dos números naturais são definidas duas operações fundamentais: a adição, que associa a cada par de números (m,n) sua soma m+n, e a multiplicação, que faz corresponder ao par (m,n) seu produto m.n. Essas operações são caracterizadas pelas seguintes igualdades, que lhes servem de definição:
m+1 = s(m)
m + s(n) = s(m + n), isto é, m + (n + 1) = (m + n) +1
m.1 = m;
m.(n + 1) = m.n + m
Noutros termos: somar 1 a m significa tomar o sucessor de m. E se já conhecemos a soma m + n também conheceremos m + (n + 1), que é o sucessor de m + n. Quanto à multiplicação: multiplicar por 1 não altera o número. E se conhecemos o produto m.n, conheceremos, m.(n + 1) = m.n + m. A demonstração da existência das operações + e . com as propriedades acima, bem como sua unicidade, se faz por indução. Os detalhes serão omitidos aqui. O leitor interessado pode consultar o "Curso de Análise", vol. 1, ou as referências bibliográficas ali contidas, onde são demonstradas (por indução) as seguintes propriedades da adição e da multiplicação:
associatividade: (m+n) + p = m + (n+p), m.(n.p) = (m.n).p;
distributividade: m.(n+p) = m.n + m.p;
comutatividade: m+n = n+m, m.n = n.m;
lei do corte: n+m = p+m => n = p, n.m = p.m => n=p.
Como exemplo, provemos a lei do corte para adição. Usaremos indução em m. Ela vale para m=1 pois n+1 = p+1 significa s(n) = s(p), logo n=p pela injetividade de s. Admitindo-a válida para m, suponhamos que n+m+1 = p+m+1. Entaão, novamente pela injetividade de s, tem-se n+m=p+m donde, pela hipótese de indução, n=p.
O princípio da indução serve de base para um método de demonstração de teoremas sobre números naturais, conhecido como o método de indução (ou recorrência), o qual funciona assim: "se uma propriedade P é válida para o número 1 e se, supondo P válida para o número n daí resultar que P é válida também para seu sucessor s(n), então P é válida para todos os números naturais".
Como exemplo de demonstração por indução, provemos que, para todo n Î IN, tem-se s(n) ¹ n. Esta afirmação é verdadeira para n=1 porque, pelo axioma 2, tem-se 1 ¹ s(n) para todo n logo, em particular, 1 ¹ s(1). Supondo-a verdadeira para um certo n Î IN, vale n ¹ s(n). Como a função s é injetiva, daí resulta s(n) ¹ s(s(n)), isto é, a afirmação é verdadeira para s(n).
No conjunto IN dos números naturais são definidas duas operações fundamentais: a adição, que associa a cada par de números (m,n) sua soma m+n, e a multiplicação, que faz corresponder ao par (m,n) seu produto m.n. Essas operações são caracterizadas pelas seguintes igualdades, que lhes servem de definição:
m+1 = s(m)
m + s(n) = s(m + n), isto é, m + (n + 1) = (m + n) +1
m.1 = m;
m.(n + 1) = m.n + m
Noutros termos: somar 1 a m significa tomar o sucessor de m. E se já conhecemos a soma m + n também conheceremos m + (n + 1), que é o sucessor de m + n. Quanto à multiplicação: multiplicar por 1 não altera o número. E se conhecemos o produto m.n, conheceremos, m.(n + 1) = m.n + m. A demonstração da existência das operações + e . com as propriedades acima, bem como sua unicidade, se faz por indução. Os detalhes serão omitidos aqui. O leitor interessado pode consultar o "Curso de Análise", vol. 1, ou as referências bibliográficas ali contidas, onde são demonstradas (por indução) as seguintes propriedades da adição e da multiplicação:
associatividade: (m+n) + p = m + (n+p), m.(n.p) = (m.n).p;
distributividade: m.(n+p) = m.n + m.p;
comutatividade: m+n = n+m, m.n = n.m;
lei do corte: n+m = p+m => n = p, n.m = p.m => n=p.
Como exemplo, provemos a lei do corte para adição. Usaremos indução em m. Ela vale para m=1 pois n+1 = p+1 significa s(n) = s(p), logo n=p pela injetividade de s. Admitindo-a válida para m, suponhamos que n+m+1 = p+m+1. Entaão, novamente pela injetividade de s, tem-se n+m=p+m donde, pela hipótese de indução, n=p.
Nenhum comentário:
Postar um comentário