Álgebra, Manuais, Projetos, Pesquisas de Matemática

Baixe Álgebra e outras Manuais, Projetos, Pesquisas em PDF para Matemática, somente na Docsity! UNIVERSIDADE DE BRASÍLIA DEPARTAMENTO DE MATEMÁTICA -IE ÁLGEBRA I (Álgebra Abstrata) Texto de aula Professor Rudolf R. Maier Versão atualizada 2005 Índice CAPÍTULO I Teoria Elementar dos Conjuntos pg. § I.0 Fundamentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Algumas observações sobre lógica elementar Conceitos primitivos e conjuntos Igualdade entre conjuntos Subconjuntos Diferença e complementar Reunião e interseção Uma propriedade fundamental do conjunto IN O conjunto das partes O teorema binomial O triângulo de Pascal § I.1 Produtos Cartesianos e Relações . . . . . . . . . . . . . . . 23 Produtos Cartesianos Relações Relação inversa Composição de relações Relações de equivalência § I.2 Aplicações (funções) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Definição e exemplos Composição de aplicações A caracterização das aplicações entre as relações Aplicações injetoras, sobrejetoras e bijetoras Conjuntos equipotentes A decomposição canónica de uma aplicação O axioma da escolha As ordens |Inj (m,n)| e |Sob (m,n)| i (A validade de) A é condição suficiente para (a validade de) B , ou B é condição necessária para A , ou A vale somente se B vale, ou B vale se A vale, ou ainda Se A , então B . É claro que A B B ⇐= A ou também ⇓ ou ⇑ B A significam o mesmo quanto A =⇒ B . Vejamos exemplos: Seja A a asserção : ”um certo número natural n é múltiplo de 4 ” (dependendo do n, isto pode ser verdadeiro ou falso), B a asserção : ”n é par ” . Claramente temos neste caso A =⇒ B , pois sempre se n é múltiplo de 4, concluimos que n é par. Assim, podemos dizer : ”n ser múltiplo de 4” implica que ”n é par ”. ”n ser múltiplo de 4” é condição suficiente para ”n ser par ”. ”n ser par ” é condição necessária para ”n ser múltiplo de 4 ”. ”n é múltiplo de 4 ” somente se ”n é par ”. ”n é par ”, se ”n é múltiplo de 4 ”. ”se n é múltiplo de 4 ”, então ”n é par ” . Um outro exemplo: Seja A a asserção : ”está chovendo ” (também isto pode ser verdadeiro ou falso aqui e agora), B a asserção : ”a praça está molhada ”. Também neste caso temos A =⇒ B , pois, se realmente está chovendo, temos certeza que a praça está molhada. Assim, 2 podemos dizer : ”estar chovendo ” implica que ” a praça está molhada ” ”estar chovendo ” é condição suficiente para termos ”uma praça molhada ” ”uma praça molhada ” é condição necessária para ”estar chovendo ” ”está chovendo ” somente se ” a praça está molhada ” ”a praça está molhada se está chovendo ” se ”está chovendo ”, então ”a praça está molhada ” Exerćıcio. Pensando-se num certo quadrângulo Q, façam o mesmo com as asserções A : ”Q é um quadrado ” B : ”Q é um losângo ”. É claro que a seta numa implicação A =⇒ B não pode ser simplesmente invertida: A é condição suficiente para B significa que B é condição necessária para A , mas não que B é condição suficiente para A : O fato de ”n ser par ” é condição necessária mas não suficiente para ”n ser múltiplo de 4 ”. O fato de ”n ser múltiplo de 4 ” é condição suficiente mas não necessária para ”n ser par ”: Também 6 é par sem ser múltiplo de 4. O fato de termos ”uma praça molhada ” é condição necessária mas não suficiente para ”estar chovendo ”. O fato de ”estar chovendo ” é condição suficiente mas não necessária para termos ”uma praça molhada ” : A praça pode estar molhada sem que esteja chovendo (por exemplo devido a uma operação dos bombeiros). Existem asserções A e B que ambas implicam na outra, ou seja, as quais satisfazem simultâneamente A =⇒ B e B =⇒ A . Nesta situação temos então que A é suficiente para B e também A é necessário para B . Dizemos que A é (condição) necessário(a) e suficiente para B , ou também A vale se e somente se vale B . Este fato indicamos por A ⇐⇒ B . 3 Dizemos também que A e B são asserções equivalentes, ou ainda que A constitui uma propriedade caracteŕıstica para B (e vice versa). Por exemplo: Seja A a asserção : ” n é múltiplo de 6 ”, B a asserção : ”n é um número par que é múltiplo de 3 ”. Cada uma destas duas propriedades, as quais um número n pode ter ou não, é suficiente para a outra. Cada uma é necessária para a outra. Cada uma é necessária e suficiente para a outra. Cada uma vale se e somente se a outra vale. Exerćıcio. Pensar sobre as asserções equivalentes, quando Q é um certo quadrângulo: A : ”Q é um quadrado ” B : ”Q é um losângo que é um retângulo ”. Se A é uma asserção, indicamos por Ā a asserção ”não - A ”, a qual é verdadeira se e somente se A é falsa. Sejam A e B duas asserções e suponha A =⇒ B . O que acontece com esta implicação se negarmos as duas asserções ? A resposta é que devemos também inverter a seta da implicação , ou seja, teremos Ā ⇐= B̄. Em outras palavras: Se A é suficiente para B , então B̄ é suficiente para Ā. Ou também: Se A é suficiente para B , então Ā é necessário para B̄. Por exemplo, se negarmos a implicação ”ser múltiplo de 4 é suficiente para ser par ”, a implicação negada é : ” não ser múltiplo de 4 é necessário para ser ı́mpar ”. Porém, não ser múltiplo de 4 não é suficiente para ser ı́mpar. Claro que numa equivalência podemos negar as asserções dos dois lados, ou seja, não importa se escrevemos 4 Como fonte de exemplos admitiremos também sem mais explicações : IR = o conjunto dos números reais , QI = { m n ∣∣∣ m ∈ ZZ, n ∈ IN } = o conjunto dos números racionais . I.0.6 Observação. Um conjunto A pode conter só uma quantidade finita de elementos distintos. Tal conjunto é denominado um conjunto finito. A quantidade dos elementos distintos nele contidos é um número natural (ou 0), indicado por |A|, é chamado de ordem de A. Temos por exemplo{ ∇,♠,♥,♣ } , { 1, 2, 3, 1, 3, 1, 3 , . . . , 3, 1, . . . } e { x ∈ ZZ ∣∣∣ x2 = 36} são conjuntos finitos. Suas ordens são ∣∣∣{∇,♠,♥,♣ }∣∣∣ = 4, ∣∣∣{1, 2, 3, 1, 3, 1, 3 , . . . , 3, 1, . . .}∣∣∣ = ∣∣∣{1, 2, 3}∣∣∣ = 3 e∣∣∣ {x ∈ ZZ ∣∣∣ x2 = 36}∣∣∣ = ∣∣∣{6,−6}∣∣∣ = 2 . Os conjuntos A = { a } que possuem um único elemento (i.e. |A| = 1) são de- nominados os conjuntos unitários. Por exemplo, temos A = { x ∈ IR ∣∣∣ x3 + 5 = 0} = {− 3√5} é um conjunto unitário. Subconjuntos I.0.7 Definição. Se A e B são dois conjuntos, dizemos que A é um subconjunto (ou uma parte) de B (também: B abrange A), se todo elemento de A fôr elemento de B, ou seja, se para todo elemento a, a implicação a ∈ A =⇒ a ∈ B fôr verdade. Escreve-se este fato como A ⊆ B ou também B ⊇ A. Temos A = B ⇐⇒ A ⊆ B e B ⊆ A. 7 I.0.8 Observação. Para quaisquer três conjuntos A, B, C temos as regras a) Sempre A ⊆ A (lei da reflexividade) b) Se A ⊆ B e B ⊆ A, entãoA = B (lei da anti-simetria) c) Se A ⊆ B e B ⊆ C, entãoA ⊆ C (lei da transitividade) Se A ⊆ B e A 6= B, escreve-se A ⊂ B, ou B ⊃ A. Às vezes também: A ⊂ 6= B ou B ⊃ 6= A, lido: A é um subconjunto próprio (parte própria) de B. Também: B abrange A própriamente. A ⊂ B significa então que todo elemento de A também é elemento de B, mas existe pelo menos um b ∈ B com b 6∈ A. Observamos que sempre vale a implicação A ⊂ B =⇒ A ⊆ B . Temos por exemplo, IN ⊆ IN 0 , IN 0 ⊆ ZZ, ZZ ⊆ QI e QI ⊆ IR. Mais abreviadamente: IN ⊆ IN 0 ⊆ ZZ ⊆ QI ⊆ IR , Na verdade, podemos até afirmar IN ⊂ IN 0 ⊂ ZZ ⊂ QI ⊂ IR , pois 0 ∈ IN 0 \ IN, −1 ∈ ZZ \ IN 0 , 12 ∈ QI \ ZZ e √ 2 ∈ IR \QI (ver I.0.9). Se A ⊆ B não é verdade para dois conjuntos A e B, escreve-se A 6⊆ B ou B 6⊇ A. Isto é lido: ”A não está contido em B ” ou também ”B não abrange A” e significa que existe pelo menos um a ∈ A com a 6∈ B. Por exemplo, se A = { n ∈ IN ∣∣∣ 2 divide n} = {2, 4, 6, 8, . . .} é o conjunto dos números naturais pares e B = { n ∈ IN ∣∣∣ 3 divide n} = {3, 6, 9, 12, . . .} 8 é o conjunto dos números naturais diviśıveis por 3, temos A 6⊆ B e também B 6⊆ A , pois 4 ∈ A, mas 4 6∈ B e também 3 ∈ B mas 3 6∈ A. Devemos advertir também que A 6⊆ B não necessáriamente significa B ⊂ A, como mostra nosso exemplo. Diferença e complementar I.0.9 Definição. Dado dois conjuntos A e B, indicamos por A \B = { a ∈ A ∣∣∣ a 6∈ B } o conjunto dos elementos em A que não estão em B. Este conjunto A \B é denominado a diferença A menos B. Mencionamos que A \B ⊆ A e B \ A ⊆ B. Por exemplo, se A = { 2, 4, 6, 8, . . . } e B = { 3, 6, 9, 12, . . . } , temos A \B = { 2, 4, 8, 10, 14, 16, . . . } e B \ A = { 3, 9, 15, 21, 27, . . . } , i.e. A \B é o conjunto dos números pares que não são múltiplos de 3, enquanto B \ A é o conjunto dos múltiplos de 3 que não são pares. No caso particular quando A e E são dois conjuntos tais que A ⊆ E, es- crevemos Cpt E (A) = E \ A e chamamos Cpt E (A) de conjunto complementar de A relativo a E. Por exemplo Cpt IR (QI) é o conjunto dos números irracionais . Claramente temos Cpt E ( Cpt E (A) ) = A . Se A = E, o conjunto complementar Cpt E (E) é caracterizado por Cpt E (E) = { a ∈ E ∣∣∣ a 6∈ E } 9 Demonstração: Para todo x ∈ E temos x ∈ Cpt E  n⋃ k=1 A k  ⇐⇒ x 6∈ n⋃ k=1 A k ⇐⇒ x 6∈ A k ∀ k ⇐⇒ ⇐⇒ x ∈ Cpt E ( A k ) ∀ k ⇐⇒ x ∈ n⋂ k=1 Cpt E ( A k ) . Da mesma forma x ∈ Cpt E  n⋂ k=1 A k  ⇐⇒ x 6∈ n⋂ k=1 A k ⇐⇒ ∃ k com x 6∈ A k ⇐⇒ ∃ k com x ∈ Cpt E ( A k ) ⇐⇒ x ∈ n⋃ k=1 Cpt E ( A k ) . Também faḿılias arbitrárias (posśıvelmente infintas) de conjuntos podem ser consideradas: Se E é um conjunto e F é uma faḿılia de subconjuntos de E colocamos⋃ X∈F X , a reunião de todos os conjuntos X ∈ F. Esta é o subconjunto dos elementos de E contidos em pelo menos um dos X ∈ F, enquanto⋂ X∈F X , a interseção de todos os conjuntos X ∈ F, é o subconjunto dos elementos de E contidos em todos os X ∈ F. Se F = { A1, A2 , . . . , An } é uma faḿılia finita, voltamos ao caso anterior. Dado um conjunto infinito E (por exemplo E = IN). F = { X ∣∣∣ X é um subconjunto finito de E } é um exemplo de uma famı́lia infinita. As regras de de Morgan podem ser formuladas agora assim: Cpt E  ⋃ X∈F X  = ⋂ X∈F Cpt E (X) e Cpt E  ⋂ X∈F X  = ⋃ X∈F Cpt E (X) . 12 Uma propriedade fundamental do conjunto IN A adição + em IN e também em ZZ, a qual queremos admitir sem mais explicações, dá origem a uma ordem natural ” ≤ ” em ZZ : ∀ n,m ∈ ZZ temos m ≤ n ⇐⇒ a equação m+ x = n possui uma solução x ∈ IN 0 . A seguinte propriedade do conjunto IN é fundamental : O prinćıpio da indução. Todo conjunto não vazio de números naturais possui um elemento mı́nimo. Em śımbolos : ∀ S, com 6O 6= S ⊆ IN ∃ m ∈ S tal que m ≤ n ∀ n ∈ S. Deste prinćıpio segue a importante I.0.16 Proposição. Seja T um conjunto de alguns números naturais (i.e. T ⊆ IN) satisfazendo às propriedades : a) 1 ∈ T b) Sempre se n ∈ T , então também n+1 ∈ T . Então T = IN é o conjunto de todos os números naturais. Demonstração: Suponhamos T 6= IN. Então vale S 6= 6O quando S = Cpt IN (T ) ⊆ IN é o conjunto complementar de T em IN. Pelo prinćıpio da indução existe m ∈ S tal que m ≤ n para todos os n ∈ S. Como 1 ∈ T pela propriedade a), temos 1 6∈ S, particularmente m > 1. Dáı concluimos n = m−1 ∈ T. Pela propriedade b) temos porém m = n+1 ∈ T, de onde sai o absurdo m ∈ S ∩ T = 6O. Isto mostra que S 6= 6O é imposśıvel. Temos que ter S = 6O e dáı T = IN. Esta fundamental proposição I.0.16 aplica-se para verificar a validade geral de fórmulas as quais envolvem números naturais, como mostra o seguinte 13 I.0.17 Exemplo. Para todos os números naturais n vale 1 + 3 + 5 + . . .+ (2n−3) + (2n−1) = n2 (∗) . Em palavras: A soma dos n primeiros números naturais ı́mpares é o n-ésimo quadrado perfeito. Demonstração: Seja T = { n ∈ IN ∣∣∣∣∣ n∑ k=1 (2k−1) = n2 } o conjunto dos números naturais para os quais a fórmula (∗) é verdadeira (o ”conjunto verdade” ou o ”conjunto de validade” de (∗)). Para mostrar que T = IN , só é preciso verificar a) e b) da Proposição I.0.16 para este T : Para n = 1 (∗) simplesmente afirma que 1 = 12, o que certamente é verdade, ou seja, 1 ∈ T . Suponhamos n ∈ T para algum número natural n, isto é, 1 + 3 + . . .+ (2n−1) = n2 . Somando-se 2n+1 a ambos os lados, obtemos 1 + 3 + . . .+ (2n−1) + (2n+1) = n2+2n+1 , de onde segue 1 + 3 + . . .+ (2n−1) + (2(n+1)−1) = (n+1)2 . Isto por sua vez significa n+1 ∈ T. Pela proposição concluimos que o conjunto verdade da fórmula (∗) é o conjunto T = IN de todos os números naturais. Vejamos mais um I.0.18 Exemplo. Para todos os números naturais n e todo real a 6= 1 vale 1 + a+ a2 + a3 + . . .+ an−1 + an = an+1−1 a− 1 . Particularmente (quando a = 2) obtemos 1 + 2 + 4 + . . .+ 2n−1 + 2n = 2n+1 − 1 . 14 vemos que 2A é um conjunto com 2 = 21 = 2 |A| elementos. Vamos supor A é um conjunto de n+1 elementos para algum n ∈ IN e podemos pensar que A = { 1, 2, 3 , . . . , n, ∗ } . Seja A∗ = { 1, 2, 3 , . . . , n } = A \ {∗}. Podemos supor que já foi provado que∣∣∣2A∗ ∣∣∣ = 2 |A∗| = 2n . Os 2n subconjuntos distintos de A∗ podemos escrever (sem especificação) como X1, X2, X3 , . . . , X2n−1, X2n . Agora, os subconjuntos Y de A se dividem em duas classes: Os Y que não contêm o elemento ∗ e os que contêm ∗. Portanto, os subconjuntos distintos de A são X1, X2, X3 , . . . , X2n−1, X2n junto com X1 ∪ {∗}, X2 ∪ {∗}, X3 ∪ {∗} , . . . , X2n−1 ∪ {∗}, X2n ∪ {∗}. Vemos que A possui um total de 2 vezes 2n subconjuntos distintos. Mas isto quer dizer que ∣∣∣2A ∣∣∣ = 2 · ∣∣∣2A∗ ∣∣∣ = 2 · 2n = 2n+1 = 2|A| . Dado um conjunto A = { 1, 2, 3 , . . . , n } com n elementos e um inteiro k com 0 ≤ k ≤ n, podemos perguntar, quantos subconjuntos de k elementos existem em A ? Isto é, queremos saber o tamanho da faḿılia C n,k = { X ∣∣∣ X ⊆ A; |X| = k} ⊆ A = 2A . Assim, a questão é ∣∣∣C n,k ∣∣∣ = ? Vamos abreviar, por enquanto, c n,k = ∣∣∣C n,k ∣∣∣ = ∣∣∣ {X ∣∣∣ X ⊆ A; |X| = k}∣∣∣. Imediato é : c n,0 = c n,n = 1 , pois A possui um único subconjunto de 0 (o subconjunto vazio) e um único de n elementos (o próprio A). Também c n,1 = c n,n−1 = n , 17 pois A possui exatamente n subconjuntos unitários e também n subconjuntos de n−1 elementos A \ { j } , obtidos por remoção de um dos n elementos de A. Em geral, podemos dizer que c n,k = c n,n−k , pois os subconjuntos de n−k elementos são obtidos por remoção de um subcon- junto de k elementos de A. Queremos pensar agora sobre, se k < n, como é obtido c n,k+1 a partir de c n,k ? Como é obtido c n,2 a partir de c n,1 ? Temos n conjuntos unitários { 1 } , { 2 } , . . . , { i } , . . . { n } . A cada { i } pode- mos acrescentar de n−1 maneiras diferentes um elemento j 6= i e obtemos o conjunto { i, j } de 2 elementos. Desta forma surgem n(n−1) subconjuntos de 2 elementos. Mas cada um { i, j } é obtido 2 vezes: Uma vez, acrescendo-se j ao i e uma segunda vez, acrescendo-se i ao j. Portanto, temos n(n−1)2 subconjuntos distintos de 2 elementos (e também de n−2 elementos) em A : c n,2 = c n,n−2 = n(n− 1) 2 . Agora, de k para k+1 : Seja X ∈ C n,k um dos c n,k subconjuntos de k elementos. Podemos acrescentar de n−k maneiras um (k+1)-ésimo ponto j ∈ A\X, obtendo um total de c n,k ·(n−k) conjuntos da forma X∪{j} ∈ C n,k+1 . Mas cada conjunto Y ∈ C n,k+1 surge desta maneira exatamente k + 1 vezes. Logo obtemos um total de c n,k · n−kk+1 subconjuntos distintos de k + 1 elementos. Portanto, c n,k+1 = c n,k · n− k k + 1 . A partir de c n,0 = 1 vemos, colocando-se k = 0, 1, 2 , . . . , n− 1 que c n,1 = c n,0 · n1 = 1 · n = n, cn,2 = cn,1 · n−1 2 = n · n−1 2 = n(n−1) 2 c n,3 = c n,2 · n−23 = n(n−1) 2 · n−2 3 = n(n−1)(n−2) 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . c n,k = n(n−1)(n−2)...(n−k+1)k! , cn,k+1 = cn,k · n−k k+1 = n(n−1)...(n−k+1)(n−k) (k+1)! . Convém lembrar aqui que, se k ∈ IN 0 , entende-se por k ! o produto k ! = k∏ `=1 ` = 1 · 2 · 3 · . . . · k , se k ∈ IN 18 e acrescentando 0! = 1 , se k = 0 (produto vazio) . k ! leia-se: k fatorial. É imediato que se tem 0! = 1! = 1, 2! = 2, 3! = 2! · 3 = 6, 4! = 3! · 4 = 24 , . . . , k ! = (k−1)! · k, (k+1)! = k ! · (k+1), . . . . I.0.23 Definição. Para todo n ∈ IN e todos os k ∈ IN 0 com k ≤ n coloca-se(n k ) = n! k!(n− k)! , número este que se chama de coeficiente binomial n sobre k. Vemos que os coeficientes binomiais nada mais são do que os nossos números c n,k (ver I.0.25 a)): (n k ) = c n,k = n(n− 1) . . . (n− k + 1) k! = n! k!(n− k)! e vemos que o conjunto A = { 1, 2, 3 , . . . , n } possui exatamente ( n k ) subconjun- tos de k elementos. Particularmente, isto explica que Os coeficientes binomiais são números inteiros. Como 2A = C n,0 ∪ C n,1 ∪ C n,2 ∪ . . . ∪ C n,n−1 ∪ Cn,n e C n,i ∩ C n,j = 6O , para todos os i, j com 0 ≤ i 6= j ≤ n [ porquê ?], concluimos ∣∣∣2A ∣∣∣ = ∣∣∣C n,0 ∣∣∣ + ∣∣∣C n,1 ∣∣∣ + ∣∣∣C n,2 ∣∣∣ + . . .+ ∣∣∣C n,n−1 ∣∣∣ + ∣∣∣C n,n ∣∣∣ . Portanto, vale a I.0.24 Conseqüência. Para todo n ∈ IN temos n∑ k=0 (n k ) = ( n 0 ) + ( n 1 ) + ( n 2 ) + . . .+ ( n n−1 ) + ( n n ) = 2n . 19 O triângulo de Pascal (Blaise Pascal [1623-1662], Filósofo e Matemático francês) . É usual, escrever-se os coeficientes binomiais ( n k ) (acrescentando-se ainda (0 0 ) = 1), ordenados no chamado Triângulo de Pascal, cuja n-ésima linha fornece então os coeficientes no desenvolvimento de (a+ b)n para n = 0, 1, 2, 3, . . . . (0 0 ) (1 0 ) (1 1 ) (2 0 ) (2 1 ) (2 2 ) (3 0 ) (3 1 ) (3 2 ) (3 3 ) . . . . . . . . . . . . .( n 0 ) ( n 1 ) . . . ( n k−1 ) ( n k ) . . . ( n n−1 ) ( n n ) ( n+1 0 ) ( n+1 1 ) . . . ( n+1 k ) . . . ( n+1 n ) ( n+1 n+1 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Vemos ainda a visualização da fórmula I.0.25 c), a qual nos diz como o termo( n+1 k ) da (n+1)-ésima linha no triângulo de Pascal é obtido como soma dos termos vizinhos ( n k−1 ) e ( n k ) da linha anterior. 22 § I.1 Produtos Cartesianos e Relações Produtos Cartesianos (René Descartes [1596-1650] Filósofo e Matemático francês) I.1.1 Definição. Sejam A1, A2 , . . . , Am 6= 6O conjuntos. O conjunto M = A1 × A2 × . . . × Am = = { (a1, a2 , . . . , am) ∣∣∣ a1 ∈ A1, a2 ∈ A2 , . . . , am ∈ Am } chama-se o produto Cartesiano dos A1, A2 , . . . , Am (nesta ordem). Os elemen- tos (a1, a2 , . . . , am) em M chamam-se m-uplas. O elemento ai ∈ Ai é a i-ésima coordenada da m-úpla (a1, a2 , . . . , am) (1 ≤ i ≤ m). Para dois elementos (a1, a2 , . . . , am) e (b1, b2 , . . . , bm) em M temos sua igualdade definida por (a1, a2 , . . . , am) = (b1, b2 , . . . , bm) ⇐⇒ a1 = b1, a2 = b2 , . . . , am = bm . No caso particular, quando m = 2, A1 = A e A2 = B, temos M = A×B = { (a, b) ∣∣∣ a ∈ A, b ∈ B } onde (a, b) = (c, d) ⇐⇒ a = c e b = d. No caso m arbitrário e A1 = A2 = . . . = Am = A, o produto Cartesiano passa a ser a potência Cartesiana m-ésima de A, indicada por M = Am = { (a1, a2 , . . . , am) ∣∣∣ a1, a2 , . . . , am ∈ A} . Particularmente, se m = 2 e A = B, temos A2 = { (a, b) ∣∣∣ a, b ∈ A}. I.1.2 Observação. Se C = { x1, x2 , . . . , xr } e B = { y1, y2 , . . . , ys } são conjuntos finitos, temos C×B =  (x1, y1), (x1, y2), . . . , (x1, ys), (x2, y1), (x2, y2), . . . , (x2, ys), · · · · · · (xr , y1), (xr , y2), . . . , (xr , ys)  23 Portanto, |C ×B | = rs = |C | |B |. I.1.3 Conseqüência. Se A1, A2 , . . . , Am são conjuntos finitos, então vale∣∣∣A1 × A2 × . . .× Am ∣∣∣ = ∣∣∣A1 ∣∣∣ ∣∣∣A2 ∣∣∣ . . . ∣∣∣Am ∣∣∣ . Particularmente, se A1 = A2 = . . . = Am = A, temos |Am| = |A|m . Demonstração: Esta afirmação é clara se m = 1. Se já foi provado∣∣∣A1 × A2 × . . .× Am−1 ∣∣∣ = ∣∣∣A1 ∣∣∣ ∣∣∣A2 ∣∣∣ . . . ∣∣∣Am−1 ∣∣∣ , podemos considerar C = A1 × A2 × . . .× Am−1 e temos A1 × A2 × . . .× Am = C × Am . Por I.1.2 vemos |C × Am | = |C | ∣∣∣Am ∣∣∣ e portanto∣∣∣A1 × A2 × . . .× Am ∣∣∣ = |C × Am | = |C | ∣∣∣Am ∣∣∣ = ∣∣∣A1 ∣∣∣ ∣∣∣A2 ∣∣∣ . . . ∣∣∣Am−1 ∣∣∣ ∣∣∣Am ∣∣∣ . I.1.4 Exemplos. Para A = { ∇,♠,♥,♣ } e B = { 1, 2, 3 } temos A×B =  (∇, 1), (♠, 1), (♥, 1), (♣, 1), (∇, 2), (♠, 2), (♥, 2), (♣, 2), (∇, 3), (♠, 3), (♥, 3), (♣, 3)  , porém B × A =  (1,∇), (2,∇), (3,∇), (1,♠), (2,♠), (3,♠), (1,♥), (2,♥), (3,♥), (1,♣), (2,♣), (3,♣)  . Vemos |A×B | = |B × A| = 12. Mas A×B 6= B × A. Mais exatamente: (A×B) ∩ (B × A) = 6O. 24 Observamos que, se A e B são conjuntos finitos de tamanhos |A| = m e |B | = n, temos para a quantidade das relações entre A e B:∣∣∣2A×B ∣∣∣ = ∣∣∣2B×A ∣∣∣ = 2|A||B| = 2mn . Particularmente, ∣∣∣2A×A ∣∣∣ = 2m2. Por exemplo: Entre A = { ∇,♠,♥,♣ } e B = { 1, 2, 3 } (e também entre B e A ) existem 212 = 4096 relações distintas. Em A = { a, b, c } existem 29 = 512 relações distintas. Relação inversa I.1.9 Definição. Sejam A,B 6= 6O dois conjuntos e ρ ∈ 2A×B uma relação. A relação ρ −1 = { (b, a) ∣∣∣ (a, b) ∈ ρ} ∈ 2B×A chama-se a relação inversa da ρ. Observamos que D(ρ −1 ) = I(ρ) e I(ρ −1 ) = D(ρ) . Além do mais, (ρ −1 ) −1 = ρ . I.1.10 Exemplo. a) Para A = ZZ e B = IR e considerando-se a relação ρ = { (a, b) ∣∣∣ a ∈ ZZ, b ∈ IR, 4a2 + 9b2 = 36} , temos ρ = { (0,±2), ( ±1,±4 √ 2 3 ) , ( ±2,±2 √ 5 3 ) , (±3, 0) } ∈ 2ZZ×IR e ρ −1 = { (±2, 0), ( ±4 √ 2 3 ,±1 ) , ( ±2 √ 5 3 ,±2 ) , (0,±3) } ∈ 2IR×ZZ . 27 D(ρ) = I(ρ−1) = { − 3, −2, −1, 0, 1, 2, 3 } e D(ρ −1 ) = I(ρ) = { −2, −4 √ 2 3 , − 2 √ 5 3 , 0, 2 √ 5 3 , 4 √ 2 3 , 2 } . b) Para A = { ∇,♠,♥,♣ } e B = { 1, 2, 3 } e considerando-se a relação ρ = { (∇, 3), (∇, 1), (♣, 3) } ∈ 2A×B , temos ρ −1 = { (3,∇), (1,∇), (3,♣) } ∈ 2B×A , D(ρ) = I(ρ −1 ) = { ∇, ♣ } e D(ρ −1 ) = I(ρ) = { 1, 3 } . Composição de relações I.1.11 Definição. Sejam A,B,C 6= 6O conjuntos, ρ ∈ 2A×B e σ ∈ 2B×C relações. Definamos a relação composta σ◦ρ ∈ 2A×C por: ∀ a ∈ A, c ∈ C : a σ◦ρ c ⇐⇒ ∃ b ∈ B tal que  a ρ b e b σ c . I.1.12 Exemplos. a) Sejam A = B = C = IR, ρ, σ ∈ 2IR×IR definidas por ρ = { (a, b) ∣∣∣ a2 + 3b2 = 5} e σ = { (b, c) ∣∣∣ b = 4c2} . Então σ ◦ ρ = { (a, c) ∣∣∣ a2 + 48c4 = 5} . b) Sejam A = { ∇,♠,♥,♣ } , B = { 1, 2, 3, 4 } e C = { a, b, c, d, e } . Sejam ρ ∈ 2A×B e σ ∈ 2B×C definidas por ρ = { (♥, 3), (♥, 4), (♠, 3), (∇, 2) } e σ = { (3, c), (1, e), (3, a), (2, d) } . 28 Então σ ◦ ρ = { (♥, c), (♥, a), (♠, c), (♠, a), (∇, d) } . I.1.13 Observação. Sejam A,B 6= 6O conjuntos. Se ρ ∈ 2A×B, então valem δ B ◦ ρ = ρ e ρ ◦ δ A = ρ . Demonstração: Para a ∈ A, b ∈ B temos a (δ B ◦ ρ) b ⇐⇒ ∃ b ′ ∈ B com  a ρ b ′ e b ′ δ B b ⇐⇒ b = b ′ e a ρ b ′ ⇐⇒ a ρ b. Logo δ B ◦ ρ = ρ. Também: a (ρ ◦ δ A ) b ⇐⇒ ∃ a ′ ∈ A com  a δ A a ′ e a ′ ρ b ⇐⇒ a = a ′ e a ′ ρ b ⇐⇒ a ρ b. Logo ρ ◦ δ A = ρ. I.1.14 Proposição. Sejam A,B,C,D 6= 6O conjuntos, ρ ∈ 2A×B, σ ∈ 2B×C e τ ∈ 2C×D relações. Então valem: a) (τ ◦ σ) ◦ ρ = τ ◦ (σ ◦ ρ), (a lei associativa da composição). b) (σ ◦ ρ)−1 = ρ−1 ◦ σ−1 (lei de inversão da composta). Demonstração: a) Para a ∈ A e d ∈ D temos: a ( (τ ◦ σ) ◦ ρ ) d ⇐⇒ ∃ b ∈ B com  a ρ b e b (τ ◦ σ) d ⇐⇒ ∃ b ∈ B, ∃ c ∈ C 29 I.1.18 Exemplos. a) Para qualquer conjunto A 6= 6O, temos δ A ∈ Eq(A) e também A×A ∈ Eq(A) , i.e. tanto a relação da igualdade, quanto a relação universal em A são relações de equivalência em A. Particularmente, sempre Eq(A) 6= 6O. b) Seja A um conjunto de bolas (de várias cores). Definindo-se ∀ a, b ∈ A: a ε b ⇐⇒ a e b possuem a mesma cor , temos que ε ∈ Eq(A). I.1.19 Definição. Se ε é uma relação de equivalência em A, e se a ∈ A, então colocamos ā = { x ∈ A ∣∣∣ x ε a} . O subconjunto ā de A chama-se a classe de equivalência de a mod ε (lido: a modulo ε). I.1.20 Exemplo. Seja A um conjunto de bolas e ε ∈ Eq(A) a relação ∀ a, b ∈ A : a ε b ⇐⇒ a e b têm a mesma cor . Para cada a ∈ A, a classe de equivalência de a mod ε é ā = { x ∈ A ∣∣∣ x tem a cor de a} . I.1.21 Proposição. Seja A 6= 6O um conjunto e ε ∈ Eq(A). Então valem para todos os a, b ∈ A: a) a ∈ ā, particularmente, ā 6= 6O. b) ā = b̄ ⇐⇒ a ε b. 32 c) ā 6= b̄ =⇒ ā ∩ b̄ = 6O. d) ⋃ a∈A ā = A. Demonstração: a) Pela reflexividade de ε temos a ∈ ā e portanto ā 6= 6O ∀ a ∈ A. b) ”⇒ ”: De ā = b̄ segue a ∈ b̄ = { x ∈ A ∣∣∣ x ε b} . Logo a ε b. ” ⇐ ”: Seja a ε b. Para todo x ∈ ā temos x ε a ε b e dáı x ∈ b̄. Segue ā ⊆ b̄. Da mesma forma: Para todo x ∈ b̄ temos x ε b ε a e dáı x ∈ ā. Segue b̄ ⊆ ā. Logo ā = b̄. c) Suponhamos ā ∩ b̄ 6= 6O e seja x ∈ ā ∩ b̄. Temos a ε x ε b e dáı por b): ā = x̄ = b̄. d) Claramente, ⋃ a∈A ā ⊆ A. Mas, como a ∈ ā, temos de fato ⋃ a∈A ā = A. I.1.22 Definição. Seja A 6= 6O um conjunto e P ⊆ 2A uma faḿılia de subconjuntos de A. Dizemos que P é uma partição de A, se a) 6O 6∈ P b) Para todos os X, Y ∈ P temos X = Y ou X ∩ Y = 6O. c) ⋃ X∈P X = A. Por I.1.21 temos o I.1.23 Exemplo. Seja ε ∈ Eq(A) e Pε = { ā ∣∣∣ a ∈ A} com ā = {x ∈ A ∣∣∣ x ε a}, o conjunto das classes de equivalência de A mod ε. Então Pε é uma partição de A. Pε chama-se a partição de A induzida por ε. 33 Vale também ao contrário que toda partição é induzida por uma relação de equivalência : I.1.24 Proposição. Seja P ⊆ 2A uma partição de A e defina uma relação ε P por ∀ a, b ∈ A: a ε P b ⇐⇒ ∃ X ∈ P com a, b ∈ X. Então a) ε P ∈ Eq(A) b) Pε P = P. Demonstração: a) Como ⋃ X∈P X = A, vemos que para todo a ∈ A existe X ∈ P com a ∈ X. Isto mostra a ε P a ∀ a ∈ A, i.e. a reflexividade da relação ε P . Se a, b ∈ A são tais que a ε P b, então existe X ∈ P com a, b ∈ X. Segue b ε P a e vemos a simetria de ε P . Sejam a, b, c ∈ A com a ε P b e b ε P c. Assim, existem X, Y ∈ P com a, b ∈ X e b, c ∈ Y . Como b ∈ X ∩ Y, concluimos X = Y, ou seja, a, c ∈ X = Y ∈ P. Logo, a ε P c e temos a transitividade de ε P . Assim provamos ε P ∈ Eq(A). b) Como a ε P b ⇐⇒ a e b pertencem ao mesmo X ∈ P, é claro que as classes de equivalência mod ε P são exatamente os conjuntos de P. I.1.25 Definição. Seja A um conjunto, ε ∈ Eq(A) e ā = { x ∈ A ∣∣∣ x ε a} a classe de equivalência de a mod ε para todo a ∈ A. A partição Pε escrevemos também como A/ε = Pε = { ā ∣∣∣ a ∈ A} e chamamos A/ε o conjunto quociente de A mod ε. 34 § I.2 Aplicações (funções) Definição e exemplos I.2.1 Definição. Sejam A, B 6= 6O dois conjuntos. Uma relacão ϕ ∈ 2A×B chama-se uma aplicação (função) de A em B , se i) ∀ a ∈ A ∃ b ∈ B com a ϕ b. ii) ∀ a ∈ A, ∀ b, b ′ temos: a ϕ b e a ϕ b ′ =⇒ b = b ′. i) diz que D(ϕ) = A, i.e. o doḿınio de definição de ϕ é o conjunto A todo. ii) diz que o elemento b ∈ B que é ϕ-relacionado com a ∈ A é determinado de maneira única por a. Este único b ∈ B que é ϕ-relacionado com a ∈ A chama-se o valor de ϕ em a e é escrito como b = ϕ(a) . A imagem de ϕ, i.e. I(ϕ) = { b ∈ B ∣∣∣ ∃ a ∈ A com a ϕ b} é agora o conjunto de todos os valores de ϕ. Portanto I(ϕ) = { ϕ(a) ∣∣∣ a ∈ A} . Escreve-se portanto também I(ϕ) = ϕ(A) . O conjunto de todas as aplicações de A em B denotamos por BA = { ϕ ∈ 2A×B ∣∣∣ ϕ é uma aplicação de A em B} . (ver a explicação desta notação em I.2.9). Temos portanto BA ⊆ 2A×B . Se ϕ ∈ BA, então podemos escrever ϕ = { ( a, ϕ(a) ) ∣∣∣ a ∈ A} . 37 I.2.2 Exemplos. a1) Seja A = B = IR. A relação ρ ∈ 2IR×IR seja definida por ρ = { (a, b) ∣∣∣ 4a2 + 9b2 = 36} . Temos D(ρ) = [−3, 3] e I(ρ) = [−2, 2] e ρ 6∈ IRIR, i.e. esta ρ não é uma aplicação de IR em IR. a2) Seja A = [−3, 3] e B = IR. ϕ ∈ 2[−3,3]×IR seja definida por ϕ = { (a, b) ∣∣∣ 4a2 + 9b2 = 36; b ≤ 0} . Temos D(ϕ) = [−3, 3] = A e I(ϕ) = [−2, 0] e ϕ ∈ IR[−3,3]. Também podemos escrever ϕ = { ( a,− √ 36−4a2 3 ) ∣∣∣∣ a ∈ [−3, 3]} . b) Seja A = { ∇,♠,♥,♣ } , B = { a, b, c, d, e } . b1) Para ϕ = { (∇, b), (♠, a), (♥, a), (♣, d) } temos ϕ ∈ BA e vale I(ϕ) = ϕ(A) = { a, b, d } . b2) Para ρ = { (∇, b), (♠, a), (♠, b), (♥, a), (♣, d) } temos ρ 6∈ BA, pois o ”valor de ρ ” em ♠ não é único. b3) Para ρ = { (∇, b), (♠, a), (♣, d) } temos ρ 6∈ BA, pois D(ρ) = { ∇, ♠, ♣ } 6= A. I.2.3 Três Exemplos importantes a) Seja B um conjunto e consideremos A = IN = { 1, 2, 3, . . . } . Toda aplicação ϕ ∈ BIN é denominada uma seqüência em B. Se ϕ(n) = bn ∈ B é o valor de ϕ em n ∈ IN , temos que ϕ = { ( n, ϕ(n) ) ∣∣∣ n ∈ IN } = { (n, bn) ∣∣∣ n = 1, 2, 3, . . .} . 38 Escreve-se a seqüência ϕ também como ϕ = ( b1 , b2 , b3 , . . . , bn , . . . ) = (bn)n∈IN . BIN é portanto o conjunto de todas as sequências em B. b) Seja A 6= 6O um conjunto e ε ∈ Eq(A). Seja A/ε = { ā ∣∣∣ a ∈ A} o conjunto quociente de A mod ε. Lembrando: ∀ a ∈ A : ā = { x ∈ A ∣∣∣ x ε a} é a classe de equivalência de a mod ε. A aplicação γ ∈ (A/ε)A , definida por γ(a) = ā ∀ a ∈ A chama-se a aplicação canónica de A sobre A/ε. Temos portanto γ = { (a, ā) ∣∣∣ a ∈ A} , i.e. a aplicação canónica associa a cada elemento a ∈ A a sua classe de equivalência mod ε na qual ele está. Por exemplo, se A = { 1, 2, 3, 4, 5 } e se ε = { (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (2, 5), (5, 2), (3, 4), (4, 3) } = = δ A ∪ { (2, 5), (5, 2), (3, 4), (4, 3) } , temos assim: A/ε = {{ 1 } , { 2, 5 } , { 3, 4 }} e γ = { (1, { 1 } ), (2, { 2, 5 } ), (3, { 3, 4 } ), (4, { 3, 4 } ), (5, { 2, 5 } ) } . c) Sejam A1 , A2 , . . . , Ar 6= 6O conjuntos e M = A1 × A2 × . . .× Ar seu produto Cartesiano. Seja i ∈ { 1, 2, . . . , r } . A aplicação π i ∈ AM i ⊆MM tal que π i ( (a1 , a2 , . . . , ar) ) = a i ∀ (a1 , a2 , . . . , ar) ∈M 39 I.2.7 Exemplos. a) Para A = B = IR e ϕ = { ( x, x2 ) ∣∣∣ x ∈ IR} ∈ 2IR×IR temos ϕ −1 ◦ ϕ = { ( x2, x ) ∣∣∣ x ∈ IR} ◦ { (x, x2) ∣∣∣ x ∈ IR} = = { (x, x) ∣∣∣ x ∈ IR} ∪ { (x,−x) ∣∣∣ x ∈ IR} ⊇ δ IR = δ A e ϕ ◦ ϕ−1 = { ( x, x2 ) ∣∣∣ x ∈ IR} ◦ { (x2, x) ∣∣∣ x ∈ IR} = = { ( x2, x2 ) ∣∣∣ x ∈ IR} ⊆ δ IR = δ B . Portanto ϕ é uma aplicação de IR em IR. b) Para A = B = IR e ρ = { ( x2, x ) ∣∣∣ x ∈ IR} ∈ 2IR×IR temos ρ −1 ◦ ρ = { ( x, x2 ) ∣∣∣ x ∈ IR} ◦ { (x2, x) ∣∣∣ x ∈ IR} = = { ( x2, x2 ) ∣∣∣ x ∈ IR} = { (y, y) ∣∣∣ 0 ≤ y ∈ IR} 6⊇ δ IR = δ A . e ρ ◦ ρ−1 = { ( x2, x ) ∣∣∣ x ∈ IR} ◦ { (x, x2) ∣∣∣ x ∈ IR} = = { (x, x) ∣∣∣ x ∈ IR} ∪ { (x,−x) ∣∣∣ x ∈ IR} 6⊆ δ IR = δ B . Portanto, D(ρ) 6= A e também ”os valores da ρ” não são únicos. Particularmente, ρ não é uma aplicação de IR em IR. Detalhar isto ! I.2.8 Proposição. Sejam A, B 6= 6O conjuntos, ϕ, ψ ∈ BA duas aplicações de A em B. Então ϕ = ψ ⇐⇒ ϕ(a) = ψ(a) ∀ a ∈ A . i.e. duas aplicações de A em B coincidem se e somente se elas assumem o mesmo valor para todos os argumentos. Demonstração: Temos ϕ = { (a, b) ∈ A×B ∣∣∣ a ϕ b} = { (a, ϕ(a)) ∣∣∣ a ∈ A} e ψ = { (x, y) ∈ A×B ∣∣∣ x ψ y} = { (x, ψ(x)) ∣∣∣ x ∈ A} . 42 ”⇐ ”: ϕ(a) = ψ(a) ∀ a ∈ A significa ( a, ϕ(a) ) = ( a, ψ(a) ) ∀ a ∈ A. Portanto, ϕ = ψ. ”⇒ ”: Se ϕ = ψ, então ( a, ϕ(a) ) ∈ ψ ∀ a ∈ A. Portanto, para todo a ∈ A existe x ∈ A com ( a, ϕ(a) ) = ( x, ψ(x) ) . Segue a = x e ϕ(a) = ψ(x) = ψ(a). Vemos que uma aplicação ϕ de um conjunto finito A = { 1, 2, . . . , m } em B é essencialmente determinada e pode ser identificada com a m-úpla dos seus valores, i. e. com ( ϕ(1), ϕ(2), . . . , ϕ(m) ) ∈ Bm . O conjunto das aplicações de A em B é portanto essencialmente a potência Cartesiana Bm. A notação BA para indicar o conjunto de todas as aplicações de A em B justifica-se agora pela seguinte I.2.9 Observação. Se A e B são conjuntos finitos com, digamos |A| = m e |B | = n elementos, então ∣∣∣BA ∣∣∣ = |B ||A| = nm . Demonstração: Podemos supor A = { 1, 2, 3, . . . , m } . A afirmação fica clara, se lembramos |Bm| = |B |m . Composição de aplicações I.2.10 Proposição. Sejam A, B, C 6= 6O conjuntos, ϕ ∈ BA e ψ ∈ CB. Então ψ ◦ ϕ ∈ CA , i.e. a relação composta (ver I.1.11) de duas aplicações é uma aplicação. Além disso, o valor único que a composta ψ ◦ ϕ assume em todo a ∈ A é calculado por (ψ ◦ ϕ)(a) = ψ ( ϕ(a) ) . 43 Demonstração: Claro que ψ ◦ ϕ ∈ 2A×C . Por I.2.6 devemos mostar que δ A ⊆ (ψ ◦ ϕ)−1 ◦ (ψ ◦ ϕ) e δ C ⊇ (ψ ◦ ϕ) ◦ (ψ ◦ ϕ)−1 . Observando-se a hipótese δ A ⊆ ϕ−1 ◦ ϕ, δ B ⊇ ϕ ◦ ϕ−1 , δ B ⊆ ψ−1 ◦ ψ e δ C ⊇ ψ ◦ ψ−1 , obtemos de fato: (ψ ◦ ϕ)−1 ◦ (ψ ◦ ϕ) = (ϕ−1 ◦ ψ−1) ◦ (ψ ◦ ϕ) = ϕ−1 ◦ (ψ−1 ◦ ψ) ◦ ϕ ⊇ ⊇ ϕ−1 ◦ δ B ◦ ϕ = ϕ−1 ◦ ϕ ⊇ δ A . Também (ψ ◦ ϕ) ◦ (ψ ◦ ϕ)−1 = (ψ ◦ ϕ) ◦ (ϕ−1 ◦ ψ−1) = ψ ◦ (ϕ ◦ ϕ−1) ◦ ψ−1) ⊆ ⊆ ψ ◦ δ B ◦ ψ−1 = ψ ◦ ψ−1 ⊆ δ C . Consequentemente, ψ ◦ ϕ ∈ CA. Como é calculado o valor (ψ ◦ ϕ)(a) ∈ C ? Temos para todo (a, c) ∈ A× C : (a, c) ∈ ψ ◦ ϕ ⇐⇒ ∃ b ∈ B tal que a ϕ b e b ψ c ⇐⇒ ⇐⇒ b = ϕ(a) e c = ψ(b) ⇐⇒ c = ψ ( ϕ(a) ) Logo, c = (ψ ◦ ϕ)(a) = ψ ( ϕ(a) ) . Portanto, podemos dizer também que ψ ◦ ϕ = { ( a, ψ ( ϕ(a) )) ∣∣∣∣ a ∈ A} . I.2.11 Notação. Se A = { 1, 2, 3, . . . , m } e B é um conjunto qualquer, uma notação transpar- ente para indicar uma aplicação ϕ ∈ BA é escrever-se uma (2 ×m)-matriz que contém na primeira linha os m argumentos k ∈ A, na segunda linha os valores ϕ(k) ∈ B correspondentes: ϕ =  1 2 3 . . . m−1 m ϕ(1) ϕ(2) ϕ(3) . . . ϕ(m−1) ϕ(m)  . 44 I.2.14 Notações. Se A e B são conjuntos, denotamos por Inj(A, B), Sob(A, B) e Bij(A, B) os conjuntos das aplicações injetoras, sobrejetoras e bijetoras, respectivamente. Temos portanto Bij(A, B) = Inj(A, B) ∩ Sob(A, B) ⊆ Inj(A, B) ∪ Sob(A, B) ⊆ BA. No caso A = B , o conjunto Bij(A, A) possui um significado importante. Abreviamos escrevendo S A = Bij(A, A) . Os elementos em S A chamam-se as permutações de A, i.e. S A é o conjunto de todas as permutações de A. Para A 6= 6O temos δ A ∈ S A . Portanto, sempre S A 6= 6O. Porém: I.2.15 Advertência. Para A 6= B é bem posśıvel Inj(A, B) = 6O ou Sob(A, B) = 6O: Por exemplo, se A e B são conjuntos finitos, temos Inj(A, B) 6= 6O ⇐⇒ |B | ≥ |A|, Sob(A, B) 6= 6O ⇐⇒ |B | ≤ |A|, (porquê ? detalhar isto !) Bij(A, B) 6= 6O ⇐⇒ |B | = |A|. I.2.16 Exemplos. a) Para A = B = IR temos: a1) ϕ = { (a, 3a) ∣∣∣ a ∈ IR} é uma aplicação injetora de A = IR em B = IR. Mas ela não é sobrejetora, pois ϕ(IR) = { 3a ∣∣∣ a ∈ IR} = {x ∈ IR ∣∣∣ x > 0} 6= IR = B . Portanto, ϕ ∈ Inj(IR, IR) \ Sob(IR, IR) . 47 a2) ϕ = { ( a, a3 − a ) ∣∣∣ a ∈ IR} é uma aplicação sobrejetora de A = IR sobre B = IR (porquê ?, demonstração !). Ela não é injetora, pois ϕ(−1) = ϕ(0) = ϕ(1). Portanto, ϕ ∈ Sob(IR, IR) \ Inj(IR, IR) . a3) ϕ = { ( a, a3 ) ∣∣∣ a ∈ IR} é uma aplicação bijetora de A = IR sobre B = IR, i.e. uma permutação de IR. Portanto ϕ ∈ S IR . b) b1) Para A = { ∇,♠,♥,♣ } e B = { 1, 2, 3, 4, 5 } temos que ϕ = { (∇, 3), (♠, 4), (♥, 2), (♣, 1) } = ( ∇ ♠ ♥ ♣ 3 4 2 1 ) ∈ Inj(A, B) \ Sob(A, B) . b2) Para A = { ∇,♠,♥,♣ } e B = { 1, 2, 3 } temos que ϕ = { (∇, 3), (♠, 3), (♥, 2), (♣, 1) } = ( ∇ ♠ ♥ ♣ 3 3 2 1 ) ∈ Sob(A, B) \ Inj(A, B) . b3) Para A = { ∇,♠,♥,♣ } e B = { 1, 2, 3, 4 } temos que ϕ = { (∇, 3), (♠, 4), (♥, 2), (♣, 1) } = ( ∇ ♠ ♥ ♣ 3 4 2 1 ) ∈ Bij(A, B) . b4) Para A = B = { ∇,♠,♥,♣ } temos que ϕ = { (∇,♠), (♠,∇), (♥,♣), (♣,♥) } = ( ∇ ♠ ♥ ♣ ♠ ∇ ♣ ♥ ) ∈ S A , i.e. ϕ é uma permutação de A. I.2.17 Proposição. Sejam A, B 6= 6O conjuntos e ϕ ∈ BA. Então a) ϕ é injetora ⇐⇒ δ A ⊇ ϕ−1 ◦ ϕ ⇐⇒ δ A = ϕ−1 ◦ ϕ b) ϕ é sobrejetora ⇐⇒ δ B ⊆ ϕ ◦ ϕ−1 ⇐⇒ δ B = ϕ ◦ ϕ−1 . c) ϕ é bijetora ⇐⇒ δ A = ϕ−1 ◦ ϕ e δ B = ϕ ◦ ϕ−1 . 48 Demonstração: a) Para qualquer aplicação temos δ A ⊆ ϕ−1◦ϕ (I.2.6). Portanto, a segunda equivalência fica clara. Só é preciso provar a primeira: ” ⇒ ”: Suponha ϕ injetora e seja dado (a, a ′) ∈ ϕ−1 ◦ ϕ. Então existe b ∈ B tal que  a ϕ b e b ϕ−1 a ′ . Isto significa  a ϕ b e a ′ ϕ b , ou seja, ϕ(a) = b = ϕ(a ′). Pela injetividade concluimos a = a ′. Portanto (a, a ′) = (a, a) ∈ δ A , o que mostra ϕ−1 ◦ ϕ ⊆ δ A . ” ⇐ ”: Suponha δ A ⊇ ϕ−1 ◦ ϕ e sejam a, a ′ ∈ A com ϕ(a) = b = ϕ(a ′). Temos portanto  a ϕ b e a ′ ϕ b . Isto significa  a ϕ b e b ϕ−1 a ′ , ou seja, (a, a ′) ∈ ϕ−1 ◦ ϕ. Por hipótese então (a, a ′) ∈ δ A e segue a = a ′. Logo ϕ é injetora. b) Para qualquer aplicação temos δ B ⊇ ϕ ◦ ϕ−1 (I.2.6). Portanto também agora, a segunda equivalência fica clara. Só é preciso provar a primeira: ” ⇒ ”: Suponha ϕ sobrejetora e seja dado (b, b) ∈ δ B onde b é qualquer elemento em B. Por hipótese, existe (pelo menos um) a ∈ A com ϕ(a) = b, i.e.  b ϕ−1 a e a ϕ b . Isto significa (b, b) ∈ ϕ ◦ ϕ−1 . Logo, δ B ⊆ ϕ ◦ ϕ−1 . ” ⇐ ”: Suponha reciprocamente, δ B ⊆ ϕ ◦ ϕ−1 e seja dado b ∈ B. Temos (b, b) ∈ δ B e por hipótese portanto (b, b) ∈ ϕ ◦ ϕ−1 . Logo existe a ∈ A com b ϕ−1 a e a ϕ b . Isto significa que descobrimos um a ∈ A com b = ϕ(a) e vemos que ϕ é ”sobre”. c) é uma conseqüência de a) e b). 49 c) Segue por combinação de a) e b). 2ademonstração: a) A injetividade de ϕ e ψ significa que δ A = ϕ −1 ◦ ϕ e δ B = ψ −1 ◦ ψ (I.2.17 a)) . Devemos mostrar que δ A = (ψ ◦ ϕ)−1 ◦ (ψ ◦ ϕ). De fato: (ψ ◦ ϕ)−1 ◦ (ψ ◦ ϕ) = ϕ−1 ◦ (ψ−1 ◦ ψ) ◦ ϕ = ϕ−1 ◦ δ B ◦ ϕ = ϕ−1 ◦ ϕ = δ A . b) A sobrejetividade de ϕ e ψ significa que δ B = ϕ ◦ ϕ−1 e δ C = ψ ◦ ψ−1 (I.2.17 b)) . Devemos mostrar que δ C = (ψ ◦ ϕ) ◦ (ψ ◦ ϕ)−1 . De fato: (ψ ◦ ϕ) ◦ (ψ ◦ ϕ)−1 = ψ ◦ (ϕ ◦ ϕ−1) ◦ ψ−1 = ψ ◦ δ B ◦ ψ−1 = ψ ◦ ψ−1 = δ C . I.2.21 Proposição. Sejam A, B 6= 6O conjuntos e ϕ ∈ BA. Equivalentes são : a) ϕ ∈ Bij(A, B). b) Existem ψ, ω ∈ AB tais que ψ ◦ ϕ = δ A e ϕ ◦ ω = δ B . Demonstração: ”a) ⇒ b)”: Suponha ϕ é bijetora. Então ϕ−1 ∈ AB e pode- mos escolher ψ = ω = ϕ−1 e obtemos com esta escolha: ψ ◦ ϕ = ϕ−1 ◦ ϕ = δ A tal como ϕ ◦ ω = ϕ ◦ ϕ−1 = δ B . ”b) ⇒ a)”: Suponha a existência das ψ, ω ∈ AB tais que ψ ◦ ϕ = δ A e ϕ ◦ ω = δ B . i) Seja dado b ∈ B. Escolhamos a = ω(b) e obtemos com esta escolha 52 ϕ(a) = ϕ ( ω(b) ) = (ϕ ◦ ω)(b) = δ B (b) = b. Portanto ϕ ∈ Sob(A, B). ii) Sejam a, a ′ ∈ A tais que ϕ(a) = ϕ(a ′). Segue ψ ( ϕ(a) ) = ψ ( ϕ(a ′) ) , ou seja, (ψ ◦ ϕ)(a) = (ψ ◦ ϕ)(a ′). Mas então a = δ A (a) = δ A (a ′) = a ′. Logo ϕ ∈ Inj(A, B). De i) e ii) segue ϕ ∈ Bij(A, B). Conjuntos equipotentes I.2.22 Definição. Dois conjuntos A, B 6= 6O chamam-se equipotentes, se Bij(A, B) 6= 6O. Para conjuntos equipotentes vamos escrever A ∼ B. Caso contrário, A 6∼ B significa que A e B não são equipotentes. Temos I.2.23 Proposição. Se A, B, C 6= 6O são três conjuntos, então valem: a) A ∼ A. b) Se A ∼ B, então B ∼ A. c) Se A ∼ B e B ∼ C, então A ∼ C. Estas regras dizem portanto que equipotência entre conjuntos podemos interpretar como relação de equivalência no universo dos conjuntos. Demonstração: a) vale, pois δ A ∈ Bij(A, A) e portanto Bij(A, A) 6= 6O. b) A ∼ B significa Bij(A, B) 6= 6O. Se ϕ ∈ Bij(A, B), então ϕ−1 ∈ Bij(B, A) (I.2.18). Logo Bij(B, A) 6= 6O e portanto B ∼ A. c) A ∼ B e B ∼ C significa Bij(A, B) 6= 6O 6= Bij(B, C). Se ϕ ∈ Bij(A, B) e ψ ∈ Bij(B, C), então ψ ◦ ϕ ∈ Bij(A, C) (I.2.20). Logo Bij(A, C) 6= 6O, ou seja, A ∼ C. 53 I.2.24 Exemplos. i) Se A e B são conjuntos finitos, entãoA ∼ B ⇐⇒ |A| = |B |. ii) Seja IN = { 1, 2, 3, . . . } e 2IN = { 2, 4, 6, . . . } . Então IN ∼ 2IN , sendo que para a aplicação ϕ definida por ϕ(n) = 2n ∀ n ∈ IN temos ϕ ∈ Bij (IN , 2IN) . iii) IN ∼ ZZ podemos verificar, olhando na aplicação ϕ ∈ Bij (IN , ZZ), definida por ϕ(n) =  n 2 se n é par −n−12 se n é ı́mpar . iv) IR ∼ (0, 1), sendo que ϕ ∈ Bij (IR , (0, 1)), quando se define ϕ(x) = 1π · arctg x+ 1 2 ∀ x ∈ IR. É importante tomarmos conhecimento que existem conjuntos infinitos que não são equipotentes: I.2.25 Proposição. IN 6∼ IN IN e também IR 6∼ IRIR . (Em I.2.33 provaremos A 6∼ AA para qualquer conjunto com |A| ≥ 2. ) Demonstração: Provaremos a primeira afirmação. A segunda é análoga. Afirma-se Bij ( IN , IN IN ) = 6O. Como Bij ( IN , IN IN ) ⊆ Sob ( IN , IN IN ) , basta provar que Sob ( IN , IN IN ) = 6O : Seja dada Ω ∈ (IN IN)IN , i.e. uma qualquer aplicação Ω : IN −→ IN IN . Afirmamos que Ω jamais pode ser sobrejetora: Para todo n ∈ IN indicamos por ϕn = Ω(n) o valor de Ω em n. Assim temos para a imagem da Ω : Ω(IN) = { ϕ1 , ϕ2 , ϕ3 , . . . , ϕn , . . . } . Seja ψ ∈ IN IN definida por ψ(x) = ϕx(x) + 1 ∀ x ∈ IN . 54 A decomposição canónica de uma aplicação I.2.29 Proposição. Sejam A, B 6= 6O conjuntos e ϕ ∈ BA. Para todos os a, a ′ ∈ A definamos a εϕ a ′ ⇐⇒ ϕ(a) = ϕ(a ′) . Então valem: a) εϕ ∈ Eq(A) ( εϕ chama-se a relação de equivalência associada à ϕ). b) Seja γ a aplicação canónica de A sobre A/εϕ , i.e. γ(a) = ā = { x ∈ A ∣∣∣ x εϕ a} . Afirmamos que existe uma única aplicação ψ ∈ Bij ( A/εϕ , ϕ(A) ) , tal que ψ ◦ γ = ϕ . Particularmente, A/εϕ ∼ ϕ(A) . Demonstração: a) é visto fácilmente (detalhar!). b) A unicidade de ψ: Sejam ψ, ψ ′ bijeções de A/εϕ sobre ϕ(A) com ψ ◦ γ = ϕ = ψ ′ ◦ γ. Segue para todo a ∈ A : (ψ ◦ γ)(a) = ϕ(a) = (ψ ′ ◦ γ)(a), ou seja, ψ ( γ(a) ) = ψ ′ ( γ(a) ) , ou seja, ψ(ā) = ψ ′(ā) ∀ ā ∈ A/εϕ. Isto mostra ψ = ψ ′. A existência de ψ: Tentemos definir ψ : A/εϕ −→ ϕ(A) ⊆ B por ψ(ā) = ϕ(a) ∀ ā ∈ A/εϕ . Esta tentativa de definição exige um cuidado especial, pois o conjunto de definição da ψ é um conjunto de classes de equivalência. Cada classe ā em geral é representada ” por muitos a ”, a saber, por todos os a ′ que são equivalentes ao a. Como a aplicação ψ tem que ter um valor único em ā, a tentativa da definição acima só dará certo se o valor ψ(ā) definido independe do representante escolhido na classe ā. 57 Este cuidado especial é conhecido como o problema da boa definição da ψ . No nosso caso temos de fato: 1) ψ é uma aplicaç~ao bem definida: Se a, a ′ ∈ A são tais que ā = ā ′, então a εϕ a ′, i.e. ϕ(a) = ϕ(a ′). Segue ψ(ā) = ϕ(a) = ϕ(a ′) = ψ(ā ′). Portanto, o valor ψ(ā) independe da escolha do representante da classe de equivalência ā. Temos que ψ é de fato uma aplicação de A/εϕ em B. 2) A sobrejetividade da ψ : Para todo b ∈ ϕ(A) existe a ∈ A com b = ϕ(a) = ψ(ā). Logo, ψ ∈ Sob ( A/εϕ , ϕ(A) ) . 3) A injetividade da ψ : Suponhamos a, a ′ ∈ A são tais que ψ(ā) = ψ(ā ′). Segue ϕ(a) = ϕ(a ′), ou seja, ā = ā ′. Portanto, ψ ∈ Inj ( A/εϕ , ϕ(A) ) . Vemos que ψ ∈ Bij ( A/εϕ , ϕ(A) ) . 4) Como (ψ ◦ γ)(a) = ψ ( γ(a) ) = ψ(ā) = ϕ(a) para todos os a ∈ A, vemos ψ ◦ γ = ϕ. I.2.30 Exemplo. Sejam A = B = IR e ϕ ∈ IRIR definida por ϕ(a) = sen 2πa ∀ a ∈ IR . Temos ϕ(IR) = [−1, 1] ⊆ IR e ∀ a, a ′ ∈ IR : ϕ(a) = ϕ(a ′) ⇐⇒ a εϕ a ′ ⇐⇒ a− a ′ ∈ ZZ ou a+ a ′ ∈ 12 + ZZ . Além disso, para todo a ∈ IR : ā = { x ∈ IR ∣∣∣ a− x ∈ ZZ ou a+ x ∈ 12 + ZZ } . A aplicação canónica γ ∈ (IR/εϕ)IR é: γ(a) = ā = { x ∈ IR ∣∣∣ a− x ∈ ZZ ou a+ x ∈ 12 + ZZ } ∀ a ∈ IR . A função ψ ∈ Bij ( IR/εϕ , [−1, 1] ) tal que ϕ = ψ ◦ γ é ψ(ā) = sen 2πa ∀ ā ∈ IR/εϕ . 58 O axioma da escolha Primeiro vamos generalizar o resultado de I.2.21: I.2.31 Proposição. Sejam A, B 6= 6O conjuntos e ϕ ∈ BA. Então : a) ϕ ∈ Inj(A, B) ⇐⇒ ∃ ψ ∈ AB com ψ ◦ ϕ = δ A . b) ϕ ∈ Sob(A, B) ⇐⇒ ∃ ω ∈ AB com ϕ ◦ ω = δ B . Demonstração: a) ” ⇐ ”: Suponha a existência de ψ ∈ AB com ψ◦ϕ = δ A e sejam a, a ′ ∈ A com ϕ(a) = ϕ(a ′). Segue ψ ( ϕ(a) ) = ψ ( ϕ(a ′) ) , ou seja, a = δ A (a) = (ψ ◦ ϕ)(a) = (ψ ◦ ϕ)(a ′) = δ A (a ′) = a ′. Logo ϕ ∈ Inj(A, B). ”⇒ ”: Suponha ϕ injetora. Escolhamos um a 0 ∈ A fixo. Para todo b ∈ ϕ(A) existe um único a ∈ A com ϕ(a) = b devido à injetividade de ϕ. Definamos ψa 0 ∈ AB por ψa 0 (b) =  a se ϕ(a) = b ∈ ϕ(A)a 0 se b 6∈ ϕ(A) . Então vale (ψa 0 ◦ ϕ)(a) = ψa 0 ( ϕ(a) ) = a ∀ a ∈ A. Portanto ψa 0 ◦ ϕ = δ A . (Mencionamos que se ϕ não é sobrejetora, esta função construida ψa 0 não é única, pois ela depende da escolha do a 0 ∈ A). b) ” ⇐ ”: Suponha a existência de ω ∈ AB com ϕ◦ω = δ B e seja dado b ∈ B. Escolhendo-se a = ω(b) obtemos b = δ B (b) = (ϕ ◦ ω)(b) = ϕ ( ω(b) ) = ϕ(a) e vemos que ϕ é sobrejetora. ”⇒ ”: Suponha ϕ é sobrejetora. Para todo b ∈ B consideremos o conjunto X b = { a ∈ A ∣∣∣ ϕ(a) = b} ⊆ A . Temos portanto a faḿılia F = { X b ∣∣∣ b ∈ B } ⊆ 2A , uma certa faḿılia de subconjuntos de A. Pela sobrejetividade de ϕ temos X b 6= 6O ∀ b ∈ B , i.e. F não contém a parte vazia de A (de fato F é uma partição de A ! [porquê ?]). Vamos escolher agora simultâneamente em cada um destes conjuntos X b exata- mente um elemento a ∈ X b para todo b ∈ B e vamos chamar este a escolhido 59 partição de A. Seja agora α ∈ AF uma funç~ao de escolha e definamos ω ∈ AB por ω(b) = α(X b ) ∀ b ∈ B . Vale para todo b ∈ B: (ϕ ◦ ω)(b) = ϕ ( ω(b) ) = ϕ ( α(X b ) ) = b = δ B (b), pois α(X b ) ∈ X b = { a ∈ A ∣∣∣ ϕ(a) = b} . Portanto, ϕ ◦ ω = δ B . Para finalizar a digressão sobre esta problemática, vejamos mais uma aplicação do axioma da escolha, provando a seguinte generalização de I.2.25: I.2.33 Observação. Para qualquer conjunto A com |A| ≥ 2 temos A 6∼ AA . Demonstração: Afirma-se Bij ( A, AA ) = 6O e basta provar Sob ( A, AA ) = 6O: Seja Ω ∈ (AA)A uma qualquer aplicação. Afirmamos que Ω jamais pode ser sobrejetora: Para todo a ∈ A indicamos por ϕa = Ω(a) o valor de Ω em a, i.e. Ω(A) = { ϕa ∣∣∣ a ∈ A} . Consideremos para cada a ∈ A o conjunto Ya = A \ { ϕa(a) } . Temos Ya 6= 6O , pois |A| ≥ 2. Considere agora a faḿılia F = { Ya ∣∣∣ a ∈ A} . Pelo axioma da escolha, existe uma função de escolha α ∈ AF. Temos portanto α(Ya) ∈ Ya , particularmente, α(Ya) 6= ϕa(a) ∀ a ∈ A . Definamos uma função ψ ∈ AA por ψ(x) = α(Yx) ∀ x ∈ A . Afirmamos ψ 6∈ Ω(A): Se fosse ψ = ϕa para algum a ∈ A, teŕıamos ψ(x) = ϕa(x) ∀ x ∈ A . 62 Particularmente, para x = a obteŕıamos ϕa(a) = ψ(a) = α(Ya) 6= ϕa(a) , um absurdo. Logo, ψ ∈ AA \ Ω(A), mostrando que Ω não é sobrejetora. As ordens |Inj(m, n)| e |Sob(m, n)| Sejam A e B conjuntos finitos com |A| = m ∈ IN e |B | = n ∈ IN . Para simplificar, vamos supor A = { 1, 2, 3, . . . , m } e B = { b1 , b2 , b3 , . . . , bn } . Sabemos BA é finito e vale ∣∣∣BA ∣∣∣ = |B ||A| = nm. Quantas destas nm aplicações são injetoras e quantas são sobrejetoras? Queremos portanto descobrir |Inj(A, B)| e |Sob(A, B)|. Abreviamos Inj(m, n) = Inj(A, B) e Sob(m, n) = Sob(A, B) e colocamos in(m) = |Inj(m, n)| e sn(m) = |Sob(m, n)| . A pergunta é: in(m) = ? e sn(m) = ? Claramente vamos ter in(m) ≤ nm e também sn(m) ≤ nm . A resposta para in(m) é fácilmente obtida: Toda ϕ ∈ Inj(m, n) é determinada pela m-upla ( ϕ(1), ϕ(2), . . . , ϕ(m) ) = (b i 1 , b i 2 , . . . , b im ) dos valores de ϕ, cujas coordenadas devem ser distintas para que ϕ seja injetora. Assim, existem n possibilidades para a escolha de b i 1 ∈ B , depois n−1 escolhas para b i 2 ∈ B, depois n−2 escolhas para b i 3 , . . . e finalmente n−m+1 escolhas para b im . Isto dá um total de n(n − 1) . . . (n −m + 1) m-uplas distintas com coordenadas distintas, ou seja in(m) = n(n− 1)(n− 2) . . . (n−m+ 1) = ( n m ) ·m! . Portanto temos 63 I.2.34 Proposição. A quantidade in(m) de aplicações injetoras de um conjunto A com m para um conjunto B com n elementos é dada por in(m) = n(n− 1)(n− 2) . . . (n−m+ 1) = n m  ·m! . Observamos que, para m > n obtemos in(m) = 0, em acordo com o fato que B tem que conter pelo menos m = |A| elementos para que uma aplicação inje- tora de A para B possa existir. Para m = n vemos que in(n) = n! . Neste caso temos Inj(n, n) = Sob(n, n) = Bij(n, n), devido à finitude dos conjuntos. Particularmente, o conjunto das permutações SA de um conjunto A = { 1, 2, . . . , n } contém exatamente |SA| = in(n) = n! elementos. A determinação de sn(m) é mais complicada e mencionamos somente o resultado: I.2.35 Proposição. A quantidade sn(m) das aplicações sobrejetoras de um conjunto A de m para um conjunto B de n elementos é dada por sn(m) = n m − ( n n−1 ) (n− 1)m + ( n n−2 ) (n− 2)m ∓ . . .+ (−1)k ( n n−k ) (n− k)m ± . . . +(−1)n−k ( n k ) km ± . . .+ (−1)n−1 ( n 1 ) 1m , ou seja, sn(m) = n∑ k=1 (−1)n+kkm · ( n k ) . 64 As composições internas ”naturais” em IN, ZZ e IR, a adição ” + ” e a multiplicação ” · ” , tornam-se nesta interpretação ” funções de duas variáveis com valores no próprio conjunto.” Assim, deveriamos escrever por exemplo + ∈ IRIR×IR e · ∈ IN IN×IN etc. . Como ninguem escreve + ( (a, b) ) para indicar a soma a+ b, introduzimos também em geral: Se M é um conjunto e > ∈ MM×M uma composição interna de M , o valor > ( (a, b) ) desta função em (a, b) é indicado por > ( (a, b) ) = a > b . a > b pode ser chamado por exemplo de ”o resultado da >-composição de a com b”. O resultado da >4-composição do exemplo c4) é portanto a >4 b = √ a2 + b2 − cos(ea + ba2) ∀ a, b ∈ IR . No exemplo e) temos ♣ >♥ = ∇ e ♠ >∇ = ♥ . Em geral, o cruzamento da linha do a com a coluna do b é o resultado a > b, para todos os a, b ∈ { ∇,♠,♥,♣ } . Vemos que uma composição interna > num conjunto finito M = { a1 , a2 , . . . , am } de m elementos é dada e pode ser identificada por um quadro de m2 entradas: > a 1 a 2 . . . a k . . . a m a 1 a 1 >a 1 a 1 >a 2 . . . a 1 >a k . . . a 1 >a m a 2 a 2 >a 2 a 2 >a 2 . . . a 2 >a k . . . a 2 >a m ... ... ... ... ... ... ... a i a i >a 1 a i >a 2 . . . a i >a k . . . a i >a m ... ... ... ... ... ... ... a m a m >a 1 a m >a 2 . . . a m >a k . . . a m >a m 67 O resultado a i > a k ∈ M da >-composição encontramos no ponto de cruzamento da i-ésima linha com a k-ésima coluna. Como MM×M é o conjunto de todas as composições internas de M , vemos que existem num conjunto M de m elementos exatamente ∣∣∣MM×M ∣∣∣ = mm2 composições internas (i.e. possibilidades de preencher um quadro de m ×m en- tradas arbitrariamente com os m elementos de M). Para que tenhamos uma idéia: Por exemplo no conjunto { ∇,♠,♥,♣ } existem 416 = 655362 ≈ 4, 29 · 109 (em palavras: 4, 29 bilhões de) composições internas distintas. Estruturas algébricas II.1.3 Definição. Seja M 6= 6O um conjunto e >∈MM×M uma composição interna de M. O par ( M ; > ) chama-se uma estrutura algébrica com uma composição interna. II.1.4 Exemplos. a) ( IN ; >1 ) , ( IN ; >2 ) , ( IN ; >3 ) , onde ∀ a, b ∈ IN : a >1 b = a+ b, a >2 b = a · b, a >3 b = ab são 3 estruturas algébricas com uma composição interna cada. b) ( ZZ ; >1 ) , ( ZZ ; >2 ) , ( ZZ ; >3 ) , onde ∀ a, b ∈ ZZ : a >1 b = a+ b, a >2 b = a · b, a >3 b = a− b são 3 estruturas algébricas com uma composição interna cada. c) ( IR ; >1 ) , ( IR ; >2 ) , ( IR ; >3 ) , ( IR ; >4 ) , onde ∀ a, b ∈ IR : a >1 b = a+ b, a >2 b = a · b, a >3 b = a− b a >4 b = √ a2 + b2 − cos(ea + ba2) , são 4 estruturas algébricas com uma composição interna cada. 68 d) Para todo conjunto E e M= 2E, os pares( M ; ∩ ) , ( M ; ∪ ) e ( M ; + ) , (onde X + Y = (X ∪ Y )\(X ∩ Y ) ∀ X, Y ∈M) são três estruturas algébricas com uma composição interna cada. e) O par ( { ∇,♠,♥,♣ } ; > ) , onde a composição >∈ { ∇,♠,♥,♣ }{ ∇,♠,♥,♣ }×{ ∇,♠,♥,♣ } é definida pela tabela > ∇ ♠ ♥ ♣ ∇ ∇ ♠ ∇ ♥ ♠ ♥ ∇ ♠ ♣ ♥ ♠ ♥ ♣ ♣ ♣ ♠ ♣ ∇ ♥ , é uma estrutura algébrica com uma composição interna (entre mais de 4 bilhões posśıveis outras no mesmo conjunto!) Às vezes convém considerar no mesmo conjunto várias composições internas si- multâneamente: II.1.5 Definição. Se M 6= 6O é um conjunto e >1 , >2 , . . . , >r ∈ MM×M são r composições internas de M, então o ”objeto” ( M ; >1 ,>2 , . . . , >r ) chama-se uma estrutura algébrica com r composições internas. II.1.6 Exemplos. a) ( IR ; + , · ) é uma estrutura com duas composições internas. 69 d) Seja M = { a1 , a2, a3 , . . . , am } e a estrutura algébrica ( M ; > ) definida pela tábua > a 1 a 2 . . . a i . . . a k . . . a m a 1 a 1 >a 1 a 1 >a 2 . . . a 1 >a i . . . a 1 >a k . . . a 1 >a m a 2 a 2 >a 2 a 2 >a 2 . . . a 2 >a i . . . a 2 >a k . . . a 2 >a m ... ... ... ... ... ... ... ... ... a i a i >a 1 a i >a 2 . . . a i >a i . . . a i >a k . . . a i >a m ... ... ... ... ... ... ... ... ... a k a k >a 1 a k >a 2 . . . a k >a i . . . a k >a k . . . a k >a m ... ... ... ... ... ... ... ... ... a m a m >a 1 a m >a 2 . . . a m >a i . . . a m >a k . . . a m >a m . Temos que ( M ; > ) é comutativa, se e somente se, a tábua é simétrica com relação a sua diagonal principal. Demonstração: a) é claro. b) Por exemplo: 2 > 3 = 23 = 8 6= 9 = 32 = 3 > 2 c) Por exemplo: 3 > − 5 = 3− (−5) = 8 6= −8 = −5− 3 = −5 > 3 d) A simetria da tábua diz: a i >a k = a k >a i para todos os i, k = 1, 2 , . . . , m. II.1.11 Observação. Num conjunto finito de m elementos M = { a1 , a2 , . . . , am } , existem exata- mente m m(m+1) 2 composições internas comutativas distintas. Por exemplo, das 416 composições existentes em M = { ∇,♠,♥,♣ } 410 são comutativas . Demonstração: Uma composição interna comutativa é determinada, preenchendo- se livremente as posições na diagonal e superior à diagonal. A quantidade destas posições é 1 + 2 + 3 + . . .+m = m(m+1)2 . 72 Centralizador e centro Em geral, uma estrutura algébrica ( M ; > ) não é comutativa. Isto não impede que certos elementos nela sejam comutáveis. II.1.12 Definição. Seja ( M ; > ) uma estrutura algébrica e 6O 6= X ⊆M. O conjunto C M (X) = { c ∈M ∣∣∣ c > x = x > c ∀ x ∈ X } chama-se o centralizador de X em M. C M (X) é portanto o conjunto dos elementos em M que comutam com cada elemento de X. Casos particulares: 1) Para X = { x } um conjunto unitário, temos C M (x) = C M ( { x } ) = { c ∈M ∣∣∣ c > x = x > c } , o centralizador de x em M. 2) Para X = M obtemos o centro de M : Z(M) = C M (M) = { c ∈M ∣∣∣ c > x = x > c ∀ x ∈M } Este é o conjunto dos elementos de M que comutam com todo elemento de M. Claro que ( M ; > ) é comutativa ⇐⇒ Z(M) = M. II.1.13 Proposição. Seja ( M ; > ) uma estrutura algébrica e 6O 6= X ⊆ Y ⊆M e x ∈M. Então a) x ∈ C M (x), particularmente, C M (x) 6= 6O. b) C M (Y ) ⊆ C M (X). c) Z(M) = ⋂ X⊆M C M (X) = ⋂ x∈M C M (x). d) Observamos que C M (X) = 6O é posśıvel, se |X | ≥ 2. 73 Demonstração: a) é claro, pois x comuta com si mesmo. b) Para c ∈ C M (Y ) temos c > x = x > c ∀ x ∈ Y. Particularmente, como X ⊆ Y , temos c > x = x > c ∀ x ∈ X. Segue c ∈ C M (X) e portanto C M (Y ) ⊆ C M (X) . c) Usando b), a afirmação segue, refletindo-se sobre as seguintes contenências: Z(M) ⊆ ⋂ X⊆M C M (X) ⊆ ⋂ { x}⊆M C M ( { x } ) = ⋂ x∈M C M (x) ⊆ Z(M) . Para a estrutura ( M ; > ) com M = { a, b } e > definida por: > a b a b b b a a . temos por exemplo Z(M) = 6O. Também para ( IN ; > ) , se a > b = ab ∀ a, b ∈ IN, temos Z(IN) = 6O. II.1.14 Definição. Seja ( M ; > ) uma estrutura algébrica. Um elemento e ∈M é chamado um a) elemento neutro (ou identidade) à esquerda, se e > x = x ∀ x ∈M . b) elemento neutro (ou identidade) à direita, se x > e = x ∀ x ∈M . c) elemento neutro (ou identidade) bilateral, se e > x = x > e = x ∀ x ∈M . Claro que, quando ( M ; > ) é uma estrutura comutativa, as noções de identidade (neutro) ”à esquerda”, ”à direita” e ”bilateral” são as mesmas. 74 Semigrupos e monóides II.1.18 Definição. a) Uma estrutura algébrica com uma composição interna ( M ; > ) é denomi- nada um semigrupo se a composição interna obedecer à lei associativa, i. e. se temos a > (b > c) = (a > b) > c para todos os elementos a, b, c ∈M. b) O semigrupo ( M ; > ) é dito um monóide, se possuir uma identidade bilateral. II.1.19 Exemplos. a) ( IN ; + ) e ( IN ; · ) são os semigrupos dos números naturais aditivo e dos números naturais multiplicativo. Ambos estes semigrupos são comutativos. ( IN ; · ) é um monóide.( IN ; + ) não possui identidade (lembrar: 0 6∈ IN). b) Seja M = (0, 5] o intervalo real semi-fechado à direita entre 0 a 5, > ∈ MM×M a composição a > b = ab 5 ∀ a, b ∈M . Então ( M ; > ) é um monóide comutativo. Sua identidade é e = 5. Se substituirmos M = (0, 5] pelo intervalo aberto M ′ = (0, 5),( M ′ ; > ) será um semigrupo comutativo sem identidade. c) A estrutura algébrica ( IN ; > ) com a > b = ab ∀ a, b ∈ IN não é um semigrupo. d) A estrutura algébrica ( ZZ ; > ) com a > b = a− b ∀ a, b ∈ ZZ não é um semigrupo. 77 Demonstração: a) é claro. b) Para todos os a, b ∈ M = (0, 5] temos também a > b = b > a = ab5 ∈ M . Portanto de fato >∈MM×M . Além disso, para todos os a, b, c ∈M temos a > (b > c) = a · bc5 5 = abc 25 = ab 5 · c 5 = (a > b) > c . e > b = eb 5 = b ∀ b ∈M significa e = 5. Isto mostra que o semigrupo ( M ; > ) é um monóide. Além disso, ( M ′ ; > ) não possui identidade, pois 5 6∈M ′. c) Temos 2 > (3 > 4) = 2 > 34 = 281. Mas (2 > 3) > 4 = 23 > 4 = 84 6= 281. d) Temos 2 > (3 > 4) = 2 > (3− 4) = 2− (−1) = 3. Mas (2 > 3) > 4 = (2− 3) > 4 = (−1)− 4 = −5 6= 3. II.1.20 Exemplo importante Seja A 6= 6O um qualquer conjunto e consideremos M = AA, o conjunto de todas as aplicações de A em si mesmo . Considerando-se para todas as ψ, ϕ ∈M a aplicação composta ψ ◦ ϕ , definida por (ψ ◦ ϕ)(a) = ψ ( ϕ(a) ) ∀ a ∈ A, vemos que ” ◦ ” define uma composição interna de AA, i. e. ◦ ∈MM×M = (AA)(AA×AA) , e portanto, ( AA ; ◦ ) é uma estrutura algébrica com uma composição interna. Sabemos que ω◦(ψ◦ϕ) = (ω◦ψ)◦ϕ para todas as ω, ψ, ϕ ∈ AA (a lei associativa válida e provada em I.1.14 para a composição de relações vale particularmente quando as relações são aplicações !). Portanto, a estrutura algébrica( AA ; ◦ ) 78 é um semigrupo. Além disso, δ A ◦ ϕ = ϕ ◦ δ A = ϕ ∀ ϕ ∈ AA. Logo, ( AA ; ◦ ) possui a identidade δ A e é portanto um monóide.( AA ; ◦ ) chama-se o monóide de todas as aplicações de A em A. II.1.21 Observação. Para |A| ≥ 2, o monóide( AA ; ◦ ) não é comutativo . Demonstração: Seja, digamos, A decomposto como A = { a, b } ∪ X com X = A\ { a, b } , onde a, b ∈ A são quaisquer dois elementos escolhidos com a 6= b (observe |A| ≥ 2). Sejam ϕ, ψ ∈M = AA definidas por ϕ(x) =  a se x = a a se x = b x se x ∈ X e ψ(x) =  b se x = a a se x = b x se x ∈ X . Temos (ψ ◦ ϕ)(a) = ψ ( ϕ(a) ) = ψ(a) = b , porém( ϕ ◦ ψ ) (a) = ϕ ( ψ(a) ) = ϕ(b) = a . Portanto, (ψ ◦ ϕ)(a) 6= ( ϕ ◦ ψ ) (a) e segue ψ ◦ ϕ 6= ϕ ◦ ψ . II.1.22 Exemplo. Para os elementos ϕ, ψ do monóide ( IRIR ; ◦ ) definidos por ϕ(t) = sen t e ψ(t) = t2 ∀ t ∈ IR temos (ψ ◦ ϕ)(t) = ψ ( ϕ(t) ) = ( sen t)2 = sen 2t , porém( ϕ ◦ ψ ) (t) = ϕ ( ψ(t) ) = sen (t2) . De fato vale para o centro do monóide ( AA ; ◦ ) : II.1.23 Proposição. Para qualquer conjunto A 6= 6O temos Z(AA; ◦ ) = { δ A } , 79 a) r é regular à esquerda ⇐⇒ λr ∈ Inj(M,M). c) r é regular à direita ⇐⇒ ξr ∈ Inj(M,M). c) r é regular bilateral ⇐⇒ ambas λr , ξr ∈ Inj(M,M). Demonstração: a) ( ∀ x, x′ ∈M : r > x = r > x′ =⇒ x = x′ ) ⇐⇒ ⇐⇒ ( ∀ x, x′ ∈M : λr(x) = λr(x′) =⇒ x = x′ ) A demonstração de b) é análoga. c) é combinação de a) e b). Se M é finito e se > é dada através de uma tábua, a regularidade à esquerda (à direita) de um elemento a ∈ M significa que na linha (coluna) do a não existem repetições II.1.29 Exemplo. Seja M = { ∇,♠,♥,♣ } e >∈MM definida por > ∇ ♠ ♥ ♣ ∇ ∇ ♠ ♥ ♥ ♠ ♥ ∇ ♠ ♣ ♥ ♠ ♥ ♣ ♣ ♣ ♠ ♣ ∇ ♥ Temos que ♣ é um regular à esquerda, porém não à direita, ♥ é um regular à direita, porém não à esquerda, ♠ é regular bilateral. II.1.30 Exemplo. Em ( IN ; > ) com a > b = ab temos: 1) Todo elemento é regular à direita. 2) Todo elemento a 6= 1 é regular à esquerda. 82 II.1.31 Observação. Seja ( M ; > ) um semigrupo. Então os conjuntos R′(M), R′′(M) e R(M) são fechados com respeito à composição >. Demonstração: Sejam r1 , r2 ∈ R ′(M) e suponhamos (r1 > r2) > x = (r1 > r2) > x ′ para dois elementos x, x′ ∈M. Segue r1 > (r2 > x) = r1 > (r2 > x ′). Devido à reg- ularidade à esquerda do r1 concluimos r2 > x = r2 > x ′. Pela mesma razão x = x′. Logo r1 > r2 ∈ R ′(M). O fechamento de R′′(M) é análogo (fazer a demonstração !). II.1.32 Definição. Seja ( M ; > ) uma estrutura algébrica com identidade bilateral e. Um elemento u ∈M chama-se um elemento i) inverśıvel à esquerda, se existe y ∈M com y > u = e. ii) inverśıvel à direita, se existe z ∈M com u > z = e. iii) bilateralmente inverśıvel, se é inverśıvel à esquerda e à direita. Às vezes usa-se a denominação ” unidade ” (à esquerda, à direita, bilateral) para esta espécie de elementos. Por U′(M) indicamos o conjunto das unidades à esquerda, por U′′(M) o conjunto das unidades à direita, por U(M) o conjunto das unidades bilaterais de M . Claramente, e ∈ U(M) = U′(M) ∩U′′(M) Todo elemento y ∈M com y > u = e, chama-se um inverso à esquerda de u. Todo elemento z ∈M com u > z = e, chama-se um inverso à direita de u. 83 Claro que para todo inverso à esquerda y de um u ∈ U′(M), temos y ∈ U′′(M) e para todo inverso à direita z de um u ∈ U′′(M), temos z ∈ U′(M). II.1.33 Observação. Seja ( M ; > ) um monóide. Então valem: a) Toda unidade à esquerda é regular à esquerda, ou seja U′(M) ⊆ R′(M) . b) Toda unidade à direita é regular à direita, ou seja U′′(M) ⊆ R′′(M) . c) Toda unidade bilateral é bilateralmente regular, ou seja U(M) ⊆ R(M) . Demonstração: Seja u ∈ U′(M). Assim, existe y ∈ M com y > u = e. Suponhamos, x, x′ ∈ M são tais que u > x = u > x′. Segue y > (u > x) = y > (u > x′) e dáı pela lei associativa, (y > u) > x = (y > u) > x′. Logo, e > x = e > x′, i.e. x = x′. Portanto, u ∈ R′(M). Logo, U′(M) ⊆ R′(M). Da mesma forma mostra-se b). c) é conseqüência de a) e b). II.1.34 Observação. Seja ( M ; > ) um monóide, e sua identidade. Seja u ∈ U(M). Então , para todos os y, z ∈M com y > u = e = u > z temos y = z . Demonstração: y = y > e = y > (u > z) = (y > u) > z = e > z = z . Isto significa que, para um elemento bilateralmente inverśıvel, todo inverso à es- querda é igual a todo inverso à direita. Particularmente, existe somente um inverso à esquerda e somente um inverso à direita para u ∈ U(M). Este único û ∈ M com û > u = u > û = e 84 II.1.39 Definição. Um monóide ( M ; > ) é denominado um grupo, se U(M) = M , i.e. se todo elemento em M é inverśıvel. II.1.40 Observação. Para todo monóide ( M ; > ) temos que( U(M) ; > ) é um grupo. II.1.41 Exemplos. a) Para todo conjunto A 6= 6O, temos que( U(AA) ; ◦ ) = ( S A ; ◦ ) é um grupo. b) Para o monóide ( ZZ ; · ) , temos que( U(ZZ) ; · ) = ( { 1,−1 } ; · ) é um grupo. II.1.42 Definição. Se A 6= 6O é um conjunto, o grupo ( S A ; ◦ ) consistindo de todas as permutações de A, é chamado o grupo de todas as permutações de A ou o grupo simétrico sobre A. Observamos que estes grupos simétricos são as estruturas algébricas mais funda- mentais para toda a Álgebra. Às vezes vale também a lei comutativa num grupo: II.1.43 Definição. Um grupo ( M ; > ) é dito comutativo ou abeliano se a > b = b > a ∀ a, b ∈M 87 (Niels Henrik Abel [1802- 1829]. Matemático norueguês). II.1.44 Exemplos. a) ( ZZ ; + ) , ( IR ; + ) , ( QI ; + ) são grupos abelianos. b) Seja P = { x ∈ IR ∣∣∣ x > 0} o conjunto dos números reais positivos. ( P ; · ) é um grupo abeliano . c) Se i = √ −1 indica uma solução (formal) da equação x2 + 1 = 0, temos que ( { 1,−1, i,−i } ; · ) é um grupo abeliano, Sua tábua de multiplicação é: · 1 −1 i −i 1 1 −1 i −i −1 −1 1 −i i i i −i −1 1 −i −i i 1 −1 88 § II.2 Subestruturas, estruturas quocientes e homomorfismos Subestruturas II.2.1 Definição. Seja ( M ; >1 , >2 , . . . , >r ) uma estrutura algébrica com r composições internas >1 , >2 , . . . , >r ∈MM×M . Um subconjunto S ⊆M chama-se uma subestrutura de ( M ; >1 , >2 , . . . , >r ) , se i) S 6= 6O ii) Para todos os a, b∈S temos a >1 b∈S, a >2 b ∈ S , . . . , a >r b∈S . Abreviado: a >i b∈S ∀ a, b∈S ∀ i = 1, 2 , . . . , r Isto significa portanto que S é fechado com respeito às composições internas definidas em M. Indicamos isto por( S ; >1 , >2 , . . . , >r ) ≤ ( M ; >1 , >2 , . . . , >r ) , ou simplesmente por S ≤M, se não houver dúvidas sobre as composições consid- eradas. O próprio S = M sempre é um exemplo de uma subestrutura de M. Se temos uma única composição > em M :( S ; > ) ≤ ( M ; > ) ⇐⇒ a > b∈S ∀ a, b∈S . Se ( M ; > ) é um semigrupo, uma subestrutura ( S ; > ) ≤ ( M ; > ) chama-se também um sub-semigrupo de M. II.2.2 Exemplos. a) Para ( ZZ ; + , · ) temos que a1) ( IN ; + , · ) ≤ ( ZZ ; + , · ) 89 Isto significa que a única subestrutura de M que contém X é a própria M. Neste caso o conjunto X é denominado um sistema de geradores para( M ; >1 , >2 , . . . , >r ) . II.2.6 Exemplo. a) A subestrutura de ( IN ; + ) gerada pelo conjunto X = {6, 15} é 〈X〉 = {6, 12, 15, 18, 21, 24, 27, 30 , . . .} = {6k + 15` > 0 | k, ` ∈ IN 0 } . b) 〈IP 〉 = ( IN ; · ) , i.e. o conjunto dos números primos X = IP é um sistema de geradores para o monóide múltiplicativo IN dos números naturais. Demonstração: a) Ponhamos E = {6k + 15` > 0 | k, ` ∈ IN 0 }. Temos {6, 15} ⊆ E e é claro que toda subestrutura S que contiver {6, 15}, tem que conter todas as somas 6k + 15` 6= 0 com k, ` ∈ IN 0 . Portanto E ⊆ S. Para todos os a = 6k1 + 15`1 e b = 6k2 + 15`2 em E temos a+ b = 6k1 + 15`1 + 6k2 + 15`2 = 6(k1 + k2) + 15(`1 + `2)∈E . Portanto, E é uma das subestruturas que contêm X. Logo, E = 〈X〉 . b) Isto deve se ao fato que todo número natural é produto de primos. Relações de congruência e estruturas quocientes II.2.7 Definição. Seja ( M ; >1 , >2 , . . . , >r ) uma estrutura algébrica. Uma relação de equivalência κ∈Eq(M) chama-se uma relação de congruência da estrutura ( M ; >1 , >2 , . . . , >r ) , se para todos os a, a ′, b, b ′∈M tivermos as seguintes compatibilidades de κ com as composições >1 , >2 , . . . , >r : Se  a κ a ′ b κ b ′ então  a >1 b κ a ′ >1 b ′ , a >2 b κ a ′ >2 b ′ , ... ... ... a >r b κ a ′ >r b ′ . 92 Mais abreviadamente: a κ a ′ b κ b ′ =⇒ a >i b κ a ′ >i b ′ ∀ i = 1, 2 , . . . , r . Por Cg ( M ; >1 , . . . , >r ) indicamos o conjunto de todas as relações de congruência da estrutura algébrica( M ; >1 , . . . , >r ) . Assim temos Cg ( M ; >1 , . . . , >r ) ⊆ Eq(M) . Para uma relação de congruência κ temos portanto: Se a κ a ′ e b κ b ′ então a >i b κ a ′ >i b ′ ∀ i = 1, 2 , . . . , r . Isto significa que duas congruências modulo κ podemos >i-compor verticalmente, sem destruir a κ-equivalência do resultado - como se as congruências fossem duas igualdades. Claro que temos Cg ( M ; >1 , >2 , . . . , >r ) = r⋂ i=1 Cg ( M ; >i ) . II.2.8 Exemplo. Para toda estrutura algébrica ( M ; >1 , >2 , . . . , >r ) temos δ M ∈ Cg ( M ; >1 , >2 , . . . , >r ) e M×M ∈Cg ( M ; >1 , >2 , . . . , >r ) , i.e. tanto a relação da igualdade como a relação universal em M são exemplos de relações de congruência. Particularmente, Cg ( M ; >1 , >2 , . . . , >r ) 6= 6O . II.2.9 Exemplos. Seja ( M ; >1 , >2 ) = ( ZZ ; + , · ) . 93 a) Para as relações de equivalência ≡n (ver I.1.26) vale de fato ≡n ∈ Cg ( ZZ ; + , · ) = Cg ( ZZ ; + ) ∩Cg ( ZZ ; · ) . b) Seja ε ∈ Eq(ZZ) definida pela partição Pε = { {x ∈ ZZ | x ≥ 0} , {x ∈ ZZ | x < 0} } . Então ε 6∈ Cg ( ZZ ; + ) . Demonstração: a) Sejam a, a ′, b, b ′ ∈ ZZ tais que  a ≡n a ′ b ≡n b ′ . Temos que a − a ′ e b − b ′ são múltiplos de n. Segue que também (a + b) − (a ′ + b ′) = (a− a ′) + (b− b ′) é múltiplo de n. Mas isto significa a+ b ≡n a ′ + b ′. Portanto, ≡n∈Cg ( ZZ ; + ) . Também ab− a ′b ′ = ab− a ′b+ a ′b− a ′b ′ = (a− a ′)b+ a ′(b− b ′) é múltiplo de n. Isto significa ab ≡n a ′b ′ . Portanto, ≡n∈Cg ( ZZ ; · ) . Assim, ≡n ∈ Cg ( ZZ ; + ) ∩Cg ( ZZ ; · ) = Cg ( ZZ ; + , · ) . b) Temos por exemplo  −8 ε − 26 ε 3 . Porém −2 = −8 + 6 6 ε − 2 + 3 = 1. Logo, esta ε ∈ Eq(ZZ) não é compat́ıvel com a adição em ZZ. As relações de congruência da estrutura algébrica ( ZZ ; + ) podem ser comple- tamente descritas. De fato, não existem outras além das ≡n : II.2.10 Teorema. Cg ( ZZ ; + ) = { ≡n ∣∣∣ n = 0, 1, 2, 3 , . . . } , i.e. as relações de congruência de ( ZZ ; + ) são exatamente as congruências mod n. (O mesmo vale a forteriori para Cg ( ZZ ; + , · ) ) Demonstração: Sabemos { ≡n ∣∣∣ n = 0, 1, 2, 3 , . . . } ⊆ Cg( ZZ ; + ) , devido 94