二項関係と写像

8.二項関係

二項関係

\(A\)と\(B\)間の二項関係とは\(A \times B\)の部分集合である

\(A\)上の二項関係

\(A\)上の二項関係とは\(A \times A\)の部分集合である

表記

二項関係\(R\)に対して\(a 〜_R b\)とは\((a,b)\in R\)を意味する。記号\(〜_R\)は適宜定められる(\(\equiv_R , \leq_R\)など)

9.写像

写像

集合\(A\)から集合\(B\)への写像とは
次を満たす二項関係\(G_f\)である

1. \(\forall a\in A\exists b\in B((a,b)\in G_f)\)
2. \((a,b_1)\in G_f\land (a,b_2)\in G_f \Rightarrow b_1=b_2\)

表記

集合\(A\)から集合\(B\)への写像 \(G_f\) を
\(f:A\rightarrow B\ (x\mapsto f(x)) \)
と表記し
\(f(x)=y \Leftrightarrow (x,y)\in G_f\)
\(f=g \Leftrightarrow G_f=G_g\)
と定める

POINT

\(f:A\rightarrow B\)は
\(A\)の元全てに\(B\)への対応があって
さらにその対応先は唯一である
(集合は相等な要素の重複を許さないため)

仮に対応のない\(A\)の元があるとすると定義されない値\(f(a)=?\)が出てきてしまって勝手が悪い

また仮に対応先が唯一でないとすると\((b_1 \neq b_2) \land (b_1=f(a)=b_2)\)
のようなことが起こりうるので\(f(a)=b\)のような対応関係を考えることができなくなってしまう

10.全射・単射

全射

\(f:X\rightarrow Y\)が全射:

\(\forall b\in Y \exists a\in X(f(a)=b)\)

単射

\(f:X\rightarrow Y\)が単射:

\(\forall a_1,a_2\in X(f(a_1)=f(a_2) \rightarrow a_1=a_2)\)

全単射

全射かつ単射な写像を全単射な写像という

11.恒等写像

恒等写像

\(X\)上の恒等写像:
\(G_{id_X}=\{(x,y)\in X\times X|y=x\}\)

恒等写像は写像である

\(id_X:X\rightarrow X\)であり\(f(x)=x\)

任意の\(a\in X\)は対応を持つ

\(X=X\)なので\(a\in X \Leftrightarrow a \in X\)

対応先も唯一である

\(\small ((a,b_1)\in G_{id_X}) \land ((a,b_2)\in G_{id_X}) \Rightarrow b_1=b_2=a\)

12.逆写像

逆写像

\(f:X\rightarrow Y\)が全単射の時
\(f^{-1}:=\{(y,x)\in Y\times X|f(x)=y\}\)

逆写像は写像である

\(f^{-1}:Y\rightarrow X\)

任意の\(b\in Y\)に対して\(X\)への対応を持つ

\(f\)は全射なので\(b\in Y \Rightarrow \exists a\in X (f(a)=b)\)から
\( b\in Y \Rightarrow  \exists a \in X((b,a)\in f^{-1})\)

対応先は唯一である

\(f\)は単射なので
\((b,a_1)\in f^{-1}\land (b,a_2)\in f^{-1}\)
\(\Leftrightarrow f(a_1)=y \land f(a_2)=y\)
\(\Rightarrow x_1=x_2\)

命題

\(f :X\rightarrow Y\)に対して以下の命題は同値

\(⓵f\)は全単射
\(⓶\small g \circ f =id_X \)かつ\(\small f\circ g=id_Y\)となる
\(\small g:B\rightarrow A\)が存在する

(1\(\Rightarrow\)2)

\(g=f^{-1}\)とする
\(a\in X\)を任意にとって\(f(a)=b\)とすると逆写像の定義から\(f^{-1}(b)=a\)なので\(f^{-1}(f(a))=a\)

\( G_{f^{-1}\circ\ f}=\{(x_1,x_2)\in X\times X|f^{-1}(f(x_1))=x_2\}\\ \\ \ \ \ \ \ \ \ \ \ \ \ =\{(x_1,x_2)\in X\times X|x_1=x_2\}=G_{id_X}\)
同様に\(G_{f \circ\ f^{-1}}=G_{id_Y}\)
よって\(f^{-1} \circ f=id_X\ \ f\circ f^{-1}=id_Y\)

(2\(\Rightarrow\)1)

全射
\(b\in Y\)を任意にとって\(g(b)=a(\in X)\)とすると
\(f(a)=f(g(b))=b\)

単射
\(f(a_1)=f(a_2)\)とする
\(a_1=g(f(a_1))=g(f(a_2))=a_2\)

13.合成写像

合成写像

\(f:X\rightarrow Y\)       \(g:Y\rightarrow Z\) のとき\(G_{g\circ f}:= \{(x,z)\in X\times Z|z=g(f(x))\}\)

合成写像は写像である

\(g\circ f:X\rightarrow Z\)であり\((g\circ f)(x)=g(f(x))\)

任意の\(a\in X\)に対して\(Z\)への対応を持つ

\(f:X\rightarrow Y\)なので\(\forall a \in X \exists b_0\in Y(f(a)=b_0)\)
\(g:Y\rightarrow Z\)なので\(\exists c\in Z((g(b_0)=c)\)
よって\(\forall a\in X\exists c\in Z(g(f(a)))\)

対応先は唯一である

\((a,c_1)\in G_{g \circ f} \land (a,c_2)\in G_{g \circ f} \)のとき
\(c_1=g(f(a))\land c_2=g(f(a))\)
よって\(c_1=c_2\)

命題

\(f :X\rightarrow Y\) \(g :Y\rightarrow Z\)に対して次が成り立つ

1. \(f,g\)全射\(\Rightarrow g\circ f\)は全射
2. \(f,g\)単射\(\Rightarrow g\circ f\)は単射

1. \(f,g\)全射\(\Rightarrow g\circ f\)は全射
2. \(f,g\)単射\(\Rightarrow g\circ f\)は単射

(1)
\(g\)が全射なので\(\forall c\in C \exists b_1\in B(g(b_1)=c)\)
\(f\)が全射なので\(\exists a_1 \in A(f(a_1)=b_1)\)

\(\forall c \in Z \exists a\in X (c=g(f(a))\)
\(g\circ f\)は全射

(2)
\(f,g\)が単射なので
\(\forall a_1,a_2\in A \)
\(\small g\circ f(a_1)=g\circ f(a_2)\Rightarrow f(a_1)=f(a_2) \Rightarrow a_1=a_2\)
\(g\circ f\)は単射

合成写像の演算法則

\(h\circ (g\circ f)=(h\circ g)\circ f\)
\((g\circ f)^{-1}=f^{-1} \circ g^{-1}\)

14.像

\(f:X\rightarrow Y\)での\(X_0\subset X\)の像:
\(f(X_0):=\{y\in Y|\exists x\in X_0(f(x)=y)\}\)

定理

\(f :X\rightarrow Y\) , \(X_1,X_2\subset X\)
に対して次が成り立つ

\((1) X_1\subset X_2 \Rightarrow f(X_1)\subset f(X_2)\)
\((2)f(X_1\cup X_2)=f(X_1)\cup f(X_2)\)
\((3)f(X_1\cap X_2)\subset f(X_1)\cap f(X_2)\)

(1)

\( b\in f(X_1)\Leftrightarrow \exists a\in X_1(f(a)=b) \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \xrightarrow{X_1\subset X_2}\exists a\in X_2(f(a)=b) \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Leftrightarrow b\in f(X_2)\)

(2)

\( b\in f(X_1\cup X_2)\Leftrightarrow \exists a\in X_1\cup X_2(f(a)=b) \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Leftrightarrow\exists a_1\in X_1(f(a_1)=b)\lor \\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \exists a_2\in X_2(f(a_2)=b)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Leftrightarrow b\in f(X_1) \lor b\in f(X_2)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Leftrightarrow b\in f(X_1)\cup f(X_2)\)

(3)

\( b\in f(X_1\cap X_2)\Leftrightarrow \exists a\in X_1\cap X_2(f(a)=b) \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Rightarrow \exists a_1\in X_1(f(a_1)=b) \land \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \exists a_2\in X_2(f(a_2)=b)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Leftrightarrow b\in f(X_1)\land b\in f(X_2)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Leftrightarrow \in f(X_1)\cap f(X_2)\)

逆像

\(f:X\rightarrow Y\)での\(Y_0\subset Y\)の逆像:
\(f^{-1}(Y_0):=\{x\in X|f(x)\in Y_0\}\)

定理

\(f :X\rightarrow Y\) , \(Y_1,Y_2\subset Y\)
に対して次が成り立つ

\((1) Y_1\subset Y_2 \Rightarrow f^{-1}(Y_1)\subset f^{-1}(Y_2)\)
\((2)f^{-1}(Y_1\cup Y_2)=f^{-1}(Y_1)\cup f^{-1}(Y_2)\)
\((3)f^{-1}(Y_1\cap Y_2)= f^{-1}(Y_1)\cap f^{-1}(Y_2)\)

\((1) Y_1\subset Y_2 \Rightarrow f^{-1}(Y_1)\subset f^{-1}(Y_2)\)
\((2)f^{-1}(Y_1\cup Y_2)=f^{-1}(Y_1)\cup f^{-1}(Y_2)\)
\((3)f^{-1}(Y_1\cap Y_2)= f^{-1}(Y_1)\cap f^{-1}(Y_2)\)

(1)

\( a\in f^{-1}(Y_1)\Leftrightarrow   f(a)\in Y_1 \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \xrightarrow{Y_1\subset Y_2}f(a)\in Y_2 \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Leftrightarrow a\in f^{-1}(Y_2)\)

(2)

\( a\in f^{-1}(Y_1\cup Y_2)\Leftrightarrow f(a)\in Y_1\cup Y_2 \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Leftrightarrow f(a)\in Y_1 \lor f(a)\in Y_2\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Leftrightarrow a\in f^{-1}(Y_1) \lor a\in f^{-1}(Y_2)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Leftrightarrow a\in f^{-1}(Y_1)\cup f^{-1}(Y_2)\)

(3)

\( a\in f^{-1}(Y_1\cap Y_2)\Leftrightarrow f(a)\in X_1\cap X_2 \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Leftrightarrow f(a)\in Y_1 \land f(a)\in Y_2 \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Leftrightarrow a\in f^{-1}(Y_1)\land a\in f^{-1}(Y_2)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Leftrightarrow a \in f^{-1}(Y_1)\cap f^{-1}(Y_2)\)