Matemática Discreta

Matemática Discreta

(Parte 10 de 14)

5.7 Isomorfismo

Uma relação R: A → B é um isomorfismo se, e somente se, existe uma relação S: B → A tal que:

=SR idA

=RS idB onde idA é uma endorrelação de igualdade em A =,A e idB é uma endorrelação de igualdade em B =,B, chamadas de relação identidade.

Assim, se =SRidA e =RSidB, podemos afirmar que a relação R possui inversa. Ainda, se existe um isomorfismo entre dois conjuntos, podemos chama-los de conjuntos isomorfos.

b a c b

Matemática Discreta

Márcia Rodrigues Notare 36

Exemplo: Dados os conjuntos A = {a, b, c} e B = {e, f, g} e a relação R: A → B tal que {}gcfbeaR,,,,,=. R é um isomorfismo, pois considerando a relação inversa de R,

Logo, a relação R possui inversa e os conjuntos A e B são conjuntos isomorfos.

Teorema: Seja R: A → B uma relação. Então R é um isomorfismo se, e somente se, R for simultaneamente um monomorfismo e um epimorfismo.

Dessa forma, uma relação é um isomorfismo se, e somente se, for simultaneamente uma relação total, injetora, funcional e sobrejetora.

Podemos observar que para uma relação ser um isomorfismo, os conjuntos origem e destino devem possuir o mesmo número de elementos.

Matemática Discreta

Márcia Rodrigues Notare 37

6 FUNÇÕES PARCIAIS E TOTAIS

Uma função parcial nada mais é do que um relação que é funcional. Se a relação funcional for também total, então a denominamos de função total. Portanto, podemos dizer que toda função total é uma função parcial e que toda função parcial é uma relação. Entretanto, nem toda relação é uma função parcial, assim como nem toda função parcial é uma função total.

6.1 Função Parcial

Uma função parcial é uma relação funcional, ou seja, cada elemento do domínio está relacionado a no máximo um elemento do contra-domínio.

Um elemento pertencente à função parcial fba∈,pode ser representado por ()baf=.

Exemplo: Dados os conjuntos A = {a} e B = {x, y} temos que as seguintes relações são funções parcias:

Vale observar que a relação inversa de uma função parcial não necessariamente é uma função parcial. Se considerarmos o conjunto A = {0, 1, 2} e a função parcial f: A → A tal que{}1,2,1,0=f, temos que a relação inversa de f, {}2,1,0,1=−f não é uma relação funcional e, consequentemente, não é uma função parcial.

Para que a relação inversa de uma relação funcional seja uma função parcial, ela deve ser também injetora (que é o dual de funcional).

6.2 Função Total

Uma função total é uma função parcial que é total. Em outras palavras, é uma função parcial definida para todos os elementos do domínio.

Se uma função é total, dizemos apenas que é uma função, ou seja, sempre que mencionarmos apenas função, estamos nos referindo a funções totais. Assim, podemos verificar as seguintes propriedades:

- Função Injetora = monomorfismo - Função Sobrejetora = epimorfismo

- Função Bijetora = isomorfismo

Ou seja, uma função bijetora é uma função injetora e sobrejetora. Da mesma forma que para funções parciais, a relação inversa de uma função não necessariamente é uma função. Considerando os conjuntos A = {0, 1} e B = {0, 1, 2} e a função{}0,2,1,1,0,0:=→ABf, temos que a relação inversa de f, {}2,0,1,1,0,01=−f não é uma relação funcional e, portanto, não é uma função.

Podemos considerar também a função g: A → B, tal que {}1,1,0,0=g. A inversa de g, {}1,1,0,01=−g não é uma relação total e, portanto, não é uma função.

Para que a relação inversa de uma função f seja uma função, f deve ser uma função bijetora.

Matemática Discreta

Márcia Rodrigues Notare 38

7 CARDINALIDADE DE CONJUNTOS

A cardinalidade de um conjunto nada mais é do que a medida de seu tamanho. Dois conjuntos A e B possuem o mesmo número de elementos ou a mesma cardinalidade, ou ainda são ditos equipotentes, denotado por

BA ## = se existe uma correspondência um-para-um BAf→:.

O conceito de cardinalidade permite definir conjuntos finitos e infinitos.

7.1 Cardinalidade Finita e Infinita A cardinalidade de um conjunto A, representada por #A é:

Finita: se existe uma bijeção entre A e o conjunto {1, 2, 3,, n}, para algum Ν∈n. Neste

caso, #A = n.

- Infinita: se existe uma bijeção entre A e um subconjunto próprio de A, ou seja, se conseguimos "tirar" alguns elementos de A e ainda assim podemos estabelecer uma bijeção com A.

Exemplo: Mostre que o conjunto dos números inteiros Z é um conjunto infinito.

Para mostrar que Z é um conjunto infinito, precisamos mostrar que existe uma bijeção entre ele e um subconjunto próprio dele, como por exemplo, o conjunto dos números naturais N. Portanto, precisamos encontrar uma função bijetora Ν→Ζ:f. Suponha Ν→Ζ:f, tal que:

A tabela abaixo mostra os valores de f(a) e sugere o relacionamento um-para-um entre Z e N.

Temos que f é uma função bijetora e sabemos que N é um subconjunto próprio de Z. Portanto, Z é um conjunto infinito, como queríamos mostrar.

Vale ressaltar que nem todos os conjuntos infinitos possuem a mesma cardinalidade. Podemos dizer que um conjunto infinito A é dito:

Matemática Discreta

Márcia Rodrigues Notare 39

- Contável: se existe um bijeção entre A e um subconjunto infinito de N.

- Não-Contável: caso contrário. A bijeção que define o conjunto A como conjunto contável é dita enumeração de A.

Exemplo: Os conjuntos Z (inteiros) e Q (racionais) são conjuntos contáveis e os conjuntos I (irracionais) e R (reais) são conjuntos não-contáveis.

(Parte 10 de 14)

Comentários