Notas de Aulas de Elementos de Matemática

Universidade de Sao Paulo Instituto de Ciˆencias Matematicas e de Computacao SMA0341 e SLC0603 Elementos de Matemática Notas de Aulas Ires Dias Sandra Maria Semensato de Godoy Sao Carlos 2012 Sumário 1 Nocoes de Logica 7 11 Proposicoes e Conectivos Logicos 7 12 Proposicoes Compostas e Tabelasverdade 9 13 Tautologia e Equivalˆencia Logica 12 14 Teoremas 15 15 Definicao de e 15 16 Quantificadores 18 17 Metodo Dedutivo 21 18 Metodos de Demonstracao 22 19 Exercıcios 24 2 Teoria dos Conjuntos 27 21 Nocoes Primitivas Definicoes e Axiomas 27 22 Operacoes com Conjuntos 34 23 O Produto Cartesiano de Dois Conjuntos 40 24 Exercıcios 42 3 Relacoes 45 31 Definicoes e Exemplos 45 32 Relacoes de Equivalˆencias e Particoes 49 33 Relacoes de Ordem 53 34 Funcoes 57 35 Exercıcios 57 3 4 Sumario 4 Nocoes de Cardinalidade 63 41 Conjuntos Equipotentes Enumeraveis e Contaveis 63 42 Numeros Cardinais e a Hipotese do Contınuo 68 43 Cardinal de um conjunto Teorema de Cantor 70 44 Aritmetica Cardinal 71 441 Adicao de Numeros Cardinais 71 442 Multiplicacao de Numeros Cardinais 72 443 Potˆencias de Numeros Cardinais 73 45 Exercıcios 75 5 Os Numeros Naturais 79 51 Os Axiomas de Peano 79 52 Adicao em N 81 53 Multiplicacao em N 83 54 Relacao de Ordem em N 85 55 Exercıcios 89 6 Os Numeros Inteiros 91 61 A adicao em Z 92 62 A multiplicacao em Z 94 63 Relacao de Ordem em Z 96 64 A Imersao de N em Z 97 65 Valor Absoluto 98 66 Aritmetica em Z 100 661 Multiplos e Divisores 100 662 Algoritmo da divisao ou algoritmo de Euclides 101 663 Maximo Divisor Comum 102 664 Mınimo Multiplo Comum 108 67 Numeros Primos 110 68 Congruˆencias e Aplicacoes 112 681 Criterios de Divisibilidade 115 Sumario 5 682 A validade de um numero de CPF 118 683 Em que dia da semana vocˆe nasceu 119 69 Exercıcios 121 7 Numeros Racionais 125 71 A adicao em Q 126 72 A Multiplicacao em Q 128 73 Relacao de Ordem em Q 129 74 A imersao de Z em Q 131 75 Exercıcios 132 Referˆencias Bibliograficas 135 1 Noções de Lógica Logica e a higiene usada pelos matematicos para conservar suas ideias saudaveis e fortes Herman Weyl 18851955 11 Proposições e Conectivos Lógicos O estudo da logica e o estudo dos princıpios e metodos utilizados para distinguir argumentos validos daqueles que nao sao validos O principal objetivo desta secao e ajudar o aluno a entender os princıpios e metodos usados em cada etapa de uma demonstracao Sem alguns conceitos logicos basicos e impossıvel escrever eou entender uma demonstracao Quando demonstramos um teorema estamos demonstrando a veracidade de certas declaracoes Em geral estas declaracoes sao compostas de proposicoes quantificadores conectivos eou modifica dores O ponto inicial da logica e o termo proposicao usado em um sentido tecnico Por uma proposicao entendemos uma sentenca declarativa afirmativa ou uma afirmacao verbal que e verdadeira ou falsa mas nao ambas simultaneamente A designacao Ver dadeira V ou Falsa F de uma proposicao e dita ser seu valor verdade ou seu valor logico Exemplo 11 As seguintes afirmacoes sao proposicoes a eπ2 e2π 7 8 1 Nocoes de Logica b 6 e um numero primo c Pedro tem olhos azuis d O dia 10 de agosto de 1935 foi uma quartafeira e O 1000o digito da expansao decimal de 2 e 6 f Existe vida inteligente em Marte Note que a e claramente V b e claramente F c e uma proposicao pois e V ou F mesmo que eu nao conheca o Pedro d e V ou F mesmo que seja difıcil saber a resposta o mesmo vale para e e f Exemplo 12 As seguintes afirmacoes nao sao proposicoes a eπ2 e igual a e2π b AH se eu passar em Elementos c x 3 d 2 3i e menor que 5 3i e xx 4 x2 4x f Esta proposicao e falsa g Hoje e tercafeira h Esta chovendo Note que a e interrogativa e nao declarativa b e exclamativa e nao declarativa c e uma sentenca aberta pode ser V ou F dependendo da variavel x d nao e V ou F pois nao existe ordem em C e nao e uma proposicao o que seria proposicao e para todo x R xx 4 x2 4x f e um paradoxo viola a definicao de proposicao pois e V e F ao mesmo tempo g e uma sentenca aberta que depende da variavel hoje assim como h depende da variavel tempo 12 Proposicoes Compostas e Tabelasverdade 9 12 Proposições Compostas e Tabelasverdade As proposicoes do exemplo 11 sao todas proposicoes simples ou seja nao foram obtidas por combinacoes ou composicoes de outras proposicoes A combinacao ou coneccao de duas ou mais proposicoes simples e uma proposicao composta Ha varias maneiras de conectar proposicoes somente cinco sao frequentemente usadas Sao os conectivos a nao simbolizado por tambem chamado de modificador b e simbolizado por operacao de conjuncao c ou simbolizado por operacao de disjuncao d se entao simbolizado por conectivo condicional e se e somente se simbolizado por conectivo bicondicional Como em algebra usamos letras para representar numeros em logica usaremos letras minusculas para representar proposicoes Definição 13 Para proposicoes p e q definimos a A negacao de p denotada por p lida nao p como sendo a proposicao com valor verdade diferente do de p b A conjuncao de p e q denotada por p q lida p e q como sendo a proposicao que e verdadeira somente quando p e q sao ambas verdadeiras c A disjuncao de p e q denotada por p q lida p ou q como sendo a proposicao que e falsa somente quando p e q sao ambas falsas d A condicional de p e q denotada por p q lida se p entao q ou p implica q ou p condiciona q ou p e condicao suficiente para q como sendo a proposicao que assume o valor falso somente quando p for verdadeira e q for falsa e A bicondicional de p e q denotada por p q lida p se e somente se q ou p bicondiciona q ou p e condicao necessaria e suficiente para q como sendo a proposicao que assume o valor verdadeiro somente quando p e q sao ambas verdadeiras ou p e q sao ambas falsas 10 1 Nocoes de Logica Exemplo 14 Maria tem uma caneta e uma proposicao p O sol e uma estrela e uma proposicao q Podemos formar as novas proposicoes Maria tem uma caneta e o sol e uma estrela p q Maria tem uma caneta ou o sol e uma estrela p q Se Maria tem uma caneta entao o sol e uma estrela p q Maria tem uma caneta se e somente se o sol e uma estrela p q Nao e verdade que Maria tem uma caneta p O sol nao e uma estrela q Observação 15 As definicoes sao condicoes necessarias e suficientes e portanto sao equivalentes a condicoes que tˆem o conectivo se e somente se Para expressarmos os valores logicos de uma proposicao composta e muito con veniente utilizarmos uma tabela chamada tabelaverdade da proposicao onde cada linha expressa os valoresverdade da composta obtidos a partir dos valoresverdade das proposicoes dadas e dos conectivos usados Vejamos as tabelasverdade das proposicoes definidas acima p p V F F V a p p q p q V V V V F F F V F F F F b p q p q p q V V V V F V F V V F F F c p q p q p q V V V V F F F V V F F V d p q p q p q V V V V F F F V F F F V e p q Tabela 11 Tabelasverdade da definicao 13 12 Proposicoes Compostas e Tabelasverdade 11 A partir destas cinco tabelasverdade podemos construir uma tabelaverdade para qualquer proposicao composta Atraves de exemplos apresentaremos duas maneiras de fazermos isso Exemplo 16 Construa a tabelaverdade para a proposicao p q p q p q p q p q V V F F F V V F F V F V F V V F F V F F V V V F Tabela 12 Construcao da tabelaverdade do exemplo 16 Esta tabela representa como chegar na proposicao p q passo a passo Na realidade a tabelaverdade desta proposicao e p q p q V V V V F V F V V F F F Tabela 13 Tabelaverdade do exemplo 16 Vale observar que 1 O conectivo abrange somente a primeira expressao que o segue exceto quando se utiliza parˆenteses eou colchetes p q p q p q p q 2 Os conectivos e abrangem toda a expressao que nao contenha o mesmo sinal p q p q significa p q p q 3 O numero de linhas de uma tabelaverdade de uma proposicao e dado por 2n onde n e o numero de proposicoes simples que a compoem Exemplo 17 Determine se a proposição seguinte é verdadeira Ou π π sen x dx 0 e d dx 2x x2x1 ou π π sen x dx 0 ln 6 ln 2ln 3 Sejam p a proposição π π sen x dx 0 q a proposição d dx 2x x2x1 e r ln 6 ln 2ln 3 Como o conectivo principal é ou ou temos que a proposição dada é p q p r Vamos então construir a tabelaverdade desta proposição Para tanto notamos que neste caso temos 3 proposições simples p q e r Logo nossa tabela terá 23 8 linhas Exemplo 19 Para toda proposição p a proposição p p é uma tautologia e p p é uma contradição De fato basta observar sua tabelaverdade p p p p p p V F V F F F V V V F V V F V V F F F F V V V V V V F F F F V V F V V F F F F V F V F V V V F F F V V V V V V V F F F V V V V V V V V V V V V V F F F V V V V V V V V V F V V V F V F F V F F F F F F F V V V F V V F F F V V F F F F F F F F V V V V V V V V V V F V F F F V V V F F F F V F F V V V F V V V V V V V V F F F V V V V V V V V V V V V V V V F V V F V V F F F F V V V V V F V V V V V V V V F V V V V V V V V V F V V V V V V F F F F V F V F V F F F F V F V F V F V V V F F F V V V V V V V F V V V F V V F V F V F V F F F V V F F F V F F F V F F F F F V F F F F V F V F V F V F V V V V F V V V V V V F V V V V V V V V V F F V V V V V V V V F 14 1 Nocoes de Logica Note que se duas proposicoes p e q sao logicamente equivalentes entao p q e uma tautologia e reciprocamente se p q for uma tautologia entao p e q serao logicamente equivalentes Em Matematica a principal importˆancia das equivalˆencias logicas esta na ideia que duas proposicoes logicamente equivalentes podem ser vistas como a mesma do ponto de vista logico Por exemplo se duas proposicoes p e q sao logicamente equivalentes e necessitamos demonstrar p e encontramos uma maneira mais simples ou mais facil de demonstrarmos q entao podemos demonstrar p provando q Exemplo 112 A proposicao p q e logicamente equivalente a q p mas nao e logicamente equivalente a p q De fato basta observar a tabelaverdade p q p q p q q p p q V V V F F V V V F F F V F V F V V V F V F F F V V V V V Tabela 17 Tabelaverdade do exemplo 112 Mais ainda a proposicao p q e logicamente equivalente a p q que e logicamente equivalente a p q como mostra a tabela abaixo p q p q p q p q p q V V V F F V V V F F F V F F F V V V F V V F F V V V V V Tabela 18 Equivalˆencia entre p q p q e p q Definição 113 Se p q e uma condicional entao q p e dita ser a condi cional contra positiva q p e dita ser a condicional recıproca e p q e a 14 Teoremas 15 condicional inversa 14 Teoremas Um teorema e uma proposicao logica que e uma tautologia As tautologias de principal interesse em matematica sao as que envolvem os conectivos condicional eou bicondicional A demonstracao de um teorema nada mais e do que a confeccao da tabelaverdade mostrando que a proposicao e de fato uma tautologia Em matematica usase outros termos como axiomas e postulados que sao fatos aceitos sem uma demonstracao lemas eou proposicoes que sao teoremas cujo propo sito e utilizalos na demonstracao de outro teorema e corolarios que sao teoremas que seguem imediatamente da demonstracao de outros teoremas 15 Definição de e Sejam p e q proposicoes Se p q e uma tautologia dizemos que esta proposicao condicional e uma implicacao e que p implica logicamente q e escrevemos p q Se p q e uma tautologia dizemos que esta bicondicional e uma biimplicacao e denotamos por p q Lembrese que p q ser tautologia significa que p e q sao logicamente equivalentes e assim p q representa a equivalˆencia entre p e q Vamos ao nosso primeiro teorema que apresenta as propriedades basicas de Teorema 114 Sejam p q e r proposicoes Entao 1 Reflexiva p p 2 Transitiva p q q r p r 3 Simplificacao p q p 4 Adicao p p q 5 Modus Ponens p p q q 6 Modus Tollens p q q p 7 Reduction ad absurdum p q q p 8 Simetria p q q p 16 1 Nocoes de Logica 9 Transitiva p q q r p r 10 p r p q r 11 Disjuncao p q p q 12 p p q 13 q p q 14 p q p q Prova Atraves da tabelaverdade mostraremos os ıtens 3 6 e 14 Os outros ficam como exercıcios Lembrando que mostrar uma implicacao e mostrar que a condi cional correspondente e uma tautologia 3 p q p p q p q p q p V V V V V F F V F V F V F F F V 6 p q q p p q q p q p q q p q q p V V F V F V V F V F F V F V F V F V F F V V V V 14 p q p q p q p q q p p q p q p q V V V V V V V F F V F V F V V F F V F F V V V V 15 Definicao de e 17 As correspondentes propriedades de sao apresentadas no proximo teorema Teorema 115 Sejam p q e r proposicoes Entao 1 Reflexiva p p 2 Dupla negacao p p 3 Negacao da conjuncao Lei de Morgan p q p q 4 Negacao da disjuncao Lei de Morgan p q p q 5 Negacao da condicional p q p q 6 Negacao da bicondicional p q p q p q 7 Comutatividade de p q q p 8 Comutatividade de p q q p 9 Associatividade de p q r p q r 10 Associatividade de p q r p q r 11 Distributividade p q r p q p r 12 Distributividade p q r p q p r 13 Bicondicional p q p q q p 14 Contra positiva p q q p 15 p q p q 16 p q r p q r 17 p q r p r q r 18 p q r p q p r 19 p q r p r q 20 p q r p r q r 21 p q r p q r 18 1 Nocoes de Logica 22 p q p q 23 Idempotˆencias p p p e p p p 24 Transitividade p q e q r p r Prova Como exercıcio fazer alguns casos Referentes as tautologias e as contradicoes temos Teorema 116 Sejam t uma tautologia c uma contradicao e p uma proposicao qual quer Entao 1 c p 2 p t 3 p t p 4 p t t 5 p p c 6 p c c 7 p c p 8 t c 9 c t 10 p p t Prova Como exercıcio fazer alguns casos 16 Quantificadores Existem sentencas para as quais nao ha como decidir se assumem valor V ou F Por exemplo x y 5 e Ele e jogador de futebol Estas sentencas sao denominadas sentencas abertas ou predicados Podemos compor sentencas abertas usando os mesmos conectivos usados nas proposicoes e formarmos novas sentencas abertas a partir de outras mais simples Ha duas maneiras formais de transformar uma sentenca aberta em uma proposicao utilizando os dois quantificadores Para isso necessitamos de um universo ou domınio de discussao isto e uma colecao de objetos para os quais consideramos propriedades Por exemplo na proposicao Todos os homens sao mortais o universo e a colecao de todos os homens e tal proposicao pode ser escrita como Para todo x do universo x e mortal 16 Quantificadores 19 A frase Para todo x do universo e chamada um quantificador universal e e sim bolizado por x A sentenca x e mortal diz alguma coisa sobre x entao sim bolizamos por px Assim escrevemos Todos os homens sao mortais como xpx que pode ser lida como para todo x px para cada x px para qualquer x px Vejamos agora a proposicaoAlguns os homens sao mortais O universo e o mesmo da proposicao anterior Com este universo em mente podemos escrever esta proposicao como Existe no mınimo um homem que e mortal Existe no mınimo um x tal que x e mortal Existe no mınimo um x tal que px A frase Existe no mınimo um x tal que e chamada quantificador existencial e denotada por x Usando este sımbolo podemos escrever a proposicao Alguns homens sao mortais como xpx que pode ser lida como existe x tal que px existe ao menos um x tal que px para algum x px para pelo menos um x px Quando existe um unico elemento no universo que torna a proposicao xpx verdadeira denotamos esta proposicao por xpx e lemos existe um unico x tal que px para um unico x px 20 1 Nocoes de Logica Note que xpx xpx O conjunto dos elementos do universo que tornam uma sentenca aberta uma propo sicao verdadeira e denominado conjuntoverdade Por exemplo para px x1 5 o conjunto universo pode ser R e o conjuntoverdade e 4 enquanto que para a sentenca aberta px sen2 x cos2 x 1 temos que o conjuntoverdade e igual ao conjunto universo que e igual a R Quando estiver subentendido quem e o conjunto universo os quantificadores podem ser omitidos por exemplo escrevemos x 1x 1 x2 1 no lugar de escrever x R x 1x 1 x2 1 Tambem e comum escrevermos os quantificadores depois da sentenca aberta por exemplo escrevemos fx 0 para todo x no lugar de escrevermos xfx 0 Observe que claramente temos xpx xpx As negacoes de proposicoes com quantificadores sao definidas por a xpx x px b xpx x px Vamos mostrar a em um caso particular Suponhamos que o conjunto universo de px seja constituıdo pelos elementos a b c Entao a proposicao xpx significa pa pb pc e verdadeira Daı xpx e o mesmo que pa pb pc que e equivalente a pa pb pc Mas se esta ultima for verdadeira entao um dos casos pa pb pc e verdade o que e equivalente a x px Daı segue que xpx x px Exemplo 117 A negacao de xsen2 x cos2 x 1 significa que x sen2 x cos2 x 1 ou seja xsen2 x cos2 x 1 17 Metodo Dedutivo 21 Os quantificadores nos dao uma ideia do que sao os exemplos e os contraexemplos Quando temos uma proposicao verdadeira que contem um dos quantificadores dar um exemplo e escolher uma variavel x para o qual ela e verdadeira ou seja e escolher um elemento do seu conjuntoverdade Quando uma proposicao que contem um dos quantificadores nao e verdadeira significa que o seu conjuntoverdade e diferente do conjunto universo Assim encontrar um contraexemplo e escolher uma variavel x que nao esteja no conjuntoverdade 17 Método Dedutivo Vimos que demonstrar teoremas significa verificar que a proposicao dada e uma tautologia e fizemos isso construindo tabelasverdade Veremos agora outra maneira de verificar a validade de proposicoes Este procedimento e chamado de metodo dedu tivo e consiste na utilizacao de definicoes de outros resultados preestabelecidos e das propriedades transitivas de e Vejamos como utilizalo em exemplos Exemplo 118 Usando o metodo dedutivo mostrar a validade de p q q p Como p q p q Teorema 115 15 p q q p Teorema 115 7 q p q p Teorema 115 2 q p q p Teorema 115 15 usando a transitividade de obtemos a equivalˆencia desejada Exemplo 119 Usando o metodo dedutivo mostre a validade de p r q s p q r s Como p r q s p r q s Teorema 115 15 p q r s Teorema 115 79 p q r s Teorema 115 3 p q r s Teorema 115 15 usando a transitividade de obtemos a equivalˆencia 22 1 Nocoes de Logica Exemplo 120 Considere as seguintes afirmacoes H1 Tempo e dinheiro H2 Vagabundo tem muito tempo T Vagabundo tem muito dinheiro A proposicao H1 H2 T e um teorema Se considerarmos p Ter tempo q Ter dinheiro e r Ser vagabundo teremos que H1 p q H2 r p e T r q Assim podemos escrever a proposicao H1 H2 T como p q r p r q que e verdadeira mostrando que a proposicao dada e um teorema Exemplo 121 Considere agora as seguintes afirmacoes H1 Penso logo existo H2 Pedras nao pensam T Pedras nao existem A proposicao H1 H2 T e um teorema Se considerarmos p Pensar e q Existir teremos que H1 p q H2 p e T q Assim podemos escrever a proposicao H1 H2 T como p q p q que nao e verdadeira pois p q p q nao e uma tautologia mostrando que a proposicao dada nao e um teorema 18 Métodos de Demonstração Veremos trˆes maneiras ou metodos de demonstrar um teorema da forma p q 1 Prova ou demonstracao direta Consiste na utilizacao do metodo dedutivo assu mindo que p e verdadeira e utilizando equivalˆencias logicas e fatos pre estabelecidos deduzir que q e verdadeira Por exemplo mostre que Se x e um numero inteiro par entao x2 e um inteiro par 18 Metodos de Demonstracao 23 Note que esta e uma implicacao do tipo p q onde p e a proposicao x e um numero inteiro par e q e a proposicao x2 e um numero inteiro par Assumindo p verdadeira temos que x e um numero inteiro par x e divisıvel por 2 por definicao x e multiplo de 2 existe n Z tal que x 2n x2 2n2 4n2 22n2 2m para algum m Z x2 e um numero inteiro par q 2 Demonstracao por contraposicao Consiste na utilizacao da equivalˆencia logica p q q p ou seja para mostrarmos o teorema p q mostramos utilizando o metodo da demonstracao direta que q p Por exemplo mostre que Se x e um numero inteiro tal que x2 e ımpar entao x e um inteiro ımpar Esta e uma implicacao do tipo p q onde p e a proposicao x2 e um numero inteiro ımpar e q e a proposicao x e um numero inteiro ımpar Note que nao e possıvel utilizar o metodo da demonstracao direta neste caso pois de x2 e um numero inteiro ımpar temos que existe n Z tal que x2 2n 1 e nao conseguimos chegar que existe um m Z tal que x 2m 1 Utilizando a equivalˆencia logica citada acima vamos mostrar que q p Agora q x nao e ımpar x e par x2 e par pelo exemplo anterior p Consequentemente p q 3 Demonstracao por contradicao Reduction ad absurdum Consiste na utilizacao da equivalˆencia logica p q p q p ou seja para mostrarmos o teorema p q mostramos que p q p o que nos leva a um absurdo pois como p e sempre verdadeira e concluımos que p e tambem verdadeira teremos que p p e verdadeira o que e uma contradicao Por exemplo mostre que Se x e um numero inteiro tal que x2 e par entao x e um inteiro par Aqui p e a proposicao x2 e um numero inteiro par e q e a proposicao x e um numero inteiro par Note que novamente nao da para demonstrar direto que p q Assuma entao que p q seja verdadeira isto e que x2 e par e x e ımpar x 2n 1 para algum n Z x2 2n 12 4n2 4n 1 22n2 2n 1 24 1 Nocoes de Logica 2m 1 para algum m Z x2 e ımpar p o que e uma contradicao Logo a proposicao x e par nao pode ser falsa o que mostra que p q 19 Exercícios 1 Considere as proposicoes p Fred tem cabelos vermelhos q Fred tem nariz grande e r Fred gosta de comer figos Passe para a linguagem simbolica as seguintes proposicoes a Fred nao gosta de comer figos b Fred tem cabelos vermelhos ou gosta de comer figos c Fred tem cabelos vermelhos e nao tem nariz grande d Fred gosta de comer figos e tem cabelos vermelhos ou tem nariz grande e Fred gosta de comer figos e tem cabelos vermelhos ou tem nariz grande f Nao e o caso de Fred ter nariz grande ou cabelos vermelhos g Fred tem nariz grande e cabelos vermelhos ou ele tem nariz grande e gosta de comer figos 2 Sejam p A casa e azul q A casa tem 30 anos e r A casa e feia Passe para a linguagem simbolica as seguintes sentencas a Se a casa tem 30 anos entao ela e feia b Se a casa e azul entao ela e feia ou tem 30 anos c Se a casa e azul entao ela e feia ou tem 30 anos d A casa nao e feia se e somente se ela tem 30 anos e A casa tem 30 anos se ela e azul e ela nao e feia se ela tem 30 anos f Para que a casa seja feia e necessario e suficiente que ela seja feia e tenha 30 anos 3 Supondo que p seja uma sentenca verdadeira que q seja falsa que r seja falsa e que s seja verdadeira decidir quais das sentencas abaixo sao verdadeiras e quais sao falsas 19 Exercıcios 25 a p r b r s q c p q d s r e s p q r f r s p q 4 Suponha que p seja uma sentenca falsa que q seja verdadeira que r seja falsa e que s seja verdadeira Quais das seguintes sentencas sao verdadeiras e quais sao falsas a r q b p r c q s p d s p s e q s s p f s p r q 5 Construir a tabelaverdade de cada uma das proposicoes abaixo a p q b r s r c p q r d p q p s e p r q s f p q r p q r p q r g p q p q r p p r h p q i p q j p q p q k p q p q l p q p q m p q r q p r 6 Quais das proposicoes acima sao equivalentes Quais sao tautologias Quais sao contradicoes Justifique suas respostas 7 Verificar que as seguintes proposicoes sao equivalentes 26 1 Nocoes de Logica a p q e p q b p q e p q c p q e p q d p q e p q 8 Quantificar as sentencas abertas a fim de obter proposicoes verdadeiras a x2 y2 z2 x y z2 2xz 2xy 2yz b x y 8 c sec2 x 1 tan2 x d sen x 2 9 Dar a negacao das proposicoes abaixo a xpx qx sx b xpx sx c xpx qx d xpx qx e x ypx y f x ypx qy g x ypx qy h x ypx y 2 Teoria dos Conjuntos 21 Noções Primitivas Definições e Axiomas A maioria das nocoes em Matematica sao definidas utilizando outras nocoes que ja foram estabelecidas Assim para definirmos uma nocao precisamos de outra pre estabelecida para esta outra precisamos de mais outra etc Aı surge a pergunta natural E a primeira de todas as nocoes como e estabelecida E natural que esta primeira nocao nao possa ser definida usandose outra pre estabelecida de onde concluımos que nao podemos definir tudo Somos obrigados ao iniciar o estudo de um certo conteudo matematico adotar sem definir as primeiras nocoes que sao chamadas nocoes primitivas Isto foi o que Euclides 330 aC a 270 aC fez com a Geometria quando escreveu Os Elementos onde alguns axiomas foram admitidos e tudo o mais foi deduzido a partir deles Na teoria dos conjuntos adotamos duas nocoes primitivas a saber a de conjunto e a de pertinˆencia denotada por A segunda nocao estabelece uma relacao entre conjuntos da seguinte forma se x e A sao conjuntos a expressao x A pode ser lida como x pertence a A ou x esta em A Com esta nocao podemos definir a nocao de elemento da seguinte forma Definição 21 Seja x um conjunto Se existe um conjunto A tal que x A entao x e dito ser elemento ou seja dizemos que x e um elemento de A ou ainda que x pertence 27 28 2 Teoria dos Conjuntos a A Quando um conjunto x nao for um elemento do conjunto A escrevemos x A e lemos x nao pertence a A ou ainda x nao esta em A que e a negacao de x A Parece estranho escolhermos conjunto e pertinˆencia como elementos primitivos ao inves de conjunto e elemento mas e mais facil definir elemento usando a nocao de pertinˆencia do que definir a nocao de pertinˆencia usando a nocao de elemento Estabeleceremos como convencao o uso de letras maiusculas para denotar conjuntos e letras minusculas para denotar elementos A seguir definimos a nocao de igualdade de conjuntos Definição 22 Sejam A e B conjuntos Dizemos que o conjunto A e igual ao conjunto B e denotamos por A B se todo elemento de A e um elemento de B e viceversa Simbolicamente escrevemos A B xx A x B x B x A Note que com esta definicao dois conjuntos sao iguais se e somente se eles tˆem os mesmos elementos A nosso intuicao nos diz que quando um elemento x esta em um conjunto A e x e igual a outro elemento y entao e natural esperar que y tambem seja elemento de A isso e garantido pelo primeiro axioma da teoria dos conjuntos Axioma da Extensao Se x y e x A entao y A A seguir definimos a nocao de inclusao de conjuntos Definição 23 Sejam A e B conjuntos Dizemos que A esta contido em B ou B contem A e denotamos por A Bou B A se todo elemento de A for um elemento de B Neste caso dizemos tambem que A e um subconjunto de B Simbolicamente escrevemos A B xx A x B Se A B e A e diferente de B dizemos que A e um subconjunto proprio de B e denotamos por A B ou A B Estas nocoes definicoes e axioma nos permitem demonstrar o seguinte resultado 21 Nocoes Primitivas Definicoes e Axiomas 29 Proposição 24 Sejam A B e C conjuntos Entao as seguintes propriedades sao va lidas a Reflexiva A A b Simetrica A B B A c Transitiva A B B C A C d Reflexiva A A e Antisimetrica A B B A A B f Transitiva A B B C A C Prova Vamos mostrar alguns ıtens as demonstracoes dos restantes ficam como exer cıcio a A proposicao x A x A e uma tautologia logo da Definicao 22 temos A A b Da Definicao 22 temos que A B xx A x B x B x A Agora pela comutatividade do conectivo e novamente pela Definicao 22 con cluımos que B A e Da Definicao 23 temos que A B B A e equivalente a proposicao xx A x B x B x A que por sua vez e equivalente a A B pela Definicao 22 Uma maneira de representar um conjunto e exibir seus elementos entre chaves e separados por vırgulas mas podemos tambem caracterizar um conjunto atraves de uma propriedade que o defina Isso deve ser feito axiomaticamente tomando certos cuidados para evitar contradicoes Vejamos o axioma que nos permite construir conjuntos a partir de propriedades 30 2 Teoria dos Conjuntos Axioma da especificacao Sejam A um conjunto e px uma proposicao em x que deve ser expressa totalmente em funcao dos sımbolos e variaveis x y z A B C Entao existe um conjunto que consiste de todos os elementos x de A que tornam px verdadeira Simbolicamente escrevemos x A px e verdadeira Observação 25 A restricao de px utilizar somente sımbolos logicos e variaveis faz sentido para evitar paradoxos do tipo semˆantico Um exemplo disso e o seguinte para doxo que numa versao simplificada diz Paradoxo de Richard Todo numero inteiro pode ser descrito em palavras utilizando um certo numero de letras Por exemplo o numero 36 pode ser descrito como trinta e seis ou quatro vezes nove A primeira descricao utiliza 11 letras e a segunda 15 letras Vamos dividir o conjunto dos numeros inteiros positivos em dois grupos o primeiro contendo todos os numeros inteiros positivos que podem ser escritos com no maximo 100 letras e o segundo inclui todos os numeros inteiros positivos que necessitam de pelo menos 101 letras para descrevˆelos Ha um numero finito de numeros no primeiro grupo pois existem no maximo 24100 expressoes com no maximo 100 letras Existe entao um menor inteiro positivo no segundo grupo Este menor inteiro pode ser descrito pela frase o menor inteiro que nao e descrito com menos de 100 letras o que o descreve com menos de 100 letras Entao este numero pertence ao primeiro grupo o que e uma contradicao Note que este conjunto nao pode ser construıdo pelo axioma da especificacao pois a propriedade do axioma esta restrita a operadores logicos e alguns sımbolos Por isso estamos livres desta contradicao Observação 26 Outra aplicacao mais interessante deste axioma e que ele garante que nao existe um conjunto que contenha todos os conjuntos De fato supondo que exista o conjunto cujos elementos sejam todos os conjuntos seja U tal conjunto Assim usando o axioma da especificacao podemos formar o conjunto B x U x x A questao agora e sera que B U Se sim temos duas possibilidades B B ou B B 21 Nocoes Primitivas Definicoes e Axiomas 31 Se B B pela especificacao de B temos que B B e se B B entao B B o que e uma contradicao Assim chegamos a conclusao que B U ou seja nao existe um conjunto universo O argumento que levou a essa conclusao chamase o paradoxo de Russel cuja versao popular e Numa certa cidade existe um barbeiro que so faz a barba nos homens que nao barbeiam a si proprios Quem faz a barba do barbeiro Com o auxılio do axioma da especificacao podemos construir varios conjuntos im portantes Definição 27 O conjunto vazio denotado por e o conjunto que nao possui elemento algum A existˆencia deste conjunto e garantida pelo axioma da especificacao pois dado qualquer conjunto A temos que x A x x Definição 28 Sejam A e B dois conjuntos A uniao de A e B denotada por A B e o conjunto formado pelos elementos x tais que x esta em pelo menos um dos dois conjuntos A ou B Simbolicamente A B x x A x B A interseccao de A e B denotada por A B e o conjunto formado pelos elementos x tais que x esta em ambos os conjuntos A e B Simbolicamente A B x x A x B Dessa definicao temos as seguintes equivalˆencias logicas x A B x A x B e x A B x A x B Note que a existˆencia dos conjuntos A B e A B e garantida pelo axioma da especificacao Com relacao a uniao e a interseccao de conjuntos temos as seguintes propriedades Teorema 29 Sejam A e B conjuntos Entao a A A B e B A B 32 2 Teoria dos Conjuntos b A B A e A B B c A B A B B e A B A B A d A B A A e A B A A Prova Para os ıtens a e b mostraremos uma das inclusoes as outras sao demons tradas de forma analoga e ficam como exercıcio Vamos mostrar que A A B o que e equivalente por definicao a mostrar que x A x A B o que e equivalente a mostrar que x A x A x B e uma tautologia o que e verdade pois e uma implicacao do tipo p p q No ıtem c tambem provaremos somente uma das equivalˆencias ficando a outra como exercıcio Vamos mostrar que A B AB B Como p q p qq p vamos mostrar as implicacoes e separadamente Queremos mostrar que se A B entao A B B Note que pela igualdade de conjuntos temos que mostrar que A B B e B A B A segunda inclusao segue de a Para a primeira seja x A B entao x A x B Se x A como por hipotese A B temos que x B Assim x B em ambos os casos como querıamos Se A B B entao como A A B B temos claramente que A B A demonstracao do ıtem d fica como exercıcio Dizemos que dois conjuntos A e B sao disjuntos se eles nao possuem elementos em comum ou seja se A B Teorema 210 Sejam X A e B conjuntos Entao temos a A A A e A b X A B X A X B c X A X B X A B e nao vale a volta desta implicacao Prova Vamos mostrar a primeira inclusao do ıtem a ou seja que A Por definicao temos que mostrar que x x A 21 Nocoes Primitivas Definicoes e Axiomas 33 Como a proposicao p x e sempre falsa entao p q e verdadeira para qualquer proposicao q o que mostra a inclusao Outra maneira de mostrar este fato e usandose a contrapositiva isto e supondo que x A entao certamente temos que x pois o conjunto vazio nao contem elementos assim x A x Mostremos agora a equivalˆencia X A B X A X B deixando o restante como exercıcio Nesta implicacao a hipotese e X A B e a tese e X A X B Seja x X como por hipotese X A B temos que x A B e pela definicao de interseccao temos que x A x B Portanto X A X B Nesta implicacao a hipotese e X A X B e a tese e X A B Seja x X por hipotese x A x B e pela definicao de interseccao temos que x A B Portanto X A B Diagramas de Venn e de Linha Uma maneira simples de ilustrar as relacoes entre conjuntos e por meio de diagra mas Existem dois tipos mais utilizados que sao os diagramas de Venn e os diagramas de linha No diagrama de Venn os conjuntos sao representados por regioes limitadas do plano e suas relacoes sao representadas pelas posicoes dessas regioes Nas figuras abaixo representamos algumas relacoes entre os conjuntos A e B U A B a A B U A B b A B Figura 21 Uniao e interseccao de conjuntos No diagrama de linha nao representamos os conjuntos mas sim a relacao de inclusao entre eles Um conjunto que contem o outro conjunto estara num nıvel vertical acima ligado ao primeiro por um segmento de reta Caso os conjuntos nao possuam a relacao de inclusao eles nao sao unidos pelo segmento de reta Neste caso eles sao colocados 22 Operações com Conjuntos Em Aritmética podemos adicionar multiplicar ou subtrair dois números Nos conjuntos as operações união interseção e diferença como definida abaixo se comportam de maneira semelhante às operações aritméticas Definição 211 Sejam A e B dois conjuntos A diferença entre A e B denotado por A B ou A B é o conjunto formado pelos elementos que estão em A e não estão em B Simbolicamente escrevemos A B x x A x B Se A B o conjunto B A é dito também ser o complementar de A em B e denotado por Ac Se A está contido em um conjunto universo U o complementar de A em U é denotado simplesmente por Ac x x A Com estas noções temos os seguintes diagramas de Venn Com respeito a estas operações entre conjuntos temos as seguintes propriedades Teorema 212 Sejam A B e C conjuntos Então a Associativa A B C A B C A B C A B C b Comutativa A B B A e A B B A c Distributiva A B C A B A C A B C A B A C 22 Operacoes com Conjuntos 35 U B A U a B A A U b Ac Figura 23 Diferenca entre Conjuntos e Complementar d Idempotˆencia A A A e A A A e A B A e A B B f A B A B e A A B B B A Se A e B sao subconjuntos de um mesmo conjunto universo U entao g Leis de Morgan A Bc Ac Bc e A Bc Ac Bc h Acc A e A Ac i A B se e somente se Bc Ac Prova Mostraremos uma das igualdades do ıtem a e uma das leis de Morgan do ıtem g deixando a demonstracoes do restante do teorema como exercıcio A igualdade A B C A B C segue das seguintes equivalˆencias x A B C x A x B C Definicao de x A x B x C Definicao de x A x B x C Distributividade de x A B x C Definicao de x A B C Definicao de A igualdade A Bc Ac Bc segue de maneira analoga a negacao da disjuncao 115 4 Axioma da potˆencia Para cada conjunto existe uma colecao de conjuntos que contem entre seus elementos todos os subconjuntos do conjunto dado 36 2 Teoria dos Conjuntos Definição 213 Seja A um conjunto O conjunto potˆencia de A ou conjunto das partes de A denotado por A e o conjunto cujos elementos sao os subconjuntos de A Simbolicamente temos A B B A Exemplo 214 Para A a b c temos A a b c a b a c b c A Proposição 215 Sejam A e B conjuntos Entao a A B A B b A B A B Prova Temos as seguintes equivalˆencias X A B X A B Definicao 213 X A X B Teorema 210 X A X B Definicao 213 X A B Definicao de o que demonstra o ıtem a A demonstracao do ıtem b fica como exercıcio Observação 216 Note que a inclusao A B A B nao e verdadeira De fato para A 1 e B 2 temos A B 1 2 1 2 1 2 e A B 1 2 1 2 Para definirmos a uniao e a interseccao de um numero finito de conjuntos podemos usar o axioma da especificacao Para uma colecao qualquer de conjuntos ja nao e pos sıvel utilizar esse axioma para construir um conjunto uniao e um conjunto interseccao Para tanto necessitamos do seguinte axioma Axioma da uniao Para toda colecao de conjuntos existe um conjunto que contem todos os elementos que pertencem a algum conjunto da colecao dada Em outras palavras este axioma garante que para toda colecao de conjuntos C existe um conjunto U tal que se x A para algum A em C entao x U Assim podemos definir Definição 217 Seja C uma coleção de conjuntos A união dos conjuntos em C ou a união dos elementos de C denotada por AC A ou UC consiste de todos os elementos que pertencem a pelo menos um conjunto da coleção Em símbolos AC A x A A C Note que nesta definição utilizamos o axioma da união e o axioma da especificação para garantir a existência de AC A A unicidade é garantida pelo axioma da extensão Podemos também escrever AC A x A C tal que x A Para a interseção de conjuntos de uma coleção temos Definição 218 Seja C uma coleção de conjuntos A interseção dos conjuntos em C ou a interseção dos elementos de C denotada por AC A ou C consiste de todos os elementos que pertencem a todos os conjuntos da coleção Em símbolos AC A x x A para todo A C Também podemos escrever C x A C x A Vejamos a noção de família ou coleção indexada de conjuntos Definição 219 Seja Γ um conjunto Assuma que para cada elemento γ Γ está associado um conjunto Aγ A coleção de tais conjuntos Aγ é dita ser uma família indexada de conjuntos indexada pelo conjunto Γ e denotada por Aγ γ Γ ou AγγΓ Observação 220 Se C Aγ γ Γ escrevemos C γΓ Aγ x x Aγ para algum γ Γ e C γΓ Aγ x x Aγ para todo γ Γ Note que dada qualquer coleção de conjuntos sempre é possível encontrar um conjunto de índices Γ e tornar esta coleção uma família indexada de conjuntos indexada por Γ Mais ainda se o conjunto de índices é finito Γ 1 2 3 n escrevemos Aγ γΓ Ai A1 A2 An e Aγ γΓ Ai A1 A2 An Se Γ ℕ escrevemos γΓ Aγ i1 Ai e γΓ Aγ i1 Ai Exemplo 221 Seja Ai i i ℕ0 Temos que A Aiiℕ 1 2 3 é uma família de conjuntos unitários Exemplo 222 Seja Ai ℕ with Ai i i ℕ0 Assim A Aiiℕ 1 2 3 2 3 4 3 4 5 Observe que para i j temos que Aj Ai Neste caso dizemos que A é uma família decrescente de conjuntos Exemplo 223 Para cada i ℕ0 seja Ai i i 1 2i 1 Encontre ni1 Ai Note que cada inteiro entre 1 e 2n 1 pertence a algum Ai da família e nenhum outro inteiro pertence a estes Ai Logo ni1 Ai 1 2 3 2n 1 Teorema 224 Seja Aγ γ Γ uma família vazia de subconjuntos de um conjunto U ou seja Γ Então a γΓ Aγ b γΓ Aγ U Prova a Note que mostrar que γ Aγ é equivalente a mostrar que para todo x U temos x γ Aγ Para x U temos que x γ Aγ x γ Aγ por notação x Aγ para algum γ pela definição de x Aγ para todo γ pela negação γ x Aγ e esta última proposição é verdadeira para todo x U pois γ é uma contradição Isso completa a demonstração da parte a b Temos que mostrar que para todo x U temos x γ Aγ Observe que por definição x γ Aγ x Aγ γ que é equivalente à proposição γ x Aγ que como visto na demonstração do item a é verdadeira para todo x U Os próximos dois teoremas generalizam para uma família qualquer resultados mostrados Teorema 225 Leis de Morgan Generalizadas Seja Aγ γ Γ uma família arbitrária de subconjuntos de um conjunto U Então a γΓ Aγc γΓ Acγ b γΓ Aγc γΓ Acγ Prova a Para todo x U temos x γΓ Aγc x γΓ Aγ definição de complementar γ Γx Aγ definição de união γ Γx Aγ negação γ Γx Acγ definição de complementar x γΓ Acγ Assim por definição de igualdade de conjuntos temos a igualdade do item a A demonstração da igualdade do item b fica como exercício Teorema 226 Leis Distributivas Generalizadas Sejam A um conjunto e C Bγ γ Γ uma família de conjuntos Então a A γΓ Bγ γΓA Bγ b A γΓ Bγ γΓA Bγ Prova Vamos provar a igualdade do item a a outra fica como exercício Um elemento x está no conjunto A γΓ Bγ se e somente se x A e x γΓ Bγ pela definição de Agora da definição de união de uma família qualquer de conjuntos temos que esta proposição é equivalente a x A e x Bγ para algum γ Γ que pode ser expressa como x A Bγ para algum γ Γ a qual por definição de é precisamente x γΓA Bγ o que mostra a pela definição de igualdade de conjunto 23 O Produto Cartesiano de Dois Conjuntos 41 Dados dois conjuntos A e B o produto cartesiano de A e B denotado por A B e o conjunto A B x x a b para algum a A e algum b B Note que em geral a b b a e A B B A Vejamos como esta nova operacao entre conjuntos se comporta com relacao as outras definidas anteriormente Teorema 228 Sejam A B e C conjuntos quaisquer Entao temos a A A b A B C A B A C c A B C A B A C d A B C A B A C Prova a Pela definicao de produto cartesiano temos A a b a A e b Como nao existe b temos que nao existe par ordenado cuja segunda coorde nada seja b assim A A outra igualdade e analoga b Aqui podemos assumir que os 3 conjuntos sao diferentes do vazio pois caso contrario a demonstracao segue facilmente doıtem a Para a A e x BC temos a x A B C a A x B C def de prod cartesiano a A x B x C def de a A x B x C associatividade do a A x B a A x C canc e comut do a A x B a A x C associatividade do a x A B a x A C def de prod cartesiano a x A B A C def de o que mostra a igualdade do ıtem b As demonstracoes de c e d ficam como exercıcio 23 O Produto Cartesiano de Dois Conjuntos Sejam A e B dois conjuntos arbitrários Para a A e b B utilizando o axioma da especificação podemos construir o conjunto a b x x a ou x b Note que como conjuntos a b b a Agora queremos definir a noção de par ordenado ou seja um conjunto com dois elementos dados onde possamos dizer qual é o primeiro e qual é o segundo elemento Para tanto precisamos da certeza que este par é também um elemento Isso é garantido pelo seguinte axioma Axioma do par Para dois conjuntos quaisquer existe um conjunto ao qual ambos pertencem Este axioma garante a existência do conjunto definido a seguir Definição 227 O par ordenado de a e b denotado por a b com primeira coordenada a e segunda coordenada b é o conjunto a b a a b 42 2 Teoria dos Conjuntos 24 Exercícios 1 Determine se as afirmacoes abaixo sao verdadeiras ou falsas justificando a 3 3 b 5 5 c 4 4 4 d 3 e 2 8 2 8 9 f 3 4 3 4 5 6 g A B CA B C A B C B h A B CA B C A B C i A B CA B A C B C j A A k A A l 2 Mostre que se A e um conjunto finito com n elementos entao A e finito e tem 2n elementos Mostre tambem que A e infinito se e somente se A e infinito 3 Sejam A e B conjuntos Determine se cada uma das afirmacoes abaixo sao ver dadeiras Se sim mostre caso contrario dˆe um contra exemplo a x A e A B x B b x A e A B x B c x A e A B x B d A B e x B x A e A B A B 4 Para A B e C conjuntos dados mostre que a C A B C A C B b C A B C A C B c A B A B A B C A B A C Se B A então A A B B A B A A A B 3 Relações 31 Definições e Exemplos Utilizando pares ordenados podemos estabelecer a teoria matematica das relacoes atraves da linguagem de conjuntos Comecamos considerando o conjunto AB onde A e o conjunto das mulheres e B e o conjunto dos homens Quando falamosMaria e esposa de Joaoestamos dizendo que Maria esta relacionada com Joao pela relacao ser esposa de ou seja o par ordenado a b onde a Maria e b Joao pertencem a relacao Note que o par b a nao pertence a relacao pois Joao nao e esposa de Maria Se a relacao fosse ser casado com entao ambos os pares estariam na relacao Formalmente temos Definição 31 Uma relacao entre dois conjuntos A e B denotada por RA B ou simplesmente por R e um subconjunto de A B Se um par a b R dizemos que a esta relacionado com b pela relacao R e escrevemos aRb Se A B entao RA A e dita ser uma relacao sobre um conjunto A ou uma relacao em A Se RA B e uma relacao em A B dizemos que R1 b a B A aRb e a relacao inversa de R Como conjuntos ha duas maneiras de representar uma relacao uma e listando os seus elementos e a outra e definindo uma regra na qual escolhemos os pares ordenados 45 46 3 Relacoes que satisfazem esta regra Exemplo 32 Exemplos de relacoes 1 Sejam A 1 2 3 e B a b c d Definimos a seguir 3 relacoes R1 1 a 1 b 3 c R2 2 a 2 b 1 a 1 b 3 a 3 b R3 2 Seja A a b c Definimos sobre A as relacoes R1 a a b b c c R2 a a a b b a b b c a c b c c R3 A A 3 Seja A Z Definimos sobre A as relacoes R1 a b Z Z a b R2 a b Z Z a b 4 Seja A Z Para as relacoes definidas no exemplo anterior temos R1 1 a b Z Z a b R1 2 a b Z Z b a Podemos visualizar algumas propriedades de uma relacao atraves de sua represen tacao grafica Para vermos isso necessitamos definir algumas nocoes Definição 33 Seja R uma relacao em AB O domınio de R denotado por DomR e o subconjunto de A dado por DomR a A aRb para algum b B A imagem de R denotado por ImR e o subconjunto de B dado por ImR b B aRb para algum a A Podemos colocar os pares ordenados da relacao R num diagrama coordenado de A B e o conjuntos destes pontos e dito ser o grafico ou diagrama cartesiano de R Outro tipo de representacao geometrica de uma relacao muito usado quando o conjunto A e finito e o diagrama de setas onde representamos os elementos de A A B A A B B Reflexiva Em cada ponto do diagrama deve ter um laço uma relação simétrica e transitiva Não é reflexiva e nem antisimétrica R3 a a b b a b b a b c é uma relação que não é simétrica nem transitiva nem reflexiva e nem antisimétrica 50 3 Relacoes de equivalˆencia determinada pelo elemento a modulo R Observe que o conjunto a e um subconjunto de A consistindo de todos os elementos de A aos quais a esta relacionado O conjunto das classes de equivalˆencia modulo R sera indicado por AR e chamado de conjunto quociente de A por R Note que se R e uma relacao de equivalˆencia sobre um conjunto nao vazio A entao para todo a A temos a a ou seja cada classe de equivalˆencia e um subconjunto nao vazio de A Exemplo 310 Considere a relacao de equivalˆencia R definidas no exemplo 355 ou seja A Z e R x y Z Z x y e multiplo de 3 Para 0 Z temos 0 x Z x e multiplo de 3 x Z x 3k para algum k Z 3Z Para 1 Z temos 1 x Z x 1 e multiplo de 3 x Z x 3k 1 para algum k Z 3Z 1 Para 2 Z temos 2 x Z x 2 e multiplo de 3 x Z x 3k 2 para algum k Z 3Z 2 Para 3 Z temos 3 x Z x 3 e multiplo de 3 x Z x 3k 3 3k 1 para algum k Z 3Z 0 Veremos no proximo teorema que de fato ZR 0 1 2 32 Relacoes de Equivalˆencias e Particoes 51 Exemplo 311 Considere a relacao de equivalˆencia R 1 1 2 2 3 3 4 4 5 5 2 5 5 2 3 5 5 3 2 3 3 2 mostre este fato Vamos calcular AR 1 1 2 2 3 5 3 2 3 5 4 4 5 2 3 5 Portanto AR 1 4 2 3 5 Com relacao as classes de equivalˆencia temos Teorema 312 Sejam R uma relacao de equivalˆencia sobre um conjunto nao vazio A e a b A As seguintes proposicoes sao equivalentes a aRb b a b c b a d a b Prova a b Decorre imediatamente da definicao de classe de equivalˆencia b c a b aRb pela definicao de classe bRa pois R e simetrica b a pela definicao de classe c d Note que a e b sao dois conjuntos assim mostrar que a b e equivalente a mostrar que a b e b a Mostremos que a b a outra inclusao e analoga Para x a temos que xRa e como por hipotese b a temos tambem que bRa Como R e simetrica obtemos xRa e aRb o que implica pela transitividade de R que xRb ou seja x b d a Seja x a b Entao pela definicao de classe temos que xRa e xRb Agora da propriedade simetrica e transitiva de R obtemos aRb Mostremos agora a afirmacao feita no final do exemplo anterior ou seja para A Z e R x y Z Z x y e multiplo de 3 temos ZR 0 1 2 E obvio que ZR 0 1 2 Agora se a ZR entao dividindo a por 3 obtemos que a 3q r com r 0 1 ou 2 Neste caso temos claramente que r a e pelo teorema anterior temos a r ou seja ZR 0 1 2 Relacoes de equivalˆencias estao diretamente relacionadas com a nocao de particao de um conjunto Definição 313 Seja A um conjunto não vazio Dizemos que uma família F de subconjuntos não vazios de A é uma partição de A se as seguintes afirmações são verdadeiras a dois elementos quaisquer de F ou são iguais ou são disjuntos b a união dos elementos de F é igual a A Teorema 316 Seja A um conjunto não vazio Se F é uma partição de A então existe uma relação de equivalência R sobre A tal que AR F Prova Para todo a b A definimos R por aRb existe X F tal que a b X Mostremos que R é uma relação de equivalência i Para cada a A desde que F A existe um X F tal que a X Assim aRa ou seja R é reflexiva ii Para a b A se aRb então pela definição de R existe um elemento X F tal que a b X o que claramente implica que bRa Logo R é simétrica iii Se a b c A são tais que aRb e bRc então existem X Y F tais que a b X e b c Y Assim b X Y ou seja X Y Como F é uma partição temos que X Y e então a c X Y o que mostra que aRc Logo R é transitiva Mostramos agora que AR F Dado a A temos que existe um único X F tal que a X onde a unicidade segue da propriedade a da definição de F Da definição de R é claro que a X o que implica que AR F Por outro lado para cada X F desde que X temos que existe a X Claramente X a o que mostra que AR F 54 3 Relacoes Dada uma relacao de ordem sobre um conjunto A dizemos que os elementos a b A sao comparaveis mediante R se aRb ou bRa Se quaisquer dois elementos de A sao comparaveis mediante R entao dizemos que R e uma ordem total sobre A e neste caso dizemos que A e um conjunto totalmente ordenado Em uma relacao de ordem se aRb tambem usaremos a notacao a b que lemos a precede b na relacao R Exemplo 319 Exemplos de relacoes de ordem 1 A relacao R a a b b c c a b a c b c e uma relacao de ordem total sobre A a b c Faca o diagrama de setas desta relacao e observe que nao ha dois pontos que nao estejam ligados por uma flecha Isso deve ocorrer sempre que a ordem for total 2 A relacao R definida sobre R por xRy x y e uma ordem total sobre R chamada a ordem usual 3 A relacao R definida sobre N por xRy x divide y e uma relacao de ordem sobre N que nao e total 4 A relacao de inclusao sobre uma famılia de subconjuntos de um dado conjunto e uma relacao de ordem que em geral nao e total Definição 320 Sejam A um conjunto ordenado pela relacao de ordem e S A um subconjunto nao vazio Dizemos que a Um elemento L A e um limite superior de S se a seguinte proposicao for verdadeira xx S x L isto e quando qualquer elemento de S precede L Exemplo 317 Dada a partição F a b c d e f do conjunto A a b c d e f temos a relação de equivalência associada R a a a b b a b b c c d d d e d f e d f d e e e f f e f f 33 Relacoes de Ordem 55 b Um elemento l A e um limite inferior de S se a seguinte proposicao for ver dadeira xx S l x isto e quando l precede qualquer elemento de S c Um elemento M S e um maximo de S se a seguinte proposicao for verdadeira xx S x M isto e quando M e um limite superior de S e M S d Um elemento m S e um mınimo de S se a seguinte proposicao for verdadeira xx S m x isto e quando m e um limite inferior de S e m S e O supremo de S e o mınimo caso exista do conjunto dos limites superiores de S f O ınfimo de S e o maximo caso exista do conjunto dos limites inferiores de S Exemplo 321 Para A R e S 0 1 com a ordem usual temos 1 O conjunto dos limites superiores de S e 1 2 O conjunto dos limites inferiores de S e 0 3 O maximo de S e 1 4 S nao tem mınimo 5 O supremo de S e 1 6 O ınfimo de S e 0 Exemplo 322 Para A 1 2 3 4 6 9 12 18 24 36 S 2 4 6 e a relacao de ordem sendo a divisibilidade temos 1 O conjunto dos limites superiores de S e 12 24 36 2 O conjunto dos limites inferiores de S e 1 2 34 Funcoes 57 Como e antisimetrica temos que M1 M2 34 Funções Aqui somente apresentaremos a definicao de funcao usando a nocao de relacao As propriedades e as nocoes de injetividade sobrejetividade bijetividade funcao composta e funcao inversa serao assumidas conhecidas para o desenvolvimento dos proximos capı tulos Normalmente o que vemos como definicao de funcao e Funcao e uma regra de correspondˆencia que associa a cada elemento x de um certo conjunto chamado de domınio da funcao um unico elemento y em um outro conjunto chamado de contradomınio da funcao A definicao formal de funcao usando conjuntos e a nocao de relacao e Definição 325 Sejam A e B conjuntos Uma funcao de A em B e uma relacao f de A em B satisfazendo as seguintes propriedades a Domf A b Se x A e y z B sao tais que x f y e x f z entao y z Escreveremos f A B para denotar que f e uma funcao de A em B 35 Exercícios 1 Determine quais das propriedades reflexiva simetrica transitiva antisimetrica sao satisfeitas por cada uma das seguintes relacoes sobre o conjunto R dos numeros reais a R x y y 1x b R x y x y 1 c R x y y2 x2 d R x y x y e R x y xy 0 2 Dˆe um exemplo de uma relacao R sobre um conjunto A que seja simetrica e transitiva e nao seja reflexiva Teorema 324 Seja S um subconjunto de um conjunto não vazio A e dita ser uma relação de ordem sobre S se R é reflexiva antisimétrica e transitiva Se existe uma relação de ordem sobre o conjunto A dizemos que A é um conjunto parcialmente ordenado ou simplesmente ordenado 58 3 Relacoes 3 Dˆe dois exemplos um listando os pares ordenados e o outro descrevendoos atraves de uma regra de relacoes que tenham as propriedades reflexiva e simetrica e nao tenham a transitiva 4 Sejam R uma relacao sobre A e a relacao identidade sobre um conjunto nao vazio A isto e x x x A Mostre que a R e reflexiva se e somente se R b Se R tiver ambas as propriedades simetrica e antisimetrica entao R c R e simetrica se e somente se R R1 d Se R e antisimetrica entao R R1 5 Sejam A um conjunto e R e R relacoes sobre A Diga se cada uma das seguintes proposicoes e verdadeira ou falsa justificando sua resposta a Se R e simetrica entao R1 e simetrica b Se R e antisimetrica entao R1 e antisimetrica c Se R e transitiva entao R1 e transitiva d Se R e reflexiva entao R R1 e Se R e simetrica entao R R1 f Se R e R sao simetricas entao R R e simetrica g Se R e R sao simetricas entao R R e simetrica h Se R e R sao transitivas entao R R e transitiva i Se R e R sao transitivas entao R R e transitiva j Se R e R sao antisimetricas entao R R e antisimetrica k Se R e R sao antisimetricas entao R R e antisimetrica l Se R e R sao reflexivas entao R R e reflexiva m Se R e R sao reflexivas entao R R e reflexiva 6 Existe algum conjunto A tal que toda relacao sobre A seja a Reflexiva b Simetrica c Transitiva d Antisimetrica 35 Exercıcios 59 Existe mais de um conjunto 7 Quais das relacoes dadas no primeiro exercıcio sao de equivalˆencia Justifique 8 a Verifique que a relacao R 1 1 2 2 3 3 4 4 5 5 2 5 5 2 3 5 5 3 2 30 3 2 e uma relacao de equivalˆencia em A 1 2 3 4 5 b Determine 1 2 3 4 e 5 c Determine AR 9 Seja a relacao sobre R definida por x y se e somente se x y Z para todo x y R Mostre que e uma relacao de equivalˆencia sobre R 10 Defina a relacao R sobre R por xRy se e somente se cosx cosy e senx seny para todo x y R a Mostre que R e uma relacao de equivalˆencia b Se a R determine a 11 Seja R3 x x1 x2 x3 xi R i 1 2 3 Defina em A R3 0 0 0 a seguinte relacao x y se existe α R tal que x αy para todo x y A a Mostre que e uma relacao de equivalˆencia b Descreva geometricamente x para algum x A 12 Seja f uma funcao real com domınio real Defina a relacao Rf pela regra xRfy fx fy Mostre que Rf e uma relacao de equivalˆencia 13 Em A N N defina a seguinte relacao a b c d a d b c para todo a b c d N 60 3 Relacoes a Mostre que e uma relacao de equivalˆencia b Encontre as seguintes classe de equivalˆencias 1 0 0 1 1 1 e 0 0 14 Defina em Z N a seguinte relacao a b c d ad bc para todo a c Z e b d N a Mostre que e uma relacao de equivalˆencia em Z N b Pense um pouco sobre o conjunto Z N Compareo com Q o conjunto dos numeros racionais 15 Seja R a relacao dos numeros naturais N definida por m e um multiplo de n Mostre que esta e uma relacao de ordem em N Esta e uma relacao de ordem total em N 16 Considere o conjunto S 2 4 8 2n e considere a relacao R definida no exercıcio anterior Mostre que S e um subconjunto de N totalmente ordenado 17 Seja S 2 3 4 5 ordenado por m divide n a Encontre todos os elementos maximais b Encontre todos os elementos minimais 18 Mostre que se a e b sao elementos minimais num conjunto A totalmente ordenado Entao a b 19 Considere a relacao de divisibilidade sobre o conjunto Z dos numeros inteiros R ab se e somente se c Z tal que b ac R e uma relacao de ordem sobre Z 20 Consideremos o conjunto dos numeros naturais que sao divisores proprios de 36 isto e E 2 3 4 6 9 12 18 e ordenemos E pela relacao de divisibilidade R a b se e somente se ab isto e c N tal que b ac R e uma relacao de ordem sobre E R e uma relacao de ordem total sobre E 21 Consideremos a ordem habitual sobre o conjunto N dos números naturais e seja E N N o produto cartesiano de N por si mesmo a Se a b e c d são dois elementos quaisquer de E então por definição a bRc d se e somente se a c e b d Mostre que R uma relação de ordem sobre E que não é total b Se a b e c d são dois elementos quaisquer de E colocaremos por definição a bRc d se e somente se a c ou a c e b d Mostre que R é uma ordem total sobre E 22 Seja R a relação de ordem sobre E a b c d e f g h i j com o seguinte diagrama de Hasse Determinar caso existam os limites superiores os limites inferiores o ínfimo o supremo o máximo e o mínimo de A d e e de B b d f 4 Noções de Cardinalidade 41 Conjuntos Equipotentes Enumeráveis e Contáveis Como podemos determinar quando dois conjuntos tˆem o mesmo tamanho Se tais conjuntos forem finitos podemos fazer isso contando os seus elementos Mas esta tecnica nao funciona para conjuntos infinitos Iremos determinar quando dois conjuntos tˆem o mesmo tamanho ou o mesmo numero de elementos nao contando quantos elementos cada um deles tem mas sim fazendo uma correspondˆencia entre cada elemento de um conjunto com um unico ele mento do outro e viceversa Mais especificamente temos Definição 41 Sejam A e B conjuntos Dizemos que A e B tˆem a mesma cardinali dade ou que eles sao equipotentes e escrevemos A B se existir uma funcao bijetora f A B Vale observar que com esta definicao estamos dizendo quando dois conjuntos tˆem o mesmo numero de elementos sem necessariamente dizer qual e esse numero Uma importante propriedade da nocao de conjuntos equipotentes e que podemos separar os conjuntos em classes de conjuntos que tˆem a mesma cardinalidade ou seja a relacao e de fato uma relacao de equivalˆencia Teorema 42 Para um conjunto universo U a relacao de equipotˆencia e uma relacao de equivalˆencia em U 63 64 4 Nocoes de Cardinalidade Prova Temos que mostrar que e reflexiva simetrica e transitiva i Para todo A U temos que I A A dada por Ia a para todo a A isto e a funcao identidade e uma bijecao Logo A A ii Se A B U sao tais que A B entao existe f A B bijetora Logo f1 B A tambem e bijetora o que mostra que B A iii Se A B C U sao tais que A B e B C entao existem f A B e g B C bijetoras Logo g f A C tambem e bijetora o que mostra que A C Ou seja e uma relacao de equivalˆencia como querıamos demonstrar Exemplo 43 Exemplos de cardinalidades de conjuntos 1 Sejam N o conjunto dos numeros naturais Entao N e 2N tˆem a mesma cardi nalidade ou seja o conjunto dos naturais e o conjunto dos naturais pares tˆem a mesma cardinalidade De fato basta observar que f N 2N definida por fn 2n para todo n N e uma funcao bijetora De maneira analoga mostrase que N e o conjunto dos naturais ımpares 2N 1 sao equipotentes 2 O conjunto dos numeros inteiros Z tem a mesma cardinalidade que N De fato basta observar que f Z N definida por fn 2n se n 0 2n 1 se n 0 para todo n Z e uma bijecao 3 Sejam a b e c d intervalos fechados de R onde a b e c d Entao a b c d De fato a funcao g a b c d definida por gx d c b ax a c para todo x a b e uma bijecao Usando restricoes da funcao g definida acima podese mostrar que se a b e c d sao numeros reais entao a b c d a b c d e a b c d 41 Conjuntos Equipotentes Enumeraveis e Contaveis 65 4 O intervalo 1 1 tem a mesma cardinalidade que R Basta ver que a funcao h 1 1 R definida por hx x 1 x para todo x 1 1 e uma bijecao Para uma melhor analise da cardinalidade de conjuntos necessitamos definir con junto finito infinito enumeravel nao enumeravel contavel etc E obvio que um conjunto infinito e um conjunto que nao e finito e viceversa Assim precisamos definir uma destas nocoes e teremos a outra Escolhemos definir conjunto infinito Definição 44 Seja A um conjunto Dizemos que a A e um conjunto infinito se A e equipotente a um subconjunto proprio de A b A e um conjunto finito se A nao for infinito c A e um conjunto enumeravel se A N d A e um conjunto contavel se A e finito ou enumeravel e A e um conjunto nao enumeravel se A nao e contavel Exemplo 45 Exemplos de conjuntos envolvendo as nocoes acima 1 Do exemplo anterior temos que N Z R e qualquer intervalo aberto fechado ou semiaberto de R sao exemplos de conjuntos infinitos 2 O conjunto vazio e finito pois nao contem subconjunto proprio 3 Para cada n N n 1 o conjunto Nn 1 2 n e finito Veremos por inducao sobre n Para n 1 o resultado e imediato desde que o unico subconjunto proprio de Nn e o vazio e nao existe uma bijecao f N1 Se n 1 suponhamos que o resultado vale para n e provaremos que ele vale para n 1 Mais adiante provaremos que isso implica que o resultado vale para todo n N Se Nn1 nao for finito entao existe um subconjunto proprio A de Nn1 tal que A Nn1 Seja f Nn1 A uma bijecao Entao a restricao f Nn Afn1 e claramente uma bijecao o que contradiz o fato de Nn ser finito 66 4 Nocoes de Cardinalidade 4 Segue diretamente do teorema 42 que N e um conjunto enumeravel Do exemplo 432 temos que Z tambem e um conjunto enumeravel Vejamos alguns resultados sobre conjuntos enumeraveis Teorema 46 Todo subconjunto infinito de um conjunto enumeravel e enumeravel Todo subconjunto de um conjunto contavel e contavel Prova Vamos demonstrar a primeira afirmacao A demonstracao da segunda afir macao fica como exercıcio Sejam A um conjunto enumeravel e B um subconjunto infinito de A Desde que A N podemos escrever A a1 a2 onde ai fi 1 para alguma bijecao f N A Seja n1 o menor ındice para o qual an1 B Desde que B e infinito temos que B an1 e tambem infinito mostre esta afirmacao Assim seja n2 o menor ındice para o qual an2 B an1 Tendo definido ank1 B seja nk o menor ındice para o qual ank B an1 an2 ank1 Usando que B e infinito temos que B an1 an2 ank1 para cada k N e infinito Assim temos uma funcao bijetora g N B dada por gk ank para cada k N o que mostra que B e enumeravel Teorema 47 O conjunto N N e enumeravel Prova Seja f N N N definida por fn m 2n3m Usando o Teorema Funda mental da Aritmetica temos que f e injetora Assim N N fN N N Como NN e um conjunto infinito mostre isso temos que fNN e infinito e pelo teorema anterior obtemos que N N e enumeravel Teorema 48 A uniao de dois conjuntos enumeraveis e enumeravel Prova Sejam A e B conjuntos enumeraveis Vamos mostrar que A B e enumeravel Consideremos dois casos 1 A B Como A N e N 2N pela transitividade de temos que A 2N De maneira analoga temos B 2N 1 Sejam f A 2N e g B 2N 1 as correspondentes bijecoes A funcao h A B 2N 2N 1 onde h f g e uma bijecao pois A B o que implica que A B 2N 2N 1 N 41 Conjuntos Equipotentes Enumeraveis e Contaveis 68 4 Nocoes de Cardinalidade tamente Assim dois numeros no intervalo 0 1 serao iguais se e somente se os dıgitos correspondentes em sua representacao decimal sao iguais Agora suponhamos por absurdo que 0 1 e um conjunto enumeravel Entao existe uma funcao bijetora f N 0 1 e consequentemente podemos listar os elementos de 0 1 como segue f0 0 a01a02a03 f1 0 a11a12a13 f2 0 a21a22a23 fk 0 ak1ak2ak3 onde cada akj 0 1 9 Vamos construir um elemento de 0 1 que nao esta na listagem acima ou seja vamos contradizer o fato de f ser sobrejetora Seja y 0 y1y2y3 onde yk 3 se akk 3 e yk 1 se akk 3 para todo k N Claramente y 0 1 mas y fk para todo k N pois yk akk Portanto 0 1 e nao enumeravel Corolário 413 O conjunto dos numeros reais R e nao enumeravel Prova Imediata pois R 0 1 Corolário 414 O conjunto dos numeros irracionais I e nao enumeravel Prova De fato se I for enumeravel como Q e enumeravel e R Q I terıamos que R seria enumeravel 42 Números Cardinais e a Hipótese do Contínuo Aqui nao iremos definir o que e um numero cardinal somente vamos introduzilos como uma nocao primitiva relacionada com o tamanho de conjuntos Assumiremos que esta nova nocao sera regida pelas seguintes leis C1 A cada conjunto A e associado um numero cardinal denotado por cardA e a cada numero cardinal a existe um conjunto A com cardA a 2 A B Neste caso para C B A temos A B A C e A C Como C B temos que C é enumerável ou finito Se C for enumerável recaímos no caso anterior Se C for finito é fácil ver que A C é enumerável Corolário 49 Sejam A1 A2 Ak conjuntos enumeráveis Então n k1 Ak é enumerável Teorema 410 O conjunto dos números racionais é enumerável Prova Vamos usar que cada número racional pode ser representado de maneira única como pq onde p Z q N 0 com mdc p q 1 Sejam Q pq p 0 e Q pq p 0 Temos então Q Q Q 0 e evidentemente Q Q Do teorema anterior temos que para mostrar que Q é enumerável é suficiente mostrar que Q é enumerável Para isso considere a função f Q N N definida por fpq p q É fácil ver que f é injetora Logo Q fQ N N Como claramente N Q N N é enumerável temos que fQ é um subconjunto infinito de um conjunto enumerável Do teorema 46 temos que fQ é enumerável Portanto Q fQ N ou seja Q é enumerável como queríamos Teorema 411 Todo conjunto infinito contém um conjunto enumerável Prova Seja X um conjunto infinito Então X portanto existe x1 X Considere o conjunto X x1 Como X é infinito existe x2 X x1 Considere o conjunto X x1 x2 Tendo escolhido xk X x1 x2 xk1 e observando que xk sempre existe para cada k N pois X é infinito temos que o conjunto x1 x2 xk xk k N é um subconjunto enumerável de X Vejamos agora alguns conjuntos não enumeráveis Teorema 412 O intervalo aberto 0 1 R é um conjunto não enumerável Prova Dado qualquer número real x 0 1 podemos expressálo na forma decimal x 0 x1x2x3 onde cada xi 0 1 9 Para obtermos a unicidade nesta representação os decimais finitos terão seu último dígito decrescido de uma unidade e adicionado 9s infin 42 Números Cardinais e a Hipótese do Contínuo 70 4 Nocoes de Cardinalidade objetivo deste curso Ela segue do seguinte resultado que enunciaremos sem demonstrar Teorema 417 SchröderBernstein Se A e B sao conjuntos tais que A e equipo tente a um subconjunto de B e B e equipotente a um subconjunto de A entao A B Corolário 418 Se A e B sao conjuntos tais que cardA cardB e cardB cardA entao cardA cardB Com isso temos que o conjunto dos numeros cardinais e um conjunto ordenado pela ordem Do exemplo 416 temos dois numeros cardinais transfinitos distintos cardN e cardR com cardN cardR Sejam ℵ0 cardN e ℵ1 cardR Note que ℵ0 e ℵ1 nao sao numeros reais A pergunta que surge e Existe algum conjunto cuja cardinalidade esta entre ℵ0 e ℵ1 A conjectura de que a resposta a esta pergunta e negativa e conhecida como a Hipotese do Contınuo Hipotese do Continuo Nao existe conjunto algum A com a propriedade ℵ0 cardA ℵ1 43 O Número Cardinal de um Conjunto Potência o Teorema de Cantor Seja X um conjunto Ja sabemos que se X e finito com n elementos entao X tambem e finito e tem 2n elementos Cantor provou que cardX cardX para qualquer conjunto X o que nos permite construir uma infinidade de numeros cardinais transfinitos por exemplo ℵ0 cardN cardN cardN Teorema 419 Cantor Se X e um conjunto entao cardX cardX Prova Se X entao cardX 0 e X Portanto cardX 1 0 C2 cardA 0 se e somente se A C3 Se A e A é finito isto é A 1 2 k para algum k N então cardA k C4 Para quaisquer dois conjuntos A e B temos cardA cardB se e somente se A B As leis C2 e C3 definem os números cardinais de conjuntos finitos ou seja o número cardinal de um conjunto finito é o número de elementos deste conjunto Em termos de teoria dos conjuntos C1 e C4 formam um axioma o axioma da cardinalidade Note que C2 e C3 são mais fáceis de serem aceitos enquanto que C1 e C4 são mais difíceis pois estas leis não expressam nada concretamente sobre cardA quando A é um conjunto infinito Dizemos que o número cardinal de um conjunto finito é um número cardinal finito e o de um conjunto infinito é um número cardinal transfinto Das propriedades C2 e C3 temos que os números cardinais finitos são precisamente os números naturais Assim temos uma relação de ordem natural 0 1 2 k k 1 Já para dois números cardinais transfintos a propriedade C4 nos diz quando eles são iguais ou não O problema agora é saber decidir quando um é menor que o outro Definição 415 Sejam A e B conjuntos Dizemos que A B ou que cardA cardB se existir uma função injetora f A B Dizemos que A B ou que cardA cardB se existir uma função injetora f A B e A B Exemplo 416 cardN cardR De fato existe f N R a inclusão que é injetora e N R pois R não é enumerável Vejamos se define uma relação de ordem no conjunto dos números cardinais i cardA cardA pois a identidade IA A A é injetora ii Se cardA cardB e cardB cardC então cardA cardC pois a composição de funções injetoras é injetora iii Se cardA cardB e cardB cardA então cardA cardB A demonstração que esta propriedade é verdadeira é mais complicada e foge do 44 Aritmetica Cardinal 71 Se X seja g X X a funcao definida por gx x para todo x X E claro que g e injetora o que mostra que cardX cardX Para mostrarmos que cardX cardX temos que mostrar que X X Suponhamos por absurdo que X X Seja f X X uma bijecao Considere S x X x fx X Desde que f e sobrejetora e S X temos que existe a X tal que S fa Se a S entao pela definicao de S temos que a fa S o que e uma contradicao Se a S entao novamente pela definicao de S temos que a fa S o que leva a uma contradicao Portanto X X como querıamos Para alguns autores a hipotese do contınuo e que nao existe um numero cardinal x tal que ℵ0 x cardN 44 Aritmética Cardinal 441 Adição de Números Cardinais Queremos uma definicao de adicao de numeros cardinais que generalize a nocao de adicao de numeros naturais ou seja dos numeros cardinais finitos Definição 420 Sejam a e b numeros cardinais A soma cardinal de a e b denotada por a b e o numeros cardinal cardA B onde A e B sao conjuntos tais que cardA a cardB b e A B Para mostrar que esta operacao esta bem definida devemos mostrar que sempre existem tais conjuntos A e B e que a definicao nao depende da escolha de tais conjuntos Dados a e b cardinais da propriedade C1 existem conjuntos X e Y tais que a cardX e b cardY Se X Y temos que A X 0 e B Y 1 sao conjuntos tais que cardA a cardB b e A B o que mostra que existem conjuntos A e B como descritos na definicao Se A e B sao conjuntos com A A B B e A B entao existem f A A e g B B bijetoras e podemos ver facilmente que f g AB AB e tambem bijetora o que mostra que AB AB ou seja cardAB cardAB Desde que a uniao de conjuntos e comutativa e associativa obtemos as propriedades correspondentes para soma cardinal 72 4 Nocoes de Cardinalidade Teorema 421 Sejam a b e c numeros cardinais Entao 1 a b b a 2 a b c a b c Exemplo 422 Encontre as seguintes somas cardinais 1 4 3 Desde que 4 card1 2 3 4 N4 N7 N4 5 6 7 card5 6 7 3 e N4 5 6 7 temos que 4 3 cardN7 7 o que coincide com a soma dos numeros naturais 2 ℵ0 ℵ0 Desde que N 2N 2N 1 esta uniao e disjunta card2N cardN ℵ0 e card2N 1 cardN ℵ0 temos ℵ0 ℵ0 ℵ0 3 ℵ1 ℵ0 Desde que 0 1 R temos que ℵ1 card0 1 Seja S 0 1 N Como 0 1 N temos que cardS ℵ1 ℵ0 Agora R 0 1 S e S R entao pelo teorema de SchroderBernstein temos cardR cardS ou seja ℵ1 ℵ0 ℵ1 442 Multiplicação de Números Cardinais Analogamente queremos uma definicao de multiplicacao de cardinais que generalize a multiplicacao dos naturais Definição 423 Sejam a e b cardinais O produto cardinal ab e definido como sendo o numero cardinal do produto cartesiano A B onde A e B sao conjuntos com cardA a e cardB b Exercício 424 Mostre que se A B A e B sao conjuntos com A A e B B entao A B A B ou seja que o produto cardinal esta bem definido Como no caso da adicao usandose propriedades do produto cartesiano de conjun tos mostrase as seguintes propriedades do produto de cardinais Teorema 425 Se a b e c sao cardinais entao 44 Aritmetica Cardinal 73 1 ab ba 2 abc abc 3 ab c ab ac Prova Exercıcio Exemplo 426 Calcule os seguintes produtos cardinais 1 1 a onde a e um numero cardinal arbitrario Seja A um conjunto com cardA a Como 1 A A temos que 1 a a 2 0 a onde a e um numero cardinal arbitrario Seja A um conjunto com cardA a Como A temos que 0 a 0 3 ℵ0 ℵ0 Desde que N N N temos que ℵ0 ℵ0 ℵ0 4 ℵ1 ℵ1 Vamos mostrar que ℵ1 ℵ1 ℵ1 Note que ℵ1 card0 1 Considere f 0 1 0 1 0 1 definida por f0 x1x2x3 0 y1y2y3 0 x1y1x2y2 E facil ver que f e injetora e consequentemente ℵ1 ℵ1 ℵ1 Por outro lado a aplicacao g 0 1 0 1 0 1 definida por gx x x para todo x 0 1 e claramente injetora o que mostra que ℵ1 ℵ1 ℵ1 Agora o resultado segue do teorema 417 443 Potências de Números Cardinais Sejam A e B conjuntos Denotaremos por BA o conjunto de todas as funcoes de A em B ou seja BA f A B f e funcao Definição 427 Sejam a e b numeros cardinais com a 0 Definimos a potˆencia cardinal ba como sendo o cardinal do conjunto BA onde A e B sao conjuntos com cardA a e cardB b O proximo teorema nos garante que esta operacao esta bem definida Teorema 428 Sejam A B X e Y conjuntos tais que A X e B Y Entao BA Y X Prova Desde que A X e B Y temos que existem funções bijetoras g A X e h B Y Queremos definir uma bijeção entre BA e YX Para cada f BA temos A f B g X ψf Y h onde definimos ψf YX por ψf h f g1 Agora é fácil mostrar que ψ BA YX é uma bijeção Como propriedades da potenciação de cardinais temos Teorema 429 Sejam a b x e y números cardinais Então 1 axr ay axy 2 axy axy 3 abr ax br Prova Exercício Com a noção de potenciação podemos calcular a cardinalidade do conjunto das partes de um conjunto A que generaliza o resultado que diz que se A tem n elementos então ϕA tem 2n elementos Teorema 430 Seja A um conjunto Então cardϕA 2cardA Prova Seja B 0 1 Agora é suficiente mostrarmos que ϕA BA Assim queremos encontrar uma função bijetora ψ ϕA BA Para cada X ϕA considere fX BA definido por fXa 0 se a 6 X 1 se a X que é a função característica de X Assim definimos ψX fX para cada X ϕA É fácil ver que para X Y ϕA temos X Y se e somente se fX fY ou seja ψ é injetora Agora para cada f BA seja X a A fa 1 Claramente temos f fX ou seja ψ é sobrejetora Portanto cardϕA cardBA 2cardA Como consequência deste teorema temos que cardϕN 2ℵ0 Vamos finalizar o estudo sobre cardinalidades mostrando que 2ℵ0 ℵ1 ou seja que R ϕN têm a mesma cardinalidade Teorema 431 2ℵ0 ℵ1 Prova Usando o teorema de SB teorema 417 é suficiente mostrarmos que 2ℵ0 ℵ1 e 2ℵ0 ℵ1 Note que ℵ0 cardQ o que implica que 2ℵ0 cardϕQ Considere f R ϕQ definida por fa x Q x a ϕQ para cada a R Se a e b são números reais distintos então sem perda de generalidade podemos supor que a b Logo existe r Q tal que a r b o que implica que r fb e r 6 fa o que mostra que fa 6 fb Consequentemente f é uma função injetora Portanto ℵ1 cardR cardϕQ 2ℵ0 Por outro lado é fácil ver que a função ψ 0 1N R definida por ψg 0g0g1g2 R para cada g N 0 1 é injetora o que mostra que 2ℵ0 ℵ1 como queríamos Corolário 432 ℵ0 ℵ1 Prova Segue do teorema acima e do teorema de Cantor 76 4 Nocoes de Cardinalidade 5 Mostre que f N Z definida por fn n 2 se n e par n 1 2 se n e ımpar e bijetora Conclua que N Z 6 Seja X um conjunto infinito x0 X e Y X finito Mostre que a X x0 e infinito b X Y e infinito c cardX cardX x0 d cardX cardX Y 7 Para todo a b R com a b mostre que os intervalos seguintes sao equivalentes a R e consequentemente todos sao nao enumeraveis a b a b a b b a b e a 8 Seja X um conjunto com cardX ℵ0 Se A X e tal que cardA ℵ0 mostre que cardX A cardX 9 Sejam A B A e B conjuntos tais que cardA cardA e cardB cardB A B e A B Mostre que cardA B cardA B 10 Sejam X Y Z e W conjuntos tais que X Y e Z W Mostre que X Z Y W 11 Seja n um numero cardinal finito Mostre que n ℵ0 12 Seja a o cardinal de um conjunto infinito Mostre que ℵ0 a Conclua que ℵ0 cardN e o menor cardinal transfinito 13 Mostre que se A B e C sao conjuntos tais que A B C e A C entao A B Sug Use o Teorema de SchroderBerstein 14 Sejam A e B conjuntos Mostre que se A B entao A B 15 Sejam A B e C conjuntos Mostre que a Se cardA cardB e cardB cardC entao cardA cardC 45 Exercıcios 77 b Se cardA cardB e cardB cardC entao cardA cardC 16 Determine as seguintes operacoes cardinais onde n card1 2 n a n ℵ0 b n ℵ1 c ℵ0 ℵ1 d n ℵ0 e n ℵ1 f ℵ0 ℵ1 g ℵ1 ℵ1 17 Mostre que ℵℵ0 0 ℵ1 45 Exercícios 1 Seja A um subconjunto infinito de N Mostre que cardN cardA 2 Sejam A B conjuntos tais que A N e B N Mostre que a A B N b A B N 3 Sejam A1 An conjuntos tais que Ai N para todo i 1 n Mostre que ni1 Ai N ou seja a união finita de conjuntos enumeráveis é enumerável 4 Seja AnnN uma família de conjuntos com Ai N para cada i N Mostre que i1 Ai N ou seja a união enumerável de conjuntos enumeráveis é enumerável 5 Os Números Naturais 51 Os Axiomas de Peano Para a construcao logica formal dos numeros naturais Peano escolheu trˆes con ceitos primitivos o zero o numero natural e a relacao e sucessor de Assumindo estes conceitos primitivos ele deu a caracterizacao dos numeros naturais atraves de cinco axiomas chamados axiomas de Peano que sao 1 Zero e um numero natural 2 Se a e um numero natural entao a tem um unico sucessor que tambem e um numero natural 3 Zero nao e sucessor de nenhum numero natural 4 Dois numeros naturais que tˆem sucessores iguais sao iguais 5 Se um conjunto S de numeros naturais contem o zero e tambem o sucessor de cada um de seus elementos entao S e o conjunto de todos os numeros naturais Usaremos as notacoes 0 para indicar o zero a para indicar o sucessor de um numero natural a e N para indicar o conjunto de todos os numeros naturais Com estas notacoes podemos reescrever os axiomas de Peano como 1 0 N 2 aa N a N 79 80 5 Os Numeros Naturais 3 aa N a 0 4 a ba b a b 5 Se S N e valem as propriedades i 0 S ii aa S a S entao S N O axioma 1 garante que N Em 2 subentendese a unicidade do sucessor O axioma 5 chamase axioma da inducao completa Vejamos agora algumas propriedades dos numeros naturais que decorrem destes axiomas Proposição 51 Se a N entao a a Prova Seja S a N a a Queremos mostrar que S N Pelo axioma 5 temos que basta mostrar que S satisfaz as hipoteses i e ii de tal axioma De 3 temos que 0 S o que mostra que S satisfaz o item i de 5 Mais ainda para todo a N se a S entao pela definicao de S temos que a a Do axioma 4 segue que a a o que implica que a S o que mostra que S satisfaz o item ii de 5 Portanto S N Proposição 52 Todo numero natural diferente de zero e sucessor de algum numero natural Prova Seja S 0 y N y 0 e y x para algum x N Por definicao 0 S o que mostra que S satisfaz i de 5 Seja a S Se a 0 entao 0 a 0 ou seja 0 S Se a 0 entao a b para algum b N o que implica que a b ou seja a S Assim S satisfaz ii de 5 Portanto o axioma 5 garante que S N o que mostra a proposicao O proximo resultado e muito importante para quando queremos mostrar que algum resultado vale para todos os numeros naturais Proposição 53 Primeiro Princípio de Indução Completa Suponhamos que a todo numero natural n esteja associada uma afirmacao Pn tal que i P0 e verdadeira 52 Adicao em N 81 ii Para todo r N se Pr e verdadeira entao Pr e verdadeira Entao Pn e verdadeira para todo n N Prova Segue imediatamente do fato que S n N Pn e verdadeira satisfaz as hipoteses do axioma 5 Uma boa visualizacao deste princıpio e o chamado efeito domino 52 Adição em N A operacao de adicao em N e definida por recorrˆencia da seguinte forma a 0 a para todo a N a b a b para todo a e b N Para os numeros naturais a b e c na expressao a b c a e b sao ditos serem as parcelas e c a soma Como esperado da forma mais natural possıvel adotaremos as seguintes notacoes 0 1 1 2 2 3 Com estas notacoes temos por exemplo que 1 1 1 0 1 0 1 2 1 2 1 1 1 1 2 3 2 1 2 0 2 0 2 3 a 1 a 0 a 0 a para todo a N Antes de apresentarmos as propriedades da operacao de adicao vamos mostrar alguns fatos basicos Proposição 54 Para todo a N temos 0 a a e 1 a a Prova Considerando Pa 0 a a para a N temos i P0 e verdadeira pois 0 0 0 ii Para todo r N se Pr e verdadeira entao 0 r r Da definicao da adicao e deste fato temos 0 r 0 r r ou seja Pr e tambem verdadeira 82 5 Os Numeros Naturais Assim pelo primeiro princıpio de inducao temos que Pa e verdadeira para todo a N o que mostra que 0 a a para todo a N Agora para a N se Pa 1 a a entao temos i P0 e verdadeira pois 1 0 1 0 ii Para todo r N se Pr e verdadeira entao 1 r r Entao 1 r 1 r r ou seja Pr e tambem verdadeira Assim de 53 temos que Pa e verdadeira para todo a N o que completa a demonstracao da proposicao Usando a definicao da adicao de numeros naturais e a proposicao acima mostraremos as principais propriedades da operacao de adicao Teorema 55 Para todo a b e c N temos a Associativa a b c a b c b Comutativa a b b a c Elemento neutro O zero e o elemento neutro da adicao d Lei do Cancelamento Se a b a c entao b c e Se a b 0 entao a b 0 Prova a Faremos por inducao sobre c ou seja a afirmacao Pc e a b Na b c a b c i P0 e verdadeira pois a b 0 a b a b 0 ii Para todo r N se Pr e verdadeira entao abr abr Entao a b r a b r a b r a b r a b r ou seja Pr e tambem verdadeira Portanto pelo primeiro princıpio de inducao temos que Pc e verdadeira para todo c N como querıamos b Mostraremos usando inducao sobre b e 54 i Se b 0 entao a 0 a 0 a por 54 53 Multiplicacao em N 83 ii Se r N e tal que ar ra entao ar ar ra ra De 54 e do item a obtemos r a r 1 a r 1 a r a ou seja o resultado vale para r Assim de 53 o resultado vale para todo b N como querıamos c Decorre do item b e do mostrado acima que 0a a a0 para todo a N Resta mostrar que o zero e o unico elemento de N satisfazendo este fato ou seja que o elemento neutro e unico mostre este fato como exercıcio d Por inducao sobre a i Se a 0 entao 0 b 0 c o que implica que b c ii Se o resultado vale para r N e rb rc usando o item b obtemos que r b r b e entao r b r c e do axioma 4 temos r b r c Por hipotese de inducao temos que b c Assim o resultado vale para r Agora o resultado segue de 53 e Sejam a e b N tais que a b 0 e suponhamos que b 0 Entao pela proposicao 52 temos que b r para algum r N Assim 0 a b a r a r o que contradiz o axioma 3 Consequentemente b 0 e a a 0 a b 0 Observação 56 Observe que de 54 e 55 b segue que a b a b para todo a e b N 53 Multiplicação em N A operacao de multiplicacao em N e definida tambem por recorrˆencia por a 0 0 para todo a N a b a b a para todo a e b N 84 5 Os Numeros Naturais Na multiplicacao a b c a e b sao os fatores e c e o produto Vejamos alguns exemplos 1 1 1 0 1 0 1 0 1 1 1 2 1 1 1 1 1 1 1 2 2 1 2 0 2 0 2 0 2 2 a 1 a 0 a 0 a 0 a a para todo a N Decorre da definicao e de 53 os seguintes fatos basicos Proposição 57 Para todo a N temos 0 a 0 e 1 a a Prova Para mostrar que 0 a a para todo a N faremos por inducao sobre a Se a 0 o resultado segue da definicao Se 0 r 0 entao 0 r 0 r 0 0 0 0 E o resultado segue de 53 Novamente por inducao sobre a mostraremos que 1 a a para todo a N Se a 0 entao 1 0 0 por definicao Se 1 r r entao 1 r 1 r 1 r 1 r e o resultado segue pelo primeiro princıpio de inducao Usando a definicao da multiplicacao de numeros naturais e a proposicao acima mostraremos as principais propriedades da operacao de multiplicacao Teorema 58 Para todo a b e c N temos a Associativa a b c a b c b Comutativa a b b a c Elemento neutro O 1 e o elemento neutro da multiplicacao d Distributivas a b c a b a c e a b c a c b c e Lei do anulamento do produto Se a b 0 entao a 0 ou b 0 Prova Para demonstrarmos a associatividade e a comutatividade necessitamos da distributividade Assim mostraremos primeiro o item d d Por inducao sobre c Se c 0 temos a b 0 a b a b a 0 Se a b r a b a r entao a b r a b r a b r a a b a r a a b a r a a b a r Logo pelo primeiro princıpio de inducao temos que a b c a b a c para todo a b e c N 54 Relacao de Ordem em N 85 Para demonstrarmos a outra propriedade distributiva novamente usaremos in ducao sobre c Se c 0 entao a b 0 0 a 0 b 0 Se abr arbr entao abr abrab arbrab Usando a associatividade e a comutatividade da adicao obtemos a b r a r a b r b a r b r e o resultado segue pelo primeiro princıpio de inducao a Por inducao sobre c Se c 0 da definicao temos ab 0 a0 0 ab 0 Se a b r a b r entao a b r a b r b e do item d obtemos a b r a b r a b a b r a b a b r Logo pelo primeiro princıpio de inducao temos que a b c a b c para todo a b e c N b Por inducao sobre b Se b 0 entao da definicao e de 57 temos a 0 0 0 a Se a r r a entao a r a r a r a a Usando a associatividade e o fato que 1 a a de 57 obtemos r a a r 1 a r a e pelo primeiro princıpio de inducao obtemos a comutatividade do produto de numeros naturais c Da definicao e de 57 temos que a1 a 1a para todo a N Resta mostrar a unicidade do elemento neutro que fica como exercıcio e Se a b 0 e b 0 entao de 52 temos que b r para algum r N Logo 0 a b a r a r a o que implica do teorema 55 e que a a r 0 54 Relação de Ordem em N Para a e b em N considere a seguinte relacao a b b a u para algum u N Se b a u para algum u N com u 0 escrevemos a b O proximo teorema nos mostra que e uma relacao de ordem total sobre N Teorema 59 A relacao e uma relacao de ordem total sobre N Prova De fato valem as seguintes propriedades i e reflexiva ou seja para todo a N temos a a pois a a 0 86 5 Os Numeros Naturais ii e antisimetrica pois para todo a e b N se a b e b a entao existem u e v N tais que b a u e a b v Logo b b v u De onde obtemos v u 0 o que implica de 55 e que u v 0 ou seja a b iii e transitiva pois para todo a b e c N se a b e b c entao existem u e v N tais que b a u e c b v Assim c a u v a u v o que mostra que a c iv Quaisquer dois elementos de N sao comparaveis com respeito a relacao De fato para cada b N considere o conjunto Sb n N n b v para algum v N b n u para algum u N i 0 Sb pois b 0 b o que mostra que n 0 satisfaz a segunda condicao para pertencer a Sb ii Se r Sb entao r b v para algum v N ou b r u para algum u N Se r b v para algum v N entao r b v b v para algum v N ou seja r Sb Se b r u para algum u N com u 0 entao u d para algum d N e neste caso b r d r d o que mostra que r Sb Se b r entao r b b 1 o que mostra que r Sb De i e ii pelo primeiro princıpio de inducao temos que Sb N Consequen temente para todo b N qualquer que seja a N temos que a Sb ou seja a b v ou b a u com u e v N o que mostra que b a ou a b concluindo a demonstracao do teorema O proximo resultado mostra que esta relacao de ordem e compatıvel com as ope racoes de adicao e multiplicacao em N No que segue usaremos a notacao ab para denotar a b com a e b N Teorema 510 Para todo a b e c N temos a Compatibilidade com a adicao Se a b entao a c b c b Compatibilidade com a multiplicacao Se a b entao ac bc 54 Relacao de Ordem em N 87 Prova a Se a b entao existe u N tal que b a u Logo da comutatividade e associatividade da adicao temos b c a u c a c u o que mostra que a c b c b Se a b entao existe u N tal que b a u Logo da distributividade temos bc a uc ac uc com uc N ou seja ac bc Com respeito a sucessores temos Proposição 511 Se a e b N sao tais que a b entao a b Prova Exercıcio Um importante resultado que esta relacionado com o axioma 5 da construcao dos naturais e o princıpio do menor elemento Teorema 512 Princípio do menor número natural Todo subconjunto nao vazio de N tem mınimo Prova Seja S N com S Queremos mostrar que existe minS Para tanto considere H n N n x para todo x S Como S N temos que 0 a para todo a S ou seja 0 H Desde que S temos que existe a S Para tal elemento a 1 H pois a a 1 a Assim temos que H N e pelo axioma 5 segue que existe b N tal que b H e b H Mostremos que b minS De fato como b H temos que b x para todo x S Resta portanto mostrarmos que b S Suponhamos por absurdo que b S Entao b x para todo x S e pela proposicao 511 b x para todo x S o que implica que b H o que e uma contradicao Portanto b S e b minS como querıamos Depois da construcao axiomatica dos numeros naturais uma pergunta que surge naturalmente e Sera que o conjunto formado por zero e seus sucessores esgota real mente o conjunto dos numeros naturais Ou seja sera que nao haveria mais numeros naturais entre um natural e seu sucessor Mostraremos que nao Proposição 513 Para cada a N nao existe x N tal que a x a 88 5 Os Numeros Naturais Prova Suponhamos por absurdo que existam a e x N tais que a x a Como a x temos que existe u N com u 0 tal que x a u Mais ainda como x a a 1 temos que existe v N com v 0 tal que a 1 x v Logo a 1 a u v a u v o que implica pelo lei do cancelamento da adicao que u v 1 Mas v 0 ou seja v c para algum c N Assim 1 u v u c u c 1 u c 1 e novamente pela lei do cancelamento da adicao obtemos u c 0 Entao de 55 e u c 0 o que e uma contradicao pois u 0 Portanto nao existe x N tal que a x a Um resultado util na demonstracao de outros e a lei da tricotomia em N Proposição 514 Lei da Tricotomia Para todos a e b em N vale uma e somente uma das relacoes a b ou a b ou b a Prova Para numeros naturais a e b desde que e uma ordem total em N temos que a b ou b a Entao b a u com u N ou a b v com v N Se a b entao temos que u 0 e v 0 ou seja se a b entao a b ou b a Resta mostrar que estas duas afirmacoes nao podem ocorrer simultaneamente De fato se a b e b a entao b a u com u 0 e a b v com v 0 Assim a a u v a u v o que implica do cancelamento da adicao que u v 0 com u 0 e v 0 o que contradiz 55 e Portanto o resultado segue Usando a lei da tricotomia podemos mostrar que vale a lei do cancelamento para o produto Proposição 515 Lei do Cancelamento Se a b e c N sao tais que c 0 e ac bc entao a b Prova Se a b entao existe u N com u 0 tal que b a u Multiplicando por c ambos os lados obtemos bc a uc ac uc Mas por hipotese ac bc entao uc 0 o que contradiz a Lei do Anulamento pois u 0 e c 0 De maneira analoga mostrase que nao pode ocorrer b a Consequentemente pela lei da tricotomia temos a b como querıamos Finalizamos este capıtulo com o seguinte resultado Proposição 516 Se a e b N sao tais que ab 1 entao a 1 e b 1 55 Exercıcios 89 Prova Se ab 1 como 1 0 temos pela Lei do Anulamento que a 0 e b 0 Logo a 1 e b 1 Suponhamos que a 1 Entao existe u N com u 0 tal que a 1 u Como b 1 v para algum v N temos 1 ab 1 u1 v 1 u v uv Usando o cancelamento para a adicao e 55 e obtemos u v uv 0 o que e uma contradicao Logo a 1 e consequentemente b 1b ab 1 como querıamos 55 Exercícios 1 Usando a lei da tricotomia mostre que para a b e c N se ab ac com a 0 entao b c 2 Mostre as propriedades abaixo relativas aos numeros naturais usando o princıpio de inducao a 12 23 n n 1 nn 1n 2 3 para todo numero natural n 1 b Se a 2 entao 1 a an an1 para todo numero natural n 1 c Se a 2 entao 2an an1 para todo numero natural n 1 d 1 3 2n 1 n2 para todo numero natural n 1 e Se n 3 entao 2n3 3n2 3n 1 f 12 22 32 n2 n 2n 1n 1 6 para todo numero natural n 1 3 Mostre usando inducao que o numero de subconjuntos de um conjunto finito com n elementos e 2n 4 Mostre que o produto de quatro numeros naturais consecutivos acrescidos de 1 e um quadrado perfeito 5 Seja x N Mostre que 1 xn 1 nx para todo n 2 6 Sejam a e b numeros naturais tais que a b 1 Mostre que a 1 ou b 1 7 Sejam a e b numeros naturais nao nulos Mostre que a ab e b ab 8 Sejam a e b numeros naturais nao nulos tais que ab 2 Mostre que a b 1 90 5 Os Numeros Naturais 9 Sejam a e b numeros naturais tais que a b 3 Mostre que a 1 ou b 1 10 Sejam a e b numeros naturais nao nulos tais que a b 3 Mostre que a 1 ou b 1 11 Mostre que dados a e b numeros naturais existe um numero natural n tal que na b Propriedade Arquimediana em N 6 Os Números Inteiros No conjunto dos numeros naturais temos que a equacao aX b com a e b N tem solucao se e somente se a b Mais ainda usando que vale o cancelamento para a adicao temos que quando esta equacao tem solucao ela e unica Queremos ampliar o conjunto dos naturais construindo um conjunto onde esta equacao sempre tenha solucao unica mesmo quando nao temos a b Note que a solucao sera b a com a e b N Assim queremos construir um conjunto contendo N onde faca sentido esta diferenca e que contenha todas as diferencas deste tipo Seguindo essa ideia intuitiva a construcao formal dos numeros inteiros surgiu da necessidade de se ampliar o conjunto dos naturais para definir a diferenca entre dois numeros naturais a e b mesmo para b a Observe por exemplo que expressoes do tipo 83 105 50 116 represen tam todas o numero 5 Mas seria muito bom se tivessemos uma certa unicidade de representacao Note que a igualdade 83 105 em N e equivalente a 85 103 Isso nos ajuda a entender a construcao que faremos a seguir Considere em N N a relacao definida por a b c d a d b c para todo a b e c d N N A relacao e uma relacao de equivalˆencia sobre N N De fato i e reflexiva pois para cada a b N N temos a b b a ou seja a b a b 91 92 6 Os Numeros Inteiros ii e simetrica pois para a b e c d N N com a b c d temos a d b c o que implica que c b d a ou seja c d a b iii e transitiva pois para a b c d e e f N N com a b c d e c d e f temos a d b c e c f d e Somando f em ambos os lados da primeira igualdade e b da segunda por transitividade obtemos a d f e d b e portanto a f b e ou seja a b e f Esta relacao de equivalˆencia determina uma particao de N N em classes de equi valˆencia Para cada a b N N seja a b a classe de equivalˆencia determinada por a b N N isto e a b x y N N x y a b x y N N x b y a O conjunto quociente de N N pela relacao ou seja o conjunto de todas as classes de equivalˆencia a b com a b N N sera indicado por Z Assim Z N N a b a b N N Por exemplo 5 1 5 1 4 0 6 2 3 2 3 2 4 3 5 4 2 5 2 5 0 3 3 6 61 A adição em Z Para os numeros naturais 4 51 e 2 31 temos que 42 5131 5 3 1 1 Isso nos leva a entender o porque da seguinte definicao Definição 61 Sejam x a b e y c d elementos quaisquer de Z Definimos a adicao de x com y e indicamos por x y como sendo o elemento de Z x y a c b d Como estamos definindo a adicao de classes de equivalˆencia necessitamos mostrar que esta definicao nao depende da escolha dos representantes de cada classe de equiv alˆencia 61 A adicao em Z 93 Exercício 62 Mostre que a operacao de adicao esta bem definida isto e se a b a1 b1 e c d c1 d1 mostre que a c b d a1 c1 b1 d1 Para a adicao em Z temos as principais propriedades Teorema 63 Para todo x y e z Z temos a Associativa x y z x y z b Comutativa x y y x c Elemento neutro Existe 0 0 0 x x N N tal que x 0 x para todo x Z d Elemento oposto Para cada x Z existe x Z tal que x x 0 e Lei do cancelamento Se x z y z entao x y Prova a Sejam x a b y c d e z e f elementos de Z Entao usando a associatividade da adicao de numeros naturais obtemos x y z a b c d e f a c b d e f a c e b d f a c e b d f a b c e d f a b c d e f x y z o que mostra o ıtem a b Exercıcio c Para todo x a b Z queremos mostrar que existe 0 Z tal que x 0 x Seja 0 a b Z satisfazendo esta igualdade Entao x 0 a b a b a a b b a b x se e somente se a a b b a b ou seja a a b b b a em N Usando as propriedades da adicao de numeros naturais obtemos a b Assim existe 0 a a 0 0 Z satisfazendo o requerido d Dado x a b Z seja x a b Z tal que x x 0 Entao a a b b 0 0 o que implica que a a b b em N Mas esta igualdade e equivalente a x b a o que mostra a afirmacao do item d Se x z y z então de d temos que existe z Z tal que z z 0 Assim usando as propriedades mostradas acima obtemos x x 0 x z z x z z y z z y 0 y como queríamos mostrar 62 A multiplicacao em Z 95 As principais propriedades da operacao de multiplicacao sobre Z sao Teorema 67 Para todos x y e z Z temos a Associativa xyz xyz b Comutativa xy yx c Elemento Neutro Existe 1 1 0 Z tal que 1 x x para todo x Z d Distributiva xy z xy xz e Lei do Anulamento Se x e y Z sao tais que xy 0 entao x 0 ou y 0 Prova A demonstracao dos resultados dos ıtens a b e d ficam como exercıcio c Para todo x a b Z queremos encontrar x a b Z tal que xx x Se existe tal elemento x entao x a b xx a b a b aa bb ab ba ou seja a b aa bb ab ba o que e equivalente a a ab ba baa bb em N para todo a e b N Em particular tomando a 0 temos ba b1 b em N para todo b N Para b 0 temos a 1 b e mais ainda substituindo a 1 b na equacao xx x obtemos a ab b1 b ba1bbb em N Assim x a b 1 b b 1 0b b 1 0 Da maneira como foi encontrado x e o unico elemento de Z satisfazendo esta igualdade o qual denotaremos por 1 1 0 d Da observacao 64 temos que cada x Z e da forma x a 0 ou x 0 a com a N Entao para mostrarmos a Lei do Anulamento em Z consideremos x e y Z tais que xy 0 e separemos em quatro casos i x a 0 e y b 0 com a e b N ii x a 0 e y 0 b com a e b N iii x 0 a e y b 0 com a e b N iv x 0 a e y 0 b com a e b N 96 6 Os Numeros Inteiros E facil ver que em todos os casos recaımos na igualdade ab 0 em N e pela lei do anulamento em N obtemos a 0 ou b 0 o que implica que x 0 ou y 0 em Z O conjunto Z com as operacoes de adicao e multiplicacao introduzidas acima e dito ser o conjunto dos numeros inteiros e seus elementos sao chamados numeros inteiros Mais ainda usando a observacao 64 podemos separar este conjunto em dois subconjuntos Z a 0 Z a N e Z 0 a Z a N Os elementos de Z sao ditos serem inteiros positivos e os de Z inteiros negativos Note que para x Z temos x Z se e somente se x Z Esta nomenclatura ficara clara na proxima secao 63 Relação de Ordem em Z A relacao de ordem em Z e definida de maneira analoga a dos numeros naturais Definição 68 Sejam x e y Z Dizemos que x e menor ou igual a y e escrevemos x y se x y z para algum z Z Tambem podemos escrever y x e dizer y e maior ou igual a x Se z Z com z 0 escrevemos x y e dizemos x e menor do que y Equivalentemente y x Observe que para todo x Z temos que 0 x pois x 0 x e para y Z temos que y 0 pois y Z e 0 y y Isso justifica a nomenclatura usada no final da secao anterior Proposição 69 A relacao e uma relacao de ordem total sobre Z Prova Demonstrar que e uma relacao de ordem sobre Z fica como exercıcio Mostraremos somente que e total ou seja que quaisquer dois elementos de Z sao comparaveis com respeito a esta relacao Sejam x e y Z Temos novamente quatro casos a considerar i x a 0 e y b 0 com a e b N Neste caso como a b ou b a em N temos que existe u N tal que b a u ou a b u Assim y b 0 a u 0 x u 0 ou 64 A Imersao de N em Z 97 x a 0 b u 0 y u 0 com u 0 Z o que mostra que x y ou y x ii x a 0 e y 0 b com a e b N Neste caso x a 0 a b b a b 0 y com a b 0 Z ou seja y x iii x 0 a e y b 0 com a e b N Analogo ao caso anterior obtemos neste caso que x y iv x 0 a e y 0 b a e b N De maneira analoga ao caso i obtemos x y ou y x Note que como consequˆencia da proposicao anterior temos que se x Z e y Z entao x y O proximo resultado mostra que esta relacao de ordem e compatıvel com as opera coes de adicao e multiplicacao em Z Proposição 610 Sejam x y e z Z a Compatibilidade com a adicao Se x y entao x z y z b Compatibilidade com a multiplicacao Se x y e 0 z entao xz yz Prova a Se x y entao existe w Z tal que y x w Logo de 67 segue que y z x w z x z w com w Z ou seja x z y z b Se x y entao existe w a 0 Z tal que y xw Se z b 0 novamente de 67 obtemos yz x wz xz wz com wz ab 0 Z Portanto xz yz 64 A Imersão de N em Z Nesta secao estamos interessados em identificar N com um subconjunto de Z Isto sera feito atraves de uma imersao ou seja uma funcao injetora f N Z que preserva as operacoes de adicao e multiplicacao e as relacoes de ordem Definimos f N Z por fa a 0 para todo a N Temos entao 98 6 Os Numeros Inteiros Imf fa a N Z f e injetora ou seja se fa fb entao a 0 b 0 em Z o que implica que a b em N para todo a e b N f preserva as operacoes de adicao ou seja fab a b 0 a 0b 0 fa fb para todo a e b N f preserva as operacoes de multiplicacao ou seja fab ab 0 a 0b 0 fafb para todo a e b N f preserva as relacoes de ordem ou seja se a b em N entao existe u N tal que b a u Logo fb b 0 a u 0 a 0 u 0 fa u 0 com u 0 Z o que implica que fa fb em Z Assim no que se refere aos aspectos algebricos e quanto a ordenacao Z e uma copia de N dentro de Z E coerente portanto identificarmos N com Z atraves de f e considerarmos que N Z Mais especificamente identificaremos o numero natural 0 com o numero inteiro 0 0 o numero natural 1 com o numero inteiro 1 0 e mas geralmente o numero natural a com o numero inteiro a 0 Isso feito temos que N Z e para cada elemento 0 b Z temos 0 b b 0 que sera identificado com b ou seja Z b b N como era de se esperar Assumindo estas identificacoes temos Z 2 1 0 1 2 e cada numero inteiro x pode ser visto como uma diferenca de dois numeros naturais isto e x a b a 0 0 b a b com a e b N mesmo quando a b que era o que tınhamos em vista com a construcao do conjunto dos numeros inteiros 65 Valor Absoluto Como em Z temos a nocao de inteiros negativos podemos definir o valor absoluto de um numero inteiro 65 Valor Absoluto 99 Definição 611 Seja a Z O valor absoluto ou modulo de a e o numero inteiro a definido por a a se a 0 a se a 0 Temos as seguintes propriedades basicas Proposição 612 Sejam a e b Z Entao a a a b a a a c ab a b d a b a b Prova Se a 0 ou b 0 as afirmacoes sao imediatas Entao assumiremos que a 0 e b 0 Note que a 0 se e somente se a 0 para todo a Z com a 0 a Se a 0 entao a a a a Se a 0 entao a a a b Se a 0 entao a a e a a a a ou seja a a a Se a 0 entao a a e a a a ou seja a a a c Se a 0 e b 0 entao ab 0 e portanto ab ab ab Se a 0 e b 0 temos que a a b b ab ab Daı ab ab ab e portanto ab ab O caso em que a 0 e b 0 e analogo Se a 0 e b 0 entao a a b b e como ab 0 segue que ab ab Daı ab ab ab e entao ab ab d Temos do item b que a a a e b b b Somando membro a membro obtemos a b a b a b Se a b a b como a b a b segue que a b a b Se a b a b entao a b a b e como a b a b temos a b a b Portanto a b a b Exercício 613 Mostre que a b a b a b para todo a e b Z 100 6 Os Numeros Inteiros 66 Aritmética em Z 661 Múltiplos e Divisores Nesta secao apresentaremos as nocoes de multiplos e divisores e suas principais propriedades Definição 614 Sejam a e b Z Dizemos que a divide b se existir c Z tal que b ac Tambem denotamos tal numero inteiro c por b a Neste caso tambem dizemos que a e divisor de b ou que b e multiplo de a e denotamos este fato por a b Caso contrario dizemos que a nao divide b e escrevemos a b Exemplo 615 Por exemplo 1 a para todo a Z pois a 1 a Mas a 1 se e somente se a 1 pois 1 ab em Z se e somente se a b 1 Para o inteiro zero temos a 0 para todo a Z pois 0 a 0 Mas 0 a se e somente se a 0 pois 0 b 0 para todo b Z As principais propriedades da relacao de divisibilidade em Z sao Proposição 616 Sejam a b c e d Z a Reflexiva a a para todo a Z b Se a b e b 0 entao a b c Se a b e b a entao a b d Transitiva Se a b e b c entao a c e Se a b e a c entao a bx cy para todo x e y Z f a b se e somente se a b g Se a b c e d c entao d a se e somente se d b Prova Mostraremos as afirmacoes dos ıtens c e e ficando as outras como exercıcio Se a b e b a entao existem a e b Z tais que b aa e a bb Logo b bba o que implica que ab 1 em Z de onde segue que a b 1 ou seja a b mostrando assim a afirmacao do ıtem c 66 Aritmetica em Z 101 Para o ıtem e se a b e a c entao existem a e b Z tais que b aa e c ab Entao bx cy aax aby aax by com ax by Z ou seja a bx cy 662 Algoritmo da divisão ou algoritmo de Euclides Dados dois numeros inteiros a e b sabemos que se b a entao existe um numero inteiro c tal que a bc Quando b a sera que podemos pensar em algo parecido Nesta direcao temos o algoritmo da divisao ou algoritmo de Euclides que diz que para cada par de numeros inteiros a e b existem unicos numeros inteiros q e r tais que a bq r com 0 r b Note que este algoritmo nao tem sentido se b 0 pois a qb r daria a r o que contradiz 0 r 0 Mostraremos primeiramente a existˆencia dos inteiros q e r no caso em que a 0 e b 0 Lema 617 Sejam a e b Z tais que a 0 e b 0 Entao existem numeros inteiros q e r tais que a bq r com 0 r b Prova Consideremos o conjunto S a bx x Z e a bx 0 Se x 0 temos que a bx a 0 e um elemento de S ou seja S Pelo princıpio do menor numero natural temos que existe r minS Como r S podemos escrever r na forma r a bq 0 para algum q Z Resta agora mostrar que r b Suponhamos que r b Entao temos que a bq 1 a bq b r b 0 e portanto a bq 1 S Mas isto e uma contradicao pois a bq 1 r b r minS Logo r b como querıamos Mostremos agora o caso geral Teorema 618 Algoritmo da Divisão Sejam a e b Z com b 0 Entao existem unicos numeros inteiros q e r tais que a bq r com 0 r b Prova Mostremos primeiramente a existˆencia dos numeros inteiros q e r Comecamos considerando b 0 e a Z O caso a 0 segue do lema anterior Consideremos entao a 0 Do lema anterior temos que existem q e r Z tais que a bq r com 0 r b Como a a 102 6 Os Numeros Inteiros temos que a bq r Se r 0 basta tomar q q e r 0 Se r 0 temos que a bq r bq b b r bq 1 b r e neste caso basta tomar q q 1 e r b r Seja agora b 0 Para todo a Z do feito acima existem q e r Z tais que a bq r com 0 r b Ou seja a bq r bq r E agora basta tomar q q e r r Mostremos agora a unicidade dos numeros inteiros q e r Suponhamos que existem inteiros q r q e r satisfazendo as condicoes do teorema Entao a bq r bq r Isto implica que bq q r r Assim bq q r r e como b r e b r temos que r r b e consequentemente bq q b Mas b 0 logo segue que 0 q q 1 ou seja q q 0 o que implica que q q Substituindo na igualdade a bq r bq r segue que r r o que finaliza a demonstracao do teorema Na expressao a bq r com 0 r b o numero inteiro a e chamado de dividendo b de divisor q de quociente e r de resto Exemplo 619 Para a 79 e b 11 encontre numeros inteiros q e r tais que 79 11 q r com 0 r 11 Fazendo a divisao de 79 por 11 encontramos 79 1172 e multiplicando ambos os membros por 1 obtemos 79 11 7 2 Claramente o resto 2 nao satisfaz a exigˆencia 0 r 11 mas adicionando e subtraindo 11 obtemos 79 11 7 11 2 11 11 8 9 Como 0 9 11 temos que q 8 e r 9 satisfazem o requerido 663 Máximo Divisor Comum Nesta secao apresentamos a definicao de maximo divisor comum de dois numeros inteiros Mostramos que sempre existe o maximo divisor comum de quaisquer dois inteiros dados e mais ainda que ele e unico Definição 620 Sejam a e b Z Dizemos que o numero inteiro d e um maximo divisor comum de a e b se i d 0 66 Aritmetica em Z 103 ii d a e d b iii Se c Z e tal que c a e c b entao c d Comecamos mostrando a unicidade Proposição 621 Para numeros inteiros a e b se existir um maximo divisor comum de a e b entao ele e unico Prova Sejam d e d em Z dois maximos divisores comum de a e b Entao d e d satisfazem as condicoes i ii e iii da definicao 620 Usando que ii vale para d e que iii vale para d obtemos que d d Analogamente usando que ii vale para d e que iii vale para d obtemos que d d Assim d d e d d De 616 c temos que d d e usando i obtemos d d Desde que temos a unicidade quando existir o maximo divisor comum d de a e b escreveremos d mdca b ou seja no que segue sempre que escrevermos d mdca b estara subentendido que existe o maximo divisor comum de a e b e que ele e igual a d Para mostrarmos a existˆencia iniciaremos com alguns resultados auxiliares Proposição 622 Sejam a e b Z Entao mdca b mdca b mdca b mdca b Prova Segue diretamente da definicao e de 616 d Usando 622 e suficiente mostrarmos a existˆencia do maximo divisor comum de dois inteiros positivos Mais ainda da proxima proposicao podemos assumir que os dois numeros inteiros sao nao nulos Proposição 623 Se a 0 entao mdca b b para todo b Z Prova Segue diretamente da definicao e do fato que b 0 para todo b Z Proposição 624 Se a b entao mdca b a Prova De fato a satisfaz i a 0 104 6 Os Numeros Inteiros ii a a e a b iii Se c Z e tal que c a e c b entao c a ou seja a mdca b Proposição 625 Se a bq r em Z entao mdca b mdcb r Prova Por 622 podemos assumir que a 0 e b 0 Se d mdca b entao d a e d b De 616 e temos que d a bq r Portanto d b e d r Por outro lado se c b e c r entao novamente por 616 e obtemos c bqr a Portanto c a e c b o que implica que c d mdca b Logo d mdcb r como querıamos demonstrar Usando os resultados acima mostraremos agora que existe o maximo divisor comum de quaisquer dois inteiros Teorema 626 Dados a e b em Z temos que existe d Z satisfazendo a definicao 620 Prova Usando que mdca b mdcb a e os resultados acima podemos assumir que a b 0 Assim aplicando o algoritmo da divisao repetidas vezes obtemos a b q r1 com 0 r1 b b r1 q2 r2 com 0 r2 r1 r1 r2 q3 r3 com 0 r3 r2 Observe que o fato de b r1 r2 r3 0 implica que existe um menor ındice n tal que rn1 0 Assim para algum n temos rn2 rn1 qn rn com 0 rn rn1 rn1 rn qn1 Da proposicao 625 temos que mdca b mdcb r1 mdcr1 r2 mdcrn1 rn 66 Aritmetica em Z 105 Como rn rn1 segue de 624 que mdcrn1 rn rn e portanto mdca b existe e e igual a rn que e o ultimo resto diferente de zero Exemplo 627 Encontre mdc3248 226 Aplicando o algoritmo da divisao ate chegarmos em um resto igual a zero temos 3248 14 226 84 226 2 84 58 84 1 58 26 58 2 26 6 26 4 6 2 6 3 2 0 Logo mdc3248 226 2 Podemos representar estas divisoes repetidas atraves de uma tabela da seguinte forma 14 2 1 2 4 3 3248 226 84 58 26 6 2 84 58 26 6 2 0 Definição 628 Dizemos que dois numeros inteiros a e b sao primos entre si ou que a e primo com b se mdca b 1 O proximo resultado mostra que o maximo divisor comum de dois numeros inteiros e uma combinacao inteira destes numeros Proposição 629 Sejam a e b Z Se d mdca b entao existem x0 e y0 Z tais que d ax0 by0 Prova Se a b 0 entao d 0 e quaisquer x0 y0 Z satisfazem o requerido Se a 0 ou b 0 considere S ax by x y Z Como a a b b a2 b2 0 e a2 b2 S temos que em S existem elementos estritamente positivos Logo pelo princıpio do menor numero natural existe o menor deles Seja d este mınimo Agora e suficiente mostrar que d mdca b De fato i d 0 pela maneira como foi escolhido 106 6 Os Numeros Inteiros ii Como d S temos que existem x0 e y0 Z tais que d ax0by0 Do algoritmo da divisao temos que a dq r com 0 r d Substituindo d nesta igualdade obtemos a ax0 by0q r de onde segue que r a1 qx0 bqy0 Assim r S e como r 0 pela minimalidade de d temos que r 0 Portanto a dq o que mostra que d a De maneira analoga mostrase que d b iii Se c Z e tal que c a e c b entao de 616 e temos que c d ax0 by0 Em geral nao vale a volta de 629 somente quando d 1 ou seja quando os inteiros a e b sao primos entre si Corolário 630 Dois numeros inteiros a e b sao primos entre si se e somente se existem x0 e y0 Z tais que ax0 by0 1 Prova Segue de 629 para d 1 E imediato que 1 0 1 a e 1 b Se c Z e tal que c a e c b entao de 616 e temos que c ax0 by0 1 o que mostra que 1 mdca b Observação 631 Uma maneira de encontrar os inteiros x0 e y0 satisfazendo a igual dade de 629 e usando as divisoes sucessivas da demonstracao da proposicao 626 Ve jamos como fazer utilizando o exemplo 627 Vimos em 627 que 2 mdc3248 226 obtido atraves das divisoes sucessivas 3248 14 226 84 226 2 84 58 84 1 58 26 58 2 26 6 26 4 6 2 6 3 2 0 Isolando os restos em cada uma das igualdades acima e começando na penúltima igualdade e substituindo os respectivos restos em cada uma delas em ordem inversa obtemos 2 26 4 6 26 4 58 2 26 4 58 9 26 4 58 9 84 1 58 9 84 13 58 9 84 13 226 2 84 13 226 35 84 13 226 35 3248 14 226 35 3248 503 226 Assim x₀ 35 e y₀ 503 satisfaz 2 mdc3248 226 3248 x₀ 226 y₀ Observe também que esta não é a única solução somando e subtraindo números inteiros convenientes obtemos outras soluções Corolário 632 Seja a e b são números inteiros com a 0 ou b 0 e d mdca b então mdc a d b d 1 Prova Como a 0 ou b 0 temos que d mdca b 0 De 629 temos que existem x₀ e y₀ Z tais que d ax₀ by₀ Então temos que a d x₀ b d y₀ 1 e o resultado segue do corolário 630 108 6 Os Numeros Inteiros Corolário 634 Se a e b sao numeros inteiros divisores do inteiro c 0 e mdca b 1 entao ab c Prova De 629 temos que existem x0 e y0 Z tais que ax0 by0 1 Entao acx0 bcy0 c Como a c e b c temos que ab bc e ab ac Novamente de 616 e obtemos que ab c Observação 635 A nocao de maximo divisor comum pode ser estendida por recor rˆencia para mais de dois numeros inteiros ou seja para a1 a2 an Z temos mdca1 a2 an mdcmdca1 a2 an1 an Nestas condicoes temos que d Z e o maximo divisor comum dos numeros inteiros a1 a2 an se e somente se i d 0 ii d ai para todo i 1 n iii Se c Z e tal que c ai para todo i 1 n entao c d 664 Mínimo Múltiplo Comum Agora apresentamos a definicao de mınimo multiplo comum de dois numeros in teiros Definição 636 Sejam a e b Z Dizemos que o numero inteiro m e um mınimo multiplo comum de a e b se i m 0 ii m e multiplo de a e de b isto e a m e b m iii Se m Z for multiplo de a e de b entao m sera multiplo de m isto e m m A existˆencia e a unicidade do mınimo multiplo comum de dois inteiros segue dire tamente da proposicao abaixo pois o maximo divisor comum de dois numeros inteiros existe e e unico assim como o valor absoluto de um numero inteiro 66 Aritmetica em Z 109 Proposição 637 Sejam a e b Z Entao existe um numero inteiro m tal que mdca b m ab a b e tal inteiro e um mınimo multiplo comum da a e b Prova Note que se a 0 ou b 0 entao m 0 satisfaz a igualdade acima e tambem a definicao 636 Podemos entao supor que a e b sao nao nulos e neste caso d mdca b 0 Vamos entao mostrar que m ab d satisfaz a definicao 636 i E obvio que m 0 ii Escrevendo m a b d como d b temos que b d Z e consequentemente a a m Analogamente mostrase que b m ou seja m e multiplo de a e de b iii Seja m Z multiplo de a e de b Entao existem r e s Z tais que m ar e m bs Mais ainda como d a e d b temos que existem a e b Z tais que a ad e b bd e do corolario 632 temos que mdca b 1 Substituindo a e b na igualdade m ar bs e usando que d 0 obtemos ar bs Logo a Z e tal que a bs com mdca b 1 o que implica do corolario 633 que a s ou seja s as para algum sainZ Assim m bs bas abs ab d s para algum s Z de onde segue que m m Assim m ab d satisfaz a definicao 636 como querıamos mostrar Provado a existˆencia e a unicidade do mınimo multiplo comum de dois numeros inteiros a e b o denotaremos por mmca b Observe que como no caso do mdca b usando 637 podemos calcular o mmca b sem necessariamente fatorar os numeros inteiros a e b De maneira analoga ao feito para o maximo divisor comum podemos definir usando recorrˆencia o mınimo multiplo comum de mais de dois numeros inteiros 110 6 Os Numeros Inteiros 67 Números Primos O objetivo desta secao e demonstrar o Teorema Fundamental da Aritmetica para numeros inteiros Iniciamos com a nocao de numeros primos Definição 638 Dizemos que um numero inteiro p com p 0 e p 1 e primo se os unicos divisores de p sao 1 e p Se a Z com a 0 e a 1 nao e primo entao dizemos que a e composto Observação 639 Note que um numero inteiro composto a pode sempre ser fatorado num produto a bc onde b 1 e c 1 Mais ainda devido as propriedades de divisibilidade temos que um numero inteiro negativo p e primo se e somente se p e primo O primeiro resultado sobre numeros primos relaciona estes com divisibilidade e de fato fornece uma definicao equivalente de numero inteiro primo Proposição 640 Sejam a b e p Z Se p e primo e p a b entao p a ou p b Reciprocamente se p Z e tal que p 0 e p 1 e p a b implica que p a ou p b entao p e um numero primo Prova O caso a 0 ou b 0 e imediato pois p 0 Suponhamos entao que a 0 b 0 e que p a Neste caso como os unicos divisores positivos que p sao 1 e p e p a temos que mdca p 1 Agora segue de 633 que p b Para a recıproca suponhamos que p seja um inteiro composto Entao existem a e b Z ambos diferentes de 1 tais que p ab Assim p a b com 1 a b p o que implica que p a e p b Consequentemente p a p b e p ab p o que contradiz a hipotese O proximo resultado mostra que o menor divisor positivo diferente de 1 de um numero inteiro dado e um numero primo Proposição 641 Seja a Z com a 0 e a 1 Entao o mınimo do conjunto S x Z x 1 e x a e um numero primo Prova Observe que S pois a S Entao pelo princıpio do menor numero 67 Numeros Primos 111 natural temos que existe p minS Se p e composto como p 0 temos que existem b e c Z positivos com b 1 c 1 tais que p b c Assim 0 b p e um inteiro tal que b p e como p a entao b a o que implica que b S o que contradiz a minimalidade de p Logo p minS e primo Para a demonstracao do Teorema Fundamental da Aritmetica usaremos o Segundo Princıpio de Inducao que apresentaremos sem demonstracao Proposição 642 Segundo Princípio de Indução Sejam a Z e Pn uma afirmacao associada a todo numero inteiro n a Se i Pa e verdadeira ii Para todo inteiro r a se Pk e verdadeira para todo k Z com a k r entao Pr tambem e verdadeira Entao Pn e verdadeira para todo n Z com n a Teorema 643 Teorema Fundamental da Aritmética Seja a Z com a 0 e a 1 Entao existem numeros primos positivos p1 p2 pr Z com r 1 tais que a p1 p2 pr ou a p1 p2 pr se a 0 ou a 0 respectivamente Mais ainda essa decomposicao e unica a menos das ordens dos fatores Prova Trocando a por a se necessario basta mostrarmos o resultado para a Z com a 1 Mostraremos a existˆencia da decomposicao usando o Segundo Princıpio de Inducao Se a 2 o resultado segue trivialmente pois 2 e primo Seja a 2 e suponhamos que exista a decomposicao para todo numero inteiro b tal que 2 b a Mostremos que o resultado vale para a Da proposicao 641 temos que existe um numero primo positivo p1 tal que a p1 a1 para algum a1 Z Se a1 1 ou a1 e primo temos que o resultado segue Caso contrario como 2 a1 a por hipotese de inducao temos que existem numeros primos positivos p2 p3 pr tais que a1 p2p3 pr e consequentemente a p1p2 pr Assim de 642 temos a existˆencia da decomposicao para todo numero inteiro a 1 112 6 Os Numeros Inteiros Para mostrarmos a unicidade da decomposicao suponhamos que existam numeros naturais 1 r s e numeros primos positivos p1 p2 pr e q1 q2 qs tais que a p1 p2 pr q1 q2 qs Entao p1 q1 q2 qs e da proposicao 640 temos que p1 qj para algum j 1 s Do fato que p1 e qj sao numeros primos positivos obtemos que p1 qj Como queremos demonstrar a unicidade a menos da ordem dos fatores sem perda de generalidade podemos assumir que j 1 ou seja que qj q1 Cancelando p1 em ambas as fatoracoes de a obtemos p2 pr q2 qs Repetindo este procedimento r vezes obtemos 1 qr1 qs e como cada qj e um numero primo isso so e possıvel se r s o que demonstra a unicidade Observação 644 Na decomposicao a p1 p2 pr os numeros primos envolvidos nao sao necessariamente distintos Usando somente numeros primos distintos podemos escrever a pα1 1 pα2 2 pαk k para algum 1 k r com αi N para todo i 1 k e numeros primos positivos p1 p2 pk que e chamada a decomposicao canˆonica de a 68 Congruências e Aplicações Vocˆe saberia responder as seguintes perguntas O 264o e o 118o dias do ano ocorrem num mesmo dia da semana Quais sao os inteiros que deixam resto 3 quando divididos por 4 Qual e o resto da divisao de 712 por 4 Qual e o criterio de divisibilidade por 7 Em que dia da semana vocˆe nasceu A partir da nocao de congruˆencia ou aritmetica modular vamos dar respostas a todas essas perguntas e mais algumas Esta nocao surgiu pela primeira vez no livro 68 Congruˆencias e Aplicacoes 113 Disquisitiones arithmeticae escrito por Carl Friedrich Gauss publicado em 1800 Ate hoje e usada a mesma notacao introduzida por Gauss O que vem a ser congruˆencia E uma linguagem na qual muitas abordagens acerca de divisibilidade de numeros inteiros podem ser simplificadas Vejamos esta nocao formalmente Definição 645 Seja m Z com m 0 fixo Para a e b Z dizemos que a e cˆongruo a b modulo m se m a b ou equivalentemente se a b for multiplo de m Notacao a b mod m Exemplo 646 5 2 mod 3 pois 3 5 2 2 1 mod 3 pois 3 2 1 5 17 mod 3 pois 3 5 17 As propriedades abaixo da relacao de congruˆencia modulo m nos mostram que esta e de fato uma relacao de equivalˆencia sobre Z para todo inteiro m 0 i Reflexiva a a mod m para todo a Z pois m 0 a a ii Simetrica Se a b mod m entao b a mod m pois para todo a b e m Z temos m a b se e somente se m b a iii Transitiva Se a b mod m e b c mod m entao a c mod m De fato de a b mod m e b c mod m temos que m a b e m b c Logo m a b b c a c ou seja a c mod m O proximo resultado relaciona congruˆencia modulo m com o algoritmo da divisao Proposição 647 Sejam a e b Z Entao a b mod m se e somente se a e b fornecem os mesmos restos na divisao euclideana por m Prova Desde que a b mod m temos que a a b ou seja existe k Z tal que a b k m e portanto a k m b Na divisao euclideana de a e b por m temos que b q m r e a p m s para algum q p r e s Z com 0 r s m Assim a k q m r p m s e pela unicidade do quociente e do resto temos que k q p e s r Portanto os restos sao iguais Suponhamos que os restos sejam iguais isto e a p m r e b q m r Entao a b p q m ou seja m a b e consequentemente a b mod m 114 6 Os Numeros Inteiros Ja estamos em condicoes de responder as duas primeiras perguntas O 264o e o 118o dias do ano ocorrem num mesmo dia da semana Desde que a semana tem 7 dias temos que eles ocorrem no mesmo dia da semana se e somente se 264 118 mod 7 De 647 isso ocorre se e somente se eles tem o mesmo resto na divisao euclideana por 7 Como 264 37 7 5 e 118 16 7 6 temos que eles nao correm no mesmo dia da semana e sim em dias seguidos Quais sao os inteiros que deixam resto 3 quando divididos por 4 Sao os numeros inteiros a tais que a 3 mod 4 ou seja 4 a 3 Entao existe k Z tal que a 3 4 k isto e a 4 k 3 com k Z Dado um numero inteiro m 0 desde que e uma relacao de equivalˆencia sobre Z podemos considerar o conjunto quociente de Z por esta relacao que denotaremos por Zm ou seja Zm a a Z onde a e a classe de equivalˆencia representada por a De 647 temos que se a q m r com 0 r m entao a r mod m e consequentemente a r Assim Zm 0 1 m 1 onde 0 a Z a 0 mod m a Z m a m k k Z m Z 1 a Z a 1 mod m a Z m a 1 m k 1 k Z m Z 1 2 a Z a 2 mod m a Z m a 2 m Z 2 m 1 a Z a m 1 mod m a Z m a m 1 m Z m 1 No proximo resultado apresentamos mais algumas propriedades da relacao de con gruˆencia Proposição 648 Sejam m 0 um inteiro fixo e a b c e d Z Entao valem as seguintes propriedades a Se a b mod m entao a c b c mod m e ac bc mod m 68 Congruˆencias e Aplicacoes 115 b Se a b mod m e c d mod m entao a c b d mod m e ac bd mod m c Se a b mod m e r 1 um inteiro entao ra rb mod m e ar br mod m Prova a Se a b mod m entao m a b Mas a b a c b c o que implica que a c b c mod m Como m a b temos que existe k Z tal que a b m k o que implica que ac bc a bc m kc m kc ou sejam m ac bc e consequentemente ac bc mod m b Se a b mod m e c d mod m entao do ıtem a temos que a c b c mod m e bc bd mod m Da transitividade obtemos ac bd mod m De maneira analoga usando o ıtem a e a transitividade da relacao obtemos ac bd mod m c Se a b mod m e r 1 um inteiro entao aplicando o resultado do ıtem b para a c e b d r vezes obtemos ra rb mod m e ar br mod m Estamos aptos a responder mais uma das perguntas do inıcio da secao Qual e o resto da divisao de 712 por 4 Podemos calcular diretamente 712 13841287201 depois dividir por 4 e veri ficar que o resto e 1 Usando a congruˆencias podemos resolver de uma maneira mais simples Desde que 7 3 mod 4 e 3 1 mod 4 por transitividade temos 7 1 mod 4 e de 648 c obtemos 712 112 mod 4 ou seja 712 1 mod 4 De 647 temos que o resto da divisao de 712 por 4 e 1 No restante do capıtulo apresentaremos algumas aplicacoes da relacao de congruˆen cia e responderemos as perguntas que faltam 681 Critérios de Divisibilidade Nesta secao deduziremos eou demonstraremos a validade dos criterios de divisibil idade conhecidos desde o ensino basico Dado um numero inteiro positivo n podemos escrevˆelo na forma n a0 a1 10 a2 102 ar 10r 116 6 Os Numeros Inteiros onde r 0 e 0 ai 9 para cada i 0 1 r sao os seus algarismos No que segue usaremos esta notacao e os resultados contidos em 647 e 648 sem mencionalos a Divisibilidade por 2 O numero n e divisıvel por 2 se e somente se a0 e divisıvel por 2 De fato n e divisıvel por 2 se e somente se n 0 mod 2 Como 10 0 mod 2 temos que 10i 0 mod 2 para todo i 1 r Assim obtemos n a0 a1 10 a2 102 ar 10r a0 a1 0 ar 0 mod 2 o que mostra que 2 n se e somente se 2 a0 b Divisibilidade por 3 O numero n e divisıvel por 3 se e somente se a0a1 ar e divisıvel por 3 De fato n e divisıvel por 3 se e somente se n 0 mod 3 Como 10 1 mod 3 temos que 10i 1 mod 3 para todo i 1 r Assim n a0 a1 10 a2 102 ar 10r a0 a1 1 ar 1 mod 3 o que mostra que 3 n se e somente se 3 a0 a1 ar c Divisibilidade por 4 O numero n e divisıvel por 4 se e somente se o numero formado por seus dois ultimos algarismos e divisıvel por 4 isto e a0 a1 10 e divisıvel por 4 De fato n e divisıvel por 4 se e somente se n 0 mod 4 Como 100 0 mod 4 temos que 10i 1 mod 4 para todo i 2 r Assim n a0 a1 10 a2 102 ar 10r a0 a1 10 mod 4 o que mostra que 4 n se e somente se 4 a0 a1 10 d Divisibilidade por 5 O numero n e divisıvel por 5 se e somente se e terminado em 0 ou 5 isto e a0 e divisıvel por 5 68 Congruˆencias e Aplicacoes 117 De fato n e divisıvel por 5 se e somente se n 0 mod 5 Como 10 0 mod 5 temos que 10i 0 mod 5 para todo i 1 r Assim n a0 a1 10 a2 102 ar 10r a0 mod 5 o que mostra que 5 n se e somente se 5 a0 e Divisibilidade por 9 O numero n e divisıvel por 9 se e somente se a0a1 ar e divisıvel por 9 De fato n e divisıvel por 9 se e somente se n 0 mod 9 Como 10 1 mod 9 temos que 10i 1 mod 9 para todo i 1 r Assim n a0 a1 10 a2 102 ar 10r a0 a1 1 ar 1 mod 9 o que mostra que 9 n se e somente se 9 a0 a1 ar f Divisibilidade por 11 O numero n e divisıvel por 11 se e somente se a0 a1 a2 a3 1rar e divisıvel por 11 Como n e divisıvel por 11 se e somente se n 0 mod 11 e 10 1 mod 11 temos que 10i 1i mod 11 para todo i 1 r Assim n a0 a1 10 ar 10r a0 a1 1 ar 1r mod 11 o que mostra o criterio g Divisibilidade por 7 Quais as condicoes sobre os algarismos de n para que n seja divisıvel por 7 Vejamos n e divisıvel por 7 se e somente se n 0 mod 7 Como 100 1 mod 7 101 3 mod 7 102 32 mod 7 102 2 mod 7 103 2 3 mod 7 103 1 mod 7 104 22 mod 7 103 3 mod 7 105 1 2 mod 7 105 2 mod 7 106 12 mod 7 103 1 mod 7 118 6 Os Numeros Inteiros temos que n a0 a1 3 a2 2 a3 a4 3 a5 2 a6 a7 3 a8 2 mod 7 o que mostra que 7 n 7 a0 a1 3 a2 2 a3 a4 3 a5 2 a6 a7 3 a8 2 682 A validade de um número de CPF O CPF Cadastro de Pessoa Fısica emitido pela Receita Federal e caracterizado por uma funcao bijetora entre o conjunto das pessoas fısicas cadastradas e o conjunto dos numeros emitidos O numero de um CPF tem exatamente 9 algarismos em sua raiz e mais dois al garismos dıgitos verificadores que sao indicados por ultimo ou seja um CPF tem 11 algarismos e e escrito na forma abcdefghi jk ou diretamente como abcdefghijk onde os algarismos nao podem ser todos iguais entre si O algarismo j e chamado o primeiro digito verificador do numero do CPF e k e chamado o segundo digito verificador do numero do CPF Regra para determinar o primeiro dıgito verificador Comecamos calculando S1 10a 9b 8c 7d 6e 5f 4g 3h 2i Encontramos r onde S1 r mod 11 Se r 0 ou r 1 o dıgito j e 0 zero Se r 0 e r 1 o dıgito j e 11 r Regra para determinar o segundo dıgito verificador Para obtermos k comecamos calculando S2 11a 10b 9c 8d 7e 6f 5g 4h 3i 2j Encontramos r onde S2 r mod 11 Se r 0 ou r 1 o dıgito k e 0 zero Se r 0 e r 1 o dıgito j e 11 r Exercício 649 Verifique se o numero de seu CPF e valido 68 Congruˆencias e Aplicacoes 119 683 Em que dia da semana você nasceu Para responder essa pergunta comecamos associando um numero a cada dia da semana da seguinte forma Numero Dia da semana 0 sabado 1 domingo 2 segundafeira 3 tercafeira 4 quartafeira 5 quintafeira 6 sextafeira A cada mˆes associamos uma constante M chamada a constante do mˆes entre 0 e 6 correspondente ao dia da semana do ultimo dia do mˆes anterior Por exemplo no mˆes de setembro de 2010 o dia primeiro foi quartafeira o dia anterior foi tercafeira e portanto M 3 Para tal constante temos a seguinte propriedade de demonstracao imediata Lema 650 M dia dia da semana mod 7 Por exemplo para o dia 14 de setembro de 2010 temos 3 14 17 3 mod 7 Portanto dia 14 de setembro de 2010 foi uma tercafeira Com a formula de 650 o problema de descobrir o dia da semana de alguma data se reduz a descobrir a constante M do mˆes correspondente Como calcular a constante do mˆes seguinte Note que por definicao a constante do mˆes seguinte outubro2010 e o dia da semana do ultimo dia de setembro2010 Como setembro tem 30 dias e 330 33 5 mod 7 temos 650 que dia 30092010 foi em uma quintafeira Portanto a constante do mˆes de outubro de 2010 e M 5 Como calcular as constantes dos meses futuros a setembro2010 Note que 30 2 mod 7 e 31 3 mod 7 Com isso obtemos 120 6 Os Numeros Inteiros N Numero de dias no mˆes 30 31 30 31 N 3 ou 2 mod 7 2 3 2 3 Mˆes S O N D M 5 0 3 5 Observe que para obtermos a constante do mˆes seguinte somamos a constante ao numero acima e tomamos a congruˆencia modulo 7 Como calcular as constantes dos meses anteriores a setembro2010 Como o mˆes de fevereiro e anterior a setembro e preciso saber se o ano em questao e ou nao um ano bissexto Sao considerados anos bissextos aqueles que sao multiplos de 4 e que nao sejam multiplos de 100 com excecao dos multiplos de 400 Em termos de congruˆencias se A e o ano em questao entao A e bissexto se e somente se A 0 mod 4 e A 0 mod 100 ou A 0 mod 400 Como 2010 2 mod 4 temos que 2010 nao e bissexto Note que 28 0 mod 7 e 29 1 mod 7 Usando este fato e o fato que 2010 nao e bissexto obtemos N 31 2829 31 30 31 30 31 31 30 3 2 ou 01 3 01 3 2 3 2 3 3 2 Mˆes J F M A M J J A S M 0 3 3 6 1 4 6 2 5 Observe que para obter as constantes dos meses anteriores subtraise a constante o numero acima do mˆes anterior e tomase a congruˆencia modulo 7 para obter a constante do mˆes anterior Em uma so tabela as constantes referentes ao ano de 2010 3 2 ou 01 3 01 3 2 3 2 3 3 2 3 2 3 Mˆes J F M A M J J A S O N D M 0 3 3 6 1 4 6 2 5 0 3 5 Juntando as constantes para 2009 e 2011 obtemos 69 Exercıcios 121 3 2 ou 01 3 01 3 2 3 2 3 3 2 3 2 3 Mˆes J F M A M J J A S O N D 2009 4 0 0 3 5 1 3 6 2 4 0 2 2010 0 3 3 6 1 4 6 2 5 0 3 5 2011 1 1 4 6 2 4 0 3 6 1 4 6 Como saber o dia da semana em uma data qualquer passada ou futura Como 365 1 mod 7 e 366 2 mod 7 temos que irmos para um ano A futuro resp passado precisamos somar resp subtrair o numero de anos da diferenca 2010 A adicionado do numero de 29s de fevereiro entre estas datas Exemplo 651 Eu Ires nasci no dia 19 de junho de 1959 Em que dia da semana eu nasci Queremos saber a constante M do mˆes de junho de 1959 Portanto A 1959 Assim 2010 A o numero de 29 de fevereiro entre as datas e 51 13 64 e 64 1 mod 7 Como a constante do mˆes junho de 2010 e M 4 temos que a constante do mˆes junho de 1959 e 4 1 3 mod 7 ou seja M 3 Assim de 650 obtemos M 19 3 19 22 1 mod 7 ou seja eu nasci em uma segundafeira Exercício 652 Em que dia da semana vocˆe nasceu 69 Exercícios 1 a Prove que a soma de dois numeros inteiros pares e par e que a soma de dois numeros inteiros ımpares tambem e par b O produto de dois numeros inteiros e ımpar se e somente se ambos sao ımpares 2 Se a e b sao numeros inteiros com a 0 e b 0 mostre que an bn a ban1 an2 b a bn2 bn1 n 1 3 Sejam x e y numeros inteiros tais que xy 1 Mostre que x y 1 ou x y 1 4 Para a b e c Z mostre que a b c se e somente se a b c 5 Para a b e c Z com a b e c d mostre que a a d b c b bc ad ac bd 6 Mostre que para todo n Z o conjunto x Z n x n 1 é vazio 7 Considerando a relação definida em Z mostre que ela é transitiva e a compatibilidade com a adição 8 Sejam a b Z e d mdca b Mostre que a mdcsa sb sd b mdc a d b d 1 9 Se n 0 não é múltiplo de 3 mostre que a 3²ⁿ 3ⁿ 1 é divisível por 13 10 Encontre o quociente e o resto na divisão euclidiana de a por b nos seguintes casos a 390 b 74 a 124 b 18 a 420 b 58 11 Na divisão euclidiana de 326 pelo inteiro b 0 o quociente é 14 e o resto é r Ache os possíveis valores de b e r 12 Seja m um inteiro ímpar Mostre que o resto da divisão de m por 4 é 1 ou 3 13 Seja a um inteiro Mostre que a Um dos inteiros a a 1 ou a 2 é divisível por 3 b Um dos inteiros a a 2 ou a 4 é divisível por 3 c Um dos inteiros a a 1 a 2 ou a 3 é divisível por 4 14 Seja m um inteiro a Mostre que o resto da divisão de m² por 3 é 0 ou 1 b Se n é impar mostre que o resto da divisão de m² por 4 é 1 69 Exercıcios 123 16 Sejam a e b Z Mostre que mdca b 1 se e somente se mdca b b 1 17 Encontre os restos nas seguintes divisoes a 245 por 7 b 1110 por 100 c 52 4841 285 por 3 18 Qual e o resto na divisao euclidiana de s 15 25 35 995 1005 por 4 Justifique 19 a Se a e um cubo perfeito a t3 para algum t Z entao mostre que a 0 1 ou 1 mod 9 b Se a e um quadrado perfeito a t2 para algum t Z e tambem um cubo perfeito a s3 para algum s Z mostre que a 0 1 9 ou 28 mod 36 20 a Mostre que todo numero inteiro primo e da forma 4k 1 ou 4k 3 com k Z b Mostre que todo numero primo e da forma 6k 1 ou 6k 5 com k Z 21 Sejam a e b numeros inteiros e p um numero primo Verificar se as afirmacoes abaixo sao verdadeiras ou falsas a Se p divide a2 b2 e p divide a entao p divide b b Se p divide ab entao p divide a e p divide b c Se p divide a b entao p divide a e p divide b d Se a divide p entao a e primo e Se a divide b e p divide b entao p divide a 71 A adição em Q 7 Números Racionais No conjunto dos numeros inteiros temos que a equacao a X b com a e b Z tem solucao se e somente se a b Podemos sempre assumir que a 0 pois caso contrario b tambem seria igual a zero e a equacao seria 0 0 Mais ainda usando a lei do cancelamento para o produto temos que quando esta equacao tem solucao ela e unica Queremos ampliar o conjunto dos numeros inteiros construindo um conjunto onde esta equacao sempre tenha solucao unica mesmo quando a b Note que a solucao sera X b a com a 0 e b Z Assim queremos construir um conjunto contendo Z onde faca sentido este quociente e que contenha todos os quocientes deste tipo Observe por exemplo que expressoes do tipo 4 2 6 3 10 5 90 45 representam to das o numero inteiro 2 Mas seria muito bom se tivessemos uma certa unicidade de representacao Note que a igualdade 4 2 10 5 em Z e equivalente a 4 5 2 10 Isso nos ajuda a entender a construcao que faremos a seguir Seja Z n Z n 0 Em Z Z definimos a relacao por m n p q m q n p para todo m n e p q Z Z A relacao acima e uma relacao de equivalˆencia sobre Z Z Verifique este fato como exercıcio Portanto determina em Z Z uma particao em classes de equivalˆencia Para cada par m n Z Z a classe de equivalˆencia representada por esse elemento sera 125 71 A adição em Q 71 A adicao em Q 127 Para tanto se x m n m n e y r s r s entao temos que mn nm e rs sr Multiplicando por ss e por nn e somando membro a membro obtemos msns rnmr nsms nsrn ou seja ms rn ns ns ms rn e portanto ms rn ns ms rn ns o que mostra que a adicao esta bem definida No proximo resultado apresentamos as principais propriedades desta operacao Teorema 72 Para x y e z Q valem as seguintes propriedades a Associativa x y z x y z b Comutativa x y y x c Elemento Neutro Existe 0 0 1 0 2 em Q tal que 0 x x para todo x Q d Elemento Oposto Para cada x Q existe y Q tal que x y 0 e Lei do Cancelamento Se x y x z entao y z Prova Exercıcio Observação 73 Usando a Lei do Cancelamento podese mostrar que o elemento neutro e unico e que para cada x Q o elemento y satisfazendo a propriedade d tambem e unico o qual sera denotado por x e dito ser o oposto ou simetrico aditivo de x Para x e y Q diremos ser a diferenca entre x e y e indicaremos por x y ao numero racional x y x y Tal como em Z com demonstracoes analogas temos algumas propriedades envol vendo adicao e opostos 128 7 Numeros Racionais Proposição 74 Sejam x y e z Q Valem as seguintes propriedades a x y x y b x y y x c x a y a y x Prova Exercıcio 72 A Multiplicação em Q Definição 75 Sejam x m n e y r s elementos de Q O elemento de Q dado por x y xy mr ns e dito ser o produto de x por y Mostre que essa definicao nao depende das particulares representacoes escolhidas para x e y ou seja que a operacao de multiplicacao em Q esta bem definida Para tal operacao temos as seguintes propriedades elementares Teorema 76 Sejam x y e z Q Valem as seguintes propriedades a Associativa x yz xy z b Comutativa xy yx c Elemento Neutro Existe 1 1 1 2 2 3 3 em Q tal que 1 x x para todo x Q d Elemento Inverso Para cada x Q com x 0 existe y Q tal que xy 1 e Distributividade xy z xy xz f Lei do Cancelamento Se xy xz e x 0 entao y z Prova Vamos mostrar os ıtens c d e f ficando a demonstracao dos outros como exercıcio c Para x m n Q temos que x 1 m n 1 1 m 1 n 1 m n x d Se x m n 0 em Q entao m 0 e consequentemente y n m Q Mais ainda x y m n n m mn mn 1 1 1 como querıamos mostrar 73 Relacao de Ordem em Q 129 f Se xy xz e x 0 entao de b temos que yx zx Mais ainda como x 0 entao do ıtem anterior existe x Q tal que xx 1 Assim multiplicando a equacao yx zx por x e usando a associatividade obtemos yxx zxx ou seja y1 z1 o que implica que y z Observação 77 Como na adicao usando a Lei do Cancelamento para a multipli cacao podese mostrar que o elemento neutro e unico e o elemento y satisfazendo a propriedade do ıtem d tambem e unico Tal elemento sera dito ser o inverso ou simetrico multiplicativo de x e denotado por x1 Com relacao a inversos temos Exercício 78 Para x e y Q mostre que a Se x 0 entao x11 x b x y1 x1 y1 Mais ainda ainda usando a nocao de inverso podemos definir a operacao de divisao sobre Q como segue Definição 79 Sejam x Q e y Q x Q x 0 A operacao de Q Q em Q que a cada par x y associa o numero racional x y1 e chamada de divisao em Q O elemento x y1 e dito ser o quociente de x por y e tambem podera ser indicado por x y Exercício 710 Mostre que x y z x z y z para todo x y Q e z Q 73 Relação de Ordem em Q Observe que dado x Q sempre poderemos considerar uma representacao para x em que o denominador seja um numero inteiro maior que zero Isso segue do simples fato que x m n m n Definição 711 Sejam x e y numeros racionais com representacoes em que os respec tivos numeradores sejam estritamente positivosisto e x m n e y r s com n 0 e s 0 em Z Dizemos que x e menor ou igual a y e escrevemos x y se ms nr em Z Neste caso dizemos tambem que y e maior ou igual a x e escrevemos y x 130 7 Numeros Racionais Se ms nr em Z dizemos que x e menor que y x y ou que y e maior que x y x Exemplo 712 Note que 8 7 3 4 pois 8 4 3 7 e 5 6 4 5 pois 5 5 6 4 Dizemos que um elemento x m n Q com n 0 e positivo se x 0 e isto ocorre se e somente se m 0 Quando x 0 ou seja m 0 dizemos que x e estritamente positivo Se x 0 isto e n 0 e m 0 dizemos que x e negativo Quando m 0 dizemos que x e estritamente negativo A relacao definida acima e analoga a relacao de ordem definida sobre Z ou seja vale o seguinte resultado Proposição 713 Sejam x e y em Q tais que x y Entao existe z Q positivo tal que y x z Prova Dados x e y em Q podemos escrever x m n e y r n com n 0 Se x y em Q entao mn rn em Z e como n 0 obtemos m r Pela definicao da relacao de ordem sobre Z temos que existe u Z tal que r m u Assim y r n m u n m n u n x z onde z u n Q e positivo pois u 0 e n 0 o que mostra o resultado No proximo resultado mostraremos que como definida acima e uma relacao de ordem total sobre Q Teorema 714 A relacao e uma relacao de ordem total sobre Q Prova Assumiremos que todos os denominadores dos elementos considerados em Q sejam estritamente positivos Sejam x m n y r s e z p q elementos de Q i e reflexiva De fato para todo x Q temos que x x m n m n mn nm pois o produto de numeros inteiros e comutativo 74 A imersão de Z em Q f é injetora ou seja se fm fn então m n 1 n 1 em Q o que implica que m 1 n 1 em Z ou seja m n para todo m e n Z f preserva as operações de adição ou seja fm n m n 1 m 1 n 1 fm fn para todo m e n Z f preserva as operações de multiplicação ou seja fm n m n 1 m 1 n 1 fm fn para todo m e n Z f preserva as relações de ordem ou seja se m n em Z então existe u Z tal que n m u Logo fn n 1 m u 1 m 1 u 1 fm u 1 com u 1 0 em Q o que implica que fm fn em Q Assim não se refere aos aspectos algébricos e quanto à ordenação Imf m 1 Z é uma cópia de Z dentro de Q É coerente portanto identificarmos Z com Imf através de f e considerarmos que Z Q Mais ainda como N pode ser visto como um subconjunto de Z temos N Z Q Como era de se esperar cada número inteiro m será identificado como m 1 em Q e omitiremos o denominador 1 ao escrevêlo Assumindo estas identificações se m e n Z com n 0 então m n m 1 n 1 m 1 1 n m n Q Vamos agora responder a questão formulada no início do capítulo Dados números inteiros a e b com a 0 a equação a X b admite uma única solução em Q à saber X a1 b ba mesmo quando a b 75 Exercıcios 133 2 Em relacao as operacoes de adicao e subtracao definidas em Q prove que para quaisquer que sejam a b c Q valem as seguintes propriedades a Associativa abc abc b Comutativa a b b a c a b a b d a b b a e a x b x b a f a b a c b c 3 Para quaisquer a b c Q prove que valem a a11 a bab1 a1b1 c ab c ab ac d a b c a c b c e ab ab ab f ab ab 4 a Seja x um elemento de Q tal que x α α para todo α Q Mostre que x 0 b Demonstrar que o oposto de um racional e unico 5 Mostre que toda equacao da forma a x b onde a b sao numeros racionais b 0 tem solucao em Q Mostre tambem que essa solucao e unica 6 Mostre que para toda terna x y z de racionais temse que a Se x y entao x z y z b Se x y e 0 z entao xz yz 7 Se x e y sao racionais tais que x y entao sempre existe um racional z tal que x z y 8 Sejam x e y racionais positivos Prove que existe um natural n tal que nx y Propriedade Arquimediana em Q Referências Bibliográficas 1 Bloch E D Proofs and Fundamentals a First Course in Abstract Mathematics Boston Birkhauser 2000 2 Castrucci B Elementos de Teoria dos Conjuntos Serie Professor n3 Sao Paulo 1976 3 Domingues H H Fundamentos de Aritmetica Editora Atual Sao Paulo 1991 4 Lipschutz S Teoria dos Conjuntos McGrawHill do Brasil 1978 5 Lipschutz S Topologia Geral McGrawHill do Brasil 1973 6 Monteiro L H J Algebra Moderna LpM Sao Paulo 1966 7 Morash R P Bridge to Abstract Mathematics The Handom HouseBirkhauser Mathematics Series 1987 135