集合画像、同値関係および論理否定
導入済み| English | 意味 |
|---|---|
| preimage/ˌpriːˈɪmɪdʒ/ | 逆像 |
| equivalence relation/ɪˈkwɪvələns rɪˈleɪʃn/ | 同値関係 |
解答前に考えるべきこと
- 異なる記録に同じラベルが割り当てられることがあります。単純な衝突のために、ある集合の像の交わりは、二つの像の交わりと異なり得ます。
- あなたの目標：像の同一性を証明し、包含と同一を区別すること。
関係性を読む
- 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} です。
- 自明性、対称性、推移性を具体的なケースを用いて確認してください。
Which identity holds for every function f and subsets A,B of its domain?
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
An output of an input in the union comes from at least one subset. Intersection equality can fail when distinct inputs share an output.
定義ルールを使う
- 逆像の振る舞いは異なります。C⊆Y において、ここでは f⁻¹(C) は f に逆関数が存在しない場合でも、C 内の点へ写されるすべての入力の集合を指します。二つの逆像に含まれるということは、まさにその入力が両方の標的集合へ写されることを意味します。したがって、逆像は明示された定義域・共集合に対して並立、交わり、補集合同士を保存します。逆像に関する定理を像にそのまま移転しないでください。f が単射であれば、像の交わりは等しくなります。なぜなら、等しい出力からは共通の入力が導かれるからです。
- 含意や論理記号を含む命題を否定する際は、その適用範囲を変えないように注意してください。
What is the negation of P⇒(Q∧R)?
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
Failure of the implication requires a true premise and a false conjunction. De Morgan changes the latter into a disjunction.
条件を確認する
- 集合 X 上の関係 R が反射的であるとは、すべての x について xRx が成り立つことをいう。対称的であるとは、xRy が成り立つなら yRx も成り立つことをいう。推移的であるとは、xRy かつ yRz が成り立つなら xRz も成り立つことをいう。これら3つが揃うと等価関係となり、その類は X を分割する。整数上で、x と y が4で割った余りが等しいときに xRy が成り立つとすると、4つの類が得られる。関係 |x−y|≤1 は反射的かつ対称的だが推移的ではない：0R1 かつ 1R2 であるにもかかわらず、0 は 2 と関係していない。図表や2つの性質のみをチェックしては不十分である。
- 含意や論理記号を含む命題を否定する際は、その適用範囲を変えないように注意してください。
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} は一元素集合です。「格納されたファイルにはすべてハッシュがある」という誤った命題は、「少なくとも一つの格納ファイルにハッシュがない」ことを意味し、「すべてのファイルにハッシュがない」ことを意味するものではありません。
How many equivalence classes are there on Z for equality of remainders modulo four?
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
Each integer belongs to exactly one of the remainder classes 0, 1, 2 or 3.
タスク形式を適用する
- 含意 P⇒Q が偽になるのは、P が真で Q が偽の場合だけです。したがって P⇒(Q∧R) の否定は ¬P⇒(¬Q∧¬R) ではなく、P∧(¬Q∨¬R) です。「すべての x は性質 A を持つ」という命題の否定は「A を持たない x が存在する」であり、「x が存在する」の否定は「すべての x は持たない」です。反例によって普遍命題を否定することはできますが、例によって証明することはできません。論理記号は個別に否定される際に順序を保ち続けます。¬(∀x∃y S(x,y)) は ∃x∀y ¬S(x,y) です。
- 含意や論理記号を含む命題を否定する際は、その適用範囲を変えないように注意してください。
f⁻¹(C) は逆関数なしの逆像集合を意味することがあります。自明かつ対称な関係でも推移性が成立しないことがあります。部分式を簡略化する前に、まず文全体を否定してください。
このケースに当てはまる答えはどれか？
像の恒等式を証明し、包含関係と同一性を区別する
The relation |x−y|≤1 on R is transitive.
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
Use x=0,y=1,z=2: the first two pairs satisfy the relation, but the pair (0,2) does not.
区別を保つ
- 逆像 — 出力が特定の標的集合に含まれる入力の集合。
- 等価関係 — 自己対称、対称的、伝達的である関係。
- 像の恒等式を証明し、包含と同一性を区別する。
- 自明性、対称性、推移性を具体的なケースを用いて確認してください。
- 含意や論理記号を含む命題を否定する際は、その適用範囲を変えないように注意してください。
Match each term with its precise meaning in this lesson.
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
難易度 3/5 · 200 コイン + 今日初回完了時に小ボーナス付与
The order follows the stated process; check each stage before the next.