Capítulo 3 - Relações
Uma das principais razões do sucesso e universalidade da teoria de conjuntos na matemática reside no facto
de praticamente todas as noções e conceitos da matemática se poderem reduzir, definir ou explicar em
termos de conjuntos e operações com conjuntos. Neste e no próximo capítulo ilustraremos tal facto
mostrando como dois conceitos matemáticos essenciais1 - relação e função - se podem representar em
termos de conjuntos.
Neste capítulo introduzir-se-á o importante conceito de relação entre vários conjuntos e num conjunto.
Particular atenção será dada às relações binárias. Falar-se-á, nomeadamente, das relações de equivalência e
da partição de um conjunto que estas induzem (o chamado conjunto quociente), e das relações de ordem,
analisando-se as ordens parciais, totais e boas ordens, e, ainda, as relações "bem fundadas".
Secção 1: Relações.
No dia a dia estamos constantemente a associar objectos do mesmo ou de diferentes tipos2. Por exemplo,
quando dizemos "aquele fulano é primo de sicrano" estamos a associar (relacionar) duas pessoas; quando
pedimos a lista (ou a tabela) dos salários de uma determinada empresa, estamos a associar (relacionar)
pessoas3 e números (os salários); quando dizemos "estas duas rectas são paralelas" estamos a associar
(relacionar) duas rectas; quando dizemos "este aluno está inscrito nesta disciplina" estamos a associar
(relacionar) pessoas e disciplinas.
Dos exemplos anteriores facilmente se extraem alguns aspectos essenciais:
• Embora possamos associar dois objectos "à toa", usualmente tal associação corresponde a uma
propriedade que esses objectos satisfazem (e, de facto, uma condição P(x,y) pode ser vista como
definindo uma relação, formada pelos pares de objectos (a,b) que satisfazem tal condição, i.e. tais que
P(a,b) é uma proposição verdadeira).
• Normalmente, dizemos (ou está implícito) que tipo de elementos estamos a relacionar.
• Finalmente, uma forma prática e muito usual de apresentar graficamente uma certa associação/relação
consiste em recorrer a uma tabela. Por exemplo, a tabela (incompleta) a seguir seria uma forma de
representar a relação de inscrição (de um aluno numa disciplina):
Aluno
José António
José António
Maria Couceiro
...
Disciplina
Análise Matemática I
Paradigmas da Programação
Análise Matemática I
...
1 E de grande aplicação em muitas áreas do saber e, naturalmente, também em Computação (veja-se, por exemplo, a
importância do conceito de relação em Bases de Dados).
2 O termo tipo está a ser aqui usado de forma informal.
3 Ou, mais precisamente, identificadores de pessoas, que poderão ser sequências de caracteres (os nomes das pessoas), ou
números (em muitas instituições cada membro tem um número que o identifica univocamente, dito a sua chave - o número do
Bilhete de Identidade funciona como tal chave na sociedade).
63
O facto de existir uma linha da tabela com (José António, Análise Matemática I), significa que o José
António está inscrito na disciplina Análise Matemática I (estão associados/relacionados por essa
propriedade de "estar inscrito em"); o facto de não existir na tabela qualquer linha com (José António,
Análise Matemática III) significa que o José António não está inscrito em Análise Matemática III (i.e. o
José António não está relacionado com Análise Matemática III por aquela propriedade4.
Do que dissemos, facilmente se conclui que uma forma natural de representar em matematica
(recorrendo à teoria de conjuntos) tal conceito fundamental, de associação/relação, consiste em ver esta
como um conjunto de pares ordenados (o conjunto dos pares que estão relacionados por tal associação).
Repare-se que a ordem por que referimos os elementos que satisfazem uma dada associação é relevante:
pense-se, por exemplo, na associação "ser pai de".
Por outro lado, nos exemplos anteriores apenas se considerou associações entre pares de elementos. Tal
é a situação mais comum, e de maior interesse, pelo que ela terá um tratamento especial nestas folhas
(nomeadamente através da introdução de notações específicas para lidar com tais associações). No entanto,
podemos facilmente conceber outro tipo de associações de interesse.
Por exemplo, a condição P(x,y,z), dada por x+y=z2, define uma associação entre três elementos.
Supondo que estamos a trabalhar no domínio dos naturais, então alguns ternos que estão assim
relacionados são (0, 0, 0), (0, 1, 1), (2, 2, 2), etc. Já o terno (2, 3, 1) não pertence a tal relação (i.e. não
satisfaz a associação definida por tal condição, uma vez que P(2,3,1) é uma proposição falsa).
Como um outro exemplo, fora do domínio da matemática, podemos considerar uma tabela que nos dá
os dados de cada empregado de uma empresa, como a que se segue:
Nome
José António
José Marçal
Maria Couceiro
...
Morada
Av. ...
Rua ...
Av. ...
Telefone
291...
291...
291...
Salário
1000
1500
2000
em que cada linha da tabela, corresponde ao que se costuma designar pela ficha ou registo de um
empregado, e expressa uma associação entre pessoas (nomes - sequências de caracteres), moradas
(sequências de caracteres), telefones (números), salários (números inteiros positivos), etc.
Igualmente podemos ver (representar) esta associação como um conjunto de tuplos (no caso
quádruplos).
4 Naturalmente, esta forma de representar uma relação só é viável se o número de elementos que se encontram relacionados
for finito (e, na prática, não demasiado grande). Por outro lado, vendo uma tabela, como a de cima, como um conjunto de pares
ordenados, tem-se que a primeira coluna nos dá a primeira coordenada, ou primeira projecção, do par ordenado que é
representado por cada linha, e a segunda coluna nos dá a segunda coordenada, ou segunda projecção de tal par. Às funções que
aplicam cada par da relação na suas coordenadas, chamam-se em matemática de projecções (primeira e segunda); quando as
relações são representadas por tabelas é vulgar denominar tais projecções como os atributos da relação. Assim, "Aluno" e
"Disciplina" foram os nomes dados naquela tabela a tais atributos da relação de "inscrição".
64
Estamos assim em condições de apresentar o conceito matemático de relação que é usado para
representar tais (diferentes fomas de) associações.
Genericamente falando, em matemática, uma relação não é mais do que um conjunto de sequências de
elementos, todas com o mesmo comprimento (em que o facto de uma dada sequência pertencer a esse
conjunto significa que os elementos que formam essa sequência estão associados pela relação em questão).
Tal conduz-nos à definição a seguir, onde se fixa o número de elementos que formam as sequências que
compõem (constituem, traduzem) uma dada relação:
Definição 1:
Uma relação n-ária (n≥1) 5, R, é um qualquer conjunto de sequências de n elementos (i.e. n-tuplos).
Se (x1, ..., xn) ∈ R diz-se que o tuplo (x1, ..., xn) está em relação por R (ou por intermédio de R)6; se
(x1, ..., xn) ∉ R diz-se que o tuplo (x1, ..., xn) não está em relação por R.
Se n=1, diz-se que R é uma relação unária; se n=2, diz-se que R é uma relação binária; se n=3, diz-se
que R é uma relação ternária; e assim sucessivamente.
∇
Exemplo 1:
a) O conjunto {(1,2,3), (2,1,4)} representa uma relação ternária.
b) O conjunto {(1,2), (1,4), (3,5)} representa uma relação binária.
c) O conjunto {(1,a), (1,b), (3,a)} representa igualmente uma relação binária.
d) O conjunto {(1,a,2,5), (1,b,2,7), (3,a,7,2)} representa uma relação quaternária.
e) O conjunto {(1,2), (1,3,4)} já não representa uma relação, pois é formado por tuplos de diferentes
comprimentos.
∇
Por outro lado, como observámos atrás, normalmente nós precisamos o "tipo" dos elementos que
estamos a associar. Tal pode ser visto como indicando, à partida, quais são os conjuntos a que podem
pertencer os elementos que formam as sequências que compõem a relação. A definição a seguir traduz essas
situações:
Definição 2:
Uma relação n-ária R (n≥1) entre os conjuntos A1, ..., An é um subconjunto do produto cartesiano
A1x...xAn.
Se n=2, diz-se que R é uma relação binária entre A1 e A2; se n=3, diz-se que R é uma relação ternária
entre A1, A2 e A3; e assim sucessivamente.
Se A1=...=An=A, diz-se que R é uma relação n-ária em A (isto é, R é uma relação n-ária num conjunto
A sse R ⊆ An).
5 Por razões mnemónicas é costume usar a letra R para designar genericamente uma relação.
6 Também se diz por vezes, com o mesmo sentido, que o tuplo (x , ..., x ) satisfaz a relação R.
1
n
65
Se n=1, fala-se de uma relação unária no conjunto7 A; se n=2, fala-se numa relação binária em A; e
assim sucessivamente).
∇
Exemplo 2:
a) Seja A = {1,2,3} e B = {a,b}. Então {(1,a), (3,a), (3,b)} é (um exemplo de) uma relação binária entre A
e B.
b) Seja A = {1,2,3}, B = {a,b} e C = {1,4,5}. Então {(1,a,1), (1,a,4), (3,b,5)} é uma relação entre A, B e
C (uma relação ternária).
c) Seja A = {1,2,3,4}. Então {(1,2), (1,3), (4,3)} é uma relação binária em A.
d) Seja A = {1,2,3,4}. Então {1,3} pode ser encarado como uma relação unária em A (ver última nota de
rodapé).
e) Seja A = {1,2,3,4}. Então {(1,2,1), (1,1,3), (2,2,2), (4,3,2)} é uma relação ternária em A.
f) A relação vazia ∅ pode ser encarada como uma relação de qualquer aridade num conjunto A.
∇
As relações com maior utilização em matemática são as relações binárias8. É portanto natural que se
introduza algumas notações, e noções específicas, apropriadas a este tipo de relações.
Notação:
Seja R uma relação binária. Então pode escrever-se xRy em vez de9 (x,y)∈R, e em vez de se dizer que o
par (x,y) está em relação por R, diz-se simplesmente que x está em relação com y por R, ou que x está na
relação R com y. Por outro lado, pode escrever-se x R/ y para designar que (x,y)∉R.
∇
Definição 3:
Seja R uma relação binária. Então:
a) Chama-se domínio de R ao conjunto de todos os elementos x para os quais existe (pelo menos) um y
tal que xRy. Designando o domínio de R por dom(R), tem-se:
dom(R) = {x: ∃y xRy}
Para designar o domínio de R também se usa domR.
7 Estritamente de acordo com esta definição, uma relação unária R em A seria um subconjunto de A1 = {(x): x ∈ A} (veja-se as
definições 3 e 4 da secção 2.5). No entanto, é costume (neste contexto) identificar uma sequência formada por um só elemento
com esse elemento, e dizer que uma relação unária em A é um qualquer subconjunto de A. Assim, por exemplo, a propriedade
"ser par" define a seguinte relação unária sobre os naturais: {0, 2, 4, 6, ...}.
8 De tal forma que por vezes se escreve mesmo apenas relação, deixando implícito que se está a falar de uma relação binária.
De qualquer modo, procuraremos ser sempre claros a esse respeito.
9 Outra notação que se usa às vezes para exprimir que "x está em relação com y por R" é: x 
R → y.
x
No contexto da lógica usa-se também, com o mesmo fim, a notação R :
(que também se lê: "y sai de x por R" ).
y
66
b) Chama-se contradomínio (ou imagem) de R ao conjunto dos y para os quais existe (pelo menos) um x
tal que xRy. Designando o contradomínio de R por cod(R), tem-se:
cod(R) = {y: ∃x xRy}
Para designar o contradomínio de R também se usa codR.
c) Chama-se de inversa ou recíproca de R, e representa-se por R-1, a relação binária assim definida:
R -1 = {(y,x): (x,y) ∈ R}
Se R é uma relação binária entre A e B, então R-1 é uma relação binária entre B e A.
∇
A relação R-1 obtém-se trocando as coordenadas de cada par (x,y) ∈ R (tem-se yR-1x ⇔ xRy). Por
exemplo, a inversa da relação (em |R) "<" é a relação ">", e a inversa da relação (em |R) definida pela
condição x2+y2=1 é essa mesma relação. É imediato que dom(R-1) = cod(R) e cod(R-1) = dom(R) e, ainda,
que (R-1)-1 = R (isto para qualquer relação binária R).
Exemplo 3:
Seja R a relação binária {(1,2), (1,4), (3,5), (6,4)}. Então:
• dom(R) = {1, 3, 6}
• cod(R) = = {2, 4, 5}
• R -1 = {(2,1), (4,1), (5,3), (4,6)}
∇
Para terminar esta introdução às relações, refira-se apenas que, informalmente, podemos ver uma
relação n-ária como uma relação n-ária entre n conjuntos que não se quer, ou que é irrelevante,
especificar10.
Exercícios:
1. Considere a relação binária R = {(0 ,1) , (0 , 0) , (0 , 2)} e diga a que é igual dom(R), cod(R) e R-1.
2. Determine os domínios, os contradomínios e as relações inversas das relações:
a) de igualdade (em |N1)
b) de "divisor" (em |N1)
c) de "inclusão" (em ℘(A), sendo A um conjunto arbitrário).
3. Determine os domínios, os contradomínios e as relações inversas das relações, em |R, formadas por
todos os pares (x,y) cujas coordenadas verificam as condições seguintes:
x ≤ y , x = 3y , x2 = y , x = sen y.
4. Descreva, em extensão, a relação de "inclusão" em ℘({1, 2}).
5. Seja B um conjunto. A relação de identidade em B, que se pode denotar por id(B) (ou idB), é a relação
binária (em B) assim definida:
10 Por exemplo, e sem querer entrar aqui em pormenores, uma relação binária R pode sempre ser vista como uma relação
binária entre os conjuntos dom(R) e cod(R), uma vez que R ⊆ dom(R) x cod(R). Mas, naturalmente, a mesma relação R pode ser
considerada como uma relação binária entre dois outros conjuntos A e B (para isso, basta que dom(R) ⊆ A e cod(R) ⊆ B).
67
id(B) = {(x, x): x ∈ B}
-1
A que é igual id(B) ?
(Nota: à relação de identidade em B também se chama a diagonal de B x B.)
6. Considere a relação binária R = ∅, e diga a que é igual R-1 ?
7. Suponha que A = ∅. Quantas relações unárias em A podem ser definidas ? E quantas relações binárias
em A podem ser definidas ?
8. Considere a linguagem de programação Mathematica. Como representaria nessa linguagem uma relação
n-ária, finita (i.e. constituída por um número finito de n-tuplos) ?
9. Considere a linguagem de programação Mathematica. Construa um programa que, recebendo (a
representação de) uma relação binária, retorna:
a) O seu domínio.
b) O seu contradomínio.
c) A sua relação inversa.
Ilustre os programas (funções) construídos, aplicando-os a várias relações binárias.
∇
Secção 2: Relações de equivalência e conjunto quociente.
De entre as relações binárias têm particular interesse as relações binárias num conjunto. Seguem-se
algumas propriedades importantes que tais relações podem (ou não) possuir.
Definição 1:
Seja R uma relação binária num conjunto A (isto é, R ⊆ A2). Então, diz-se que:
a) R é reflexiva sse ∀x∈A xRx
(i.e. sse ∀ x(x∈A ⇒ xRx) )
b) R é simétrica sse ∀x,y∈A(xRy ⇒ yRx)
(i.e. sse ∀ x,y(x,y∈A ∧ xRy ⇒ yRx) )
c) R é transitiva sse ∀x,y,z∈A(xRy ∧ yRz ⇒ xRz)
d) R é uma relação de equivalência (em A) sse R é reflexiva, simétrica e transitiva11.
∇
Exemplo 1:
a) São relações de equivalência: 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 um caso particular
do paralelismo), a relação de "semelhança" (entre triângulos, por exemplo), a relação "ter a mesma
idade que" (no conjunto das pessoas), etc.
b) Não são relações de equivalência: a relação de "perpendicularidade" entre rectas (não é reflexiva, nem
transitiva), a relação de "divisor" nos números inteiros positivos (não é simétrica), a relação de
11 É imediato que se R é uma relação de equivalência em A, então (como R tem de ser reflexiva, tem-se) R ≠ ∅, excepto no
caso pouco interessante (do ponto de vista prático) em que A = ∅ (nesse caso, a única relação binária em A é a relação vazia,
que será então uma relação de equivalência).
68
"contido" (definida no conjunto das partes de um conjunto não vazio), a relação "maior" (p.ex. nos
naturais), etc.
c) A relação R = {(a,a), (a,b), (b,a), (b,b)} não é uma relação de equivalência no conjunto A = {a, b, c}
(das letras “a”, “b” e “c”), uma vez que c não está em relação consigo próprio por R (pelo que R não é
reflexiva).
d) A relação R = {(a,a), (a,b), (b,a), (b,b), (c,c)} é uma relação de equivalência no conjunto A = {a, b, c}.
∇
Fixada uma relação de equivalência R num conjunto A, diz-se que dois elementos x e y de A são
equivalentes (segundo R) sse xRy.
As relações de equivalência num conjunto não vazio desempenham um papel importante em
matemática. Em particular, elas permitem "partir" tal conjunto em classes. Porém, antes de discutirmos
como tal se processa, analisemos primeiro o conceito geral de partição de um conjunto.
Definição 2:
Seja A um conjunto não vazio12. Uma partição de A é um conjunto B, formado por subconjuntos de A,
que satisfaz as seguintes condições:
a) todo o elemento de B é não vazio (i.e. ∀S∈B S≠ ∅ )
b) os elementos de B são disjuntos dois a dois (i.e. ∀S1,S2∈B(S1≠ S2 ⇒ S1∩S2=∅) )
c) a união da colecção B é igual a A (i.e. ∪B =
U
S = A)
S ∈B
∇
Aos elementos de uma partição B de um conjunto A chama-se, por vezes, de células (ou classes de
partição). Por c) e b) cada elemento de A pertence a uma e uma só célula; também por c), em cada célula
só podem estar elementos de A; finalmente, por a), não existem células vazias.
A seguir representa-se graficamente uma possível partição do conjunto {a, b, c, d, e}: as ovais a
tracejado representam as três células da partição em causa (i.e. a partição {{a, d}, {b}, {c, e}})
a•
b•
d•
c•
e•
Existem, em geral, muitas maneiras de partir um conjunto A, não vazio. Por exemplo, dado um
qualquer subconjunto próprio de A, não vazio, X, então {X, A-X} constitui uma partição de A. Igualmente
12 A definição de partição de A, a seguir, pode-se estender ao caso em que A é o conjunto vazio. Nesse caso, a única partição
possível de A é B = ∅.
69
constitui uma partição de A o conjunto {{x}: x ∈ A}. Mas, como é natural, normalmente quando
"partimos" um conjunto A, estamos interessados não numa qualquer partição, mas sim em partições que
traduzam alguma propriedade relevante13, i.e. em que os elementos que se encontram em cada célula se
relacionam de alguma maneira ("interessante"). Ora, as propriedades que nos permitem efectuar partições
são aquelas que definem relações de equivalência.
De facto, as relações de equivalência desempenham um papel fundamental no contexto das partições de
um conjunto:
• não só a qualquer partição de A podemos associar uma relação de equivalência em A (ver exercício 2);
• como qualquer relação de equivalência em A induz uma partição de A, como se mostra a seguir.
Definição 3:
Seja R uma relação de equivalência em A e seja c um qualquer elemento de A. A classe de equivalência de
c (segundo R, ou módulo R), que se designa usualmente por [c]R (ou simplesmente por [c], se a relação R
em causa for evidente pelo contexto), é o conjunto de todos os elementos de A que são equivalentes a c
(segundo R), isto é:
[c]R = {x∈A: xRc}
(como R é uma relação binária em A, pode escrever-se simplesmente, [c]R={x: xRc})
∇
Ao elemento c (de A) usado na notação [c]R
para designar a classe {x(∈A): xRc} chama-se de
representante dessa classe. Como decorre do teorema 1-b) a seguir, qualquer elemento da classe pode ser
escolhido para seu representante (no sentido de que se a∈[c]R, então [a]R=[c]R).
Por outro lado, como uma relação de equivalência é necessariamente simétrica, é irrelevante se
definimos [c]R como {x∈A: xRc} (como fizemos), ou se definimos [c]R como {x∈A: cRx}.
Exemplo 2:
a) 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 da recta dada.
b) Para a relação de igualdade num conjunto X, qualquer que seja o elemento c de X tem-se que [c] = {c}.
c) Para a relação R = {(a,a), (a,b), (b,a), (b,b), (c,c)} em A = {a, b, c} (com a, b e c três elementos
distintos), tem-se: [a] = [b] = {a,b} e [c]={c}.
∇
Teorema 1:
Seja R uma relação de equivalência num conjunto A, e sejam a e b elementos quaisquer de A. Tem-se:
13 Por exemplo, a mobília de uma casa (ou apartamento) pode ser agrupada pelas divisões em que se encontra: tal
corresponderá a uma partição do conjunto de toda a mobília da casa. Os alunos ordinários (por oposição a alunos
extraordinários) da universidade podem ser agrupados pelos cursos que frequentam: tal corresponderá a uma partição do
conjunto de todos esses alunos.
70
a) a∈[a]
b) aRb ⇔ [a] = [b]
c) a R/ b ⇔ [a] ∩ [b] = ∅
Demonstração:
a)
Decorre de R ser reflexiva.
b-1) Demonstremos que aRb ⇒ [a] = [b]:
Suponha-se que aRb e provemos que [a] ⊆ [b] (a demonstração de que [b] ⊆ [a] é semelhante, embora
necessite de usar ainda a simetria de R, e é deixada como exercício):
Seja x∈[a] qualquer. Então (por definição de [a]) xRa. Logo, como R é transitiva, tem-se xRb, o
que implica (por definição de [b]) que x∈[b] (c.q.d.)
b-2) Demonstremos o recíproco de b-1), i.e. que [a] = [b] ⇒ aRb:
Suponha-se que [a] = [b].
Queremos provar que aRb, i.e. que a∈[b] (recordar definição de [b]).
Ora, como (por hipótese) [a] = [b], ficará provado que a∈[b], se provarmos que a∈[a]. Mas isso já foi
demonstrado (alínea a) deste teorema).
c-1) Demonstremos que a R/ b ⇒ [a] ∩ [b] = ∅:
Suponha-se, por absurdo, que a R/ b e [a]∩[b]≠∅, e vejamos (com algum pormenor) que tal nos
conduz a uma contradição.
Como [a]∩[b]≠∅, tem-se que existe c∈[a]∩[b]. Mas (qualquer que seja c):
c ∈ [a]∩[b]
⇓
c ∈ [a] ∧ c ∈ [b]
⇓ (por definição de [a] e de [b])
cRa ∧ cRb
⇓ (R é simétrica)
aRc ∧ cRb
⇓ (R é transitiva)
aRb
Logo, como existe c tal que c∈[a]∩[b] e como (qualquer que seja c) c∈[a]∩[b] ⇒ aRb, conclui-se
que aRb. Mas, por hipótese, a R/ b, obtendo-se, portanto, uma contradição (como pretendíamos).
c-2) Reciprocamente, suponha-se que [a] ∩ [b] = ∅ e provemos que a R/ b.
Ora, pela alínea a), a∈[a]. Logo (como, por hipótese, [a] ∩ [b] = ∅, conclui-se que) a∉[b]. Mas (por
definição de [b]) tal significa que a R/ b (c.q.d.).
∇
Definição 4:
Seja R uma relação de equivalência em A.
Chama-se conjunto quociente de A (segundo R, ou módulo R) ao conjunto formado pelas classes de
equivalência (segundo R) de todos os elementos de A, conjunto que se designa por A/R.
71
Isto é14:
A/R = [x]R: x∈A}
(ou, deixando a relação R implícita na descrição das classes, A/R = {[x]: x∈A} )
∇
Seja R uma relação de equivalência num conjunto A, não vazio. Por a) do teorema 1, nenhuma classe
de equivalência (de um elemento de A) é vazia. Pela mesma alínea do teorema 1, todo o elemento c de A
pertence a alguma classe de equivalência (nomeadamente, à classe [c]); assim, como, por definição das
classes de equivalência (segundo R), também se tem que estas são formadas só por elementos de A,
conclui-se que a união de todas as classes é o próprio conjunto A. Finalmente, por b) e c) do teorema 1,
quaisquer duas classes distintas são disjuntas. Tem-se, portanto:
Teorema 2 (corolário do teorema 1):
Seja R uma relação de equivalência num conjunto A, não vazio. Então A/R constitui uma partição de A (a
partição de A induzida por R).
∇
Exemplo 3:
a) Sendo R a relação {(a,a), (a,b), (b,a), (b,b), (c,c)} em A = {a, b, c} (com a, b e c três elementos
distintos), tem-se A/R = {[a], [c]} = {{a,b}, {c}}.
b) No conjunto dos naturais |N0, a relação R definida por
m R n sse m é congruente com n modulo 6
é uma relação de equivalência.
(Diz-se que m é congruente com n modulo 6 (o que se pode denotar escrevendo "m ≡ n mod 6") se m-n
é múltiplo inteiro de 6, isto é, simbolicamente, sse ∃k∈Zm-n=6k. Dito de outra forma, m é congruente
com n modulo 6 sse m e n têm o mesmo resto na divisão inteira por 6.)
Cada classe de equivalência (segundo R) é formada pelos naturais que têm o mesmo resto na divisão
(inteira) por 6 (por exemplo, [1] = {1, 7, 13, .., (6k+1), ...}).
Tem-se: |N0/R = {[0], [1], [2], [3], [4], [5]}.
∇
Observações (complementares)15:
1. (Construção dos inteiros a partir dos naturais:)
Suponha-se que o conjunto dos naturais |N0 é bem conhecido e vejamos o processo usualmente
adoptado para definir o conjunto Z dos inteiros, a partir desse conjunto.
Para compreendermos a construção a seguir, comece-se por recordar que o surgimento dos inteiros se
deu para "remediar" o facto de nos naturais a operação de subtracção nem sempre ser possível.
14 Se A = ∅, então A/R = ∅.
15 Adaptadas de [19].
72
De facto, a equação em x (com a,b∈|N0): a + x = b só tem solução em |N0 se for a≤b. E. como esta
limitação é indesejável, do ponto de vista algébrico, procurou-se então definir um "conjunto maior" do que
o dos naturais, onde tal operação fosse sempre possível (para quaisquer a e b nesse conjunto). Ideia:
Quando a + x = b tem solução (em |N0), esta é única (x = b-a). Isto é, a cada par (a,b), que satisfaça
a≤b, corresponde um e um só natural x que é solução de a+x=b. Mas a diferentes pares pode corresponder,
por este processo, o mesmo natural (i.e. a correspondência referida não é biunívoca): por exemplo ao par
(a,b)=(1,5) corresponde o natural 4 pela operação de subtracção (b-a), ao par (2,6) corresponde o mesmo
natural, e assim por diante. Mais geralmente, a dois pares de naturais (a,b) e (c,d), com a≤b e c≤d,
corresponde (pela operação de subtracção) o mesmo natural sse b-a=d-c, condição que pode ser expressa,
sem recorrer à operação de subtracção, como se segue: a+d = b+c.
Ou seja embora a operação de subtracção não nos permita identificar um natural com um e um só par
de naturais, ela permite-nos associar, biunivocamente, naturais e conjuntos de pares de naturais em que a
primeira coordenada é menor ou igual à segunda.
Mais precisamente, seja X = {(a,b): a,b∈|N0 ∧ a≤b} e seja R a seguinte relação entre pares de naturais:
(a , b) R (c , d) ⇔ a+d = b+c
Então R é uma relação de equivalência em X (ver exercício 5), e podemos associar, biunivocamente, as
classes de equivalência, que assim se obtêm, e os números naturais, o que permite “identificar” cada natural
com uma e uma só classe de equivalência (um natural x é identificado com uma classe [(a,b)] sse b-a=x).
O que se passará, agora, se considerarmos a relação de equivalência R, definida da mesma forma, não
em X, mas em todo o conjunto |N02 ? Além das classes de equivalência correspondentes aos números
naturais (todas formadas por pares de naturais em que a primeira coordenada é menor ou igual que a
segunda), obteremos novas classes que, intuitivamente, podemos supor corresponderem a números de novo
tipo, precisamente os números de que necessitávamos para resolver equações da forma a+x=b, quando a>b.
Agora, para dar uma definição matematicamente correcta dos objectos que constituem o novo conjunto
numérico que alcançámos (por enquanto apenas intuitivamente) e que é precisamente o conjunto dos
inteiros, o mais simples será chamar número inteiro a qualquer das classes de equivalência determinadas em
|N02 pela relação R. Uma tal definição parecerá certamente, pelo menos à primeira vista, muito abstracta e
um tanto artificial, e é claro que, na prática, ninguém pensará nunca, ao trabalhar (fazer cálculos) com
inteiros, que eles são certas "classes de equivalência de pares de naturais".
Porém, não é de cálculo que agora se trata, mas sim de fundamentar a contrução dos inteiros,
procurando obter uma definição rigorosa do conjunto Z, a partir de |N0 e utilizando exclusivamente noções
fundamentais da teoria dos conjuntos (tais como a de produto cartesiano e conjunto quociente) que, por sua
vez, tenham já sido definidas com o indispensável rigor16. Ora, para este efeito, a definição indicada é
perfeitamente satisfatória.
16 Observe-se que os naturais também podem ser representados na teoria dos conjuntos de uma forma simples. Sem entrarmos
em pormenores, uma ideia (proposta por von Neumann em 1925) consiste em representar o zero pelo conjunto vazio, e em
identificar cada um dos restantes naturais com o conjunto dos naturais precedentes, conduzindo à definição: 0 = ∅; 1 = {∅}; 2 =
{0, 1} = {∅, {∅}}; 3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}; e assim sucessivamente.
73
Sendo a e b naturais quaisquer, diremos que uma classe [(a,b)] é um inteiro que corresponde a um
número natural (o número b-a) sse for a≤b; se for a>b, então a classe [(a,b)] é um inteiro que não
corresponde já a nenhum número natural.
Na prática, cada número natural e o número inteiro correspondente - em princípio, objectos
matemáticos distintos - são mesmo "identificados", passando-se a designá-los pelo mesmo símbolo (a
classe [(0,0)] é designada pelo símbolo 0; as classes [(0,b)], com b>0, são designadas pelo símbolo b, ou
+b; as classes [(b,0)], com b>0, são designadas por -b). Feita esta identificação, poderá dizer-se que o
conjunto N0 é um subconjunto do conjunto Z.
Resta-nos indicar como se definem as operações algébricas no conjunto Z, acabado de construir. Tal
será deixado para mais tarde.
2. (Construção dos racionais a partir dos inteiros:)
Pode construir-se o conjunto
Q,
dos números racionais, a partir do conjunto
Z,
por um processo
inteiramente análogo ao que se indicou para passar de |N0 para Z.
A ideia orientadora desta nova "ampliação" é a de tornar resolúvel qualquer equação da forma a x = b,
com a≠0, isto é, no fundo, a de tornar sempre possível a divisão, com divisor diferente de zero.
Resumidamente:
Tem-se (para a e c diferentes de zero): a x = b ⇔ c x = d sse (
Define-se, assim, no conjunto (Z -{0}) x
Z,
b d
=
sse) a d = b c.
a c
a seguir designado abreviadamente por W, a relação de
equivalência:
€
(a , b) S (c , d) ⇔ a d = b c
e define-se o conjunto Q como sendo o conjunto quociente W/S.
∇
Exercícios:
1. Sejam a, b e c objectos distintos. Construa todas as possíveis partições de {a, b, c}.
2. Seja A um conjunto não vazio e seja B uma partição de A,
Demontre que a relação binária R, em A, assim definida:
x R y sse ∃ S∈B (x ∈ S ∧ y ∈ S)
é uma relação de equivalência (a relação de equivalência induzida por B em A).
3. Sejam a, b e c objectos distintos. Considere a relação de equivalência em B = {a, b, c} assim definida:
R = {(a,a), (a,b), (b,a), (b,b), (a,c), (c,a), (b,c) (c,b), (c,c)}
A que é igual B/R ?
4. Sejam a, b, c e d objectos distintos. Considere a relação de equivalência em A = {a, b, c, d} assim
definida:
R = {(a,a), (a,b), (b,a), (b,b), (c,d), (d,c), (c,c), (d,d)}
A que é igual A/R ?
5. Considere a relação R assim definida:
74
(a,b) R (c,d) ⇔ a+d = b+c.
Verifique que se trata de uma relação de equivalência em qualquer conjunto de pares de naturais (e,
portanto, também em |N02).
6. Suponha que R é uma relação de equivalência num conjunto X. A que é igual dom(R) ? E cod(R) ?
7. Considere o conjunto X = {1, 2, 3, 4} e a relação S, em X2, definida por:
(a , b) S (c , d) ⇔ a d = b c
a) Demonstre que S é uma relação de equivalência.
b) Diga a que é igual [(2,1)].
c) Diga a que é igual X2/S.
8. Seja R uma relação num conjunto X e S = R∪R-1. Demonstre que:
a) S é simétrica;
b) Se R for reflexiva, então S também o é;
c) O facto de R ser transitiva, não garante que S também o seja.
9. Demonstre que a intersecção de duas relações de equivalência num mesmo conjunto X ainda é uma
relação de equivalência em X.
10. Considere a linguagem de programação Mathematica e considere (neste exercício) relações de
equivalência num conjunto finito de números. (Suponha ainda que tais relações de equivalência são
representadas "extensivamente", através da descrição de todos os pares que as compõem).
Construa um programa (nessa linguagem) que:
a) Recebendo uma relação de equivalência num certo conjunto e um elemento x desse conjunto,
retorna [x] (i.e. a classe de equivalência desse elemento).
b) Recebendo uma relação de equivalência num certo conjunto, retorna o respectivo conjunto
quociente.
11. Sendo R uma relação binária entre A e B e S uma relação binária entre B e C, pode definir-se a
composição destas relações como se segue:
S o R = {(a, c): ∃b∈B ((a,b)∈R ∧ (b,c)∈S)}
(Nota: Quando falamos em composição de relações, as notações podem divergir de autor para autor:
há também quem escreva antes RoS para denotar o conjunto anterior17. Para o que se segue, é
irrelevante se denotamos a composição anterior por SoR ou por RoS.)
À custa da operação anterior podem definir-se algumas noções úteis, como as seguintes:
Seja R uma relação binária num conjuto A. Então, define-se
• R 0 = id(A) = {(x,x): x ∈ A}
(Nota: R0 denota o elemento neutro para a composição; esta definição não coincide com a definição
de potência zero de um conjunto, dada na definição 4-b) da secção 5 do último capítulo.)
• R1 = R
17 No entanto, se estivermos a encarar as relações R e S como funções (quando isso é possível), então a notação standard para
denotar o conjunto acima é SoR: ver próximo capítulo.
75
• e, qualquer que seja n≥0, Rn+1 = Rn o R (informalmente, Rn = R o ... o R, n vezes)
e chama-se
• o fecho reflexivo de R à relação (binária em A) dada por R ∪ R0
• o fecho simétrico de R à relação dada por R ∪ R-1
• o fecho transitivo de R à relação dada por R+ =
U Rn
n≥1
• o fecho reflexivo e transitivo de R à relação dada por R* =
€
U
Rn
n≥0
Exemplos: Se A = {1,2,3,4} e R={(1,2), (2,3), (4,1)}, então
€
R 0 = {(1,1), (2,2), (3,3), (4,4)};
R 1 = R = {(1,2), (2,3), (4,1)};
R 2 = R1 o R = {(1,3), (4,2)};
R 3 = R2 o R = {(4,3)};
R 4 = R3 o R = ∅; R5 = R4 o R = ∅; ... ;
R + = {(1,2), (2,3), (4,1), (1,3), (4,2), (4,3)}.
Sendo R uma relação binária num conjuto A,:
a) Prove que o fecho reflexivo (respectivamente, simétrico, transitivo) de R é uma relação reflexiva
(resp. simétrica e transitiva).
b) Prove que (R ∪ R-1)* é uma relação de equivalência em A.
c) Mostre que R* ∪ (R-1)* pode não ser uma relação de equivalência em A.
12P*. Considere a linguagem de programação Mathematica e construa um programa (nessa linguagem) que,
recebendo uma relação binária R num conjunto finito A, calcula o fecho transitivo de R.
(Sugestão: veja p.ex. a secção 6.3.2 de [8], onde esse programa é construído e utilizado para determinar
se existe, ou não, algum caminho entre dois vértices num grafo, importante problema prático de que
falaremos mais à frente. Refira-se contudo, a propósito, que existem outras maneiras mais simples e
usuais de responder a tal questão sobre grafos, como aliás também se mostra nesse livro.)
∇
Secção 3: Relações de ordem.
Outra classe importante de relações binárias, num conjunto A, são as chamadas relações de ordem18.
Saliente-se que os alunos já estão habituados a lidar com as relações de ordem usuais (≤ e <) nos
conjuntos dos números (naturais, inteiros, racionais e reais). Pode até dizer-se que a maioria das noções
introduzidas nesta secção já são mesmo conhecidas dos alunos, que no Secundário as aprenderam, mas
definindo-as directamente para o caso particular da ordenação usual dos reais. Parte do objectivo desta
secção reside em abstrair-nos desse caso particular e em definir estes conceitos para ordens genéricas.
18 Relações que têm grande aplicação em certas áreas da Ciência da Computação.
76
Definição 1:
Seja R uma relação binária num conjunto A. Então, diz-se que:
a) Dois elementos x e y, de A, são comparáveis por meio de R sse xRy ∨ yRx;
dois elementos x e y, de A, são incomparáveis por meio de R sse não são comparáveis.
b) R é irreflexiva sse ∀x∈A x R/ x
i.e., de forma equivalente, R é irreflexiva sse ¬∃x∈A xRx
c) R é anti-simétrica sse ∀x,y∈A(xRy ∧ yRx ⇒ x=y)
i.e., de forma equivalente, R é anti-simétrica sse ¬∃x,y∈A(xRy ∧ yRx ∧ x≠y)
d) R é uma relação de ordem parcial, em sentido lato, sse R é reflexiva, anti-simétrica e transitiva.
e) R é uma relação de ordem parcial, em sentido estrito, sse R é irreflexiva e transitiva.
∇
Exemplo 1:
a) Considere-se a relação binária R = {(1,2), (2,2), (2,3), (3,4), (4,5)} no conjunto A = {1, 2, 3, 4, 5}. A
relação R não é irreflexiva, pois (2,2)∈R (i.e. tem-se 2R2). Será que R é reflexiva ?
b) Considere-se a relação binária R = {(1,2), (2,1), (1,2), (4,5)} no conjunto A = {1, 2, 3, 4, 5}. A
relação R é irreflexiva. A relação R não é anti-simétrica (pois 1R2 ∧ 2R1 ∧ 1≠2).
c) Considere-se a relação binária R = {(1,1), (1,2), (2,3), (1,3)} no conjunto A = {1, 2, 3}. A relação R é
anti-simétrica e transitiva. A relação R não é irreflexiva (pois 1R1).
d) Considere-se a relação binária R = {(1,2), (2,3)} no conjunto A = {1, 2, 3}. A relação R é antisimétrica e irreflexiva. A relação R não é transitiva (pois 1R2 ∧ 2R1 ∧ 1 R/ 1).
e) Considere-se a relação binária R = {(1,2), (2,3), (1,3)} no conjunto A = {1, 2, 3}. A relação R é antisimétrica e transitiva. A relação R não é reflexiva (pois p.ex. 1 R/ 1).
f) Considere-se a relação binária R = {(1,2), (2,1), (1,1), (2,2), (3,3)} no conjunto A = {1, 2, 3}. A
relação R é reflexiva e transitiva. A relação R não é anti-simétrica (pois 1R2 ∧ 2R1 ∧ 1≠2).
g) Considere-se a relação binária R = { (1,1), (2,2), (3,3), (1,2), (2,3)} no conjunto A = {1, 2, 3}. A
relação R é reflexiva e anti-simétrica. A relação R não é transitiva (pois 1R2 ∧ 2R3 ∧ 1 R/ 3).
∇
Em vez de dizer que R é uma relação de ordem parcial em sentido lato, também se diz, mais
abreviadamente, que R é uma ordem parcial em sentido lato, ou que R é uma ordem parcial lata, ou
mesmo, apenas, que R é uma ordem parcial. Analogamente, em vez de dizer que R é uma relação de ordem
parcial em sentido estrito, também se diz que R é uma ordem parcial em sentido estrito, ou que R é uma
ordem parcial estrita19.
A relação ≤ (por exemplo no conjunto dos reais) é um exemplo típico de uma ordem parcial (lata), e a
relação < um exemplo típico de uma ordem parcial estrita.
19 Quando se fala numa ordem parcial, sem dizer se é estrita ou lata, assume-se em geral (como faremos aqui) que se trata de
uma ordem parcial em sentido lato. No entanto, nem todos os autores assumem essa convenção.
77
Mas muitos outros exemplos existem, seja de natureza matemática, seja de outra natureza: a relação de
inclusão ⊆, no conjunto das partes de um conjunto A, é uma ordem parcial; a relação de "descendente", no
conjunto dos seres humanos, é uma ordem parcial, em sentido estrito; etc. Podemos mesmo conceber
outro tipo de ordens parciais associadas a "conceitos mais difusos". Por exemplo, podemos querer ordenar
portais pela quantidade de informação que disponibilizam (naturalmente nem todos os portais serão
comparáveis por essa hipotética relação de ordem estrita "disponibilizar menos informação que" ).
As relações de ordem parcial podem ser representadas graficamente de maneira muito sugestiva: os
elementos são representados por pontos, e os elementos distintos que estão em relação são ligados por
segmentos de recta, de modo a que xRy sse o ponto que representa x está por baixo e ligado (através de um
ou mais segmentos de recta) ao ponto que representa y. Na figura da direita representa-se a ordem parcial ⊆
no conjunto das partes de A = {0,1,2}.
A
{0,1}
{1,2}
{0,2}
{1}
{0}
{2}
{}
Como é claro dos exemplos acima, numa ordem parcial alguns elementos podem ser incomparáveis
(daí, aliás, o termo "parcial"): tal acontece por exemplo com os elementos {1} e {2}, na ordem da direita.
Quando todos os elementos distintos são comparáveis, dois a dois (como, por exemplo, na ordem ≤ nos
reais), diz-se que estamos em presença de uma ordem total:
Definição 2:
Seja R uma relação binária num conjunto A. Então, diz-se que:
a) R satisfaz a propriedade dicotómica sse quaisquer dois elementos são comparáveis por meio de R, isto
é, sse ∀ x,y∈A(xRy ∨ yRx).
b) R satisfaz a propriedade tricotómica20 sse quaisquer dois elementos distintos são comparáveis por meio
de R, isto é, sse ∀x,y∈A(x=y ∨ xRy ∨ yRx).
(Note-se que ∀x,y∈A(x=y ∨ xRy ∨ yRx) é equivalente a ∀x,y∈A(x≠y ⇒ xRy ∨ yRx).)
c) R é uma ordem total ou uma ordem linear (em sentido lato ou estrito) sse R é uma ordem parcial (em
sentido lato ou estrito) que satisfaz a propriedade tricotómica.
∇
Uma ordem parcial, em sentido lato, satisfaz a propriedade tricotómica sse satisfaz a propriedade
dicotómica. Logo, pode também dizer-se, de forma equivalente (e como é mais usual), que uma ordem
total, em sentido lato, é uma ordem parcial em sentido lato que satisfaz a propriedade dicotómica.
20 Também se diz, nesse caso, que R é conexa.
78
Por outro lado, tal como em relação às ordens parciais, quando se fala numa ordem total, sem dizer se é
estrita ou lata, assume-se em geral (e assumiremos aqui) que se trata de uma ordem total em sentido
lato21.
A uma ordem total R (estrita ou lata) também se chama de ordem linear (estrita ou lata) por ela se
poder representar através de uma linha recta22 (tendo-se que, para dois elementos distintos x e y, xRy sse o
ponto que representa x está à esquerda do ponto que representa y). Veja-se por exemplo a representação da
relação ≤ nos inteiros:
-2
-1
0
1
2
3
Exemplo 2:
a) A relação ≤ é uma ordem total nos naturais (assim como nos inteiros, nos racionais ou nos reais).
b) A relação ≥ é também uma ordem total nos naturais (e nos inteiros, nos racionais ou nos reais).
c) A relação determinada, no conjunto de todas as palavras da língua portuguesa, pela condição "x precede
alfabeticamente y" é uma ordem total, em sentido estrito.
d) A relação de inclusão ⊆ no conjunto das partes de um conjunto A é uma ordem parcial que não é total
(só será total se A tiver no máximo 1 elemento).
e) A relação de "descendente", no conjunto dos seres humanos, é uma ordem parcial, em sentido estrito,
que não é total.
f) A relação, em |N1, "x divide y", ou "x é divisor de y" (que se verifica sse ∃k∈|N1 y = k x, e que se denota
muitas vezes escrevendo x|y 23), é uma ordem parcial (que também não é total).
g) Considere-se, agora, a relação binária R = {(1,2), (2,3), (3,4), (4,5)} no conjunto A = {1, 2, 3, 4, 5}.
Embora intuitivamente R ordene linearmente os elementos de A, não se trata de uma ordem linear
estrita em A. De facto, não só não é total (p.ex. 1 e 3 não são comparáveis por meio de R), como não
é mesmo uma ordem parcial estrita em A, pois não é transitiva.
No entanto, se considerarmos o fecho transitivo de R, dado por (ver exercício 11 da última secção)
R + = {(1,2), (2,3), (3,4), (4,5), (1,3), (2,4), (3,5), (1,4), (2,5), (1,5)}
já estaremos em presença de ordem linear estrita em A = {1, 2, 3, 4, 5}.
h) A relação R = {(1,2), (2,3), (1,3), (4,5)} é uma ordem parcial estrita no conjunto A = {1, 2, 3, 4, 5},
que não é total (pois p.ex. 1 e 4 não são comparáveis por meio de R).
i) A relação R = {(1,1), (2,2), (3,3), (4,4)} é uma ordem parcial (lata) no conjunto A = {1, 2, 3, 4}, que
não é total (pois p.ex. 1 e 2 não são comparáveis por meio de R).
21 Por outro lado, alguns autores quando falam em ordens (ou relações de ordem), sem explicitar se são parciais ou totais,
referem-se a ordens totais. Aqui explicitaremos sempre se se trata de uma ordem parcial ou de uma ordem total. (Naturalmente,
como decorre da definição, uma ordem total é sempre uma ordem parcial).
22 Um aspecto desse fenómeno é não haver "ciclos" (como, por exemplo: x R x ∧ x R x ∧ x R x ∧ x R x ).
1
2
2
3
3
4
4
1
23 Não se deve confundir x|y com x/y. A expressão x|y não é um número (não representa o quociente de x por y),
correspondendo sim a afirmar que (o valor de) x divide (o valor de) y. Por exemplo, tem-se 3|6, mas não se tem que 3|4.
79
j) Analogamente, a relação R = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,3), (1,3)} é uma ordem parcial (lata)
no conjunto A = {1, 2, 3, 4}, que não é total (pois p.ex. 1 e 4 não são comparáveis por meio de R).
k) A relação R = {(1,1), (1,2), (2,2), (2,3), (3,3), (3,4), (4,4)} já é uma ordem linear (lata) no conjunto A
= {1, 2, 3, 4}.
∇
Notações:
1. Usa-se frequentemente o símbolo
p A (ou p A) para denotar (genericamente24) que se está a considerar
uma relação que é uma ordem parcial no conjunto A. Quando o conjunto A, no qual se está a considerar
uma ordem parcial, é evidente pelo contexto, pode escrever-se simplesmente
p (em vez de p A).
Por vezes usa-se mesmo o símbolo ≤ com esse fim; no entanto, tal notação poderá sugerir que
estamos a trabalhar com a usual relação "menor ou igual" em conjuntos de números, pelo que a evitamos
(note-se, por exemplo, que a relação ≥ nos naturais também é uma ordem parcial).
O símbolo
p pode ler-se "precede ou é igual a" (ou mesmo "é menor ou igual que").
Dada uma ordem parcial
p A, designa-se por p A a relação binária, em A, assim definida:
pA y ⇔ x pA y ∧ x ≠ y
x
Pode verificar-se que
p A é uma ordem em sentido estrito, e que p A é uma ordem total sse p A o for (o que
se deixa como exercício).
Diz-se que
p A é a relação de ordem estrita associada a, ou induzida por, p A.
Igualmente se introduzem as habituais convenções de notação seguintes (onde se omite a referência a
A, assumindo-se este conjunto implícito):
fy ⇔ yp x
x f y ⇔ x f y ∨ x=y
x p y p z ⇔ xp y ∧ yp z
x p y p z ⇔ xp y ∧ yp z
x
etc.
E, quando
p
é uma ordem total em A, também se define, por vezes, as noções de intervalo25, aberto,
fechado e semi-fechado, de extremos a e b (pertencentes a A), como se segue:
[a, b] = {x∈A: a
p
[a, b[ = {x∈A: a
p x p b}
]a, b] = {x∈A: a
p x p b}
p b}
]a, b[ = {x∈A: a p x p b}
x
24 Quando nos queremos referir a específicas ordens parciais, como por exemplo a relação de inclusão nas partes de um
conjunto, então usamos naturamente o seu símbolo próprio: ⊆.
25 A noção de intervalo também se pode definir (como a seguir) para ordens parciais
p , que não sejam totais. No entanto, os
intervalos têm mais interesse (e são usualmente considerados só) no contexto de ordens totais.
80
2. Analogamente, pode-se partir de uma ordem parcial em sentido estrito e definir a partir dela as outras
ordens associadas.
p A (ou p A) - que se pode ler "precede" (ou "é menor que") - para denotar que se está
a considerar uma ordem parcial em sentido estrito, no conjunto A (ou simplesmente p , se A for evidente
pelo contexto), designa-se por p A a relação binária, em A, assim definida:
Usando o símbolo
p A y ⇔ x pA y ∨ x = y
que se diz a relação de ordem lata associada a (ou induzida por) p A.
x
As outras convenções notacionais definem-se, então, tal como em 1 anterior.
∇
Definição 2:
a) A um par ordenado, ƒ = (A, R), constituído por um conjunto A e uma relação binária R em A
chamamos de estrutura 26. (Em vez de se escrever (A,R) também se escreve (A; R).)
b) Se R for uma ordem parcial (respectivamente total) em A, então diz-se que (A, R) é uma estrutura
parcialmente (resp. totalmente) ordenada. Por abuso de linguagem, em tal caso diz-se mesmo que (A,R)
é um conjunto parcialmente (totalmente) ordenado
27.
O termo cpo é uma abreviatura de conjunto
parcialmente ordenado (em inglês usa-se o termo poset que é uma abreviatura de "partially ordered set").
∇
Associado a um cpo definem-se algumas noções importantes, como a seguir. (Saliente-se que nestas
definições é irrelevante se consideramos que o conjunto A está "equipado", à partida, com uma ordem
parcial lata
p , e definimos p como a ordem parcial estrita que lhe está associada, ou se consideramos que
A está equipado, à partida, com uma ordem parcial estrita p , e definimos
p como a ordem parcial lata que
lhe está associada.)
Definição 3:
Seja (A ,
p ) um cpo e seja X um subconjunto qualquer de A.
a) Diz-se que um elemento c de A é um minorante de X (com respeito à ordem parcial
p em
consideração) sse
∀x∈X c p x
Analogamente, diz-se que um elemento c de A é um majorante de X sse
∀x∈X x p c
b) Diz-se que X é minorado, ou limitado inferiormente (em A), sse X tiver pelo menos um minorante em
A (i.e. sse ∃c∈A∀x∈X c p x)
26 Ou, mais precisamente, estrutura relacional (ou sistema relacional). Voltaremos a abordar o conceito de estrutura à frente.
27 Quando a ordem parcial (total) R em questão está subentendida, o abuso pode ir mais longe, chamando-se ao próprio
conjunto A de conjunto parcialmente (totalmente) ordenado. Por outro lado, um conjunto totalmente ordenado também se designa
por conjunto linearmente ordenado.
81
Diz-se que X é majorado, ou limitado superiormente (em A) sse X tiver pelo menos um majorante em
A (i.e. sse ∃c∈A∀x∈X x p c)
E diz-se que X é limitado (em A) sse X for minorado e majorado (i.e. sse ∃c,d∈A∀x∈X c p x p d)
c) Diz-se que um elemento c (de A) é um elemento minimal de X sse
c∈X ∧ ∀x∈X (x p c ⇒ c=x)
condição que é equivalente (demonstre!) a
c∈X ∧ ¬ ∃x∈X x
pc
Analogamente, diz-se que um elemento c (de A) é um elemento maximal de X sse
c∈X ∧ ∀x∈X (c p x ⇒ c=x)
condição que é equivalente a:
c∈X ∧ ¬ ∃x∈X x
fc
d) Diz-se que um elemento c (de A) é um mínimo de X sse
c∈X ∧ ∀x∈X c p x
e diz-se que X admite mínimo sse existe um elemento c que é um mínimo de X.
Analogamente, diz-se que um elemento c (de A) é um máximo de X sse
c∈X ∧ ∀x∈X x p c
e diz-se que X admite máximo sse existe um elemento c que é um máximo de X.
e) Diz-se que um elemento c de A é um ínfimo de X sse c é um minorante de X e qualquer outro
minorante de X precede c de acordo com a ordem
p:
∀x∈X c p x ∧ ∀ d∈A(∀x∈X d p x ⇒ d p c)
e diz-se que X admite ínfimo (em A) sse existe um elemento c de A que é um ínfimo de X.
Analogamente, diz-se que um elemento c de A é um supremo de X sse c é um majorante de X que
precede qualquer outro majorante de X:
∀x∈X x p c ∧ ∀ d∈A(∀x∈X x p d ⇒ c p d)
e diz-se que X admite supremo (em A) sse existe um elemento c de A que é um supremo de X.
∇
Em seguida ilustra-se as noções acabadas de definir, e fazem-se alguns comentários sobre o seu
significado e sobre as relações existentes entre as diferentes noções.
Seja (A ,
p ) um cpo e seja X um subconjunto de A. Então:
Um minorante de X é um elemento de A que é "menor ou igual" (de acordo com a ordem
p
subjacente) que todos os elementos de X.
Exemplo 3:
•
considerando a usual ordem ≤ nos reais (i.e. (A, p ) = (|R,≤)), então qualquer real não positivo (i.e.
qualquer real negativo ou nulo) é um minorante do conjunto X = ]0,+∞[;
•
considerando a mesma ordem, qualquer real não positivo é (também) um minorante de [0,+∞[;
82
•
considerando a ordem ⊆ no conjunto A = ℘{1,2,3} (das partes de {1,2,3}}, então o conjunto vazio é
um minorante de qualquer subconjunto de A (repare-se que os subconjuntos de A são conjuntos
formados por subconjuntos de {1,2,3});
•
considerando a (mesma) ordem ⊆ no conjunto A = ℘{1,2,3}, então o (sub)conjunto (de A)
X={{2,3},{1,2,3}} tem como minorantes ∅, {2}, {3} e {2,3}, e o conjunto X={{1,2},{2,3},{1,2,3}}
tem como minorantes ∅ e {2}.
∇
Um elemento c (de A) é um elemento minimal de X sse c∈X e não existem elementos em X menores
do que c.
Exemplo 4:
•
considerando a usual ordem ≤ nos reais, então 0 é um elemento minimal do conjunto X = [0,+∞[, e os
conjuntos X = ]0,+∞[ e X = ]-∞,0] não possuem elementos minimais;
•
considerando a usual ordem ≤ nos naturais, que podemos descrever graficamente como se segue:
0
1
2
3
4
5
então 0 é um elemento minimal do conjunto dos pares, bem como de |N0 ;
•
considerando, agora, a relação inversa da anterior (que também é uma ordem parcial), isto é,
considerando o cpo (A, p ) = (|N0 , ≥) (onde ≤ designa a usual relação "maior ou igual" nos naturais),
que podemos descrever graficamente como se segue:
X
6
5
4
3
2
1
0
então 5 é um elemento minimal do conjunto X={1, 2, 3, 4, 5}, bem como do conjunto Y = {1, 3, 5},
e o conjunto dos pares não possui elementos minimais;
•
considerando a ordem ⊆ no conjunto A = ℘ {1,2,3}, então {2,3} é um elemento minimal de
X={{2,3},{1,2,3}}, e quer {1,2}, quer {2,3}, são elementos minimais de X={{1,2},{2,3},{1,2,3}}.
∇
Um mínimo de X é um elemento de X que é "menor ou igual" que todos os elementos de X. Um
subconjunto X de A pode não admitir mínimo (para uma dada ordem parcial
p em A), mas se admitir este
é único (ver exercícios à frente). Daí que quando c é um mínimo de um conjunto X se possa dizer que c é o
mínimo de X. Podemos também dizer que o mínimo de X é o menor elemento de X, no sentido de que é
um elemento de X que é menor ( p ) que todos os outros elementos de X.
O mínimo de X (quando existe) denota-se por min(X), ou minX (deixando-se implícito qual o cpo
(A, p ) onde se está a calcular tal mínimo, o qual, naturalmente, deverá ser evidente pelo contexto).
É imediato (pelas definições) que o mínimo de X (quando existe) é um minorante de X e que qualquer
minorante de X, que pertença ao próprio conjunto X, é um mínimo de X. Igualmente se pode verificar que
83
um mínimo de X é sempre um elemento minimal de X, mas o recíproco pode não se verificar (um
elemento minimal pode não ser mínimo); no entanto, se a ordem
minimal é necessariamente um mínimo
28
p for total, então um elemento
(ver exercícios à frente).
Exemplo 5:
•
considerando a usual ordem ≤ nos reais, então 0 é o mínimo do conjunto X = [0,+∞[;
•
considerando a ordem ⊆ no conjunto A=℘{1,2,3}, então {2,3} é o mínimo do conjunto X=
{{2,3},{1,2,3}}, e X={{1,2},{2,3},{1,2,3}} não tem mínimo (apesar de ter elementos minimais);
•
sendo A = {a, b} ∪ Z, ≤ a usual relação de "menor ou igual" definida nos inteiros e
em A assim definida:
p = {(a,a), (a,b), (b,b)} ∪ ≤, então o conjunto X = {a} ∪
Z
p a ordem parcial
possui um (e um
só) elemento minimal (o elemento a), mas não possui mínimo.
∇
Um ínfimo de um subconjunto X de A não é mais do que o maior dos minorantes de X (em A), i.e. é
o máximo do subconjunto de A formado por todos os minorantes de X em A.
Como o máximo de um subconjunto de (um cpo) A pode não existir, mas se existir é único, concluise imediatamente que um subconjunto X de A pode não admitir ínfimo, mas se admitir este é único. Daí
que quando c é um ínfimo de X se possa dizer que c é o ínfimo de X.
O ínfimo de X, quando existe, designa-se por inf(X), ou infX.
Como referimos acima, qualquer minorante de X, que pertença ao próprio conjunto X, é um mínimo de
X. Assim, como o ínfimo de X é um minorante de X, se o ínfimo de X (existir e) pertencer a X, então o
ínfimo de X coincide com o mínimo de X. Por outro lado, se existir o mínimo de X ele coincide
necessariamente com o seu ínfimo (ver exercícios à frente). No entanto um subconjunto X de um cpo A
pode admitir ínfimo, sem que admita mínimo (ver exemplos a seguir).
Observe-se, ainda, que como não existem minorantes de X maiores que o seu ínfimo, não é difícil
verificar (ver exercícios à frente) que:
Se
p
for uma ordem total, então
o ínfimo de X (quando existe) satisfaz a seguinte condição "qualquer elemento maior do que ele é maior
do que algum elemento de X", i.e. simbolicamente
c = inf(X) ⇒ ∀z∈A(c
p z ⇒ ∃x∈X x p z)
Exemplo 6:
•
considerando a usual ordem ≤ nos reais, então: 0 é um infímo do conjunto X = ]0,+∞[ (mas 0 não é
um mínimo de X, pois não pertence a X); 0 é um mínimo (e portanto também um ínfimo) do
conjunto [0,+∞[; e o conjunto ]-∞,0] não possui ínfimo;
28 Assim, como as ordens usuais associadas aos conjuntos de números são totais, nessas ordens não se distinguem os conceitos
de elemento minimal e de mínimo. Daí que no Secundário o conceito de elemento minimal não seja introduzido.
84
•
se considerarmos agora a ordem (inversa da anterior) ≥ nos reais (i.e. (A, p ) = (|R , ≥)), então o
conjunto X = [0,+∞[ não possui ínfimo;
•
considerando a ordem ⊆ no conjunto A = ℘{1,2,3}, então {2} é um ínfimo (mas não um mínimo) do
conjunto X={{1,2},{2,3},{1,2,3}}.
∇
Considerações análogas podem ser feitas a propósito dos conceitos "duais" dos anteriores, i.e. a
propósito dos majorantes, elementos maximais, máximo e supremo de um subconjunto de um cpo. Em
particular, refira-se que o máximo de X (quando existe) denota-se por max(X), ou maxX, e que o supremo
de X (quando existe) designa-se por sup(X), ou supX.
Seguem-se mais alguns exemplos sobre estas noções.
Exemplo 7:
Seja (A ,
p ) = (|R, ≤) (onde ≤ designa a usual relação "menor ou igual" no conjunto dos reais). Então:
a) O conjunto (X =) |N0 é um conjunto minorado (qualquer real < 0 é minorante de tal conjunto), mas não
é majorado, nem, portanto, limitado.
b) O conjunto dos racionais negativos é majorado (são majorantes todos os reais ≥0) mas não é limitado.
c) O conjunto X = {x: x2 < 4} = ]-2,2[ é limitado.
d) O conjunto [0,1[ não tem máximo, mas tem supremo (o 1).
e) Os conjuntos dos naturais, inteiros, dos racionais e dos reais não têm supremo.
f) Os conjuntos [0,5[ e |N0 têm mínimo (o 0) mas não máximo.
g) Os conjuntos {2, 3, 7} e [2, 7] têm máximo (o 7) e mínimo (o 2).
h) O conjunto X = {x: ∃n∈|N1 x = 1/n}, formado pelos inversos dos naturais positivos, tem por supremo 1
(que é também máximo, uma vez que pertence ao próprio X) e por ínfimo 0 (que não é mínimo).
∇
Para terminar esta introdução aos cpo´s, introduziremos ainda duas outras noções importantes,
começando pela noção de boa ordem.
Definição 4:
Uma ordem parcial (lata ou estrita) diz-se uma boa ordem num conjunto A sse essa ordem for uma ordem
total em A que satisfaz: "qualquer subconjunto não vazio de A possui mínimo".
∇
Como
p é uma ordem total num conjunto A sse p o for, é imediato que uma relação p é uma boa
ordem em A sse
p é uma boa ordem em A, sendo irrelevante considerar p ou p nos resultados a seguir.
Em vez de dizer que uma relação
p (ou p ) é uma boa ordem num conjunto A, também se diz que
(A, p ) (resp. (A, p )) é um conjunto bem ordenado. Quando a ordem em causa é evidente pelo contexto,
diz-se mesmo, simplesmente, que A é um conjunto bem ordenado.
Antes de vermos exemplos, observe-se que a definição de uma boa ordem pode ser "simplificada":
85
Teorema 1:
Seja (A, p ) um cpo. Então:
A é um conjunto bem ordenado
sse
qualquer subconjunto não vazio de A possui mínimo (em relação à ordem
p ).
Demonstração:
⇓: Sai imediatamente da definição de boa ordem.
⇑: Temos de provar que o facto de qualquer subconjunto não vazio de A possuir mínimo implica que
p é
uma ordem total. Mas tal é imediato, pois se x e y são dois (quaisquer) elementos de A, então um deles
será o mínimo de {x, y} e, portanto, será
p que o outro (pelo que x e y são comparáveis por p ).
∇
Exemplo 8:
a) A usual relação de ordem ≤ nos naturais é uma boa-ordem.
b) No entanto, se considerarmos o conjunto dos inteiros, então a ordem ≤ já não é uma boa-ordem neste
conjunto (p.ex., {0, -2, -4, -6, ...} é não vazio e não possui mínimo).
c) Igualmente (|R, ≤) não é bem ordenado (p.ex., ]0,5] não tem mínimo).
∇
Apesar de os exemplos anteriores mostrarem que nem toda a ordem total constitui uma boa ordem, o
princípio da boa-ordenação diz-nos que é sempre possível definir uma boa ordenação de um conjunto29:
Princípio da boa ordenação (de Zermelo) 30:
Todo o conjunto admite uma boa ordem (i.e. dado um conjunto qualquer A, é possível definir uma relação
R que constitui uma boa ordem em A).
∇
Refira-se, para terminar, uma última noção importante (e fundamental para os tópicos abordados no
capítulo 7), e que corresponde (como veremos) a um “enfraquecimento” da noção de boa-ordem.
29 Mas não nos diz que é fácil descobri-la e explicitá-la. Em muitos casos pode não ser. O princípio apenas diz que ela existe.
30 Designámos esta asserção de princípio, e não de teorema, para chamar a atenção de que a sua demonstração (que não
faremos aqui) depende da aceitação do famoso axioma da escolha (axioma que aceitaremos, tal como a maioria dos
matemáticos o faz). Mais precisamente, pode mostrar-se que este princípio é mesmo equivalente ao axioma da escolha, axioma
que pode ser formulado (recorrendo a famílias - ver próximo capítulo) como se segue: "Dada uma família (Ai) i∈I, de conjuntos
não vazios, é possível formar uma família (xi) i∈I, tal que, para cada i∈I, se tem que xi∈A i".
Um outro princípio que é equivalente ao axioma da escolha é o chamado lema de Zorn, que podemos enunciar como se
p ) é um cpo no qual tota a cadeia não vazia tem (pelo menos) um majorante em A, então A tem, pelo menos,
um elemento maximal", onde uma cadeia de um cpo (A , p ) é um (qualquer) subconjunto X de A que satisfaz a propriedade
dicotómica (i.e. em que quaisquer dois seus elementos são comparáveis por meio de p ).
segue: "Se (A ,
86
Definição 5 (Relação bem fundada):
Uma relação bem fundada num conjunto A é uma relação binária R em A tal que não existem "cadeias
descendentes infinitas" da forma (onde a0, a1, a2, ... são elementos de A não necessariamente distintos 31)
... R an R ... R a1 R a0
∇
Se R é uma relação (em A) bem fundada, então R é obrigatoriamente irreflexiva (pois, caso existisse
a∈A tal que aRa, então existiria uma cadeia descendente infinita ... R a R ... R a R a). No entanto, uma
relação bem fundada pode não ser transitiva32, como ilustra o exemplo a seguir.
Exemplo 9:
A relação R nos naturais, dada por n R k sse n = k-1, é uma relação bem fundada (e não é transitiva).
∇
Assim, uma relação bem fundada pode não ser uma ordem parcial estrita. Apesar disso, usa-se muitas
vezes o símbolo
p para se referir genericamente a uma relação bem fundada (e quando x p y costuma
dizer-se que x é um predecessor, ou um antecessor, de y). Igualmente se define:
x
e diz-se€que
p y ⇔ xp y ∨ x=y
€ fundada em A.
p é uma relação bem fundada num conjunto A sse p é uma relação bem
O próximo teorema enuncia uma caracterização alternativa da noção de relação bem fundada:
€
Teorema 2:
p uma relação binária num conjunto A. Então:
A relação p é bem fundada
Seja
sse
€
qualquer subconjunto X de A, não vazio, possui (pelo menos) um elemento minimal (em relação a
p ),
€no sentido de que33 existe algum c tal que
c∈X ∧ ¬ ∃a∈X a
pc
€
Demonstração:
⇑: Suponha-se que qualquer subconjunto X de A, não vazio, possui um elemento minimal e suponha-se,
por absurdo, que existe uma cadeia descendente infinita ...
€
31 De acordo com a terminologia da secção 5 do próximo capítulo (a )
i
€
p an p ... p a1 p a0.
€
€
i≥0 constitui uma família de elementos de A (indexada pelo
conjunto dos naturais).
32 Isto de acordo com a definição acima de relação bem fundada, que é a definição que ocorre, por exemplo, em [46]. Noutros
textos, como em [41], a noção de relação bem fundada só aparece definida no contexto de ordens parciais e, naturalmente, se
falarmos num cpo (A, p ) bem fundado, então a relação p em causa será necessariamente transitiva.
33 Definindo elemento minimal tal como na definição 3-c), mas onde este conceito só foi definido para ordens. Refira-se, a
propósito, que esta condição é equivalente quer à condição c∈X ∧ ∀a (∈ A) (a p c ⇒ a∉ X), quer a c∈ X ∧ ∀ a ∈ X (a p c ⇒ c=x).
€
87
Seja m um elemento minimal de {a0, a1, ..., an, ...} e seja k o primeiro natural tal que m = ak (cuja
existência é garantida pelo facto de m pertencer ao conjunto {a0, a1, ..., an, ...}).
Ora, se m é um elemento minimal de {a0, a1, ..., an, ...} não podem existir em {a0, a1, ..., an, ...}
elementos menores que m = ak, o que entra em contradição com o facto de ak+1
⇓: Suponha-se que a relação
p ak.
p é bem fundada e seja X um subconjunto não vazio de A e suponha-se, por
absurdo, que X não possui um elemento minimal. Então chega-se a uma contradição, como se esboça
€
a seguir:
€
Seja a0 um elemento
de X qualquer (cuja existência é garantida pelo facto de X ser não vazio).
Como X não posui elemento minimal, a0 não é um elemento minimal de X. Logo existe (pelo menos)
p a0. E, como a1 também não é um elemento minimal de X. existe
um elemento a2 em X tal que a2 p a1, e assim sucessivamente, pelo que (indutivamente) existirá uma
cadeia descendente infinita ... p an p ... p a1 p a0, o que contradiz a relação p ser bem fundada.
€
∇
€
E, usando o teorema €
anterior,
€ facilmente
€ € se estabelecem relacionamentos
€ entre as noções de boa ordem
um elemento a1 em X tal que a1
e de relação bem fundada, verificando-se, nomeadamente, que a primeira é um caso particular da segunda:
Teorema 3
34:
p uma boa ordem num conjunto A. Então p é uma relação bem fundada em A.
b) Se p é uma relação em A, que é bem fundada e total35, então p é uma boa ordem em A
a) Seja
Demonstração:
€a) Imediato, pelo teorema anterior, pois (por
€ definição de boa ordem) qualquer subconjunto X de A, não
€ vazio, possui mínimo e um mínimo é sempre um elemento
€
minimal (ver exercício à frente).
b) Seja
i)
p é uma relação em A, que é bem fundada e total. Então:
p é uma relação transitiva em A. Dem.:
Sejam x, y e z quaisquer elementos de A tais que x p y e y p z. Quer-se provar que x p z.
€
€
Como
p é total, ou x = z, ou z p x, ou x p z.
Se se verificasse o primeiro caso (x=z), então conseguia-se construir uma cadeia descendente
€
infinita:
€
€
...€x
€
€
py px py px py
p ser bem fundada. Portanto x não pode ser igual a z.
Se se verificasse o segundo caso (z p x), igualmente se construía uma cadeia descendente infinita:
€ ...€ z p€ x p€ y p€ z p x p y
Portanto não se€pode ter z p x.
€ “por exclusão de partes”, tem de ter-se x p z (c.q.d.)
Logo, (como se costuma dizer)
€ € € € €
€
34 Neste teorema estar p ou p é indiferente, uma vez que p é uma boa ordem em A sse p o é, e, como se observou atrás,
€
dizer que p é uma relação bem fundada em A é equivalente a dizer que p é uma relação bem fundada em A
35 Definindo relação total tal como na definição 2-c), mas onde este conceito foi definido só para ordens. Isto é, p é uma
relação total em A €
se quaisquer dois elementos distintos de A são comparáveis por€meio de p .
€
€
88
€
o que é impossível por
ii) Assim, como já sabemos que qualquer relação bem fundada é irreflexiva, podemos portanto concluir
p é uma ordem total estrita em A.
iii) Pelo teorema anterior, se p é uma relação em A, que é bem fundada, então qualquer subconjunto
que
não vazio de A possui um elemento minimal. Mas, numa ordem total (ver exercícios à frente) um
€
elemento minimal é mínimo. Logo, qualquer subconjunto não vazio de A possui mínimo.
Logo, por ii) e iii),
€p é uma boa ordem em A.
∇
p em X um conjunto {x∈ X: x p y} pode não ser finito):
Ao contrário do que poderá parecer à primeira vista, do facto de p ser uma relação bem fundada, ou
mesmo uma boa ordem, num conjunto X, não se pode concluir que todo o conjunto {x∈X: x p y}, com
Observação (Numa
€ boa ordem
y∈X, seja necessariamente finito.
Para o ver, considere-se a ordem
p em X= |N0x|N0, dada por:
(x1,y1)
p (x2,y2) sse x1<x2 ou (x1=x2 e y1<y2)
(a usual ordem lexicográfica em |N0x|N0: ver exercício 21)
Trata-se não só de uma relação bem fundada em X (ver exercício 30), mas mesmo de uma boa ordem (pois
é total). No entanto, os únicos conjuntos {x∈X: x
p y} que são finitos são aqueles em que y = (0,k) para
algum k∈|N0. Por exemplo:
p (1,0)} = {(0,0), (0,1), (0,2), (0,3), ...} = {(0,n): n ∈ |N0};
• {(a,b)∈X: (a,b) p (1,1)} = {(0,n): n∈|N0} ∪ {(1,0)};
• {(a,b)∈X: (a,b)
• etc.
∇
Para concluir esta secção, vejamos vários exemplos de relações bem fundadas, nomeadamente sobre
sequências36:
Exemplo 10:
Seja B um conjunto e seja A = B* (i.e., A é o conjunto formado por todas as sequências de elementos de
B, incluindo a sequência vazia: definição 2.5.5-a)).
a) Seja
p a relação binária em A, dada por:
(quaisquer que sejam as sequências s1 e s2, pertencentes a A)
s1
€
p
s2 sse s1 é uma "parte inicial estrita" de s2
onde37 (assumindo n,k≥0 e (a1, ..., an)=() se n=0):
€
36 Pensando na linguagem de programação Mathematica, refira-se que no exemplo 10, a seguir, em vez de sequências poderia
também estar listas, uma vez que se trata do mesmo tipo de estruturas (bastaria substituir a notação que se usa para descrever
sequências pela notação usada na linguagem Mathematica para a descrição de listas).
37 Nota: a sequência vazia é uma parte inicial de qualquer sequência e qualquer sequência é uma parte inicial de si própria.
89
• s1 = (a1, ..., an) é uma "parte inicial" de s2 = (b1, ..., bk)
sse
n ≤ k e, qualquer que seja 1≤i≤n, ai = bi (i.e., a1=b1 e ... e an=bn)
• s1 é uma "parte inicial estrita (ou própria)" de s2
sse
s1 é uma parte inicial de s2 e #s1 < #s2
(ou, de forma equivalente, sse s1 é uma parte inicial de s2 e s1 ≠ s2.)
p é uma ordem parcial estrita em A que é bem fundada.
Mas, se B tiver mais do que um elemento, então p não é uma boa ordem em A, pois não é uma
Então
ordem total: por exemplo, se b1 e b2 são dois elementos distintos de B, então as sequências (b1) e (b2)
€ não são comparáveis por meio de p .
b) Seja
p a relação binária em A, dada por:
€
€s1 p s2 sse s1 é uma "parte final estrita" de s2
onde:
€
• s1 = (a1, ..., an) é uma "parte final" de s2 = (b1, ..., bk)
sse
€
n ≤ k e, qualquer que seja 1≤i≤n, ai = bi+(k-n) (i.e., a1=bk-n+1 e ... e an=bk)
• s1 é uma "parte final estrita (ou própria)" de s2 sse s1 é uma parte final de s2 e #s1 < #s2
p é uma ordem parcial estrita em A que é bem fundada.
Mas, se B tiver mais do que um elemento, então p não é uma boa ordem em A (porquê ?).
Então
c) Seja
€
p a relação binária em A, dada por:
s1
€
p s2
sse s1 é uma€"subsequência estrita (ou própria)" de s2
(onde a noção de subsequência, e de subsequência própria, foi caracterizada na secção 5 do capítulo 2).
p é uma ordem parcial estrita em A que é bem fundada.
€
Mas, se B tiver mais do que um elemento, então p não é uma boa ordem em A (porquê ?).
Então
d) Seja agora
€
p a relação binária em A, dada por38:
s1
Então
€
p
s2 sse (s1 é uma
€ parte inicial de s2 e #s1 = #s2 - 1)
p ainda é uma relação bem fundada em A, mas já não é uma ordem parcial estrita, pois não é
transitiva (desde que A não seja vazio). Também não é, obviamente, total.
€
e) A situação é análoga à anterior, se p for qualquer uma das seguintes relações binárias em A:
€
38 Considerando as listas da linguagem Mathematica, esta relação pode ser expressa como se segue (usando as operações
€
disponibilizadas nessa linguagem - ver apêndice 2): s1
de números, será mais correcto dizer que s1
p s2
€
€
p s2
sse s1 ==Drop[s2,-1] (se não nos estivermos a referir a listas
sse s1 ===Drop[s2,-1], mas não entraremos aqui nessas questões).
90
€
s1
p
s1
p s2
s1
p
s2 sse39 (s1 é uma parte final de s2 e #s1 = #s2 - 1)
s2 sse40 #s1 = #s2 - 1
f) E a relação binária em A,
€
€
s1
p
sse (s1 é uma subsequência de s2 e #s1 = #s2 - 1)
p , dada por:
s2 sse41 #s1 < #s2
é uma relação bem
€ fundada e é uma ordem parcial estrita. No entanto, não é uma boa ordem, pois não é
total (duas sequências distintas, com o mesmo comprimento, não são comparáveis por meio de
€
p ).
∇
Exemplo 11:
€
p A uma relação bem fundada num conjunto A e f`: B → A.
Então a relação binária em B, p B, dada por:
Seja
(quaisquer que sejam b e b' pertencentes a B)
€
b
€
p B b' sse f(b) p A f(b')
é uma relação bem fundada em B (como é imediato de verficar: se, por absurdo, existisse uma cadeia
infinita descendente, em B, ...
p B bn p B
€ descendente
€ em A.
uma cadeia infinita
... p B b1
p B b0, então ... p B f(bn) p B ... p B f(b1) p B f(b0) seria
∇
Exercícios:
€
€
€
€
€
€
€
€
1. Demonstre que uma relação binária num conjunto não vazio pode não ser reflexiva sem ser irreflexiva.
2. Será que uma relação binária reflexiva num conjunto não vazio pode ser vazia ? E uma relação binária
irreflexiva ?
3. Demonstre que uma relação binária num conjunto não vazio pode não ser simétrica sem ser antisimétrica.
4. Será que uma relação binária num conjunto não vazio pode ser simultaneamente simétrica e antisimétrica ? Justifique.
5. Seja R uma relação binária num conjunto A. Demonstre que se R não é anti-simétrica e é transitiva,
então R não é irreflexiva.
6. Demonstre que se R é uma relação de ordem parcial num conjunto A, então a relação inversa (R-1)
também é uma relação de ordem parcial em A (e (A,R-1) diz-se o dual do cpo (A,R)).
7. Seja R uma relação de ordem parcial num conjunto A e seja X um subconjunto de A. Demonstre que:
39 Considerando as listas da linguagem Mathematica: s1
40 Considerando as listas da linguagem Mathematica: s1
41 Considerando as listas da linguagem Mathematica: s1
€
€
€
p s2
p s2
p s2
sse s1 ==Rest[s2].
sse Length[s1]==Length[s2]-1.
sse Length[s1]<Length[s2].
91
a) Um elemento c (de A) é um minorante de X no cpo (A,R) (isto é, com respeito à ordem parcial R)
sse c é um majorante de X no cpo dual (A,R-1) (isto é, com respeito à ordem parcial R-1).
b) Um elemento c é um elemento minimal de X no cpo (A,R) sse c é um elemento maximal de X no
cpo dual (A,R-1).
c) Um elemento c é um mínimo de X no cpo (A,R) sse c é um máximo de X no cpo dual (A,R-1).
d) Um elemento c é um ínfimo de X no cpo (A,R) sse c é um supremo de X no cpo dual (A,R-1).
8. Seja A um conjunto não vazio e R uma relação binária em A. Demonstre que R é simultaneamente
uma ordem parcial (em sentido lato) e uma relação de equivalência sse R é a relação de identidade em A
(ver definição no exercício 1.5, i.e. no exercício 5 da secção 1 deste capítulo).
9. Sejam R1 e R2 duas relações binárias num conjunto A. Demontre que se R1 é reflexiva e R2 é
irreflexiva, então (quaisquer que sejam x e y pertencentes a A) a condição
x R1 y ⇔ x R2 y ∨ x = y
é equivalente à condição
x R2 y ⇔ x R1 y ∧ x ≠ y
10. Seja
p uma relação reflexiva num conjunto A e designe-se por p a relação binária, em A, assim
definida: x
p y ⇔ x p y ∧ x ≠ y. Demontre que:
a)
p uma ordem parcial em sentido lato sse p é uma ordem parcial em sentido estrito
b)
p uma ordem total sse p é uma ordem total.
11. Seja
p uma relação irreflexiva num conjunto A e designe-se por p a relação binária, em A, assim
definida: x
p y ⇔ x p y ∨ x = y. Demontre que:
a)
p uma ordem parcial em sentido lato sse p é uma ordem parcial em sentido estrito
b)
p uma ordem total sse p é uma ordem total.
12. Seja (A, p ) um cpo, X um subconjunto (qualquer) de A, e c (∈A) um minorante de X. Demonstre que
se d (∈A) é tal que d
p c, então d é também um minorante de X.
13. Seja (A, p ) um cpo e X ⊆ A. Demonstre que o mínimo de X, quando existe, é único.
14. Prove que para que uma relação binária R num conjunto A seja uma relação de ordem total, em sentido
estrito, é necessário e suficiente que sejam satisfeitas as duas propriedades seguintes:
i) transitividade;
ii) quaisquer que sejam x e y pertencentes a A, verifica-se necessariamente uma e uma s ó das
condições: xRy, x=y, yRx.
15. Seja (A, p ) um cpo e X ⊆ A. Demonstre que se o mínimo de X existe, então existe o ínfimo de X e
min(X) = inf(X).
16. Seja (A, p ) um conjunto totalmente ordenado e X ⊆ A. Demonstre que o ínfimo de X (quando existe)
satisfaz a seguinte condição "qualquer elemento maior do que ele é maior do que algum elemento de X"
Isto é, simbolicamente: c = inf(X) ⇒ ∀z∈A(c
p z ⇒ ∃x∈X x p z)
17. Considere o conjunto dos racionais parcialmente ordenado pela usual relação ≤, i.e. considere o cpo
(Q, ≤), e considere o subconjunto X de Q assim definido: X = {x: x ∈ Q ∧ x2 < 2}.
a) X é majorado (nesse cpo) ?
92
b) X tem supremo (nesse cpo) ?
18. Seja (A, p ) um cpo e X e Y subconjuntos de A tais que X⊆Y, X admite supremo e Y também.
Demonstre que sup(X)
p sup(Y).
19. Determine todas as ordens parciais e totais (em sentido lato) que se podem definir nos conjuntos
seguintes (onde a, b e c são objectos distintos):
a) ∅
b) {a}
c) {a, b}
d) {a, b, c}
20. Seja (A, p A) um cpo e X = A2. Seja
(x1 , y1)
p X a relação binária em X assim definida:
p X (x2 , y2) sse x1 p A x2 e y1 p A y2
Demonstre que (X, p X) é um cpo.
p A e p B duas ordens totais, em sentido estrito, nos conjuntos A e B, respectivamente. Mostre
que a relação p C, em C = A x B, definida por:
(x1 , y1) p C (x2 , y2) sse x1 p A x2 ou (x1 = x2 e y1 p B y2)
21. Sejam
é uma relação de ordem total, em sentido estrito, em C (chamada ordem lexicográfica em C).
22. Seja (A, p ) um cpo e X um subconjunto de A. Demonstre que se X tiver máximo então o máximo de
X é um elemento maximal de X.
23. Demonstre que se (A1, R1) e (A2, R2) são dois cpo's, então (A1 ∩ A2, R1 ∩ R2) também é um cpo.
24. Considere a relação x
p y sse "x divide (é divisor de) y", no conjunto dos naturais, e diga quais são os
elementos maximais de X = {2, 3, 4, 8, 9}
25. Considere o cpo (A,
p ) = (℘{1,2,3,4}, ⊆).
a) Quais são os elementos maximais do conjunto X={{1}, {4},{1,2},{2,3},{1,2,3}} ?
b) O conjunto X={{1}, {4},{1,2},{2,3},{1,2,3}} tem supremo ?
c) O conjunto X={{1}, {4},{1,2},{2,3},{1,2,3}} tem máximo ?
26. Verifique que um elemento maximal de um subconjunto X de um cpo pode não ser um máximo de X.
27. Seja (A, p ) um cpo e X um subconjunto de A. Demonstre que se
p for uma ordem total, então um
elemento maximal de X é máximo de X.
28.
28. Diga quais das estruturas (A ,
p ) a seguir são conjuntos bem ordenados:
a) (A ,
p ) = (|N1 , ≤) (onde aqui, e nas alíneas a seguir, ≤ designa a usual relação de menor ou igual)
b) (A ,
p ) = (|R , ≤)
+
c) (|R , ≤) (onde |R+ designa o conjunto dos reais positivos)
d) (A ,
29. Seja
p ) = (|N0 , ≥)
p uma relação bem fundada num conjunto A.
a) Esboce a demonstração de que o fecho transitivo de
anterior) também é uma relação bem fundada.
93
p (i.e. a relação p +: ver exercício 11 da secção
b) Demonstre que o fecho reflexivo e transitivo de
p (i.e. a relação p *: ver exercício 11 da secção
anterior) é uma ordem parcial (lata).
p A e p B duas relações bem fundadas nos conjuntos A e B, respectivamente. Mostre que a
ordem lexicográfica p C em C = AxB (definida como no exercício 21) é bem fundada.
30. Sejam
(Sugestão: Considere um qualquer subconjunto D de C não vazio, e mostre que ele possui um
elemento minimal como se segue: considere D1 = {a∈A: ∃ b∈B (a,b)∈D}; seja m1 um elemento
minimal de D1; considere D2 = {b∈B: (m1,b)∈D}; seja m2 um elemento minimal de D2; verifique
que m=(m1,m2) é um elemento minimal de D)
31. Considere a linguagem de programação Mathematica.
a) Construa um programa recursivo (nessa linguagem) que, recebendo duas listas, retorna True se a
primeira é uma parte inicial da segunda, e retorna False, se tal não se verificar.
b) Construa um programa recursivo, e um programa não recursivo, que, recebendo duas listas, retorna
True se a primeira é uma parte inicial estrita da segunda, e retorna False, se tal não se verificar.
c) Construa um programa que, recebendo duas listas, retorna True se a primeira é uma parte final
estrita da segunda, e retorna False, se tal não se verificar.
d) Construa um programa que, recebendo duas listas, retorna True se a primeira é uma sublista da
segunda, e retorna False, se tal não se verificar.
∇
94