Pares ordenados
A ordem dos elementos em um conjunto não faz diferença; ou seja, os conjuntos \(\{a,b\}\) e \(\{b,a\}\) são iguais. Além disso, os conjuntos \(\{a,a,b\}\) e \(\{b,b,a\}\) são também iguais ao conjunto \(\{a,b\}\) e não tem como indicar quantas vezes um conjunto contém algum elemento. Às vezes é necessário trabalhar com coleções ordenadas de objetos (onde a ordem faz diferença) que podem também conter elementos mais que uma vez. Para isso servem os pares ordenados e as tuplas ordenadas. O par ordenado dos objetos \(a,b\) é denotado por \((a,b)\).
A propriedade fundamental de pares ordenados é que \[
(a,b)=(c,d)\quad \bicond\quad a=c\mbox{ e }b=d.
\]
Uma possível definição formal de um par ordenado é devido ao matemático Kuratowski. Ele definiu o par ordenado \((a,b)\) como o conjunto \(\{\{a\},\{a,b\}\}\). O leitor pode verificar que definindo assim pares ordenados, o conceito obtido satisfaz a propriedade fundamental.
Exemplo 6.1 No plano cartesiano, um ponto \(P\) está definido com suas coordenadas \((x,y)\); ou seja, com o par ordenado \((x,y)\). Por exemplo, o ponto \(P=(1,2)\) é diferente do ponto \(Q=(2,1)\) e precisamos também falar do ponto \(R=(-1,-1)\). De fato, dois pontos \(P_1=(x_1,y_1)\) e \(P_2=(x_2,y_2)\) são iguais se e somente se \(x_1=x_2\) e \(y_1=y_2\).
O produto cartesiano
Definição 6.1 O produto cartesiano de dois conjuntos \(A\) e \(B\) é o conjunto de pares ordenados \((a,b)\) tais que \(a\in A\) e \(b\in B\). Em símbolos, \[
A\times B=\{(a,b)\mid a\in A\mbox{ e }b\in B\}
\]
Exemplo 6.2 Por exemplo, se \(A=\{1,2\}\) e \(B=\{1,3,4\}\), então \[
A\times B=\{(1,1),(1,3),(1,4),(2,1),(2,3),(2,4)\}
\]
A seguinte tabela mostra os elementos de \(A\times B\).
| 1 |
(1,1) |
(2,1) |
|
| 3 |
(1,3) |
(2,3) |
|
| 4 |
(1,4) |
(2,4) |
|
| \(B\) |
|
|
|
Exemplo 6.3 O conjunto dos pontos no plano cartesiano pode ser identificado com o conjunto \[
\R\times \R=\{(x,y)\mid x,y\in \R\}.
\]
\(k\)-uplas ordenadas e produto cartesiano de vários conjuntos
Similarmente ao par ordenado, podemos considerar coleções ordenadas \((a_1,a_2,\ldots,a_k)\) (chamadas de \(k\)-uplas ou tuplas) de objetos. A propriedade fundamental destes \(k\)-uplas é que \[
(a_1,a_2,\ldots,a_k)=(b_1,b_2,\ldots,b_k)\quad\mbox{se e somente se}\quad \forall i\in\{1,\ldots,k\}\colon a_i=b_i.
\]
Podemos definir o produto cartesiano de conjuntos \(A_1,\ldots,A_k\) como \[
A_1\times \cdots \times A_k=\{(a_1,a_2,\ldots,a_k)\mid \forall i\in\{1,\ldots,k\}\colon a_i\in A_i\}.
\]
Exemplo 6.4 Similarmente ao plano cartesiano, um ponto no espaço cartesiano pode ser caraterizado por uma \(3\)-upla (tripla) \((x,y,z)\in\R\times \R\times \R=\R^3\). Assim o espaço cartesiano pode ser identificado com o conjunto \(\R^3=\R\times \R\times\R\).
Na disciplina GAAL, vocês estudam o espaço \(\R^n\) que pode ser visto como o produto cartesiano \(\R\times\cdots\times\R\) de \(n\) cópias de \(\R\) e seus elementos são \(n\)-uplas \((x_1,\ldots,x_n)\) com \(x_i\in \R\).
Relações
Definição 6.2 Sejam \(A\) e \(B\) conjuntos. Uma relação entre \(A\) e \(B\) é um subconjunto \[
R\subseteq A\times B.
\] Quando \(A=B\) e \(R\subseteq A\times A\), dizemos que \(R\) é uma relação sobre \(A\) ou uma relação em \(A\).
Exemplo 6.5 Por exemplo, considerando o conjunto no Exemplo 6.2, o conjunto \[
R=\{(1,3),(1,4),(2,1)\}
\] é uma relação entre \(A\) e \(B\).
Definição 6.3 Seja \(R\subseteq A\times B\). Quando \((a,b)\in R\) dizemos que \(a\) está relacionado com \(b\), \(a\) está em relação com \(b\), ou que \(a\) e \(b\) estão relacionados. Neste caso escrevemos \[
aRb.
\]
Exemplo 6.6 No Exemplo 6.5, temos que \(1\) está relacionado com \(3\) pela relação \(R\) e escrevemos que \(1R3\). Por outro lado, \(2\) não está relacionado com \(3\) pela mesma relação e escrevemos que \(2\not R3\).
Quando trabalhamos com relações teoricamente, denotamo-nas com letras como \(R\), \(Q\), \(S\), etc. Quando trabalhamos com relações particulares, usaremos símbolos tais como \(=\), \(\leq\), \(<\), \(\prec\), etc, como nos seguintes exemplos.
Exemplo 6.7 Os seguintes são exemplos importantes de relações.
Em qualquer conjunto \(A\neq\emptyset\), temos a relação igualdade \(=\). Formalmente, a igualdade é a relação \[
\{(a,a)\mid a\in A\}\subseteq A\times A.
\] Dois elementos \(a,b\in A\) estão relacionados se e somente se \(a=b\).
Se \(A\subseteq \R\) não vazio, então temos a relação menor \(<\). Esta relação está definido com o conjunto \[
\{(a,b)\in A\times A\mid a<b\}\subseteq A\times A.
\] Podemos definir similarmente a relação menor ou igual \(\leq\) como o conjunto \[
\{(a,b)\in A\times A\mid a\leq b\}\subseteq A\times A.
\] Além disso, o leitor pode também definir as relações maior e maior ou igual.
No conjunto \(\Z\) podemos definir a relação divisor \(\mid\). Esta relação está definida formalmente como \[
\{(a,b)\in\Z\times\Z\mid b=qa\textrm{ com algum }q\in \Z\}.
\]
Propriedades de relações
Definição 6.4 Seja \(R\) uma relação sobre \(A\).
- Dizemos que \(R\) é reflexiva se \(aRa\) para todo \(a\in A\) (ou seja \((a,a)\in R\) para todo \(a\in A\)).
- Dizemos que \(R\) é simétrica se \(aRb\) implica que \(bRa\) para todo \(a,b\in A\).
- Dizemos que \(R\) é antisimétrica se \(aRb\) e \(bRa\) implicam que \(a=b\) para todo \(a,b\in A\).
- Dizemos que \(R\) é transitiva se \(aRb\) e \(bRc\) implicam que \(aRc\) para todo \(a,b,c\in A\).
Exemplo 6.8 Considerando as relações no Exemplo 6.7, temos que as relações de igualdade, maior ou igual, menor ou igual, e divisor são reflexivas. A igualdade é simétrica. As relações maior ou igual, menor ou igual, maior e menor são antisimétricas, e todas as relações neste exemplo são transitivas.
Relações de equivalência
Relações de equivalência fornecem uma ferramenta importante na matemática, pois elas nos permitem considerar objetos distintos como fossem iguais. Comecemos com o seguinte exemplo. Considere as frações \(2/3\) e \(4/6\). Se perguntar um aluno aleatório da matemática, ele ou ela provavelmente vai dizer que estas duas são iguais. Mas se perguntar o mesmo aluno quais são os numeradores destas frações, o mesmo aluno vai responder que o numerador do primeiro é \(2\) enquanto o numerador do seguindo é \(4\). Mas isso, parece contraditório, pois se elas são iguais, as suas caraterísticas devem ser as mesmas, e como podem ter numeradores diferentes?
A solução a este paradoxo é reconhecer que \(2/3\) e \(4/6\) são frações diferentes, mas representam o mesmo número racional e elas podem ser trocadas entre si em contas aritméticas. Ou seja, elas são equivalentes do ponto de vista da aritmética. O conceito da relação de equivalência captura este fenômeno e nos permite analisar conceitos similares de maneira matematicamente rigorosa.
Definição 6.5 Seja \(A\) um conjunto. Uma relação \(R\subseteq A\times A\) é dita relação de equivalência se
- \(R\) é reflexiva (ou seja, \(aRa\) para todo \(a\in A\));
- \(R\) é simétrica (ou seja \(aRb\) implica \(bRa\) para todo \(a,b\in A\)); e
- \(R\) é transitiva (ou seja \(aRb\) e \(bRc\) implica \(aRc\) para todo \(a,b,c\in A\)).
As relações de equivalência são normalmente denotadas com os símbolos \(\equiv\), \(\cong\), etc, e escrevemos \(a\equiv b\) ou \(a\cong b\) em vez de \(aRb\).
Exemplo 6.9 O protôtipo das relações de equivalência é a relação de igualdade. A relação de igualdade \[
\{(a,a)\mid a\in A\}
\] é uma relação de equivalência para todo conjunto \(A\).
Exemplo 6.10 Seja \(A=\{1,2,3,4,5\}\) e seja \[
\equiv=\{(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,1),(3,4),(3,5),(4,3),(4,5),(5,3),(5,4)\}
\] Então \(\equiv\) é uma relação de equivalência.
Exemplo 6.11 Considere a relação \(R\) em \(\Z\) definido como \[
a\equiv b\quad\mbox{se e somente se $a-b$ é par}.
\] Note que \(\equiv\) é uma relação de equivalência. Também note que \(a\equiv b\) se e somente se \(a\) e \(b\) tem a mesma paridade. Ou seja, \(0\equiv 2\), \(0\equiv -2\), \(0\equiv 4\), \(0\equiv -4\), \(1\equiv -1\), \(1\equiv 3\), \(1\equiv -3\), etc, mas \(2\not\equiv -1\).
Classes de equivalência
Definição 6.6 Seja \(A\) um conjunto e \(\equiv\) uma relação de equivalência. Seja \(a\in A\). O conjunto \[
[a]_\equiv=\{b\in A\mid a\equiv b\}
\] é chamado de classe de equivalência de \(a\) pela relação \(\equiv\). Quando não tem perigo de ambiguidade, escrevemos \([a]\) em vez de \([a]_\equiv\). Note que \([a]\subseteq A\).
Exemplo 6.12 No Exemplo 6.9, a classe de equivalência de um elemento \(a\in A\) é o conjunto \(\{a\}\). No Exemplo 6.10, temos que \[
[1]=[2]=\{1,2\}\quad \mbox{e}\quad [3]=[4]=[5]=\{3,4,5\}.
\] No Exemplo 6.10, temos que \[
[a]=\{0,\pm 2,\pm 4,\ldots\}=\{2k\mid k\in\Z\}\quad\mbox{se}\quad \mbox{$a$ é par},
\] e \[
[a]=\{\pm 1,\pm 3,\ldots\}=\{2k+1\mid k\in\Z\}\quad\mbox{se}\quad \mbox{$a$ é ímpar}.
\] Ou seja, temos apenas duas classes de equivalência, uma formada pelos números pares, e a outra formada pelos números ímpares.
Lema 6.1 Seja \(A\) um conjunto e assuma que \(\equiv\) é uma relação de equivalência. Temos as seguintes propriedades para todo \(a,b\in A\).
- \(a\in [a]\);
- \([a]=[b]\) se e somente se \(a\equiv b\).
- se \([a]\cap [b]\neq \emptyset\) então \([a]=[b]\).
Comprovação.
- Note que \(a\in[a]\) é equivalente a dizer que \(a\equiv a\) e isso vale pois a relação \(\equiv\) é reflexiva.
- Assuma primeiro que \([a]=[b]\). Vamos provar que \(a\equiv b\). Temos por item 1. que \(a\in[a]\). Mas como \([a]=[b]\) isso implica que \(a\in [b]\). Ora, a definição de \([b]\) implica que \(b\equiv a\) e a simetria da relação \(\equiv\) implica que \(a\equiv b\). Agora assuma que \(a\equiv b\). Vamos provar que \([a]=[b]\); ou seja \([a]\subseteq [b]\) e \([b]\subseteq [a]\). Na primeira inclusão, seja \(x\in[a]\). Pela definição de \([a]\), temos que \(a\equiv x\). Por suposição, temos que \(a\equiv b\) e a simetria implica que \(b\equiv a\). Ora, \(b\equiv a\) e \(a\equiv x\) e a transitividade implicam que \(b\equiv x\). Ou seja \(x\in [b]\), pela definição de \([b]\). A inclusão que \([b]\subseteq [a]\) pode ser demonstrada da mesma forma. Assuma que \(y\in [b]\); ou seja \(b\equiv y\). Como temos \(a\equiv b\) e \(b\equiv y\), a transitividade implica que \(a\equiv y\); ou seja a definição de \([a]\) dá que \(y\in[a]\). Ou seja, temos que \([a]\subseteq [b]\) e \([b]\subseteq [a]\) e assim \([a]=[b]\) como foi afirmado.
- Assuma que \(c\in [a]\cap [b]\). Isso quer dizer que \(a\equiv c\) e \(b\equiv c\). Por simetria temos também que \(c\equiv b\). Ora por transitividade, \(a\equiv c\) e \(c\equiv b\) implicam que \(a\equiv b\) e item 2. mostra que \([a]=[b]\).
Partições
Definição 6.7 Seja \(A\) um conjunto. Um conjunto \(\mathcal P\) de subconjuntos de \(A\) é dito partição de \(A\) se
- todo elemento \(a\in A\) pertence a um subconjunto \(X\in \mathcal P\); e
- se \(X,Y\in \mathcal P\) são distintos, então \(X\cap Y=\emptyset\).
Os conjuntos \(X\in\mathcal P\) são chamados de partes ou blocos da partição \(\mathcal P\).
Exemplo 6.13 Todo conjunto \(A\) tem duas partições triviais: \[
\{A\}\quad\mbox{e}\quad \{\{a\}\mid a\in A\}.
\] O conjunto \(\{\{1,2\},\{3,4,5\}\}\) é uma partição do conjunto \(\{1,2,3,4,5\}\). O conjunto dos números inteioros pode ser particionado como \[
\{\{2k\mid k\in \Z\},\{2k+1\mid k\in\Z\}\}.
\] Ou seja, o conjunto dos inteiros pode ser particionado para o conjunto de pares e o conjunto de ímpares.
Teorema 6.1 Seja \(A\) um conjunto. Se \(\equiv\) é uma relação de equivalência sobre \(A\), então o conjunto das classes de equivalência é uma partição de \(A\).
Reciprocamente, se \(\mathcal P\) é uma partição de \(A\), então pode-se definir uma relação de equivalência \(\equiv_{\mathcal P}\) pondo \[
a\equiv_{\mathcal P} b\quad \bicond\quad \mbox{$a$ e $b$ estão no mesma parte de $\mathcal P$}.
\] As classes de equivalência de \(\equiv_{\mathcal P}\) são as partes de \(\mathcal P\).
Comprovação. Assuma primeiro que \(\equiv\) é uma relação de equivalência. Seja \(\mathcal C\) o conjunto de classes de equivalência. Por item 1. do Lema 6.1, obtemos que \(a\in [a]\in \mathcal C\) para todo \(a\in A\). Então o item 1. da Definição 90.1 está verificada. O item 2. da Definição 90.1 está verdadeira para \(\mathcal C\) por causa do item 2. do Lema 6.1.
Assuma agora que \(\mathcal P\) é uma partição de \(A\) e defina \(\equiv_{\mathcal P}\) como no enunciado do teorema. Vamos verificar as três propriedades na definição Definição 6.5.
- Reflexividade: se \(a\in A\), então \(a\) claramente pertence à mesma parte de \(\mathcal P\) que \(a\) e \(a\equiv_{\mathcal P} a\). Logo \(\equiv_{\mathcal P}\) é reflexiva.
- Simetria: se \(a\equiv_{\mathcal P}b\), então \(a,b\) pertencem à mesma parte de \(\mathcal P\). Logo \(b,a\) também pertencem à mesma parte e assim \(b\equiv_{\mathcal P}a\). Portanto \(\equiv_{\mathcal P}\) é simétrica.
- Transitividade: se \(a\equiv_{\mathcal P}b\) e \(b\equiv_{\mathcal P}c\), então \(a\) e \(b\) pertencem à mesma parte \(X\) de \(\mathcal P\) e \(b\) e \(c\) também pertencem à mesma parte \(Y\) de \(\mathcal P\). Como \(b\in X\cap Y\), temos que \(X\cap Y\neq \emptyset\) e a contrapositiva do item 2. da Definição 90.1 implica que \(X=Y\). Isso implica que \(a,c\in X\); ou seja, eles pertencem à mesma parte de \(\mathcal P\). Portanto \(a\equiv_{\mathcal P}c\) e a relação \(\equiv_{\mathcal P}\) é transitiva.
Finalmente, seja \(a\in A\) e assuma que \(a\in X\in\mathcal P\) (ou seja \(a\) pertence ao bloco \(X\) de \(\mathcal P\)). A classe de equivalência de \(a\) é \[
[a]=\{b\in A\mid a\equiv_{\mathcal P}b\}=\{b\in A\mid b\in X\}=X.
\] Portanto a classe \([a]\) coincide com \(X\).
Exemplo: Classes residuais
Como nós já discutimos, dizemos que \(a\) divide \(b\) (\(a\) e \(b\) são números inteiros) se \(b=qa\) com algum \(q\) inteiro. Neste caso pode-se dizer também que \(a\) é um divisor de \(b\) ou que \(b\) é múltiplo de \(a\). Se \(a\) divide \(b\), então escrevemos \(a\mid b\).
Defina a seguinte relação sobre \(\Z\): \[
a\equiv_3 b\quad\bicond\quad b-a=3k\mbox{ com algum }k\in\Z.
\] Pode também dizer que \(a\equiv_3 b\) se e somente se \(3\mid b-a\).
Lema 6.2 A relação \(\equiv_3\) é uma relação de equivalência sobre \(\Z\).
Comprovação. Por definição, Definição 6.5, precisamos verificar que a relação é reflexiva, simétrica, e transitiva.
Reflexividade: Se \(a\in\Z\), então \(a-a=0=3\cdot 0\). Logo \(a\equiv_3 a\).
Simetria: Sejam \(a,b\in\Z\) tal que \(a\equiv_3 b\). Então \(b-a=3k\) e assim \(a-b=-(b-a)=-3k=3(-k)\).
Transitividade: Sejam \(a,b,c\in\Z\) tais que \(a\equiv_3 b\) e \(b\equiv_3 c\); ou seja \(b-a=3k_1\) e \(c-b=3k_2\). Neste caso \[
c-a=(b-a)+(c-b)=3k_1+3k_2=3(k_1+k_2).
\] Pronto.
Exemplo 6.14 Por exemplo \(2\equiv_3 5\), pois \(5-2=3=3\cdot 1\). Temos também que \(1\equiv_3 -2\), pois \(-2-1=-3=3\cdot (-1)\). Por outro lado, \(1\not\equiv_3 -1\), pois \(-1-1=-2\neq 3k\).
Quais são as classes de equivalência (Definição 6.6)? Por exemplo, qual conjunto é a classe \([0]\) de \(0\)? Temos pela definição da classe \([0]\) que \[
[0]=\{a\in\Z\mid 0\equiv_3 a\}=\{a\in\Z\mid a-0=3k\}=\{a\in\Z\mid a=3k\}=\{3k\mid k\in \Z\}.
\] Ou seja, \[
[0]=\{0,3,-3,6,-6,\ldots\}=\{3k\mid k\in\Z\}.
\] Similarmente \[\begin{align*}
[1]&=\{a\in\Z\mid 1\equiv_3 a\}=\{a\in\Z\mid a-1=3k\}=\{a\in\Z\mid a=3k+1\}\\&=\{1,-2,4,-5,7,-8,10,\ldots\}
\end{align*}\] e \[\begin{align*}
[2]&=\{a\in\Z\mid 2\equiv_3 a\}=\{a\in\Z\mid a-2=3k\}=\{a\in\Z\mid a=3k+2\}\\&=\{2,-1,5,-4,8,-7,\ldots\}
\end{align*}\]
Obtemos que todo número inteiro pertençe a uma das classes de equivalência \([0],[1],[2]\). De fato se \(a\in\Z\), então o resto de \(a\) quando dividido por \(3\) é \(0\), \(1\) ou \(2\) e \(a\in[r]\) onde \(r\) é o seu resto. Assim temos apenas estas três classes.
Exercício 6.1 Seja \(n\geq 2\) um inteiro e defina a relação \(\equiv_n\) sobre \(\Z\) na seguinte forma: \[
a\equiv_n b\quad\mbox{se e somente se $b-a=kn$ com algum $k\in \Z$}.
\] Descreve as classes de equivalência para a relação \(\equiv_n\).
Mais exemplos
Exemplo 6.15 O exemplo dado no início da Seção 6.6 pode ser formalizado na seguinte maneira usando relações de equivalência. Uma fração \(a/b\) pode ser identificado com um par ordenado \((a,b)\in\Z\times (\Z\setminus\{0\})\). De fato, a ordem dos números na fração é importante, \(a\) e \(b\) são números inteiros e \(b\neq 0\) (pois divisão por zero não é permitida). Mas as frações não satisfazem a propriedade principal dos pares ordenados, pois \(a/b\) e \(c/d\) podem ser iguais (como números racionais) mesmo quando \(a\neq c\) ou \(b\neq d\). Considere \(A=\Z\times (\Z\setminus\{0\})\) e considere a seguinte relação \(\sim\) sobre \(A\): \[
(a,b)\sim (c,d)\quad\mbox{se e somente se}\quad ad=bc.
\] Afirmamos que \(\sim\) é uma relação de equivalência. Na prova vamos precisar da lei cancelativa que diz que quando \(x,y,z\in \Z\) tal que \(z\neq 0\), a equação \(xz=yz\) implica que \(x=y\) (ou seja, \(z\) pode ser cancelado).
- Reflexividade: Seja \((a,b)\in A\). Então \(ab=ba\), portanto \((a,b)\sim (a,b)\).
- Simetria: Assuma que \((a,b),(c,d)\in A\) tais que \((a,b)\sim (c,d)\). Então \(ad=bc\). Mas isso implica que \(cb=da\) que mostra que \((c,d)\sim (a,b)\).
- Transitividade: Assuma que \((a,b),(c,d),(e,f)\in A\) tais que \((a,b)\sim (c,d)\) e \((c,d)\sim (e,f)\). A definição de \(\sim\) implica que \[\begin{align*}
ad&=bc\\ cf&=de.
\end{align*}\] Multiplicando as duas equações: \(adcf=bcde\). Como \(c,d\neq 0\), podemos usar a lei cancelativa que implica que \(af=be\) que implica que \((a,b)\sim (e,f)\).
Note que \((a,b)\sim (c,d)\) se e somente se \(ad=bc\). Dado que \(b,d\neq 0\), esta relação equivale a dizer que \(a/b=c/d\) como números racionais. Isso quer dizer que a classe da equivalência \([(a,b)]\) contém exatamente os pares \((c,d)\) tais que \(a/b\) e \(c/d\) representam o mesmo número racional. Por exemplo, \[
[(1,2)]=\{(1,2),(2,4),(-1,-2),(-2,-4),(3,6),(-3,-6),\ldots\}
\] Em outras palavras, as classes de equivalência correspondem aos números racionais.
O seguinte exemplo é similar e deixamos ao leitor verificar os detalhes.
Exercício 6.2 Seja \(A=\N\times \N\) e defina a seguinte relação sobre \(A\): \[
(a,b)\equiv (c,d)\quad\bicond \quad a+d=b+c.
\]
- Mostre que \(\equiv\) é uma relação de equivalência.
- Ache as classes de equivalência dos elementos \((1,2)\), \((2,4)\), e \((3,5)\).
- Dê uma descrição de todas as classes de equivalência.
No seguinte exemplo voltamos ao exemplo motivador da seção e estudamos a relação que explica melhor os números racionais.
Relação de ordem
Definição 6.8 Seja \(A\) um conjunto e \(R\) uma relação em \(A\). Dizemos que \(R\) é uma relação de ordem (ou ordem parcial) em \(A\) se
- \(R\) é reflexiva (\(aRa\) para todo \(a\in A\));
- \(R\) é antisimétrica (se \(aRb\) e \(bRa\) então \(a=b\) para todo \(a,b\in A\));
- \(R\) é transitiva (se \(aRb\) e \(bRc\) então \(aRc\) para todo \(a,b,c\in A\)).
Exemplo 6.16
Se \(A\) é um conjunto de números, então as relações \(\leq\) e \(\geq\) são relações de ordem, mas as relações \(<\) e \(>\) não são relações de ordem pela Definição 6.8 (pois elas não são reflexivas).
Assuma que \(X\) é um conjunto e seja \[
A=\{Y\mid Y\subseteq X\}.
\] As relações \(\subseteq\) e \(\supseteq\) são relações de ordem sobre \(A\).
Seja \(A=\N\) e considere a relação \(\mid\) de divisibilidade. Em outras palávras, \(a\mid b\) se e somente se \(b=qa\) com algum \(q\in\N\). Então \(\mid\) é uma relação de ordem sobre \(A\). Note que a mesma relação não é relação de ordem sobre \(\Z\), pois \(2\mid -2\) e \(-2\mid 2\), mas \(-2\neq 2\). Ou seja, \(\mid\) não é antisimétrica em \(\Z\).
Definição 6.9 Seja \(R\) uma relação de ordem sobre o conjunto \(A\), Dizemos que \(R\) é uma ordem total ou ordem linear se \[
aRb\quad \mbox{ou}\quad bRa
\] vale para todo \(a,b\in R\).
Exercício 6.3 Entre os exemplos no Exemplo 6.16, 1. é ordem total, mas 2. e 3. não são ordens totais.