Sejam X e Y conjuntos e rho, sigma relações binárias de X em Y. Mostre que são equivalentes:
(i)Se a rho b, então a sigma b;
(ii) rho subset sigma;
(iii) rho cup sigma=sigma;
(iv) rho cap sigma=rho;
(v) rho cap[(X times Y)-sigma]=emptyset;
(vi) [(X times Y)-sigma] subset[(X times Y)-rho].

Passo 1

O enunciado fala de duas relações binárias rho e sigma de X em Y, ou seja, rhosubset Xtimes Y e sigmasubset Xtimes Y. Queremos mostrar que as seis afirmações abaixo são logicamente equivalentes, usando a teoria de inclusão, união, interseção e complemento de conjuntos:
(i) Se a,rho,b, então a,sigma,b.
(ii) rhosubsetsigma.
(iii) rhocupsigma=sigma.
(iv) rhocapsigma=rho.
(v) rhocapl[(Xtimes Y)-sigmar]=emptyset.
(vi) ,(Xtimes Y)-sigmasubset (Xtimes Y)-rho.

Passo 2

Mostramos que (i) e (ii) são a mesma coisa:
“Se a,rho,b então a,sigma,b” significa exatamente que todo par de rho está também em sigma. Por definição de subconjunto, isto é
l(forall (a,b)l[(a,b)inrhoimplies (a,b)insigmar]r) Long<=ftrightarrow rhosubsetsigma
Logo, (i) iff(ii).

Passo 3

Usamos agora propriedades de inclusão com união e interseção:
  • Para quaisquer conjuntos A,B, vale Asubset Biff Acup B = B Aplicando com A=rho e B=sigma, segue
    rhosubsetsigmaiff rhocupsigma=sigma, ou seja, (ii) iff(iii).
  • Também vale Asubset Biff Acap B = A Logo, rhosubsetsigmaiff rhocapsigma=rho, isto é, (ii) iff(iv).

Passo 4

Agora usemos o complemento em relação ao universo Xtimes Y. Para quaisquer A,Bsubset Xtimes Y temos
Asubset Biff Acapl[(Xtimes Y)-Br]=emptyset
Com A=rho e B=sigma segue
rhosubsetsigmaiff rhocapl[(Xtimes Y)-sigmar]=emptyset, ou seja, (ii) iff(v).

Passo 5

Por fim, outra forma de expressar inclusão via complemento é
Asubset Biff (Xtimes Y)-B ;subset; (Xtimes Y)-A
Com A=rho e B=sigma obtemos
(Xtimes Y)-sigmasubset (Xtimes Y)-rhoiff rhosubsetsigma, ou seja, (ii) iff(vi).

Resposta

As seis condições (i)–(vi) são equivalentes.

Exercícios relacionados