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

大学卒GRE準備。検証済みETS範囲内の地域的な目標；これは独自の教育であり、公式テストや得点予測器ではありません。

前提知識: 集合演算、論理記号、関数、初等的証明。

• 値域の恒等式を証明し、包含と同一を区別する
• 明示的なケースを用いて反射律、対称性、推移性を確認する
• 帰結と論理記号付き文の否定を行い、そのスコープを変更しない

逆像: 出力が指定された対象集合に含まれる入力の集合。

同値関係: 反射的、対称的、推移的な関係。

f:X→Y かつ A⊆X において、値域 f(A) は a∈A である f(a) のすべてからなる集合である。一点が f(A∪B) に含まれるのは、それが A または B から来ている場合のみであり、したがって f(A∪B)=f(A)∪f(B) である。A⊆B ならば f(A)⊆f(B) である。交差については、f(A∩B)⊆f(A)∩f(B) だけが自動的に成り立つ：同じ出力は異なる入力から来ることがある。f(x)=x²、A={−1}、B={1} を用いると、左辺の値域は空であるが、右辺の交差は {1} である。

逆像は異なる振る舞いを示す。C⊆Y において、ここで f⁻¹(C) は f が逆関数を持たない場合でも、C に送られる入力のすべてを表す集合である。2つの逆像への所属とは、非常に同じ入力が両方の対象集合にマッピングされることを意味する。したがって、逆像は明示された定義域／陪集合に対して並立、交差、補集合を保存する。逆像に関する定理を値域に移転しないでほしい。f が単射であれば、値域の交差も等しくなる。なぜなら、等しい出力は共有された入力を強制するためである。

集合 X 上の関係 R が Requirements に reflexive（自己律）であるとは、すべての x について xRx が成り立つことをいう。symmetric（対称的）であるとは、xRy が成り立つのなら yRx も成り立つことをいう。transitive（推移的）であるとは、xRy かつ yRz が成り立つなら xRz も成り立つことをいう。これら3つが揃うと equivalence relation（同値関係）となり、その類は X を partition（分割）する。整数に対して、x と y が4で割った余りが同じとき xRy とすれば、4つの類ができる。関係 |x−y|≤1 は reflexive かつ symmetric だが transitive ではない：0R1 かつ 1R2 だが、0 は 2 と関係しない。図や性質の2つだけを確認だけでは不十分である。

含意 P⇒Q が false（偽）となるのは、P が true（真）で Q が false のときだけである。したがって、P⇒(Q∧R) の否定は P∧(¬Q∨¬R) であり、¬P⇒(¬Q∧¬R) ではない。「すべての x は性質 A を持つ」の否定は「A を持たない x が存在する」であり、「ある x は存在する」の否定は「すべての x は持たない」となる。counterexample（反例）によって universal claim（全称命題）を falsify（反証）できるが、例では prove（証明）できない。quantifiers（量詞）は個々に否定される際に順序を保つ：¬(∀x∃y S(x,y)) は ∃x∀y ¬S(x,y) となる。

f が a と b の両方をラベル L に写すとします。A={a}、B={b} とすると、f(A∩B)=∅ ですが、f(A)∩f(B)={L} です。R 上で xRy が x=y または x=−y で定義される場合、自明性と対称性は直接導かれ、符号を二回変えても z=±x となるため、推移性が証明されます。類は {x,−x} で、{0} は一元素集合です。「格納されたファイルにはすべてハッシュがある」という誤った命題は、「少なくとも一つの格納ファイルにハッシュがない」ことを意味し、「すべてのファイルにハッシュがない」ことを意味するものではありません。

f⁻¹(C) は逆関数なしの逆像集合を意味することがあります。自明かつ対称な関係でも推移性が成立しないことがあります。部分式を簡略化する前に、まず文全体を否定してください。

$f(A\cap B)\subseteq f(A)\cap f(B)$ を证明せよ。strict-inclusion（厳密な包含）の例を示せ。f に対するどのような追加の仮定により、すべての A と B について equality（等号）が導かれるか。

解例

もし $y=f(x)$ が $x\in A\cap B$ に対して成り立つなら、x は各 set に含まれるので、y は各 image にも含まれる。strictness（厳密性）のためには、異なる a, b を同じ c に写し、$A=\{a\}$, $B=\{b\}$ を取る。左側の image は空集合であり、右側の intersection は $\{c\}$ である。 f が injective（単射）で、$y=f(a)=f(b)$ が $a\in A,b\in B$ に対して成り立つなら、injectivity により intersection で a=b が得られ、reverse inclusion（逆包含）が証明される。逆に、singleton（一元素集合）の例は、すべての pair について equality が成り立つことが injectivity を強制することを示している。

整数上で、$a-b$ が 4 で割り切れるときに $aRb$ を定義せよ。これが同値関係であることを証明し、すべての類を記述せよ。また、「すべての整数 n に対して、n より大きい整数 m が存在し、性質 P を満たす」の否定を述べよ。

解答後の確認

反射性は $a-a=0$ を用い、対称性は四の倍数の負の数を用い、推移性は二つの四の倍数の和を用いる。類は四で割った余りの四通りであり、a の類は $a+4\mathbb Z$ である。 否定は以下の通りである：ある整数 n が存在して、n よりすべての整数 m は P を満たさない。すなわち $\exists n\,\forall m\,(m>n\Rightarrow\neg P(m))$ 。これは P がすべての整数について成立しないこと、あるいは m がすべての m に対して n 以下であることを主張するものではない。