Capı́tulo 3
Relação de Equivalência e
Ordem
3.1
Relações de equivalência e abstracções
Uma relação binária R(x, y) em que tanto x como y percorrem certo conjunto,
X, diz-se relação de equivalência se tem as seguintes propriedades:
1) ∀x R(x, x) – propriedade reflexiva
2) ∀x ∀y [R(x, y) ⇒ R(y, x)] – propriedade simétrica
3) ∀x ∀y ∀z [R(x, y) ∧ R(y, z) ⇒ R(x, z)] – propriedade transitiva
Por exemplo, sendo X o conjunto das rectas do plano, x, y, . . . , a relação
“x é paralela a y” é relação de equivalência (se se convencionar que cada
recta é paralela a si própria); sendo X o conjunto dos números racionais,
Q, a relação “x é aproximadamente igual a y a menos de 0, 001” não é
relação de equivalência porque não satisfaz 3). As relações de equivalência
intervêm no processo mental de abstracção do modo seguinte: por vezes,
sabemos reconhecer se dois objectos, x e y, têm ou não certa analogia ainda
que não saibamos definir a caracterı́stica comum que os torna análogos, mas,
se a relação R(x, y) que traduz essa analogia entre x e y for uma relação
de equivalência, dado um objecto, x0 , o conjunto {x : R(x0 , x)} que representaremos por x̂0 e se chama a classe de equivalência definida por R e x0 e o
conjunto x̂1 = {x : R(x1 , x)} em que x1 satisfaz R(x0 , x1 ) – isto é, em que x1
é análogo a x0 – são iguais em virtude de 2) e 3). Deste modo, a propriedade
33
34
CAPÍTULO 3. RELAÇÃO DE EQUIVALÊNCIA E ORDEM
de pertencer a esta classe de equivalência não depende especificamente de
x0 , podendo ser definida por qualquer outro elemento, x1 , da mesma classe.
Abstraimos assim um conceito novo, a propriedade comum a x0 e aos objectos análogos (segundo R). Por exemplo, como a relação de paralelismo
entre rectas do plano é uma equivalência, todas as paralelas a certa recta
x0 têm uma propriedade comum, que se chama a direcção definida por x0
(ou por qualquer destas paralelas). Pelo contrário, com a relação de igualdade aproximada a menos de 0, 001, as coisas passam-se diferentemente: por
exemplo, o n.◦ 2, 4006 tem a propriedade de diferir de 2, 4 menos de 0, 001
mas a propriedade de diferir de 2, 4006 menos de 0, 001 já é outra (2, 3992
tem a primeira propriedade mas não a segunda).
Vimos que, se R(x0 , x1 ), as classes de equivalência x̂0 e x̂1 coincidem.
Vejamos agora que, se ∼ R(x0 , x1 ), as mesmas classes são disjuntas, isto é,
x̂0 ∩ x̂1 = 0. Porque, se existisse x2 ∈ x̂0 ∩ x̂1 verificar-se-iam R(x0 , x2 ) e
R(x1 , x2 ), donde, por 2), R(x2 , x1 ) e, por 3), R(x0 , x1 ), contradição.
Exemplo:
No conjunto
X = {1, 2, 3, 4, 5},
“x − y é múltiplo de 3” é uma relação de equivalência, visto que
∀x x − x é múltiplo de 3
∀x ∀y (x − y múltiplo de 3 ⇒ y − x múltiplo de 3)
∀x ∀y ∀z (x − y múltiplo de 3 ∧ y − z múltiplo de 3 ⇒ x − z múltiplo de 3)
As classes de equivalência são:
1̂ = 4̂ = {1, 4}
2̂ = 5̂ = {2, 5}
3̂ = {3}
Como se vê neste exemplo, e também de um modo geral, uma relação R
de equivalência definida no conjunto X efectua uma decomposição de X em
subconjuntos (as classes de equivalência) dois a dois sem elementos comuns.
Reciprocamente, seja dada uma decomposição de X em subconjuntos Ai :
[
X=
Ai
i∈I
35
3.2. CARDINAIS
com
∀i∈I ∀j∈I (i 6= j ⇒ Ai
\
Aj = 0)
A relação R(x, y) definida por ∃i∈I (x ∈ Ai ∧ y ∈ Ai ), isto é, x e y
satisfazem R sse ambos pertencem a um mesmo dos conjuntos Ai , é uma
relação de equivalência.
Demonstremos, por exemplo, que R é transitiva. Suponhamos que R(x, y)
e R(y, z), isto é,
∃i∈I (x ∈ Ai ∧ y ∈ Ai )
e
∃j∈I (y ∈ Aj ∧ z ∈ Aj )
Como
y ∈ Ai ∩ Aj , Ai ∩ Aj 6= 0, donde i = j
(porque i 6= j ⇒ Ai ∩ Aj = 0) de modo que z ∈ Ai e ∃i (x ∈ Ai ∧ z ∈ Ai ),
isto é, R(x, z).
Dado um conjunto, X, e uma relação de equivalência, R, definida em X,
fica então definido o conjunto das respectivas classes de equivalência, que se
X
chama conjunto quociente de X pela relação R e se escreve X/R ou .
R
No exemplo supra,
X
= {{1, 4}, {2, 5}, {3}}.
R
Como a cada elemento x de X corresponde uma e uma só classe (porque
duas classes distintas não têm elementos comuns), a classe x̂, e como cada
classe, x̂, tem pelo menos um elemento (o próprio x), vê-se que a aplicação
x 7→ x̂ é uma sobrejecção X → X/R.
3.2
Cardinais
Um exemplo importante de conceito definido por uma relação de equivalência
é o de número cardinal, ou cardinalidade ou potência de um conjunto; dados
dois conjuntos X e Y diz-se que são equicardinais ou equipotentes ou têm o
mesmo cardinal se existe uma bijecção de X para Y . A bijecção iX e o facto
de serem bijecções a inversa de uma bijecção e a composta de duas, mostram
36
CAPÍTULO 3. RELAÇÃO DE EQUIVALÊNCIA E ORDEM
que esta relação entre X e Y é, de facto, uma equivalência e a correspondente
noção é a de número cardinal 1 .
Às diversas classes de equicardinalidade correspondem, assim, números
cardinais 2 : à que é definida pelo conjunto vazio, ∅, (e que só possui esse
conjunto) corresponde um cardinal a que se chama 0 (zero); à classe de
equicardinalidade de que faz parte o conjunto {∅} (e todos os que lhe são
equicardinais, como {a}, {24}, etc.) corresponde um cardinal a que se chama
1; chama-se 2 o cardinal do conjunto {∅, {∅}}, 3 o cardinal do conjunto
{∅, {∅}, {∅, {∅}}} e assim por diante, considerando de cada vez um conjunto
cujos elementos são todos os conjuntos anteriores.
Ficam, assim definidos o zero e os números naturais e poderiam definir-se
também, para estes números, as relações de desigualdade (≤, ≥, <, >) e as
operações (+, −, ×, :, potenciação) que já conhecemos, e demonstrar, a partir
dessas definições, as suas propriedades.
Em particular poderia demonstrar-se o princı́pio de boa ordem (em qualquer conjunto de números naturais há um que é o menor de todos) e o
princı́pio de indução completa: se P (n) é uma propriedade da variável natural n,
P (1) ∧ ∀n [P (n) ⇒ P (n + 1)] ⇒ ∀n P (n)
Os números naturais constituem um conjunto N, cujo cardinal (chamado
álefe-zero, ℵ0 ) já não é um número natural, pois (num sentido intuitivamente
evidente, mas que adiante se definirá), os primeiros são finitos e o segundo
não.
Poderia ainda pensar-se que todos os conjuntos infinitos tinham o mesmo
cardinal, mas não é verdade: alguns têm “mais elementos” que outros, se se
definir esta noção do seguinte modo:
Dados dois conjuntos X e Y , diz-se que X ≤ Y se existe uma injecção
i : X → Y (o que sucede, por exemplo, se X ⊆ Y ). Se isto se verifica, i
é também uma bijecção X → i(X) ⊆ Y e, reciprocamente, se existe uma
bijecção b : X → Y1 ⊆ Y , b é também uma injecção b : X → Y . Em
particular, se X = Y existe uma bijecção b : X → Y e b−1 é também
1
O cardinal do conjunto A representa-se aqui pela sua primitiva notação: A. Outras
são Card A e #A.
2
A ideia de definir deste modo o número de elementos de um conjunto, que aparece por
vezes atribuı́da a Russell, foi exposta já em 1884 pelo matemático alemão F.L.G. Frege
(1848 - 1925) a quem se deve a fundamentação da aritmética na lógica.
37
3.2. CARDINAIS
bijectiva: Y → X, donde
X =Y ⇒X ≤Y ∧Y ≤X
Podem então, em princı́pio, acontecer quatro casos:
X ≤ Y ∧ Y ≤ X (isto é, existem injecções i : X → Y e j : Y → X)
X ≤Y∧∼Y ≤X
∼X ≤Y ∧Y ≤X
∼X ≤Y∧∼Y ≤X
É necessário recorrer agora a dois teoremas importantes da teoria dos conjuntos que não poderemos demonstrar aqui. O primeiro afirma que
∀X ∀Y X ≤ Y ∨ Y ≤ X,
propriedade que, por vezes, se chama dicotómica (da relação ≤) ficando deste
modo excluı́do o 4.◦ caso.
O outro teorema é o de Bernstein, e afirma que
X ≤Y ∧Y ≤X ⇒X =Y
isto é, se existem injecções i : X → Y e j : Y → X existe uma bijecção
b:X →Y.
Deste modo, dados os cardinais de dois conjuntos quaisquer, X e Y , ou
se está no primeiro caso e X = Y , ou no segundo e diz-se então que X < Y
porque é X ≤ Y mas não X = Y , ou no terceiro e diz-se então, por motivos
análogos, que Y < X. Este resultado constitui a propriedade tricotómica da
desigualdade de cardinais.
Definamos agora conjunto finito e conjunto infinito.
Representando por X ∗ ⊂ X o facto de ser X ∗ ⊆ X mas X ∗ 6= X, o que
se exprime também dizendo que X ∗ é parte própria de X, diz-se que X é
finito se nenhuma parte própria de X é equicardinal a X (isto é, se não existe
nenhuma bijecção b : X → X ∗ ⊆ X).
38
CAPÍTULO 3. RELAÇÃO DE EQUIVALÊNCIA E ORDEM
Por exemplo, {a, b} com a 6= b é finito porque as suas partes próprias são
∅, {a} e {b}, e facilmente se vê que nenhuma é equicardinal a {a, b}. Um
conjunto que não é finito diz-se infinito e o seu cardinal chama-se transfinito.
Um exemplo simples é o do conjunto N que é equicardinal a N \ {1}, pela
bijecção b(n) = n + 1, ou ao conjunto {1, 4, 9, 16, . . .} dos quadrados dos
números naturais 3 . Estes conjuntos e todos os que são equicardinais a N
chamam-se conjuntos numeráveis, isto é, que podem ser numerados usando
apenas os números naturais e todos eles.
Não podemos desenvolver aqui a teoria dos números cardinais (finitos ou
transfinitos) e das suas relações e operações mas vamos citar alguns resultados
importantes demonstrando alguns.
a) A infinito ⇒ A ≥ N
Suponhamos que existe b : A → A∗ ⊂ A. A \ A∗ tem pelo menos um
elemento, a1 . Seja a2 = b(a1 ), a3 = b(a2 ), . . . e em geral an+1 = b(an ).
Mostremos que estes elementos são todos distintos.
Com efeito, se não fossem todos distintos, pelo prı́ncipio de boa ordem
haveria um ı́ndice m que seria o menor ı́ndice tal que
∃n>m am = an .
De n > m deduz-se sucessivamente n > 1, an = b(an−1 ), an ∈ A∗ (por ser
imagem na bijecção b), am ∈ A∗ (por ser = an ), am = b(am−1 ), b(am−1 ) =
b(an−1 ) e am−1 = an−1 por ser b bijectiva. Mas isto contraria a hipótese de
ser m o menor ı́ndice, tal que
∃n>m am = an .
b) A ≥ N ⇒ A infinito
Seja i uma injecção: N → A. i é também uma bijecção i : N → i(N) que
tem uma inversa i1 : i(N) → N.
3
É o chamado paradoxo de Galileu: paradoxo, porque contradiz o axioma “a parte
é menor que o todo” que vem já dos geómetras gregos, e de Galileu porque nos tempos
modernos foi o astrónomo e fı́sico florentino Galileu Galilei (1564 - 1642), bem conhecido
protagonista da polémica em torno do heliocentrismo, quem chamou a atenção para este
facto. Mas descobriu-se recentemente que já na primeira metade do séc. XIV se tinham
ocupado do assunto dois autores, Henry of Harclay, em Oxford, e Gregorio da Rimini.
3.2. CARDINAIS
39
Considere-se a aplicação j : A → A definida por

se x ∈ A \ i (N)
 x
j(x) =

i(i1 (x) + 1) se x ∈ i (N)
j não é sobrejectiva porque, no primeiro caso, j(x) ∈ A \ i(N) e, no segundo,
i1 (x) + 1 nunca toma o valor 1, de modo que ∈ N \ {1} e, como i é injectiva,
j(x) = i(i1 (x) + 1) ∈ i(N \ {1}) = i(N) \ {i(1)}; logo, j(x) nunca toma valor
i(1).
Por outor lado, j é injectiva, pois: se j(x1 ) e j(x2 ) resultam do primeiro
caso (x1 e x2 ∈ A \ i(N)), j(x1 ) = j(x2 ) ⇒ x1 = x2 porque j(x1 ) = x1 , etc.;
se j(x1 ) e j(x2 ) resultam do segundo caso,
j(x1 ) = j(x2 ) ⇒ i(i1 (x1 ) + 1) = i(i1 (x2 ) + 1) ⇒ i1 (x1 ) + 1 = i1 (x2 ) + 1 ⇒
⇒ i1 (x1 ) = i1 (x2 ) ⇒ x1 = x2
em vista de serem i e i1 injectivas.
Então j é uma injecção A → A \ {i(1)} ⊂ A e A é infinito.
De a) deduz-se
c) Se A é infinito, contém um subconjunto numerável.
De a) e b) deduz-se
d) A é finito ⇔ A < N
Pode demonstrar-se que também
e) A é finito ⇔ A é um número natural, ou zero.
f) N × N é numerável.
g) A reunião de uma famı́lia numerável (isto é, cujo conjunto de ı́ndices é
N) de conjuntos numeráveis é um conjunto numerável.
h) A reunião de um número finito de conjuntos numeráveis é um conjunto
numerável.
40
CAPÍTULO 3. RELAÇÃO DE EQUIVALÊNCIA E ORDEM
i) A reunião de um conjunto finito com um conjunto numerável é um
conjunto numerável.
A segunda destas propriedades pode demonstrar-se elementarmente do
seguinte modo. N × N é o conjunto de todos os pares (m, n) em que m e
n são naturais. Se dispusermos estes pares num quadro com uma infinidade
numerável de linhas e uma infinidade numerável de colunas como o que é
sugerido à esquerda da figura 3 e se os numerarmos como é indicado pela
outra parte da mesma figura, segundo linhas oblı́quas 4 fica definida uma
bijecção de N × N para N.
(1, 1) (1, 2) (1, 3) (1, 4) · · ·
1
2
4
(2, 1) (2, 2) (2, 3) (2, 4) · · ·
3
5
8
(3, 1) (3, 2) (3, 3) (3, 4) · · ·
6
9
(4, 1) (4, 2) (4, 3) (4, 4) · · ·
10
7
11 · · ·
12 · · · · · ·
13 · · · · · · · · ·
14 · · · · · · · · · · · ·
···
···
···
··· ···
15 · · · · · · · · · · · · · · ·
···
···
···
··· ···
··· ··· ··· ··· ··· ···
Fig. 3
A propriedade g) pode demonstrar-se por um processo análogo:
Sendo A1 ∪ A2 ∪ . . . An ∪ . . . 5 uma reunião de conjuntos numeráveis,
podemos dispôr os elementos de A1 na primeira linha de um quadro como o
dos pares (m, n) da figura 3, os de A2 na segunda linha e assim por diante e
enumerá-los de modo análogo ao que aı́ se indicou apenas com a precaução
de desprezar os elementos que, por figurarem em mais de um dos conjuntos
An , já tinham recebido numeração. A demonstração de h) é análoga à de g)
e a de i) é muito fácil.
i) permite mostrar que é numerável o conjunto N0 = N ∪ {0}; daı́, usando
h), deduz-se que é numerável Z porque o conjunto dos inteiros negativos é evidentemente equicardinal a N; g) permite mostrar que é numerável o conjunto
4
É possı́vel indicar explicitamente uma função b(m, n) que defina uma bijecção b :
N × N → N de modo que esta propriedade se
[ demonstre sem recurso à figura.
5
Ai .
Modo sugestivo de exprimir a reunião
i∈N
3.3. RELAÇÕES DE ORDEM
41
Q+ dos números racionais positivos (A1 seriam as fracções de denominador
1, A2 as de denominador 2, etc...) e daqui se deduz, usando outra vez i) e
h), que Q também é numerável.
Finalmente, mostremos que
j) P(X) > X
Como a aplicação x 7→ {x} é uma injecção de X em P(X), X ≤ P(X).
Se fosse igual, existiria uma injecção i : P(X) → X.
Seja C = {i(A) : i(A) 6∈ A}. Se fosse i(C) ∈ C, i(C) seria um dos
elementos i(A) com a propriedade i(A) 6∈ A, logo i(C) 6∈ C, contradição. Se
fosse i(C) 6∈ C, i(C) teria aquela propriedade e i(C) ∈ C, outra contradição.
Logo, não existe i.
3.3
Relações de ordem
Chama-se relação de ordem (parcial) em sentido lato num conjunto X uma
relação binária R que tenha as seguintes propriedades:
1) ∀x R(x, x)
2) ∀x ∀y [R(x, y) ∧ R(y, x) ⇒ x = y]
3) ∀x ∀y ∀z [R(x, y) ∧ R(y, z) ⇒ R(x, z)]
A cada relação R deste tipo corresponde uma e uma só relação binária
R0 , relação de ordem (parcial) em sentido restrito definida por R 0 (x, y) sse
R(x, y) ∧ x 6= y, que tem as propriedades seguintes:
10 ) ∀x ∼ R0 (x, x)
20 ) ∀x ∀y ∼ [R0 (x, y) ∧ R0 (y, x)]
30 ) ∀x ∀y ∀z [R0 (x, y) ∧ R0 (y, z) ⇒ R0 (x, z)]
como seria fácil de provar.
Reciprocamente, dada uma relação R0 com as propriedades 10 ), 20 ) e 30 )
e definindo R por meio de
R(x, y) sse R0 (x, y) ∨ x = y
42
CAPÍTULO 3. RELAÇÃO DE EQUIVALÊNCIA E ORDEM
vê-se que R tem as propriedades 1), 2) e 3).
Também a partir de uma relação R se pode definir a relação inversa
−1
R (x, y), que se verifica sse R(y, x) e que é também uma relação de ordem
parcial, em sentido restrito ou em sentido lato, conforme for R.
Chama-se conjunto ordenado (parcialmente) um conjunto em que esteja
definida uma relação de ordem parcial (por exemplo, em sentido lato R e,
portanto, também as respectivas relações de ordem parcial R0 , R−1 e (R−1 )0 ).
Mais propriamente, um conjunto ordenado é o par (X, R) em que X é
um conjunto e R uma relação de ordem parcial.
Exemplos:
1.◦ ) O exemplo tı́pico é o da relação x ≤ y no conjunto N, Z, Q ou R.
Por este motivo, em vez de R(x, y), escreveremos muitas vezes x ≤ y,
mesmo que não se trate destes conjuntos ordenados e que ≤ tenha um
significado diferente.
As respectivas relações R0 , etc., são <, ≥ e >.
2.◦ ) Uma recta horizontal, como conjunto dos seus pontos, ordenados por
“x não está à direita de y”. No conjunto dos pontos de um plano esta
relação já não é de ordem parcial por se não verificar 2) nem 20 ).
3.◦ ) N, com a relação “x é divisor de y”.
4.◦ ) Sendo E um conjunto, P(E) com a relação X ⊆ Y , em que X ⊆ E e
Y ⊆ E.
5.◦ ) Considere-se o conjunto {a, b, c, . . . , h} de pontos indicados na figura 4:
a
?
 ???

??

??

??


??

?

b ???? ??c??  d
?? 
?? 
??
??
 ???  ???

?? 
??

f
e ???
 g

??


??

??

?? 
?? 

h
Fig. 4
43
3.3. RELAÇÕES DE ORDEM
com a relação “x = y ∨ x está abaixo de y e ligado a y por uma
poligonal que não é intersectada em mais de um ponto por nenhuma
recta horizontal”. Verifica-se, por exemplo, R(h, h), R(h, e), R(h, c)
mas não R(e, f ) porque uma poligonal que una e a f , como e b f ou
e h f já não tem a propriedade indicada.
Sendo finito o conjunto ordenado X, pode representar-se a relação de
ordem R por um esquema deste tipo.
O exemplo 3.◦ , no conjunto {2, 3, . . . , 10}, tem o esquema
8•
4•
6
9
10
3
5
7
•
•
jjjj•

jjjjjj 


j


jjjj
 jjjjjj





jjjj
•
•
•
2 •jj
Fig. 5
Dado um conjunto parcialmente ordenado (X, ≤), define-se:
a é um elemento máximo (ou maximal) de X quando, com x ∈ X, ∀x (a ≤
x ⇒ a = x).
Do mesmo modo, a é um elemento mı́nimo (ou minimal) de X quando
∀x (x ≤ a ⇒ x = a).
Pode haver ou não e haver um ou mais elementos máximos e mı́nimos.
Assim, considerem-se os seguintes exemplos:
6.◦ ) Em (N, ≤) não há máximos e há um único mı́nimo, 1.
7.◦ ) Em (Z, ≤) e no segundo dos exemplos anteriores não há máximos nem
mı́nimos.
8.◦ ) No exemplo a que se refere a figura 5 há cinco máximos, 6, 7, 8, 9 e
10 e 4 mı́nimos, 2, 3, 5 e 7.
9.◦ ) Em (P({1, 2, 3}), ⊆) há um máximo, {1, 2, 3}, e um mı́nimo, ∅. O
esquema deste conjunto ordenado é o da figura 4.
44
CAPÍTULO 3. RELAÇÃO DE EQUIVALÊNCIA E ORDEM
Desta noção de máximo e mı́nimo é preciso distinguir a seguinte:
Chama-se o maior (ou o máximo) elemento de X, se existir, ao elemento
a ∈ X tal que ∀x x ≤ a. Analogamente, a é o menor (ou o mı́nimo) elemento
de X quando ∀x a ≤ x.
O maior e o menor elemento de X podem existir ou não: em (Z, ≤) não
existem; em (N, ≤) existe só o menor elemento, 1; em (P{1, 2, 3}), ≤) {1, 2, 3}
é o maior elemento e ∅ o menor.
a) O maior [menor] elemento de X, se existe é um máximo [mı́nimo] e o
único máximo [mı́nimo].
Por exemplo, sendo a o maior elemento, ∀x x ≤ a. Então, se a ≤ x, a = x,
isto é, ∀x (a ≤ x ⇒ a = x) e a é máximo.
Se fosse a0 outro máximo, tinha de ser a0 ≤ a (por ser a o maior) e
a0 ≤ a ⇒ a0 = a por ser a0 máximo; logo, a0 = a.
Dado um subconjunto A do conjunto ordenado X, chama-se maiorante
de A, um elemento m de X tal que ∀x∈A x ≤ m; do mesmo modo, m é
minorante de A quando ∀x∈A m ≤ x.
Como nas definições anteriores, pode haver ou não maiorantes e minorantes. E um ou mais.
6
Exemplos:
10.◦ ) Em (Z, ≤) o conjunto N não admite maiorantes e tem muitos minorantes, como −4, 0 e até 1 (este por sinal ∈ N).
11.◦ ) No 5.◦ exemplo, o conjunto A = {b, c, d} tem um só maiorante, a, que
6∈ A e 4 minorantes, e, f, g, h.
Se A = ∅, como ∀x∈A x ≤ m significa ∀x (x ∈ A ⇒ x ≤ m) e a hipótese x ∈
A é sempre F , qualquer m ∈ X é maiorante (e, analogamente, é minorante)
de A.
Por vezes usam-se as seguintes abreviaturas:
Em vez de ∀x∈A x ≤ m escreve-se A ≤ m e, analogamente se interpretam
A < m, A ≥ m, A > m. Se ∀x∈A ∀y∈B x ≤ y, escreve-se A ≤ B e do mesmo
modo A < B, etc.7 .
6
Melhor que “majorante” pois todas as palavras portuguesas da famı́lia de “maior” se
escrevem com i, excepto “major”.
7
Não são relações de ordem em P(X).
45
3.3. RELAÇÕES DE ORDEM
Sendo (X, ≤) um conjunto ordenado e A ⊆ X, A e a restrição 8 da relação
≤ ao conjunto A definem um novo conjunto ordenado. Pode, por exemplo,
falar-se do maior dos elementos de A. E facilmente se vê que
b) O maior [menor] dos elementos de A é maiorante [minorante] de A (no
conjunto ordenado (X, ≤)).
Considere-se agora o conjunto MA dos maiorantes [minorantes] de A. Se
existe o menor [maior] elemento de MA , chama-se-lhe supremo ou extremo
superior [ı́nfimo ou extremo inferior] de A e representa-se por sup A [inf A].
Pode existir ou não, mas se existir é único em virtude de a).
Exemplos:
12.◦ ) N em (Z, ≤) não tem supremo (porque não tem maiorantes) mas tem
ı́nfimo, que é 1 e ∈ N.
13.◦ ) {b, c, d}, do exemplo 11.◦ , tem supremo, a, que 6∈ {b, c, d} mas não tem
ı́nfimo.
14.◦ ) Considere-se uma recta horizontal de que se excluiu um ponto, p, e
ordene-se este conjunto, X, pela relação do exemplo 2.◦ (figura 6).
X
A
◦
p
|
m
Fig. 6
Seja A = {x : x está à esquerda de p}. Os maiorantes de A são todos os
pontos de X que estão à direita de p (p não é maiorante porque não faz parte
de X). Mas não existe sup A porque, dado um dos maiorantes, m, o ponto
médio do segmento pm ainda é maiorante de A e está à esquerda de m.
Seja A uma parte do conjunto parcialmente ordenado X e MA o conjunto
dos seus maiorantes.
Então:
8
Isto é, a relação ≤ (x, y) que se verifica sse x ∈ A, y ∈ A e x ≤ y. Salvo indicação
em contrário, quando se considera como conjunto ordenado um subconjunto A de (X, ≤)
supõe-se que se toma para relação de ordem em A esta restrição de ≤.
46
CAPÍTULO 3. RELAÇÃO DE EQUIVALÊNCIA E ORDEM
a) m é o maior dos elementos de A sse m ∈ A ∩ MA .
Pois a definição de “maior dos elementos” foi que m ∈ A e ∀x∈A x ≤A m
sendo ≤A a restrição da relação ≤ ao conjunto A.
Mas, entre elementos x e m de A, x ≤A m sse x ≤ m, sendo pois m o
maior dos elementos de A sse m ∈ A ∧ ∀x∈A x ≤ m, isto é, sse m ∈ A ∩ MA .
a0 ) m é o menor dos elementos de A sse m ∈ A e m é minorante de A.
b) Se m ∈ A ∩ MA , m = sup A
m é maiorante de A. Para qualquer outro maiorante, m0 , ∀x∈A x ≤ m0 , logo,
porque m ∈ A, m ≤ m0 , isto é, m é minorante de MA e, como ∈ MA de
acordo com a0 ) é o menor dos maiorantes de A, isto é, o sup A.
b0 ) Se algum minorante de A pertencer a A é o inf A.
c) Se existe inf MA , existe sup A e é igual. E reciprocamente.
Seja c = inf MA .
Ora
∀a∈A a ≤ MA (a é minorante de MA ),
donde
∀a a ≤ c
por ser c o maior dos minorantes de MA .
Logo, c ∈ MA , mas como é minorante de MA , por a0 ), c é o menor
elemento de MA , isto é, sup A.
Reciprocamente, se c = sup A, é o menor elemento de MA , logo, por a0 )
e b0 ), é o inf MA .
c0 ) Se existe o supremo dos minorantes de A, existe inf A e é igual. E
reciprocamente.
Facilmente se vê que
d) m ≥ A ⇔ m ≥ sup A e m ≤ A ⇔ m ≤ inf A.
e) Se A ⊆ B, sup A ≤ sup B caso estes supremos existam.
47
3.3. RELAÇÕES DE ORDEM
De facto, x ∈ A ⇒ x ∈ B.
Logo, ∀x∈B x ≤ m ⇒ ∀x∈A x ≤ m.
Logo, m ∈ MB ⇒ m ∈ MA , isto é, MB ⊆ MA .
Como sup B ∈ MB , sup B ∈ MA , e como sup A é o menor elemento de
MA , sup A ≤ sup B.
e0 ) Se A ⊆ B e inf A e inf B existem, inf A ≥ inf B.
f) Se A 6= ∅ e inf A e sup A existem, inf A ≤ sup A porque ∃a a ∈ A e
inf A ≤ a ≤ sup A.
Mas é costume considerar sup ∅ igual ao menor dos elementos de X e inf ∅
igual ao maior, se estes elementos existirem (porque, por exemplo, ∀m∈X (x ∈
∅ ⇒ x ≤ m), de modo que M∅ = X).
Seja f : X → Y , em que X é um conjunto qualquer e Y um conjunto
ordenado pela relação ≤. Seja A ⊆ X.
f (A), como parte de Y , pode ter ou não sup e inf, que se chamam então
supremo ou ı́nfimo de f em A e se representam por sup f e inf f ou sup f (x)
A
A
x∈A
e inf f (x).
x∈A
Se em particular este supremo ou este ı́nfimo pertencerem a f (A), isto
é, forem valores efectivamente tomados pela função f em A, chamam-se o
máximo absoluto 9 de f em A e o mı́nimo absoluto de f em A.
Por exemplo, sendo f : R → R dada por x 7→ x2 e A = [−1, 2[, f (A) é
[0, 4[, inf f = 0, sup f = 4 e 0 é também o mı́nimo absoluto de f em A.
A
A
g) A ⊆ B ⇒ sup f ≤ sup f ∧ inf f ≥ inf f
A
A
B
B
Basta atender a e) e e0 ) e a que f (A) ⊆ f (B).
h) Se ∀x∈A f (x) ≤ g(x) e se sup f e sup g existem, sup f ≤ sup g.
A
A
A
A
Porque a hipótese implica que qualquer maiorante de g(A) é maiorante
de f (A), isto é, Mg(A) ⊆ Mf (A) , donde inf Mf (A) ≤ inf Mg(A) e estes ı́nfimos
são precisamente sup f e sup g.
A
9
A
Mesmo que, para abreviar, se diga apenas “o máximo de f em A” distingue-se esta
noção da de “um máximo de f (A)” porque agora se usa o artigo definido.
48
CAPÍTULO 3. RELAÇÃO DE EQUIVALÊNCIA E ORDEM
h0 ) Sob a mesma condição, se inf f e inf g existem, inf f ≤ inf g.
A
A
A
A
As noções de supremo, máximo, etc., de uma função aplicam-se naturalmente
a famı́lias (xi : i ∈ I), bastando que xi ∈ X, parcialmente ordenado.
Em particular o conjunto dos ı́ndices pode ser um produto cartesiano
I × J, isto é, pode tratar-se de um aplicação x : I × J → X, dada por
(i, j) 7→ xij .
Sem demonstração, citaremos uma propriedade importante.
i) Se ∀j∈J sup xij existe, então
I∈I
sup
xij existe sse existe sup xij e,
(i,j)∈ I×J
j∈J i∈I
nesse caso, estes dois supremos coincidem.
Seja agora f : X → Y uma aplicação entre dois conjuntos parcialmente
ordenados por certas relações de ordem que, para simplificar, designaremos
– ambas – pelo mesmo sinal ≤.
Diz-se que f é crescente em sentido lato quando
∀x ∀y [x < y ⇒ f (x) ≤ f (y)]
Analogamente, diz-se que f é crescente em sentido restrito, decrescente
em sentido lato e decrescente em sentido restrito quando se verificam propriedades análogas em que apenas a desigualdade f (x) ≤ f (y) é substituı́da,
respectivamente por f (x) < f (y), f (x) ≥ f (y) e f (x) > f (y).
No primeiro e no terceiro casos diz-se, ainda, que f é monótona em sentido
lato e que é monótona em sentido restrito nos outros dois.
É claro que a função crescente em sentido restrito é também crescente em
sentido lato, etc.
Se f é crescente e decrescente em sentido lato, ∀x ∀y [x < y ⇒ f (x) =
f (y)], de modo que f é constante.
15.◦ ) Exemplos de aplicações f : R → R classificadas quanto ao crescimento:
49
3.3. RELAÇÕES DE ORDEM
tt
tt
t
t
tt
tt
t
t
tt
tt
t
tt
tt
ttt
ttt
44
44
44
44
44
4
OOO
OOO
OOO
OOO
OOO OO
Fig. 7
Num conjunto parcialmente ordenado, X, dados dois elementos a e b,
chamam-se intervalos de extremos a e b (por esta ordem) os conjuntos
[a, b] = {x : a ≤ x ∧ x ≤ b}
10
intervalo fechado
]a, b[= {x : a < x ∧ x < b}
intervalo aberto
[a, b[= {x : a ≤ x ∧ x < b}
intervalo fechado à esquerda e aberto à direita
]a, b] = {x : a < x ∧ x ≤ b}
intervalo aberto à esquerda e fechado à direita
Consideram-se ainda os intervalos ilimitados [a, → [, ]a, → [, ] ←, b],
] ←, b[ e ] ←, → [, que significam, respectivamente,
{x : a ≤ x}, {x : a < x}, {x : x ≤ b}, {x : x < b} e X
16.◦ ) Exemplos de intervalos no conjunto ordenado do exemplo 5.◦ .
[e, a] = {e, b, c, a}, [g, a[= {g, c, d}, ]f, c[= ∅, [f, → [= {f, b, d, a},
[f, f ] = {f }, [f, h] = ∅, ] ←, h[= ∅
50
CAPÍTULO 3. RELAÇÃO DE EQUIVALÊNCIA E ORDEM
Facilmente se vê que os intervalos [a, → [ e ] ←, b] e, se a ≤ b, os intervalos
[a, b], [a, b[ e ]a, b] não podem ser vazios.
Se a < b e ]a, b[ é vazio, diz-se que a e b são consecutivos.
Consideremos agora diversas espécies particulares de conjuntos ordenados.
Diz-se que X, ordenado por ≤, é filtrante à direita [esquerda] quando
∀x ∀y ∃m (x ≤ m ∧ y ≤ m) [∀x ∀y ∃m (m ≤ x ∧ m ≤ y)],
isto é, quando dois quaisquer elementos possuem um maiorante [minorante]
comum.
j) Num conjunto filtrante à direita [esquerda], qualquer elemento máximo
é o maior [menor] elemento.
Seja a o máximo.
∀x ∃m (a ≤ m ∧ x ≤ m).
Como a é um máximo,
a ≤ m ⇒ a = m,
donde
∀x x ≤ a.
17.◦ ) O conjunto do exemplo 3.◦ é filtrante à direita (por exemplo m =
m.m.c. (x, y)) e à esquerda (m = 1).
18.◦ ) O conjunto parcialmente ordenado a, b, c representado por
a •??
•c
??

?? 
? 
•
b
é filtrante à esquerda mas não à direita.
Diz-se que X é um reticulado quando, dados dois quaisquer elementos, x
e y, existem
sup{x, y} e inf{x, y}
Exemplo:
3.3. RELAÇÕES DE ORDEM
51
19.◦ ) (P(E), ⊆) é um reticulado.
Dados A e B, contidos em E, os maiorantes de A, B, isto é, os subconjuntos
de E que contêm A e B são A ∪ B e todos os conjuntos que contêm A ∪ B.
A ∪ B é, pois, um maiorante ≤ que qualquer outro (isto é, ⊆ em qualquer
outro).
Logo, A∪B = sup{A, B} e analogamente inf{A, B} = A∩B, no conjunto
ordenado que estamos considerando.
1) Num reticulado a intersecção de dois intervalos é um intervalo.
Bastará analisar o que se passa num dos casos; os outros são análogos.
[a0 , b[ ∩ ]a00 , → [ = {x : a0 ≤ x ∧ x < b} ∩ {x : a00 < x}
= {x : a0 ≤ x ∧ x < b ∧ a00 ≤ x ∧ a00 6= x}
= {x : a0 ≤ x ∧ a00 ≤ x ∧ a00 6= x ∧ x < b}.
Seja a = sup {a0 , a00 }.
Então
a0 ≤ x ∧ a00 ≤ x ⇔ {a0 , a00 } ≤ x ⇔ a ≤ x
(de acordo com d). Logo, a intersecção daqueles intervalos é igual a
{x : a ≤ x ∧ a00 6= x ∧ x < b} = [a, b[\{a00 }.
Como a00 < a ∨ a00 = a, a mesma intersecção ou é [a, b[ ou ]a, b[.
Chama-se denso um conjunto parcialmente ordenado, tal que
∀a ∀b (a ≤ b ⇒]a, b[6= 0),
isto é, onde não há elementos consecutivos.
Por exemplo, (Q, ≤) é denso, porque, dados
m2
m1
e
,
n1
n2
a sua média aritmética é ainda ∈ Q e pertence ao intervalo aberto determinado por aqueles números; (Z, ≤) não é denso porque ]2, 3[, por exemplo, é
vazio.
Chama-se completo um conjunto parcialmente ordenado que satisfaz uma
das três condições seguintes (em que A e B designam subconjuntos do c.p.o.
X)
52
CAPÍTULO 3. RELAÇÃO DE EQUIVALÊNCIA E ORDEM
1) ∀A (A 6= ∅ ∧ A maiorado ⇒ ∃s s = sup A)
2) ∀B (B 6= ∅ ∧ B minorado ⇒ ∃i i = inf B)
3) ∀A ∀B (A 6= ∅ ∧ B 6= ∅ ∧ A ≤ B ⇒ ∃x A ≤ x ≤ B)
(diz-se que entre A e B, com A ≤ B, há uma lacuna se ∼ ∃x A ≤ x ≤ B).
Estas três condições são equivalentes entre si, bastando verificar-se uma
delas para que as outras se verifiquem (e o c.p.o. seja completo).
Demonstração:
Vejamos que 1) ⇒ 3). Se A e B satisfazem a hipótese de 3), como B 6= 0,
∃b (b ∈ B ∧ A ≤ b) (porque A ≤ B) de modo que A é maiorado; por 1) existe
s = sup A, o que implica, conforme a definição de sup, s ∈ MA e s ≤ MA ,
donde, respectivamente A ≤ s e s ≤ B (porque todos os elementos de B
pertencem a MA por ser A ≤ B); s é então o x a que se refere a tese de 3).
Vejamos que 3) ⇒ 2).
Seja B 6= 0 e minorado e seja A = {x : x é minorante de B}. A 6= 0
porque B é minorado e A ≤ B, dada a definição de A.
Então, por 3), ∃i A ≤ i ≤ B. A ≤ i significa que i é ≥ qualquer minorante
de B; i ≤ B significa ser i minorante de B.
Logo, i = inf B.
Vejamos que 2) ⇒ 1).
Se A satisfaz as hipóteses de 1), A maiorado, donde MA 6= 0, e A 6= 0, de
modo que MA minorado (por ser A ≤ MA ).
Então, por 2), existe inf MA , mas, como se viu em c), existe então sup A.
20.◦ ) Exemplo de um c.p.o. completo é (Z, ≤) pois se A é um conjunto de
inteiros não vazio (∃n1 n1 ∈ A) e maiorado (∃n2 A ≤ n2 ), como n1 ≤ n2
e entre n1 e n2 há apenas um número finito de inteiros, pode verificar-se
um a um se ∈ A ou 6∈ A e encontrar-se assim o maior dos elementos de
A, que é o sup A.
21.◦ ) Exemplo de um c.p.o. não completo é o exemplo 14.◦ , acima mencionado, por não existir sup A como logo se vê.
Há aqui, pois, uma lacuna entre A e X \ A como a figura 6 sugere.
22.◦ ) Outro exemplo de c.p.o. não completo é (Q, ≤).
53
3.3. RELAÇÕES DE ORDEM
Seja A = {q : q > 0 ∧ q 2 < 2}. 1 ∈ A, logo A 6= 0. q ∈ A ⇒ q ≤ 2, pois
q > 2 ⇒ q 2 > 4; logo A ≤ 2.
Se existisse, em Q, s = sup A, teria de ser 1 ≤ s ≤ 2.
Vejamos o valor de s2 .
m
Se s2 = 2, seja s = , irredutı́vel.
n
2
m
Então 2 = 2, m2 = 2 n2 , m par, m = 2 p, 4 p2 = 2 n2 , 2 p2 = n2 e n
n
m
par contra a hipótese de ser
irredutı́vel.
n
Se s2 < 2, como s2 ≥ 1, 0 < 2 − s2 ≤ 2 − 1 = 1.
Então,
(s +
2 − s2 2
2
(2 − s2 )2
) = s2 + s (2 − s2 ) +
5
5
25
2
2−s
4
≤ s2 + (2 − s2 ) +
5
25
(atendendo a que s ≤ 2 e 2 − s2 ≤ 1), donde
(s +
2 − s2 2
21
) = s2 +
(2 − s2 ) < s2 + (2 − s2 ) = 2.
5
25
2 − s2
∈ A, não podendo s ser maiorante de A.
5
Se s2 > 2, 0 ≤ s2 − 2, e
O racional s +
(s −
s2 − 2 2
2
(s2 − 2)2
) = s2 − s (s2 − 2) +
5
5
25
≥ s2 −
4 2
(s − 2)
5
porque s ≤ 2, vindo
(s −
Como s2 ≤ 4,
s2 − 2 2
5
) > s2 − (s2 − 2) = 2.
5
5
s2 − 2
2
s2 − 2
≤ <s e s−
é positivo.
5
5
5
54
CAPÍTULO 3. RELAÇÃO DE EQUIVALÊNCIA E ORDEM
s2 − 2
s2 − 2
6∈ A e, se q > s −
também q > 0 e q 2 > 2,
Logo, s −
5
5
donde q 6∈ A.
Então, q ∈ A ⇒ q ≤ s −
contradiz s = sup A.
s2 − 2
s2 − 2
e s−
∈ MA sendo < s, o que
5
5
Finalmente, um conjunto parcialmente ordenado (X, R) diz-se totalmente
ordenado ou linearmente ordenado se R satisfaz
4) ∀x ∀y [R(x, y) ∨ R(y, x)]
não podendo, pois, existir em X elementos incomparáveis (tais que nem
x ≤ y nem y ≤ x).
O conjunto do exemplo 5.◦ não é linearmente ordenado. Os conjuntos N, Z
e Q são-no.
Se R satisfaz esta condição, a respectiva relação de ordem em sentido
restrito, R0 , satisfaz a propriedade tricotómica:
∀x ∀y Verifica-se sempre uma e uma só das três condições seguintes:
R0 (x, y), x = y, R0 (y, x).
De facto, se R(x, y) ∨ R(y, x), há três casos possı́veis:
R(x, y) ∧ R(y, x), donde, por 2), x = y;
R(x, y)∧ ∼ R(y, x), donde R0 (x, y), porque ∼ R(y, x) implica, em vista
de 1), x 6= y; e analogamente, se ∼ R(x, y) ∧ R(y, x).
Em sentido inverso, se R0 é tricotómica, a respectiva relação R satisfaz 1)
e 2), como facilmente se vê, de modo que se pode caracterizar um conjunto
totalmente ordenado por meio de uma relação de ordem (em sentido restrito)
que seja, apenas, transitiva e tricotómica.
Algumas propriedades dos c.t.o.
m) Se (X, ≤) é totalmente ordenado, é um reticulado.
Pois, dados a e b, se a ≤ b, sup {a, b} = b e inf {a, b} = a, e inversamente se
a ≥ b.
55
3.3. RELAÇÕES DE ORDEM
n) Uma aplicação, f , monótona em sentido restrito de um conjunto totalmente ordenado X num conjunto parcialmente ordenado, Y , é injectiva
e a respectiva aplicação f −1 : f (X) → X é crescente em sentido restrito
ou decrescente em sentido restrito conforme for f .
Supondo f crescente,


 x < y ⇒ f (x) < f (y) 
ou
x 6= y ⇒
⇒ f (x) 6= f (y)


x > y ⇒ f (x) > f (y)
de modo que f é injectiva. Inversamente, dados dois elementos de f (X),
f (x) e f (y), f (x) 6= f (y) ⇒ x 6= y e o esquema anterior mostra que
<
<
f −1 [f (x)] = x > y = f −1 [f (y)] conforme f (x) > f (y).
o) Num conjunto totalmente ordenado, X, dado um subconjunto, A,
s = sup A ⇔ s ≥ A ∧ ∀x (x < s ⇒ ∃a∈A x < a ≤ s)
De facto, se s = sup A, é ≥ A e sendo x < s, ∼ x ≥ A, logo ∃a∈A ∼ x ≥ a.
Ora, sendo X totalmente ordenado,
∀x (∼ x ≥ a ⇔ x < a)
de modo que
11
∃a∈A x < a e a ≤ s por ser s = sup A.
Reciprocamente x < s ⇒ ∃a x < a significa x < s ⇒∼ x ≥ A, donde
x ≥ A ⇒∼ x < s ⇒ x ≥ s. Logo, s é minorante de MA , mas como s ≥ A,
s ∈ MA e é o sup A.
Analogamente, num conjunto totalmente ordenado
i = inf A ⇔ i ≤ A ∧ ∀x (x > i ⇒ ∃a x > a ≥ i).
11
De ∀x (∼ x ≥ a ⇔ x < a) deduz-se sucessivamente ∀x (∼∼ x ≤ a ⇔∼ x < a), e por 3)
da pág. ??, ∀x ∼∼ x ≥ a ⇔ ∀x ∼ x < a, e finalmente ∼ ∀x ∼∼ x ≥ a ⇔∼ ∀x ∼ x < a,
isto é, ∃x ∼ x ≥ a ⇔ ∃x x < a.