関数による表現
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/05 06:03 UTC 版)
「カントールの対角線論法」の記事における「関数による表現」の解説
以下の補題を使った論法も対角線論法と呼ばれる。後で見るように、実は以下の補題は前節で示した補題と同値である。 X {\displaystyle X} を集合とし、 ϕ : X × X → { 0 , 1 } {\displaystyle \phi :X\times X\rightarrow \{0,1\}} を写像とする。 ϕ ( x , y ) {\displaystyle \phi (x,y)} を ϕ x ( y ) {\displaystyle \phi _{x}(y)} と書くと、各 x ∈ X {\displaystyle x\in X} に対し ϕ x {\displaystyle \phi _{x}} は X {\displaystyle X} から { 0 , 1 } {\displaystyle \{0,1\}} への写像である。 g : X → { 0 , 1 } {\displaystyle g:X\rightarrow \{0,1\}} を、 g ( x ) = ¬ ϕ x ( x ) {\displaystyle g(x)=\neg \phi _{x}(x)} により定義する。ここで、「 ¬ {\displaystyle \neg } 」は0と1を反転する写像。すなわち、 ¬ 0 = 1 {\displaystyle \neg {0}=1\quad } 、 ¬ 1 = 0 {\displaystyle \neg {1}=0\quad } 。このとき、 ϕ x 0 = g {\displaystyle \phi _{x_{0}}=g} となる x 0 ∈ X {\displaystyle x_{0}\in X} は存在しない。 実際、もしそのような x 0 ∈ X {\displaystyle x_{0}\in X} が存在すれば、 ϕ x 0 ( x 0 ) = g ( x 0 ) = ¬ ϕ x 0 ( x 0 ) {\displaystyle \phi _{x_{0}}(x_{0})=g(x_{0})=\neg \phi _{x_{0}}(x_{0})} となり矛盾する。第一の等号は ϕ x 0 = g {\displaystyle \phi _{x_{0}}=g} より。第二の等号はgの定義より。 なお上の補題は ϕ {\displaystyle \phi } の値域 Z {\displaystyle Z} が {0,1} ではない場合にも一般化でき、 σ : Z → X {\displaystyle \sigma :Z\rightarrow X} を σ ( z ) = z {\displaystyle \sigma (z)=z} となる z ∈ Z {\displaystyle z\in Z} が存在しない写像とし、 g ( x ) = σ ∘ ϕ x ( x ) {\displaystyle g(x)=\sigma \circ \phi _{x}(x)} とすると、 ϕ x 0 = g {\displaystyle \phi _{x_{0}}=g} となる x 0 ∈ X {\displaystyle x_{0}\in X} は存在しない。 べき集合2Xは、Xから{0,1}への関数全体の集合と自然に同一視できる事がよく知られているが、「関数による表現」の対角線論法と「集合による表現」の対角線論法はこの同一視を通して同値である事が証明できる。実際、ψを「集合による表現」で登場した関数とするとき、ψ(x)∈2XはXから{0,1}への関数とみなせる。関数ψ(x)によるy∈Xの像をψ(x)(y)と書き、関数φ: X×X→{0,1}を、φ(x,y)=ψ(x)(y)として「関数による表現」の補題を使う事で、「集合による表現」の補題を証明できる。（逆もまた真。）
※この「関数による表現」の解説は、「カントールの対角線論法」の解説の一部です。
「関数による表現」を含む「カントールの対角線論法」の記事については、「カントールの対角線論法」の概要を参照ください。
- 関数による表現のページへのリンク
