単射の定義を解釈する方法

Aug 23 2020

テレンス・タオの分析を読んでいます。セクション3.3で、彼は単射の定義を次のように紹介します。

異なる要素が異なる要素にマップされる場合、関数fは1対1(または単射)です。 $$x \neq x' \Longrightarrow f(x) \neq f(x') $$ 同様に、関数は次の場合に1対1です。 $$ f(x) = f(x') \Longrightarrow x = x'$$

言語は理解するのは難しいことではありません。しかし、演習3.3.3を行っていたとき、それはそれほど厳密ではなく、定義の解釈が異なると結論も異なることがわかりました。

たとえば、次のように解釈すると(ドメインが $X$$$ \forall x \forall x'(x \in X \wedge x' \in X \wedge (x \neq x' \Longrightarrow f(x) \neq f(x')))$$、その後、空関数は単射ではありません。 $x \in \varnothing$ 常に虚偽の陳述です。

一方、それを次のように解釈すると $$\forall x \forall x'((x \in X \wedge x' \in X \wedge x \neq x') \Longrightarrow (f(x) \neq f(x'))) $$、または $$ \forall x \forall x'((x \in X \wedge x' \in X) \Longrightarrow( x \neq x' \Rightarrow (f(x) \neq f(x'))) $$、その後、空関数は常に単射です $$(x \in \varnothing \wedge x' \in \varnothing \wedge x \neq x') \Longrightarrow (f(x) \neq f(x'))$$ そして $$(x \in \varnothing \wedge x' \in \varnothing) \Longrightarrow( x \neq x' \Rightarrow (f(x) \neq f(x'))$$ 空虚な真です。

どちらの解釈が正しいですか、それとも定義に異なる解釈がありますか?

回答

1 AsafKaragila Aug 23 2020 at 16:03

あなたの最初の解釈、 $$\forall x\forall x'(x\in X\land x'\in X\land (x\neq x'\to f(x)\neq f(x'))),$$ 間違っています。

ここでやろうとしているのは、全称記号をバインドすることです。 $$(\forall x\in X)(\forall x'\in X)(x\neq x'\to f(x)\neq f(x')),$$ しかし、有界全称記号は次のように定義されます。 $$(\forall x\in X)\varphi := \forall x(x\in X\to\varphi).$$

正しい解釈は確かに2番目の解釈です。 $$\forall x\forall x'((x\in X)\to((x'\in X)\to(x\neq x'\to f(x)\neq f(x')))),$$ または簡略化した後、 $$\forall x\forall x'((x\in X\land x'\in X)\to(x\neq x'\to f(x)\neq f(x'))).$$

対照的に、それを追加しましょう。 $(\exists x\in X)\varphi$ と定義されている $\exists x(x\in X\land\varphi)$。それがあなたが問題に終わった理由です。

1 HennoBrandsma Aug 23 2020 at 15:21

場合 $f$ ドメインが付属しています $X$、次に単射を解釈する必要があります(2番目の解釈に沿って):

$$\forall x,x': \left( x \in X \land x' \in X \land x \neq x' \right) \implies (f(x) \neq f(x')$$

これは確かに、空のドメインで任意の機能を空虚に単射にします。グレッグもコメントで述べたように、あなたが後で言及するものは、2つの意味を持っていますが、論理的に同等です$p \to (q \to r)$ 論理的には同等です $(p\land q) \to r$