Lógica Matemática e Teoria de Conjuntos - Cap 4

Lógica Matemática e Teoria de Conjuntos - Cap 4

(Parte 1 de 3)

Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis

Ad eni»c~ao de Dedekind, de conjunto innito, ¶e usada ma discuss~ao de propriedades de conjuntos innitos e de conjuntos nitos. ¶E demonstrado, dentre outras coisas, que conjuntos enumer¶aveis s~ao os menores, em tamanho, dentre os conjuntos innitos. Propriedades e exemplos, de conjuntos enumer¶aveis e de conjuntos n~ao enumer¶aveis, s~ao dadas.

4.1 Conjuntos nitos e in¯nitos

Na Se»c~ao 2.1, Cap¶³tulo 1, mencionamos informalmente que um conjunto nito ¶eu m conjunto que cont¶em apenas uma quantidade nita de elementos; embora este conceito possa ser transformado em uma deni»c~ao matem¶atica mais precisa, daremos preferencia au ma deni»c~ao alternativa (Deni»c~ao 4.1), formulada por Dedekind.

Foi enfatizado, na Se»c~ao 2.1, do Cap¶³tulo 2, que o conjunto N,d os n¶umeros naturais, ¶eu m conjunto innito.S eja Np = f2;4;6;:: :g oc onjuntod et odos os n¶umeros naturais pares. Como foi mostrado ao leitor, no Problema 8, Exerc¶³cios 3.6.1, existe uma correspondencia um-a-um entre o conjunto N e seu subconjunto pr¶oprio Np.

Em outras palavras,

Uma parte ¶et ~ao numerosa quanto o todo.1

Esta propriedade estranha (de um conjunto innito) incomodou muitos matem¶aticos, inclusive Georg Cantor. Foi Richard Dedekind (1831{1916)2 que tornou esta

1Uma diferen»ca not¶avel em rela»c~ao ao axioma de Euclides: \O todo ¶e maior que qualquer de suas partes." (325 a.C.). 2Richard Dedekind, um dos maiores matem¶aticos, nasceu em 6 de outubro de 1831, em Brunswick,

Alemanha. De in¶³cio, os interesses de Dedekind estavam na F¶³sica e na Qu¶³mica; ele considerava a Matem¶atica meramente como uma serva das ciencias. Mas isto n~ao durou muito; aos dezessete anos,

78 Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis propriedade a caracter¶³stica denidora de um conjunto innito. A seguinte deni»c~ao foi dada por Dedekind em 1888.

Deni»c~ao 4.1 Um conjunto X ¶e innito quando possui um subconjunto pr¶oprio Y ,t al que existe uma correspondencia um-a-um entre X e Y . Um conjunto ¶e nito se n~ao for in¯nito.

Em outras palavras, um conjunto X ¶e innito se e somente se existe uma inje»c~ao f : X ! X tal que f(X) ¶e um subconjunto pr¶oprio de X. Logo, o conjunto N de numeros naturais ¶e um conjunto in¯nito.

Exemplo 4.1 O conjunto ¿ e os conjuntos unit¶arios3 s~ao ¯nitos.

Solu»c~ao. (a) Como o conjunto vazio n~ao possui nenhum subconjunto pr¶oprio, o conjunto vazio ¶e nito. (b) Seja fag um conjunto unit¶ario qualquer. Como o ¶unico subconjunto pr¶oprio de fag ¶e o conjunto vazio, e n~ao h¶a nenhuma correspondencia biun¶³voca entre fag e ¿, fag ¶e necessariamente nito.

Teorema 4.1 (a) Todo superconjunto, de um conjunto innito, ¶ei nnito. (b) Todo subconjunto, de um conjunto nito, ¶e nito.

Demonstra»c~ao.

(a) Seja X um conjunto innito ¶e e seja Y um superconjunto de X,i .e., X ½ Y . Ent~ao, pela Deni»c~ao 4.1, existe uma inje»c~ao f : X ! X tal que f(X) 6= X.

Dena uma fun»c~ao g: Y ! Y por

y se y 2 Y ¡X

Deixamos ao leitor vericar que a fun»c~ao g: Y ! Y ¶e injetora e que g(Y ) 6= Y . Segue ent~ao, pela Deni»c~ao 4.1, que Y ¶e in¯nito.

(b) Seja Y um conjunto nito e seja X um subconjunto de Y , i.e., X ½ Y .P ara demonstrar que X ¶e nito, supomos o contr¶ario, que X ¶e innito. Ent~ao, por (a), o conjunto Y deve ser innito. Isto ¶e uma contradi»c~ao. Portanto, o conjunto X ¶e nito.

ele havia se mudado, da F¶³sica e da Qu¶³mica, para a Matem¶atica, cuja l¶ogicaa chavam aiss atisfat¶oria. Aosd ezenovea nos, matriculou-sen aU niversidade deG Äottingen para estudar Matem¶atica, e recebeu seu grau de doutor tres anos depois, sob a orienta»c~ao de Gauss. Sua contribui»c~ao fundamental µaM atem¶atica inclui o famoso \corte de Dedekind", um conceito importante no estudo de n¶umeros irracionais, que o leitor poder¶a ter a oportunidade de estudar em um curso de an¶alise real. 3Um conjunto unit¶ario ¶e um conjunto que consiste de um ¶unico elemento.

Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis 79

Teorema 4.2 Seja g: X ! Y uma correspondencia um-a-um. Se o conjunto X ¶e innito, ent~ao Y ¶e in¯nito.

Demonstra»c~ao. Como X ¶e innito, pela Deni»c~ao 4.1, existe uma inje»c~ao f : X ! X tal que f(X) 6= X. Como g: X ! Y ¶e uma correspondencia um-a-um, tamb¶em o ¶e g¡1: Y ! X (Teorema 3.14, Cap¶³tulo 3). Temos agora o seguinte diagrama de inje»c~oes:

ConseqÄuentemente, a composi»c~ao h = g ± f ± g¡1: Y ! Y de inje»c~oes ¶eu ma inje»c~ao [Problema 7, Exerc¶³cios 3.7.1]. Finalmente, temos

e g(f(X)) 6= Y,p orque f(X) 6= X. Logo, h(Y ) ¶e um subconjunto pr¶oprio de Y ,ep ortanto Y ¶e in¯nito.

Corol¶ario 4.1 Seja g: X ! Y uma correspondencia um-a-um. Se o conjunto X ¶e nito, ent~ao Y ¶e nito.

Demonstra»c~ao. Exerc¶³cio.

Teorema 4.3 Seja X um conjunto innito e seja x0 2 X.E nt~ao X ¡f x0g ¶e innito.

Demonstra»c~ao. Pela Deni»c~ao 4.1, existe uma inje»c~ao f : X ! X tal que f(X) Ã X.

H¶a dois casos a serem considerados: (1) x0 2 f(X),o u( 2) x0 2 X ¡ f(X).E m cada caso, devemos construir uma inje»c~ao gX ¡fx0g: ! X ¡fx0g,t al que g(X ¡fx0g) 6= X ¡fx0g.

Caso 1. x0 2 f(X). Existe um elemento x1 em X tal que f(x1)= x0.U ma fun»c~ao g: X ¡fx0g! X ¡fx0g pode agora ser denida por

80 Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis em que x2 ¶e um elemento do conjunto n~ao vazio X¡f(X), arbitrariamente xado. Segue que gX ¡fx0g: ! X¡fx0g ¶e injetora e que g(X¡fx0g)= f(X¡fx0;x1g)[fx2g6= X ¡f x0g.P ortanto, X ¡f x0g ¶e innito neste caso.

Dena uma fun»c~ao g: X ¡f x0g! X ¡f x0g por g(x)= f(x) para todo x 2

X ¡f x0g. Como f : X ! X ¶e injetora, tamb¶em o ¶e g: X ¡f x0g! X ¡f x0g. Finalmente,

Portanto, em qualquer caso, X ¡f x0g ¶e innito.

No que segue, denotaremos por Nk, k 2 N, o conjunto de todos os n¶umeros naturais de 1 at¶e k;i sto ¶e, Nk = f1;2;:: : ;kg. Como uma aplica»c~ao do Teorema 4.3, mostramos no seguinte exemplo que cada Nk ¶e nito.

Exemplo 4.2 Para cada k 2 N, o conjunto Nk ¶e nito.

Demonstra»c~ao. Demonstraremos isto pelo princ¶³pio de indu»c~ao matem¶atica. Pelo Exem- plo 4.1, a arma»c~ao ¶e verdadeira para k =1 . Agora, suponha que o conjunto Nk ¶e nito para algum n¶umero natural k. Considere o conjunto Nk+1 = Nk [fk +1g.S e Nk+1 for innito, ent~ao, pelo Teorema 4.3, Nk+1¡fk+1g = Nk ser¶a um conjunto innito, o que contradiz a hip¶otese de indu»c~ao. Logo, se Nk ¶e nito, ent~ao Nk+1 ¶e nito. Portanto, pelo princ¶³pio de indu»c~ao matem¶atica, o conjunto Nk ¶e nito para cada k 2 N.

Na verdade, existe uma conex~ao ¶³ntima entre um conjunto nito n~ao vazio e um conjunto Nk.

Teorema 4.4 Um conjunto X ¶e nito se e somente se X = ¿ ou X est¶a em correspondencia um-a-um com algum Nk.

Demonstra»c~ao. Se X ¶ev azio ou est¶a em correspondencia um-a-um com algum Nk, ent~ao, pelo Corol¶ario do Teorema 4.2, e Exemplos 4.1 e 4.2, o conjunto X ¶e nito.

Para mostrar a rec¶³proca, mostramos, equivalentemente, sua contrapositiva: Se X 6= ¿ e X n~ao est¶ae mc orrespondencia um-a-um com nenhum Nk,e nt~ao X ¶e in¯nito.

Podemos tomar um elemento x1 de X,e ter novamente X ¡fx1g n~ao vazio; pois, caso contr¶ario, ter¶³amos X = fx1g em correspondencia com N1, uma contradi»c~ao com a hip¶otese sobre X.

Continuando desta maneira, suponhamos que escolhemos elementos x1, x2, :: :, xk de X.E nt~ao X ¡fx1;x2;::: ;xkg ¶en ~ao vazio; caso contr¶ario, teremos X = fx1;x2; :: : ; xkg em correspondencia um-a-um com Nk,u ma contradi»c~ao com nossa hip¶otese sobre X. Logo, podemos sempre escolher um elemento xk+1 de X ¡f x1;x2;: :: ;xkg. Ent~ao, por indu»c~ao matem¶atica, para todo n¶umero natural n, existe um subconjunto

Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis 81 pr¶oprio fx1;x2;::: ;xng de X. Denotemos o conjunto dos xn's escolhidos por Y .4 Ent~ao a fun»c~ao f : Y ! Y ¡f x1g, denida por f(xk)= xk+1 para todo k 2 N, estabelece uma correspondencia um-a-um entre Y e seu subconjunto pr¶oprio Y ¡f x1g. Portanto, pela Deni»c~ao 4.1, Y ¶e innito e portanto, pelo Teorema 4.1, X ¶e in¯nito.

Mencionaremos aqui que o Teorema 4.4 sugere uma deni»c~ao alternativa de conjuntos nitos e innitos. Podemos denir um conjunto como sendo nito se e somente se ele ¶e vazio ou est¶a em correspondencia um-a-um com algum Nk, e sendo innito se es omente se n~ao ¶e nito. Desta deni»c~ao alternativa, nossa Deni»c~ao 4.1 pode ser demonstrada como um teorema. Entretanto, isto requeriria mais ou menos o mesmo montante de trabalho requerido pela nossa presente abordagem.

1. Complete a demonstra»c~ao do Teorema 1. 2. Seja g: X ! Y uma correspondencia um-a-um. Demonstre que se X ¶e nito, ent~ao Y ¶e nito. 3. Demonstre que os conjuntos Z, Q e R s~ao in¯nitos. 4. Demonstre que se A ¶e um conjunto innito, ent~ao A £ A tamb¶em o ¶e. 5. Demonstre que se A e B s~ao conjuntos innitos, ent~ao A[B ¶e um conjunto in¯nito. 6. Demonstre que a reuni~ao de um n¶umero nito de conjuntos nitos ¶e um conjunto ¯nito. 7. Sejam A e B dois conjuntos tais que A [ B ¶e innito. Demonstre que ao menos um dos dois conjuntos A e B ¶e innito. 8. Demonstre a seguinte generaliza»c~ao do Teorema 4.3: Se Y ¶e um subconjunto nito de um conjunto innito X,e nt~ao X ¡ Y ¶e in¯nito.

(Parte 1 de 3)

Comentários