集合と写像

目的は，公理的集合論そのものではなく，そこで保証された道具を知ることだけなので，悪しからず．

集合

集まり

何かのもの（元と呼ばれる）を集めたものを集まりと呼び，（自分の知る限り）以下の操作が許される．

集合

ZFC公理系を満たす集まりのことを集合と呼ぶ．

空集合

元を持たない集合 ∃ ⁡ ∅ , ∀ ⁡ 𝑥 , ( 𝑥 ∉ ∅ ) が（一意的に）存在する．この∅を空集合と呼ぶ．

冪集合

集合𝐴を与える．すべての部分集合の集合を冪集合と呼び， 2 𝐴 と表す．

選択公理

集合の集合𝑋を与える．各元𝐴∈𝑋から元を一つずつとってきたものも集合になる，という公理のことを選択公理(axiom of choice)と言う．

写像

写像

集合𝐴,𝐵を与える．

∀⁡𝑎∈𝐴に対し，𝑏∈𝐵を一つ対応させる．この対応規則を 𝑓 : 𝐴 → 𝐵 , 𝑎 ↦ 𝑏 のように表し，これを写像(mapping)と表す．∀⁡𝑎∈𝐴に対して選んだ𝑏∈𝐵のことを 𝑓 ⁡ ( 𝑎 ) ≔ 𝑏 と書く．

このとき，𝐴を𝑓の始域(domain)（または定義域），𝐵を𝑓の終域(codomain)と呼ぶ．

特に𝐴=𝐵のとき，𝑓を𝐴上の写像，または変換(transformation)と呼ぶ．

写像の合成

を与える．

𝑔 ∘ 𝑓 : 𝐴 → 𝐶 , 𝑎 ↦ 𝑔 ⁡ ( 𝑓 ⁡ ( 𝑎 ) ) 𝑓と𝑔の合成（写像）と呼ぶ．

恒等写像

集合𝐴を与える．

1 𝐴 : 𝐴 → 𝐴 , 𝑎 ↦ 𝑎 を𝐴上の恒等写像と呼ぶ．

集合の圏

とする圏を集合の圏と呼び，𝐒𝐞𝐭と表す．

冪集合上の写像

を与える．

このとき𝑓は，それぞれの冪集合に関する自然な写像 2 𝐴 → 2 𝐵 , 𝑋 ↦ { 𝑓 ⁡ ( 𝑥 ) | 𝑥 ∈ 𝑋 } を誘導する．この写像のことも（記号の濫用で）𝑓と表す．

像

集合𝐴,𝐵と写像 𝑓 : 𝐴 → 𝐵 を与える．

∀ ⁡ 𝑎 ∈ 𝐴 に対し， 𝑓 ⁡ ( 𝑎 ) を𝑎の𝑓による像と呼ぶ．

∀ ⁡ 𝑋 ∈ 2 𝐴 に対し， 𝑓 ⁡ ( 𝑋 ) を𝑋の𝑓による像と呼ぶ．

𝑓 ⁡ ( 𝐴 ) のことを単に𝑓の像(image)，または値域と呼ぶ．

特性函数

集合𝐴とその部分集合 𝑋 ∈ 2 𝐴 ，二元集合 { 0 , 1 } を与える．

このとき𝑋は写像 𝜒 𝑋 : 𝐴 → { 0 , 1 } , 𝑥 ↦ 𝜒 𝑋 ≔ { 1 𝑥 ∈ 𝑋 0 𝑥 ∉ 𝑋 を誘導する．これを（𝐴上の）特性函数と呼ぶ．

逆に写像 𝜒 : 𝐴 → { 0 , 1 } （これも特性函数と呼ばれる）を与えたとき， 𝑓 − 1 ⁡ ( 1 ) ∈ 2 𝐴 であり， 𝜒 = 𝜒 𝑓 − 1 ⁡ ( 1 ) を満たす．つまり，特性函数と冪集合には一対一の関係がある．冪集合の2はこれが理由となる．

濃度

集合の元の数を一般化した概念を濃度と呼ぶ．

関係

関係，そして特に重要な同値関係を扱う．

関係

集合𝐴,𝐵を与える．

直積集合の部分集合 𝐺 ∈ 2 𝐴 × 𝐵 に対し，記号∈の代わりに∼を用いて， ( 𝑥 , 𝑦 ) ∈ 𝐺 ⇔ 𝑥 ∼ 𝑦 ( 𝑥 , 𝑦 ) ∉ 𝐺 ⇔ 𝑥 ≁ 𝑦 と表す．∼を（𝐺が誘導する）𝐴と𝐵の間の（二項）関係((binary) relation)と呼ぶ．

また，𝐺を関係∼グラフ(graph)と呼ぶ．

特に，𝐵=𝐴のとき，𝐴上の関係と呼ぶ．

関係の合成

集合𝐴,𝐵,𝐶，𝐴と𝐵の関係∼，𝐵と𝐶の関係 ∼ ′ を与える．

∀ ⁡ ( 𝑎 , 𝑐 ) ∈ 𝐴 × 𝐶 , 𝑎 ∼ ′ ∘ ∼ 𝑐 ⇔ ∃ ⁡ 𝑏 ∈ 𝐵 , 𝑎 ∼ 𝑏 ∼ ′ 𝑐 で定義される𝐴と𝐶の関係を，∼と ∼ ′ の合成(composition)と呼ぶ．

関係としての等号

集合𝐴,𝐵を与える．

集合の元として等しいことを表す等号=𝐴,𝐵は，関係の合成に関する恒等射をなす．

つまり，任意の関係∼に対し以下を満たす： ( ∼ ∘ = 𝐴 ) = ∼ = ( = 𝐵 ∘ ∼ )

関係の圏

とする圏を関係の圏と呼び，𝐑𝐞𝐥と表す．

反対関係

集合𝐴,𝐵を与える．

𝐴と𝐵の間の関係は，自然な𝐵と𝐴の間の関係 𝑏 ∼ op 𝑎 ⇔ 𝑎 ∼ 𝑏 を誘導する．これを∼の反対関係(opposite/converse relation)と呼ぶ．

左右一意的・一対一

集合𝐴,𝐵を与える．

𝐴と𝐵の間の関係 ∼ ∈ 𝐑𝐞𝐥 ⁡ ( 𝐴 , 𝐵 ) で，以下を満たすものを左一意的(left-unique)と呼ぶ． ∀ ⁡ 𝑏 ∈ 𝐵 , ∀ ⁡ 𝑎 1 , 𝑎 2 ∈ 𝐴 , 𝑎 1 ∼ 𝑏 ∩ 𝑎 2 ∼ 𝑏 ⇒ 𝑎 1 = 𝑎 2

𝐴と𝐵の間の関係 ∼ ∈ 𝐑𝐞𝐥 ⁡ ( 𝐴 , 𝐵 ) で，以下を満たすものを右一意的(right-unique)と呼ぶ． ∀ ⁡ 𝑎 ∈ 𝐴 , ∀ ⁡ 𝑏 1 , 𝑏 2 ∈ 𝐵 , 𝑎 ∼ 𝑏 1 ∩ 𝑎 ∼ 𝑏 2 ⇒ 𝑏 1 = 𝑏 2

左一意的かつ右一意的な関係を一対一(one-to-one)と呼ぶ．

ここでの一意的は，あくまで「存在すれば」一意である．

左右全域的・対応

集合𝐴,𝐵を与える．

𝐴と𝐵の間の関係 ∼ ∈ 𝐑𝐞𝐥 ⁡ ( 𝐴 , 𝐵 ) で，以下を満たすものを左全域的(left-entire, left-total)と呼ぶ． ∀ ⁡ 𝑎 ∈ 𝐴 , ∃ ⁡ 𝑏 ∈ 𝐵 , 𝑎 ∼ 𝑏

𝐴と𝐵の間の関係 ∼ ∈ 𝐑𝐞𝐥 ⁡ ( 𝐴 , 𝐵 ) で，以下を満たすものを右全域的(right-entire, right-total)と呼ぶ． ∀ ⁡ 𝑏 ∈ 𝐵 , ∃ ⁡ 𝑎 ∈ 𝐴 , 𝑎 ∼ 𝑏

左全域的かつ右全域的な関係を対応(correspondence)と呼ぶ．

左右可逆関係

集合𝐴,𝐵を与える．

𝐴と𝐵の間の関係 ∼ ∈ 𝐑𝐞𝐥 ⁡ ( 𝐴 , 𝐵 ) で，以下の同値な条件のいずれか（ゆえに全て）を満たすものをモノ関係(monic relation)または左可逆(left-invertible)と呼ぶ．

𝐴と𝐵の間の関係 ∼ ∈ 𝐑𝐞𝐥 ⁡ ( 𝐴 , 𝐵 ) で，以下の同値な条件のいずれか（ゆえに全て）を満たすものをエピ関係(epic relation)または右可逆(right-invertible)と呼ぶ．

条件の同値性の証明

左可逆の方を示す．実は ∼ − 1 は反対関係に他ならない，というのを念頭においておこう．

  1. ∼の左一意性の左全域性を仮定する． ∼ op が右全域的であることに注意すると， ∀ ⁡ 𝑎 1 ∈ 𝐴 に対し， ∀ ⁡ 𝑎 2 ∈ 𝐴 , ∃ ⁡ 𝑏 ∈ 𝐵 , 𝑎 1 ∼ 𝑏 ∼ op 𝑎 2 ⇔ 𝑎 1 = 𝑎 2 が成り立つから， ∼ − 1 = ∼ op が存在する．
  2. ∼ − 1 が存在するとき，関係の圏のモノ射になることは自明．
  3. 関係の圏のモノ射になることを仮定し，背理法で∼の左一意性の左全域性を示す．グラフ𝐺⊂𝐴×𝐵が誘導する関係を∼𝐺と表す．
    • ∼が左一意的でない，つまり ∃ ⁡ 𝑏 ∈ 𝐵 , ∃ ⁡ 𝑎 1 ≠ 𝑎 2 ∈ 𝐴 , 𝑎 1 ∼ 𝑏 ∩ 𝑎 2 ∼ 𝑏 を満たすと仮定すると，この ∃ ⁡ 𝑎 1 ≠ 𝑎 2 ∈ 𝐴 ，任意の空でない集合𝐶， 𝑐 ∈ 𝐶 に対し， ∼ ∘ ∼ { ( 𝑐 , 𝑎 1 ) } = ∼ ∘ ∼ { ( 𝑐 , 𝑎 2 ) } を満たすが， ∼ { ( 𝑐 , 𝑎 1 ) } ≠ ∼ { ( 𝑐 , 𝑎 2 ) } なので矛盾．
    • ∼の左全域性でない，つまり ∃ ⁡ 𝑎 ∈ 𝐴 , ∀ ⁡ 𝑏 ∈ 𝐵 , 𝑎 ≁ 𝑏 を満たすと仮定すると，この𝑎∈𝐴，任意の濃度2以上の集合𝐶， 𝑐 1 ≠ 𝑐 2 ∈ 𝐶 に対し， ∼ ∘ ∼ { ( 𝑐 1 , 𝑎 ) } = ∼ ∘ ∼ { ( 𝑐 2 , 𝑎 ) } を満たすが， ∼ { ( 𝑐 1 , 𝑎 ) } ≠ ∼ { ( 𝑐 2 , 𝑎 ) } なので矛盾．

一対一対応・可逆関係

集合𝐴,𝐵を与える．

𝐴と𝐵の間の関係 ∼ ∈ 𝐑𝐞𝐥 ⁡ ( 𝐴 , 𝐵 ) で，以下の同値な条件のいずれか（ゆえに全て）を満たすものを一対一対応(one-to-one correspondence)，可逆関係(invertible relation)，同型関係(isomorphic relation)等と呼ぶ．

∼ − 1 ≔ ∼ op のことを∼の逆関係(inverse relation)と呼ぶ．

条件の同値性は，左一意的かつ右一意的かつ左一意的かつ右一意的の言い換えなので自明．

関係の合併

集合𝐴,𝐵，𝐴と𝐵の関係 ∼ , ∼ ′ とそれぞれのグラフ 𝐺 , 𝐺 ′ を与える．

𝐺 ∪ 𝐺 ′ が誘導する関係を，∼と ∼ ′ の合併(union)と呼び， ∼ ∪ ∼ ′ と表す．

関係の交叉

集合𝐴,𝐵，𝐴と𝐵の関係 ∼ , ∼ ′ とそれぞれのグラフ 𝐺 , 𝐺 ′ を与える．

𝐺 ∩ 𝐺 ′ が誘導する関係を，∼と ∼ ′ の交叉(intersection)と呼び， ∼ ∩ ∼ ′ と表す．

関係の差

集合𝐴,𝐵，𝐴と𝐵の関係 ∼ , ∼ ′ とそれぞれのグラフ 𝐺 , 𝐺 ′ を与える．

𝐺 ∖ 𝐺 ′ が誘導する関係を，∼と ∼ ′ の差()と呼び， ∼ ∖ ∼ ′ と表す．

集合上の関係

とりあえず名前のついた特別な関係を確認する．

反射関係

集合𝐴を与える．

𝐴上の関係∼で，以下を満たすものを反射関係(reflexive relation)と呼ぶ．

∀ ⁡ 𝑎 ∈ 𝐴 , 𝑎 ∼ 𝑎

𝐴上の関係∼で，以下を満たすものを非反射関係(irreflexive relation)と呼ぶ．

∀ ⁡ 𝑎 ∈ 𝐴 , 𝑎 ≁ 𝑎

対称関係

集合𝐴を与える．

𝐴上の関係∼で，以下を満たすものを対称関係(symmetric relation)と呼ぶ．

∀ ⁡ 𝑎 , 𝑏 ∈ 𝐴 , 𝑎 ∼ 𝑏 ⇒ 𝑏 ∼ 𝑎

𝐴上の関係∼で，以下を満たすものを反対称関係(antisymmetric relation)と呼ぶ．

∀ ⁡ 𝑎 , 𝑏 ∈ 𝐴 , 𝑎 ∼ 𝑏 ∩ 𝑏 ∼ 𝑎 ⇒ 𝑎 = 𝑏

𝐴上の関係∼で，以下を満たすものを非対称関係(asymmetric relation)と呼ぶ．

∀ ⁡ 𝑎 , 𝑏 ∈ 𝐴 , 𝑎 ∼ 𝑏 ⇒ 𝑏 ≁ 𝑎

推移関係

集合𝐴を与える．

𝐴上の関係∼で，以下を満たすものを推移関係(transitive relation)と呼ぶ．

∀ ⁡ 𝑎 , 𝑏 , 𝑐 ∈ 𝐴 , 𝑎 ∼ 𝑏 , 𝑏 ∼ 𝑐 ⇒ 𝑎 ∼ 𝑐

𝐴上の関係∼で，以下を満たすものを非推移関係(intransitive relation)と呼ぶ．

∀ ⁡ 𝑎 , 𝑏 , 𝑐 ∈ 𝐴 , 𝑎 ∼ 𝑏 , 𝑏 ∼ 𝑐 ⇒ 𝑎 ≁ 𝑐

完全関係

集合𝐴を与える．

𝐴上の関係∼で，以下を満たすものを完全関係(total relation)と呼ぶ．

∀ ⁡ 𝑎 , 𝑏 ∈ 𝐴 , 𝑎 ∼ 𝑏 または 𝑏 ∼ 𝑎

以上のうちいくつかを同時に満たすこともある．多くが関係の代わりに順序と呼ばれ，それらは順序理論で扱う（希望的観測）．もう一つ重要なのが同値関係で，あとで扱っている．

閉包と簡約

関係∼に対し，適当な関係を合併することで，上に挙げたような性質を満たすようにできる．このうち最小のもの（そのような関係全ての交叉）を閉包(closure)と呼ぶ．

具体的には以下がある．

反射閉包

集合𝐴，𝐴上の関係∼を与える．

∼ = ≔ ∼ ∪ = と定義される関係を∼の反射閉包(reflexive closure)と呼ぶ．

対称閉包

集合𝐴，𝐴上の関係∼を与える．

∼とその反対関係の合併 ∼ ∪ ∼ op で定義される関係を∼の対称閉包(symmetric closure)と呼ぶ．

推移閉包

集合𝐴，𝐴上の関係∼を与える．

⋃ 𝑛 = 1 ∞ ∼ ∘ 𝑛 で定義される関係を∼の推移閉包(transitive closure)と呼ぶ．

逆に，関係∼に，適当な関係との交叉または差をとることで，上に挙げたような性質を満たすようにできる．このうち最大のもの（そのような関係全ての合併）を簡約(reduction)と呼ぶ．

具体的には以下がある．

非反射簡約

集合𝐴，𝐴上の関係∼を与える．

∼ ≠ ≔ ∼ ∖ = と定義される関係を∼の非反射簡約(irreflexive reduction)と呼ぶ．

同値関係と商集合

分割

集合𝐴を与える．

部分集合の集合 𝑃 ⊂ 2 𝐴 が𝐴の分割(partition)であるとは，以下を満たすことをいう．

  • ∅ ∉ 𝑃
  • ⋃ 𝑋 ∈ 𝑃 𝑋 = 𝐴
  • ∀ ⁡ 𝑋 , 𝑌 ∈ 𝐴 , 𝑋 ≠ 𝑌 ⇒ 𝑋 ∩ 𝑌 = ∅

分割の分割っぽさ

集合𝐴とその分割𝑃を与えると，以下が成り立つ．

∀ ⁡ 𝑎 ∈ 𝐴 , ∃! ⁡ 𝑋 ∈ 𝑃 , 𝑎 ∈ 𝑋

分割ないしは「類別」の定義としては妥当だろうが，分割になっているかの判定に使うには，抽象度が高い．応用上便利な方法は，関係を使う方法である．その準備をしよう．

同値関係

集合𝐴を与える．

𝐴上の関係∼で，以下を満たすものを同値関係(equivalence relation)と呼ぶ．

反射律
∀ ⁡ 𝑎 ∈ 𝐴 , 𝑎 ~ 𝑎
対称律
∀ ⁡ 𝑎 , 𝑏 ∈ 𝐴 , 𝑎 ∼ 𝑏 ⇒ 𝑏 ∼ 𝑎
推移律
∀ ⁡ 𝑎 , 𝑏 ∈ 𝐴 , 𝑎 ∼ 𝑏 または 𝑏 ∼ 𝑎

同値類・商集合

集合𝐴と同値関係∼を与える．

𝑎∈𝐴に対し， [ 𝑎 ] ≔ { 𝑥 ∈ 𝑆 | 𝑎 ∼ 𝑥 } を𝑎の∼による同値類と呼ぶ．

すべての同値類の集合を 𝑆 ∕ ∼ ≔ { [ 𝑎 ] | 𝑎 ∈ 𝑆 } と表し，商集合と呼ぶ．

∼が誘導する写像 𝐴 → 𝐴 ∕ ∼ : 𝑎 ↦ [ 𝑎 ] を標準射影canonical projection)と呼ぶ．

同値類と分割は本質的に等価

商集合は分割であり，これらは一対一に対応する．

同型定理

核対? 等化子?

定義より明らかだが，一応代数学的な同型定理は以下となる．

同型定理

集合𝐴,𝐵とをの間の写像 𝑓 : 𝐴 → 𝐵 を与えると，以下が成り立つ．

  • 𝑓の核対?は𝐴の商集合．
  • 𝑓の像 𝑓 ⁡ ( 𝐴 ) は𝐵の部分集合．
  • 𝑓の核対?と𝑓の像 𝑓 ⁡ ( 𝐴 ) は自然な全単射をもつ．特に等濃．

最後に，時々使う同値閉包を明示しておく．