T.7 · Imagens de conjuntos, relações de equivalência e negação lógica

Preparação de graduação para o GRE. Objetivos locais dentro do escopo revisado do ETS; este é ensino original, não um teste oficial ou preditor de nota.

Pré-requisitos: Operações de conjuntos, quantificadores, funções e prova elementar.

• Prove identidades de imagem e distinga inclusão estrita de igualdade
• Verifique reflexividade, simetria e transitividade com casos explícitos
• Negue implicações e afirmações quantificadas sem alterar seu escopo

pré-imagem: O conjunto de entradas cujas saídas pertencem a um conjunto-alvo especificado.

relação de equivalência: Uma relação que é reflexiva, simétrica e transitiva.

Para f:X→Y e A⊆X, a imagem f(A) consiste em todas as saídas f(a) com a em A. Um ponto pertence a f(A∪B) exatamente quando vem de A ou B, logo f(A∪B)=f(A)∪f(B). Se A⊆B, então f(A)⊆f(B). Para interseção apenas, f(A∩B)⊆f(A)∩f(B) é automático: a mesma saída pode vir de entradas diferentes. Use f(x)=x², A={−1}, B={1}; a imagem à esquerda é vazia enquanto a interseção à direita é {1}.

Pré-imagens comportam-se diferentemente. Para C⊆Y, f⁻¹(C) denota aqui o conjunto de todas as entradas enviadas para C, mesmo se f não tiver função inversa. Pertença a duas pré-imagens significa a mesma entrada mapeia para ambos os conjuntos-alvo. Consequentemente, pré-imagens preservam uniões, interseções e complementos relativos ao domínio/codomínio declarado. Não transfira teoremas sobre pré-imagens para imagens. Se f for injetora, interseções de imagem tornam-se iguais, pois saídas iguais forçam entrada comum.

Uma relação R em X é reflexiva quando xRx para todo x, simétrica quando xRy implica yRx, e transitiva quando xRy e yRz implicam xRz. As três formam uma relação de equivalência; suas classes particionam X. Nos inteiros, xRy quando x e y têm o mesmo resto módulo quatro dá quatro classes. A relação |x−y|≤1 é reflexiva e simétrica, mas não transitiva: 0R1 e 1R2 enquanto 0 não está relacionado a 2. Verificar apenas um diagrama ou duas propriedades é insuficiente.

Uma implicação P⇒Q é falsa exatamente quando P é verdadeira e Q falsa. Logo, a negação de P⇒(Q∧R) é P∧(¬Q∨¬R), não ¬P⇒(¬Q∧¬R). Negar “todo x tem propriedade A” resulta em “existe x sem A”; negar “existe x” resulta em “todo x não”. Um contraexemplo pode refutar uma afirmação universal, enquanto exemplos não podem prová-la. Os quantificadores mantêm sua ordem ao serem negados individualmente: ¬(∀x∃y S(x,y)) é ∃x∀y ¬S(x,y).

Seja f mapeando tanto a quanto b para o rótulo L. Com A={a} e B={b}, f(A∩B)=∅, mas f(A)∩f(B)={L}. Para xRy definido por x=y ou x=−y em ℝ, a reflexividade e simetria seguem diretamente, e duas trocas de sinal ainda resultam em z=±x, provando a transitividade. As classes são {x,−x}, com {0} sendo um conjunto unitário. Um enunciado falso “todo arquivo armazenado tem um hash” significa que pelo menos um arquivo armazenado não tem hash; não significa que todos os arquivos carecem de hashes.

f⁻¹(C) pode significar um conjunto pré-imagem sem uma função inversa. Uma relação reflexiva e simétrica ainda pode falhar na transitividade. Negue a declaração inteira antes de simplificar suas partes.

Prove $f(A\cap B)\subseteq f(A)\cap f(B)$. Dê um exemplo de inclusão estrita. Sob qual suposição adicional em f a igualdade segue para todos A e B?

Solução resolvida

Se $y=f(x)$ para $x\in A\cap B$, então x pertence a cada conjunto, logo y pertence a cada imagem. Para rigor, mapeie distintos a,b para o mesmo c e tome $A=\{a\}$, $B=\{b\}$. A imagem à esquerda é vazia e a interseção à direita é $\{c\}$. Se f for injetora e $y=f(a)=f(b)$ com $a\in A,b\in B$, a injetividade garante a=b na interseção, provando inclusão reversa. Por outro lado, o exemplo do singleton mostra que a igualdade para todos os pares força a injetividade.

Nos inteiros, defina $aRb$ quando $a-b$ é divisível por 4. Prove que é uma relação de equivalência e descreva cada classe. Negue: “Para todo inteiro n existe um inteiro m maior que n com propriedade P.”

Verificar após tentar

Reflexividade usa $a-a=0$; simetria usa o negativo de um múltiplo de quatro; transitividade usa a soma de dois tais múltiplos. As classes são os quatro resíduos módulo quatro; a classe de a é $a+4\mathbb Z$. A negação é: existe um inteiro n tal que todo inteiro m maior que n falha P. Equivalentemente $\exists n\,\forall m\,(m>n\Rightarrow\neg P(m))$. Não afirma que P falha para todo inteiro, nem que m é no máximo n para cada m.