aula_14_ordem

Prévia do material em texto

Relac¸o˜es de ordem
Renata de Freitas e Petrucio Viana
Instituto de Matema´tica e Estat´ıstica, UFF
Abril de 2011
Suma´rio
• Reflexividade, antissimetria, transitividade.
• Relac¸o˜es de ordem.
• Principais exemplos.
• Elementos e propriedades especiais.
Helmut Hasse
• Matema´tico alema˜o.
(1898 – 1979)
Motivac¸a˜o
Algumas relac¸o˜es organizam os objetos relacionados em n´ıveis.
aRb
se, e somente se,
a esta´ no mesmo degrau ou
em degrau abaixo ao de b.
Inclusa˜o
Uma das mais famosas e´ a inclusa˜o de conjuntos.
Propriedades da inclusa˜o:
(1) Para todo conjunto A, temos que A ⊆ A.
(2) Para todos os conjuntos A,B, se A ⊆ B e B ⊆ A, enta˜o
A = B.
(3) Para todos os conjuntos A,B,C , se A ⊆ B e B ⊆ C , enta˜o
A ⊆ C .
Inclusa˜o organiza os conjuntos
Diagramas de Hasse
P({x})
Inclusa˜o organiza os conjuntos
P({x , y})
Inclusa˜o organiza os conjuntos
P({x , y , z})
Exerc´ıcio
• Esboc¸ar o diagrama de Hasse de ⊆ em P({x , y , z ,w}).
Relac¸o˜es de ordem
Qualquer relac¸a˜o que tem as mesmas propriedades que a inclusa˜o
tambe´m organiza objetos em n´ıveis.
Definic¸a˜o Seja A um conjunto e R ⊆ A× A. Dizemos que R e´
uma relac¸a˜o de ordem em A se R e´ reflexiva, antissime´trica e
transitiva.
A´lgebra
Proposic¸a˜o Seja R uma relac¸a˜o em A.
• R e´ reflexiva se, e somente se, IA ⊆ R.
• R e´ antissime´trica se, e somente se, R−1 ∩ R ⊆ I .
• R e´ transitiva se, e somente se, R ◦ R ⊆ R.
Principais exemplos
Os principais exemplos sa˜o as ordens nume´ricas.
• ≤ em N
• ≤ em Z
• ≤ em Q
• ≤ em R
• ≤ em C
Voceˆ saberia diferenciar estas ordens?
≤ em N
Definic¸a˜o Seja A um conjunto, R uma relac¸a˜o de ordem em A e
a ∈ A. Dizemos que a e´ um primeiro elemento de A segundo R se
para todo b ∈ A, temos que aRb.
• 0 e´ um primeiro elemento de N segundo ≤.
• Z na˜o possui um primeiro elemento, segundo ≤.
Proposic¸a˜o Se a e b sa˜o primeiros elementos de A segundo R,
enta˜o a = b.
Exerc´ıcio
1. Defina u´ltimo elemento.
2. Mostre que N na˜o tem u´ltimo elemento segundo ≤.
3. Encontre um exemplo de uma ordem que tem u´ltimo
elemento.
≤ em Z
Definic¸a˜o Seja A um conjunto e R uma relac¸a˜o de ordem em A.
Dizemos que R e´ discreta em A se, para todos a, b ∈ A, temos que
{c ∈ A : aRc e cRb} e´ finito.
• ≤ e´ discreta em N e em Z.
• ≤ na˜o e´ discreta em Q.
≤ em Q
Definic¸a˜o Seja A um conjunto e R uma relac¸a˜o de ordem em A.
Dizemos que R e´ densa em A se, para todos a, b ∈ A, se a 6= b,
enta˜o existe c ∈ A tal que c 6= a, c 6= b, aRc e cRb.
Ou seja, para todos a, b ∈ A, se aRb e a 6= b, enta˜o
{c ∈ A : aRc e cRb} e´ infinito.
• ≤ na˜o e´ densa em Z.
• ≤ e´ densa em Q.
≤ em R
Definic¸a˜o Seja A um conjunto, R uma relac¸a˜o de ordem em A e
a ∈ A. Dizemos que a e´ um elemento minimal de A segundo R se
na˜o existe b ∈ A, tal que bRa e b 6= a.
• O aluno a de MD sentado no primeiro degrau ocupado da
escadaria do IME-UFF e´ um elemento minimal.
• No entanto, nem sempre temos um u´nico elemento minimal.
Exerc´ıcio
1. Considere a relac¸a˜o de divisibilidade | em N.
(a) Mostre que | e´ relac¸a˜o de ordem em N.
(b) Mostre que N tem primeiro e u´ltimo elemento segundo |.
(b) Verifique se | e´ densa em N.
2. Considere a relac¸a˜o de divisibilidade | em N− {0, 1}.
(a) Mostre que N− {0, 1} na˜o tem primeiro nem u´ltimo elemento
segundo |.
(b) Identifique os elementos minimais de N− {0, 1} segundo |.
(c) Identifique os elementos maximais de N− {0, 1} segundo |.
≤ em R
Definic¸a˜o Seja A um conjunto, R uma relac¸a˜o de ordem em A,
X ⊆ A e a ∈ A. Dizemos que a e´ um limite inferior de X em A
segundo R se
para todo x ∈ X , temos que aRx .
Definic¸a˜o Seja A um conjunto, R uma relac¸a˜o de ordem em A e
X ⊆ A. Dizemos que X e´ limitado inferiormente em A segundo R
se existe a ∈ A, tal que a e´ um limite inferior de X em A.
• {x ∈ Q : √2 ≤ x} e´ limitado inferiormente em Q segundo ≤.
≤ em R
Definic¸a˜o Seja A um conjunto, R uma relac¸a˜o de ordem em A,
X ⊆ A tal que X 6= ∅, e a ∈ A. Dizemos que a e´ o ı´nfimo de X em
A segundo R se a e´ o u´ltimo elemento do conjunto dos limites
inferiores de X em A segundo R.
Definic¸a˜o Seja A um conjunto e R uma relac¸a˜o de ordem em A.
Dizemos que A e´ completo segundo R se todo subconjunto de A
na˜o vazio limitado inferiormente possui ı´nfimo em A, segundo R.
• {x ∈ Q : √2 ≤ x} na˜o possui ı´nfimo em Q segundo ≤.
Exerc´ıcio
1. Defina elemento maximal.
2. Defina limite superior e conjunto limitado superiormente.
3. Defina supremo.
4. Mostre que, se A e´ completo segundo R, enta˜o todo
subconjunto de A na˜o vazio limitado superiormente possui
supremo em A.
Exerc´ıcios
1. Exerc´ıcios do Menezes
(Paulo B. Menezes, Matema´tica Discreta para Computac¸a˜o e
Informa´tica, 2a. edic¸a˜o, Sagra Luzzatto / Instituto de Informa´tica da
UFRGS, Porto Alegre, 2006).
2. Exerc´ıcios do Scheinerman
(E.R. Scheinerman, Matema´tica Discreta, Thomson, Sa˜o Paulo, 2006).
3. Exerc´ıcios da Lista 14.