圏論/代数系/写像，演算

4.1 ρ {\displaystyle \rho } は集合 A {\displaystyle A} の元と集合 B {\displaystyle B} の元との間の関係とする. もし
一価律: a ρ b {\displaystyle a\rho b} かつ a ρ b ′ {\displaystyle a\rho b'} ならば b = b ′ {\displaystyle b=b'}
がみたされるならば, ρ {\displaystyle \rho } は A {\displaystyle A} から B {\displaystyle B} への半写像, または半関数といい, a ρ b {\displaystyle a\rho b} となる唯一の b {\displaystyle b} を ρ ( a ) {\displaystyle \rho (a)} で表し,これを a {\displaystyle a} における ρ {\displaystyle \rho } の値という. また A {\displaystyle A} はこの半写像の域, B {\displaystyle B} は余域という. ρ {\displaystyle \rho } の逆がまた一価律をみたすとき、 ρ {\displaystyle \rho } は一対一であるという.
ρ {\displaystyle \rho } が A {\displaystyle A} から B {\displaystyle B} への半写像であるとき、 a ρ b {\displaystyle a\rho b} である b {\displaystyle b} が存在するような a {\displaystyle a} の集合を ρ {\displaystyle \rho } の定義域, a ρ b {\displaystyle a\rho b} である a {\displaystyle a} の存在するような b {\displaystyle b} の集合を ρ {\displaystyle \rho } の像という. ρ {\displaystyle \rho } の定義域が A {\displaystyle A} と一致するとき, ρ {\displaystyle \rho } は A {\displaystyle A} から B {\displaystyle B} への写像,または関数といい, ρ {\displaystyle \rho } が A {\displaystyle A} から B {\displaystyle B} への写像であることを ρ : A → B {\displaystyle \rho :A\to B} で表す. 写像 ρ {\displaystyle \rho } の像が B {\displaystyle B} と一致するとき, ρ {\displaystyle \rho } は B {\displaystyle B} の上への写像,または全射的な写像という. ρ {\displaystyle \rho } が全射的な一対一写像のとき, ρ {\displaystyle \rho } は A {\displaystyle A} と B {\displaystyle B} の間の一対一対応といい,このことを ρ : A ≡ B {\displaystyle \rho :A\equiv B} で表す.
再び ρ {\displaystyle \rho } は A {\displaystyle A} から B {\displaystyle B} への半写像として, X ⊂ A , Y ⊂ B {\displaystyle X\subset A,Y\subset B} とする.このとき B {\displaystyle B} の部分集合 { ρ ( a ) | a ∈ X } {\displaystyle \{\rho (a)|a\in X\}} を X {\displaystyle X} の ρ {\displaystyle \rho } による像といい, ρ ( X ) {\displaystyle \rho (X)} で表す. ρ {\displaystyle \rho } の像とは ρ {\displaystyle \rho } による A {\displaystyle A} の像のことであった. また A {\displaystyle A} の部分集合 { a | ρ ( a ) ∈ Y } {\displaystyle \{a|\rho (a)\in Y\}} は ρ {\displaystyle \rho } による Y {\displaystyle Y} の逆像といい, ρ − 1 ( Y ) {\displaystyle \rho ^{-1}(Y)} で表す. ただし b ∈ B {\displaystyle b\in B} のとき ρ − 1 ( { b } ) {\displaystyle \rho ^{-1}(\{b\})} は単に ρ − 1 ( b ) {\displaystyle \rho ^{-1}(b)} と書く.
4.2 A , B , C {\displaystyle A,B,C} は集合, f : A → B , g : B → C {\displaystyle f:A\to B,g:B\to C} は写像とする.このとき各 a ∈ A {\displaystyle a\in A} に対してただ一つの c = g ( f ( a ) ) ∈ C {\displaystyle c=g(f(a))\in C} が定まる. この c {\displaystyle c} を k ( a ) {\displaystyle k(a)} で表せば k {\displaystyle k} は写像 k : A → C {\displaystyle k:A\to C} を定義する.この k {\displaystyle k} を g ∘ f {\displaystyle g\circ f} または g f {\displaystyle gf} で表し, f {\displaystyle f} と g {\displaystyle g} の合成という.さらに h : C → D {\displaystyle h:C\to D} ならば h ∘ ( g ∘ f ) = ( h ∘ g ) ∘ f {\displaystyle h\circ (g\circ f)=(h\circ g)\circ f} である. この両辺は括弧を省略して h ∘ g ∘ f {\displaystyle h\circ g\circ f} で表される. 次の定理は容易に証明できる.
定理 A , B , C {\displaystyle A,B,C} は集合, f : A → B , g : B → C {\displaystyle f:A\to B,g:B\to C} とする.
(i) f {\displaystyle f} と g {\displaystyle g} が共に一対一ならば g ∘ f {\displaystyle g\circ f} も一対一である。
(ii) f {\displaystyle f} と g {\displaystyle g} が共に全射的ならば g ∘ f {\displaystyle g\circ f} も全射的である.
(iii) g ∘ f {\displaystyle g\circ f} が一対一ならば f {\displaystyle f} も一対一である .
(iv) g ∘ f {\displaystyle g\circ f} が全射的ならば g {\displaystyle g} も全射的である. .
4.3 A {\displaystyle A} は集合, U {\displaystyle {\mathfrak {U}}} は A {\displaystyle A} の類別とするとき, 各 a ∈ A {\displaystyle a\in A} に対して a ∈ X {\displaystyle a\in X} である X ∈ U {\displaystyle X\in {\mathfrak {U}}} がただ一つ定まる. この X {\displaystyle X} を p ( a ) {\displaystyle p(a)} とおけば p {\displaystyle p} は A {\displaystyle A} から U {\displaystyle {\mathfrak {U}}} の上への写像となる.この p {\displaystyle p} を類別 U {\displaystyle {\mathfrak {U}}} への標準射影という.
f {\displaystyle f} が集合 A {\displaystyle A} から B {\displaystyle B} への写像のとき, A {\displaystyle A} の二元 a , a ′ {\displaystyle a,a'} に対して f ( a ) = f ( a ′ ) {\displaystyle f(a)=f(a')} のとき a ∼ a ′ {\displaystyle a\sim a'} と定義すれば ∼ {\displaystyle \sim } は A {\displaystyle A} 上の同値関係となる. これによる類別を U {\displaystyle {\mathfrak {U}}} とすれば各 X ∈ U {\displaystyle X\in {\mathfrak {U}}} に対して b ∈ B {\displaystyle b\in B} が定まり, a ∈ X {\displaystyle a\in X} ならば f ( a ) = b {\displaystyle f(a)=b} である. この b {\displaystyle b} を q ( X ) {\displaystyle q(X)} とおけば q {\displaystyle q} は U {\displaystyle {\mathfrak {U}}} から B {\displaystyle B} への写像で,これは一対一である. また p : A → U {\displaystyle p:A\to {\mathfrak {U}}} は U {\displaystyle {\mathfrak {U}}} への標準射影とすれば f = q ∘ p {\displaystyle f=q\circ p} . この対 ( p , q ) {\displaystyle (p,q)} を f {\displaystyle f} の右標準全単分解という.
4.4 X {\displaystyle X} が集合 B {\displaystyle B} の部分集合のとき、各 x ∈ X {\displaystyle x\in X} に対して i ( x ) = x {\displaystyle i(x)=x} とおけば, i {\displaystyle i} は X {\displaystyle X} から B {\displaystyle B} への写像となり, これは一対一である.この i {\displaystyle i} を X {\displaystyle X} の B {\displaystyle B} への理蔵または標準射入という. さらに g : B → C {\displaystyle g:B\to C} のとき,合成 g ∘ i {\displaystyle g\circ i} を g {\displaystyle g} の X {\displaystyle X} への制限といい, g ↾ X {\displaystyle g{\upharpoonright _{X}}} で表す.また h = g ↾ X {\displaystyle h=g{\upharpoonright _{X}}} に対して g {\displaystyle g} を h {\displaystyle h} の拡張という.
特に X = B {\displaystyle X=B} のとき, B {\displaystyle B} の B {\displaystyle B} への埋蔵を B {\displaystyle B} 上の恒等写像といい, 1 B {\displaystyle 1_{B}} で表す.任意の f : A → B , g : B → A {\displaystyle f:A\to B,g:B\to A} に対して 1 B ∘ f = f , g ∘ 1 B = g {\displaystyle 1_{B}\circ f=f,g\circ 1_{B}=g} である.また g ∘ f = 1 A {\displaystyle g\circ f=1_{A}} のとき g {\displaystyle g} は f {\displaystyle f} の左逆写像, f {\displaystyle f} は g {\displaystyle g} の右逆写像といい, さらに f ∘ g = 1 B {\displaystyle f\circ g=1_{B}} ならば f {\displaystyle f} と g {\displaystyle g} とは互いに他の逆写像という. このとき f {\displaystyle f} は A {\displaystyle A} と B {\displaystyle B} との間の一対一対応となる.逆に f {\displaystyle f} が一対一対応ならば f {\displaystyle f} は逆写像 g {\displaystyle g} を持つ.これを f − 1 {\displaystyle f^{-1}} で表す.
任意の写像 f : A → B {\displaystyle f:A\to B} に対して f {\displaystyle f} の像を X {\displaystyle X} とし, s ( a ) = f ( a ) {\displaystyle s(a)=f(a)} で s : A → X {\displaystyle s:A\to X} を定義すれば s {\displaystyle s} は X {\displaystyle X} の上への写像である.さらに r : X → B {\displaystyle r:X\to B} を埋蔵とすれば f = r ∘ s {\displaystyle f=r\circ s} . この対 ( s , r ) {\displaystyle (s,r)} を f {\displaystyle f} の左標準全単分解という.さらに ( p , q ) {\displaystyle (p,q)} が s {\displaystyle s} の右標準全単分解ならば f = r ∘ q ∘ p {\displaystyle f=r\circ q\circ p} で q {\displaystyle q} は一対一対応である.この三つ組 ( p , q , r ) {\displaystyle (p,q,r)} を f {\displaystyle f} の両標準全単分解という.
4.5 V = { A λ | λ ∈ Λ } {\displaystyle {\mathfrak {V}}=\{A_{\lambda }|\lambda \in \Lambda \}} を集合の族とし, A = ⋃ V {\displaystyle A=\bigcup {\mathfrak {V}}} とする.写像 φ : Λ → A {\displaystyle \varphi :\Lambda \to A} ですべての λ ∈ Λ {\displaystyle \lambda \in \Lambda } について φ ( λ ) ∈ A λ {\displaystyle \varphi (\lambda )\in A_{\lambda }} となるようなものを集合族 V {\displaystyle {\mathfrak {V}}} 上の選択関数という. V {\displaystyle {\mathfrak {V}}} 上の選択関数全体の集合を V {\displaystyle {\mathfrak {V}}} の直積といい, ∏ V {\displaystyle \prod {\mathfrak {V}}} ,または ∏ λ ∈ Λ A λ {\displaystyle \prod _{\lambda \in \Lambda }A_{\lambda }} で表す. 各 A λ ∈ V {\displaystyle A_{\lambda }\in {\mathfrak {V}}} はこの直積の成分という.また写像 π λ : ∏ V → A λ {\displaystyle \pi _{\lambda }:\prod {\mathfrak {V}}\to A_{\lambda }} で,各 φ ∈ ∏ V {\displaystyle \varphi \in \prod {\mathfrak {V}}} における値 π λ ( φ ) {\displaystyle \pi _{\lambda }(\varphi )} が φ ( λ ) {\displaystyle \varphi (\lambda )} であるものを直積の A λ {\displaystyle A_{\lambda }} 成分への標準射影という.
普通,集合論においては
選択公理:どの成分も空でなければそれらの直積も空でない
を仮定している.以下の議論もこの仮定のもとに行う.
特に Λ {\displaystyle \Lambda } が有限集合 { 1 , 2 , ⋅ ⋅ ⋅ , n } {\displaystyle \{1,2,\cdot \cdot \cdot ,n\}} のとき ∏ V {\displaystyle \prod {\mathfrak {V}}} は有限直積といい,また A 1 × A 2 × ⋅ ⋅ ⋅ × A n {\displaystyle A_{1}\times A_{2}\times \cdot \cdot \cdot \times A_{n}} で表され,その元 φ {\displaystyle \varphi } で λ = 1 , 2 , ⋅ ⋅ ⋅ , n {\displaystyle \lambda =1,2,\cdot \cdot \cdot ,n} に対して φ ( λ ) = a λ {\displaystyle \varphi (\lambda )=a_{\lambda }} となるものは ( a 1 , a 2 , ⋅ ⋅ ⋅ , a n ) {\displaystyle (a_{1},a_{2},\cdot \cdot \cdot ,a_{n})} で表される. §2 の始めに現れた二つの集合の直積 A × B {\displaystyle A\times B} も Λ = { 1 , 2 } {\displaystyle \Lambda =\{1,2\}} の特別な場合であった.また A 1 = A 2 = ⋅ ⋅ ⋅ = A n = A {\displaystyle A_{1}=A_{2}=\cdot \cdot \cdot =A_{n}=A} のとき ∏ V {\displaystyle \prod {\mathfrak {V}}} は A n {\displaystyle A^{n}} で表される.
2.1 で定義したように集合 A {\displaystyle A} の元と集合 B {\displaystyle B} の元との間の関係とは直積 A × B {\displaystyle A\times B} の部分集合のことであったが,この概念を拡大して一般に A 1 × A 2 × ⋅ ⋅ ⋅ × A n {\displaystyle A_{1}\times A_{2}\times \cdot \cdot \cdot \times A_{n}} の部分集合のことをこれらの集合の元の間の n {\displaystyle n} 元関係といい,特に A 1 = A 2 = ⋅ ⋅ ⋅ = A n = A {\displaystyle A_{1}=A_{2}=\cdot \cdot \cdot =A_{n}=A} の場合は集合 A {\displaystyle A} の上の n {\displaystyle n} 元(内部)関係という.
集合の有限直積 A 1 × A 2 × ⋅ ⋅ ⋅ × A n {\displaystyle A_{1}\times A_{2}\times \cdot \cdot \cdot \times A_{n}} から集合 B {\displaystyle B} への写像 f {\displaystyle f} は n {\displaystyle n} 項写像,または n {\displaystyle n} 変数の写像といわれ f : A 1 , A 2 , ⋅ ⋅ ⋅ , A n → B {\displaystyle f:A_{1},A_{2},\cdot \cdot \cdot ,A_{n}\to B} で表される.またこのとき直積の元 ( a 1 , a 2 , ⋅ ⋅ ⋅ , a n ) {\displaystyle (a_{1},a_{2},\cdot \cdot \cdot ,a_{n})} における f {\displaystyle f} の値は f ( a 1 , a 2 , ⋅ ⋅ ⋅ , a n ) {\displaystyle f(a_{1},a_{2},\cdot \cdot \cdot ,a_{n})} で表される.この a k {\displaystyle a_{k}} を写像 f {\displaystyle f} の第 k {\displaystyle k} 項という.二項以上の写像は一般に多項写像といわれる.
f {\displaystyle f} が有限直積からの半写像のときも同様の定義と表記法とを用いる.
4.6 集合 A {\displaystyle A} において A n {\displaystyle A^{n}} から A {\displaystyle A} への写像, または半写像はそれぞれ A {\displaystyle A} 上の n {\displaystyle n} 項演算, または n {\displaystyle n} 項半演算ともいわれる.ただし n = 1 {\displaystyle n=1} のときは単項演算,単項半演算といい,このとき f ( x ) {\displaystyle f(x)} のかわりにしばしば x f {\displaystyle x^{f}} の形で表す. f {\displaystyle f} が A {\displaystyle A} 上の二項演算(または二項半演算,以下同様)のときは §1 で例示したように, これに適当な演算記号 ⊥ {\displaystyle \bot } 等を与え, f ( x , y ) {\displaystyle f(x,y)} のかわりに x ⊥ y {\displaystyle x\bot y} の形で表すのが普通である.
関係や演算に関する議論ではその元数や項数によって本質的な差異が起こらぬことが多い. 以下このような場合代表として二元関係,二項演算について解説する. 同じ議論が一般の n {\displaystyle n} 元関係, n {\displaystyle n} 項演算についても拡張,適用できることは各自確かめられたい.
4.7 ρ , σ {\displaystyle \rho ,\sigma } はそれぞれ集合 A , B {\displaystyle A,B} 上の二元関係, ⊥ , ⊤ {\displaystyle \bot ,\top } はそれぞれ A , B {\displaystyle A,B} 上の二項演算, f {\displaystyle f} は A {\displaystyle A} から B {\displaystyle B} への写像とする.
もし f {\displaystyle f} が条件
をみたすならば, f {\displaystyle f} は関係 ρ {\displaystyle \rho } を σ {\displaystyle \sigma } に移すといい, また条件
をみたすとき f {\displaystyle f} は 演算 ⊥ {\displaystyle \bot } を ⊤ {\displaystyle \top } に移すという.
例えば log {\displaystyle \log } は正の実数の集合 R + {\displaystyle \mathbf {R} ^{+}} から実数の集合 R {\displaystyle \mathbf {R} } への写像で、 R + {\displaystyle \mathbf {R} ^{+}} 上の順序と積演算をそれぞれ R {\displaystyle R} 上の順序と和演算とに移す.
また X = { x ∈ R | x > − 1 } {\displaystyle X=\{x\in R|x>-1\}} とし、 x , y ∈ X {\displaystyle x,y\in X} のとき
x ∗ y = x + y + x y {\displaystyle x*y=x+y+xy}
とおけば X {\displaystyle X} は ∗ {\displaystyle *} によって群となることがわかる. 実は ∗ {\displaystyle *} は R + {\displaystyle R^{+}} 上の積演算を f ( x ) = x − 1 {\displaystyle f(x)=x-1} によって X {\displaystyle X} の上に移して作られた演算である.
特に集合 A , B {\displaystyle A,B} 上に同一の記号 ρ {\displaystyle \rho } で書かれた二元関係 ρ {\displaystyle \rho } があり(または A = B {\displaystyle A=B} で f : A → A {\displaystyle f:A\to A} のとき)、条件
をみたすとき f {\displaystyle f} は 関係 ρ {\displaystyle \rho } を保存する といい, 同様に A , B {\displaystyle A,B} 上に同じ記号 ⊥ {\displaystyle \bot } で書かれた二項演算があり (または A = B {\displaystyle A=B} で f : A → A {\displaystyle f:A\to A} のとき),条件
をみたすとき, f {\displaystyle f} は 演算 ⊥ {\displaystyle \bot } を保存する という.
例えば x ∈ R + {\displaystyle x\in R^{+}} に対して f ( x ) = x 2 {\displaystyle f(x)=x^{2}} とおけばこれは R + {\displaystyle R^{+}} 上の自然な順序 ≦ {\displaystyle \leqq } を保存するが,この写像は R {\displaystyle R} 上では ≦ {\displaystyle \leqq } を保存しない. 一般に二つの順序集合の間の順序を保存する写像は 増加的 であるという。
x ∈ R {\displaystyle x\in R} に対して f ( x ) = − x {\displaystyle f(x)=-x} とおけば f {\displaystyle f} は R {\displaystyle R} 上で演算 + {\displaystyle +} は保存するが,積は保存しない.

4.8 ⊥ {\displaystyle \bot } は二つの集合 A , B {\displaystyle A,B} 上に定義された二項演算, f : A → B {\displaystyle f:A\to B} は ⊥ {\displaystyle \bot } を保存する写像とする. このとき 4.3 で示した f ( a ) = f ( b ) {\displaystyle f(a)=f(b)} のとき a ∼ b {\displaystyle a\sim b} として定義された A {\displaystyle A} 上の同値関係 ∼ {\displaystyle \sim } は条件
をみたす.実際仮定から f ( a ) = f ( b ) {\displaystyle f(a)=f(b)} で f ( c ) = f ( d ) {\displaystyle f(c)=f(d)} . f {\displaystyle f} は ⊥ {\displaystyle \bot } を保存するから f ( a ⊥ c ) = f ( a ) ⊥ f ( c ) = f ( b ) ⊥ f ( d ) = f ( b ⊥ d ) {\displaystyle f(a\bot c)=f(a)\bot f(c)=f(b)\bot f(d)=f(b\bot d)} .よって a ⊥ c ∼ b ⊥ d {\displaystyle a\bot c\sim b\bot d} .
一般に A {\displaystyle A} 上に同値関係 ∼ {\displaystyle \sim } があり,それが A {\displaystyle A} 上の演算 ⊥ {\displaystyle \bot } についての上の両立性をみたすとき, ∼ {\displaystyle \sim } は ⊥ {\displaystyle \bot } と両立するという.このとき ∼ {\displaystyle \sim } による類別 U {\displaystyle {\mathfrak {U}}} の二つの同値類を X , Y {\displaystyle X,Y} とし,ある x ∈ X {\displaystyle x\in X} と y ∈ Y {\displaystyle y\in Y} とについて x ⊥ y {\displaystyle x\bot y} を含む同値類を Z {\displaystyle Z} とすれば, ∼ {\displaystyle \sim } の両立性はすべての a ∈ X {\displaystyle a\in X} と b ∈ Y {\displaystyle b\in Y} とについて a ⊥ b ∈ Z {\displaystyle a\bot b\in Z} であることを意味する.すなわち a ∈ X , b ∈ Y {\displaystyle a\in X,b\in Y} ならば a ⊥ b ∈ Z {\displaystyle a\bot b\in Z} となる同値類 Z {\displaystyle Z} は X {\displaystyle X} と Y {\displaystyle Y} から一意的に定まる.この Z {\displaystyle Z} を X ⊥ Y {\displaystyle X\bot Y} と定義すれば ⊥ {\displaystyle \bot } は U {\displaystyle {\mathfrak {U}}} 上の演算となり, A {\displaystyle A} から U {\displaystyle {\mathfrak {U}}} への標準射影 p {\displaystyle p} は ⊥ {\displaystyle \bot } を保存する.