T.7 · Set images, equivalence relations and logical negation

Undergraduate GRE preparation. Local objectives within the reviewed ETS scope; this is original teaching, not an official test or score predictor.

Prerequisites: Set operations, quantifiers, functions and elementary proof.

• Prove image identities and distinguish inclusion from equality
• Check reflexivity, symmetry and transitivity with explicit cases
• Negate implications and quantified statements without changing their scope

preimage 原像: The set of inputs whose outputs lie in a specified target set.

equivalence relation 等价关系: A relation that is reflexive, symmetric and transitive.

For f:X→Y and A⊆X, the image f(A) consists of all outputs f(a) with a in A. A point is in f(A∪B) exactly when it comes from A or B, so f(A∪B)=f(A)∪f(B). If A⊆B, then f(A)⊆f(B). For an intersection only f(A∩B)⊆f(A)∩f(B) is automatic: the same output may come from different inputs. Use f(x)=x², A={−1}, B={1}; the left image is empty while the right intersection is {1}.

Preimages behave differently. For C⊆Y, f⁻¹(C) here denotes the set of all inputs sent into C, even if f has no inverse function. Membership in two preimages means the very same input maps into both target sets. Consequently preimages preserve unions, intersections and complements relative to the stated domain/codomain. Do not transfer a theorem about preimages to images. If f is injective, image intersections do become equal, because equal outputs then force a shared input.

A relation R on X is reflexive when xRx for every x, symmetric when xRy implies yRx, and transitive when xRy and yRz imply xRz. All three make an equivalence relation; its classes partition X. On integers, xRy when x and y have the same remainder modulo four gives four classes. The relation |x−y|≤1 is reflexive and symmetric but not transitive: 0R1 and 1R2 while 0 is not related to 2. Checking only a diagram or two properties is insufficient.

An implication P⇒Q is false exactly when P is true and Q false. Thus the negation of P⇒(Q∧R) is P∧(¬Q∨¬R), not ¬P⇒(¬Q∧¬R). Negating “every x has property A” gives “there exists x without A”; negating “there exists x” gives “every x does not”. A counterexample can disprove a universal claim, while examples cannot prove it. The quantifiers retain their order when individually negated: ¬(∀x∃y S(x,y)) is ∃x∀y ¬S(x,y).

Let f map both a and b to label L. With A={a}, B={b}, f(A∩B)=∅ but f(A)∩f(B)={L}. For xRy defined by x=y or x=−y on R, reflexivity and symmetry follow directly, and two sign changes still give z=±x, proving transitivity. The classes are {x,−x}, with {0} a singleton. A false statement “every stored file has a hash” means at least one stored file has no hash; it does not mean all files lack hashes.

f⁻¹(C) can mean a preimage set without an inverse function. A reflexive, symmetric relation may still fail transitivity. Negate the whole statement before simplifying its parts.

Prove $f(A\cap B)\subseteq f(A)\cap f(B)$. Give a strict-inclusion example. Under what additional assumption on f does equality follow for all A and B?

Worked solution

If $y=f(x)$ for $x\in A\cap B$, then x belongs to each set, so y belongs to each image. For strictness, map distinct a,b to the same c and take $A=\{a\}$, $B=\{b\}$. The left image is empty and the right intersection is $\{c\}$. If f is injective and $y=f(a)=f(b)$ with $a\in A,b\in B$, injectivity gives a=b in the intersection, proving reverse inclusion. Conversely the singleton example shows that equality for all pairs forces injectivity.

On the integers define $aRb$ when $a-b$ is divisible by 4. Prove it is an equivalence relation and describe every class. Negate: “For every integer n there exists an integer m greater than n with property P.”

Check after attempting

Reflexivity uses $a-a=0$; symmetry uses the negative of a multiple of four; transitivity uses the sum of two such multiples. Classes are the four residues modulo four; the class of a is $a+4\mathbb Z$. The negation is: there exists an integer n such that every integer m greater than n fails P. Equivalently $\exists n\,\forall m\,(m>n\Rightarrow\neg P(m))$. It does not assert that P fails for every integer, nor that m is at most n for every m.