01. Conceitos Básicos de Conjuntos

SAVE OFFLINE

Teoria Grafos dos

CONCEITOS BÁSICOS DE CONJUNTOS

Nesta parte são apresentados os principais conceitos e resultados relacionados a funções e relações relevantes para a apresentação da TG.

• Definição 1 A família de todos os subconjuntos de um conjunto A é o conjunto potência de A, simbolizado por 2A.

 Exemplo: • A = {1,2,3} (3 elementos) • 2A = { Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} } (23 = 8 elementos)

• Definição 2 O par ordenado de a e b, notado por , é o conjunto { { a } , {a,b} } . Dado o par ordenado , a é a primeira coordenada do par, e b é a segunda.

A principal propriedade de um par ordenado, que deve ser passível de ser deduzida de sua definição, é sua unicidade.

 Teorema 1 Se = , então a = x e b = y * Note que = {{a},{a,b}} = {{a},{b,a}} = {{b,a},{a}} ≠ {{b},{a,b}} = . * Note também que = {{a},{a,a}} = {{ a},{a}} = {{a}}.

• Definição 3 O produto cartesiano dos conjuntos A e B, notado AxB, é o conjunto de pares ordenados cuja primeira coordenada é um elemento de A e a segunda coordenada é um elemento de B:

• A x B = { | a

Aeb

B}

 Exemplo: Considere os conjuntos A={1,2} e B={a,b,c}. Então, • AxB = {,,,,,} • BxA = {,,,,,} • AxA = {,,,}

Se o conjunto A tem n elementos (|A| = n) e o conjunto B tem m elementos (|B|= m), então os produtos cartesianos A x B e B x A têm m x n elementos.

Se A e B são considerados não vazios e A ≠ B, então AxB ≠ BxA. Se A ou B for Ø, então AxØ = ØxB = ØxØ =Ø

Considere os conjuntos X ={1} e Y = {1,2,3}. Então, • XxY = {,, } • YxX = {,,} • (XxY)

(YxX) = {}

• Observação

O produto cartesiano A x A x A x ... x A, de n conjuntos A tem por notação An .

• Definição 4 O conjunto f é uma função do conjunto A no conjunto B se e só se f for um subconjunto do conjunto de pares ordenados A x B e f e f, implica b = c.

 Exemplo: Considere os conjuntos f = { | x R} e g = { | x R} , em que R é o conjuntos dos reais. Embora f seja uma função, g não é função (uma vez que, por exemplo, g e g ).

Exemplo: Considere os conjuntos A = {1,2,3} e B = {a,b,c}. Cada um dos conjuntos f1 = {,}, f2 = {}, f3 = {, , } e f4 = {, } é uma função de A em B. Já o conjunto f5 = {, , } não é função de A em B, dado que f5 , f5 e a ≠c.

• Definição 5 Seja f AxB uma função. O domínio (Df) e o contradomínio (Cf) de f são os conjuntos: Df = {a | para algum b,

f}

Cf = {b | para algum a,

f}

Se Df = A, a função f é uma função total em relação a A. Se Cf = B, a função é sobre o conjunto B (f é, então, função sobrejetora).Uma função total de A em B é notada por f:A B.

 Exemplo: Função

Domínio

Contradomínio

Tipo

f1

{1, 2}

{a, b}

f2

{1}

{c}

f3

{1, 2, 3}

{a, b, c}

Não é total e nem sobre Não é total e nem sobre Total e sobre

f4

{1, 2}

{a}

Não é total e nem sobre

• Definição 6 Se f:A BeC A, então a função f (CxB) é a restrição f a C, escrita f|C. A função f é uma extensão da função g se e somente se g f.

 Exemplo: Considere os conjuntos A = {1,2,3,4}, B = {3,7,8,9} e a função total f:A B, expressa pelo conjunto {, , , }, como mostrado na Figura a seguir. Considere ainda o conjunto C = {2,3}.

Função total f:A B, expressa por {, , , }.

O produto cartesiano CxB = {2,3} x {3,7,8,9} = {, , , , , , , }. A restrição f|C = f (CxB) = {, , , } {, , , , , , , } = {, }.

• Definição 7 A composição das funções g e h, notada h°g, é definida como conjunto: • h°g = { | existe um y tal que g e h}.

 Exemplo: Considere os conjuntos X = {1,3,4,5}, Y = {a,b,c,d} e Z = {z1, z2, z3}, ilustrados na figura a seguir, e as funções g e h não são totais e são definidas por: • g = {, , } • h = {, }

A composição das funções g e h é a função expressa por: • h°g = { | existe um y tal que h} = {, , }

ge

Composição das funções g e h.

 Observação A composição h°g das funções g e h é também uma função. Se g:X Y e h: Y Z, então h°g: X Z e (h°g)(x) pode ser escrita como h(g(x)).

• Definição 8 Uma função total f:A B é injetora (ou um-a-um) quando associa elementos distintos de A a elementos distintos de B, ou seja, f é injetora se e só se f(x1) = f(x2) ..... x1 = x2.

Alternativamente, uma função f injetora se e só se x1 ≠ x2 f(x1) ≠ f(x2).

é

Uma função total que não é injetora é chamada, muitos-a-um.

• Definição 9

Uma função injetora e sobrejetora é chamada bijetora.

 Exemplo: A função g do Exemplo anterior não é injetora, pois g(3) = b, g(4) = b e 3 ≠ 4. A função h do mesmo exemplo é uma função injetora. Nenhuma delas, entretanto, é bijetora.

 Teorema 2 Seja f:A B uma função. Considere a função sobre g:f f’, tal que g() = . O conjunto f’ é uma função se e só se f for injetora. Além disso, f’ é total em B se e só se f for sobre B.

 Exemplos: (a) Considere os conjuntos A = {1,2,3}, B = {a,b} e a função sobrejetora f = {, , }, que não é injetora. Considere ainda a função g:f f’, tal que g() = , como estabelece o Teorema 2.

A função g é, pois, o seguinte conjunto: g = {,, }. Note que o conjunto f’ do Teorema 2 é o conjunto f’ = {,,} (como pode ser visualizado na Figura a seguir), que não é uma função (uma vez que f não é injetora).

Função g:f

f’ como estabelecida pelo Teorema 2.

(b) Considere os conjuntos A = {1,2,3}, B = {a,b,c,d} e a função f = {, , }, que é injetora, mas não sobrejetora. Considere, ainda, a função g:f f’, tal que g() = , como estabelece o Teorema 2.

A função g é, portanto, o seguinte conjunto: g ={,, }. Note que o conjunto f’ do Teorema 2 é o conjunto f’ = {, , }, que é uma função de B em A (uma vez que f é injetora).

Note, entretanto, que f’ não é o total (isto é, o domínio de f’ não é o conjunto B todo), uma vez que f não é sobrejetora).

(c) Considere os conjuntos A = {1,2,3}, B = {a,b,c} e a função f = {, , }, que é bijetora, ou seja, injetora e sobrejetora. A função g definida pelo Teorema 2 é o seguinte conjunto: • g = {,,}. Note que o conjunto f’ do Teorema 2 é o conjunto f’ = {, , }, que é uma função total de B em A.

• Definição 10

Se f:A B é uma função injetora, então a função inversa de f, notada por f-1, é o contradomínio da função g:f f’ com g() = . Se f não for injetora, f-1 não existe.

 Teorema 3 Considere os conjuntos A e B, com |A| = a e |B| = b. O número de funções totais de A em B é ba .

Considere os conjuntos A = {a,b} e B = {1,2,3}. Como |A| = 2 e |B| = 3, o Teorema 3 garante que o número de funções totais de A em B é 3². A tabela a seguir mostra as nove funções totais existentes.

f1

X

f2

X

f3

X











X X X

f4

X

f5

X

f6

X

X X X

f7

X

f8

X

f9

X

X X X

As nove funções totais de A em B existentes.

• Definição 11 Uma relação binária do conjunto A no conjunto B é um subconjunto do produto cartesiano AxB. Para indicar que um par pertence à relação R, escreve-se R ou xRy.

• Definição 12

Um subconjunto do produto cartesiano AxA é uma relação binária no conjunto A. O conjunto A x A é a relação universal em A.

 Exemplos: (a) Seja A = {1,2,3} e B = {a,b}, o conjunto R = {, , } é uma relação de A em B. Além disso, R, R, R.

(b) Seja {, relação

C = {a,b,c}, o conjunto R = , , } é uma em C. Além disso, R, R e R.

• Definição 13 Seja R uma relação e A um conjunto, então: • R[A] = { y | para algum x em A, xRy} É chamado conjunto relacionados dos elementos de A.

de

R-

(a) Considere a relação R = {, , , , }. A tabela mostra alguns conjuntos de R-relacionados.

A

Conjunto R-relacionados de A

{1}

{1,2}

{2}

{1,2}

{3}

{3}

{1,2}

{1,2}

{4}

(b)

Considere a relação: R = {, , , , , , , , , , , , }. A tabela mostra alguns conjuntos de R-relacionados.

A {1} {2} {3} {1,2} {1,3} {1,2,3} {4} {5} {4,5}

Conjunto R-relacionados de A {1,2,3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} {4,5} {4,5} {4,5}

• Definição 14 O domínio (Dω) e o contradomínio (Cω) da relação ω são: • Dω = {x | para algum y,

ω}

• Cω = {y | para algum x,

ω}

 Observação O domínio de uma relação é o conjunto de todas as primeiras coordenadas, e o contradomínio é o conjunto de todas as segundas coordenadas da relação, então ω[Dω] = Cω.

 Exemplo: Considere a relação R = {, , , , }. DR = {1,2,3}, e o conjunto dos R-relacionados de DR, isto é, R[DR] = {1,2,3} = CR.

• Definição 15 Se R é uma relação, então a relação reversa de R, R-1, é a relação tal que yR-1x se e só se xRy. (A relação reversa R-1 consiste nos pares ordenados que, quando invertidos, pertencem a R).

 Exemplos: (a) Seja A = {1,2,3} e B = {a,b}, a relação R = {, , }. A relação reversa de R é R-1 = {, , }.

(b) Seja B = {a,b,c} e a relação R = {, , , }, a relação reversa de R é R-1 = {, , , }.

• Definição 16 A relação R no conjunto A é: (a) Reflexiva: se xRx para todos x A; (b) Irreflexiva: se x A | R; (c) Anti-reflexiva: se R, para nenhum x A; (d) Identidade: se for reflexiva e se R, para x,y A x = y;

(e) Simétrica: se R, para x,y A R; (f) Não simétrica(ou assimétrica): se x,y A, tal que R e R; (g) Anti-simétrica: se R e R, para x,y A x = y; (h) Transitiva: se e R, para x,y,z A R.

 Exemplo:

(a) Seja A = {1,2,3,4} e R = {, , , , } uma relação em A. R é irreflexiva ( R) e não é simétrica.

(b) Como R implica R-1, então R é uma relação simétrica se e só se R = R-1.

(c) Em uma relação anti-simétrica, se a ≠ b, então possivelmente a estará relacionado com b ou b com a, mas nunca ambos.

(d) Seja A = {1,2,3,4} e a relação R = {, , , }, a relação R não é antisimétrica em A, pois R e R. Tampouco é uma relação simétrica, dado que R e R.

(e) A relação ≤ em um conjunto de números é reflexiva, anti-simétrica e transitiva. A relação < é anti-reflexiva, anti-simétrica e transitiva.

(f) Para o conjunto A = {1,2,3}, a tabela a seguir mostra algumas relações definidas em A e suas propriedades.

Relações

Reflexiva

Simétrica

Anti-simétrica

Transitiva

R1 = {,,,}

N

N

N

N

R2 = {,,,,,}

S

N

N

N

R3 = {}

N

N

S

S

R4 = AxA

S

S

N

S

R5 = {}

N

S

S

S

R6 = {, }

N

N

S

S

R7 = {,,,,}

N

N

N

N

R8 = {,}

N

N

S

N

Relações em A = {1,2,3} e propriedades (S: sim, N: não).

A tabela a seguir nomeia algumas relações relevantes. São de particular interesse as relações de equivalência e de ordem parcial, que serão tratadas oportunamente. Relações de compatibilidade (reflexiva e simétrica) podem ser abordadas como generalizações de relações de equivalência (reflexiva, simétrica e transitiva).

Elementos que estão relacionados por meio de uma relação de compatibilidade são vistos como compatíveis, mas não necessariamente como equivalentes.

Relação de

Reflexiva Anti-reflexiva Simétrica Anti-simétrica

Equivalência

X

Quase equivalência Compatibilidade

X

Ordem parcial

X

Ordem estrita Quase ordem

Transitiva

X

X

X

X

X

X

X

X

X

X

X

Relações e propriedades

X

• Definição 17 Uma partição P(A) de um conjunto A, P(A) = {Ai | i I,} é uma família de subconjuntos distintos e não vazios, tal que , i,j I, i ≠ j. Os i IAi = A e Ai ∩ Aj = conjuntos Ai são chamados blocos da partição.

 Exemplo: Seja A = {1,2,3,4}. Algumas partições de A: P1(A) = {{1,2}, {3,4}}, P2(A) = {{1}, {2}, {3}, {4}}, P3(A) = {{1}, {2,4}, {3}}, P4(A) = {{1,2,3,4}}.

• Definição 18

Uma relação em um conjunto é uma relação de equivalência se for reflexiva, simétrica e transitiva.

• Definição 19 Seja R uma relação de equivalência no conjunto A, considere o elemento a A. O conjunto dos R-relacionados de a, R[{a}], notado por [a], é chamado R-classe de equivalência gerada por a.

 Teorema 4 Seja R uma relação de equivalência no conjunto A e sejam a,b A, então: (a) a [a] (b) se aRb, então [a] = [b]

 Teorema 5 Seja X o conjunto de relações de equivalência eu um conjunto A e seja Y o conjunto de partições de A. Seja p qualquer elemento de X. Existe uma função bijetora f:X Y, tal que f(p) é o conjunto de todas as p-classes de equivalência geradas por elementos de A.

 Exemplos: (a) Sejam a, b e m inteiros (m≠0). A relação congruência módulo m no conjunto dos inteiros é definida como: a é congruente a b módulo m se e só se a-b for divisível por m.

Congruência módulo m é uma relação de equivalência com o número de classes de equivalência na partição induzida pela relação igual a m.

Quando m = 5, o conjunto de todos os inteiros é particionado em cinco classes de equivalência: [0] ={...,-5,0,5,10,15,...}, [1] = {...,-4,1,6,11,16,...}, [2] ={...,-3,2,7,12,17,...}, [3] = {...,-2,3,8,13,18,...}, [4] = {...,-1,4,9,14,19,...}.

(b) Considere o conjunto A = {-2,-1,0,1,2,3,4} e a relação de congruência módulo 3 definida em A, notada por ≡3. Como definido anteriormente, um par do conjunto AxA pertence à relação de congruência módulo 3 se x-y for divisível por 3. Tem-se pois que ≡3 = {, , , , , , , , , , , , , , , , }

Como pode ser facilmente verificado, a relação ≡3 é reflexiva, simétrica e transitiva e, portanto, é uma relação de equivalência. Devido ao fato de ser uma relação de equivalência, ela induz sobre o conjunto A uma partição em classe de equivalência. As classes de equivalência são:

• [-2] = {-2,1,4} = [1] = [4] • [-1] = {-1,2} = [2] • [0] = {0,3} = [3] Relações de ordem de vários tipos são importantes, pois buscam estabelecer formas de ordenação dos elementos de determinado conjunto.

Para refletir a noção intuitiva de ordenação, é importante notar de qualquer relação de ordem deve ser transitiva e não pode ser simétricas, porque se x precede y, de acordo com uma certa ordenação, y não pode preceder x de acordo com a mesma ordenação.

Além disso, se x precede y e y precede z, então x também deve preceder z, ou seja, a relação deve ser transitiva.

• Definição 20 Uma relação reflexiva, antissimétrica e transitiva em um conjunto, é uma relação de ordem parcial ou uma ordenação parcial no conjunto. Se R é uma relação de ordem parcial em A, o par ordenado é um conjunto parcialmente ordenado.

 Exemplo: A relação ≤ (menor ou igual) em qualquer subconjunto dos números é uma relação de ordem parcial. A relação < (menor) não é reflexiva e, portanto, não é de ordem parcial.

 Definição 21 Para a,b A, a < b se e só se a ≤ b e a ≠ b. Se a < b, diz-se que a precede b ou que b segue a.

• Definição 22 Uma relação de ordem parcial ≤ em um conjunto A é simples (ou linear, total, completa) se e só se a ≤ b ou b ≤ a para todo a,b A. Se ≤ é uma ordem simples em A, o par (A,≤) é uma cadeia. Se para algum a,b não acontece a ≤ b ou b ≤ a, a e b são ditos incomparáveis.

 Exemplos: (a)

Seja A = {1,2,3,5,6,10,15,30} o conjunto dos números que dividem 30, o conjunto A é parcialmente ordenado pela relação ‘‘menor ou igual’’, notada por ≤, e também pela relação ‘‘divide’’, notada por ≤’. Então, (A,≤) e (A,≤’) são diferentes conjuntos parcialmente ordenados. Apenas (A,≤) é uma cadeia. Ambas relações estão descritas a seguir:

≤ = { , , , , , , , , , , , , , ,, , , , , , , , , , , , , , , , , , , , , }

≤’ = {, , , , , , , , , , , , , , , , , , , , , , , , , , }

(b)

A relação (contido) em qualquer família de conjuntos é uma relação de ordem parcial. Raramente é uma ordem simples. Seja A = {1,2,3}, então P(A) = { , {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, A }. O par (P(A), ) não é ordenado por uma relação de ordem simples. Por exemplo, {1,2} {2,3} e {2,3} {1,2}, ou seja, {1,2} e {2,3} são incomparáveis.

Já o par (A, ), em que A = { Ø , {1}, {1,3}, {1,2,3}}, é um conjunto ordenado por uma relação de ordem simples. = {< Ø , Ø >, < Ø,{1}>, < Ø ,{1,3}>, < Ø , {1,2,3}>, , , , , , }

• Definição 23 O menor elemento de um conjunto A referente a uma relação de ordem parcial ≤ em A é um elemento b A, tal que, para todo a A, b ≤ a.

• Definição 24 O maior elemento de um conjunto A referente a uma relação de ordem parcial ≤ em A é um elemento b A, tal que, para todo a A, a ≤ b.

 Exemplo: Considere a família de conjuntos: A = {{1}, {2}, {3}, {1,2}, {1,3}, {2,3}}. Com relação à ordem parcial em A, não existe menor nem maior elemento.

= {, , , , , , , , , , , }

Considere agora A relação fica:

{ Ø } = { Ø ,{1}, {2},{3},{1,2},{1,3},{2,3}}. A

= { , , , , , , , , , , , , , , , , , , } e, portanto, Ø é o menor elemento.

Considere, ainda, A {Ø} {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}. A relação se torna:

{{1,2,3}}

=

{

Ø,

={,,,,,,,, , , , , , , , , , , , , , , , , , , } Portanto, o conjunto A {Ø} parcial , tem menor e maior elementos.

{{1,2,3}}, referente à relação de ordem

 Observação

Com relação a alguma ordem parcial, um conjunto pode ter, no máximo, um menor elemento e um maior elemento.

• Definição 25 Um elemento minimal de um conjunto A com relação a uma ordem parcial ≤ em A é um elemento b A, tal que, para nenhum a A, a < b. De maneira semelhante, b é um elemento maximal se b < a para nenhum a A.

 Exemplo: Considere novamente a família de conjuntos: A = {{1},{2},{3},{1,2},{1,3},{2,3}} do exemplo anterior. Com relação à ordem parcial em A, a família tem:

• Três elementos minimais: {1}, {2} e {3}; • Três elementos maximais: {1,2}, {1,3} e {2,3}. Já a família A {Ø} {{1,2,3}} tem um único elemento minimal e um único elemento maximal.

 Observação O fato de um conjunto ter um menor (maior) elemento implica que o conjunto tem exatamente um elemento minimal (maximal). O inverso não é verdade.

• Definição 26

Seja A um conjunto parcialmente ordenado por ≤, e seja Ø B A,

(a) Um elemento a A é um limitante superior de B se e só se para todo b B, b ≤ a. O menor elemento do conjunto de todos os limitantes superiores de B é o menor limitante superior ou supremo de B, simbolizado por sup(B);

(b) Um elemento a A é um limitante inferior de B se e só se para todo b B, a ≤ b. O maior elemento do conjunto de todos os limitantes inferiores de B é o maior limitante inferior ou ínfimo de B, simbolizado por inf(B).

 Exemplo: Considere o parcialmente por .

conjunto

P({1,2,3})

ordenado

= {,,,,,, ,, , , , , , , , , , , , , , , , , , , }

B1 = {{1},{2}} O conjunto dos limitantes superiores de B1 é {{1,2},{1,2,3}}. O conjunto B1, tem um único limitante inferior: Ø. Então, sup(B1) = {1,2} e inf(B1) = Ø. Nenhum deles pertence a B1.

B2 = {{1},{1,2}} O conjunto dos limitantes superiores de B2 é {{1,2},{1,2,3}}. O conjunto dos limitantes inferiores de B2 é { Ø,{1}}. Então sup(B2) = {1,2} e inf(B2) = {1}. Tanto o supremo quanto o ínfimo de B2 pertencem a B2.

• Definição 27 Seja (A, ≤) um conjunto parcialmente ordenado. O sistema (A,≤) é um reticulado se e só se cada par de elementos ai e aj de A tiver um supremo e um ínfimo em A. Denotam-se sup(ai,aj) por ai aj e inf(ai,aj) por ai aj.

• Definição 28 O reticulado (A, , se, para todo a,b,c A,

) é distributivo

• a (b c) = (a b)

(a c)

• a (b c) = (a b)

(a c)

A figura abaixo mostra a representação gráfica de três reticulados.