T.7 · Imágenes de conjuntos, relaciones de equivalencia y negación lógica

Preparación de GRE para grado universitario. Objetivos locales dentro del alcance revisado de ETS; esto es enseñanza original, no una prueba oficial ni un predictor de puntuación.

Requisitos previos: Operaciones con conjuntos, cuantificadores, funciones y demostraciones elementales.

• Demostrar identidades de imagen y distinguir inclusión de igualdad
• Verificar reflexividad, simetría y transitividad con casos explícitos
• Negar implicaciones y enunciados cuantificados sin cambiar su alcance

imagen inversa: El conjunto de entradas cuyas salidas pertenecen a un conjunto objetivo especificado.

relación de equivalencia: Una relación que es reflexiva, simétrica y transitiva.

Para f:X→Y y A⊆X, la imagen f(A) consiste en todas las salidas f(a) con a en A. Un punto está en f(A∪B) exactamente cuando proviene de A o de B, por lo que f(A∪B)=f(A)∪f(B). Si A⊆B, entonces f(A)⊆f(B). Para una intersección solo f(A∩B)⊆f(A)∩f(B) es automático: la misma salida puede provenir de diferentes entradas. Use f(x)=x², A={−1}, B={1}; la imagen izquierda está vacía mientras que la intersección derecha es {1}.

Las preimágenes se comportan de manera diferente. Para C⊆Y, f⁻¹(C) denota aquí el conjunto de todas las entradas enviadas a C, incluso si f no tiene función inversa. La pertenencia a dos preimágenes significa que la misma entrada mapea hacia ambos conjuntos objetivo. En consecuencia, las preimágenes preservan uniones, intersecciones y complementos respecto al dominio/codominio indicado. No transfiera un teorema sobre preimágenes a imágenes. Si f es inyectiva, las intersecciones de imágenes se vuelven iguales, porque las salidas iguales obligan a una entrada compartida.

Una relación R en X es reflexiva cuando xRx para todo x, simétrica cuando xRy implica yRx, y transitiva cuando xRy e yRz implican xRz. Las tres constituyen una relación de equivalencia; sus clases particionan X. En los enteros, xRy cuando x e y tienen el mismo residuo módulo cuatro da lugar a cuatro clases. La relación |x−y|≤1 es reflexiva y simétrica pero no transitiva: 0R1 y 1R2 mientras que 0 no está relacionado con 2. Revisar solo un diagrama o verificar solo dos propiedades es insuficiente.

Una implicación P⇒Q es falsa exactamente cuando P es verdadera y Q falsa. Así, la negación de P⇒(Q∧R) es P∧(¬Q∨¬R), no ¬P⇒(¬Q∧¬R). Negar “todo x tiene la propiedad A” da “existe x sin A”; negar “existe x” da “todo x no”. Un contraejemplo puede refutar una afirmación universal, mientras que ejemplos no pueden probarla. Los cuantificadores retienen su orden al ser negados individualmente: ¬(∀xy S(x,y)) es ∃x∀y ¬S(x,y).

Sea f que mapea tanto a como b a la etiqueta L. Con A={a}, B={b}, f(A∩B)=∅ pero f(A)∩f(B)={L}. Para xRy definido por x=y o x=−y en ℝ, la reflexividad y la simetría se derivan directamente, y dos cambios de signo aún dan z=±x, probando la transitividad. Las clases son {x,−x}, con {0} como un singleton. Un enunciado falso “todo archivo almacenado tiene un hash” significa que al menos un archivo almacenado no tiene hash; no significa que todos los archivos carezcan de hashes.

f⁻¹(C) puede significar un conjunto preimagen sin función inversa. Una relación reflexiva y simétrica aún puede fallar en la transitividad. Niegue el enunciado completo antes de simplificar sus partes.

Demuestre $f(A\cap B)\subseteq f(A)\cap f(B)$. Proporcione un ejemplo de inclusión estricta. ¿Bajo qué suposición adicional sobre f se sigue la igualdad para toda A y B?

Solución resuelta

Si $y=f(x)$ para $x\in A\cap B$, entonces x pertenece a cada conjunto, por lo que y pertenece a cada imagen. Para la estrictez, mapee a distintos a,b al mismo c y tome $A=\{a\}$, $B=\{b\}$. La imagen izquierda está vacía y la intersección derecha es $\{c\}$. Si f es inyectiva y $y=f(a)=f(b)$ con $a\in A,b\in B$, la inyectividad garantiza a=b en la intersección, probando la inclusión recíproca. Por el contrario, el ejemplo del singleton muestra que la igualdad para todos los pares fuerza la inyectividad.

En los enteros defina $aRb$ cuando $a-b$ es divisible por 4. Demuestre que es una relación de equivalencia y describa cada clase. Niegue: “Para todo entero n existe un entero m mayor que n con la propiedad P.”

Verificar después de intentar

La reflexividad usa $a-a=0$; la simetría usa el negativo de un múltiplo de cuatro; la transitividad usa la suma de dos tales múltiplos. Las clases son los cuatro residuos módulo cuatro; la clase de a es $a+4\mathbb Z$. La negación es: existe un entero n tal que todo entero m mayor que n no cumple P. Equivalente a $\exists n\,\forall m\,(m>n\Rightarrow\neg P(m))$. No afirma que P falle para todo entero, ni que m sea como máximo n para todo m.