Set images, equivalence relations and logical negation
Introduced| English | Meaning |
|---|---|
| preimage/ˌpriːˈɪmɪdʒ/ | The set of inputs whose outputs belong to a specified set. |
| equivalence relation/ɪˈkwɪvələns rɪˈleɪʃn/ | A reflexive, symmetric and transitive relation; its classes partition the underlying set. |
| negation/nɪˈɡeɪʃn/ | The statement true exactly when the original is false. |
Two records, one label
- A hash function sends distinct files $a$ and $b$ to the same label $L$. With $A=\{a\}$ and $B=\{b\}$, the image of $A\cap B$ is empty, but $f(A)\cap f(B)=\{L\}$.
- The same label need not mean the same input. This distinction connects preimages 原像, equivalence relations 等价关系 and logical negation 否定.
State the two universes
- Fix $f:X\to Y$. For $A\subseteq X$, its image is $f(A)=\{f(x):x\in A\}$. For $C\subseteq Y$, its preimage is $f^{-1}(C)=\{x\in X:f(x)\in C\}$.
- The symbol $f^{-1}(C)$ describes a set of inputs, even when $f$ has no inverse function. Complements must name their universe: $X\setminus A$ and $Y\setminus C$ live in different sets.
Why images preserve unions
- If $y\in f(A\cup B)$, some input $x\in A\cup B$ maps to $y$. That input lies in $A$ or $B$, so $y\in f(A)\cup f(B)$.
- Conversely, membership in either image gives an input in $A\cup B$. The two inclusions prove $f(A\cup B)=f(A)\cup f(B)$, without any assumption of injectivity.
Intersections: one input or two?
- If $y\in f(A\cap B)$, one input belongs to both sets and maps to $y$. Thus $f(A\cap B)\subseteq f(A)\cap f(B)$. In the reverse direction, the two inputs might differ: squaring sends both $-1$ and $1$ to $1$.
- If $f$ is injective, equal outputs force those inputs to agree, giving equality. Equality for every pair $A,B$ also forces injectivity: a collision gives disjoint singletons with overlapping images. Equality for one pair, such as $A=B$, proves nothing about injectivity.
For every function $f$ and sets $A, B$ in its domain, which always holds?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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\}$ and $B=\{b\}$, what are $f(A\cap B)$ and $f(A)\cap f(B)$?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The input intersection is empty, but both image sets contain L.
Differences and complements can fail
- Always $f(A)\setminus f(B)\subseteq f(A\setminus B)$: an output absent from $f(B)$ has no input in $B$. The reverse can fail. If $f(a)=f(b)=L$, then $A=\{a\}$ and $B=\{b\}$ give $\{L\}$ on the right but the empty set on the left.
- 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 the quantifiers, set universes and explicit witnesses in your reasoning.
Preimages preserve set operations
- For $C,D\subseteq Y$, an input maps into $C\cup D$ exactly when it maps into at least one set. It maps into $C\cap D$ exactly when it maps into both. Hence preimages preserve both unions and intersections.
- Also $f^{-1}(Y\setminus C)=X\setminus f^{-1}(C)$: both sides contain exactly the inputs whose outputs are outside $C$. None of these identities needs injectivity or surjectivity.
$f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D)$ for every function $f$.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
An input maps into C ∩ D exactly when it maps into both C and D; injectivity is unnecessary.
Going out and back
- The identity $f(f^{-1}(C))=C\cap f(X)$ keeps only reachable outputs. In the finite map above, $C=\{L,N\}$ has preimage $\{a,b\}$ and image-of-preimage $\{L\}$: missing output $N$ cannot appear.
- Always $A\subseteq f^{-1}(f(A))$. This round trip adds every input sharing an output with $A$. For $A=\{a\}$ it gives $\{a,b\}$. Equality for every $A$ holds exactly when $f$ is injective.
Valid for every map?
Distinguish universal identities from claims needing extra hypotheses.
For $f(x)=x^2$ on $\mathbb R$ and $A=\{-2\}$, how many elements belong to $f^{-1}(f(A))$?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
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))$.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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\}$ to $Y=\{L,M,N\}$. For $A=\{a\}$ and $C=\{L,N\}$, find $f^{-1}(f(A))$, $f(f^{-1}(C))$, and $f^{-1}(Y\setminus C)$. Explain each change.
Compare the quantifiers, set universes and explicit witnesses in your reasoning.
Three relation properties
- 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.
- Transitivity requires $x\sim y$ and $y\sim z$ to imply $x\sim z$ for every triple. An equivalence relation has all three properties. Always state $S$: changing the allowed elements can change the answer.
Why equivalence classes partition a set
- Define $[x]=\{y\in S:y\sim x\}$. Reflexivity places $x$ in $[x]$, so the classes cover $S$. Each class is nonempty.
- If $z\in[x]\cap[y]$, symmetry and transitivity give $x\sim y$. Any $w\sim x$ then also satisfies $w\sim y$, so $[x]\subseteq[y]$; reversing the roles gives equality. Distinct classes are therefore disjoint: together they form a partition.
Remainders give complete classes
- On $\mathbb Z$, let $x\sim y$ mean $4$ divides $x-y$. Reflexivity follows from $x-x=0$; symmetry from changing the sign; transitivity from adding two differences divisible by $4$.
- The four classes are $[0],[1],[2],[3]$, with $[r]=\{r+4k:k\in\mathbb Z\}$. Negative integers belong too: $-1\in[3]$. Replacing $4$ by $6$ gives exactly six classes, since every integer has one remainder from $0$ through $5$.
How many equivalence classes does “same remainder mod 6” have on $\mathbb Z$?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Two integers are related when they leave the same remainder on division by 6. The possible remainders 0, 1, …, 5 give exactly 6 classes.
Equal squares, equal class
- On $\mathbb R$, $x\sim y$ when $x=\pm y$, equivalently $x^2=y^2$. Equality of these outputs is reflexive, symmetric and transitive, so this is an equivalence relation.
- For $x\ne0$, the class is $\{x,-x\}$; the class of zero is just $\{0\}$. More generally, any function groups inputs into equivalence classes by equal output, whether or not that function is injective.
Find the property that fails
- On $\mathbb R$, $|x-y|\le1$ fails transitivity using $0,1,2$. On $\mathbb Z$, odd difference fails reflexivity because $x-x=0$; it also fails transitivity using $1,2,3$. Both relations are symmetric.
- The relation $x\le y$ on $\mathbb R$ fails symmetry using $0,1$. The relation $xy>0$ on $\mathbb R\setminus\{0\}$ is equivalence by sign, but on all of $\mathbb R$ it fails reflexivity at zero. The universe is part of the question.
Equivalence relation?
Check reflexive, symmetric and transitive together.
On $\mathbb Z$, the relation “$x - y$ is odd” is
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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$.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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 the quantifiers, set universes and explicit witnesses in your reasoning.
Implication and its contrapositive
- $P\Rightarrow Q$ is false exactly when $P$ is true and $Q$ is false. If $P$ is false, the implication is true. For example, “if $3$ is divisible by $4$, then $3$ is even” has a false premise and is a true implication.
- The contrapositive $\neg Q\Rightarrow\neg P$ has the same truth value as $P\Rightarrow Q$. The converse $Q\Rightarrow P$ need not: divisibility by $4$ implies evenness for integers, but the even number $2$ is not divisible by $4$.
$P \Rightarrow Q$ is false only when $P$ is true and $Q$ is ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Truth table of implication.
Negate the whole statement
- Negating an implication gives $\neg(P\Rightarrow Q)\equiv P\wedge\neg Q$. De Morgan's laws swap “and” with “or”: for example, $\neg(Q\wedge R)\equiv\neg Q\vee\neg R$.
- Combining the rules, the negation of $P\Rightarrow(Q\wedge R)$ is $P\wedge(\neg Q\vee\neg R)$. The premise must hold, and at least one promised conclusion must fail. The “or” includes the possibility that both conclusions fail.
Quantifier order controls the claim
- On $\mathbb R$, “for every $x$ there is $y>x$” is true: choose $y=x+1$. “There is $y$ greater than every $x$” is false: set $x=y$. Moving an existential quantifier earlier prevents its choice from depending on later variables.
- Negate one quantifier at a time, keeping order and domains: $\neg(\forall x\,\exists y\,S)\equiv\exists x\,\forall y\,\neg S$. Thus “every stored file has a hash” is false exactly when some stored file has no hash; it does not mean every file lacks one.
On $\mathbb R$, “for every $x$ there is $y>x$” is equivalent to “there is $y$ such that $y>x$ for every $x$.”
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The first holds using y=x+1. The second fails by taking x=y for any proposed y.
Negating convergence to zero
- For a real sequence, convergence to zero means: for every $\varepsilon>0$, there is a nonnegative integer $N$ such that every positive integer $n>N$ satisfies $|a_n|<\varepsilon$. The cutoff $N$ may depend on $\varepsilon$.
- Its negation is: there is $\varepsilon>0$ such that for every cutoff $N$, some integer $n>N$ satisfies $|a_n|\ge\varepsilon$. Keep the strict condition $n>N$; negate only the conclusion $|a_n|<\varepsilon$, including equality in its failure.
The negation of “for every $\varepsilon > 0$ there is $N$ with $|a_n| < \varepsilon$ for all $n > N$” is
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Arbitrarily late is not eventually always
- Let $a_n=1$ for odd $n$ and $a_n=0$ for even $n$. Choose $\varepsilon=1/2$. Beyond every cutoff there is an odd index with $|a_n|\ge\varepsilon$, so the sequence does not converge to zero.
- Yet it is not eventually bounded away from zero: even indices give zeros arbitrarily late. Nor does every positive tolerance fail: $\varepsilon=2$ contains the whole sequence. One failed tolerance is enough; its bad indices need not include every later index.
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.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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$ and $a_n=0$ otherwise. Negate convergence to zero and verify the negation. Does the sequence eventually stay away from zero?
Compare the quantifiers, set universes and explicit witnesses in your reasoning.
Recap
- A preimage is the set of inputs whose outputs belong to a specified set. Preimages preserve unions, intersections and complements in their stated universes; images always preserve unions, but intersection equality for every pair requires injectivity.
- An equivalence relation is a reflexive, symmetric and transitive relation; its classes partition the underlying set. A negation is the statement true exactly when the original is false. Negate quantifiers in order, keeping their domains and any dependence between choices.