Set images, equivalence relations and logical negation
| English | Français |
|---|---|
| preimage/ˌpriːˈɪmɪdʒ/ | preimage |
| equivalence relation/ɪˈkwɪvələns rɪˈleɪʃn/ | equivalence relation |
A decision before an answer
- Two different records can be assigned the same label. That simple collision explains why an image of an intersection can differ from the intersection of two images.
- Your goal: Prove image identities and distinguish inclusion from equality.
Read the relationship
- 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}.
- Check reflexivity, symmetry and transitivity with explicit cases.
Which identity holds for every function f and subsets A,B of its domain?
An output of an input in the union comes from at least one subset. Intersection equality can fail when distinct inputs share an output.
Use the defining rule
- 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.
- Negate implications and quantified statements without changing their scope.
What is the negation of P⇒(Q∧R)?
Failure of the implication requires a true premise and a false conjunction. De Morgan changes the latter into a disjunction.
Check the conditions
- 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.
- Negate implications and quantified statements without changing their scope.
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.
How many equivalence classes are there on Z for equality of remainders modulo four?
Each integer belongs to exactly one of the remainder classes 0, 1, 2 or 3.
Apply the task format
- 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).
- Negate implications and quantified statements without changing their scope.
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.
Which answer fits this case?
Prove image identities and distinguish inclusion from equality
The relation |x−y|≤1 on R is transitive.
Use x=0,y=1,z=2: the first two pairs satisfy the relation, but the pair (0,2) does not.
Keep the distinctions
- preimage 原像 — The set of inputs whose outputs lie in a specified target set.
- equivalence relation 等价关系 — A relation that is reflexive, symmetric and transitive.
- 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.
Match each term with its precise meaning in this lesson.
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
The order follows the stated process; check each stage before the next.