Sol_L7D131

Prévia do material em texto

MAT 01375 – Matema´tica Discreta B 2013/1
Lista de Exerc´ıcios 7
Soluc¸o˜es de Exerc´ıcios Escolhidos
Questo˜es 1 e 2.
(a) A relac¸a˜o e´ uma ordem parcial. Suponha que os elementos do conjunto sejam
a, b, c, d, cuja ordem respeita as linhas e colunas da matriz. Na˜o e´ ordem total,
pois b e c na˜o sa˜o compara´veis, por exemplo.
(b) Suponha que os elementos do conjunto sejam a, b, c, d, cuja ordem respeita
as linhas e colunas da matriz. A relac¸a˜o na˜o e´ ordem parcial, pois na˜o satisfaz
transitividade. Note que a � b e b � d, mas a 6� d.
(c) Suponha que os elementos do conjunto sejam a, b, c, cuja ordem respeita as
linhas e colunas da matriz. A relac¸a˜o na˜o e´ ordem parcial, pois na˜o satisfaz
antissimetria. Note que a � c e c � a, apesar de que a 6= c.
(d) A relac¸a˜o R1 e´ uma ordem parcial, mas na˜o possui Diagrama de Hasse.
Tambe´m na˜o e´ uma ordem total, pois as func¸o˜es f(x) = x e g(x) = 1 − x sa˜o
elementos de S(R) tais que f na˜o se relaciona com g, ja´ que f(1) = 1 > g(1) = 0
e g na˜o se relaciona com f , ja´ que g(0) = 1 > f(0) = 0.
Reflexividade: Dada f ∈ S(R), temos (∀x ∈ [0, 1])[f(x) ≤ f(x)], de forma que
fR1f .
Antissimetria: Sejam f, g ∈ S(R) tais que fR1g e gR1f . Essas condic¸o˜es impli-
cam, respectivamente, (∀x ∈ [0, 1])[f(x) ≤ g(x)] e (∀x ∈ [0, 1])[g(x) ≤ f(x)]. Em
particular, f(x) = g(x) para todo x ∈ [0, 1], de forma que f = g.
Transitividade: Sejam f, g, h ∈ S(R) tais que fR1g e gR1h. Essas condic¸o˜es
implicam, respectivamente, (∀x ∈ [0, 1])[f(x) ≤ g(x)] e (∀x ∈ [0, 1])[g(x) ≤ h(x)].
Pela transitividade da ordem usual, temos que (∀x ∈ [0, 1])[f(x) ≤ h(x)], de forma
que fR1h.
(e) A relac¸a˜o R1 na˜o e´ antissime´trica, pois 00R101 e 01R100, logo na˜o e´ relac¸a˜o
de ordem.
(g) A relac¸a˜o R1 na˜o e´ antissime´trica, pois {2}R1{1, 2} e {1, 2}R1{2}, logo na˜o e´
relac¸a˜o de ordem.
(h) A relac¸a˜o R2 e´ uma relac¸a˜o de ordem, como demonstrado abaixo.
Reflexividade: Seja C ∈ B. Como C = C, temos CR2C pela definic¸a˜o de R1.
Antissimetria: Sejam C,D ∈ B tais que CR2D e DR2C. Suponha por absurdo
que C 6= D. Logo, CR2D implica que x = max{i : i ∈ (C −D) ∪ (D − C)} ∈ D,
enquanto que DR2C implica que y = max{i : i ∈ (D−C)∪ (C −D)} ∈ C. Como
(C −D) ∪ (D − C) = (D − C) ∪ (C −D) conclu´ımos que x = y ∈ C ∩D. Isso e´
absurdo, ja´ que leva a` conclusa˜o de que x /∈ (D−C)∪ (C−D) = C∪D− (C∩D).
Transitividade: Sejam C,D,E ∈ B tais que CR2D e DR2E. Se C = D ou
D = E, e´ claro que CR2E, portanto suponha que esse na˜o e´ o caso. Note que
C 6= E, caso contra´rio ter´ıamos C = D por antissimetria. Como CR2D, segue
que x = max{i : i ∈ (C − D) ∪ (D − C)} ∈ D e, como DR2E, segue que y =
max{i : i ∈ (D − E) ∪ (E −D)} ∈ E.
Seja z = max{i : i ∈ (C − E) ∪ (E − C)}, que esta´ bem definido pois C 6= E.
Por absurdo, suponha que z ∈ C. Consideraremos, separadamente, os casos x < y
e y < x (note que x 6= y, ja´ que x ∈ D e y /∈ D).
Suponha que x < y. Por um lado, se z ∈ D, enta˜o z < y pela definic¸a˜o de y
(pois sabemos que z /∈ E). A maximalidade de z implica que y ∈ C (pois sabemos
que y ∈ E), e portanto y ∈ C − D, contradizendo a definic¸a˜o de x. Por outro
lado, se z /∈ D, enta˜o z < x pela definic¸a˜o de x, logo z < y e novamente chegamos
a uma contradic¸a˜o pelas considerac¸o˜es anteriores.
Suponha agora que y < x. Por um lado, se z /∈ D, enta˜o z < x pela definic¸a˜o
de x (pois sabemos que z ∈ C). A maximalidade de z implica que x /∈ E (pois
sabemos que x /∈ C), e portanto x ∈ D − E, contradizendo a definic¸a˜o de y. Por
outro lado, se z ∈ D, enta˜o z < y pela definic¸a˜o de y, logo z < x e novamente
chegamos a uma contradic¸a˜o pelas considerac¸o˜es anteriores.
Portanto, temos que z ∈ E, de forma que CR2E, como quer´ıamos demonstrar.
Para concluir, provaremos que a ordem e´ total. De fato, dados C,D ∈ B, e´
claro que C e D se relacionam se C = D, portanto suponha que sa˜o distintos.
Nesse caso, o conjunto (C −D) ∪ (D − C) e´ na˜o-vazio, e como e´ limitado, possui
elemento ma´ximo. Se esse elemento estiver em D, temos CR2D, caso contra´rio
estara´ em C e DR2C.
5. (Parcial) A relac¸a˜o R2 na˜o e´ relac¸a˜o de ordem parcial porque na˜o e´ antis-
sime´trica. De fato, os nu´meros 2 e 4 teˆm os mesmos divisores primos (a saber, o
nu´mero 2), e portanto 2R24 e 4R22. Para que a relac¸a˜o R3 seja relac¸a˜o de ordem
parcial o enunciado deveria ser xR3y
se {p primo: p|x} ( {p primo: p|y} ou se {p primo: p|x} = {p primo: p|y} e x ≥ y.
Note que a definic¸a˜o de R3 leva a conclusa˜o de que xR3y =⇒ {p primo: p|x} ⊆
{p primo: p|y}.
Reflexividade: Dado x ∈ {2, 3, 4, · · · }, temos {p primo: p|x} = {p primo: p|x}
e x ≥ x de forma que xR3x.
Antissimetria: Sejam x, y ∈ {2, 3, 4, · · · } tais que xR3y e yR3x. Essas condic¸o˜es
implicam {p primo: p|x} ⊆ {p primo: p|y} e {p primo: p|y} ⊆ {p primo: p|x},
respectivamente, de forma que {p primo: p|x} = {p primo: p|y} pela antissimetria
da ordem ⊆ em conjuntos. Pela definic¸a˜o de R3, temos enta˜o x ≥ y e y ≥ x, o
que nos leva a x = y, como quer´ıamos demonstrar.
Transitividade: Sejam x, y, z ∈ {2, 3, 4, · · · } tais que xR3y e yR3z. Essas
condic¸o˜es implicam {p primo: p|x} ⊆ {p primo: p|y} ⊆ {p primo: p|z}, de forma
que teremos xR3z se {p primo: p|x} ( {p primo: p|y} ou se {p primo: p|y} (
{p primo: p|z}. Suponha enta˜o que {p primo: p|x} = {p primo: p|y} = {p primo: p|z}.
Por definic¸a˜o de R3, temos x ≥ y e y ≥ z, e portanto xR3z segue da transitividade
da ordem usual.
6.
(a) Para provar a ida, suponhamos inicialmente que vale a propriedade
(x ≺R y) ∧ (∀z ∈ A)[x �R z ∧ z �R y → z ∈ {x, y}].
Queremos provar que (∀z ∈ A)[x ≺R z ∧ z �R y → z = y]. Seja z ∈ A tal que
x ≺R z ∧ z �R y. Em outras palavras, temos (x 6= z) ∧ (x �R z ∧ z �R y). Por
hipo´tese, isso implica (x 6= z) ∧ (x ≺R y) ∧ ∧(z ∈ {x, y}), de forma que z = y,
como desejado.
Para provar a volta, suponhamos que
(x ≺R y) ∧ (∀z ∈ A)[x ≺R z ∧ z �R y → z = y].
Queremos provar que (∀z ∈ A)[x �R z ∧ z �R y → z ∈ {x, y}]. Seja z ∈ A tal
que x �R z ∧ z �R y. Logo, temos (x = z ∧ z �R y) ∨ (x ≺R z ∧ z �R y), o que
implica (x = z)∨ (z = y) = z ∈ {x, y}. (O primeiro pedac¸o da implicac¸a˜o vem do
fato de que x ≺ y, e logo x 6= y, e o segundo vem da segunda parte da hipo´tese.)
(b) O enunciado esta´ incorreto. A ordem a ser utilizada e´ R3 (R2 na˜o e´ or-
dem). Seja n ∈ {2, 3, 4, . . .} e seja n = pe11 · · · pe`` a sua fatorac¸a˜o em primos com
p1, . . . , p` distintos e e1, . . . , e` ≥ 1. Para cada j ∈ {1, . . . , `}, seja mj = npj
e defina m = min{mj : j ∈ {1, . . . , `}}. Por definic¸a˜o, temos mR3n e m 6= n.
Considere agora um elemento arbitra´rio t tal que tR3n e t 6= n. Para obter o
nosso resultado, basta mostrar que tR3m. Note que essa conclusa˜o e´ imediata se
{p primo: p|t} ( {p primo: p|n}, pois {p primo: p|n} = {p primo: p|m}. Supo-
nha enta˜o que {p primo: p|t} = {p primo: p|n}, de forma que t > n pela definic¸a˜o
de R3. Como os fatores primos de t e de n sa˜o os mesmos, conclu´ımos que t pode
ser escrito como t = apn, onde a ≥ 1 e p ∈ {p1, . . . , p`}, de forma que t ≥ m pela
minimalidade de m. Isso implica que tR3m, como quer´ıamos demonstrar.
(c) Ha´ um problema com o enunciado. Deveria ser: “Um inteiro n ≥ 2 e´ o
produto de primos distintos se e somente se n na˜o possui sucessor imediato com
relac¸a˜o a R3.”
Vamos demonstrar esse fato. Suponhamos inicialmente que n = p1 · p`, onde
os primos pi sa˜o distintos, e queremos mostrar que n na˜o tem sucessor imediato.
Mostraremos que nenhuma cota superior de n e´ um sucessor imediato, o que
implica o resultado desejado. Seja m uma cota superior para n, m 6= n. Note que
{p primo: p|n} ( {p primo: p|m}, pois n e´ o maior dos elementos de {2, 3, 4, . . .}
com respeito a R3 para o qual o conjunto de divisores primos e´ {p1, . . . , p`}. Seja
q um fator primo de m tal que q na˜o divide m. Por definic¸a˜o, para m′ = qm,
temos nR3m
′ e m′R3m, como quer´ıamos demonstrar.
Para provar a outra direc¸a˜o, utilizaremos contraposic¸a˜o e provaremos que, se
existe um primo q tal que q2 divide n, enta˜o n possui um sucessor imediato. De
fato,sejam p1, . . . , p` os fatores primos distintos de n cuja multiplicidade em n
seja pelo menos dois. Seja m = max{n/pi : i ∈ {1, 2, . . . , `}}. Mostraremos que
m e´ o u´nico sucessor imediato de n. Como m < n e os seus conjuntos de fatores
primos sa˜o ideˆnticos, temos que nR3m. Seja t uma cota superior qualquer de m.
Se {p primo: p|n} ( {p primo: p|t}, teremos mR3t, como desejado. Suponhamos
enta˜o que {p primo: p|n} = {p primo: p|t}, de forma que t < n pela definic¸a˜o de
R3. Essas duas informac¸o˜es, combinadas a` definic¸a˜o de m, implicam que t ≤ m,
e portanto mR3t, como quer´ıamos demonstrar.
7.
(a) Na˜o, pois o conjunto na˜o-vazio Z na˜o tem elemento mı´nimo.
(b) Sim. Considere a relac¸a˜o definida por x � y se |x| < |y| ou se |x| = |y| e
x ≤ y. Inicialmente, provaremos que � e´ uma ordem. Observe que essa tem
por consequeˆncia x � y =⇒ |x| ≤ |y|.
Reflexividade: Dado x ∈ Z, temos |x| = |x|, e x ≤ x de forma que x � x.
Antissimetria: Sejam x, y ∈ Z tais que x � y e y � x. Essas condic¸o˜es
implicam |x| ≤ |y| e |y| ≤ |x|, respectivamente, de forma que |x| = |y| pela
antissimetria da ordem usual. Pela definic¸a˜o de �, temos enta˜o x ≤ y e
y ≤ x, o que nos leva a x = y, como quer´ıamos demonstrar.
Transitividade: Sejam x, y, z ∈ Z tais que x � y e y � z. Essas condic¸o˜es
implicam |x| ≤ |y| ≤ |z|, de forma que teremos x � z se |x| < |y| ou se
|y| < |z|. Suponha enta˜o que |x| = |y| = |z|. Por definic¸a˜o de �, temos x ≤ y
e y ≤ z, e portanto x � z segue da transitividade da ordem usual.
Para concluir, provaremos que � e´ uma boa ordem. Seja S ⊆ Z, S 6= ∅.
Portanto, o conjunto T = {|x| : x ∈ S} ⊆ N tambe´m e´ na˜o-vazio. Como
a ordem usual e´ uma boa ordem para os naturais, o conjunto T tem um
elemento mı´nimo y. Se −y ∈ S, enta˜o esse sera´ elemento mı´nimo de S com
respeito a � (ja´ que −y � y). Se −y /∈ S, enta˜o y ∈ S (caso contra´rio y /∈ T )
e esse sera´ o elemento mı´nimo de T com respeito a �.
(c) Seja � uma boa ordem em um conjunto S. Temos que mostrar que � e´ uma
ordem total, isto e´, quaisquer x, y ∈ S sa˜o compara´veis. Considere o conjunto
C = {x, y}. Como � e´ uma boa ordem, possui um elemento mı´nimo. Se esse
elemento for x, enta˜o x � y, caso contra´rio y � x, e o resultado segue.