Sumário de Teoria dos Conjuntos e Lógica

Sumário 1 A linguagem matemática 2 11 Noções de lógica e teoria dos conjuntos 2 111 Sentenças conectivos e operadores lógicos 3 112 A implicação lógica 9 Exercícios 14 12 A teoria dos conjuntos de ZermeloFraenkel 18 121 Abordagem intuitiva da teoria dos conjuntos 18 122 Abordagem axiomática mas ainda intuitiva da teoria dos conjuntos 21 123 Par ordenado e Produto cartesiano 23 124 Relações e Funções 24 Exercícios 25 Complemento Conjuntos numéricos 27 2 Demonstrações 30 21 Demonstrações 30 211 Considerações iniciais 30 212 Demonstração direta de implicação 32 213 Demonstração de equivalências 34 214 Demonstração indireta de implicação 35 215 Demonstração por vacuidade e prova trivial 38 216 Demonstração por casos 38 217 Demonstrações existenciais 39 218 Mais exemplos uso do PBO 40 219 Considerações finais 42 Exercícios 43 Complemento O método probabilístico 46 3 Princípios de Indução Finita e demonstrações por indução 48 31 Princípios de indução 48 311 Indução em subconjuntos dos inteiros limitados inferiormente 49 312 Mais duas variantes 50 313 Equivalência entre os princípios 50 32 Demonstrações por indução 50 321 A base é importante 52 322 O passo é importante 52 323 Outro exemplo de prova errada 53 324 Desigualdade das médias aritmética e geométrica 53 33 Definições recursivas 54 Exercícios 57 Complemento Indução nos reais 59 4 Relações 61 41 Relação de equivalência 62 Exercícios 64 Complemento Construção dos Inteiros 65 42 Relação de ordem 65 i 421 Boa ordem e Indução 68 422 opcional O teorema de Dilworth 70 Exercícios 70 Complemento Números naturais e ordinais 73 43 Relações bem fundadas 74 431 Indução bem fundada 75 Exercícios 79 Complemento Lema de Zorn e teorema da boa ordem 80 5 Contagem 82 51 Princípios de contagem 82 511 Bijeções 82 512 Conjuntos finitos 85 513 Conjuntos enumeráveis 87 514 Conjuntos infinitos 87 515 Princípio das gavetas 88 516 Demonstração do Teorema de CantorSchröderBernstein 90 Exercícios 91 Complemento O problema de HadwigerNelson 1950 93 52 Combinatória 94 521 Arranjo 95 522 Combinação 96 523 Relações de equivalência e contagem 102 Exercícios 106 Complemento Aproximação de Stirling 110 53 Funções geradoras 111 531 Série formal de potências 112 532 Expansão de funções de geradoras 116 Exercícios 118 Complemento Série analítica de potências 120 Complemento Teorema binomial estendido 122 1 Capítulo 1 A linguagem matemática 11 Noções de lógica e teoria dos conjuntos Uma parte do trabalho dos matemáticos de um modo geral é descobrir e comunicar verdades matemáticas e uma demons tração é um argumento cujo objetivo é convencer outras pessoas de que algo é verdade As demonstrações que aparecem nos textos desde livros didáticos até artigos publicados em periódicos de matemática diferem enormemente quanto ao estilo po rém encerram construções que estão em ou formam em certo sentido um senso comum quanto aos seus significados O estilo é em grande parte influenciado pelo público a que se destina o texto e considera entre outras coisas o conhecimento esperado da audiência a que se destina A linguagem usada nas demostrações é uma linguagem natural como o português o inglês e o francês porém tais linguagens podem levar a ambiguidades e paradoxos Um desses paradoxos é o famoso paradoxo de Russell de 1901 que levou a uma contradição no sistema que formalizava a teoria dos conjuntos na época Seja U o conjunto formado pelos conjuntos que não pertencem a eles mesmos O conjunto U pertence a ele mesmo No início do século 20 esse e outros problemas culminaram no que ficou conhecido como a crise dos fundamentos da mate mática Para tentar evitar ambiguidades na matemática usamos palavras como ou seentão e outras com um significado muito específico e que nem sempre é o significado coloquial Além disso há uma certa gramática subjacente algumas cons truções baseadas em princípios lógicos estão presentes nas demonstrações Enfim se corretamente apresentada uma demons tração não deixa dúvidas quanto a sua correção o que dá a linguagem matemática a propriedade notável da sua precisão O estudo formal das deduções logicamente válidas é um dos objetos de estudo da Lógica Matemática Os lógicos constroem linguagens formais rigorosas livres de ambiguidades e de contexto e que são adequadas para lidar com a relação de dedução Essas linguagens possuem uma dimensão sintática que define os símbolos da linguagem e as regras de combinação às quais estão sujeitos para a construção dos termos e fórmulas e uma dimensão semântica que define precisamente o significado delas Além disso um sistema formal especifica os axiomas e as regras de inferência que independem da semântica e são usados para deduzir os teoremas lógicos As teorias axiomáticas são estudadas acrescentando ao sistema lógico seus símbolos e axiomas desse último deduzimos os teoremas que compõem a teoria A teoria dos conjuntos é um sistema adequado para descrever e explicar as estruturas matemáticas A linguagem da lógica de predicados juntamente com a linguagem da teoria de conjuntos compõem um sistema dedutivo formal capaz de expres sar praticamente toda a matemática sem ambiguidades Para conjuntos uma teoria axiomática bem aceita foi apresentada por Ernest Zermelo e Abraham Fraenkel no início do século 20 a teoria de conjuntos de ZermeloFraenkel ZF é um dos vários siste mas axiomáticos propostos para formular uma teoria de conjuntos livre de paradoxos como o paradoxo de Russell por exemplo Acrescentando aos axiomas de ZF o axioma da escolha a teoria é conhecida pela sigla ZFC e é o tratamento axiomático mais comum da teoria dos conjuntos na matemática e amplamente aceita entre os matemáticos como o ponto de partida para fun damentar a matemática de maneira estritamente formal Nós não utilizamos essa linguagem formal no diaadia em Matemática isso deixaria tudo muito árido mas como já disse mos existe uma convenção linguística quase universal na escrita em linguagem natural nas proposições matemáticas que nos faz aceitar as formas como rigorosas e não ambíguas Neste capítulo abordamos tal linguagem informal1 da matemática Ado taremos aqui uma abordagem intuitiva para a teoria dos conjunto e discutiremos brevemente e informalmente a abordagem axiomática ZermeloFraenkel 1Em oposição ao formal das linguagens lógicas 2 111 Sentenças conectivos e operadores lógicos As afirmações matemáticas são sentenças que podem ser verdadeiras ou falsas mas não ambas Uma sentença é uma frase declarativa de um juízo com verbo no indicativo e que assume um e só um de dois valores VERDADEIRO que passamos a denotar por V ou FALSO que passamos a denotar por F O valor de uma sentença é chamado valor lógico da sentença Por exemplo são sentenças 1 O time joga bem 2 O céu está limpo 3 A grama é verde 4 Os torcedores estão felizes Do ponto de vista da linguagem natural é bastante restritivo considerarmos apenas sentenças declarativas porém estamos inte ressado nos enunciados matemáticos 5 11 2 6 3 5 7 Uma sequência limitada de de números reias é convergente 8 27 é um quadrado perfeito 9 O conjunto vazio é único Para tal efeito essas sentaças são satisfatórias Notemos que são sentenças enunciadas como 10 x2 é positivo 11 x é a soma de quatro quadrados perfeitos 12 essa frase é falsa pois não podemos atribuir a elas um valor lógico Toda linguagem permite construir sentenças mais complexas a partir de outras sentenças Uma sentença é dita atômica se a ela corresponde individualmente um desses valoresverdade Sentenças compostas são construídas com os conectivos não e ou seentão se e somente se que chamamos conectivos lógicos São sentenças atômicas O time ganhou o campeonato assim como O técnico é culpado mas não é o caso de O time ganhou o campeonato ou o técnico é o culpado essa última é composta Vejamos mais alguns exemplos 1 Os torcedores estão felizes e o técnico foi demitido 2 Samuel virá para a festa e Maximiliano não virá ou Samuel não virá para a festa e Maximiliano vai se divertir 3 Se o time joga bem então o time ganha o campeonato 4 Se o time não joga bem então o técnico é o culpado 5 27 não é um quadrado perfeito 6 O conjunto vazio não é único O valor lógico de uma sentença composta depende do valor lógico das sentenças atômicas que a compõem e da maneira como elas são combinadas usando os conectivos A cada conectivo lógico corresponde um operador lógico que determina um valor lógico de acordo com as regras abaixo As letras A e B denotam sentenças A negação de A é a sentença não A cujo valor lógico é A dado pela tabela 11 A disjunção de A e B é a sentença A ou B cujo valor lógico é A B dado pela tabela 12 A conjunção é a sentença A e B cujo valor lógico é A B também dado na tabela 12 A condicional é a sentença se A então B cujo valor lógico é A B é dado na tabela 12 Finalmente a bicondicional é a sentença A se e somente se B cujo valor lógico é A B dado na tabela 12 3 A A V F F V Tabela 11 operador negação A B A B A B A B A B V V V V V V V F V F F F F V V F V F F F F F V V Tabela 12 operadores conjunção disjunção condicional e bicondicional Esse é o modo como interpretamos essas palavras chaves e essa interpretação as vezes entra em conflito com interpretações coloquiais O e em geral não causa confusão exceto possivelmente pelo estilo de escrita As vezes pode ocorrer uma confusão por abreviações na escrita Por exemplo quando dizemos que 5 é um natural primo e ímpar significa que 5 tem as duas propriedades porém o conectivo e com sentido lógico conecta sentenças não objetos ou propriedades deles de modo que tal sentença expressa 5 é um natural primo e 5 é um natural ímpar A sentença a se 7 é primo e divide 289 então 7 divide 28 ou divide 9 fica melhor exprimida por se 7 é primo e 7 divide 289 então 7 divide 28 ou 7 divide 9 No caso do ou o equivoco comum é considerar o ou exclusivo no sentido de que a disjunção é verdadeira quando ou uma ou a outra sentença é verdadeira não ambas O não por sua vez é mal interpretado quando mudamos o significado na negação Por exemplo a rigor a negação de o natural 5 é par é o natural 5 não é par que não pode em princípio ser tomada como o natural 5 é ímpar essa equivalência só vale como consequência do teorema da divisão que garante que se um natural não é da forma 2k o que o caracteriza como par então é da forma 2k 1 o que o caracteriza como ímpar A negação de m é o maior elemento do conjunto finito de números A não é dizer que m é o menor elemento de A simplesmente diz que m não é o maior elemento de A Veremos que o oconjunto A está contido no conjunto B significa que todo elemento do conjunto A é elemento do conjunto B cuja negação não é nenhum elemento de A é elemento de B A sentença negada é o oconjunto A não está contido no oconjunto B e significa que nem todo elemento do conjunto A é elemento do conjunto B ou algum elemento do conjunto A não é elemento do conjunto B Esse último caso tem a ver com a negação de uma condicional A condicional é provavelmente o conectivo com mais chance de confusão entre a interpretação coloquial e a intencionada na matemática O condicional É no condicional que se dá a maior diferença entre os significados em matemática e na linguagem coloquial Se os pais dizem ao seu filho se não comer toda a refeição então não ganha a sobremesa a única situação em que os pais ficam desmoralizados é quando o filho não come toda a refeição e ganha a sobremesa A confusão aqui normalmente se dá quando se não comer toda a refeição então não ganha a sobremesa é interpretado também como se comer toda a refeição então ganha a sobremesa o que a rigor no sentido matemático não está dito tal sentença valeria se a sentença original fosse uma bicondicional Ocorre que não foi estabelecido o que acontece quando o filho come toda a refeição de modo que se ele ganha a sobremesa está tudo correto os pais estão sendo verdadeiros e se ele não ganha a sobremesa também está tudo correto Certamente se o filho não comer toda a refeição e não ganhar a sobremesa também os pais foram verdadeiros Outro problema que ocorre frequentemente é quando interpretamos a condicional como uma consequência uma relação de causaefeito entre as sentenças que não é o caso Todos concordamos que é verdadeira a sentença2 para todo número natural n se n primo então n é maior ou igual a dois pois decorre da definição de número primo Dito isso as particularizações de se n primo então n é maior ou igual a dois devem ser verdadeiras ou seja se 1 primo então 1 é maior ou igual a dois 2Augusto Oliveira Lógica Aritmética Ed Gradiva 2010 4 é verdadeira se F então F é verdadeira assim como se 4 primo então 4 é maior ou igual a dois é verdadeira se F então V é verdadeira Exercício 1 Qual é a única sentença falsa dentre as quatro condicionais a seguir se 2 é racional então 2 é par se 2 é racional então 2 é ímpar se 2 não é racional então 2 é par se 2 não é racional então 2 é ímpar Em A B chamamos A de antecedente e B de consequente da condicional A recíproca de A B é B A Observe que há casos em que A B tem valor lógico diferente de B A A contraposutiva de A B é B A Podese verificar que contrapositiva tem sempre o mesmo valor lógico que a sentença que a originou Em português a sentença se A então B pode ser expressa de muitas formas Algumas delas estão descritas abaixo B sempre que A B se A A é suficiente para B B é necessário para A O se e somente se também pode ser expresso de várias maneiras dentre elas A é condição necessária e suficiente para B A é sócio equivalentes se A então B e se B então A Neste texto usamos a abreviação A se B Tautologia e Contradição Tautologia e contradição é como chamamos as sentenças compostas com valorlógico constante Uma tautologia é uma sentença composta que é sempre verdadeira Uma contradição é uma sentença composta que é sempre falsa Por exemplo A A é uma tautologia e A B A B é uma tautologia enquanto que A A é uma contradição Por abuso de notação representamos uma tautologia qualquer genérica por V e uma contradição qualquer genérica por F Variáveis Usualmente uma variável é um símbolo que funciona como um espaço reservado para um objeto matemático de algum universo do discurso Embora tratamos de sintaxes linguagens formais como a teoria formal de conjuntos o que não é feito neste texto as variáveis devem estar associadas a domínios Em geral o símbolo usado é uma letra É possível que variáveis desempenhem papéis diferentes na mesma expressão Por exemplo como na forma geral de um polinômio de grau no máximo dois ax² bx c onde a b c são considerados números são chamadas de parâmetros ou coeficientes muitas vezes são chamadas impropriamente de constantes e x é a indeterminada Com funções o termo variável se refere aos argumentos das funções em fx a letra f é uma função da variável x Em algumas situações o termo essa x também é chamada de parâmetro um objeto ou quantidade de um problema que apresenta constante durante toda a solução ou cálculo desse problema Por exemplo em termodinâmica a pressão e a temperatura são parâmetros para o estudo de gases Todas essas denominações de variáveis são de natureza semântica Em disciplinas como a matemática e a ciência da computação uma variável livre é um símbolo que especifica posições em uma expressão onde uma substituição pode eventualmente ocorrer Por exemplo esse x do caso de x em limxh xh² x²h 2x Predicados Uma sentença aberta é uma sentença parametrizada por uma ou mais variáveis ela nos diz algo um predicado de uma ou mais variáveis Uma sentença aberta não tem valor lógico porque atrai um elemento de um conjunto o domínio para variar e a sentença deixa de ser aberta e passa a ser um sentença com valor lógico O processo de trocar as ocorrências de uma variável por um elemento de um domínio chamamos de instanciação da variável Entendemos por predicado a declaração a respeito de uma ou mais variáveis Por exemplo x é primo x é maior que 0 x é menor ou igual a y x y z são vértices de um triângulo x 1 são predicados Observemos que x 1 não é predicado essas expressões não diz algo a respeito de x Algumas vezes por conveniência usamos a notação funcional para sentenças preditivas letras minúsculas x y z denotam variáveis e letras maiúsculas PQR os predicados os quais são seguidos por uma lista de variáveis distintas entre parênteses usados para denotar sentenças abertas que dependem dessas variáveis por exemplo Ox representa a sentença aberta x x² Px representa a sentença aberta x é primo Qxy representa a sentença aberta x y² Sn representa a sentença aberta Σn k1 kn1 Em nossos casos uma instanciação de uma variável torna toda ocorrência daquela variável pela instância Usando os exemplos acima temos O1 é 1 1² P4 é 4 é primo e Q12 é 1 2² A sentença Q1 2 é 1 2² portanto aberta Se instanciamos todas as variáveis de uma sentença aberta ela deixa de ser aberta e passa a ter valor lógico por exemplo Rxy dada por x y é uma sentença verdadeira se os valores de x e y forem 7 e 4 ou seja R7 4 é verdadeira Mas sentença é falsa se os valores extremos x 1 e y 2 ou seja R1 2 é falsa De um modo geral dado um predicado Px₁x₂xᵢ usamos a notação Pv₁v₂vᵢ para indicar a substituição de todas as ocorrências da variável xᵢ pelo valor vᵢ para todo i 12n Podemos combinar predicados usando os conectivos lógicos para formar outros preditorados 6 Uma variável muda às vezes chamada de variável ligada ou variável vinculada é uma variável associada a um valor específico ou conjunto de valores como é o acima A expressão 11 expressa informação a respeito de x mas não expressa nada a respeito de h ela poderia ser então escrita como limₕ0 xh² x²h A sentença n 2 n é para natural j que expressa algo a respeito de n a saber que é um número par porém não expressa nada a respeito de k poderíamos ter escrito n 2 j para natural j A variável livre nessa expressão se torna muda quando escrevemos para todo natural n n 2 k para natural j Agora não se expressa mais um fato a respeito de n pois se exprime que todo número natural é par A expressão n k1 k nn12 afirma algo a respeito da variável n essa variável é livre k por seu lado é muda Ela está associada aos números inteiros de 1 a n pois o símbolo Σ à esquerda da igualdade nos indica a soma de todos os valores que k assume nesse intervalo desde quando k 1 até k n Notemos que é indiferente usarmos k e k para esse fim Em k0 xkk a variável k é muda enquanto que t e n são livres o valor das expressões também não depende de k só de t e de n de modo que podemos dizer que temos uma função f com domínio e contradomínio que devem ser especificados dada por ftn 1x k0 xkk então agora é essa sentença que não apresenta variável livre é verdadeira No exemplo ₀ xⁿ ex dx uma expressão aritmética que varia depende da variável x mas não da variável k de fato essa soma infinita é a função f que consideramos R Assim é k0 xkk² é uma expressão a certa da variável 1 x e modo que se expressa para todo x R assim e k0 k² e então agora é essa sentença que não apresenta variável livre é verdadeira 12 Modus tollens Se A B e B são duas premissas podemos usar o modus tollens para deduzir A Por exemplo A B B Portanto A Se você tem uma senha então você pode entrar no moodle Você não pode entrar no moodle Portanto você não tem uma senha Regra do silogismo hipotético Se A B e B C são duas premissas podemos usar o silogismo hipotético para deduzir A C A B B C A C Regra do silogismo disjuntivo Se A e A B são premissas podemos usar o silogismo disjuntivo para deduzir B A B A B Regra da contradição Se A F é verdadeiro então A é verdadeiro A F A Regra da conjunção Se temos A e B então deduzimos A B A B A B Podemos usar essa regras para escrever outras regras ou argumentos válidos O seguinte é um argumento válido Resolucao Vejamos passo proposta justificativa 1 A B premissa 2 B S premissa 3 A C premissa 4 C A contrapositiva de 3 5 C B Silogismo hipotético de 4 e 1 6 C S Silogismo hipotético de 5 e 2 Exercício 9 Preste atenção nesse caso se 2 32 então 2 94 2 32 Portanto 2 94 o argumento é válido Exercício 10 Verifique a validade das seguintes regras de inferência Quantificadores A substituição de variáveis por valores do domínio não é a única maneira de transformar uma sentença aberta em uma sentença Outra maneira é a quantificação da variável A quantificação permite expressar conceitos como todos os elementos do domínio ou alguns elementos do domínio O primeiro é chamado quantificação universal e segundo de quantificação existencial A quantificação universal de Px é a sentença para todo x D Px 12 que é verdadeira se Px é verdadeiro para toda instanciação de x com valores de um domínio D Caso Px seja falsa para um ou mais valores atribuídos a x então a sentença 12 é falsa A sentença 12 é simbolicamente escrita como x D Px Um elemento de D para o qual P é falso um contraexemplo para 12 Por exemplo para todo x Z x x 1 é verdadeira enquanto que para todo x N x é primo é falsa pois por exemplo 4 N e 4 não é primo Nesse caso dizemos que 4 é um contraexemplo para para todo x N x é primo A quantificação existencial da sentença aberta Px é a sentença existe x D Px 13 que é verdadeira se Px é verdadeiro para pelo menos uma instanciação de x com valores de D Caso Px seja falsa para todos os valores de D atribuídos a x então a sentença existe x D Px é falsa Simbolicamente usamos x D Px para expressar 13 Por exemplo existe x Z x x 1 é falsa enquanto que existe x N x é primo é verdadeira Exemplo 2 São exemplos de sentenças quantificadas 1 Todo o número inteiro que não é ímpar é par Essa sentença fica melhor no sentido de explicitar seus componentes lógicos se a escrevemos comopara todo n Z se n não é impar então n é par Em símbolos poderíamos escrevêla como n Zk Zn 2k 1 k Nn 2k 2 Para cada número real x existe um número real y para o qual y3 x ou em símbolos x R y R y3 x 3 Dado qualquer dois números racionais a e b seguese que ab é racional ou seja para todo a Q para todo b Q a b Q Exemplo 3 As sentenças 1 para todo x R se x 0 então x2 0 2 existe x R se x 0 então x2 0 são verdadeiras Agora para todo x R se x 0 então x2 3 é falsa e para mostrar isso basta exibirmos um contraexemplo Nesse caso um contraexemplo é um valor a do domínio para o qual se a 0 então a2 3 é falso como o número 0 Negação e domínio vazio Deve ficar claro que da exposição acima podemos concluir que a negação de para todo x D Px é existe x D não Px Exercício 4 Qual é a negação de existe x D Px No caso de domínio vazio convencionamos que para todo x D Px é verdadeiro Isso corrobora o fato da negação dessa sentença ser falsa isto é existe x D não Px é falso independentemente de P pois D Analogamente existe x D Px é falso 7 Omissão de quantificadores As vezes infelizmente ocorre em textos que lemos a omissão de quantificadores que deveriam estar presentes para que expressões tenham seu significado explicitado Nesses casos os quantificadores estão implícitos como nos seguintes exemplos No domínio do reais a afirmação se x é inteiro então x é racional é uma sentença implicitamente quantificada universal mente que simbolicamente pode ser escrita como para todo x R se Z então x Q assim como a identidade trigonométrica sin2xcos2x 1 que é completamete expressa como para todo x R sin2xcos2x 1 Múltiplos quantificadores Se uma sentença aberta menciona mais de uma variável é preciso um quantificador para cada va riável distinta para transformála numa sentença fechada Por exemplo no domínio dos inteiros há oito maneiras de transformar a sentença aberta x y y x em uma sentença fechada 1 x Z y Zx y y x 2 x Z y Zx y y x 3 x Z y Zx y y x 4 x Z y Zx y y x 5 y Z x Zx y y x 6 y Z x Zx y y x 7 y Z x Zx y y x 8 y Z x Zx y y x Em sentenças com mais de uma variável a ordem em que os quantificadores aparece é importante Por exemplo se x e y são inteiros para todo x Z existe y Z x y 0 14 não é logicamente equivalente a existe y Z para todo x Z x y 0 15 pois 14 é verdadeiro enquanto que 15 é falso Entretanto em alguns casos vale a equivalência Por exemplo para todo x N existe y N x divide y é verdadeira assim como existe y N para todo x N x divide y pois no segundo caso todo x N divide o 0 Ao escrever e ler demonstrações de teoremas nós devemos estar sempre atentos à estrutura lógica e ao significados das sentenças Às vezes é útil escrevêlas em expressões que envolvem símbolos lógicos Isso pode ser feito mentalmente ou em papel de rascunho ou ocasionalmente mesmo explicitamente dentro do corpo de uma prova Entretanto devese ter em mente que simbolizar uma sentença não a torna mais formal ou mais correta Exercício 5 Escreva a seguintes sentenças em português e diga se são verdadeiras ou falsas 1 x R x2 0 2 x R n N xn 0 3 a R x R ax x 4 n Z m Z m n 5 5 m Z n Z m n 5 8 112 A implicação lógica Quando lemos um teorema em um livro como se a função f é diferenciável em a então a função f é contínua em a em um livro de análise real por exemplo entendemos que tal sentença é verdadeira e seguirá uma demonstração de tal fato Esse entendimento de que a sentença do teorema é verdadeira significa formularmos uma outra sentença que afirma que algo sobre a primeira sentença a saber formulamos que a sentença se a função f é diferenciável em a então a função f é contínua em a é verdadeira Dizemos que essa última é uma metassentença uma sentença que diz algo respeito de sentenças Ademais a demonstração de tal teorema estabelece uma relação entre a sentença a função f é diferenciável em a e a sentença a função f é contínua em a a saber que a segunda é verdadeira sempre que a primeira é verdadeira A ideia intuitiva de implicação lógica é que a sentença A implica na declaração B se B é verdadeiro sempre que A é verdadeiro Em outras palavras nunca pode ser o caso em que A é verdadeiro e B é falso O valor verdadeiro da condicional A B não deve ser circunstancial devido ao valor verdade das sentenças A e B A impli cação lógica não deve depender dos valores lógicos particulares das sentenças atômicas que a compõem pois elas estão de tal forma relacionadas nas fórmulas que resultado final é sempre uma condicional tautológica como no seguinte exemplo trivial A A não importa o valor lógico de A a condicional é sempre verdadeira O mesmo ocorre com A e A B B o segundo condicional é sempre verdadeiro independentemente dos valores lógicos de a e B Dizemos que A implica logicamente B ou simplesmente A implica B se a sentença condicional se A então B em símbolos A B é uma tautologia Nós abreviamos a expressão A implica B por A B É importante notarmos a diferença entre as notações A B e A B Na prática do ponto de vista informal que adotamos a distinção é simples A B é uma sentença composta construída a partir de A e B que lemos se A então B A B é uma metasentença que significa que A B é uma tautologia ou seja verdadeiro independentemente dos valores lógicos de A e de B e que lemos se A então B é verdadeiro ou se A é verdadeiro então B é verdadeiro Veremos adiante que as implicações são extremamente úteis na construção de argumentos válidos Mais geralmente sejam A1 A2 An e B sentenças Dizemos que essas sentenças A1 A2 An implicam logicamente B se A1 A2 An B é uma tautologia e escrevemos A1 A2 An B Por exemplo dado que A B é verdadeira temos que sua conclusão B pode ser verdadeira ou falsa mas se nos é dado que a hipótese A também é verdadeiras então a conclusão B deve ser obrigatoriamente verdadeira isto é A A B B Essa implicação lógica é conhecida por modus ponens Exemplo 6 Considere as sentenças A dada por Mané estuda B por Mané joga futebol e C dada por Mané passa em discreta Então A C B A C têm como consequência lógica B A tabela 13 lista algumas consequências lógicas notáveis As letras ABC denotam sentenças e A e B predicados Adição A A B Simplificação A B A A B B Modus ponens A A B B Modus tollens A BB A Silogismos A BB C A C A BA B Contradição A F A Distributiva para quantificadores xPxxQx x PxQx x PxQx xPxxQx Tabela 13 Consequências lógicas notáveis 9 Do exemplo 6 acima tiramos 1 A C premissa 2 C premissa 3 B A premissa 4 C A contrapositiva de 1 5 A Modus ponens de 2 e 4 6 A B contrapositiva de 3 7 B modus ponens de 5 e 6 8 B dupla negação em que cada linha a partir da linha 4 é consequência lógica das linhas anteriores portanto B é consequência lógica das premis sas Equivalência lógica Há sentenças que são diferentes mas transmitem a mesma informação como não é o caso de eu não perder o guardachuva ser equivalente a eu vou perder o guardachuva O que nos interessa são declarações logicamente equivalentes ou seja sentenças diferentes como mesmo valor lógico como por exemplo A e A Duas sentenças A e B são logicamente equivalentes se assumem o mesmo valor lógico isto é A B é uma tautologia A notação é A B As sentenças abertas Px e Qx são logicamente equivalentes se Pa Qa é tautologia para todo a D e escrevemos x DPx Qx Por exemplo A B A B e A B A BB A Observamos que é um conectivo ele conecta sentenças enquanto que é uma abreviação de uma metassentença As leis de equivalências dadas na tabela 14 são notórias e a seguir são usadas para deduzir outras Identidade A V A A F A Idempotência A A A A A A Distributiva A B C A BA C A B C A BA C Comutativa A B B A A B B A Associativa A B C A BC A B C A BC Absorção A A B A A A B A De Morgan A B A B A B A B Dominação A V V A F F Inversas A A V A A F Dupla negação A A Contrapositiva A B B A Contradição A B A B F Distributiva para quantificadores x PxQx xPxxQx x PxQx xPxxQx Negação x Px x Px x Px x Px Tabela 14 Equivalências lógicas notáveis 10 Exercício 7 Verifique usando as leis da tabela 14 que A BAB é logicamente equivalente a A Resolução A BAB A BAB por De Morgan A BA B por dupla negação A B B por distributiva A F por inversa A por identidade Exercício 8 Verifique que A B A B Regras de Inferência e Argumentos válidos Um argumento é uma sequência A1 A2 An de sentenças ditas premissas que terminam com uma sentença dita conclusão B o que indicamos pelo símbolo lido como portanto A1 A2 An B O argumento é válido se e só se A1 A2 An B isto é se a conclusão B é verdadeira sempre as premissas forem verdadeiras Regras de inferência são esquemas de argumentos válidos simples que usamos para para construir argumentos válidos mais complexos Por exemplo Se você tem uma senha então você pode entrar no moodle Você tem uma senha Portanto você pode entrar no moodle é um argumento válido porque se encaixa na lei de modus ponens dada na tabela 13 o argumento A B A B é uma regra de inferência chamada Modus Ponens Cada lei dada na tabela 13 nos dá uma regra de inferência 1 Regra da Adição Se A é uma premissa podemos deduzir A B A A B 2 Regra da Simplificação Se A B é uma premissa podemos deduzir A A B A 3 Modus ponens A B A B 11 9 Resolução A B A C B C 10 Prova por casos A B C B A C B Regras de inferência para quantificadores 11 Instanciação universal Se x D Px é uma premissa então deduzimos Pc para qualquer que seja c elemento do domínio D x DPx Pc 12 Generalização universal Se Pc para um elemento c arbitrário do domínio D é premissa então deduzimos x D Px Pc para c arbitrário x DPx Exemplo 11 Consideremos a sentença aberta n2 n Usando a generalização universal para c 0 02 0 n N n2 n o que não é válido porque 0 não é um elemento arbitrário 13 Instanciação existencial Se x D Px é premissa então deduzimos Pc para algum elemento c do domínio D x DPx Pc 14 Generalização existencial Se Pc para algum c particular em D é premissa então deduzimos x D Px Pc para algum c particular x D Px Por exemplo o seguinte argumento é válido xPx Qx xQx Rx xPx Rx Vejamos passo proposição justificativa 1 xPx Qx premissa 2 xQx Rx premissa 3 Pc Qc instanciação universal de 1 4 Qc Rc instanciação universal de 2 5 Pc Rc Silogismo hipotético de 3 e 4 6 xPx Rx generalização universal Da regra da conjunção podemos mostrar que x DPxQx x DPxx DQx Vejamos 13 passo proposição justificativa 1 xPxQx premissa 2 PcQc instanciação existencial de 1 3 Pc simplificação de 2 4 Qc simplificação de 2 5 xPx generalização existencial de 3 6 xQx generalização existencial de 4 7 xPxxQx conjunção No próximo exercício suponha que há um domínio associado sem se preocupar com o que de fato é tal conjunto pode ser o conjunto de todos os animais conhecidos por exemplo Exercício 12 Lewis Carrol Verfique se o seguinte argumento é válido Todos os leões são selvagens Alguns leões não bebem café Portanto alguma criatura selvagem não bebe café Solução Consideremos Matata um elemento do domínio passo proposição justificativa 1 xLx Sx premissa 2 xLxCx premissa 3 LMatataCMatata instanciação universal de 2 4 LMatata simplificação de 3 5 CMatata simplificação de 3 6 LMatata SMatata instanciação universal de 1 7 SMatata Modus Ponens de 4 e 6 8 SMatataCMatata conjunção de 5 e 7 9 xSxCx generalização existencial Exercício 13 Modus ponens universal Verifique se o seguinte argumento que combina instanciação universal com Modus Po nens é válido xPx Qx Pa Qa Exercícios 1 Sejam P e Q as sentenças a eleição foi decidida e os votos foram contados respectivamente Expresse cada uma das sentenças simbólicas abaixo como uma sentença em português a P b PQ c P Q d QPQ 2 Considere que P Q e R sejam sentenças verdadeiras Verifique quais das afirmações são verdadeiras a P Q b Q P c P Q R d P Q e P R f P Q P 3 Verifique que 14 a há casos em que P Q é verdadeira mas sua recíproca Q P é falsa e viceversa b há casos em que P Q é verdadeira mas sua inversa P Q é falsa c a sentença P Q e sua contrapositiva Q P têm sempre o mesmo valor lógico 4 A sentença A BA B é uma contradição 5 Escreva as afirmações abaixo na forma simbólica definindo e atribuindo símbolos aos predicados e definido os domínios dos quantificadores a Todos os estudantes gostam de lógica b Alguns estudantes não gostam de lógica c Cada pessoa tem uma mãe d Entre todos os inteiros exitem alguns que são primos e Um dia do próximo mês é domingo f Alguns inteiros são pares e divisíveis por 3 g Alguns inteiros são pares ou divisíveis por 3 h x2 14 0 tem uma solução positiva i Toda solução de x2 14 0 é positiva j Nenhuma solução de x2 14 0 é positiva k Existe algum estudante de direito que não é brasileiro l Todo estudante de direito tem um celular m Ninguém é perfeito n Alguém é perfeito o Todos os nossos amigos são perfeitos p Algum de nossos amigos é perfeito q Todos são nossos amigos e são perfeitos r Ninguém é nosso amigo ou alguém não é perfeito 6 Sejam N o conjunto dos números naturais e suponha que Px significa x é par Qx significa x e divisível por 3 Rx significa x e divisível por 4 e Sx y é x 2 y Escreva em português cada uma das sentenças a seguir e determine seu valor lógico a x NPx b x NPxQx c x NPx Qx d x NPxRx e x NPxRx f x NRx Px g x NPx Qx h x NPx Px 2 i x NRx Rx 4 j x NQx Qx 1 k x NRx l x NPxQx m x NPx Qx n x NQx Qx 1 o x NPx Qx 1 p x Ny NSx y 15 q x Ny NSx y r y Nx NSx y 7 Verifique as equivalências e implicações lógicas notáveis dadas nas tabelas 14 página 10 e 13 página 9 8 Verifique as seguintes equivalência lógicas para provas por contradição P Q P Q R R P Q P Q P P Q P Q Q 9 Para cada sentença determine o valor verdade e a negação Na negação expresse em símbolos a sentença usando as equivalências lógicas para a negação de quantificadores a n Nm Nn2 m b n Nm Nn m2 c x Ry Rx y2 d n Nm Nn m 0 e n Nm Nn2 m2 25 f n Nm Nn m 4n m 2 g n Nm Np Np nm 2 h x Ry Rxy 0 i x Rx 0 y Rxy 1 j x Ry Ry 0 xy 1 k x Ry Rx 2y 22x 4y 5 l x Ry Rx y 22x y 1 10 Considere Gx y como x gosta de y Expresse em símbolos as sentenças a todo mundo gosta de todo mundo b todo mundo gosta de alguém c alguém gosta de todo mundo d alguém gosta de alguém 11 A sentença x X Ax é falsa se e somente se x X Ax é verdadeira ou seja a sentença x X Ax é falsa se e somente se podemos encontrar um x0 X tal que Ax0 é uma sentença falsa Tal x0 é chamado de contraexemplo para x X Ax Determine um contraexemplo para a x R x 0 b x R x2 x c x N x2 x d x 3579 x 3 7 e x 3579 x é primo 12 Verifique se cada argumento abaixo é um argumento válido a A B A C A B C b Rc t DPt Qt t DQt Rt Pc 16 13 Dê a justifcativa para cada passo dos argumentos abaixo para que seja válido a P P QS RR Q S T b P QR SP R Q S c passo justificativa 1 P 2 P Q 3 Q 4 R Q 5 Q R 6 R 7 S R 8 S 9 S T d passo justificativa 1 Q S 2 Q S 3 S 4 R S 5 R 6 P Q 7 Q 8 P 9 P R 10 R 11 R R 12 Q S 14 Uma argumento não é válido se é possível que as premissas sejam verdadeiras e a conclusão falsa Mostre que os seguintes argumentos não são válidos exibindo valoreslógicos para as sentenças PQRS de modo que as premissas são verdadeiras mas a conclusão é falsa a P Q Q R R S S Q S b P P R P Q R QS S 15 Verifique que valem as equivalências e consequências lógicas abaixo a x DPxQx x DPxx DQx b x DPxx DQx x DPxQx c x DPxQx x DPxx DQx d x DPxQx x DPxx DQx 16 Escreva os seguinte argumentos na forma simbólica estabeleça sua validade ou dê um contraexemplo para mostrar que é inválido a Se Raquel consegue posto de supervisor e trabalha duro ela ganhará um aumento Se ela receber o aumento então ela vai comprar um carro novo Ela não comprou um carro novo Portanto ou Raquel não conseguiu o posto de supervisor ou ela não trabalhou duro 17 b Se Dominic for para a pista Helen ficará louca Se Ralph jogar cartas a noite toda então Carmela ficará louca Se Helen ou Carmela ficarem loucas então Veronica a advogada delas será notificada Verônica não teve notícias de nenhum desses dois clientes Portanto Dominic não chegou à pista e Ralph não jogou cartas a noite toda c Se há uma possibilidade de chuva ou sua camisa vermelho está lavando Luiz não cortará sua grama Sempre que a temperatura é superior a 25ºC não há chance de chuva Hoje a temperatura é de 30ºC e Luiz está usando sua camisa vermelha Portanto hoje Luiz cortará a grama 12 A teoria dos conjuntos de ZermeloFraenkel A elegante teoria dos conjuntos desenvolvida por Ernest Zermelo 18711953 e Abraham Fraenkel 18911965 e que teve impor tantes contribuições de outros outros conquistou a matemática moderna que fez dela um dos seus pilares fundamentais A ideia por trás dessa fundamentação é considerar que todos os objetos é estruturas ma temáticas são definíveis como conjuntos nú meros conjuntos elementos dos conjuntos tudo é conjunto A teoria foi batizada como sistema ZFC em homenagem a Zermelo e Fraenkel a letra C vem do inglês choice em referência ao axioma da escolha que levanta polêmica entre alguns matemáticos 121 Abordagem intuitiva da teoria dos conjuntos Conjunto é informalmente entendido como uma coleção de entidades ou objetos chamados de elementos do conjunto e eles mesmos podem ser conjuntos Um elemento x pertence ao conjunto A se x é um elemento de A o que é denotado por x A e escrevemos a negação como x A Essa sentença não define conjunto ela é circular pois usa o termo coleção que é sinônimo de conjunto e não esclarece o que são objetos Não definimos conjunto e assumimos que todos têm alguma noção mesmo que possivelmente errada da concepção de conjuntos Axiomas e termos indefinidos são inevitáveis em um tratamento rigoroso da matemática A abordagem moderna em mate mática aceita a existência de termos indefinidos desde que sejam usados adequadamente Em última análise objetos indefini dos não nos incomodam porque tais objetos não existem em si mesmos pois são determinados pelas propriedades axiomáticas hipotetizadas para eles e são essas propriedades que usamos nas provas Convencionamos usar letras maiúsculas para conjuntos e minúsculas para elementos Entretanto um conjunto pode ser elemento de outro conjunto assim um conjunto representado por uma letra minúscula deve ser entendido como um elemento de algum outro conjunto Igualdade de conjuntos Dois conjuntos são iguais se e somente se têm os mesmos elementos Ou seja a única propriedade distintiva de um conjunto é sua lista de membros Conjunto vazio Há um único conjunto sem elementos denotado por e chamado de conjunto vazio Especificação de conjuntos Da igualdade de conjuntos podemos inferir que especificar todos os elementos de um conjunto é suficiente para definilo podemos fazer isso de diversas formas Se um conjunto tem poucos elementos podemos listálos entre chaves separados por vírgulas Por exemplo o conjunto dos algarismos primos é formado pelos números inteiros 2 3 5 e 7 e escrevemos 2357 O conjunto dos algarismos indo arábicos é 0123456789 Quando os conjuntos têm muitos elementos não é viável escrever todos seus elementos e uma solução comum mas que só usamos quando o contexto não dá margem a ambiguidade sobre seu significado é o uso de reticências Por exemplo o con junto dos naturais menores que 2017 é descrito por 012016 o conjunto das letras do alfabeto abcz o conjunto dos naturais pares 0246 No geral é preciso muito cuidado e a recomendação é que essa solução deve ser evitada pois por exemplo o que é o conjunto 357 Exercício 14 Encontre duas respostas factíveis para a pergunta acima Além de listar os elementos de um conjunto explicitamente também podemos definir conjunto por especificação também chamado de seleção onde damos uma regra de como gerar todos os seus elementos Podemos especificar um conjunto através de uma ou mais propriedade de seus elementos e nesse caso usamos a notação como A x D Px 18 em que P é um predicado sentença aberta Assim a A é verdadeiro e se σ é um elemento do domínio D para o qual Pa é verdadeiro Por exemplo x ℝ x² 2 corresponde ao intervalo fechado da reta real composto pelos números cujos quadrado é no máximo 2 ou ainda o intervalo 22 o conjunto dos números naturais primos é o conjunto dos números naturais maiores que 1 e que não têm divisores além do 1 e do próprio número Essa sentença pode ser escrita como se x yz então y 1 ou z 1 e modo que o conjunto dos números primos é especificado por x ℕ x 1 para todo y e todo z naturais se yz x então y 1 ou z 1 Há ainda um esquema de substituição uma descrição parametrizada usada para os elementos de um conjunto Nesse caso se f é uma função com um domínio que incluiu o conjunto D então formamos o conjunto dos fx tal que x D Por exemplo o conjunto dos inteiros ímpares é dado por 2k 1 k ℤ Observamos que 2357 pode ser especificado Observamos também que elementos de um conjunto podem eles mesmos serem conjuntos X a b c Observamos ainda que conjuntos não contêm elementos repetidos e não existe ordem na descrição dos elementos 111 1 1211 12 123 231 213 Operações sobre conjuntos As operações sobre conjuntos definem novos conjuntos A seguir descrevemos as quatro operações mais usuais e suas propriedades União A B denota a união dos conjuntos A e B que é o conjunto dos elementos que pertencem a A ou a B A B x x A ou x B Interseção A B denota a interseção dos conjuntos A e B que é o conjunto dos elementos que pertencem a A e a B A B x x A e x B Diferença A B denota o conjunto dos elementos que pertencem a A e não a B A B x x A e x B Diferença simétrica A Δ B denota o conjunto dos elementos que pertencem exclusivamente a A ou a B mas não a ambos A Δ B x x A B e x A B Figura 11 Diagrama de Venn das operações sobre conjuntos Fica como exercício a verificação das propriedades descritas na tabela 15 abaixo Algumas delas seguem das equivalências lógicas notáveis exercício 7 página 16 as outras seguem de alguma equivalência lógica que você deve provar Exercício 18 Verifique que para quaisquer conjuntos A e B as duas inclusões abaixo são verdadeiras A B A B Partição de um conjunto Dizemos que A e B são conjuntos disjuntos se A B Se X é um conjunto então dizemos que o conjunto P é uma partição de X se 1 para todo a P e todo b P se a b então a b em outras palavras quaisquer dois elementos distintos de P são disjuntos 2 UP X em outras palavras a união dos elementos de P é exatamente X Exercício 20 Seja P o conjunto dos números inteiros Para cada i 012 denote por Ri o subconjunto dos números inteiros que deixaram rest e quando divisível por 3 Prove que R0R1R2 é uma partição de Z A teoria axiomática dos conjuntos utilizada na matemática é formalizada a partir de uma coleção de axiomas que nos permitem construir essencialmente a partir do zero um universo grande o suficiente para manter toda a matemática sem contradições aparentes evitando os paradoxos que podem surgir na teoria intuitiva dos conjuntos Vamos descrever os dez axiomas usuais da teoria ZFC abaixo esses axiomas garantem a existência de conjuntos específicos que permitem construir conjuntos a partir de outros conjuntos Axioma da vazio Existe um conjunto que não tem elementos Na linguagem formal axx a Esse conjunto sem elementos é o conjunto vazio Axioma da extensionalidade Quaisquer dois conjuntos com os mesmos elementos são iguais aba b xx a x b Axiom da par Dados conjuntos y e z existe um conjunto a tal que se x e a então x y ou x z Pelo axioma anterior esse conjunto é único é o conjunto y z yzaxx a x y ou x z Axiom da fundação ou da regularidade Cada conjunto não vazio a tem um elemento b com a b aa b a 3ba b b Corolário 24 Se a b então a b b a Para provar o teorema usamos o seguinte resultado auxiliar Lema 25 Se a b a e então a y Funções Definição 28 Uma relação R A B é uma função se para cada x A existe um único y B tal que xy R nesse caso escrevemos Rx y O único y tal que xy R é dito o valor que a função assume em x O conjunto de todas as funções de A em B é um subconjunto de PA B denotado por BA Por exemplo a função f que o axioma afirma existe é um subconjunto de x X ou seja f x Ux com a propriedade de que fy y para todo y x Uma função f A B pode ou não ter uma ou mais das seguintes propriedades injetividade se e só se é verdade que para todos x x A se x x então fx fx sobrejetividade se e só se é verdade que para todo y B existe x A tal que fx y bijetividade se e só se for injetiva e bijetiva isto é é vale a sentença y B x A fx y Composição e inversa de relações As relações e funções podem ser compostas Das relações R A B e S B C definimos a relação composta S R A C pela regra xz S R se e somente se existe y B tal que xy R e yz S Em notação usual x S R z yRxy Syz Não é difícil ver que a composição ordinária de funções é um caso especial de composição de relação Por exemplo considere as relações R 11 14 23 13 34 S 10 20 31 32 41 A composição delas é S R 10 11 21 22 30 31 Dada uma relação R A B a relação inversa R1 em B A definida a partir da equivalência x R1 y se e somente se y R x Toda relação tem uma inversa no entanto a inversa de uma função pode não ser função Por exemplo tome A 123 e R 12 23 33 A relação inversa é R1 21 32 33 Ademais R1 R 11 22 22 33 14 24 41 É verdade que todo subconjunto não vazio de N N tem um menor elemento com respeito a tal order 26 1 Tome A 112 Quais das afirmações a seguir são verdadeiras a Ø b Ø c d e f g h 1 A i 1 A j 2 A k 1 A l 2 A m 1 A n 2 A o 2 A 2 Verifique cada uma das propriedades das operações de conjunto listas na tabela 15 usando equivalências lógicas 3 Enuncie as leis de De Morgan no caso de união e interseção com mais de dois conjuntos 4 Escreva o conjunto das partes de a 2 b 123 c 123 d 123 5 Tome R 11212321130223 e escreva os conjuntos U R e U R 6 Construa os seguintes conjuntos a partir dos axiomas da teoria ZFC Dados os conjuntos A e B a A B b todas as relações de A em B c todas as funções de A em B 7 Seja f X Y e então definimos f1B x X fx B Verifique que a f1A B f1A f1B b f1A B f1A f1B c f1Y B X f1B 8 Considere as seguintes relações sobre 01234 R 1114233134 S 1020313241 Determine S o R R S S o R R 9 Determine a relação inversa de R 121323 sobre A 123 Determine também R1 R e R R1 10 Considere o conjunto N N com a relação N N N N definida por xy ab se x a ou x a e y b 11 Ordene os seguintes elementos de acordo com a relação 1221311222331424441 É verdade que todo subconjunto não vazio de N N tem um menor elemento com respeito a tal ordem 12 Prove que f A B é injetiva e g B C é injetiva então g f A C é injetiva 13 Prove que a composição de duas funções bijetivas é uma função bijetiva 28 Números inteiros e suas propriedades aritméticas e de ordem O conjunto Z 21012 é o conjunto dos números inteiros que munidos das funções operações soma e produto Z Z Z e da relação de ordem satisfazem as propriedades listadas a seguir Com relação a soma Para quaisquer abc Z 1 associativa a b c a b c 2 comutativa a b b a 3 elemento neutro a 0 a e 0 é o único inteiro que satisfaz essa sentença 4 elemento simétrico a a 0 e a é o único inteiro que satisfaz essa sentença 5 cancelatividade se a b a c então b c 6 troca de sinal a b a b a b Com relação ao produto Para quaisquer abc Z 7 associativa a b c a b c 8 comutativa a b b a 9 elemento neutro a 1 a e 1 é o único inteiro que satisfaz essa sentença 10 distributiva a b c a b a c 11 cancelatividade b c a b a c a 0 e a b c b c 12 anulamento se a b 0 então a 0 ou b 0 13 se a b 1 então a 1 e b 1 Com relação a ordem Para quaisquer abc Z 13 reflexiva a a 14 antissimétrica se a b e b a então b a 15 transitiva se a b e b c então a c 16 comparabilidade a b ou b a 17 tricotomia vale uma e só uma das relações a b a b b a 18 compatibilidade a b a c b c c N e a b a c b c 19 a b e b c a c 20 a b e b c a c 21 a b a 2 b 22 a b a b Complemento Conjuntos numéricos Não é difícil definir o conjunto N dos números naturais como conjunto na teoria axiomática dos conjuntos usando o axioma do infinito Uma construção conhecida é devida ao matemático John von Neumann7 A partir da construção definimos as operações aritméticas a relação de ordem e tudo o mais da aritmética pode ser deduzido formalmente dentro da teoria dos conjuntos A partir dos naturais podemos construir os inteiros usando produto cartesiano e um tipo especial de relação chamada de relação de equivalência veja a definição 118 página 62 Também podemos construir os números racionais e até os reais com por exemplo os cortes de Dedekind Neste texto não adotamos tal abordagem a aritmética elementar dos naturais e dos inteiros e suas propriedades são assu midas como axiomas e a definição dos conjuntos em si é a intuitiva Esse será o ponto de partida para estudarmos algumas técnicas de demonstração no próximo capítulo Números naturais e suas propriedades aritméticas e de ordem O conjunto dos números naturais é o conjunto N 012 que munido da adição8 da multiplicação9 e da relação10 usuais nos números naturais satisfazem as seguintes propriedades para quaisquer abcmnp números naturais 1 associativa a bc a b c e m n p m n p 2 comutativa a b b a e m n n m 3 elemento neutro 0 é o único natural tal que a 0 0 a a e 1 é único tal que m 1 1m m e 1 4 cancelamento se a c b c então a b e para a multiplicação se mp np e p 0 então m n 5 distributiva a bm a m b m 6 se a b 0 então a b 0 se m n 1 então m n 1 7 se m n 0 então m 0 ou n 0 8 reflexiva a a 9 antisimétrica se a b e b a então b a 10 transitiva se a b e b c então a c 11 comparabilidade a b ou b a 12 tricotomia vale uma e só uma das relações a b a b b a 13 compatibilidade se a b então a c b c se a b então a c b c Uma propriedade muito importante da estrutura N é que a relação de ordem nos dá uma boaordem Definição 30 Dizemos que a N é o menor elemento de A N se e só se a A e para todo x A a x Denotamos o menor elemento de A por minA Princípio da Boa Ordem PBO Para todo A N se A é nãovazio então A tem um menor elemento 7Também foi um precursor do computador digital os computadores pessoais têm uma arquitetura um esquema de interligar memória cpu dispositivos de entrada e saída chamada arquitetura de von Neumann 8 é uma operação binária NN N e escrevemos a b para denotar ab 9 é uma operação binária NN N e escrevemos a b para denotar ab 10Escrevemos a b se existe um natural m tal que a m b Escrevemos a b caso m 0 Ainda a b denota b a e a b denota b a 27 A b c 0 a b Capítulo 2 Demonstrações 21 Introdução a técnicas de demonstrações Do ponto de vista lógico existem essencialmente dois tipos de sentenças verdadeiras os axiomas que são admitidos como verdadeiros e os teoremas que são demonstrados serem verdadeiros Em textos matemáticos as sentenças que nós demonstra mos são geralmente chamadas de teoremas proposições lemas e corolários A diferença entre esses rótulos é circunstancial e depende de uma convenção não muito rígida que diz em geral que teoremas são resultados importantes as proposições são menos importantes que os teoremas os lemas são resultados auxiliares usadas nas provas de outros resultados e que merecem destaque os corolários são sentenças que se seguem facilmente de outros resultados Ainda há sentenças que chamamos princípio que é um teorema ou axioma e que ocupa um papel fundamental numa teoria por ser a chave para demonstrar um grande número de propriedades importantes Um exemplo típico é o Princípio da Indução Finita que em algumas exposições sobre os naturais ele aparece como um dos axiomas como no tratamento axiomático de Peano e em outras como teorema como na teoria dos conjuntos ZFC Um outro termo recorrente em textos matemáticos é conjetura ou conjectura que é uma sentença que está sendo proposta como uma sentença verdadeira porém não é conhecida uma demonstração Se posteriormente demonstrada verdadeira torna se um teorema se for mostrado um contraexemplo deixa de ser uma conjetura Até o momento que este texto estava sendo escrito a seguinte sentença não tinha uma demonstração CONJECTURA 32 CONJETURA DE GOLDBACH Todo inteiro par maior que 2 pode ser escrito como a soma de dois números primos Muitas das sentenças de teoremas talvez a maior parte são generalizações de sentenças condicionais e vamos dar ênfase nesse caso já que é inviável considerarmos todos as possíveis estruturas lógicas dos enunciados de sentenças 211 Considerações iniciais através de um exemplo Para demonstrar uma sentença precisamos conhecer as definições dos termos usados na sentença Vamos ver um exemplo Começamos com uma definição de número par Definição 33 Um inteiro n é par se e somente se n é da forma 2k para algum inteiro k Um inteiro n é ímpar se e somente se n é da forma 2k 1 para algum inteiro k Observemos que a definição acima é dada por um se e somente se de modo que é usada em demonstrações como uma equivalência lógica para qualquer que seja o inteiro n n é par k Z n 2k 21 Se a definição é dada por uma condicional n é par se n é da forma 2k para algum inteiro k ao invés de uma bicondicional ela a rigor não exclui a possibilidade de n 1 ser par veja a discussão no início da seção 111 Entretanto em textos matemáticos é comum encontrar definições que usam uma condicional e nesses casos devemos entender que a intenção é a da equivalência Por exemplo em um inteiro n é par se ele é múltiplo de 2 não garante que um número par é múltiplo de 2 Além das definições usamos axiomas e teoremas já conhecidos Essa metodologia de derivar teoremas a partir de axiomas o método axiomático foi usado de modo pragmático pela primeira vez por Euclides por volta de 300 aC Como alguém pensa e 30 cria uma demonstração é uma ponto que está fora do nosso alcance não vamos discutir mas a demonstração em si tem que se desenrolar em passos logicamente válidos do início ao fim e é da praxe que as demonstrações sigam alguns paradigmas Cada demonstração tem os seus próprios detalhes mas os paradigmas nos dão um referencial organizado para uma boa escrita das deduções Em muitos casos as sentenças de teoremas são sentenças condicionais não escritas explicitamente as palavraschave se então e para todo ou equivalentes não apareçam explicitamente assim como os quantificadores são omitidos O trabalho inicial sempre é o da interpretação e análise do texto Por exemplo em o quadrado de todo número real não nulo é positivo temos implicitamente a estrutura lógica para todo número real x se x 0 então x2 0 TEOREMA 34 A soma de inteiros pares é par Para demonstrar essa afirmação provamos que para quaisquer x e y inteiros se x é par e y é par então x y é par Essa sentença tem a forma lógica A B C e o que precisamos demonstrar que se A é verdadeiro x é par e B é verdadeiro y é par então C é verdadeiro x y é par Para isso assumimos A e B como hipóteses ou premissas verdadeiras e construímos uma demonstração que conclui que C é verdadeiro Demonstração do teorema 34 Sejam x e y números inteiros e assuma que x é par e y é par Então por definição existem inteiros k1 e k2 tais que x 2k1 e y 2k2 logo x y 2k1 k2 portanto pela definição x y é par Note que na demostração usamos a equivalência 21 nos dois sentido se x é par então ele é múltiplo de 2 e se x y é múltiplo de 2 então ele é par Uma consideração importante ao escrever uma demonstração é reconhecer o que precisa ser provado e o que pode ser usado sem justificativa Esse último depende do contexto e é em geral calibrado de acordo com a audiência a que se destina a demonstração O nosso contexto é o de aprendizado elementar logo é necessário escrever com bastante detalhes Também um trabalho de rascunhagem investigativa é muito importante para descobrir a estratégia geral para abordar o problema a ser resolvido antes de examinar os detalhes Todo matemático teve que tentar muitas abordagens para provar um teorema antes de encontrar uma que funcionasse aqui está a maior parte do trabalho Finalmente as demonstrações devem se escritas em português usando frases completas e com pontuação adequada como foi feito no caso da Demonstração do teorema 34 e não como feita na tabela abaixo Fórmulas e símbolos matemáticos são partes de frases e não são tratados diferente de outras palavras A Leitura Ler uma demonstração exige esforço para a validação do argumento Em casos muito simples como no teorema acima não dá muito trabalho explicitar todo esquema lógico desse argumento Fazemos isso abaixo na tabela 21 usando alguns símbolos para encurtar a escrita fazemos referência a algumas regras de inferência apresentadas na página 11 e seguintes e a propriedades aritméticas apresentadas na seção 124 1 x é par e y é par hipótese 2 x é par regra da simplificação 3 y é par regra da simplificação 4 Se x é par então k1 Zx 2k1 definição 5 k1 Zx 2k1 modus ponens 6 x 2k1 regra da instanciação existencial 7 Se y é par então k2 Z y 2k2 definição 8 k2 Z y 2k2 modus ponens 9 y 2k2 regra da instanciação existencial 10 x 2k1 e y 2k2 regra da conjunção 11 Se x 2k1 e y 2k2 então x y 2k1 k2 compatibilidade 12 x y 2k1 k2 modus ponens 13 Se x y 2k1 k2 então regra da generalização c Zx y 2c universal 14 c Z tal que x y 2c modus ponens 15 Se c Zx y 2c então x y é par definição 16 x y é par modus ponens Tabela 21 Um escrutínio da demonstração do teorema 34 31 Notemos que a partir das premissas na tabela 21 uma linha qualquer é uma sentença verdadeira sempre a linhas anteriores a ela são verdadeiras portanto se a hipótese é verdadeira a última linha é uma sentença verdadeira 212 Demonstração direta de implicação Na argumentação mais direta para demonstrar que P Q é verdadeiro assumimos P verdadeiro e concluímos que Q é verda deiro Essa estratégia é chamada de prova direta da implicação TEOREMA 35 Se a e b são números inteiros tais que 0 a b então a2 b2 DEMONSTRAÇÃO Sejam a e b são números inteiros Vamos supor que 0 a b e provar que a2 b2 Se a b e 0 a então a2 ab Se a b e 0 b então ab b2 Por transitividade a2 b2 como queríamos demonstrar Uma leitura detalhada do argumento é dada na tabela 22 1 0 a e a b hipótese 2 a b regra da simplificação 3 0 a regra da simplificação 4 se 0 a e a b 0 b transitividade do 5 0 b modus ponens 6 se a 0 e a b então a a a b compatibilidade do com 7 a2 ab modus ponens 8 b 0 e a b regra da conjunção 9 se b 0 e a b então a b b b compatibilidade do com 10 ab b2 modus ponens 11 a2 ab e ab b2 regra da conjunção 12 se a2 ab e ab b2 então a2 b2 transitividade do 13 a2 b2 modus ponens Tabela 22 Um escrutínio do teorema 35 TEOREMA 36 Sejam ABC conjuntos não vazios Se A C B e a C então a A B De acordo com a estratégia de demonstração direta devemos supor que A C B e a C é verdadeiro e provar que a A B é verdadeiro Pela definição de diferença de conjuntos a A B é logicamente equivalente a nãoa A e a B que é logicamente equiva lente a a A ou a B que por sua vez é logicamente equivalente a a A a B Portanto se assumimos verdadeiro AC B e a C e deduzirmos que a A a B é verdadeiro então podemos concluir pela equivalência lógica que a A B é verdadeiro Assim nossa tarefa é demonstrar que é verdadeira a primeira condicional A C B e a C a A a B 22 Para demonstrar que vale 22 assumimos A C B e a C verdadeiro provamos a A a B verdadeiro para provar que a A a B é verdadeiro uma condicional assumimos a A verdadeiro e deduzimos que a B é verdadeiro no caso a A não há o que fazer pois a condicional é verdadeira Assim para demonstrar 22 assumimos A C B e a C e a A verdadeiro provamos a B verdadeiro Com esse rascunho em mãos escreveremos a demonstração DEMONSTRAÇÃO Sejam ABC conjuntos não vazios e a A Vamos assumir que A C B e a C e a A Se a C e a A então a A C por definição de interseção Se a A C e A C B então a B por definição de inclusão Portanto a B Há uma esquema lógico genérico da ideia empregada acima vale o seguinte P1 P2 Pn P Q se e somente se P1 P2 Pn P Q 32 Sobre enunciados Como já dissemos muitos teoremas afirmam propriedades para todos os elementos de um domínio sem que o quantificador seja explicitamente mencionado por exemplo Se 3 divide o inteiro n então 9 divide n² 21 Demonstração indireta de implicação Nesse tipo de prova demonstramos que é verdadeira uma sentença logicamente equivalente a P Q como a contrapositiva por exemplo Demonstração pela contrapositiva Para provar que P Q é verdadeira demonstramos Q P é verdadeira Por exemplo para um número natural n arbitrário a seguinte implicação é verdadeira tente uma prova direta se n² é par então n é par 24 A contrapositiva de 24 é assumindo ímpar é negação de par veja corolário 70 se n não é impar então n² é ímpar que é verdadeira como foi estabelecido pelo teorema 39 Definição 44 O maior divisor comum dos inteiros a b denotado mdca b é dado por mdca b 0 maxd ℕ d a e d b se a b 0 caso contrário 25 Os inteiros a e b são coprimos se e só se mdca b 1 Observamos que se d é um natural que divide a então d a portanto o conjunto de todos os divisores de a não tem um maior elemento Se a 0 então todo inteiro d divisor de a portanto o conjunto de todos os divisores de a não tem um maior elemento Analogamente o conjunto de todos os divisores de b não tem um maior elemento Disto o mdca b está bem definido por 25 TEOREMA 45 Para todos a b ℕ se a e b são coprimos então a não é par ou b não é par Vamos demonstrar pela contrapositiva que se a e b são coprimos então não são ambos par Antes o leitor é convidado a dar uma prova direta da sentença A contrapositiva significa provar a sentença se a for par e b for par então mdca b 1 36 para todos ab ℕ A estratégia é clara caso 1 Tome a e b par 2 a 2 b mdca b 2 3 portanto mdca b 1 Pela generalização universal pois a e b são inteiros arbitrários vale que a equação 26 é verdadeira Passemos à demonstração Demonstração do teorema 45 Vamos provar o teorema 45 pela contraposita Sejam a e b números inteiros quaisquer e assumamos que a é par e que b é par Então pela definição 2 divide a logo o mdca b é pelo menos 2 Portanto mdca b 1 Demonstração por contradição Para demonstrar que P Q nós demonstramos a veracidade da condicional P Q F A regra da contradição dada na página 12 é a consequência lógica A F A e fazendo A ser a sentença P Q justifica tal equivalência lógica Assim numa demonstração por contradição assumimos que a hipótese é verdadeira e a negação da sentença é provada é verdadeira e com essas hipóteses derivamos uma contradição Um exemplo de estratégia para prova por contradição é 1 P por hipótese 2 Q por hipótese 3 P por dedução 4 P P pela regra da conjunção De fato na linha 3 deduzimos alguma sentença que junto com as premissas formam uma sentença lógica falsa Também pode ser o caso em que a contradição seja alguma outra sentença que negue algum teorema alguma sentença que é sabia ser verdadeira Veja o exemplo 50 mais adiante Demonstração do teorema 45 A demonstração é por contradição Sejam a e b números inteiros arbitrários Assumamos que a e b são coprimos então a é par então mdca b 2 ou seja mdca b 1 mdca b 2 uma contradição Portanto se a e b são coprimos então a e b não são ambos números pares 37 1 2 Q 2 2 Q a b ℕ coprimos e 2 ab corolário 49 dado abaixo 3 a b ℕ coprimos e 2 ab modus ponens 4 2 ab e a e b são coprimos instanciação existencial 5 a e b são coprimos regra da simplificação 6 2 ab 7 Se 2 ab então 2 ab² compatibilidade 8 Se 2 ab² então a² 2b² compatibilidade 9 2 R e então a² 2b² silogismo 10 a² 2b² então a² é par definição de par 11 Se a² é par então a é par contrapositiva teo 39 12 a é par modus ponens 13 Se a é par então existe k ℕ a 2k definição de par 14 Se a é par então existe k ℕ a 2k definição de par 15 Existe k ℕ a 2k modus ponens 16 a 2k instanciação universal 17 a 2k e a² 2b² conjunção 18 Se a 2k então a² 2b² então 4k² 2b² compatibilidade 19 Se b² 2k² então b² é par definição de par 20 Se b² 2k² então b² é par silogismo 21 Se a 2k e a² 2b² então b é par silogismo 22 b é par modus ponens 23 a é par e b é par conjunção 24 a e b coprimos e a é par e b é par contradição Exemplos 50 Outra prova de que 2 Q Suponha 2 pq de modo que 2 p²q² Escreva q² 2k com k ímpar isso pode ser feito por causa do teorema fundamental da aritmética teorema 73 página 42 Por 2k² ser um quadrado k tem que ser par Por outro lado p² 2q² 2k¹ p e ser um quadrado k é ímpar Portanto k é par e k ímpar o que é uma contradição pelo corolário 70 página 41 A seguir damos um exemplo de prova de uma equivalência usando métodos diferentes para cada condicional Teorema 51 Para todo n Z n é ímpar se e somente se n² é ímpar Demonstração Seja n Z arbitrário Vamos provar que n² ímpar se e só se n ímpar Agora vamos assumir que n² ímpar para provar que n ímpar A prova é por contradição suponha que n é par Então n 2k para algum k Z e n 2k então n² 4k² ou seja n² é par e n ímpar uma contradição Portanto n ímpar se e só se n² ímpar para todo natural n Corolário 52 Para todo n Z n é par se e somente se n² é par Demonstração Exercício Teorema 62 Para todo n racional existe um inteiro x tal que y x Demonstração construtiva Seja y um racional arbitrário Vamos exibir um inteiro n tal que y n Faça n y 1 Temos da definição do valor absoluto que y y Além disso y p e p n Portanto p n Corolário 68 PRINCÍPIO DA DESCIDA INFINITA DE FERMAT Não existe uma sequência decrescente de números naturais TEOREMA 73 TEOREMA FUNDAMENTAL DA ARITMÉTICA Para todo n N se n 1 então n é primo ou pode ser escrito como produto de números primos ademais tal escrita é única a menos da ordem com que se escreve os fatores primos DEMONSTRAÇÃO Seja n 1 um natural A prova é por contradição Assuma que exista n 1 natural que não é primo e não pode ser escrito como produto de primos e defina o conjunto não vazio A formado por todos naturais com tal propriedade Pelo PBO o conjunto A tem um mínimo m Como m não é primo tem um divisor a 1m isto é existe q N tal que m aq Claramente 1 aq m Como m é mínimo a e q são primos ou produtos de primos e em todos os casos m é produto de primos assim temos uma contradição Exercício 74 Prove que há um único modo de escrever n 1 como produto de primos exceto pela ordem dos fatores COROLÁRIO 75 Se n 101 é inteiro então existem primos p1pk tais que n p1p2 pk Vejamos uma prova existencial construtiva para outra propriedade de inteiros dada na página 29 TEOREMA 76 Todo A Z não vazio e limitado inferiormente tem um menor elemento DEMONSTRAÇÃO Seja A Z um subconjunto limitado inferiormente e seja m é uma cota inferior de A Defina o conjunto B a m a A Então B N e B logo para algum b A temos b m minB Se a A então a m B logo b m a m portanto b a ou seja b minA Uma aplicação dessa versão do PBO é o seguinte resultado PROPOSIÇÃO 77 Qualquer postagem que custe pelo menos oito reais pode ser feita com selos de 3 e 5 reais Vamos chamar n N de postal se n pode ser um valor obtido a partir de selos de 3 e 5 reais Por exemplo 8 é postal pois 8 35 também 9 é postal pois 9 3305 e 10 é postal pois 10 0325 DEMONSTRAÇÃO O teorema afirma que para todo elemento de n N n 8 é postal A prova é por contradição Suponha que a afirmação do teorema é falsa Seja A N o subconjunto dos naturais maiores ou iguais a 8 nãopostais Por hipótese A portanto tem um menor elemento m Como 8 é postal basta tomar x y 1 deduzimos que m 9 Dessa forma m1 8 e é postal Logo existem x0 e y0 inteiros tais que m 1 3x0 5y0 Assim deduzimos m 3x0 5y0 1 3x0 5y0 3352 3x0 35y0 2 e como m não é postal obtemos uma contradição Se permitimos troco todo valor pode ser obtido com selos de 3 e 5 Por exemplo se entregamos 3 selos de 3 e recebemos de volta 1 selo de 5 ficamos com 3351 4 pagos pela postagem Exercício 78 Prove que qualquer inteiro z pode se obtido como múltiplo inteiro de 3 mais múltiplo inteiro de 5 Exercício 79 teorema de Bézout Escreva um enunciado preciso e use o PBO para provar a seguinte sentença Sejam ab N números coprimos Existem inteiros x e y tais que ax by 1 dica tome o mínimo do conjunto dos números positivos da forma ax by prove por contradição que esse mínimo é 1 219 Considerações sobre a escrita de uma demonstração Em um sentido técnico e abstrato uma demonstração matemática é a verificação de uma proposição por uma cadeia de dedu ções lógicas a partir de um conjunto básico de axiomas porém o objetivo de uma demostração é fornecer aos leitores provas convincentes para a veracidade de uma afirmação Para cumprir o objetivo de fornecer aos leitores provas convincentes para a veracidade de uma afirmação uma boa demonstração deve ser clara Uma prova bem escrita é mais provável de ser uma prova correta já que os erros são difíceis de esconder Aqui estão algumas dicas sobre como escrever boas provas Indique sua estratégia uma boa prova começa por explicar a linha geral de raciocínio por exemplo Nós usamos indução em n ou Nós provamos por contradição Isso cria uma imagem mental na qual o leitor pode ajustar os detalhes subsequentes Explique seu raciocínio Muitos estudantes inicialmente escrevem provas da forma como eles computam integrais O resul tado é uma longa sequência de expressões sem explicação Uma boa prova geralmente parece um ensaio com algumas equações lançadas Use frases completas Evite o simbolismo excessivo 42 Simplificação provas longas e complicadas levam o leitor mais tempo e esforço para entender e pode ocultar mais facilmente os erros d se d 1 e n então d não divide n 1 Teorema 80 Se existe x tal que Px e existe x tal que Qx então existe x tal que Px Qx Em símbolos x Px x Qx xPx Qx Demonstração Considere o seguinte argumento 1 Px Qx premissa 2 x Px simplificação de 1 3 Pc instanciação existencial de 2 4 x Qx simplificação de 1 5 Qc instanciação existencial de 4 6 Pc Qc conjunção de 3 e 5 7 x Px Qx generalização existencial de 7 a Dê um contraexemplo para a afirmação feita no teorema isto é encontre um domínio D e predicados P e Q sobre elementos de D para o qual a sentença não vale b Indique os erros na demonstração 19 Leia a enunciação o seguinte teorema e uma suposta demonstração Teorema 81 Para todos a b c d números naturais se c divide a e c divide b e d divide a e d divide b e c não divide d então dc divide a e d divide b Em símbolos a b c d N c a e b d a e b c d dc a e dc b Demonstração Sejam a b c d números naturais tais que c divide a c divide b d divide a d divide b e c não divide d Se d divide a e b então existem x e y naturais tais que a xd e b yd Se c divide a então c divide xd Analogamente se c divide b então c divide yd Se c divide yd e não divide d então c divide y Se c divide x e y então existem z e w tais que x cz e y cw Das conclusões acima temos a xd czd dcz b cwd portanto dc divide a e dc divide b a Dê um contraexemplo para a afirmação feita no teorema b Indique os erros na demonstração 20 Dizem que nos seus primeiros anos de Hogwarts Harry Potter resolveu usar seus poderes para escrever uma prova análoga de que 2 não é racional coisa que quase todo mundo sabe que não é A prova de Harry Potter foi Teorema 82 4 não é racional Demonstração Se 4 é racional então existem a b N primos entre si tais que ab 4 Elevando os dois termos da equação ao quadrado temos a² 4b² Logo a² é divisível por 4 e portanto a também o é Por definição podemos escrever a 4k para algum k N e ficamos com 4k² 4b² e portanto 16k² 4b² ou seja b² 4k² Logo b² é divisível por 4 e portanto b também o é o que contraria a escolha de a e b primos entre si Portanto 4 não é racional Onde está a mágica 21 Seja n um natural Prove que se n não é um quadrado então n é irracional dica exerc 2 item 4 ou o corolário 68 22 Prove que existe um racional x e um irracional y tais que xy é irracional 23 O que está errado na seguinte demonstração Teorema 83 Para todo natural n n² n 1 é ímpar Demonstração A prova é por contradição assuma que n² n 1 é par e seja A o subconjunto formado por tais números Pelo P80 podemos tomar m min A Como m 1 m temos que m 1² m 1 1 é par Porém m 1 é m² m 1 2m ou equivalentemente m 1 m 1² m 1 1 2m que é para temos uma contradição Teorema 85 Existe um conjunto de acerto para H com no máximo log₂ mk elementos Demonstração Sorteios uniformemente h log₂ mk elementos de V com repetição para cada um deles a probabilidade de não estar em Aᵢ é 1 kVⁱ A probabilidade de nenhum dos sorteados estarem em Aᵢ é 1 kVⁱʰ Usando que 1 1xᵏ eᵏ logx 1m A probabilidade de haver algum j 12m tal que nenhum dos sorteados estejam em Aᵢ é menor que ᵐⱼ₁ 1m 1 portanto com probabilidade positiva essa seleção define um conjunto com h elementos por causa da repetição que encontra todos os elementos de H Esses dois teoremas são conhecidos como Dessa forma a combinação de um evento fértil para o método probabilístico vamos usar o método probabilístico para provar por contradição que existem infinitos números primos Demonstração Vamos assumir que M é o maior número primo Seja R um número aleatório sorteado de acordo com a seguinte regra R 2² 3³ 5⁵ Mᵗ⁶ e Tₗ é um a menos da quantidade de lançamentos de um dado com p faces as faces são 1p e obtivemos um resultado diferente de 1 Capítulo 3 Princípios de Indução Finita e demonstrações por indução Vimos e usamos em algumas demonstações o Princípio da Boa Ordenação PBO para os números naturais com respeito a ordem usual todo A N nãovazio tem um menor elemento e como consequência provado na página 42 provamos uma versão do PBO para subconjuntos dos inteiros que são limitados inferiormente todo A Z não vazio e limitado inferiormente tem um menor elemento Ambos são ferramentas que provam teoremas importantes sobre números inteiros como o teorema da divisão o teorema de Bézout e o teorema fundamental da aritmética Isso não é por acaso o PBO é de fato um princípio muito forte Esse princípio não vale noutros conjuntos numéricos como Q e R com respeito a ordem canônica Por exemplo o intervalo 01 em R não tem menor elemento enquanto que 01 em R tem menor elemento Entretanto é uma consequência da axioma da escolha que todo conjunto não vazio admite uma relação de ordem que o bemordena Embora o axioma afirme que R pode ser bem ordenado não sabemos como fazêlo Neste texto por Princípio da Boa Ordem ou a forma curta PBO referemse exclusivamente ao enunciado acima a respeito da ordem usual nos naturais e as vezes por abuso a versão para inteiros como acima 31 Princípios de indução Há várias formulações equivalentes para o Princípio de Indução Finita PIF e todos podem ser provados a partir do PBO TEOREMA 87 PRINCÍPIO DA INDUÇÃO FINITA PIF Seja X N Se 1 0 X e 2 para todo k N se k X então k 1 X então X N DEMONSTRAÇÃO A prova é por contradição Seja X um subconjunto dos naturais que satisfaz as hipóteses 1 e 2 do teorema Suponha que a conclusão do teorema seja falsa ou seja que X N Então A N X é não vazio e pelo PBO tomamos m minA De 0 X temos m 1 portanto m 1 é natural Pela minimalidade de m temos que m 1 A portanto m 1 X Porém se m 1 X então m X pela hipótese 2 Portanto m X Agora e m A N X e m X é uma contradição Portanto X N A forma mais usual é enunciada da seguinte forma COROLÁRIO 88 PRINCÍPIO DA INDUÇÃO FINITA PIF Seja Pn um predicado de números naturais Se 1 P0 é verdadeiro e 2 para todo k 0 se Pk é verdadeiro então Pk 1 é verdadeiro 48 então Pn é verdadeiro para todo natural n DEMONSTRAÇÃO Seja P um predicado e suponha que vale as hipóteses 1 e 2 dadas Faça X k N Pk e temos da hipótese 1 que 0 X e da hipótese 2 se k X então k 1 X Assim estamos nas hipóteses do teorema 87 e podemos concluir que X N ou seja Pn é verdadeiro para todo natural n TEOREMA 89 PRINCÍPIO DA INDUÇÃO FINITA COMPLETO PIFC Seja X N Se 1 0 X 2 para todo k N se 01k X então k 1 X então X N DEMONSTRAÇÃO Seja X N um conjunto que satisfaz as hipóteses do 1 e 2 do teorema 89 Nesse caso as hipóteses do teorema 87 ficam satisfeitas donde concluímos que X N Antes de prosseguirmos vejamos como podemos deduzir esse teorema do PBO A prova é por contradição seja S NX Podemos tomar k N tal que k 1 seja o menor elemento de S com respeito a ordem dos naturais Então x k 1 x X para todo x N o que implica k 1 X uma contradição pois k 1 S O seguinte enunciado é a forma mais diretamente usada nas demonstrações por indução COROLÁRIO 90 PRINCÍPIO DA INDUÇÃO FINITA COMPLETO PIFC Seja Pn um predicado de números naturais Se 1 P0 é verdadeiro e 2 para todo k 0 P0 e P1 e e Pk implica Pk 1 então Pn é verdadeiro para todo natural n 0 DEMONSTRAÇÃO Exercício 311 Indução em subconjuntos dos inteiros limitados inferiormente Como corolário do PIF ou mais diretamente da consequência do PBO para subconjuntos de inteiros limitados inferiormente temos o seguinte resultado que estende o PIF para subconjuntos dos inteiros limitados inferiormente TEOREMA 91 PRINCÍPIO DA INDUÇÃO FINITA GENERALIZADO PIFG Sejam Pn um predicado de números inteiros e n0 Z Se 1 Pn0 é verdadeiro e 2 para todo z n0 se Pz é verdadeiro então Pz 1 é verdadeiro então Pn é verdadeiro para todo inteiro n n0 DEMONSTRAÇÃO Sejam P e n0 como enunciado no teorema A prova é por contradição Se existe z n0 inteiro que não satisfaz P então o conjunto A z Z z n0 e nãoPz é não vazio e limitado inferiormente portanto tem m minA Pela hipótese 1 m n0 1 logo m 1 n0 e Pm 1 é verdadeiro por causa da minimalidade de m Pela hipótese 2 Pm é verdadeiro e temos uma contradição Portanto Pn é verdadeiro para todo inteiro n n0 A versão completa também vale para subconjuntos de inteiros limitados inferiormente TEOREMA 92 PRINCÍPIO DA INDUÇÃO FINITA COMPLETO GENERALIZADO PIFCG Sejam Pn um predicado de números inteiros e n0 Z Se 1 Pn0 é verdadeiro e 2 para todo inteiro z n0 se Pn0 e Pn0 1 e e Pz é verdadeiro então Pz 1 é verdadeiro então Pn é verdadeiro para todo inteiro n n0 Para fins didáticos vamos demonstrar esse teorema transformando o problema em Z num problema equivalente em N DEMONSTRAÇÃO Sejam P e n0 como no enunciado do teorema Defina o conjunto X m N Pm n0 N Então 0 X pela condição 1 da hipótese do enunciado do teorema Dado n N suponha que 01n X Então Pn0 e P1 n0 e e Pn n0 é verdadeiro e pela hipótese 2 do enunciado do teorema temos que e Pn 1 n0 é verdadeiro isto é n 1 X Pelo PIFc teorema 89 X N ou seja Pm n0 para todo natural m Portanto Pn é verdadeiro para todo inteiro n n0 49 312 Mais duas variantes Em alguma situações podem ser úteis as seguintes variantes do PIF Exercício 93 PIF passo k Seja Pn um predicado a respeito de n N Se 1 P0 e P1 e e Pk 1 é verdadeiro e 2 para todo n N Pn e Pn 1 e e Pn k 1 verdadeiro implica Pn k verdadeiro então Pn para todo n N TEOREMA 94 INDUÇÃO PRA FRENTEPRA TRÁS Seja ai uma sequência crescente de números naturais Seja Pn um predicado a respeito dos números naturais Se 1 Pai é verdadeiro para todo índice i N e 2 para todo natural k se Pk 1 é verdadeiro então Pk é verdadeiro então Pn é verdadeiro para todo natural n DEMONSTRAÇÃO Sejam ai e Pn como no enunciado e que as hipóteses sejam verdadeiras A prova é por contradição supo nha que exista k tal que Pk seja falso Existe um natural ℓ tal que aℓ1 k aℓ justifique Definimos o conjunto A n N aℓ1 n aℓ e nãoPn que é não vazio por hipótese Pelo exercício 16 página 44 po demos tomar m maxA Assim temos que Pm1 é verdadeiro e pela hipótese 2 do enunciado do teorema Pm é verdadeiro uma contradição Portanto Pn é verdadeiro para todo natural n Exercício 95 Demonstre o teorema 94 usando o PIF Dica para provar Pk no passo defina Qn para n 01aℓ aℓ1 pondo Qn Paℓ n onde aℓ é como na demonstração acima prove Qk Paℓ k usando indução em n 313 Equivalência entre os princípios Acima deduzimos PIFc de PIF e PIF de PBO Todos esses princípios são de fato teoremas equivalentes Para provar a equivalência vamos provar que PBO segue de PIFc e teremos as implicações PBO PIF PIFc PBO Demonstração de PIFc PBO Seja A N não vazio Vamos provar que A tem um menor elemento A prova é por contradição suponha que A não tem menor elemento Definimos o conjunto X como o complemento de A X n N n A e vamos provar que X satisfaz as hipóteses de PIFc i 0 X e ii para todo k N se 0k X então k 1 X Se 0 X então 0 A portanto 0 é o menor elemento de A contradição Com isso provamos que 0 X Seja k 0 arbitrário e suponha 0k X Se k 1 X então k 1 A portanto k 1 é o menor elemento de A já que 0k X contradição Portanto k 1 X e com k é arbitrário provamos para todo k N 0k X implica k 1 X Com i e ii podemos usar o PIFc para concluir que X N ou seja A uma contradição Portanto A tem menor elemento Exercício 96 Na página 40 provamos a partir do PBO o Princípio da descida infinita de Fermat PDI não existe uma sequência decrescente de números naturais De fato o PDI é equivalente ao PBO e portanto aos PIF Deduza o PBO do PDI 32 Demonstrações por indução Indução matemática também é uma técnica de prova para sentenças da forma para todo n a Pn Já vimos alguns exemplos nas demonstrações dos teoremas 89 e 92 da implicação PIFc PBO Numa prova por indução verificamos a validade das duas hipóteses do princípio de indução finita e se sendo verdadeiras concluímos que para todo n a Pn Na verificação das hipóteses provamos Pa isto é verificamos que a instanciação da variável com a resulta numa sentença verdadeira a isso chamamos base da indução e provamos a segunda hipótese que é uma condicional a isso chamamos passo da indução O passo é provado usando as estratégias que já aprendemos para isso no caso direto fixamos um k arbitrário supomos Pk verdadeiro e provamos que Pk 1 é verdadeiro 50 Exemplos 97 Para todo n N 0 1 n nn 12 Vamos provar usando indução em n Base Para n 0 a igualdade afirmada se verifica 0 0 12 Passo Seja k 0 um natural arbitrário e suponha que 0 1 k kk 12 Precisamos provar que 0 1 k k 1 k 1k 22 Por definição Fk2 Fk1 Fk pela hipótese Fk1 Fk 15 1 52k 1 1 52k 1 Seja Pn a sentença para todo n natural 6n 0 Vamos provar Pn por indução em n Para n 0 a sentença P0 é claramente verdadeira Então 61 1 6 6 1 0 0 0 Portanto 66 1 0 ou seja Pn 1 vale para todo n 1 x1 x2 x2k 2 x2k1 2xk2 2xk1 e 3 x1 x2 xk 2k1 2xk1 logo se só se x1 x2 xk xk1 x2k1 Pelo PIF a desigualdade MAMG vale para qualquer lista com 2k números reais positivos para todo k 1 Para concluir usamos indução de novo agora a versão para trás Tomando ai 2 i para o teorema 94 a demonstração acima prova a base da indução Para o passo de indução tomamos j 2 arbitrário e assumimos que MAMG vale para qualquer lista com j números positivos Vamos provar que vale para x1 x2 xj1 Pela hipótese indutiva x1 x2 xj1 Gx1 xj1 j x1 x2 xj1 rescrevendo lado esquerdo x1 x2 xj1 Gx1 xj1 j j 1Ax1 xj1 Gx1 xj1 j e reescrevendo lado direito x1 x2 xj1 Gx1 xj1 j Gx1 xj1 e a desigualdade inicial fica j 1Ax1 x2 xj1 Gx1 xj1 jGx1 xj1 então concluímos que Ax1 x2 xj1 Gx1 xj1 Falta verificar a condição de igualdade que deixamos como exercício Portanto pelo teorema 94 indução pra frentepra trás concluímos que MAMG vale para qualquer lista com n 1 números reais positivos Exercício 104 Prove que dentre todos os triângulos de mesmo perímetro o equilátero é o de maior área Exercício 105 Considere a sequência an definida por a0 1 e an 1 1n n Prove usando indução que essa sequência é crescente Prove usando indução que MAMG essa sequência é crescente Podemos definir recursivamente o produto cartesiano de mais de dois conjuntos De um modo geral seja A1 A2 An são conjuntos não vazios Definimos a1 a2 an a1 a2 an se n 1 e a1 a2 an 1 se n 1 então n i1 Ai a1 se n 1 n i1 Ai An se n 1 No caso em que os conjuntos A1 A2 An são iguais a A denotamos por An o produto cartesiano n i1 Ai Funções definidas recursivamente Definimos qualquer função f N A ou uma sequência an de elementos de A modo que an fn recursivamente em duas etapas na base especificamos o valor da função f em 0 k e no passo damos uma regra para encontrar o valor de fn n k em função de seus valores no inteiros menores fn 1 fn 2 fn k em função de n Por exemplo f0 0 fn 1 fn gn em que g é uma função qualquer definida em N Tal definição é chamada de definição recursiva Uma equação de recorrência é uma expressão que define uma sequência recursiva As funções definidas recursivamente estão bem definidas se dada qualquer n podemos usar as duas partes da definição para encontrar o valor da função no ponto de forma inequívoca Exemplo 106 fatorial O fatorial de qualquer número natural fixo n definido por f0 1 e fn n 1 n 1 n Nesse caso fn é denotado por n Nota que podemos usar o PIF para verificar que f está bem definida Chame X o conjunto dos n para os quais sabemos calcular f Certamente e 0 X por outro lado fn 1 n 1 fn concluímos que para todo n se n X então n 1 X Exemplo 107 A sequência de Fibonacci Fn é bem definida por F0 0 F1 1 e Fn Fn1 Fn Nesse caso o PIF passo 2 exercício 93 página 50 garante que F está bem definida pois sabemos calcularlhe em 1 e 1 se calculála em k em k 1 também sabemos em k 2 para todo k Exemplo 108 juro composto Se começamos uma poupança com um capital de C unidades monetárias após n meses o montante poupado supondo i e 01 fixo como a taxa de juros mensal é Mn1 Mn iMn Se poupamos Dn unidades monetárias no mês n D0 C o aplicamos nessa poupança M0 C Mn1 1 iMn Dn1 Exemplo 109 progressões aritmética e geométrica Uma progressão aritmética que começa em a R e tem razão r R é uma sequência an tal que a0 a an1 an r para todo n N Uma progressão geométrica que começa em a R e tem razão r R é uma sequência an tal que a0 a an1 an r para todo n N Exemplo 110 O método de NewtonRaphson para achar zero de função real quando aplicado a x2 a computa aproximadamente a raiz quadrada de a A partir de x0 1 podemos computar 2 usando xn1 12 xn 2xn Exemplo 111 mapa logístico O mapa logístico é uma equação de recorrência frequentemente dada como exemplo de comportamento complexo e crítico podendo sugerir a variadas equações não lineares muito simples xn1 r xn1 xn onde r é uma constante e x0 um valor inicial dado Essa equação foi popularizada em um artigo de 1976 do biólogo Robert May em parte como um modelo demográfico em tempo discreto Nesse estudoestudase o comportamento assintótico de xn variando o parâmetro r e 01 o período dos órbitas são descritos pelo seu elegante diagrama de bifurcações Uma função φ satisfaz uma recorrência para an se φn an Do exemplo 101 temos que φx 15 152 x 152 x satisfaz a recorrência que define os números de Fibonacci Uma vantagem dessa expressão é que torna em princípio mais fácil o cálculo de número de Fibonacci grandes com F2019 por exemplo Essa função φ é chamada de solução da equação de recorrência Uma solução para uma relação de recorrência é uma forma fechada da função que satisfaz Uma forma fechada é uma expressão matemática que pode ser avaliada com um número pequeno de operações em geral as operações aritméticas usuais e as funções bem conhecidas como por exemplo nésima raiz exponencial logaritmo funções trigonométricas e funções hiperbólicas inversas Uma recorrência sempre tem uma função que a satisfaz aquela que a recorrência define porém pode não ter uma solução uma forma fechada Veremos na seção 53 uma técnica que permite encontrar soluções de alguns tipos de equações de recorrência Em todo caso definida essa função é inducão verificar se uma expressão é solução de uma recorrência Vamos provar por indução que a sequência an nr a para todo n é uma solução para a recorrência da progressão aritmética que começa em a em razão r De fato a base n 0 é verdadeira a0 0 r a a definição Seja k um natural arbitrário e suponha que ak k r a Vamos provar que ak1 k 1 r a Temos ak1 ak r por definição ak k r a por hipótese Portanto ak1 k 1 r a Portanto pelo PIF para todo n an nr a Exercício 112 Use o PIF para provar que uma função F definida pela especificação F0 e uma regra para obter Fn 1 a partir de Fn está bem definida Exercício 113 Use o PIF para provar que uma função F definida especificando F0 e uma regra para obter Fn 1 dos valores Fk para k 0 1 2 n não está bem definida Tal conjunto I do exemplo 114 e o subconjunto dos números naturais ímpares Para provar que todo elemento de I é ímpar suponha o contrário que existe ao menos um natural em I não ímpar Seja m o menor natural em I que não é ímpar pois existe pelo PBO Certamente a b portanto a b 2 para algum b I Pela minimalidade de m e deduzimos que b é ímpar portanto b 2 é ímpar uma contradição Agora vamos provar que todo natural ímpar pertence a I Por indução que 2n 1 I para todo natural n Se n 0 então 2n 1 1 I Seja k um natural arbitrário e assuma que 2k 1 I e por definição 2k 1 2 I logo 2k 1 1 I Pelo PIM temos 2n 1 I para todo n Exercício 115 Para o conjunto I do exemplo 114 prove que qualquer A I que satisfaça as duas regras de definição A I Prove também que a interseção de todos os conjuntos que satisfaçam as duas regras de definição A I Figura 32 a Ladrilho em L b Graude quadrados 2² x 2² Prove usando indução as seguintes afirmações para os números de Fibonacci a F₀² Fₙ² FₙFₙ₁ b F₀ F₂n F₂ₙ₁ c Fₙ₁ Fₙ F²ₙ 1ⁿ₁ para todo n 1 d Fₙ Fₙ₁ F²ₙ 1ⁿ para todo n 1 e Fₙ é divisível por 5 f Fₙ é par g F₁ F₃ F₂ₙ₁ F₂ₙ Prove usando indução que a sequência 1 1n é crescente Considere S N definido recursivamente por 0 S para todo n se n S então 2n 1 S De uma definição não recursiva para S e prove que o conjunto da sua definição é de fato o mesmo conjunto que o definido recursivamente Suponha que um casal de urubus começa a criar crias com dois anos de idade e produz 6 criações três casas de urubuzinhos a cada ano Suponha que um lixão começou a ser frequentado por 1 casal recémnascido e que nenhum urubu é acrescentado ou eliminado do lixão Escreva uma definição recursiva para o número de urubus que existem no ano n Qual é o erro da seguinte dedução por indução para a sentença Para qualquer conjunto de n retas no plano se não há quaisquer duas retas paralelas então todas se encontram em um ponto Para n 1 para n 2 a sentença é claramente verdadeira Seja k 2 um inteiro arbitrário e assuma que Pk é verdadeira Considere um conjunto qualquer k 1 retas no plano dadas por r₁ r₂ rₖ₁ e em quaisquer duas não paralelas Pela hipótese da indução r₁ r₂ rₖ se encontram em um ponto Como r₂ e rₖ se estão nos dois conjuntos p é portanto r₁ r₂ rₖ₁ se encontram em um ponto Pelo PIF a sentença enunciada vale para todo n 1 2 para todo s se a s z e s S então existe u s tal que su S 3 para todo s se a s z e as S então s S Então S az Vejamos como utilizar o teorema acima para provar Toda função contínua f az R é limitada DEMONSTRAÇÃO Seja f uma função contínua definida em az Definimos S s az f as R é limitada Claramente a S portanto 1 do teorema fica satisfeito Seja s S tal que f é limitada em as Como f é contínua existe δ 0 tal que para todo y s δs δ vale que f y f s1 logo f é limitada em ss δ Portanto 2 do teorema fica satisfeito para u s δ Agora seja s az tal que as S De f contínua em s temos f limitada em s δs para algum 0 δ s a e como a s δ s concluímos que f é limitada em as δ portanto limitada em as Assim 3 do teorema fica satisfeito logo S az 60 Capítulo 4 Relações Vamos relembrar que uma relação com domínio A e contradomínio B ambos não vazio é um subconjunto de um produto cartesiano A B Se A B escrevemos A2 para A B e dizemos que R A2 é uma relação sobre A ou em A Usualmente R A B e ab R escrevemos a R b Por exemplo é uma relação sobre N e ao invés de escrevermos x y escrevemos x y como em 3 4 ao invés de 34 Ademais no que se refere a notação é mais comum usarmos símbolos como em vez de R S ou qualquer letra do alfabeto Propriedades de relações Uma relação sobre um conjunto A não vazio pode ou não ter uma ou mais das seguintes propriedades reflexiva para todo a A a a irreflexiva para todo a A a a simétrica para todo a A para todo b A se a b então b a antissimétrica para todo a A para todo b A se a b e b a então b a transitiva para todo a A para todo b A para todo c A se a b e b c então a c Uma relação pode ser simétrica e antissimétrica ao mesmo tempo como 11 sobre 1 ou pode não ser nem simétrica nem antissimétrica como 12 sobre 12 Uma relação pode não ser reflexiva e nem irreflexiva porém uma relação não pode ser ao mesmo tempo reflexiva e irreflexiva sobre A dê um exemplo Por exemplo as relações sobre A 1234 1 R1 1112212233344144 é reflexiva 2 R2 111221 é simétrica 3 R3 1112212233411444 é reflexiva e simétrica 4 R4 213132414243 é irreflexiva antissimétrica e transitiva 5 R5 11121314222324333444 é reflexiva antissimétrica e transitiva 6 R6 34 é irreflexiva antissimétrica e transitiva Exercício 117 A seguir considere A 1234 e B 123 e classifique quanto as propriedades acima as relações 1 R1 12211331 2 R2 112233 3 R3 11223323 4 R4 112333 5 R5 122331 61 41 Relação de equivalência Relação de equivalência é um tipo de relação ubíqua em matemática usada por exemplo na definição de cardinalidade na construção dos números inteiros e dos racionais a partir dos números naturais na definição de objetos geométricos como a garrafa de Klein e a fita de Möbius Dizendo de modo bastante ingênuo as relações de equivalência permitem construções de novos conjuntos a partir de um conjunto dado onde tratamos elementos diferentes do conjunto dado como iguais no novo conjunto Por exemplo em certas situações pode se interessante estudar a circunferência como o conjunto dos pontos obtidos de um intervalo quando identifica mos tratamos como iguais os seus extremos estudar o cilindro como o conjunto dos pontos obtidos de um retângulo quando identificamos tratamos como iguais dois de seus lados paralelos oi ainda estudar o toro como o conjunto dos pontos obtidos de um retângulo quando identificamos tratamos como iguais seus lados paralelos Definição 118 Uma relação de equivalência em um conjunto A é uma relação que satisfaz as propriedades reflexiva simétrica e transitiva Por exemplo 1 é uma relação de equivalência em N 2 não é uma relação de equivalência em N 3 Se T e S são triângulos no plano euclideano e T S se os triângulos são semelhantes então é relação de equivalência sobre o conjunto de todos os triângulos no plano 4 Semelhança de matriz é uma relação de equivalência sobre o conjuntos de todas as matrizes quadradas de ordem n de números reais 5 mod 3 é a relação dada pelos pares de inteiros que deixam o mesmo resto quando divididos por 3 assim 13 22 mod 3 e 7 13 mod 3 Essa relação é de equivalência 6 não é relação de equivalência sobre o conjunto das partes de A Em R a relação x y se e só se x y 1 é reflexiva simétrica e transitiva 62 Definição 119 Seja uma relação de equivalência qualquer sobre o conjunto A Ø e x A a classe de equivalência de x é o subconjunto x b A b x de formado por todos os elementos de A equivalentes a x O elemento dentro dos colchetes nesse caso x é chamado de representante da classe Para causa da transitividade da relação qualquer elemento da classe pode ser seu representante pois ambos definem a mesma classe de equivalência PROPOSIÇÃO 120 Seja uma relação de equivalência sobre um conjunto A Para qualquer a b A são equivalentes as sentenças 1 a b 2 a b 3 a b Ø DEMONSTRAÇÃO Vamos provar a equivalência entre os itens 1 e 2 Sejam a b A com b a Para todo c a vale c a portanto c b pela transitividade logo c b Para argumento análogo se c b Assim provamos a b se e só se a b 41 Exemplo 121 Em Z definimos a relação congruência módulo 3 onde para quaisquer inteiros a b deem o mesmo resto quando divididos por 3 Essa relação é de equivalência e pela proposição acima e o teorema da divisão euclidiana 03 3k k Z 13 3k 1 k Z 23 3k 2 k Z Qualquer múltiplo de três define a mesma classe de equivalência do 0 qualquer inteiro que deixa resto 1 quando dividido por 3 define a mesma classe de equivalência do 1 e qualquer inteiro que deixa resto 2 quando dividido por 3 define a mesma classe de equivalência do 2 Exemplo 122 Tomemos o intervalo I 0 1 da reta real Definimos uma relação de equivalência formada pelos pares x x para todo x I mais os pares 0 1 e 1 0 As classes de equivalência dessa relação são x x para x 0 que é a mesma que 1 Exemplo 123 No produto I I definimos uma relação de equivalência formada pelos pares x y x y para todo x y I mais os pares 0 y 1 y para todo y I As classe são 0 y 1 y para cada y I mais os unitários x y para x 0 1 e y I Notemos que no caso do exemplo 121 acima 03 13 23 Z isso de fato é uma propriedade das classes de uma relação de equivalência Para todo A Ø e todo a A seja A K A é relação de equivalência então da propriedade reflexiva segue que a a de modo que A eAa Por outro lado a A por definição logo eAa A Portanto A eAa 42 DEMONSTRAÇÃO Sejam A como dados no enunciado Da proposição 120 e equação 42 A é uma partição de A Agora vamos considerar uma partição de A e definir a relação por a x y se e só se x e y estão numa mesma parte da partição A relação é reflexiva pois para todo a A existe um B A tal que a b B e então b B A relação é transitiva pois para todos a b c A existe um B A tal que a B e B existe um C A tal que b c C então temos B C pelo item 2 da definição de partição Ainda se X é um conjunto parte da partição então X Y Ø logo podemos tomar x X Por definição y X e só se y r x Ademais y r x se e só se y x Assim as partes da partição de A são as classes de equivalência da relação por Se é uma relação de equivalência sobre A então chamamos de conjunto quociente de A pela relação de equivalência o conjunto das classes de equivalência da relação A a a A Exemplo 125 No caso da relação congruência módulo 3 o conjunto quociente Z3 é o conjunto 03 13 23 e Z3 é usualmente denotado por Z3 Exemplo 126 No caso do exemplo 122 o conjunto quociente é um conjunto de pontos topologicamente idêntico a uma circunferência Assim da mesma forma o conjunto 123 o conjunto quociente é um conjunto topologicamente idêntico a um cilindro Exemplo 127 Para todo R todo Rℓ e todo Rₓ seguem relações de equivalência sobre A 1 Sejam A um conjunto não vazio A o conjunto das relações de equivalência sobre A R RℰA 2 Sejam A um conjunto não vazio A o conjunto das relações de equivalência sobre A R RℰA Complemento Construção dos Inteiros Intuitivamente digamos que queremos construir um conjunto de números ordem n k faça sentido quaisquer que sejam os naturais n k por exemplo 4 11 Façamos 7 7 4 11 3 10 5 12 Notemos que se a b n m então a m b n e fazemos todas essas representações do 7 equivalentes temos uma relação de equivalência Formalmente considere a relação Z N definida por a bZn m se e só se a m b n Z que é uma relação de equivalência Para cada a b a classe de equivalência de a b é o conjunto a b n m N N a bZn m Por exemplo 1 2 0 1 1 2 2 3 3 4 5 2 3 0 4 1 5 2 6 3 2 2 4 1 Notemos que 1 2 3 2 0 1 3 0 Definimos p q como a classe de equivalência p q a n b m Definese p q p q e definimos p q se a p N para quaisquer inteiros p e q enquanto que quaisquer dois números inteiros x e y são comparáveis pela relação isto é vale que x y ou y x Seja A um conjunto não vazio e uma relação de ordem em A Os elementos a b A são ditos comparáveis por se e só se vale que x y ou y x Caso contrário são ditos incomparáveis Definição 130 Escrevemos x y se e só se x y e x y O é uma relação sobre o mesmo conjunto que chamada de ordem estrita definida por O par A é a ordem estrita associada a ordem parcial A De modo geral uma relação sobre A é uma ordem estrita se é uma relação irreflexiva e transitiva Exercício 131 Seja uma ordem estrita sobre A Prove que é assimétrica ou seja para quaisquer a b A a a e b não b a Diagrama de Hasse Quando x y e não existe z A tal que x z y então dizemos que y cobre x Essa relação cobre é um subconjunto da relação Usamos esta abreviação para em alguns casos montar um diagrama que representa a ordem parcial conhecido como diagrama de Hasse que é bastante útil para ilustrar propriedades de uma ordem parcial Representamos cada elemento y como um ponto no plano vértice e desenhamos um segmento ou curva aresta que vai para cima de x para y sempre que y cobre x e y x A relação de ordem é indicada tanto pelas arestas quanto pelo posicionamento relativo dos vértices As ordens são desenhadas de baixo para cima se um elemento x é menor que y então existe um caminho de x para y que é direcionado para cima Pode ser neste desenho que as arestas conectando os elementos se cruzem fora dos vértices mas uma ordem parcial A figura 41 abaixo exibe um diagrama de Hasse do ordenal parcial 123 Na figura 42 temos um diagrama da Hasse dos divisores de 60 com a ordem Elementos máximo mínimo maximal e minimal Alguns elementos quando existem desempenham um papel especial numa ordem parcial A Temos que x A é minimal se e só se para todo y A y x implica y x mínimo se e só se para todo y A x y maximal se e só se para todo y A x y implica y x máximo se e só se para todo y A y x Há ordens parciais onde não ocorrem nenhum desses casos como por exemplo em Z Também um conjunto parci almente ordenado pode ter vários elementos minimais e vários elementos maximais Por exemplo o conjunto formado por todos os subconjuntos de A com k elementos para algum 0 k n parcialmente ordenados por é formado por elementos incomparáveis entre si todos os elementos são maximais e todos são minimais não há máximo e não há mínimo No conjunto dos divisores próprios de 60 em N com a ordem de divisibilidade que tem uma representação dada pelo diagrama da figura 43 percebemos que essa ordem parcial não tem máximo nem mínimo Os elementos 122030 são elementos 2 3 5 4 6 10 15 12 20 30 Figura 43 diagrama de Hasse dos divisores próprios de 60 maximais 235 são minimais Se consideramos todos os divisores figura 42 notamos que 1 é mínimo e 60 é máximo Exemplo 132 Dado um conjunto A com n elementos tomamos A A isto é os subconjuntos próprios de A parcial mente ordenados por pela relação de inclusão Nesse caso há n elementos maximais e n minimais justifique essa afirmação Quando A é um conjunto de conjuntos e a relação de ordem é a inclusão um elemento minimal de A é um conjunto que não contém propriamente nenhum outro elemento de A um elemento maximal de A é um conjunto que não está contido propriamente nenhum outro elemento de A Por exemplo se A 21213124345 então 124 não é minimal pois contém propriamente 12 A São os elementos minimais 2 13 e 345 O elemento 2 não é maximal nem 12 Os elementos maximais do conjunto A são 13 124 e 345 Exemplo 133 Para o conjunto A 123456 munido da relação de ordem dada por 132314243456112233445566 o número 2 A é um elemento minimal de pois não existe nenhum par a2 a 2 na relação Os elementos minimais A são 1 2 e 5 Quais são os maximais Há máximo Há mínimo A figura 44 é uma representação dessa ordem parcial 1 2 5 6 3 4 Figura 44 diagrama de Hasse do exemplo 133 67 Exemplo 134 Tomemos N 01 como a relação de divisibilidade denotada O número 21 não é minimal pois por exemplo 321 O número 17 é minimal pois não existe z tal que q17 a única possibilidade seria o 1 que não está no conjunto Note que os elementos minimais de N 01 são os números primos Já em N 00 o 1 é o único minimal que também é mínimo PROPOSIÇÃO 135 Numa ordem parcial se existe mínimo então ele é único e se existe máximo ele também é único DEMONSTRAÇÃO Seja A uma ordem parcial Suponha que x₁ e x₂ sejam mínimos dessa ordem Como x₁ é mínimo x₁ x₂ analogamente x₂ x₁ portanto x₁ x₂ pela propriedade antissimétrica A demonstração para máximo é análoga Exemplo 136 Considere o conjunto S³N de todos os subconjuntos de N com no máximo três elementos e ordenados por inclusão O infinito mínimo dessa ordem parcial é Todos os subconjuntos de 3 elementos são maximas pois não há subconjuntos com 4 elementos do modo que por exemplo nenhum elemento de S³N contém 12 nem 123 Como consequência de haver dois elementos maximais inferiores não há máximo nessa ordem parcial Cadeias Numa ordem parcial podem ocorrer subconjuntos nos quais quaisquer dois elementos são comparáveis É o caso por exemplo de 12360 na ordem dos divisores de 60 Outros cuja quaisquer dois elementos são incomparáveis como 456 na ordem dos divisores de 60 Nesse caso 0 1 2 2 Uma propriedade muito interessante de uma boa ordem é que implica um princípio indutivo Um princípio de indução completa para uma boa ordem é como segue TEOREMA 140 PRINCÍPIO DE INDUÇÃO COMPLETA PARA BOA ORDEM Seja A uma boa ordem e P um predicado sobre A Suponha que para todo y A Py é verdadeira sempre que Px seja verdadeira para todo x y Então Px é verdadeira para todo x A De modo sinético em símbolos a sentença x A Pa é consequência lógica de y A x Ax y Px Py DEMONSTRAÇÃO A prova é por contradição Sejam A uma boa ordem e P um predicado sobre A Assumamos que 43 é verdadeiro ie para todo y A é verdadeiro x Ax y Px Py e suponhamos que existe a A tal que Pa não é verdadeiro Assim não é vazio o conjunto S a A não Pa Façamos y minS o menor elemento de S com respeito a ordem que existe pois o conjunto é bem ordenado De 44 verdadeiro e Py segue que é verdadeira a sentença x A x y Px portanto por 44 Py é verdadeiro o que é uma contradição Usamos este princípio para todo elemento de um conjunto bem ordenado tem uma dada propriedade Para isso verificamos que um elemento do conjunto S deve verificar que Py é verdadeiro a propriedade vale no menor elemento da boa ordem Usualmente chamamos essa tarefa de base da indução Vamos a um exemplo O conjunto N N como um ordenal lexicográfico isto é ex y a b se e só se a e y b Agora defina a função f N N N por f00 0 e nos outros casos fm n fm 1n 1 se n 0 e m 0 fmn 1 n se n 0 A relação bem ordena o conjunto N N Vamos provar por indução que fmn m nn 12 Começamos provando x N Nx y Px Py para todo y N N em que o predicado Py é igualdade fmn m nn 12 quando y mn Para y 00 temos Py verdadeira pela definição f00 0 e pela fórmula f00 0 portanto 46 vale trivialmente Tome y ab ab ou ab Pab de modo que se b 0 fab fab 1 b a 1 bb 12 1 a b 12 e em ambos os casos Pab é verdadeiro O seguinte resultado é equivalente a vários teoremas importantes em combinatória como o teorema de Hall e o teorema de BirkhoffVon Neumann também é uma generalização do teorema de ErdősSzekeres sobre subsequências monótonas Defina a relação R sobre Z Z pela regra a bRc d a c ou b d A relação é uma ordem parcial sobre Z Z 20 Uma linearização de um conjunto parcialmente ordenado e finito P é uma enumeração dos elementos do conjunto x1x2xn de modo que i j implique xi x j ou xi e x j incomparáveis Seja S3 o conjunto das sequências binárias de 3 bits com a ordem produto ou seja a0a1a2 b0b1b2 see somente se a0 b0 e a1 b1 e a2 b2 a Desenhe um diagrama de Hasse da ordem parcial posicionando os elementos de S3 como os vértices de um cubo projetado contra o plano b Verifique que a seguinte enumeração é de fato uma linearização 000001010100011101110111 c Prove que temse exatamente 6 formas de reordenar os elementos de S3 de modo à respeitar a ordem de S3 ou seja bijeções monótonas x y Fx Fy Dica Veja que estas devem respeitar a geometria do cubo d Porem o números de linearizações possíveis é bem maior Verifique que temse 48 linearizações Dica 48 33322 Obs ordenação topológica é outro nome para linearização usado na computação 21 Prove que todo subconjunto de um conjunto bem ordenado é bem ordenado 22 Prove que são boas ordens as ordens parciais dos exemplos 138 e 139 e a ordem lexicográfica em NN 23 Sejam A e B duas ordens parciais Tome em A B a ordem lexicográfica isto é x y ab se e só se x a ou x a e y b e x y ab se e só se x a e y b Prove que se A e B são boa ordem então A B é boa ordem 24 Defina a relação sobre o conjunto Z dos inteiros negativos por a b se e somente se a b a Prove que é uma boa ordem sobre Z b Defina f Z Z por f 1 1 e f n f n 1n Calcule f 2 f 3 f 4 Prove que f está bem definida Use o princípio de Indução para conjuntos bemordenados para provar que f n nn1 2 72 25 A relação de Stifel também conhecida como regra de Pascal é a parte recursiva da definição da função C NN N dada por Cnk 0 se k n 1 se k n ou k 0 Cn 1k 1Cn 1k se 0 k n Prove que C está bem definida 26 Se uma função crescente f como definida no exercício 17 página 71 é uma bijeção então chamamos f de isomorfismo e as ordens totais A e B são ditas isomorfas Prove que se duas boa ordens são isomorfas então há um único isomorfismo entre elas 27 Seja A uma boa ordem e B A Prove que se f A B é um isomorfismo então x f x para todo x A 28 Sejam A uma ordem total Um subconjunto I A é chamado de segmento inicial se para algum x A I y A y x o qual é um segmento inicial próprio caso I A Prove que uma boa ordem não é isomorfa a um segmento inicial próprio dela 29 Sejam A e B boas ordens Prove que vale uma e só uma das seguintes afirmações a A é isomorfa a um segmento inicial próprio de B b B é isomorfa a um segmento inicial próprio de A c A e B são isomorfas 30 Na teoria e conjuntos ZFC uma consequência do axioma da escolha é que todo conjunto admite uma boa ordenação Seja uma ordem parcial que bem ordena o R Tome x0 minR e x1 minR x0 Demonstre que não há x R tal que x0 x x1 31 Seja S uma ordem parcial sem cadeias de comprimento maior que m Prove que S pode ser coberto por no máximo m anticadeias Dica indução em m Para m 1 seja M o conjunto de todos os elementos maximais em S Então S M não tem cadeias de comprimento maior que m 1 e M é uma anticadeia Complemento Números naturais e ordinais No uso comum a palavra ordinal é um adjetivo para ordem posição como primeiro segundo terceiro e assim por diante Em teoria dos conjuntos são tipos de ordem duas boas ordens são do mesmo tipo se são isomorfas veja os exercícios 17 ao 29 O conjunto N dos ordinais finitos de Von Neumann são dados pela definição recursiva 1 N 2 se x N então x x N Com isso os números naturais são definidos na teoria dos conjuntos ZF 0 1 0 2 01 3 012 e assim por diante Note que 0 1 2 3 De fato é uma relação bem fundada em N Tomando a função sucessor Sn n n a estrutura N 0S em que 0 é constante dada pelo conjunto vazio satisfaz os axiomas de Peano 1 Todo número natural possui um único sucessor que também é um número natural 2 Existe um único número natural o 0 que não é sucessor de nenhum outro 3 Números naturais diferentes possuem sucessores diferentes 73 Se um conjunto de números naturais contém o número 0 e além disso contém o sucessor de cada um dos seus elementos então esse conjunto coincide com o conjunto dos números naturais Também é uma relação bem fundada sobre o conjunto de todas as palavras sobre um alfabeto fixo e totalmente ordenado com a ordem definida por u w para palavras u e w ser u é mais curto tem menos letras que w e no caso de empate u é lexicograficamente menor que w Nesse caso devemos ter uma relação sobre os pares x y com condição de cadeia descendente para garantir a condição de para a recursão da definição de A Exemplo 154 Vamos provar usando a indução que toda fórmula bem formada tem um quantitade par de parênteses Cada fórmula atômica tem 0 parênteses A quantidade de nós de uma árvore binária T é definida recursivamente por nT 1 se T r r 1 nE nD se T E r D e a altura de uma árvore binária T é definida recursivamente por hT 0 se T r r 1 maxhE hD se T E r D As duas árvores dos exemplos anteriores figuras 46 e 47 têm altura 2 Na figura 48 representamos uma árvore de altura 3 As folhas são 12356 A relação S T definida por S é um subárvore binária a esquerda ou a direita de T é bem fundado pela condição de cadeia descendente Por exemplo 11522 1152273644 Agora vamos provar por indução que o número de nós numa árvore binária T de altura hT é nT 2hT1 1 Se T r r então hT 1 o que satisfaz 49 Seja T E r D uma árvore binária arbitrária e assuma que 49 é verdadeira para B Por hipóteses ní 2hE 1 nD 2hD 1 logo nT 1 nE nD 1 2hE1 1 2hD1 1 2max2hE 2hD 1 mas max2hE 2hD 2maxhEhD que por 48 é 2hT 1 Pela indução neoteriana 49 vale para todo árvore binária Como não caixa do PIF e PBO temos uma estratégia de prova por contradição assumindo que não no conjunto de todas as estruturas de um certo tipo há aquelas que não têm uma determinada propriedade então o subconjunto de contraexemplo não é vazio portanto deve ter um elemento minimal A partir desse contraexemplo mínimo derivamos uma contradição Vejamos um exemplo Definimos árvore binária plena como árvore binária em que os nós internos são obrigatoriamente dos descendentes ou seja na formação da árvore ErD não podemos ter E vazio nem D vazio exceto nos casos bare ambos são vazias Proposição 158 Em qualquer árvore binária plena de n nós de folhas é um mais que o número de nós internos Demonstração Suponha que haja um contraexemplo para tal afirmação Então deve existir um contraexemplo T com iT nós internos e fT 1 folhas onde iT fT εminimal O contraexemplo T não é da forma rs porque al árvore têm 0 nós internos e 1 folha portanto T ErD com ED Pela minimalidade de T temos iE fE iD fD Assim fT fE fD iE iD 1 pois iE iD 1 iT contrariando o fato de T ser um contraexemplo Uma demonstração alternativa da proposição acima usando o PBO é como segue Suponha que haja um contraexemplo para tal afirmação O contraexemplo T não é da forma rs logo tem pelo menos uma folha f cujo pai p é um nó interno Exclua essa folha f e seu pai p da árvore promovendo o nó irmão da folha f para a posição ocupada por seu pai não imediatamente acima no diagrama Por exemplo essa operação no nó 5 da árvore da figura 48 resulta na árvore da figura 49 O resultado dessa operação é uma árvore binária plena T com uma folha e um nó interno a menos portanto iT 1 fT e portanto é um contraexemplo menor uma contradição Exercícios 1 Prove usando a condição de cadeia descendente que 4n 1 não é racional para todo n 1 inteiro 2 Sejam A e B duas ordens estritas Tome em A B a ordem lexicográfica estrita α isto é x y α a b se e só se x a ou x a e y b Prove que A e B são bem fundadas então A B é bem fundada 3 Prove que a relação binária m n N m n 1 m n N é uma relação de ordem bem fundada sobre N Rescreva o princípio de indução para ordens bem fundadas para esse caso específico É um resultado conhecido 4 Prove que a relação de ordem estrita usual sobre N é bem fundada Rescreva o princípio de indução para ordens bem fundadas para esse caso específico É um resultado conhecido 5 Prove que a relação de inclusão estrita de conjuntos é bem fundada se e só se o universo onde são tomados os subconjuntos é finito 6 Prove que os três resultados da seção 431 a saber α β em fórmulas e é uma subárvore binária própria de e tem nós são sobre árvores binárias são relações bem fundadas é a menor minimal relação transitiva que contém R chamada de fecho transitivo de R 73 Demonstre os análogos de 71 e 72 para o fecho transitivo Ainda podemos formar o conjunto de todas as relações reflexivas e transitivas que contém R tomar a interseção que resultada no fecho reflexivo e transitivo da relação R 74 Demonstre os análogos de 71 e 72 para o fecho reflexivo e transitivo 75 Seja uma relação bem fundada sobre um conjunto A Demonstre que a o fecho transitivo de é uma relação bem fundada b o fecho reflexivo e transitivo de é uma ordem parcial 8 Prove usando indução que na linguagem livre de contexto S ab aSb SS todas as palavras têm a mesma quantidade de símbolos a e b 9 Prove usando indução as seguintes propriedades da função de Ackermann A a para todo n 0 A1n n 2 b para todo n 0 A2n 2n 3 c para todo n 0 A3n 2n3 3 d para todos mn 0 Amn n Complemento Lema de Zorn e teorema da boa ordem The Axiom of Choice is obviously true the wellordering principle obviously false and who can tell about Zorns lemma Jerry Bona Para encerrar essa seção enunciaremos dois resultados bem conhecidos e importantes para por exemplo provar que todo espaço vetorial tem base o teorema de HahnBanach da análise funcional e o teorema de Tychonoff da topologia O lema de Zorn é útil quando precisamos iterar algum tipo de operação infinitamente muitas vezes de maneira rigorosa TEOREMA 159 LEMA DE ZORN Seja A um conjunto parcialmente ordenado tal que toda cadeia em A tem um limitante superior Então A tem um elemento maximal TEOREMA 160 TEOREMA DA BOA ORDEM Para todo conjunto A não vazio existe uma ordem tal que A é bemordenado O lema de Zorn e o Teorema da boaordem podem ser demonstrados na teoria ZFC de conjuntos usando o axioma da escolha De fato as três sentenças Axioma da Escolha Lema de Zorn e Teorema da Boa Ordem são equivalentes no sentido que na teoria dos conjuntos assumindo os axiomas de ZF se acrescentamos a boaordem aos axiomas então provamos escolha e Zorn e se acrescentamos Zorn então provamos escolha e boa ordem Por exemplo da boa ordem é fácil provar o axioma da escolha a função escolha é f y miny Exercício 161 Deduza do lema de Zorn o lema de Tukey6 Seja F uma família de subconjuntos do conjunto não vazio X com a propriedade de que se F F se e somente se cada subconjunto finito de F está em F Então F tem um elemento máximal 6John Wilder Tukey é matemático e cunhou o termo bit para dígito binário 80 SVEN GOLLY MASTER HYPNOTIST WORKS IN TRICKS HENCE A IS MAXIMAL Capítulo 5 Contagem 51 Princípios de contagem bijeção e cardinalidade Uma característica importante dos números naturais é que eles constituem o modelo matemático que torna possível o processo de contagem e respondem a pergunta quantos elementos tem esse conjunto Contagem é em última instância o processo de criar uma bijeção entre um conjunto que queremos contar e algum conjunto cujo tamanho já sabemos Esse tamanho de um conjunto é chamado de cardinalidade e é intuitivamente clara no caso de conjuntos finitos a cardinalidade de um conjunto finito é a quantidade de elementos no conjunto expressa por um número natural Cardinalidade é um conceito que a teoria dos conjuntos estende para qualquer conjunto Os números cardinais transfinitos descrevem os tamanhos de conjuntos infinitos e há uma sequência transfinita de números cardinais 0123nℵ0ℵ1ℵ2ℵωℵω1ℵωωℵω2ℵωωℵα Na verdade a ideia de cardinalidade tornase bastante sutil quando os conjuntos são infinitos Numa contagem geralmente não fornecemos uma bijeção explícita para calcular o tamanho de um conjunto mas nos base amos em princípios de contagem derivados dos processos de construção de conjuntos O ramo da matemática que estudadentre outro temas conjuntos construídos pela combinação de outros conjuntos é chamado de combinatória e a subárea que estuda os métodos de contagem é chamada de combinatória enumerativa Também na teoria dos conjuntos estudase extensões das ideias e técnicas da combinatória para conjuntos infinitos esse ramo da matemática é chamado de combinatória infinitária 511 Bijeções Para contar os elementos de um conjunto usamos a noção de correspondência biunívoca ou bijeção ou função bijetiva Dois conjuntos têm a mesma cardinalidade se e somente se há uma correspondência umparaum bijeção entre os elementos dos dois conjuntos Lembremos que uma função f X Y é bijetiva se e só se para todo y Y existe um único x X tal que f x y Dois conjuntos A e B têm a mesma cardinalidade e por abuso de notação1 denotamos isso por A B se e somente se existe uma bijeção f A B Lêse A como cardinalidade de A Como de uma função bijetiva f A B temos que a sua inversa f 1 B A também é bijetiva então dizer que dois conjuntos têm a mesma cardinalidade está bem definido Ademais A A pois a função identidade id A A dada por idx x para todo x é bijetiva Exercício 162 Prove que se A B e B C então A C Exemplo 163 A função f 0 01 nos reais dada por f x x x1 é bijetiva A função é injetiva pois x x 1 y y 1 yx y yx x x y e é sobrejetiva pois para todo y 01 f y 1 y y 82 Essa função f tem a seguinte interpretação gráfica veja a figura 51 no plano cartesiano Para cada x in 0infty o valor fx é dado pela intersecção com o eixo y da reta que passa por x0 e por P 11 Usando semelhança de triângulos temos frac1x1 fracfxx onde tiramos a expressão para fx Segue desse exercício que 0infty 01 Notemos que os conjuntos acima têm a mesma cardinalidade e a diferença 0infty setminus 01 não é vazia muito pelo contrário é 1infty e tem a mesma cardinalidade dos outros dois verifique A função g mathbbR o 0infty dada por x mapsto frac12x é bijetiva logo pelo exercício 162 0infty mathbbR e f circ g mathbbR o 01 é uma bijeção que certifica tal fato dada por f circ gx frac2x2x 1 Vejamos alguns comparações entre a cardinalidade de alguns conjuntos conhecidos 1 mathbbN mathbbZ uma ideia para estabelecermos uma bijeção entre esses conjuntos é olharmos para uma boa ordem de mathbbZ e tentar escrever mathbbZ como uma sequência dada pela ordenação Na boa ordenação dos inteiros dados no exemplo 139 0 1 1 2 3 ldots mathbbZ 0 o 1 o 2 o 3 o ldots Para mostrar que mathbbN mathbbZ definimos a função f mathbbZ o mathbbN dada por fz begincases 2z extse z ge 0 22z1 extse z 0 endcases Dado n in mathbbN se n é par então n 2z para algum z in mathbbZ portanto fz n senão n é ímpar n 2z 1 para algum z in mathbbZ portanto fz n Assim f é sobrejetiva Agora se fz fz então z z portanto f é bijetora 6 mathbbR2 mathbbR ou seja o plano cartesiano tem tantos pontos quantos um de seus eixos Aqui é suficiente mostrarmos que 01 mathbbR pois temos 01 imes 01 para todo x bijetiva Um ponto no quadrado 01 imes 01 deve ser mapeado por uma sequência binária infinita b0b1b2 ldots se tivermos ideia de representação continua finita 7 mathbbN mathbbN conjunto dos pares de mathbbN tem tantos elementos quanto mathbbR Vamos assumir que mathbbN 01 que 2 mathbbN 01 Que mathbbN mathbbR logo provamos que não podemos representar por uma sequência binária infinita b0b1b2 ldots em que i 1 e i é bi 1 e i é bi 1 portanto nunca existirá f mathbbN o mathbbR bijetiva tampouco f mathbbN o mathbbR bijetiva Exercício 169 Prove que a cardinalidade de qualquer conjunto A está bem definida quando A in mathbbN Corolário 170 Se A eq emptyset e conjunto f n o A g m o A são bijeições então m n Definição 171 A é finito se e só se A n para algum n in mathbbN A é infinito se e só se não é finito A relação entre cardinais no caso finito concorda com a representação conjuntista de número natural os números ordinais de von Neumann que apresentamos na página 73 0 20 emptyset 2 0 1 ldots n 0 1 ldots n1 assim por diante Assim 3 e 4 são diferentes f 0123 o 0123 injetiva a saber fn n Definição 172 Se A eq emptyset então uma bijeção f que prova a finitude é chamada de enumeração ou contagem dos elementos de A Desse modo A f0 f1 ldots fn1 Demonstração Seja A um conjunto de cardinalidade n Se n 0 então A emptyset e único subconjunto dele mesmo é 20 1 Senão n 1 então existe uma bijeção f n o A Como A f0 f1 ldots fn1 cada subconjunto B subset A corresponde a uma e só uma sequência binária b b0 b1 ldots bn1 in 01n dada por bi 1 se fi in B para cada i in n ou seja b 2A o 0 1n assim definida é bijetiva verifique de modo que 2A 01n 2n Cantor conjecturou que não há um cardinal entre aleph0 e c Por quase um século após a descoberta de Cantor de que diferentes infinitos números matemáticos atacaram o problema de descobrir se existe um conjunto A tal que mathbbN A 2mathbbN Supunhase que tal conjunto não existiria e a sentença que não existe tal A é conhecida como hipótese do contínuo Gödel nos anos 1930 provou que a negação da hipótese do contínuo não pode ser provada a partir dos axiomas ZFC Em 1964 Paul Cohen descobriu que nenhuma prova pode deduzir a hipótese do contínuo a partir dos axiomas de ZFC Tomados em conjunto os resultados de Gödel e Cohen significam que os dois lados da Teoria dos Conjuntos não se pode decidir se a hipótese do contínuo é verdadeira ou falsa nenhum conflito lógico surge a partir da afirmação ou negação da hipótese do contínuo Dizemos que a hipótese do contínuo é independente de ZFC Assumindo a hipótese do contínuo temos mathbbN 2mathbbN c De modo geral para o ordinal aleph1 2mathbbN Figura 53 dentre os 4 pontos equidistantes A B C D há 2 de mesma cor Fazendo ti t para todo i e não teorema obtemos o seguinte resultado COROLÁRIO 184 Em toda distribuição de rt 1 1 objetos em r gavetas há pelo menos l objetos numa mesma gaveta Como aplicação deste resultado vemos o seguinte que é um teorema conhecido numa disciplina combinatória conhecida como Teoria de Ramsey TEOREMA 185 PRINCÍPIO DAS GAVETAS ORDENADO Toda sequência de mn 1 números reais possui uma subsequência crescente de m 1 termos ou uma subsequência decrescente n 1 termos DEMONSTRAÇÃO Sejam a1 a2 am1 uma sequência numérica Para cada ai seja Ci o número de termos da maior subsequência crescente começando em ai Se Ci m 1 para algum i então temos uma subsequência crescente de tamanho m 1 Senão suponha Ci m para todo i e defina a função ϕ a1am1 1m ai Ci Pelo corolário 184 em toda distribuição de mn 1 objetos em m gavetas haverá alguma gaveta com pelo menos n 1 objetos digamos G aj1 aj2 ajn1 com spb j1 j2 jn1 Se para algum k vale ajk ajk1 então teremos uma sequência crescente de comprimento m começando em ajk1 por hipótese e consequentemente uma sequência crescente de tamanho s 1 começando em ajk o que dá uma contradição pois o cara de ajk é s Desse modo concluímos que aj aj2 ajn1 ie é uma subsequência decrescente com n 1 termos agora usamos que 1 x expx e obtemos PC 0 exp1r exp2r expn 1r expnn 12r TEOREMA 186 PRINCÍPIO DAS GAVETAS PROBABILÍSTICO Numa distribuição ao acaso em r gavetas de n r objetos a probabilidade com que existem pelo menos dois objetos numa mesma gaveta é maior que 1 expnn 12r O conhecido paradoxo dos aniversários é o caso n 23 e r 365 na equação acima PC 05 ou seja apenas 23 pessoas são suficientes para que duas delas façam aniversário no mesmo dia com probabilidade maior que 12 supondo os nascimentos ocorram uniformemente ao longo do ano Para 75 mil pessoas a probabilidade é maior do que 999 O paradoxo dos aniversários é contraintuitivo e é também chamado de paradoxo por causa do estranhamento causado pelo fato de que apenas 23 pessoas são necessárias para se obter 50 de probabilidade para duas pessoas nascerem no mesmo dia PG prova o PIF Agora para explorar o forte do PG vejamos que o PIF é uma consequência do PG na teoria dos conjuntos Como provamos o PG do PIF segue que tais princípios são logicamente equivalentes Seja P um predito dos números naturais e assuma i P0 é verdadeiro e ii n ℕ Pn Pn 1 é verdadeiro Vamos demonstrar que Pn vale para todo n por contradição Suponha que existe m ℕ tal que não há Pm De i temos m 1 e assim podemos definir uma função ϕ m m 1 por ϕi i se Pi i 1 se nãoPi Tal função está bem definida Pelo PG existem i j no domínio da ϕ tais que ϕi ϕj pois ϕ m m 1 não pode ser injetiva De i j ϕi ϕj e da definição da ϕ temos que ϕi i j 1 ϕj ou ϕj i 1 j ϕi No primeiro caso i j 1 vale Pj mas não vale Pi Pi 1 contrariando a hipótese de Pi Pi 1 verdadeira No segundo caso a dedução e análoga e contraria Pj Pj 1 verdadeira Com isso a hipótese assumida de haver m ℕ tal que nãoPm não pode ser verdadeia ou seja Pn vale para todo natural n 516 Demonstração do Teorema de CantorSchröderBernstein Antes de demonstrar o teorema vamos adotar a seguinte convenção notacional A X X A DEMONSTRAÇÃO Sejam A e B conjuntos tais que A B e B A e vamos mostrar que A B Seja f A B e g B A funções injetivas que existem por hipótese Vamos mostrar que existe uma bijeção h A B Definimos para todo x A FX A gB fX A gfX gfX 4 onde fX é o subconjunto de B formado pela imagem dos elementos de X Vamos mostrar que existe A0 A tal que FA0 A0 Primeiro notemos que por uma sequência qualquer Ai i 1 de subconjuntos de A temos h A B dado por hx fx se x A0 g1x caso contrário isto é x gFA0B é uma bijeção Que é sobrejetiva seja y B Se y fA0 então y fx para x A0 isto seja y fA0 logo gy Aog hgy g1gy y portanto h é sobrejetora Que é injetiva sejam x y A com x y A demonstração segue em três casos i se x A0 então hx fx fy hy ii se x A0 então hx fx e se y A0 ou seja y gFA0 então hy g1y g1gFA0 fA0 então hx g1x g1y hy Em todos os casos hx hy logo h é injetora Exercícios 1 Verifique que g ℝ 0 dada por gx 2x é bijetiva 2 Verifique que g ℚ ℕ por g p q 0 se p 0 2p3q se p 0 5p3q se p 0 é bijetiva 3 Seja A um conjunto de cardinalidade n e f uma enumeração de A Dado B A defina bi 0 1 para todo i n por bi 1 se se x A Verifique que a função b 2A 0 1 n B b0 b2 bn1 é bijetiva 4 A função de pareamento de cantor é uma função que atribui números naturais consecutivos a pontos ao longo das diagonais no plano veja a figura 54 A função é f ℕ ℕ ℕ dada por fu v u vu v 1 2 u Prove que essa função é uma bijeção e determine a inversa Figura 54 função de pareamento de Cantor 5 Prove ou dê um contraexemplo para a seguinte sentença A é infinito se e somente se A n para todo n N 6 Sejam A1 A2 An conjuntos finitos e não vazios Prove usando indução que A1 A2 An A1 A2 An 7 Seja A U tal que 2A n Determine 2B se a B A x para algum x U A b B A x y para algum x y U A c B A x1x2xk para x1x2xk U A 8 Mostre que o conjunto dos inteiros ímpares números da forma 2k 1 com k Z tem a mesma cardinalidade que N 9 Verifique se é verdadeira ou falsa cada uma das afirmações a seguir No caso de ser falsa apresente um contraexemplo a se A e B são infinitos então A B é infinito b se B é infinito A B então A é infinito c se B é finito A B então A é finito d se A é finito A B então B é finito 10 Use o argumento da diagonal de Cantor para mostrar quer N não é enumerável 11 Prove que acrescentar um novo elemento a um conjunto finito resulta num conjunto finito 12 Prove que remover um elemento de um conjunto infinito resulta num conjunto infinito 13 Prove que todo subconjunto de um conjunto finito também é finito 14 Prove que todo conjunto infinito contém um subconjunto infinito enumerável 15 Prove que todo conjunto infinito contém um subconjunto próprio de mesma cardinalidade 16 Prove ou refute se A não é enumerável então A R 17 Prove ou refute Se A B C e A e C infinitos e enumeráveis então B é infinito enumerável 18 Prove ou refute Todo conjunto infinito é subconjunto de um conjunto infinito enumerável 19 Prove ou refute Se A B e A é infinito e enumerável e B não enumerável então B A não é enumerável 20 Prove que se A e B são enumeráveis então A B é enumerável e A B é enumerável 21 Um conjunto A é chamado de Peanofinito se e somente se existe um natural n e uma bijeção entre A e n e é chamado de Peanoinfinito se e somente se A não é Peanofinito Um conjunto A é Dedekindinfinito se há uma bijeção entre A e algum subconjunto próprio de A caso contrário é Dedekindfinito Prove por indução que se um conjunto é Peanofinito então é Dedekindfinito Usando o Princípio de Boa Ordem provar que se um conjunto é Peanoinfinito então é Dedekindinfinito 22 Prove que o PM é equivalente ao PIF portanto ao princípio da descida infinita de Fermat ao PBO e ao PG sugetão PMPG e PIFPM 23 Enuncie formalmente e dê uma prova para o princípio das gavetas infinitário se todo número natural é guardado em alguma dentre r gavetas então alguma gaveta tem um quantidade infinita enumerável de números naturais 24 Demonstre usando o princípio da casa dos pombos as afirmações abaixo a Para quaisquer seis ou mais usuários do facebook há sempre três deles amigos entre si ou há três deles desconheci dos entre si b Em grupo com 17 ou mais pessoas podemos encontrar três pessoas que se amam entre si três que se odeiam entre si ou três que são indiferentes entre si 92 c Em qualquer escolha da mais do que n números do conjunto 2n haverão dois deles primos entre si d Se escolhemos 13 pontos no interior de um retângulo 3 x 4 então existem dois pontos tais que sua distância é menor ou igual a 2 e a ba cb c é par para qualquer a b e c inteiros f Chico e sua esposa foram a uma festa com três outros casais No encontro deles houveram vários apertos de mão Ninguém apertou a própria mão ou a mão doa esposoa e ninguém apertou a mão da mesma pessoa mais que uma vez Após os cumprimentos Chico perguntou para todos inclusive para a esposa quantas mãos cada um apertou e recebeu de cada pessoa uma resposta diferente Quantas mãos Chico apertou g Os pontos de uma reta são coloridos com 12 cores Prove que existem dois pontos com a mesma cor tal que a distância entre eles é um número inteiro h Suponha que o conjunto 122n foi dividido em dois subconjuntos com n elementos cada Os elementos do primeiro conjunto foram ordenados em ordem crescente a1 a2 an e os do segundo conjunto ordenados em ordem decrescente b1 b2 bn Prove que Σni1 ai bi n2 dada para cada i de ai e bi pertence a 1n ou não 26 Cada estrada na Bozolândia é de mão única e cada par de cidades é conectada por exatamente uma estrada Prove que existe uma cidade que pode ser alcançada a partir de qualquer outra cidade em no máximo uma outra dica Figura 56 ladrilhamento 7colorido do plano 52 Princípios de contagem combinatória Uma interpretação para o princípio aditivo que vimos anteriormente é suponha que o evento E pode ocorrer n maneiras e o evento F de m maneiras distintas das outras n Então o número de maneiras de ocorrer o evento E ou F é nm No caso geral se A1 An são conjuntos doisadois disjuntos então A1 A2 An A1 A2 An Por exemplo há quantas possibilidades de escolher um inteiro entre 1 e 16 que é múltiplo de 3 ou de 7 Devemos determinar a cardinalidade do conjunto de inteiros entre 1 e 16 que são múltiplos de 3 ou múltiplos de 7 tais conjuntos são disjuntos pois mmc37 21 Os múltiplos de 3 são cinco os múltiplos de 7 são dois portanto os múltiplos de ambos são 52 7 O evento múltiplo de 3 ou múltiplo de 7 ocorre de 7 modos distintos E se contássemos os múltiplos de 2 e 3 entre 1 e 16 O princípio aditivo não se aplica pois alguns números são contados duas vezes como o 6 e o 12 TEOREMA 187 PRINCÍPIO DE INCLUSÃOEXCLUSÃO Se E e F são conjuntos finitos não necessariamente disjuntos então E F E F E F DEMONSTRAÇÃO Sejam E e F conjuntos finitos Podemos escrever E E F E F uma união disjunta verifique Logo podemos usar o princípio aditivo e escrever rearranjando os termos que E F E E F 52 Agora escrevemos E F como a seguinte união de subconjuntos disjuntos verifique E F E FF EE F e pelo princípio aditivo e 52 temos E F E F E F Por inclusãoexclusão o número de possíveis resultados que são múltiplo de 2 ou de 3 no lançamento de uma dado é dado por os múltiplos de 2 definem o subconjunto E 246 os múltiplos de 3 definem o subconjunto F 36 portanto E F E F E F 4 Exercício 188 Prove que se A B e C são conjuntos finitos então A B C AB C A B B C A C A B C Exercício 189 Conjecture uma expressão para o princípio de inclusãoexclusão para a cardinalidade da união de n conjuntos finitos Em uma turma de Matemática Discreta há 43 estudantes que fazem aula de Análise de Algoritmos 57 estudantes que fazem Análise Real e 29 estudantes que tomam aula de Análise na Educação Básica Há 10 alunos em Análise de Algoritmos e Análise real 5 em Análise Real e Análise na Educação Básica 5 em Análise de Algoritmos e Análise na Educação Básica e 2 tendo todos os três cursos Quantos alunos estão fazendo pelo menos dos cursos de análises Vamos indicar por C P e E os conjuntos de alunos que fazem Análise de Algoritmos Análise Real e Análise na Educação Básica respectivamente Queremos calcular C P E Aplicamos inclusãoexclusão C P E C P E C P P E C E C P E 111 Exercício 190 De quantas maneiras podemos escolher um número em 12100 que não é divisível por 2 3 ou 5 94 Podemos interpretar o princípio multiplicativo da seguinte forma se um experimento pode ser descrito em duas etapas de modo que há n desfechos possíveis para a 1ª etapa e há m desfechos possíveis para a 2ª etapa então o número de possíveis desfechos para o experimento é nm De um modo geral seja E1Er representarem r etapas de experimento composto então o números de modos distintos de realizar o experimento é E1E2Er que pode ser demonstrado usando princípio da indução Exemplo 191 Uma placa de carro é uma sequência de 3 letras seguidas por 4 dígitos Qual a quantidade de placas distintas que podemos obter Tomamos os conjuntos Ei ABZ das letras do alfabeto com i 123 para cada letra placa e os dígitos Ei 0123456789 para i 4567 cada número da placa Assim a quantidade de placas distintas que podemos obter é Πni1 Ei 262626104 175760000 Exemplo 192 Cada posição da memória célula de memória em um computador tem um endereço que é uma sequência binária As arquiteturas com processadores 32bits têm capacidade para endereçamento de 232 4294967296 posições de memória aproximadamente 4 Gigabytes As arquiteturas com processadores 64bits têm capacidade para endereçamento de 264 18446744073709551616 posições de memória aproximadamente 16 Exabytes 16 milhões de Terabytes Suponhamos que ocupe um dispositivo de dimensões 1 mm x 1 mm x 1 mm Para guardar 16 Exabytes precisaríamos de um quarto de dimensões 25 m x 25 m x 25 m Um arranjo em que é permitido repetição é chamado arranjo com repetição PROPOSIÇÃO 196 A quantidade de arranjos com repetição r elementos tomados de um conjunto A com n elementos é A quantidade de tais sequências é Ar Ar por 53 Retornando ao paradoxo do aniversário página 89 com que probabilidade ocorre que um novo grupo com 25 pessoas 2 ou mais pessoas façam aniversariano no mesmo dia Os aniversários de 25 pessoas podem ocorrer pelo princípio multiplicativo de 365 diferentes portanto há 36525 36525 possibilidades diferentes para o aniversário de 25 pessoas com pelo menos duas aniversariando no mesmo dia A probabilidade desse evento é Permutação Um arranjo simples com r n é chamado permutação Exemplo 197 A quantidade de permutações que podem ser formadas com as letras da palavra livros é 6 720 A quantidade de permutações que podem ser formadas com as letras da palavra teclado é 7 5040 A quantidade de permutações que podem ser formadas com as letras da palavra discreta é 8 40320 A quantidade de permutações que podem ser formadas com as letras da palavra universo é 362880 A quantidade de permutações que podem ser formadas com as letras da palavra semnublado é 6 11 39916800 A quantidade de permutações que podem ser formadas com as letras da palavra configurável é 12 479001600 A quantidade de subconjuntos de A com r elementos para 0 r n é Cn r Demonstração Dados um conjunto A de cardinalidade n e 0 r n seja Cn r a quantidade de subconjuntos de A com cardinalidade r Um único subconjunto do tamanho r determina n arranjos de r elementos de A Subconjuntos distintos determinam arranjos distintos portanto Cn r nnr Usando 54 Cn r nnr O coeficiente binomial n r para todo n r 0 é dado por n r nrnr Convencionamos que n r 0 se n r Em combinatória entendemos n r como a quantidade de subconjuntos de r elementos que podem ser formados a partir de um conjunto com n elementos Exemplo 200 A MegaSena é um jogo de apostas que consiste em acertar 6 dezenas escolhidas dentre 60 O número de possíveis resultados distintos para a MegaSena é 60 6 50063860 Se uma aposta em seis números demorar 1 segundo para ser registrada então registrar 50063860 demoraria um ano e meio aproximadamente A probabilidade de acertar os seis números é 160 6 150063860 2 108 A chance de morrer no Brasil em 2010 era 08 x 106 40 vezes melhor Exemplo 201 Numa população com n elementos n não são azuis e n n₁ são verdes De quantas maneiras podemos escolher k elementos com r deles azuis 0 r minn₁ k O número de maneiras de escolher k azuis é n₂ r Pelo Princípio Multiplicativo o número de maneiras de escolher r azuis e k r verdes é n₂ r n₁ k r Soluções inteiras de equações lineares Vamos começar com um caso simples estudaremos o número de soluções de x₁ x₂ x₃ 6 com xᵢ 012 para todo i Combinando com repetição escolhemos uma peça de dominó ao acaso com que probabilidade obtemos a peça p As peças de dominó são formadas por dois números tomados dos números de 0 a 6 podendo haver repetição Os dominós com pares de números diferentes são 6 2 21 mais os 7 1 7 pares repetidos resultam em 6 2 7 1 28 peças de dominós portanto 7 1 combinações de 2 objetos tomados dentre 7 com repetição Assim a probabilidade de ocorrer a peça p é num sorteio 128 Agora vamos imaginar um dominó com três pontas cada uma com um número de 0 a 6 de modo que em cada trio de números pode haver repetições e além disso cada trio aparece numa única peça na coleção de peças desse jogo Observação 205 Com os números 1 3 e 4 poderíamos ter duas peças como na figura 57 abaixo que são diferentes como observar lendoas no sentido horário a partir da mesma ponta Entretanto consideramos apenas uma delas na coleção Como vimos acima há 4 2 dominós de duas pontas e 3 1 dominós de três pontas Ingenuramente podemos conjecturar que são 10 4 de quatro pontas e 1 5 de cinco pontas Indo um pouco mais adiante conjecturamos que 2r 1 dominós de p pontas De fato essa conjectura se verifica e uma estratégia alternativa de contagem mais simples que a usada acima é contar quantas vezes podemos repetir cada um dos sete número do modo que a soma total das repetições é r Se xᵢ é quantas vezes o i é escolhido em N de tais escolhas Para o caso geral que vale dentre n objetos se queremos selecionar r podendo haver repetição então isso pode ser feito de n r 1 r maneiras diferentes por exemplo sejam 7 números dos quais selecionamos 2 podendo repetir número de 7 2 1 2 862 28 1 1 1 1 1 1 6 e uma solução da equação 59 corresponde a escolha de 2 operadores dentro os 5 escritos na equação acima por exemplo se usamos θ para representar as escolhas correspondente a x₁ 2 x₂ 2 e x₃ 1 e 1 1 1 1 1 1 6 corresponde a x₁ 2 x₂ 2 e x₃ 2 Portanto essa equação têm g soluções em ℤ Agora estudaremos o número de soluções de x₁ x₂ x₃ 6 com xᵢ 012 para todo i Notemos que uma solução x₁x₂x₃ xyz inteira positiva da equação x₁ x₂ x₃ 6 determina uma única solução inteira e nãonegativa x₁ 1 y 1 z 1 da equação x₁ x₂ x₃ 6 viceversa ou seja as equações x₁ x₂ x₃ 6 6 3 com xᵢ 123 para todo i Agora para o problema que gerou essa discussão o número de maneiras de selecionar r objetos podendo haver repetição dentre n objetos é igual ao número de soluções inteiras da equação 58 que é o mesmo número de soluções inteiras de x₁ x₂ xₙ n r com xᵢ 12 para todo i Consideramos 1 1 1 n r n r 1 operadores e escolhemos n 1 ou seja usando 55 são nr1 r 1 distribuir n bolas distintas em n caixas distintas com qualquer número de bolas por caixa distribuir n bolas distintas em n caixas distintas com no máximo uma bola por caixa distribuir n bolas idênticas em n caixas distintas com no máximo uma bola por caixa distribuir n bolas idênticas em n caixas distintas com qualquer número de bolas por caixa O número de modos de distribuir n bolas distintas em n caixas idênticas é conhecido como número de Bell do qual falaremos adiante Binômio de Newton Se A é um conjunto com n elementos então a quantidade de subconjuntos de A de cardinalidade r é o número de maneiras distintas que podemos selecionar r elementos dentre os n do conjunto isto é são n r subconjuntos Por outro lado a bijeção que identifica subconjuntos de A com sequências binárias exercício 3 na página 91 garante que há 2n subconjuntos de A Dissó Esse fato também é consequência de um resultado mais geral conhecido como Teorema Binomial TEOREMA 209 Teorema Binomial Para todo n 0 vale x yn n rxr ynr Vejamos como o produto se desenvolve para valores pequenos de n No caso n 2 temos xyxy xyxy xxxyyxyy e multiplicando o resultado por xy obtemos o caso n 3 xyxyxy xyxxxyyxyy xyxxxxyxxyyxyxyyxyy xxxxyxxyyyyy Exercício 210 Escreva uma prova do teorema binomial usando indução Exercício 211 Verifique se vale a igualdade n rn rxr ynr n rn rxr ynr A relação de Stifel nos dá um algoritmo para encontrar os coeficientes do polinômio Dispõe esses coeficientes num arranjo triangular cuja nésima linha são os coeficientes de xyn chamado triângulo de Pascal 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 Vejanos exemplo de aplicação do teorema binomial na prova de uma igualdade Por um lado temos 1 x2n 2n m02n mxm Por outro lado temos que 1 x2n é o produto k1 nkk0 nk Da equação 511 acima são 43nc pares A B cuja interseção está contida em qualquer C S cuja cardinalidade é c A quantidade de termos C c portanto o número de teras A B C S S S tais que A B C é n r0n c43nc 4 3n Novamente na equação 512 usamos o teorema binomial para concluir o resultado Portanto IA B C S S S A B C 7n Exercício 213 Escreva uma equação de recorrência para resolver o problema do exercício anterior Verifique usando indução que 7n é uma solução Exemplo 215 Um modo de contar quantos subconjuntos de cardinalidade r tem um conjunto de cardinalidade n é considerar o conjunto A dos arranjos simples de r elementos Dados dois arranjos α β e dizemos que eles são equivalentes se eles diferem apenas na ordem dos elementos os elementos em si são os mesmos Se α e β são equivalentes escrevemos α β e como relação de equivalência sobre A verifique Como α e β têm os mesmos elementos α é uma permutação de β assim a classe de equivalência α tem r elementos Toda classe de equivalência tem r elementos pelo mesmo argumento Notemos que há tantos subconjuntos de cardinalidade r de um conjunto de cardinalidade n quantos são os elementos de A o conjunto das classes de equivalência de sobre A Lembremos o teorema 124 página 63 que diz que o conjunto quociente A formado pelas classes de equivalência da relação sobre A é uma partição de A de modo que A r A pelo princípio aditivo Finalmente A A é cardinalidade de subconjuntos de cardinalidade r de um conjunto de cardinalidade n é A A É frequente precisar determinar a cardinalidade das classes de equivalência de um conjunto quociente nas aplicações TEOREMA 216 Se A é finito e uma relação de equivalência sobre A cujas classes de equivalência têm a mesma cardinalidade digamos k A então A A k Demonstração Se A é finito então 42 da proposição 120 página 63 e do princípio aditivo temos A a e A Exemplo 229 dados de Sicherman Um dado com faces 1 2 2 3 3 4 e outro com faces 1 3 4 5 6 8 quando são lançados tem as frequências das soma dadas por x1 2x2 2x3 x4x1 x3 x4 x5 x6 x8 x12 2x11 3x10 4x9 5x8 6x7 5x6 4x5 3x4 2x3 x2 que é a mesma dos dados regulares 517 Para três lançamentos usamos a expansão do polinômio ao 515 cubo para ter as quantidades de soluções de i j k m com i jk 16 e todo m N A resposta está codificada em x1 x2 x3 x4 x5 x63 x18 3x17 6x16 10x15 15x14 21x13 25x12 27x11 27x10 25x9 21x8 15x7 10x6 6x5 3x4 x3 Para responder a pergunta inicial precisamos conhecer o coeficiente de x14 na quarta potência de 515 x1 x2 x3 x4 x5 x64 x24 4x23 10x22 20x21 35x20 56x19 80x18 104x17 125x16 140x15 146x14 140x13 125x12 104x11 80x10 56x9 35x8 20x7 10x6 4x5 x4 portanto há 146 maneiras diferentes de obter a soma 14 No exemplo do dado com faces 122255 as somas de 4 lançamentos são dadas pela quarta potência do polinômio 516 x1 3x2 2x54 16x20 96x17 32x16 216x14 144x13 24x12 216x11 216x10 72x9 89x8 108x7 54x6 12x5 x4 portanto há 216 maneiras diferentes de obter a soma 14 Exemplo 230 Um pai generoso deseja dividir R2000 entre seus três filhos de modo que cada um receba pelo menos R500 e ninguém receba mais que R1000 e a quantia do filho mais velho é par De quantas maneiras ele pode fazer essa divisão O filho mais velho recebe um valor de 6810 e os outros filhos de 5678910 portanto procuramos pelo coeficiente de x20 no polinômio x6 x8 x10x5 x6 x7 x8 x9 x10x5 x6 x7 x8 x9 x10 x30 2x29 4x28 6x27 9x26 12x25 13x24 14x23 13x22 12x21 9x20 6x19 4x18 2x17 x16 Portanto são 9 maneiras de realizar a divisão Exercício 231 Quantas soluções inteiras tem x1 x2 x3 11 com x1 123 e x2x3 45 Solução O coeficiente de x11 em x1 x2 x3x4 x5x4 x5 531 Série formal de potências Imagine um país no qual há apenas três valores de moedas 1 centavo 2 centavos e 4 centavos De quantas maneiras podemos formar 10000 centavos Precisamos resolver a equação a 2b 4c 10000 para números inteiros nãonegativos abc Os possíveis valores para a são codificados pelo polinômio 1 x x2 os possíveis valores para b são codificados por 1 x2 x4 e os possíveis valores para b são codificados por 1 x4 x8 Agora procuramos o coeficiente de x10000 no polinômio Px 1 x x2 1 x2 x4 1 x4 x8 Podemos multiplicar os termos e com alguma perseverança eventualmente encontramos o coeficiente de x10000 Mas agora precisamos buscar um modo mais pragmático para essa tarefa 112 Índice Remissivo A B 19 Cnr 97 nr 95 A B 9 A1 A2 An B 9 B A 95 xnAx 113 ℵ0 87 F 3 V 3 c 87 maxA 44 Árvore binária com raiz 77 ímpar 30 Modus Ponens 11 Modus ponens 11 Modus tollens 12 modus ponens 9 antecedente 5 anticadeia 68 anulamento 28 argumento 11 arranjo 96 arranjo com repetição 96 arranjo simples 95 associativa 28 atômica 3 base da indução 50 bem definidas 55 bem fundada 74 bicondicional 3 bijetividade 25 boa ordem 68 boaordem 27 cadeia 68 cancelativa 28 cardinalidade 82 85 cardinalidade do contínuo 87 classe de equivalência 63 cobre 66 coeficiente 113 coeficiente binomial 97 coeficiente multinomial 104 combinação 96 comparáveis 66 composto 41 comutativa 28 conclusão 11 condição de cadeia descendente 74 condicional 3 conectivos lógicos 3 conjunção 3 conjunto das partes de A 19 conjunto indutivo 22 conjunto quociente 64 consequente 5 contagem 86 contagem dupla 100 contradição 5 contraexemplo 7 contrapositiva 5 converge 113 convergente 122 cota inferior 29 crescente 40 decrescente 40 definição recursiva 55 Desigualdade de Bernoulli 51 diagrama de Hasse 66 Diferença 20 Diferença simétrica 20 disjunção 3 disjuntos 21 distributiva 28 divergente 122 divide 33 domínio 24 e 3 elemento neutro 28 elemento simétrico 28 enumerável 87 enumeração 86 equação de recorrência 55 equivalência lógica 10 fatores 33 fatorial 55 124 fecho reflexivo 79 fecho transitivo 80 finito 86 forma fechada 56 forma reduzida 36 função 25 função de Ackermann 75 função de pareamento de cantor 91 função geradora ordinária 113 Generalização existencial 13 Generalização universal 13 grafo de Moser 93 hipótese do contínuo 88 identidade de Vandermonde 108 implica logicamente 9 implicam logicamente 9 incomparáveis 66 indução noetheriana 75 Indução pra frentepra trás 50 injetividade 25 instanciação 6 Instanciação existencial 13 Instanciação universal 13 Intersecção 20 irracional 36 isomorfas 73 isomorfismo 73 juro composto 55 lema de Tukey 80 Lema de Zorn 80 limitado inferiormente 29 limitado superiormente 44 linearização 72 logicamente equivalentes 10 mínimo 29 67 máximo 67 média aritmética 53 média geométrica 53 módulo 29 mãos de bridge 104 maior divisor comum 35 maior elemento 44 mapa logístico 55 maximal 67 menor elemento 27 29 mesma cardinalidade 82 minimal 67 número de Bell 106 número de Stirling do segundo tipo 105 números de Fibonacci 51 não 3 nãocrescente 40 nãodecrescente 40 negação 3 ordem estrita 66 ordem estrita associada 66 ordem lexicografica 71 ordem parcial 65 ordem produto 71 ordem total 68 ordenação topológica 71 ordinais finitos de Von Neumann 73 ordinais limites 74 ordinais sucessores 74 ou 3 par 30 par ordenado 23 paradoxo dos aniversários 89 96 partição 21 passo da indução 50 permutação 96 permutação caótica 108 PG 85 PIF 48 PIF passo k 50 PIFc 49 PIFcg 49 PIFg 49 PM 86 premissas 11 preserva a ordem 71 primo 41 princípio das gavetas generalizado 88 princípio aditivo 86 princípio da casa dos pombos 85 princípio da descida infinita de Fermat 41 Princípio da Indução finita 48 Princípio da Indução finita completo 49 Princípio da Indução finita completo generalizado 49 Princípio da Indução finita generalizado 49 Princípio das Gavetas 85 Princípio das gavetas generalizado 88 princípio das gavetas infinitário 92 Princípio das gavetas ordenado 89 Princípio das gavetas probabilístico 89 Princípio de InclusãoExclusão 94 108 Princípio de indução completo para boa ordem 69 Princípio de indução completo para relação bem fundada 75 princípio multiplicativo 86 princípo da boa ordenação do naturais 27 problema 125 de HadwigerNelson 93 produto cartesiano 23 progressões aritmética e geométrica 55 projeção canônica 64 Prova por casos 13 quantificação existencial 7 quantificação universal 7 racional 36 recíproca 5 recíproco 114 refina 64 Regra da Adição 11 Regra da conjunção 12 Regra da contradição 12 Regra da Simplificação 11 Regra do silogismo disjuntivo 12 Regra do silogismo hipotético 12 Regras de inferência 11 relação 24 relação composta 25 relação de equivalência 62 relação de Stifel 73 relação inversa 25 representante 63 Resolução 13 se e somente se 3 seentão 3 segmento inicial 73 segmento inicial próprio 73 sentença 3 sentença aberta 6 sequência numérica 40 sequência transfinita 74 sobrejetividade 25 solução 56 subconjunto 19 subconjunto próprio 19 subconjuntos próprios 67 tautologia 5 Teorema Binomial 100 Teorema da boa ordem 80 teorema da divisão euclidiana 41 teorema de Bézout 42 teorema de BachetBézout 76 Teorema de Cantor 87 Teorema de CantorSchröderBernstein 83 Teorema de Dilworth 70 teorema de ErdosSzekerés 70 teorema fundamental da aritmética 41 teorema fundamental das relações de equivalência 63 teorema multinomial 109 triângulo de Pascal 101 União 20 válido 11 valor absoluto 29 valorlógico 3 variável livre 5 variável muda 6 126