Docsity
Docsity

Prepare-se para as provas
Prepare-se para as provas

Estude fácil! Tem muito documento disponível na Docsity


Ganhe pontos para baixar
Ganhe pontos para baixar

Ganhe pontos ajudando outros esrudantes ou compre um plano Premium


Guias e Dicas
Guias e Dicas

Elemento de Logica Matematica e Teoria de Conjuntos, Notas de estudo de Informática

- - - - - - -

Tipologia: Notas de estudo

Antes de 2010

Compartilhado em 14/03/2008

daniel-jose-gomes-da-costa-6
daniel-jose-gomes-da-costa-6 🇧🇷

5

(1)

5 documentos

Pré-visualização parcial do texto

Baixe Elemento de Logica Matematica e Teoria de Conjuntos e outras Notas de estudo em PDF para Informática, somente na Docsity! Α U Elementos de Lógica Matemática e Teoria dos Conjuntos Jaime Campos Ferreira Uma reedição revista pelo autor dos capítulos iniciais das Lições de Análise Real  Departamento de Matemática  Instituto Superior Técnico  Outubro de 2001 Introdução Alguns amigos e colegas, regentes das primeiras disciplinas de Análise Ma- temática no IST, aconselharam uma reedição dos dois primeiros caṕıtulos do texto Lições de Análise Real (que redigi há mais de trinta anos), por entenderem que, nas condições actuais do nosso ensino, poderiam ser de al- guma utilidade como introdução aos principais assuntos versados nas suas aulas. Foi esta a causa da presente publicação. O texto foi agora submetido a uma revisão ligeira; no entanto, para os estudantes que utilizem também o livro Introdução à Análise Matemática, convém mencionar uma pequena di- ferença: o conjunto dos números naturais (em ambos os trabalhos designado pela letra N) é definido nesse livro por forma a incluir o número zero, en- quanto no texto que agora se publica o não inclui. Trata-se evidentemente de uma discrepância em matéria de natureza convencional, da qual, depois de devidamente acentuada, não resultará decerto qualquer inconveniente para os eventuais utilizadores dos dois trabalhos. Lisboa, Outubro de 2000, Jaime Campos Ferreira 4 Caṕıtulo 1 Elementos de lógica matemática Para compreender bem as definições e teoremas que constituem as teorias matemáticas cujo estudo vamos iniciar, é indispensável habituarmo-nos a usar uma linguagem mais precisa e rigorosa do que a que se utiliza, em geral, na vida corrente. A aquisição desse hábito pode ser muito facilitada pelo recurso a algumas noções e śımbolos da Lógica Matemática, dos quais indicaremos neste primeiro caṕıtulo, de forma muito resumida e largamente baseada na intuição, aqueles que têm maior interesse para a sequência do nosso curso. Convém, no entanto, observar que a Lógica Matemática tem hoje aplica- ções concretas extremamente importantes, em diversos domı́nios; uma das mais notáveis é, sem dúvida, a sua utilização no planeamento dos modernos computadores electrónicos. 1.1 Termos e proposições. Álgebra proposicional. A linguagem usada na Matemática, como qualquer outra linguagem, com- preende designações (também chamadas nomes ou termos) e proposições (ou frases). As designações servem para indicar determinados objectos ma- temáticos: números, pontos, conjuntos, funções, operações, figuras geométri- cas, etc.; as proposições exprimem afirmações — que podem ser verdadeiras ou falsas — a respeito dos mesmos objectos. Como exemplos de designações registamos as seguintes1: 7, 3 + 4, ( 2−√π )7 , 2 + 3i, N, R. Observe-se que as duas primeiras designações se referem ao mesmo ob- jecto: são designações equivalentes ou sinónimas; para indicar que duas designações, a e b, são equivalentes, escreve-se usualmente a = b. Como exemplos de proposições (as duas primeiras verdadeiras, as outras falsas) 1Designamos por N e R, respectivamente, o conjunto dos números naturais e o conjunto dos números reais. 5 CAPÍTULO 1. ELEMENTOS DE LÓGICA MATEMÁTICA podemos indicar: 7 = 3 + 4, 4 ≤ 4, 2 + 3i = 3 + 2i, 2 + 1 < 1 + 2. Uma proposição é necessariamente verdadeira ou falsa (mas nunca uma coisa e outra); na primeira hipótese, diz-se também por vezes que a proposição tem o valor lógico 1, na segunda que tem o valor lógico 0. Os śımbolos 1 e 0 servem assim, de forma convencional, para designar respectivamente verdade e falsidade. Duas proposições dizem-se equivalentes quando têm o mesmo valor lógico; por exemplo, são equivalentes as proposições 7 ≤ 0 e (−2)5 = 25. Para indicar que duas proposições — designadas, por exemplo, pelos śımbolos p e q — são equivalentes, costuma-se escrever p ⇐⇒ q. Dadas duas proposições, p e q, chama-se conjunção ou produto lógico de p e q, e designa-se por p∧q (ler “p e q”) a proposição que consiste em afirmar simultaneamente p e q. A proposição p ∧ q será, portanto, verdadeira se o forem as duas proposições dadas e falsa quando uma destas for falsa (ou quando o forem ambas). Por exemplo, a conjunção das proposições “4 é um número par” e “4 é um divisor de 10” equivale à afirmação de que “4 é um número par e um divisor de 10” e é, evidentemente, uma proposição falsa. Por outro lado, chama-se disjunção ou soma lógica de p e q, e designa-se por p ∨ q, (“p ou q”), a proposição que consiste em afirmar que pelo menos uma das proposições dadas é verdadeira. Nestas condições, a proposição p∨q só é falsa quando o forem ambas as proposições p e q. A disjunção das duas proposições consideradas no exemplo anterior é a proposição (verdadeira): “4 é um número par ou é um divisor de 10”. Nas tabelas seguintes, análogas às vulgares tabuadas das operações ele- mentares estudadas na escola primária, indicam-se os valores lógicos das proposições p∧q e p∨q, em correspondência com os posśıveis valores lógicos de p e q: Observe-se que o valor lógico de p ∧ q é o mı́nimo dos valores lógicos das proposições p e q, enquanto o valor lógico de p ∨ q é o máximo dos valores lógicos das mesmas proposições (evidentemente, no caso de estas terem valores lógicos iguais, entende-se por máximo e mı́nimo desses valores lógicos o seu valor comum). Nota. Podem definir-se de forma inteiramente análoga a conjunção e a disjunção no caso de serem dadas mais de duas proposições. Por exemplo, a conjunção das proposições p, q, r,. . . consiste na afirmação de que todas essas proposições são verdadeiras e é portanto uma proposição que só é falsa se alguma das proposições p, q, r,. . . , o fôr. 6 1.2. EXPRESSÕES COM VARIÁVEIS. (supondo que x e y têm por domı́nio o conjunto R). Consideremos agora as expressões: x2 > 0, 2x = x2, x2 − y2 = 0, x− y > y − z. Se em qualquer destas expressões substituirmos todas as variáveis por de- signações de números reais, obteremos desta vez, não designações, mas sim proposições, verdadeiras ou falsas. As expressões com variáveis, que se transformam em proposições quando as variáveis são substitúıdas por designações convenientes, chamam-se ex- pressões proposicionais ou condições. As expressões proposicionais podem também combinar-se por meio de operações lógicas inteiramente análogas às que considerámos no caso das proposições. Sejam, por exemplo, p(x) e q(x) duas expressões proposicionais com uma variável. A conjunção, p(x) ∧ q(x), é uma nova condição que se converte numa proposição verdadeira sse forem atribúıdos a x valores que tornem verdadei- ras as duas condições p(x) e q(x). A disjunção, p(x)∨ q(x), é uma condição que só é falsa para os valores da variável que tornam p(x) e q(x) ambas falsas. A negação de p(x) é a condição ∼ p(x), apenas verdadeira para os valores de x que convertem p(x) numa proposição falsa. A implicação, p(x) =⇒ q(x), é uma condição que se converte numa proposição falsa sse forem atribúıdos à variável x valores para os quais p(x) seja verdadeira e q(x) falsa. Finalmente, a equivalência, p(x) ⇐⇒ q(x), é a conjunção das implicações p(x) =⇒ q(x) e q(x) =⇒ p(x). Vejamos alguns exemplos de equivalências (verdadeiras, quaisquer que sejam os valores reais atribúıdos às variáveis): [(x > 3) ∨ (x = 3)] ⇐⇒ x ≥ 3, [(x < 3) ∧ (x ≥ 2)] ⇐⇒ 2 ≤ x < 3, ∼ (x < 1) ⇐⇒ x ≥ 1, x2 > 0 ⇐⇒ x 6= 0. São também sempre verdadeiras as condições: x < 1 =⇒ x < 3, [(x < y) ∧ (y < z)] =⇒ x < z, e, supondo que x designa agora uma variável cujo domı́nio é o conjunto dos números naturais, N: ∼ (x é par ) ⇐⇒ x é ı́mpar, x é múltiplo de 6 =⇒ x é múltiplo de 3, [(x é múltiplo de 2) ∧ (x é múltiplo de 3)] ⇐⇒ (x é múltiplo de 6). 9 CAPÍTULO 1. ELEMENTOS DE LÓGICA MATEMÁTICA 1.3 Quantificadores. Se, numa dada condição p(x), atribuirmos à variável x um dos valores do seu domı́nio, obteremos, como vimos, uma proposição. Outra forma, ex- tremamente importante em Matemática, de obter proposições a partir de uma condição p(x), é antepor-lhe um dos śımbolos ∀x ou ∃x, que se chamam quantificadores (quantificador universal e quantificador existencial , respec- tivamente). A proposição ∀x p(x) lê-se “qualquer que seja x, p(x)” ou “para todo o x, tem-se p(x)” e é verdadeira sse, atribuindo a x qualquer valor do seu domı́nio, p(x) se converter sempre numa proposição verdadeira. A proposição ∃x p(x), que se lê “existe um x tal que p(x)” ou “para algum x, tem-se p(x)”, é falsa sse p(x) se transformar numa proposição falsa sempre que à variável x seja atribúıdo um valor qualquer do seu domı́nio. Por exemplo, sendo x uma variável real, são verdadeiras as proposições: ∀x x2 + 1 > 0, ∃x x4 ≤ 0 e ∃x x2 − 3 = 0. A definição e o uso dos quantificadores, no caso de proposições com mais de uma variável, são inteiramente análogos. Assim, supondo x e y variáveis reais, a proposição ∀x∃y y < x pode ler-se “qualquer que seja x existe um y tal que y < x” e equivale portanto a afirmar que “não existe um número real que seja menor do que todos os outros”. É, evidentemente, uma proposição verdadeira (observe-se que seria falsa se o domı́nio das variáveis x e y fosse, em vez do conjunto dos reais, o dos naturais). A proposição ∃y∀x y < x, que exprime a existência de um número real menor do que qualquer outro (e até menor do que ele próprio), é obviamente falsa. Convém notar bem que, como acabámos de ver, trocando a posição dos dois quantificadores que intervêm na proposição ∀x∃y y < x, se obtem uma proposição não equivalente. Este facto verifica-se correntemente, quando os quantificadores trocados são de tipo diferente (um universal, outro existen- cial). Em contrapartida, a permutação de quantificadores do mesmo tipo con- duz sempre, como é fácil verificar, a uma proposição equivalente à inicial. Por exemplo, são equivalentes as proposições: ∀x∀y [x3 = y3 ⇐⇒ x = y] ∀y∀x [x3 = y3 ⇐⇒ x = y] que podem escrever-se abreviadamente4: ∀x,y [x3 = y3 ⇐⇒ x = y]. 4Esta proposição, verdadeira no caso de x e y serem variáveis reais, seria falsa se se tratasse de variáveis complexas (isto é, de variáveis tendo por domı́nio o conjunto dos números complexos). Em qualquer hipótese, porem, era sempre leǵıtima a permutação dos dois quantificadores universais. 10 1.3. QUANTIFICADORES. Dadas duas condições — p(x, y) e q(x, y) por exemplo — diz-se que a primeira implica formalmente a segunda sse é verdadeira a proposição: ∀x,y p(x, y) =⇒ q(x, y) Por exemplo, no conjunto dos reais, x = y2 implica formalmente x2 = y4, mas já a implicação x > y =⇒ x2 > y2 não é formal. Observe-se que é vulgar na linguagem matemática usar-se apenas a pa- lavra “implica” no sentido de “implica formalmente” e até escrever somente p(x) =⇒ q(x), em lugar de ∀x p(x) =⇒ q(x). Trata-se de “abusos de lingua- gem” que, geralmente, não têm inconveniente de maior, porque o próprio contexto permite reconhecer com facilidade se se pretende ou não exprimir uma implicação formal. De forma análoga, diz-se que as condições p(x, y) e q(x, y) são formal- mente equivalentes (ou apenas equivalentes) sse se tiver: ∀x,y p(x, y) ⇐⇒ q(x, y), expressão esta em que, muitas vezes, se suprime também o quantificador. Convém salientar que a implicação formal p(x, y) =⇒ q(x, y) pode tam- bém exprimir-se dizendo que “p(x, y) é condição suficiente para q(x, y)” ou que “q(x, y) é condição necessária para p(x, y)”. No caso de equivalência for- mal costuma também dizer-se que “p(x, y) é condição necessária e suficiente para q(x, y)”. Têm importância fundamental as seguintes leis — designadas por se- gundas leis de De Morgan — que indicam como se efectua a negação de proposições com quantificadores: ∼ ∀x p(x) ⇐⇒ ∃x ∼ p(x), ∼ ∃x p(x) ⇐⇒ ∀x ∼ p(x). Para enunciar esta última, poderia dizer-se que “não existindo nenhum valor de x que torne p(x) verdadeira, todos os valores de x tornam essa proposição falsa, e reciprocamente”. Assim, por exemplo: ∼ ∀x x2 > 0 ⇐⇒ ∃x x2 ≤ 0, ∼ ∀x,y∃z x = yz ⇐⇒ ∃x,y∀z x 6= yz. 11 CAPÍTULO 1. ELEMENTOS DE LÓGICA MATEMÁTICA 14 BIBLIOGRAFIA Bibliografia [1] F. Dias Agudo. Introdução à Álgebra Linear e Geometria Anaĺıtica. 1964. [2] R. Godement. Cours d’Algèbre. [3] M. Monroe. Introductory Real Analysis. [4] J. Santos Guerreiro. Curso de Matemáticas Gerais. Livraria Escolar Editora, 1973. [5] J. Sebastião e Silva. Compêndio de Matemática, volume 1, 1o tomo. Gabinete de Estudos e Planeamento, Ministério da Educação, 1970. [6] R. Stoll. Sets, Logic and Axiomatic Theories. [7] P. Suppes. Introduction to Logic. 15 BIBLIOGRAFIA 16 2.1. CONJUNTOS. OPERAÇÕES FUNDAMENTAIS. conjunto vazio e se designa usualmente por ∅. Trata-se, evidentemente, de um conjunto sem elemento algum. Tem-se assim, por exemplo: ∅ = {x : x 6= x}. Dados dois conjuntos, A e B, a intersecção de A com B, designada por A∩B, é o conjunto formado pelos elementos comuns a A e a B; a reunião de A com B é o conjunto A∪B, formado por todos os elementos que pertencem a um, pelo menos, dos conjuntos A e B. Simbolicamente: A ∩B = {x : x ∈ A ∧ x ∈ B}, A ∪B = {x : x ∈ A ∨ x ∈ B}. Se A∩B = ∅, isto é, se A e B não têm elementos comuns, diz-se que são conjuntos disjuntos. Chama-se diferença dos conjuntos A e B, ou complementar de B em A, ao conjunto A \ B formado pelos elementos de A que não pertencem a B: A \ B = {x : x ∈ A ∧ x /∈ B}. É evidente que se tem A \ B = ∅ sse A ⊂ B. No estudo de diversas questões sucede, por vezes, poder fixar-se de ińıcio um conjunto U , tal que todos os conjuntos que interessa considerar no desenvolvimento da teoria são subconjuntos de U . Quando está assim fixado um conjunto universal , é usual chamar apenas complementar de um dado conjunto A (tal que A ⊂ U evidentemente!) ao conjunto U \A, que então se designa de preferência pelo śımbolo C(A). Pode também escrever-se, nessa hipótese (e só nessa): C(A) = {x : x /∈ A}. Exerćıcios 1. Mostre que, quaisquer que sejam os conjuntos A, B e C, se tem A ⊂ A e A ⊂ B ∧B ⊂ C =⇒ A ⊂ C. 2. Mostre que se tem {x : p(x)} ⊂ {x : q(x)} sse p(x) implica (formalmente) q(x) e {x : p(x)} = {x : q(x)} sse p(x) é equivalente a q(x). 3. Recorrendo à equivalência das proposições A 6⊂ B e ∃x(x ∈ A∧ x /∈ B), mostre que o conjunto vazio está contido em qualquer conjunto. 19 CAPÍTULO 2. ELEMENTOS DE TEORIA DOS CONJUNTOS. 4. Indique quais das proposições seguintes são verdadeiras: ∅ ⊂ ∅, 1 ∈ {1}, {1} ∈ {1, 2, 3}, 2 ∈ {1, 2}, 1 ∈ {2, 3}, 2 ∈ {1, 2, 3} {1} ⊂ {1, {2, 3}}, ∅ = {x : x ∈ N ∧ x = x + 1}. 5. Quantos elementos têm os conjuntos seguintes: ∅, {∅}, {∅, {∅}}, {{∅}}? Indique algumas proposições verdadeiras que exprimam relações de inclusão (isto é, da forma X ⊂ Y ) e relações de pertença (X ∈ Y ) entre dois dos conjuntos dados. 6. Indique dois conjuntos A e B para os quais seja verdadeira a proposição A ∈ B ∧ A ⊂ B. 7. Sendo A um conjunto qualquer, chama-se conjunto das partes de A e designa-se por P(A) o conjunto cujos elementos são, precisamente, todos os subconjuntos de A. Por exemplo, se A = {1, 2} é P(A) = {∅, {1}, {2}, A} a) Quantos elementos têm os conjuntos P(∅),P(P(∅))? b) Verifique que as relações x ∈ X e {x} ∈ P(X) são equivalentes. c) Prove, por indução, que, sendo A um conjunto com n elementos, o número de elementos de P(A) é 2n. 8. Sendo A = {1}, B = {x : x ∈ N ∧ x ≥ 2}, C = {x : x ∈ N ∧ x ≤ 6} e designando em geral por Mn e Dn, respectivamente, o conjunto dos múltiplos e o conjunto dos divisores do número natural n, determine os conjuntos A ∪B, A ∩B, B ∪C, B ∩ C, A ∩M2, M2 ∩D12, N \ A, (N \D12) ∪ (N \D17). 9. a) Interprete geometricamente (como subconjuntos de R) os seguin- tes conjuntos: A = {x : |x| < 1}, B = {x : |x| < 0}, C = {x : |x− a| < ε}, D = {x : |x| > 0}, E = {x : |x| > −1}, F = {x : (x− a)(x− b) < 0}. 20 2.2. PARES ORDENADOS. SEQUÊNCIAS. PRODUTO CARTESIANO. RELAÇÕES. b) Determine A ∩ C, A ∩D, A ∪D, E ∩ F . 10. a) Interprete geometricamente, como subconjuntos do “plano” R2, os seguintes: A = {(x, y) : x2 + y2 ≤ 1}, B = { (x, y) : x > 1 2 } , C = {(x, y) : x < y}, D = {(x, y) : xy ≥ 0}, E = {(x, y) : x > 0 ∧ y > senx}, F = {(x, y) : |x|+ |y| ≤ 1}, G = {(x, y) : max(|x|, |y|) < 1}. b) Recorrendo à interpretação geométrica, determine A∩D, C(B)∪ E, B ∩C ∩D, A ∩ F , A ∪G, C(A) ∩ F . 11. Verifique que qualquer das condições seguintes é equivalente a A ⊂ B: A ∩B = A, A ∪B = B e, suposto fixado um conjunto universal, U : C(B) ⊂ C(A), A ∩ C(B) = ∅, C(A) ∪B = U . 12. Um conjunto X = {a, b, . . .} e duas operações designadas, por exemplo, pelos śımbolos ∪ e ∩, constituem uma álgebra de Boole sse forem verificados os seguintes axiomas: 1) a, b ∈ X =⇒ a ∪ b ∈ X ∧ a ∩ b ∈ X; 2) (a ∪ b) ∪ c = a ∪ (b ∪ c), a ∩ (b ∩ c) = (a ∩ b) ∩ c (associatividade); 3) a ∪ b = b ∪ a, a ∩ b = b ∩ a (comutatividade); 4) a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c), a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪ c) (distributividade); 5) existem em X dois elementos, que designaremos por 0 e 1, tais que, para todo o a ∈ X, a ∪ 0 = a, a ∩ 1 = a; 6) para todo o a ∈ X existe a′ ∈ X tal que a ∪ a′ = 1, a ∩ a′ = 0. Prove que, sendo A um conjunto arbitário, o conjunto P(A) e as operações de reunião e intersecção de conjuntos, constituem uma álgebra de Boole. Quais são os elementos 0 e 1 dessa álgebra? 2.2 Pares ordenados. Sequências. Produto cartesiano. Relações. Observemos em primeiro lugar que, sendo a e b dois objectos quaisquer, se tem, evidentemente {a, b} = {b, a}. 21 CAPÍTULO 2. ELEMENTOS DE TEORIA DOS CONJUNTOS. por todas as sequências (x1, x2, . . . , xn) tais que x1 ∈ A1, x2 ∈ A2, . . . , xn ∈ An: A1 ×A2 × . . . ×An = {(x1, x2, . . . , xn) : x1 ∈ A1 ∧ . . . ∧ xn ∈ An}. Se fôr A1 = A2 = . . . = An = A, o conjunto A1 × A2 × . . . × An é a na potência cartesiana de A, habitualmente designada por An. Exemplos 1. Sendo n um natural qualquer, a na potência cartesiana do conjunto dos reais, Rn, é o conjunto de todas as sequências de n números reais; são elementos de Rn, por exemplo, as sequências (1, 12 , . . . , 1 n ), (0, 0 . . . , 0) (com n zeros). 2. Institúıdo um referencial no “espaço ordinário”, cada ponto P deste espaço determina um terno ordenado de números reais (a abcissa x, a ordenada y e a cota z do ponto P , no referencial considerado); reci- procamente, a cada terno ordenado de números reais corresponde um ponto do espaço ordinário. Nesta ordem de ideias, tal como o conjunto PSfrag replacements x y z P = (x, y, z) R pode ser identificado com o conjunto dos pontos de uma recta e o conjunto R2 com o conjunto dos pontos de um plano, R3 pode ser interpretado como o conjunto dos pontos do espaço ordinário (fixado um referencial). Para n > 3, não há possibilidade de interpretações geométricas intuitivas deste tipo. Em Geometria Anaĺıtica Plana faz-se corresponder à condição p(x, y) — onde x e y são variáveis reais — um subconjunto A de pontos do plano. 24 2.2. PARES ORDENADOS. SEQUÊNCIAS. PRODUTO CARTESIANO. RELAÇÕES. Essa correspondência é estabelecida com base na seguinte convenção: para que um ponto, (x0, y0), pertença ao conjunto A é necessário e suficiente que p(x0, y0) seja uma proposição verdadeira; para exprimir esta ideia, pode também escrever-se, como sabemos: A = {(x, y) : p(x, y)}. Assim, por exemplo, às condições y = 2x e y > x — que exprimem certas “relações” entre x e y : “y é o dobro de x”, “y é maior do que x” — correspondem respectivamente, uma determinada recta e um determinado semiplano (observe-se, porém, que a mesma recta e o mesmo semiplano corresponderiam também, por exemplo, às condições 10y = 100x e y3 > x3, equivalentes a y = 2x e y > x, respectivamente). Em sentido inverso, se for fixado um conjunto de pontos do plano, é também natural pensar que ficará assim definida uma “relação entre x e y”: por exemplo, à bissectriz dos quadrantes pares — isto é, ao conjunto de todos os pontos (x, y) tais que x + y = 0 — corresponderia a relação de simetria (“y é o simétrico de x”); à circunferência de centro na origem e raio 1, ficaria associada uma relação que poderia exprimir-se dizendo que “a soma dos quadrados de x e y é igual à unidade”, etc. Note-se que, nas considerações precedentes, o termo “relação” (que não foi ainda definido) tem estado a ser utilizado na sua acepção intuitiva; tem- se apenas em vista sugerir que a cada “relação” das que foram consideradas, pode associar-se um conjunto de pares ordenados de tal forma que, conhecido este conjunto, poderá dizer-se, em certo sentido, que ficará determinada a relação considerada. Um outro exemplo: seja H o conjunto dos homens e M o conjunto das mulheres, residentes em determinada localidade. Uma relação entre M e H (ou entre elementos de M e elementos de H) é a que se exprime pela condição “y é o marido de x” (com x ∈ M e y ∈ H). Neste caso, para quem dispusesse de uma lista de todos os “casais” (x, y), seria fácil, escolhidos arbitrariamente dois elementos, um de M e outro de H, verificar se eles constituiam ou não um casal, isto é, se estavam ou não na relação considerada. Uma vez mais, o conhecimento de um conjunto de pares ordenados equivaleria ao conhecimento da relação em causa. Consideremos agora a condição “X é o ponto médio do segmento de ex- tremos Y e Z” (onde pode supor-se que o domı́nio de qualquer das variáveis X, Y e Z é o espaço ordinário). Esta condição exprime uma relação que pode ser ou não ser verificada por três pontos X, Y e Z arbitrariamente escolhidos (e considerados por certa ordem); do ponto de vista que temos vindo a desenvolver, a essa relação corresponde um conjunto, cujos elemen- tos são todos os ternos ordenados (U, V,W ) tais que “U , V , W são pontos do espaço ordinário e U é o ponto médio do segmento que tem V e W por extremos”. Trata-se, desta vez, de uma relação que faz intervir três objectos (relação ternária). 25 CAPÍTULO 2. ELEMENTOS DE TEORIA DOS CONJUNTOS. Analogamente, à condição “os pontos P , Q, R e S são complanares” cor- responde um certo conjunto de quaternos ordenados (relação quaternária), etc. Os exemplos anteriores contribuirão talvez para tornar menos artifici- ais as definições seguintes, que enunciaremos nos termos abstractos carac- teŕısticos da teoria dos conjuntos: Chama-se relação binária a qualquer conjunto de pares ordenados. Mais explicitamente: diz-se que um conjunto A é uma relação binária sse cada um dos elementos que o constituem é um par ordenado, isto é, sse: ∀z∈A∃x,y z = (x, y). Se G é uma relação binária, em vez de dizer que o par (a, b) pertence a G, diz-se também que o elemento a está na relação G com o elemento b e escreve-se, por vezes, a G b. Consideremos, por exemplo, a relação binária entre números reais que habitualmente se representa pelo sinal <. De acordo com a definição an- terior, essa relação é um conjunto de pares, tais como (2, 3), (−1, 5), etc. Em vez de dizer que o par (2, 3) pertence à relação considerada, diz-se de preferência que 2 está nessa relação com 3 (ou que “2 é menor do que 3”) e escreve-se 2 < 3. De forma análoga, uma relação ternária é, por definição, qualquer con- junto de ternos ordenados; mais geralmente, sendo n ∈ N , chama-se relação n-ária a qualquer conjunto formado por sequências de n objectos. As- sim, por exemplo, são relações n-árias os conjuntos de todas as sequências (x1, x2, . . . , xn) de n números reais que verificam uma qualquer das três condições seguintes: 1a) x1 + x2 + . . . + xn = 0, 2a) x21 + x 2 2 + . . . + x 2 n = 0, 3a) x21 + x 2 2 + . . . + x 2 n + 1 = 0. Observe-se de passagem que, no 1o caso, há infinitas sequências que perten- cem à relação considerada (se n > 1); no 2o caso, a relação é constitúıda por uma única sequência: a sequência nula, formada por n zeros; no 3o, a relação não contem sequência alguma (relação vazia). No que vai seguir-se, as relações que terão maior interesse para nós serão as relações binárias; aliás, nesta parte do curso, quase nunca nos referiremos a outras. Convencionamos por isso que o termo “relação” deverá de aqui em diante ser interpretado como abreviatura da expressão “relação binária” (salvo algum caso em que seja evidente que tal interpretação é inaceitável). Sendo A e B dois conjuntos, qualquer subconjunto do produto cartesiano A × B é, evidentemente, um conjunto de pares ordenados, e portanto uma relação: é o que por vezes se chama uma relação entre os conjuntos A e 26 2.3. FUNÇÕES. APLICAÇÕES. INVERSÃO. COMPOSIÇÃO. à coluna dos y o contradomı́nio. Evidentemente, tratando-se de facto de uma função, se figurarem, em duas linhas, os pares (x, y) e (x, z), ter-se-á necessariamente y = z. Em vez de dizer que uma função F tem por domı́nio o conjunto A, diz-se também que F é uma função definida em A. Seja F uma função e x um elemento qualquer do seu domı́nio; chama-se valor de F em x (ou valor de F no ponto x) o (único) objecto y tal que (x, y) ∈ F . O valor de F no ponto x é habitualmente designado por F (x), podendo então escrever-se y = F (x) em lugar de (x, y) ∈ F . Quando se pretende definir uma função é geralmente prefeŕıvel, em vez de indicar explicitamente os pa- res que a constituem, descrever o seu domı́nio e, para cada valor de x nesse domı́nio, indicar como pode obter-se o correspondente valor da função. Por exemplo, o conjunto de todos os pares (x, x2), com x ∈ R é evidentemente uma função, f . Para descrevê-la, poderá dizer-se: f é a função definida em R tal que f(x) = x2(∀x ∈ R). Sendo A e B dois conjuntos quaisquer, designa-se por aplicação de A em B qualquer função cujo domı́nio seja A e cujo contradomı́nio seja uma parte de B 4. Para indicar que f é uma aplicação de A em B pode escrever-se f : A → B. Evidentemente, sempre que f seja uma aplicação de A em B, ter-se-á, por definição, Df = A, Cf ⊂ B. No caso particular de ser Cf = B, diz-se que a aplicação f é sobrejectiva (ou que f é uma sobrejecção) de A em B; dizer que f : A → B é uma sobrejecção equivale portanto a afirmar que é verdadeira a proposição ∀y∈B∃x∈A y = f(x) Por outro lado, uma aplicação f : A → B diz-se injectiva (ou uma injecção) sse, para cada y ∈ B, existe quando muito um x ∈ A tal que y = f(x); doutra forma, dizer que f é injectiva equivale a dizer que: ∀x′,x′′∈A x′ 6= x′′ =⇒ f(x′) 6= f(x′′), ou, o que é o mesmo: ∀x′,x′′∈A f(x′) = f(x′′) =⇒ x′ = x′′. Diz-se ainda que f : A → B é bijectiva (ou que é uma bijecção) sse f é injectiva e sobrejectiva. Às aplicações bijectivas de A em B chama-se também correspondências biuńıvocas entre A e B5. 4Em vez de aplicação de A em B diz-se também por vezes função definida em A e com valores em B. 5Usam-se também as expressões: aplicação de A sobre B, aplicação biuńıvoca de A em B, a aplicação biuńıvoca de A sobre B para significar respectivamente, aplicação sobrejectiva, injectiva e bijectiva de A em B. 29 CAPÍTULO 2. ELEMENTOS DE TEORIA DOS CONJUNTOS. Exemplos 1. A aplicação f : R → R, tal que f(x) = x2(∀x ∈ R) não é injectiva (por exemplo, f(−3) = f(3)), nem sobrejectiva (não existe x ∈ R tal que f(x) = −1). 2. A aplicação g : N → N, definida por g(x) = x2, é injectiva mas não sobrejectiva (não existe x ∈ N que g(x) = 2). 3. A aplicação D : D → {0, 1} definida por D(x) = { 0 se x é racional, 1 se x é irracional, (aplicação por vezes chamada função de Dirichlet) é sobrejectiva mas não injectiva. 4. A aplicação Ψ : R → R,Ψ(x) = x3 é uma bijecção. Seja f uma aplicação de A em B. Como qualquer relação, f admite uma relação inversa, f−1. Em geral, porém, f−1 não é uma função. Quais serão então as aplicações f para as quais f−1 é uma função? A resposta é fácil: para que f−1 seja uma função deve ter-se: ∀x′,x′′∈A f(x′) = f(x′′) =⇒ x′ = x′′ o que, como vimos, significa que f é injectiva. Assim, a relação inversa f−1 de uma aplicação f : A → B é uma função, sse f é injectiva. Em tal caso, chama-se a f−1 a função inversa ou a aplicação inversa de f . Sejam A, B e C três conjuntos, f uma aplicação de A em B e g uma aplicação de B em C. A cada x ∈ A corresponde, por meio de f , um único elemento y = f(x) ∈ B; por sua vez g, aplicação de B em C, associa a esse y um e um só z = g(y) ∈ C. Assim, aplicando, sucessivamente f e g, faz-se corresponder a cada x ∈ A um único elemento z = g(f(x)) ∈ C, definindo-se portanto uma aplicação de A em C, que se chama aplicação composta de f e g. Em resumo: chama-se aplicação composta de f e g e designa-se por g ◦ f a aplicação de A em C definida por (g ◦ f)(x) = g(f(x)) (∀x ∈ A). Consideramos, por exemplo, as aplicações: ϕ : R → R, ϕ(x) = senx, Ψ : R → R, Ψ(x) = x2. 30 2.3. FUNÇÕES. APLICAÇÕES. INVERSÃO. COMPOSIÇÃO. Tem-se: (Ψ ◦ ϕ)(x) = Ψ(ϕ(x)) = (senx)2 = sen2 x, (ϕ ◦Ψ)(x) = sen(x2) e também: (ϕ ◦ ϕ)(x) = sen(senx), (Ψ ◦Ψ)(x) = x4. Por outro lado, se fôr θ : N → R, θ(x) = √x, ter-se-á ainda: (ϕ ◦ θ)(x) = sen√x (∀x ∈ N) (Ψ ◦ θ)(x) = x (∀x ∈ N), mas as composições θ ◦ ϕ, θ ◦ Ψ não poderão formar-se (notar que a com- posição de duas aplicações f e g só foi definida na hipótese de ser f : A → B e g : B → C; ver, no entanto, uma nota ulterior). O exemplo anterior revela, em particular, que a composição de aplicações não é uma operação comutativa: existindo f ◦ g e g ◦ f pode ter-se f ◦ g 6= g ◦ f (pode também acontecer que uma das composições tenha sentido e a outra não ou que qualquer delas o não tenha). É fácil, porém provar que a composição de aplicações é associativa, isto é, que, sendo f : A → B, g : B → C e h : C → D, se tem sempre h ◦ (g ◦ f) = (h ◦ g) ◦ f. Deixaremos a demonstração como exerćıcio. Sendo A um conjunto qualquer, chama-se aplicação idêntica em A à aplicação : IA : A → A definida por IA(x) = x (∀x ∈ A). É evidente que a aplicação IA é uma bijecção e que a inversa, A −1, é a própria aplicação IA. Já sabemos que se ϕ : A → B é uma aplicação bijectiva, a inversa ϕ−1 é também uma bijecção (de B em A). Tem-se então, como logo se reconhece: (ϕ−1 ◦ ϕ)(x) = x ∀x ∈ A, (ϕ ◦ ϕ−1)(y) = y ∀y ∈ B, isto é, ϕ−1 ◦ ϕ = IA, ϕ ◦ ϕ−1 = IB . 31 CAPÍTULO 2. ELEMENTOS DE TEORIA DOS CONJUNTOS. 10. Recordando que uma função foi definida como sendo um conjunto de pares ordenados (com certa propriedade especial) e tendo em conta a definição de igualdade de conjuntos, prove que duas funções f e g são iguais sse (Df = Dg) ∧ (∀x∈Df f(x) = g(x)). 11. Prove que se f : A → B e g : B → C são injectivas (resp. sobrejectivas) g ◦ f é injectiva (resp. sobrejectiva). 12. Prove que f : A → B é uma bijecção sse existe g : B → A tal que f ◦ g = IB e g ◦ f = IA. 13. Sendo A e B dois conjuntos, diz-se que A é equipotente a B e escreve- se A ≈ B sse existe uma bijecção f : A → B. Prove que, quaisquer que sejam A, B e C, se tem: a) A ≈ A. b) A ≈ B ⇐⇒ B ≈ A. c) A ≈ B ∧ B ≈ C =⇒ A ≈ C. 2.4 Relações de equivalência. Relações de ordem. Seja A um conjunto não vazio. Uma relação G no conjunto A, diz-se uma relação de equivalência sse forem verificadas as propriedades seguintes: ∀x∈A xGx (reflexividade), ∀x,y∈A xGy =⇒ y Gx (simetria), ∀x,y,z∈A xGy ∧ y G z =⇒ xGz (transitividade). São relações de equivalência, por exemplo, a relação de “igualdade” (num conjunto qualquer), a relação de paralelismo (no conjunto das rectas do espaço, e admitindo que se considera a coincidência como caso particular do paralelismo), a relação de “semelhança” (entre triângulos, por exemplo), a relação de “equipotência”, entre subconjuntos de um conjunto arbitário (cf. exerćıcio 13), etc. Não são relações de equivalência: a relação de “perpen- dicularidade”, entre rectas (não é reflexiva, nem transitiva), as relações de “divisor” entre números naturais e de “contido” entre conjuntos (não são simétricas), a relação de “maior” (não é reflexiva, nem simétrica). Fixada uma relação de equivalência G num conjunto A, diz-se que dois elementos a, b de A são equivalentes (segundo G) sse aG b. Nas mesmas condições, sendo c um elemento qualquer de A, chama-se classe de equi- valência de c (segundo G) e designa-se usualmente por G[c], ou apenas [c], o conjunto de todos os elementos de A que são equivalentes a c: x ∈ [c] ⇐⇒ xGc. 34 2.4. RELAÇÕES DE EQUIVALÊNCIA. RELAÇÕES DE ORDEM. No caso da relação de paralelismo, a classe de equivalência de uma recta é o conjunto de todas as rectas que têm a mesma direcção do que a recta dada; para a relação de igualdade num conjunto X, tem-se para qualquer elemento c ∈ X, [c] = {c} (isto é, a classe de equivalência de c tem um único elemento: o próprio c). Demonstraremos agora o seguinte: Teorema. Seja G uma relação de equivalência no conjunto A, a e b ele- mentos quaisquer de A. Tem-se então: 1) a ∈ [a]. 2) aG b ⇐⇒ [a] = [b]. 3) ∼ (a G b) ⇐⇒ [a] ∩ [b] = ∅. Demonstração: 1) Para provar que a pertence à sua própria classe de equivalência, basta atender à definição desta classe e ao facto de que, por hipótese, a é equivalente a si próprio (visto que a relação G é reflexiva). Observe-se que de aqui resulta, em particular, que nenhuma classe de equivalência é vazia. 2) Para provar que, se a e b são equivalentes têm a mesma classe de equi- valência, suponha-se, de facto, aG b e observe-se que, se c é um elemento qualquer de [a] tem-se (por definição de [a]) cGa e portanto também, pela transitividade de G, cG b, isto é c ∈ [b]. Fica assim provado que [a] ⊂ [b] e, como poderia provar-se da mesma forma que [b] ⊂ [a], pode concluir-se que [a] = [b]. Reciprocamente, se [a] = [b], tem-se, por (1), a ∈ [b] e portanto aG b. 3) Para reconhecer que as classes de equivalência de dois elementos não equivalentes são disjuntas — ou, o que é o mesmo que, se [a] ∩ [b] 6= ∅, se tem necessariamente, aG b — basta notar que, sendo c ∈ [a] ∩ [b], ter-se-á cGa (visto que c ∈ [a]) e cG b (visto que c ∈ [b]). Logo, atendendo à simetria de G, ter-se-á também aG c e cG b e finalmente, pela transitividade, aG b. Em sentido inverso observe-se que, por (2), aG b =⇒ [a] = [b] e portanto, como uma classe de equivalência não pode ser vazia, [a] ∩ [b] 6= ∅.  Introduziremos ainda a seguinte definição: Sendo G uma relação de equivalência num conjunto A, chama-se con- junto quociente de A (segundo G) e designa-se por A/G o conjunto formado pelas classes de equivalência (segundo G) de todos os elementos de A. Por exemplo, no caso de G ser a relação de igualdade no conjunto A, A/G é o conjunto de todas as partes de A que têm apenas um elemento. Se G for 35 CAPÍTULO 2. ELEMENTOS DE TEORIA DOS CONJUNTOS. a relação de equivalência, no conjunto das pessoas (não apátridas), definida por: xGy ⇐⇒ x tem a mesma nacionalidade que y, cada uma das classes de equivalência segundo G será formada por todas as pessoas que têm uma determinada nacionalidade e o conjunto quociente corresponderá, de certo modo, ao conjunto de todas as nacionalidades. Nota. Como exemplo particularmente significativo da utilização da noção de conjunto quociente em Matemática, indicaremos nesta nota o processo usualmente adoptado para definir o conjunto Z dos números inteiros (0, ±1, ±2,. . . ) a partir do conjunto dos naturais, N, que, por agora, suporemos previamente conhecido. A definição pode indicar-se em poucas palavras (mas só poderá ser bem compreendida se se tiver em conta a motivação que será indicada posteriormente): Considere-se o conjunto N2, de todos os pares ordenados de números naturais, N2 = {(a, b) : a, b ∈ N} e, neste conjunto, a relação de equivalência G definida da seguinte forma: (a, b) G (c, d) ⇐⇒ a + d = b + c. Nestas condições, o conjunto Z dos números inteiros é, por definição, o conjunto quociente N2/G. Qual a ordem de ideias que pode conduzir naturalmente a esta definição? Para a apreender comecemos por lembrar que a consideração do conjunto Z é essencialmente motivada por uma “insuficiência” do conjunto dos naturais: o facto de nem sempre ser posśıvel em N a operação de subtracção. Na realidade, supondo a, b ∈ N, a equação em x: a + x = b só tem solução em N se fôr a < b. Como esta limitação é indesejável, do ponto de vista algébrico, surge naturalmente a ideia de construir um sobreconjunto Z do conjunto N, no qual a equação anterior já tenha solução, quaisquer que sejam a e b. Nesse sentido, observemos primeiramente que, quando a equação consi- derada tem solução em N — isto é, quando a < b — essa solução é única (x = b − a). Pode exprimir-se este facto dizendo que a cada par (a, b) de números naturais, que verifique a condição a < b, corresponde um e um só natural x, que é solução da equação considerada. Note-se, porém, que a correspondência assim estabelecida entre os números naturais x e os pa- res ordenados (a, b) ∈ N2, tais que a < b, não é biuńıvoca; por exemplo, a qualquer dos pares (1, 5), (2, 6), (3, 7), . . . corresponde o mesmo natural, 4 (solução comum das equações 1 + x = 5, 2 + x = 6, . . .). 36 2.4. RELAÇÕES DE EQUIVALÊNCIA. RELAÇÕES DE ORDEM. O conjunto dos racionais Q é, por definição o quociente W/S. Quanto às operações algébricas, designando por b a a classe de equivalência a que per- tence o par (a, b) — o que, aliás, poderá lançar alguma luz sobre a razão que levou a definir a relação S pela forma indicada. . .— pôr-se-á, por definição: b a + d c = ad + bc a · c , b a · d c = b · d a · c . Cada número inteiro c será “identificado” com um racional, precisa- mente o racional c1 , passando então a ter-se N ⊂ Z ⊂ Q. Também neste caso podem deduzir-se sem dificuldade as propriedades operatórias já conhe- cidas, o que não faremos. Seja A um conjunto qualquer e suponhamos fixada uma relação binária no conjunto A, relação que designaremos pelo śımbolo ≺ (que pode ler- se “precede”). Diz-se que ≺ é uma relação de ordem parcial sse forem verificadas as propriedades seguintes: ∀x,y∈A x ≺ y =⇒ x 6= y (anti-reflexividade), ∀x,y∈A x ≺ y =⇒∼ (y ≺ x) (anti-simetria), ∀x,y,z∈A x ≺ y ∧ y ≺ z =⇒ x ≺ z (transitividade). Se, além destas propriedades, se tiver: ∀x,y∈A x ≺ y ∨ x = y ∨ y ≺ x (tricotomia) a relação ≺ dir-se-á uma relação de ordem total , ou simplesmente uma relação de ordem. Como exemplos de relações de ordem, registaremos: a relação de < (ou a de >), no conjunto dos reais, R (ou em qualquer dos conjuntos N, Z, Q) e a relação determinada, no conjunto de todas as pa- lavras da ĺıngua portuguesa, pela condição “x precede alfabeticamente y”. Como exemplos de relações de ordem parcial (além dos anteriores, visto que qualquer relação de ordem total é também uma relação de ordem parcial) indicaremos ainda a relação de “inclusão estrita” — isto é, a relação defi- nida pela condição X ⊂ Y ∧ X 6= Y — entre as partes de um conjunto qualquer, a relação de “divisor estrito” no conjunto dos inteiros 7, a relação de “descendente” no conjunto dos seres humanos, etc. Um conjunto A diz-se ordenado (ou totalmente ordenado), quando es- tiver fixada uma relação de ordem em A; da mesma forma, um conjunto no qual se tenha fixado uma relação de ordem parcial é um conjunto parci- almente ordenado. Dada uma relação de ordem ≺ (total ou parcial), num 7“x é divisor estrito de y” equivale a “x divide y e x 6= y”. 39 CAPÍTULO 2. ELEMENTOS DE TEORIA DOS CONJUNTOS. conjunto A, chama-se relação de ordem lata associada a ≺, a relação ≺ definida pela forma seguinte: x ≺ y ⇐⇒ x ≺ y ∨ x = y. Por exemplo, a relação de ≤, no conjunto dos reais é a relação de ordem lata associada à relação <; as relações latas associadas às de “estritamente contido” e de “divisor estrito” são as relações de “contido” e de “divisor”, respectivamente. Facilmente se verifica que, sendo ≺ uma relação de ordem parcial no conjunto A, a relação de ordem lata associada a ≺ tem as propriedades: ∀x∈A x ≺ x (reflexividade), ∀x,y∈A x ≺ y ∧ y ≺ x =⇒ x = y (anti-simetria lata), ∀x,y,z∈A x ≺ y ∧ y ≺ z =⇒ x ≺ z (transitividade) e que, se ≺ for uma relação de ordem total, se tem ainda: ∀x,y∈Ax ≺ y ∨ y ≺ x (dicotomia). Consideremos agora um conjunto (totalmente) ordenado A e, para maior comodidade, designemos pelo śımbolo <, que leremos mesmo “menor”, a relação de ordem fixada em A. Introduzamos ainda as habituais convenções de notação: a > b ⇐⇒ b < a, a ≥ b ⇐⇒ a > b ∨ a = b, a < b < c ⇐⇒ a < b ∧ b < c, a ≤ b < c ⇐⇒ a ≤ b ∧ b < c, etc. Nestas condições, sendo a e b elementos de A tais que a ≤ b, chama-se intervalo fechado de extremos a e b (no conjunto A) e designa-se por [a, b], o conjunto: [a, b] = {x : x ∈ A ∧ a ≤ x ≤ b} Define-se analogamente o intervalo aberto de extremos a e b: ]a, b[ = {x : x ∈ A ∧ a < x < b} e os intervalos semifechados: [a, b[ = {x : x ∈ A ∧ a ≤ x < b} ]a, b] = {x : x ∈ A ∧ a < x ≤ b} 40 2.4. RELAÇÕES DE EQUIVALÊNCIA. RELAÇÕES DE ORDEM. Seja agora X um subconjunto qualquer de A. Diz-se que um elemento c de A é um minorante de X sse ∀x∈X c ≤ x. Evidentemente, se c for um minorante de X, qualquer elemento c′ ∈ A tal que c′ ≤ c será também um minorante de X. Diz-se que o conjunto X é minorado (ou limitado inferiormente) sse X tiver pelo menos um minorante; assim, dizer que X é minorado equivale a afirmar que ∃c∈A∀x∈X c ≤ x. Analogamente, chama-se majorante de X a qualquer elemento d ∈ A tal que ∀x∈X x ≤ d e diz-se que o conjunto X é majorado (ou limitado superiormente) sse ∃d∈A∀x∈X x ≤ d. Um conjunto X ⊂ A que seja minorado e majorado diz-se um conjunto limitado; portanto, X é limitado sse ∃c,d∈A∀x∈X c ≤ x ≤ d. Exemplos: (considerando sempre como conjunto ordenado — isto é, no lugar do conjunto A das definições precedentes — o conjunto R, com a relação de ordem < usual): N é um conjunto minorado (qualquer número real ≤ 1 é um minorante) mas não majorado nem, portanto, limitado; o conjunto Q−, dos racionais negativos é majorado (são majorantes os reais ≥ 0) mas também não é limitado; é limitado o conjunto dos reais que verificam a condição x2 < 4, que é precismente o intervalo ] − 2, 2[ e que tem por minorantes os reais ≤ −2 e por majorantes os reais ≥ 2. Dado um subconjunto X do conjunto ordenado A pode existir ou não em X um elemento menor do que todos os outros, isto é, um elemento a tal que: 1) a ∈ X, 2) ∀x∈X a ≤ x. É fácil, porém, reconhecer que, se existir um elemento a nas condições indicadas, esse elemento é único: basta observar que, se a e a′ verificam as condições (1) e (2), se tem necessariamente a′ ≤ a e a ≤ a′, donde resulta a = a′. Um tal elemento a (quando existe) é chamado o mı́nimo do conjunto X e designado por minX. Define-se de forma análoga o máximo de X (maxX): b é máximo de X sse 41 CAPÍTULO 2. ELEMENTOS DE TEORIA DOS CONJUNTOS. 5. Sendo A um conjunto qualquer, chama-se partição de A a qualquer conjunto P de partes de A não vazias, disjuntas duas a duas e cuja reunião seja A; à relação ρ, no conjunto A, definida por x ρ y ⇐⇒ ∃B∈P x ∈ B ∧ y ∈ B é uma relação de equivalência. Qual é o conjunto quociente, A/ρ? Prove também que qualquer relação de equivalência em A determina, por sua vez, uma partição de A, formada pelas correspondentes classes de equivalência. 6. Prove que, para que uma relação binária ≺ num conjunto A seja uma relação de ordem (total), é necessário e suficiente que sejam satisfeitas as duas propriedades seguintes: 1a — transitividade, 2a — sendo x e y elementos quaisquer de A, verifica-se necessaria- mente uma e uma só das condições: x ≺ y, x = y, y ≺ x. 7. No conjunto ordenado R com a ordenação usual, verifique se são majo- rados, minorados e limitados os conjuntos considerados nos exerćıcios 8 e 9 da secção 2.1 e, se posśıvel, determine máximos, mı́nimos, supre- mos e ı́nfimos dos mesmos conjuntos. 8. Questões análogas às do exerćıcio 7, para os conjuntos de números reais definidos pelas fórmulas: a) 1 + 2 n , b) n n− 1 2 , c) 1− 1 n , d) (−1)n n+1 n , e) (1 + 1 n ) · sennπ2 , f) 1+(−1) n 2+(−1)n+1 . onde se supõe que n assume todos os valores naturais. 9. Considere como conjunto ordenado total o conjunto Q, dos racionais, com a usual relação de <, e verifique que o subconjunto X de Q definido por: X = {x : x ∈ Q ∧ x2 < 2} é majorado mas não tem supremo. 10. Prove que, se X e Y são subconjuntos limitados de um conjunto or- denado A, X ∩ Y e X ∪ Y são também limitados. 44 2.4. RELAÇÕES DE EQUIVALÊNCIA. RELAÇÕES DE ORDEM. 11. Sendo X e Y partes de um conjunto ordenado A, tais que X ⊂ Y e supondo que existem supX e supY , prove que supX ≤ supY . 45 CAPÍTULO 2. ELEMENTOS DE TEORIA DOS CONJUNTOS. 46 ÍNDICE REMISSIVO função, 28 de Dirichlet, 30 inversa, 30 vazia, 32 igualdade de pares ordenados, 22 imagem, 32 imagem inversa, 32 imagem rećıproca, ver imagem inversa implicação, 9 formal, 7, 11 inclusão, 18 ı́nfimo, 42 injecção, ver aplicação injectiva injectiva, ver aplicação injectiva intersecção, 19 intervalo aberto, 40 fechado, 40 semifechado, 40 leis de De Morgan, 7, 11 limitada, ver sucessão limitada limitado inferiormente, 41 superiormente, 41 máximo, 6, 41 mı́nimo, 6, 41 majorado, 41 majorante, 41 minorado, 41 minorante, 41 negação, 7 par, 22 ordenado, 22 parte, 18 estrita, 18 própria, ver estrita partição, 44 pertença, 17 potência cartesiana, 24 primeiras leis de De Morgan, 7 produto cartesiano, 23 produto lógico, ver conjunção projecção, 22 proposições, 5 quadrado cartesiano, 23 quantificador, 10 existencial, 10 universal, 10 relação n-ária, 26 binária, 26 de equivalência, 34 de inclusão, 20 de ordem, 39 lata, 40 parcial, 39 total, 39 de pertença, 20 entre conjuntos, 26 inversa, 27 num conjunto, 27 quaternária, 26 rećıproca, 27 reflexiva, 35 ternária, 25, 26 restrição, 32 reunião, 19 segundas leis de De Morgan, 11 sequência, 22 simetria, 25 sobreconjunto, 18 sobrejecção, ver aplicação sobrejec- tiva sobrejectiva, ver aplicação sobrejec- tiva soma lógica, 6 subconjunto, 18 sucessão limitada, 13 supremo, 42 termos, 5 terno ordenado, 22 49 ÍNDICE REMISSIVO transformado, ver imagem transitividade, 39 tricotomia, 39 valor lógico, 6 variáveis, 8 variável livre, 12 não quantificada, 12 50
Docsity logo



Copyright © 2024 Ladybird Srl - Via Leonardo da Vinci 16, 10126, Torino, Italy - VAT 10816460017 - All rights reserved