集合像、等价关系与逻辑否定
引入| English | 释义 | 拼音 |
|---|---|---|
| preimage/ˌpriːˈɪmɪdʒ/ | 原像 | yuán xiàng |
| equivalence relation/ɪˈkwɪvələns rɪˈleɪʃn/ | 等价关系 | děng jià guān xì |
| negation/nɪˈɡeɪʃn/ | 否定 | fǒu dìng |
两条记录,一个标签
- 哈希函数将不同的文件 $a$ 和 $b$ 映射到同一标签 $L$。当 $A=\{a\}$ 且 $B=\{b\}$ 时,$A\cap B$ 的像为空,但 $f(A)\cap f(B)=\{L\}$ 非空。
- 同一标签未必对应相同输入。这一区分关联原像、等价关系和逻辑否定。
陈述两个全集
- 固定 $f:X\to Y$。对于 $A\subseteq X$,其像为 $f(A)=\{f(x):x\in A\}$。对于 $C\subseteq Y$,其原像为 $f^{-1}(C)=\{x\in X:f(x)\in C\}$。
- 符号 $f^{-1}(C)$ 描述了一组输入,即使 $f$ 没有反函数也是如此。补集必须指明其所属的全集:$X\setminus A$ 和 $Y\setminus C$ 位于不同的集合中。
为什么像保持并集
- 如果 $y\in f(A\cup B)$,某个输入 $x\in A\cup B$ 映射到 $y$。该输入属于 $A$ 或 $B$,因此 $y\in f(A)\cup f(B)$。
- 反之,属于任一像中的元素意味着存在一个在 $A\cup B$ 中的输入。这两个包含关系证明了 $f(A\cup B)=f(A)\cup f(B)$,无需任何单射假设。
交集:一个输入还是两个?
- 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$.
- 如果 $f$ 是单射,相等的输出迫使这些输入相同,从而得到相等性。对于每一对 $A,B$ 的相等性也迫使单射成立:碰撞会产生具有重叠像的不相交单点集。仅一对(如 $A=B$)的相等性无法证明单射。
For every function $f$ and sets $A, B$ in its domain, which always holds?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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)$?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
The input intersection is empty, but both image sets contain L.
差集和补集可能不成立
- 总是 $f(A)\setminus f(B)\subseteq f(A\setminus B)$:若一个输出不在 $f(B)$ 中,则其在 $B$ 中没有对应的输入。反之不一定成立。如果 $f(a)=f(b)=L$,则 $A=\{a\}$ 和 $B=\{b\}$ 在右侧给出 $\{L\}$,但在左侧为空集。
- 设 $X=\{a,b,c\}$、$Y=\{L,M,N\}$,其中 $a,b\mapsto L$ 和 $c\mapsto M$。对于 $A=\{a\}$,$X\setminus A$ 的像为 $\{L,M\}$,而 $Y\setminus f(A)=\{M,N\}$。相对于整个 $Y$ 保持补集,对任意 $A$ 均成立,需满足双射条件。
Prove that images preserve unions and give intersection inclusion. Then use a collision to disprove image-difference equality.
比较推理中的量词、集合论域及显式见证者。
原像保持集合运算
- 对于 $C,D\subseteq Y$,一个输入映射入 $C\cup D$ 当且仅当它映射入至少一个集合。它映射入 $C\cap D$ 当且仅当它映射入两个集合。因此原像既保持并集也保持交集。
- 同样有 $f^{-1}(Y\setminus C)=X\setminus f^{-1}(C)$:两边恰好包含那些输出不在 $C$ 中的输入。这些恒等式均不需要单射或满射条件。
$f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D)$ for every function $f$.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
An input maps into C ∩ D exactly when it maps into both C and D; injectivity is unnecessary.
出去与返回
- 恒等式 $f(f^{-1}(C))=C\cap f(X)$ 仅保留可达的输出。在上述有限映射中,$C=\{L,N\}$ 的原像是 $\{a,b\}$,其像的原像是 $\{L\}$:缺失的输出 $N$ 不会出现。
- 总是 $A\subseteq f^{-1}(f(A))$。这个往返过程加入了所有与 $A$ 共享输出的输入。对于 $A=\{a\}$,它给出 $\{a,b\}$。对所有 $A$ 的相等性成立当且仅当 $f$ 是单射。
对任意映射是否成立?
区分普遍恒等式与需额外假设的命题。
支持 $f(x)=x^2$ on $\mathbb R$ and $A=\{-2\}$, how many elements belong to $f^{-1}(f(A))$?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
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))$.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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\}$ 到 $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.
比较推理中的量词、集合论域及显式见证者。
关系的三个性质
- 集合 $S$ 上的关系如果是自反的,则要求 $x\sim x$ 对所有 $x\in S$ 成立;如果是对称的,则要求 $x\sim y$ 蕴含 $y\sim x$ 对所有数对成立。单个反例元素或数对即可证伪相应性质。
- 传递性要求 $x\sim y$ 和 $y\sim z$ 蕴含 $x\sim z$ 对每一三元组成立。等价关系具备全部三个性质。务必声明 $S$:改变允许的集合元素可能改变答案。
为什么等价类划分一个集合
- 定义 $[x]=\{y\in S:y\sim x\}$。自反性将 $x$ 置于 $[x]$ 中,因此这些类覆盖 $S$。每个类都是非空的。
- 若满足 $z\in[x]\cap[y]$、对称性和传递性,则得出 $x\sim y$。任意 $w\sim x$ 也满足 $w\sim y$,故 $[x]\subseteq[y]$;交换角色即得相等。因此不同的类互不相交:它们共同构成一个划分。
余数给出完整的类
- 在 $\mathbb Z$ 上,定义 $x\sim y$ 表示 $4$ 整除 $x-y$。自反性源于 $x-x=0$;对称性通过改变符号得出;传递性由两个被 $4$ 整除的差相加得到。
- 这四个类是 $[0],[1],[2],[3]$,包含 $[r]=\{r+4k:k\in\mathbb Z\}$。负整数也属于其中:$-1\in[3]$。将 $4$ 替换为 $6$ 恰好得到六个类,因为每个整数都有一个从 $0$ 到 $5$ 的余数。
How many equivalence classes does “same remainder mod 6” have on $\mathbb Z$?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Two integers are related when they leave the same remainder on division by 6. The possible remainders 0, 1, …, 5 give exactly 6 classes.
平方相等,类相同
- 在 $\mathbb R$ 上,当 $x=\pm y$ 时 $x\sim y$ 成立,等价于 $x^2=y^2$。这两个输出相等具有自反性、对称性和传递性,因此这是一种等价关系。
- 对于 $x\ne0$,该类是 $\{x,-x\}$;零的类仅为 $\{0\}$。更一般地,任何函数都通过相等的输出将输入分组为等价类,无论该函数是否单射。
找出失效的性质
- 在 $\mathbb R$ 上,利用 $0,1,2$ 可知 $|x-y|\le1$ 不满足传递性。在 $\mathbb Z$ 上,奇数差因 $x-x=0$ 而不满足自反性;利用 $1,2,3$ 也不满足传递性。这两种关系都具有对称性。
- $x\le y$ 在 $\mathbb R$ 上的关系利用 $0,1$ 不满足对称性。$xy>0$ 在 $\mathbb R\setminus\{0\}$ 上是基于符号的等价关系,但在整个 $\mathbb R$ 上于零处不满足自反性。论域是题目的一部分。
等价关系?
同时检查自反性、对称性和传递性。
开启 $\mathbb Z$, the relation “$x - y$ is odd” is
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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$.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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.
比较推理中的量词、集合论域及显式见证者。
蕴含及其逆否命题
- $P\Rightarrow Q$ 恰好在 $P$ 为真且 $Q$ 为假时为假。若 $P$ 为假,则该蕴含为真。例如,“若 $3$ 能被 $4$ 整除,则 $3$ 是偶数”具有假的前提,是一个真的蕴含。
- 逆否命题 $\neg Q\Rightarrow\neg P$ 与 $P\Rightarrow Q$ 具有相同的真值。但逆命题 $Q\Rightarrow P$ 不一定:被 $4$ 整除意味着整数是偶数,但偶数 $2$ 不能被 $4$ 整除。
$P \Rightarrow Q$ is false only when $P$ is true and $Q$ is ____.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Truth table of implication.
否定整个陈述
- 否定一个蕴含得到 $\neg(P\Rightarrow Q)\equiv P\wedge\neg Q$。德摩根定律将“与”互换为“或”:例如,$\neg(Q\wedge R)\equiv\neg Q\vee\neg R$。
- 结合规则,$P\Rightarrow(Q\wedge R)$ 的否定是 $P\wedge(\neg Q\vee\neg R)$。前提必须成立,且至少一个承诺的结论必须失败。“或”包括两个结论都失败的可能性。
量词顺序控制断言
- 在 $\mathbb R$ 上,“对于每一个 $x$,都存在 $y>x$”为真:选择 $y=x+1$。“存在一个 $y$ 大于每一个 $x$”为假:设定 $x=y$。将存在量词移至前面可防止其选择依赖于后续变量。
- 逐次否定一个量词,保持顺序和论域不变:$\neg(\forall x\,\exists y\,S)\equiv\exists x\,\forall y\,\neg S$。因此“每个已存储的文件都有哈希值”为假,当且仅当某个已存储的文件没有哈希值;这并不意味着所有文件都没有哈希值。
开启 $\mathbb R$, “for every $x$ there is $y>x$” is equivalent to “there is $y$ such that $y>x$ for every $x$.”
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
The first holds using y=x+1. The second fails by taking x=y for any proposed y.
否定收敛于零
- 对于实数序列,收敛于零意味着:对于每一个 $\varepsilon>0$,存在一个非负整数 $N$,使得每一个正整数 $n>N$ 都满足 $|a_n|<\varepsilon$。截断点 $N$ 可能依赖于 $\varepsilon$。
- 其否定是:存在一个 $\varepsilon>0$,使得对于每一个截断点 $N$,某个整数 $n>N$ 满足 $|a_n|\ge\varepsilon$。保留严格条件 $n>N$;仅否定结论 $|a_n|<\varepsilon$,包括等号失效的情况。
The negation of “for every $\varepsilon > 0$ there is $N$ with $|a_n| < \varepsilon$ for all $n > N$” is
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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.
任意靠后不等于最终恒成立
- 令 $a_n=1$ 对应奇数下标 $n$,$a_n=0$ 对应偶数下标 $n$。选择 $\varepsilon=1/2$。在每个截断点之后都存在一个奇数下标使得 $|a_n|\ge\varepsilon$ 成立,因此该序列不收敛于零。
- 然而它并非最终远离零:偶数下标会任意靠后地给出零值。也并非每个正容差都失败:$\varepsilon=2$ 包含了整个序列。一个失败的容差就足够了;其坏下标不必包含所有后续下标。
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.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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?
比较推理中的量词、集合论域及显式见证者。
复习要点
- 原像是指输出属于指定集合的输入所构成的集合。原像在声明的全集中保持并集、交集和补集;像总是保持并集,但对每对集合的交集相等性要求映射是单射。
- 等价关系是自反、对称和传递的关系;其等价类划分底层集合。否定是在原命题为假时恰好为真的陈述。按顺序否定量词,保持其论域及选择之间的任何依赖关系。