集合論の言葉による二項関係と写像の表現

前回の記事では順序対や直積集合を定義したが、二項関係や写像は直積集合の部分集合と定義されるので、前回の記事でその準備が整ったことになる。そこで、今回は二項関係と写像について述べる。

二項関係

二項関係はおおざっぱに言えば2つのモノに対して定められる関係で、モノによってその関係が成立したりしなかったりする。たとえば自然数の大小関係は自然数同士の二項関係であり、$1\leq 2$ は成立して $4\leq 3$ は成立しない。

この記事シリーズではもうお馴染みだが、この二項関係というモノもやはり集合として定義する。

定義$x$, $y$ をモノ (集合) とする。このとき $x\times y$ の部分集合を二項関係とよぶ。$R$ が二項関係であるとき、$\langle z,w\rangle \in R$ であることを $zRw$ と書き、$z$ と $w$ に $R$ の関係があるとみなす。

大雑把に言えば、$R$ の関係にあるという設定にしたい二者による対をすべて集合 $R$ に属させることで、関係を集合として定義する。

この定義によって、これから先、直積集合の部分集合を記述する機会が格段に増える。そこで、その記述のために内包的記法の新しい書き方を導入する。「$z\in x$, $w\in y$ であって $\psi(z,w)$ を満たすような順序対 $\langle z,w \rangle$ のみがすべて属する集合」を\[\{\langle z,w\rangle\in x\times y \mid \psi(z,w)\}\]で書き表すことにする。この新しい記法を使わなくても同じモノを\[\{t\in x\times y \mid \exists z\exists w[t=\langle z,w\rangle, \psi(z,w)]\}\]と従来の方法で表記できるので、これは単に書き方の簡略化にすぎず、新たに集合の存在を保証するようなものではない。

二項関係の例

例として、次の二項関係 $R$ を考えよう。\[R=\{\langle x,y\rangle\in \omega\times\omega \mid x\in y\}\]つまり、$x$ と $y$ が自然数であって $x\in y$ であれば $\langle x,y\rangle$ は $R$ に属し (つまり $xRy$ であり)、そうでなければ属さない。具体例を出すと、$0\in 2$, $1\in 2$ であるので $0R2$, $1R2$ であり、$2\not\in 2$, $3\not\in 2$ であるので $2R2$, $3R2$ ではない。

この $R$ がどんな関係かを探るために自然数の定義を思い返すと、各自然数は「自身以前の自然数だけがすべて属する集合」として定義されている。このことから、上の $R$ は、$x$ が自然数 $y$ 以前の自然数であれば $xRy$ であり、そうでなければ $xRy$ ではない関係と言える。この関係は実は、素朴には「大小関係」と呼んでいた関係に一致する。現に、素朴に「$x$ は $y$ より小さい」を満たすと思われる自然数 $x$, $y$ を思い浮かべると $xRy$ となっており、「$x$ は $y$ より小さくない」を満たすと思われる自然数 $x$, $y$ を思い浮かべると $xRy$ とはなっていない。つまり、この $R$ こそが集合論の言葉で自然数の大小関係を記述したモノとして定義できる。

定義二項関係 $R$ が\[R=\{\langle x,y\rangle\in \omega\times\omega \mid x\in y\}\]を満たすとする。この関係を自然数の大小関係と呼び、$xRy$ であること (つまり $\langle x,y\rangle\in R$ であること) を $x\lt y$ もしくは $y\gt x$ と書き、それぞれを「$x$ は $y$ より小さい」もしくは「$y$ は $x$ より大きい」と表現する。

ようやく、自然数同士の関係を1つ定義することができた。今後、二項関係を用いて四則演算を定義した暁には、それを利用して様々な二項関係が定義できるだろう。

写像

写像は2つの集合の間に定義される。「$x$ から $y$ への写像」とは「$x$ に属するモノを一つ与えると、$y$ に属するモノをちょうど一つだけ返すようなもの」のことである。実は似たものは中学数学でも扱われ、『○に属するモノ』を『数』に変えれば関数として習ったものになる。

たとえば、「$\omega$ に属するモノ $x$ を与えると、$\omega$ に属する $x\cup\{x\}$ (つまり $x$ の次の数) を返すようなもの」は $\omega$ から $\omega$ への写像である。この写像に1を与えれば2が返り、5を与えれば6が返る。ここで言い回しを変えてみることをしよう。すると「$x$ を与えると $y$ が返る」ことを「$x$ と $y$ に関係がある」ということもできるだろう。つまり、写像は二項関係の一種として考えることができる。たとえば上の例を二項関係 $R$ としてとらえると、\[1R2,\; 5R6,\; xR(x\cup\{x\})\]ということになる。

ただし、二項関係なら何でも写像になるわけではない。たとえば $0R1$, $0R2$ の両方が成立すると、0を与えると1が返り2も返ることになるので「ちょうど一つだけ返す」 という写像の性質を満たさない。また、$1Rx$ を満たす $x$ が存在しなければ「1を与えても何も返さない」ことになってしまう。以上のことから、写像は二項関係のうち特定の条件を満たすものである。

定義$f\subset x\times y$ であるとする。次の条件を満たすとき、$f$ は $x$ から $y$ への写像である; $a\in x$ である限り、$b\in y$ がただ一つ存在して $\langle a,b\rangle \in f$ となる。

$f$ が $x$ から $y$ への写像であることを $f:x\to y$ と書く。このときの $x$ を $f$ の始域 (もしくは定義域) とよび、$y$ を $f$ の終域とよぶ。

$f$ が写像であるなら、$x$ に属する $a$ に対して $\langle a,b\rangle \in f$ となる唯一の $b$ を $f(a)$ と書き、「$f$ に $a$ を与えたときの値」とよぶ。

この定義に則って先ほど例示した写像を $S$ として定義すると\[S=\{\langle x,y\rangle\in \omega\times \omega\mid y=x\cup\{x\}\}\]となる。こうするとたとえば $S(1)=2$, $S(5)=6$ であり、自然数 $x$ に対して\[S(x)=x\cup\{x\}\]である。

写像の合成

2つの写像 $f: x\to y$, $g:y\to z$ があった場合、その2つを元に得られる新たな写像である『合成』が広く知られているのでここに記す。$g$ と $f$ の合成とは「$x$ に属するモノ $a$ を与えたときに $z$ に属するモノ $g(f(a))$ を返すような写像」である。この合成がいつでも一つだけ存在することの証明はここでは省略する。

集合論の言葉を使って定義しておく。

定義$f: x\to y$, $g:y\to z$ とする。このとき二項関係\[\{\langle a,c \rangle \in x\times z \mid c=g(f(a))\}\]は写像であり、この写像を $g$ と $f$ の合成と呼び、$g\circ f$ と書く。

二項関係と写像の相等

これまでの定義を採用したとき、二項関係同士や写像同士はどういうときに「等しい・同じ」であるのかを確認していく。双方ともモノ (集合) として定義したので、外延性の公理に準じて考えればよい。

外延性の公理に準ずるので、2つの二項関係 $R$ と $S$ は、一方にしか属さないような順序対が存在すれば等しくない ($R\neq S$) し、一方に属する順序対が必ずもう一方にも属していれば等しい ($R=S$)。

もう少し二項関係風の言い回しに変えてみると、$xRy$ と $xSy$ の一方しか満たさないような $x$, $y$ が存在すれば $R\neq S$ であり、どんな $x$, $y$ を持ち出しても $xRy$ と $xSy$ のどちらも満たさないかどちらも満たすのであれば $R=S$ である。

写像風にも言い換えてみよう。その場合、$R(x)\neq S(x)$ となるような $x$ が存在すれば $R\neq S$ であり、どんな $x$ を持ち出しても $x$ が $R$ と $S$ のいずれかの始域に属している限り $R(x)=S(x)$ となるなら $R=S$ である。なお、外延性の公理と写像の定義を見比べると、どんな写像同士であっても始域が一致しなければ等しくないとわかる。

定理2つの写像の始域が等しくないとき、それらの写像は等しくない。

(証明) 写像 $f$ の始域を $x$ とし、$g$ の始域を $y$ とし、$x\neq y$ とする。このとき、外延性の公理により $x$ と $y$ の一方にしか属さないモノ $t$ が存在する。仮に $t$ が $x$ のみに属するとすると、写像の定義より $\langle t,z\rangle\in f$ となる $z$ が存在するが、$g$ の始域に $t$ は属さないので $\langle t,z\rangle\not\in g$ である。一方にしか属さない順序対があるので $f\neq g$。

途中の「$t$ が $x$ のみに属する」という仮定が誤っていれば「$t$ が $y$ のみに属する」ことになるが、その場合でも同様に $f\neq g$ が導かれる。

一方で、終域は一致していなくても写像同士が等しいことはありうる。たとえば上述の $S:\omega\to\omega$ と以下の $S':\omega\to\omega\setminus\{0\}$\[S'=\{\langle x,y\rangle\in\omega\times(\omega\setminus\{0\})\mid y=x\cup\{x\}\}\]について考えると、始域は一致しており、$x$ が始域に属する限り $S(x)=S'(x)$ であるので、$S=S'$ である。外延性の公理からじかに考えても一方にしか属さない順序対がないのでやはり $S=S'$ である。

この記事シリーズでは上述の定義を用いるのでこのようになっているが、圏論などでは終域が違えば別の写像であるとみなしたい場合もあり、その場合は少々異なる定義を持ち出すこともある。

二項関係や写像からなる集合

以前、順序対を定義したときに、順序対からなる集合として直積集合の存在を示した。今回も、二項関係や写像からなる集合について述べておく。

まず「$x$ に属するモノと $y$ に属するモノの二項関係だけがすべて属する集合」について述べる。といっても「$x$ に属するモノと $y$ に属するモノの二項関係」は「$x\times y$ の部分集合」のことなので、それだけがすべて属する集合とはつまり $x\times y$ の冪集合 $\mathfrak{P}(x\times y)$ のことである。冪集合の存在証明は以前に済ませたとおりである。

次に「$x$ から $y$ への写像だけがすべて属する集合」について述べる。「$x$ から $y$ への写像」とは「$x$ に属するモノと $y$ に属するモノの二項関係」のうち特殊な条件を満たすもののことだったから、$\mathfrak{P}(x\times y)$ に属するモノのうち、その条件を満たすものを内包的記法で取り出せばよい。すなわち\[\{f\in\mathfrak{P}(x\times y) \mid \text{$f$ は写像である}\}\]が「$x$ から $y$ への写像だけがすべて属する集合」である。ここでは条件部分を日本語で書いたが、論理式で書くこともできるので、この内包的記法で示された集合は存在する。この集合は配置集合とよばれ、$\text{Map}(x,y)$ や $y^x$ と書かれる。

写像に関する記法

ここで写像の記法について補足しておく。上でも出てきた\[S(x)=x\cup\{x\}\]という式は「写像 $S$ に $x$ 与えると $x\cup\{x\}$ が返る」と解釈することができるが、このことを\[S:x\mapsto x\cup\{x\}\]のように矢尻がある矢印を使って書き表せる。始域や終域も同時に表したい場合は\[S:\omega\to\omega; x\mapsto x\cup\{x\}\]と書けばよい。

また、写像そのものの表し方にもいくつか違う書き方がある。$f:x\to y$ としたとき、この写像 $f$ のことを $f(i)$ と表せる値の集まりとして\[(f_i)_{i\in x}\]や\[(f_i \mid i\in x)\]と書くことがある。この記法を使えば、上で例示した $S$ のことを\[(x\cup\{x\} \mid x\in\omega)\]と表せる。

単射と全射

単射や全射は、特別な条件を満たす写像のことである。素朴な集合論でも用いられる表現であり、「すべてのモノが集合である」論理を扱うにあたっての特記事項は特にないのだが、これらについて全く知らないと後々の話をしづらくなるのでここで説明しておく (注: 以下、この記事シリーズではまだ定義していない実数やその四則演算を例に用いる)

単射とは、「異なるモノを与えたら必ず異なるモノが返る写像」のことである。たとえば上で挙げた $S$ については $n\neq m$ なら必ず $S(n)\neq S(m)$ となるので単射である。一方で、実数から実数への写像 $f:x\mapsto x^2$ については異なるモノ $2$ と $-2$ に対して同じモノ $4$ が返るので単射ではない。

全射とは、「どうやっても返らないモノが終域に属さない写像」のことである。より砕けた言い方をすれば、終域に属するモノを余すことなく使っている写像のことである。たとえば上で挙げた $S$ については、終域 $\omega$ に 0 が属するのに何を与えても 0 が返らないので全射ではない。一方で、上で挙げた $S'$ については、与えるモノを適切に設定すれば終域 $\omega\setminus\{0\}$ に属するどんなモノも返るようにできるので全射である。この例のように、どんな写像であっても終域を適切に小さくすれば全射になる。

単射であり全射でもある写像のことを全単射とよぶ。全単射は『列の並び替え』を考えたり『個数』を定義したりする際に重要な概念である。