Imágenes de conjuntos, relaciones de equivalencia y negación lógica
Introducido| English | Significado |
|---|---|
| preimage/ˌpriːˈɪmɪdʒ/ | Preimagen |
| equivalence relation/ɪˈkwɪvələns rɪˈleɪʃn/ | Relación de equivalencia |
| negation/nɪˈɡeɪʃn/ | Negación |
Dos registros, una etiqueta
- Una función hash envía archivos distintos $a$ y $b$ a la misma etiqueta $L$. Con $A=\{a\}$ y $B=\{b\}$, la imagen de $A\cap B$ es vacía, pero $f(A)\cap f(B)=\{L\}$.
- La misma etiqueta no necesariamente significa la misma entrada. Esta distinción conecta preimágenes, relaciones de equivalencia y negación lógica.
Enunciar los dos universos
- Fijar $f:X\to Y$. Para $A\subseteq X$, su imagen es $f(A)=\{f(x):x\in A\}$. Para $C\subseteq Y$, su preimagen es $f^{-1}(C)=\{x\in X:f(x)\in C\}$.
- El símbolo $f^{-1}(C)$ describe un conjunto de entradas, incluso cuando $f$ no tiene función inversa. Los complementos deben nombrar su universo: $X\setminus A$ y $Y\setminus C$ viven en conjuntos diferentes.
Por qué las imágenes preservan uniones
- Si $y\in f(A\cup B)$, alguna entrada $x\in A\cup B$ mapea a $y$. Esa entrada pertenece a $A$ o a $B$, por lo tanto $y\in f(A)\cup f(B)$.
- Por el contrario, la pertenencia a cualquiera de las imágenes proporciona una entrada en $A\cup B$. Las dos inclusiones demuestran $f(A\cup B)=f(A)\cup f(B)$, sin ninguna suposición de inyectividad.
Intersecciones: ¿una entrada o dos?
- Si $y\in f(A\cap B)$, una entrada pertenece a ambos conjuntos y se mapea a $y$. Así $f(A\cap B)\subseteq f(A)\cap f(B)$. En la dirección inversa, las dos entradas pueden diferir: elevar al cuadrado envía tanto $-1$ como $1$ a $1$.
- Si $f$ es inyectiva, salidas iguales obligan a que esas entradas coincidan, dando igualdad. La igualdad para todo par $A,B$ también fuerza la inyectividad: una colisión da singulares disjuntos con imágenes superpuestas. La igualdad para un solo par, como $A=B$, no demuestra nada sobre la inyectividad.
For every function $f$ and sets $A, B$ in its domain, which always holds?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Union equality holds for every map. The other equalities/inclusion become valid for every pair under injectivity, but can fail for a map with a collision. A particular pair can still give equality without injectivity.
Let $a,b$ be distinct and $f(a)=f(b)=L$. For $A=\{a\}$ y $B=\{b\}$, what are $f(A\cap B)$ y $f(A)\cap f(B)$?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
The input intersection is empty, but both image sets contain L.
Diferencias y complementos pueden fallar
- Siempre $f(A)\setminus f(B)\subseteq f(A\setminus B)$: una salida ausente de $f(B)$ no tiene entrada en $B$. La implicación inversa puede fallar. Si $f(a)=f(b)=L$, entonces $A=\{a\}$ y $B=\{b\}$ dan $\{L\}$ a la derecha pero el conjunto vacío a la izquierda.
- Let $X=\{a,b,c\}$, $Y=\{L,M,N\}$, with $a,b\mapsto L$ and $c\mapsto M$. For $A=\{a\}$, the image of $X\setminus A$ is $\{L,M\}$, whereas $Y\setminus f(A)=\{M,N\}$. Preserving complements relative to all of $Y$, for every $A$, requires a bijection.
Prove that images preserve unions and give intersection inclusion. Then use a collision to disprove image-difference equality.
Compare los cuantificadores, universos de conjuntos y testigos explícitos en su razonamiento.
Preimágenes preservan operaciones de conjuntos
- Para $C,D\subseteq Y$, una entrada se mapea dentro de $C\cup D$ exactamente cuando se mapea dentro de al menos un conjunto. Se mapea dentro de $C\cap D$ exactamente cuando se mapea dentro de ambos. Por lo tanto, las preimágenes preservan tanto uniones como intersecciones.
- También $f^{-1}(Y\setminus C)=X\setminus f^{-1}(C)$: ambos lados contienen exactamente las entradas cuyas salidas están fuera de $C$. Ninguna de estas identidades necesita inyectividad ni sobreyectividad.
$f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D)$ for every function $f$.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
An input maps into C ∩ D exactly when it maps into both C and D; injectivity is unnecessary.
Ir hacia afuera y volver
- La identidad $f(f^{-1}(C))=C\cap f(X)$ retiene solo las salidas alcanzables. En el mapa finito anterior, $C=\{L,N\}$ tiene preimagen $\{a,b\}$ e imagen-de-preimagen $\{L\}$: la salida faltante $N$ no puede aparecer.
- Siempre $A\subseteq f^{-1}(f(A))$. Este viaje de ida y vuelta añade cada entrada que comparte una salida con $A$. Para $A=\{a\}$ da $\{a,b\}$. La igualdad para todo $A$ se cumple exactamente cuando $f$ es inyectiva.
¿Válido para todo mapa?
Distinguir identidades universales de afirmaciones que requieren hipótesis adicionales.
A favor $f(x)=x^2$ on $\mathbb R$ y $A=\{-2\}$, how many elements belong to $f^{-1}(f(A))$?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
f(A)={4}, whose preimage is {-2,2}. The round trip can add inputs.
Let $X=\{a,b,c\}$, $Y=\{L,M,N\}$, $f(a)=f(b)=L$, $f(c)=M$, and $C=\{L,N\}$. Find $f(f^{-1}(C))$.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Only L is in both C and the image {L,M}. No input maps to N.
Use $a,b\mapsto L$, $c\mapsto M$ from $X=\{a,b,c\}$ hasta $Y=\{L,M,N\}$. For $A=\{a\}$ y $C=\{L,N\}$, find $f^{-1}(f(A))$, $f(f^{-1}(C))$, and $f^{-1}(Y\setminus C)$. Explain each change.
Compare los cuantificadores, universos de conjuntos y testigos explícitos en su razonamiento.
Tres propiedades de relación
- A relation on a set $S$ is reflexive if $x\sim x$ for every $x\in S$, and symmetric if $x\sim y$ implies $y\sim x$ for every pair. A single failing element or pair disproves the corresponding property.
- La transitividad requiere que $x\sim y$ y $y\sim z$ impliquen $x\sim z$ para cada tríada. Una relación de equivalencia tiene las tres propiedades. Siempre declare $S$: cambiar los elementos permitidos puede cambiar la respuesta.
Por qué las clases de equivalencia particionan un conjunto
- Defina $[x]=\{y\in S:y\sim x\}$. La reflexividad coloca $x$ en $[x]$, por lo que las clases cubren $S$. Cada clase es no vacía.
- Si $z\in[x]\cap[y]$, la simetría y la transitividad dan $x\sim y$. Cualquier $w\sim x$ entonces también satisface $w\sim y$, así que $[x]\subseteq[y]$; invertir los roles da igualdad. Las clases distintas son por lo tanto disjuntas: juntas forman una partición.
Los residuos dan clases completas
- En $\mathbb Z$, sea $x\sim y$ que $4$ divide a $x-y$. La reflexividad sigue de $x-x=0$; la simetría del cambio de signo; la transitividad de sumar dos diferencias divisibles por $4$.
- Las cuatro clases son $[0],[1],[2],[3]$, con $[r]=\{r+4k:k\in\mathbb Z\}$. Los enteros negativos también pertenecen: $-1\in[3]$. Reemplazar $4$ por $6$ da exactamente seis clases, ya que todo entero tiene un residuo de $0$ a $5$.
How many equivalence classes does “same remainder mod 6” have on $\mathbb Z$?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Two integers are related when they leave the same remainder on division by 6. The possible remainders 0, 1, …, 5 give exactly 6 classes.
Cuadrados iguales, clase igual
- En $\mathbb R$, $x\sim y$ cuando $x=\pm y$, equivalentemente $x^2=y^2$. La igualdad de estas salidas es reflexiva, simétrica y transitiva, por lo tanto esta es una relación de equivalencia.
- Para $x\ne0$, la clase es $\{x,-x\}$; la clase de cero es solo $\{0\}$. Más generalmente, cualquier función agrupa entradas en clases de equivalencia por salida igual, independientemente de si esa función es inyectiva o no.
Encuentre la propiedad que falla
- En $\mathbb R$, $|x-y|\le1$ falla transitividad usando $0,1,2$. En $\mathbb Z$, diferencia impar falla reflexividad porque $x-x=0$; también falla transitividad usando $1,2,3$. Ambas relaciones son simétricas.
- La relación $x\le y$ sobre $\mathbb R$ falla simetría usando $0,1$. La relación $xy>0$ sobre $\mathbb R\setminus\{0\}$ es por equivalencia de signo, pero sobre todo el conjunto de $\mathbb R$ falla reflexividad en cero. El universo forma parte de la pregunta.
¿Relación de equivalencia?
Verificar reflexividad, simetría y transitividad conjuntamente.
Activado $\mathbb Z$, the relation “$x - y$ is odd” is
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
It fails reflexivity because x − x = 0 is even. It is symmetric (x − y odd ⇒ y − x odd) but not transitive: 1 − 2 and 2 − 3 are odd, yet 1 − 3 is even.
The relation $xy>0$ is an equivalence relation on all of $\mathbb R$.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
At x=0, x² is not positive, so reflexivity fails. Removing zero gives an equivalence relation with two sign classes.
Prove that $6\mid(x-y)$ defines an equivalence relation on $\mathbb Z$ and describe its classes. Explain why replacing “divisible by 6” by “odd” fails.
Compare los cuantificadores, universos de conjuntos y testigos explícitos en su razonamiento.
Implicación y su contrapositiva
- $P\Rightarrow Q$ es falso exactamente cuando $P$ es verdadero y $Q$ es falso. Si $P$ es falso, la implicación es verdadera. Por ejemplo, “si $3$ es divisible por $4$, entonces $3$ es par” tiene una premisa falsa y es una implicación verdadera.
- La contrapositiva $\neg Q\Rightarrow\neg P$ tiene el mismo valor de verdad que $P\Rightarrow Q$. La conversión $Q\Rightarrow P$ no necesariamente: la divisibilidad por $4$ implica paridad para los enteros, pero el número par $2$ no es divisible por $4$.
$P \Rightarrow Q$ is false only when $P$ is true and $Q$ is ____.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Truth table of implication.
Negar toda la afirmación
- Negar una implicación da como resultado $\neg(P\Rightarrow Q)\equiv P\wedge\neg Q$. Las leyes de De Morgan intercambian “y” por “o”: por ejemplo, $\neg(Q\wedge R)\equiv\neg Q\vee\neg R$.
- Combinando las reglas, la negación de $P\Rightarrow(Q\wedge R)$ es $P\wedge(\neg Q\vee\neg R)$. La premisa debe cumplirse, y al menos una conclusión prometida debe fallar. La “o” incluye la posibilidad de que ambas conclusiones fallen.
El orden del cuantificador controla la afirmación
- En $\mathbb R$, “para cada $x$ existe un $y>x$” es verdadero: elija $y=x+1$. “Existe un $y$ mayor que cada $x$” es falso: fije $x=y$. Mover un cuantificador existencial antes impide que su elección dependa de variables posteriores.
- Niegue un cuantificador a la vez, manteniendo el orden y los dominios: $\neg(\forall x\,\exists y\,S)\equiv\exists x\,\forall y\,\neg S$. Así “todo archivo almacenado tiene un hash” es falso exactamente cuando alguno archivo almacenado no tiene hash; no significa que todos carezcan de uno.
Activado $\mathbb R$, “for every $x$ there is $y>x$” is equivalent to “there is $y$ such that $y>x$ for every $x$.”
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
The first holds using y=x+1. The second fails by taking x=y for any proposed y.
Negar la convergencia a cero
- Para una secuencia real, la convergencia a cero significa: para cada $\varepsilon>0$, existe un entero no negativo $N$ tal que cada entero positivo $n>N$ satisface $|a_n|<\varepsilon$. El punto de corte $N$ puede depender de $\varepsilon$.
- Su negación es: existe un $\varepsilon>0$ tal que para cada punto de corte $N$, algún entero $n>N$ satisface $|a_n|\ge\varepsilon$. Mantenga la condición estricta $n>N$; niegue solo la conclusión $|a_n|<\varepsilon$, incluyendo la igualdad en su fracaso.
The negation of “for every $\varepsilon > 0$ there is $N$ with $|a_n| < \varepsilon$ for all $n > N$” is
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Flip ∀ε, ∃N, ∀n>N to ∃ε, ∀N, ∃n>N, in that order. Failure of a strict inequality includes equality. Alternating zeros and ones fails at ε=1/2 but has late zeros, and ε=2 never fails.
Tardío arbitrariamente no es eventualmente siempre
- Sea $a_n=1$ para ímpar $n$ y $a_n=0$ para par $n$. Elija $\varepsilon=1/2$. Más allá de cualquier umbral existe un índice impar con $|a_n|\ge\varepsilon$, por lo que la secuencia no converge a cero.
- Sin embargo, no está eventual y acotado lejos de cero: los índices pares dan ceros tardíamente. Tampoco falla cada tolerancia positiva: $\varepsilon=2$ contiene toda la secuencia. Basta una tolerancia fallida; sus índices defectuosos no necesitan incluir todos los índices posteriores.
If a real sequence does not converge to zero, there must be a positive tolerance which every sufficiently late term exceeds or equals in absolute value.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Alternating 1 and 0 has arbitrarily late terms outside ε=1/2, but also arbitrarily late zeros. Some late term for every cutoff is weaker than all terms beyond one cutoff.
Let $a_n=1$ when $n$ is a power of $2$ y $a_n=0$ otherwise. Negate convergence to zero and verify the negation. Does the sequence eventually stay away from zero?
Compare los cuantificadores, universos de conjuntos y testigos explícitos en su razonamiento.
Resumen
- Una imagen inversa es el conjunto de entradas cuyas salidas pertenecen a un conjunto especificado. Las imágenes inversas preservan uniones, intersecciones y complementos en sus universos declarados; las imágenes siempre preservan uniones, pero la igualdad de intersecciones para cada par requiere inyectividad.
- Una relación de equivalencia es una relación reflexiva, simétrica y transitiva; sus clases particionan el subyacente conjunto. Una negación es la afirmación verdadera exactamente cuando la original es falsa. Niegue los cuantificadores en orden, manteniendo sus dominios y cualquier dependencia entre elecciones.