関係 (集合論)

  • 2019/03/15 09:00
この記事は, 旧ブログから移植された記事です. よって, その内容として, 旧ブログに依存した文脈が含まれている可能性があります. 予めご了承下さい.

関係 (集合論) について復習.

一般的な関係

いま, 二つの要素の順序体を <a,b>\left\lt a, b\right\gt と書くこととする. 他の異なる順序体 <c,b>\left\lt c, b\right\gt に対し, 以下の通り定義する.

<a,b>=<c,d>:=a=c,b=dデカルト積=直積=A×B:={<a,b>aA,bB} \begin{aligned} \left\lt a,b\right\gt=\left\lt c,d\right\gt&:=&a=c, b=d\\ {\rm デカルト積} = {\rm 直積} = A\times B&:=&\left\{\left\lt a,b\right\gt\mid a\in A, b\in B\right\} \end{aligned}

このとき順序体の要素を nn 個に拡張したものを nn-tuple といい, 以下の通り定義する.

nn-tuple の同値関係と直積

<a1,a2,,an>=<b1,b2,,bn>:=(a1=b1,a2=b2,,an=bn)(1) \left\lt a_1,a_2,\cdots,a_n\right\gt=\left\lt b_1,b_2,\cdots,b_n\right\gt:=(a_1=b_1,a_2=b_2,\cdots,a_n=b_n) \tag{1} デカルト積=直積=A1×A2××An=i=1nAi:={<a1,a2,,an>a1A1,a2A2,,anAn}(2) {\rm デカルト積} = {\rm直積} = A_1\times A_2\times\cdots\times A_n=\prod_{i=1}^{n}A_i:=\left\{\left\lt a_1,a_2,\cdots,a_n\right\gt\mid a_1\in A_1,a_2\in A_2,\cdots,a_n\in A_n\right\} \tag{2}

なお (2)(2) より An:=(A1=A2==An)A^n:=(A_1=A_2=\cdots =A_n) が自明に導ける. いま集合 AA から BB に対する二項関係 RA×BR\subseteq A\times B があって, <a,b>R\left\lt a,b\right\gt\in R ならば aabb は関係 RR にあるといい, R(a,b)R(a,b) または aRbaRb と書く.

R:={<a,b>aA,bB,aRb}R:=\{\left\lt a,b\right\gt\mid a\in A,b\in B,aRb\}

(a,b)∉R(a,b)\not\in R ならば aabb は関係 RR にないといい, R(a,b)\overline{R}(a,b) または aRba\overline{R}b と書く. このとき A=BA=B ならば二項関係 R(A2=A×B)R\subseteq (A^2=A\times B)AA 上の二項関係という1.

例えば, 自然数の集合 N\mathbb{N} に対し, その同値関係==” を順序体を用いて新たに

R:={<n,n>nN}N2R:=\{\left\lt n,n\right\gt\mid n\in \mathbb{N}\}\subseteq\mathbb{N}^2

と定義すると a,bNa,b\in \mathbb{N} に対して aR=ba=ba R_=b\Leftrightarrow a=b である. また, 集合 X=1,2,3X={1,2,3} に対し, その順序関係 R>X2R_\gt\subseteq X^2 を大なりの関係 “>\gt” とすると R>R_\gt

R>={<2,1>,<3,1>,<3,2>}R_\gt=\{\left\lt 2,1\right\gt, \left\lt 3,1\right\gt, \left\lt 3,2\right\gt\}

となる. ここで, 逆関係を導入する. 関係 RR の逆関係は BB から AA への関係, すなわち

R1:={<b,a>aA,bB,aRb}R^{-1}:=\{\left\lt b,a\right\gt\mid a\in A, b\in B, aRb\}

と定義される. 従って, 例えば集合 XX に対する R>R_\gt の逆関係は R>1=<1,2>,<1,3>,<2,3>R_\gt^{-1}={\left\lt 1,2\right\gt, \left\lt 1,3\right\gt, \left\lt 2,3\right\gt} である.

二項関係は, より一般化することができる.

nn 項関係

いま複数の集合の直積の部分集合, すなわち nn 項関係 Ri=1nAiR\subseteq\prod_{i=1}^{n}A_i があって, <a1,a2,,an>R\left\lt a_1,a_2,\cdots,a_n\right\gt\in R ならば a1,a2,,ana_1,a_2,\cdots,a_n は 関係 RR にあるといい, R(a1,a2,,an)R(a_1,a_2,\cdots,a_n) と書く.

R:={<a1,a2,,an>a1A1,a2A2,,anAn,R(a1,a2,,an)}i=1nAiR:=\{\left\lt a_1,a_2,\cdots,a_n\right\gt\mid a_1\in A_1,a_2\in A_2,\cdots,a_n\in A_n, R(a_1,a_2,\cdots,a_n)\}\subseteq\prod_{i=1}^{n}A_i

また <a1,a2,,an>⊈R\left\lt a_1,a_2,\cdots,a_n\right\gt\not\subseteq R ならば a1,a2,,ana_1,a_2,\cdots,a_n は 関係 RR にないといい, R(a1,a2,,an)\overline{R}(a_1,a_2,\cdots,a_n) と書く.

ここで, 本ブログ内で特に断りなく使われる一般的な関係に関する記号の表記, その意図について表明しておく.

本ブログで使われる一般的な関係に関する記号表記

任意の二項関係 \lesssim の要素 <a,b> \left\lt a,b\right\gt\in\ \lesssim に対し:
  •  :=<a,b><a,b> ,ab\prec\ :={\left\lt a,b \right\gt\mid \left\lt a, b\right\gt\in\ \lesssim, a\not=b}
  •  :=<a,b><a,c>∉  かつ <c,b>∉ \ll\ :={\left\lt a,b\right\gt\mid\left\lt a, c\right\gt\not\in\ \lesssim\ {\rm かつ}\ \left\lt c,b\right\gt\not\in\ \lesssim}

すなわち, xyx\prec yxx は真に yy の前にある, xyx\ll yxxyy の直前にあることを意味する.

主な二項関係の規則

主な二項関係における規則を以下に定義する.

反射律

二項関係 RA×BR\subseteq A\times B, また xABx\in A\cap B があって, <x,x>R\left\lt x,x\right\gt\in R が存在するとき RR は反射律を満たすという.

例えば, 実数の集合 R\mathbb{R} をとってみると, 任意の xR^\forall x\in\mathbb{R} に対して xxx\leq x であるから \leqR\mathbb{R} の下で反射律を満たす. しかし, x<xx\lt x は成立しないので, <\ltR\mathbb{R} の下で反射律を満たさない.

対称律

二項関係 RA×BR\subseteq A\times B, また x,yABx,y\in A\cap B があって, <x,y>R\left\lt x,y\right\gt\in R ならば <y,x>R\left\lt y,x\right\gt \in R が存在するとき, RR は対称律を満たすという.

例えば, 実数の集合 R\mathbb{R} をとってみると, 自明な例でいえば, 任意の x,yR^\forall x,y\in\mathbb{R} に対して x=yx=y ならば y=xy=x なので ==R\mathbb{R} の下で対称律を満たす. しかし, x<yx\lt y ならば y<xy\lt x ではないので, <\ltR\mathbb{R} の下で対称律を満たさない. また, 別の例として, 例えば平面状のすべての三角形から成る集合 AA と, 相似の関係 RR を組み合わせると RRAA 上で対称律を満たす. R={<x,y>x,yA,x と y は相似}A2R=\{\left\lt x,y\right\gt\mid x,y\in A,x\ {\rm と}\ y\ {\rm は相似}\}\subseteq A^2 なお, これは同値律を満たす. 対称律の特徴を挙げると:

  • 必ずしも x=yx=y ではない
  • 真に大きい/小さい関係はあり得ない. R R\not=\ \prec かつ R R\not=\ \succ (すべてのありとあらゆる集合上で xyならばy⊀xx\prec y ならば y\not\prec x なので)

反対称律

二項関係 RA×BR\subseteq A\times B, また x,yABx,y\in A\cap B があって, <x,y>R\left\lt x,y\right\gt\in R に対し <y,x>R\left\lt y,x\right\gt\in R が存在するならば x=yx=y のとき, RR は反対称律を満たすという.

例えば, 集合 A={a1,a2}A=\{a_1,a_2\} に対して 二項関係を:

  • R={<a1,a1>,<a2,a2>}R=\{\left\lt a_1,a_1\right\gt,\left\lt a_2,a_2\right\gt\} とおくと, RRAA 上で (対称律を満たし) 反対称律を満たす. なお, これは同値律を満たす.
  • R={<a1,a1>,<a1,a2>}R=\{\left\lt a_1,a_1\right\gt,\left\lt a_1,a_2\right\gt\} とおくと, RRAA 上で (対称律を満たさないが) 反対称律を満たす.
  • R={<a1,a2>,<a2,a1>}R=\{\left\lt a_1,a_2\right\gt,\left\lt a_2,a_1\right\gt\} とおくと, RRAA 上で (対称律を満たすが) 反対称律を満たさない.

反対称律の特徴を挙げると:

  • 対象的な二項関係が存在するとき, 必ず x=yx=y

推移律

二項関係 RA×BR\subseteq A\times B, また x,y,zABx,y,z\in A\cap B があって, <x,y>,<y,z>R\left\lt x,y\right\gt,\left\lt y,z\right\gt\in R ならば <x,z>R\left\lt x,z\right\gt \in R が存在するとき, RR は推移律を満たすという.

例えば, 実数の集合 R\mathbb{R} をとってみると, 任意の x,y,zR^\forall x,y,z\in\mathbb{R} に対して xyx\leq y かつ yzy\leq z ならば xzx\leq z なので \leqR\mathbb{R} の下で推移律を満たす. しかし, 例えば自然数の集合 N\mathbb{N} に対して R={<a,b>a,b,cN,a=b2 かつ b=c2 ならば a=c2 を満たす}N2R=\left\{\left\lt a, b\right\gt\mid a,b,c\in\mathbb{N}, a=b^2\ {\rm かつ}\ b=c^2\ {\rm ならば}\ a=c^2\ {\rm を満たす}\right\}\subseteq\mathbb{N}^2 としたとき, 任意の x,yAx,y\in A に対し必ずしも <x,y>R\left\lt x,y\right\gt\in R が存在するとは限らない (反例: 16=4216=4^2 かつ 4=224=2^2 だが 162216\not=2^2) ので, RRN\mathbb{N} の下で推移律を満たさない.

主な二項関係

前順序

二項関係 RR が集合 AA 上で反射律, 推移律を同時に満たすとき, RRAA 上の前順序関係という.

これは要するに, じゃんけんのような, 3 すくみ, すなわち グー \lesssim パー \lesssim チョキ \lesssim グー \lesssim\cdots といった循環関係がないこと, グラフで表したときに有向非巡回グラフとなることを要請している.

同値

前順序関係 RR が集合 AA 上で対称律を満たすとき, RRAA 上で同値律を満たすという. また:
  • {yXxRy}\{y\in X\mid xRy\}xx の同値類といい, [x]R\left[x\right]_R[x]\left[x\right] と書く. このときの xx は, 同値類 [x]\left[x\right] の代表元という
  • 集合 AA 上の同値関係 RR の同値類全体から成る集合 {[a]aA}\{[a]\mid a\in A\} を商集合といい, A/RA/R と書く

まず自明な例でいえば, == は, 空でない任意の集合上で同値関係にあるといえる. ほかに, 例えば, 整数の集合 Z\mathbb{Z} について RR を整数 pZp\in\mathbb{Z} を法とする合同関係 p\equiv_p とおくと, RRZ\mathbb{Z} 上の同値関係となる. R=p={<m,n>m,nZ,mと n は p で割ったときの余りが等しい}Z2R=\equiv_p=\{\left\lt m,n\right\gt\mid m,n\in\mathbb{Z}, m {\rm と}\ n\ {\rm は}\ p\ {\rm で割ったときの余りが等しい}\}\subseteq\mathbb{Z}^2 一つ一つ確認してみると

  • 反射律: 任意の mZm\in\mathbb{Z} に対して mm=0pm-m=0\cdot p なので mpmm\equiv_p m
  • 推移律: 任意の m,n,kZm,n,k\in\mathbb{Z} に対して mpnm\equiv_p n かつ npkn\equiv_p k と仮定すると, ある d,dZd,d'\in\mathbb{Z} に対して mn=dpm-n=d\cdot p かつ nk=dpn-k=d'\cdot p で, このとき mk=(mn)+(nk)=(d+d)pm-k=(m-n)+(n-k)=(d+d')\cdot p である. d+dZd+d'\in\mathbb{Z} なので, mpkm\equiv_p k
  • 対称律: 任意の m,nZm,n\in\mathbb{Z} に対して mpnm\equiv_p n と仮定すると, ある dZd\in\mathbb{Z} に対して mn=dpm-n=d\cdot p だから nm=(d)pn-m=(-d)\cdot p で, dZ-d\in\mathbb{Z} だから npmn\equiv_p m

と同値律を満たすことがわかる.

同値類や商集合の例として, 集合 X=1,3,6,10,11,15,16NX={1,3,6,10,11,15,16}\subseteq \mathbb{N} の要素 11 を代表元とし, いまその同値関係を 55 を法とした合同2で考えると, 11 の同値類 [1]R=x1x(mod5)\left[1\right]_R={x\mid 1\equiv x\pmod{5}}[1]R=1,6,11,16\left[1\right]_R={1,6,11,16} である3. また,

[1]R={1,6,11,16}[3]R={3}[6]R={1,6,11,16}[10]R={10,15}[11]R={1,6,11,16}[15]R={10,15}[16]R={1,6,11,16}\begin{aligned} \left[1\right]_R&=&\left\{1,6,11,16\right\}\\ \left[3\right]_R&=&\left\{3\right\}\\ \left[6\right]_R&=&\left\{1,6,11,16\right\}\\ \left[10\right]_R&=&\left\{10,15\right\}\\ \left[11\right]_R&=&\left\{1,6,11,16\right\}\\ \left[15\right]_R&=&\left\{10,15\right\}\\ \left[16\right]_R&=&\left\{1,6,11,16\right\} \end{aligned}

であるので, X/R=1,6,11,16,10,15,3X/R={{1,6,11,16},{10,15},{3}} である.

半順序

前順序関係 RR が集合 AA 上で反対称律を満たすとき, RRAA 上の半順序関係といい, AA を半順序集合 (poset) という.

例えば, 集合族上の包含関係 \subset は以下の通り半順序である.

AAAB かつ BA ならば A=BAB かつ BC ならば AC\begin{aligned} \begin{array}{l} A\subset A\\ A\subset B{\rm\ かつ}\ B\subset A{\rm\ ならば}\ A=B\\ A\subset B{\rm\ かつ}\ B\subset C{\rm\ ならば}\ A\subset C \end{array} \end{aligned}

半順序集合が定義できれば, (最(大|小), 極(大|小))(要素|元)が定義できる.

(最(大|小)|極(大|小))(要素|元)

半順序集合 AA の要素 a0Aa_0\in A について

  • aA s.t. a0a^\exists a\in A\ {\rm s.t.}\ a_0\lesssim a なる aa が存在しないとき a0a_0AA の最大(要素|元)といい, maxA\max A と書く. とくに AA が複素数の部分集合 ACA\subseteq\mathbb{C} ならば, maxA\max A を最大値という
  • aA s.t. aa0^\exists a\in A\ {\rm s.t.}\ a\lesssim a_0 なる aa が存在しないとき a0a_0AA の最小(要素|元)といい, minA\min A と書く. とくに AA が複素数の部分集合 ACA\subseteq\mathbb{C} ならば, minA\min A を最小値という

また aAa\in A に対し

  • aa0a\gtrsim a_0 ならば a=a0a=a_0 のとき a0a_0AA の極大(要素|元)という
  • aa0a\lesssim a_0 ならば a=a0a=a_0 のとき a0a_0AA の極小(要素|元)という

AA に最小元が存在するとき, AA は点付き (pointed) であるという. また, 最大値, 最小値あるいは極大値, 極小値を総じて extremum という (参考文献 1, 参考文献 2).

例えば, 自然数全体の集合 N\mathbb{N} の最小要素は 00 であるが, 最大要素は存在しない. 実数全体の集合 R\mathbb{R} には最(大|小)要素が存在しない4. 集合 X=x1,x2,x3X={x_1,x_2,x_3} に対して順序集合 ((X),X,)(\wp(X)-{\emptyset,X},\leq)5 の極大要素は x1,x2,x1,x3,x2,x3{x_1,x_2},{x_1,x_3},{x_2,x_3}, また極小要素は x1,x2,x3{x_1},{x_2},{x_3} である.

半順序集合が定義できれば, (上|下)(界|限)が定義できる.

(上|下)(界|限)

半順序集合 ((X),)(\wp(X),\leq) の空でない部分集合 AA\not =\emptyset の任意の要素 aAa\in A に対し,
  • xX s.t. ax^\exists x\in X\ {\rm s.t.}\ a\lesssim x なる xx が存在するならば AA は上に有界であるといい, xxAA の上界という.
  • xX s.t. xa^\exists x\in X\ {\rm s.t.}\ x\gtrsim a なる xx が存在するならば AA は下に有界であるといい, xxAA の下界という.
  • AA の上界全体の集合 B={xXax}B=\{x\in X | a\lesssim x\} の最小要素 minB\min BAA の上限, または最小上界といい, supA\sup A と書く.
  • AA の下界全体の集合 B={xXxa}B=\{x\in X | x\lesssim a\} の最大要素 maxB\max BAA の下限, または最大下限といい, infA\inf A と書く.

例えば, 集合 X=1,12,13,14,X={1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\cdots} について, 上界および最大値は supA=maxA=1\sup A=\max A=1, 下界は infA=0\inf A=0, 最小値は存在しないといえる. また, 実数全体の集合 RR の空でない部分集合が(上|下)に有界ならば, その(上|下)限が必ず存在する. これは, ワイエルストラスの定理といわれる.

有向 (directed) 集合

集合 AA\not=\emptyset前順序関係 RR との組 (A,R)(A,R) に対し, AA の任意の有限部分集合 XAX\subseteq A の上界 supXA\sup X\in A が存在するとき, AA を有向 (directed) 集合という.

有向集合は, 反対称律を要請されていないので, 必ずしも半順序集合とはならないことに注意. 例えば, 集合 A={a1,a2,a3}A=\{a_1,a_2,a_3\} と関係 R={<a1,a1>,<a1,a2>,<a1,a3>,<a2,a2>,<a3,a3>,<a3,a1>,<a3,a2>}R=\{\left\lt a_1,a_1\right\gt,\left\lt a_1,a_2\right\gt,\left\lt a_1,a_3\right\gt, \left\lt a_2,a_2\right\gt,\left\lt a_3,a_3\right\gt,\left\lt a_3,a_1\right\gt,\left\lt a_3,a_2\right\gt\} の組は, 半順序でない有向集合である (<a1,a3>,<a3,a1>R\left\lt a_1,a_3\right\gt,\left\lt a_3,a_1\right\gt\in R だが, a1=a3a_1=a_3 は要請していない).

図 1: 集合 A={a1,a2,a3}A=\{a_1,a_2,a_3\} と関係 R={<a1,a1>,<a1,a2>,<a1,a3>,<a2,a2>,<a3,a3>,<a3,a1>,<a3,a2>}R=\{\left\lt a_1,a_1\right\gt, \left\lt a_1,a_2\right\gt,\left\lt a_1,a_3\right\gt, \left\lt a_2,a_2\right\gt,\left\lt a_3,a_3\right\gt, \left\lt a_3,a_1\right\gt,\left\lt a_3,a_2\right\gt\} の有向グラフによる図示

全順序

半順序関係 RR が集合 AA 上の任意の要素に対して比較可能であるとき, RRAA 上の全順序関係という.

任意の全順序集合の有限部分集合は明らかに最大要素がただ 1 つ存在するため有界であるので, 有向集合である. その他, 例えば, 大小関係 \leq は自然数の集合 N\mathbb{N} 上で全順序関係である.

ω\omega

半順序関係 RR と集合 AA の組 (A,R)\left(A,R\right) に対し, 二項関係 {<a0,a1>,<a1,a2>,}R\left\{\left\lt a_0,a_1\right\gt,\left\lt a_1,a_2\right\gt,\cdots\right\}\subseteq R に関する AA の元の列 a0 R a1 R a2 Ra_0\ R\ a_1\ R\ a_2\ R \cdotsω\omega 鎖という. 列 <a0,a1,a2,>\left\lt a_0,a_1,a_2,\cdots\right\gt は自然数の集合と 1 対 1 に対応し, ij<ai,aj>Ri\leq j\Rightarrow \left\lt a_i,a_j\right\gt\in R.

ω\omega 鎖は (関係 RR の部分集合と示したように), 自然数の連鎖と同型の半順序集合の部分集合についてをいい, 全順序集合と同じ理由より明らかに有向集合である. 教科書によっては, ω\omega 鎖が上限を持つ構造を cpoω\omega-cpo ということがある.

上記で定義した二項関係と集合間の射について定義する.

単調 (monotone)

半順序関係 R0,R1RR_0,R_1\subseteq R と集合 A0,A1AA_0,A_1\subseteq A の組 (A0,R0),(A1,R1)\left(A_0,R_0\right),\left(A_1,R_1\right) と射 f:A0A1f:A_0\rightarrow A_1 について以下が成りたつとき, ff は単調である (または単調関数) という. a0,a1A0.<a0,a1>R0<f(a0),f(a1)>R1^\forall a_0,a_1\in A_0.\left\lt a_0,a_1\right\gt\in R_0\Rightarrow \left\lt f(a_0),f(a_1)\right\gt\in R_1

ハッセ図

主に半順序集合の図示の方法としてよく使われるハッセ図について, 以下にいくつかの例を示す.

まずは, 入門書でよく見る例題に習い, 自然数全体の集合 N\mathbb{N} の任意の要素 m,nNm,n\in\mathbb{N} について, mmnn を割り切ることを mnm\mid n と書くとき6, 整除関係 \midN\mathbb{N} 上の半順序であることに関して考察しよう.

xxxy かつ yx ならば x=yxy かつ yz ならば xz\begin{aligned} \begin{array}{l} x\mid x\\ x\mid y{\rm\ かつ}\ y\mid x{\rm\ ならば}\ x=y\\ x\mid y{\rm\ かつ}\ y\mid z{\rm\ ならば}\ x\mid z \end{array} \end{aligned}

さて, このような一つの有限半順序集合上の関係は, 図 1 と同様にして, 以下のように有向グラフにより表現できる. いま, 集合 X={nnN,1n10}X=\{n\mid n\in\mathbb{N}, 1\leq n\leq 10\} に対する整除関係による順序を \ll で考えると, xyx\mid y なら yy は必ず xx の後に存在する (xyx\lesssim y) ので, 次のような有向非巡回グラフが書ける7.

図2: 整除の下で \ll の関係における XX の有限グラフによる図示

これをハッセ図では次のように書く.

図3: 整除の下で \ll の関係における XX のハッセ図による図示

有向グラフが xyx\to y というように矢印で順序を表しているのに対して, ハッセ図では yyxx よりも高い位置に置いて, それぞれを線で結ぶ. このときの最小値および下限は 11 であり, 上界は 10,8,6,910,8,6,9 だが 10,8,6,910,8,6,9 を比較不可能であるため, 上限は存在しない.

別の例として, X={a,b,c,d}X=\left\{a, b, c, d\right\} とおいたとき, ac,ad,bc,bda\lesssim c, a\lesssim d, b\lesssim c, b\lesssim d という半順序関係にある集合 (X,)(X,\lesssim) を考えると, 以下のように示せる.

図4: 半順序関係 ac,ad,bc,bda\lesssim c, a\lesssim d, b\lesssim c, b\lesssim d のハッセ図による図示

このときの下界は a,ba,b, 上界は c,dc,d である. 最小元, 最大元, 下限, 上限は a,ba,b および c,dc,d が比較不可能であるため存在しない.

最後にもう 1 つ, 半順序集合 ((x1,x2,x3),)(\wp({x_1,x_2,x_3}), \subset) について考えてみる. 先にも示したように, 集合族上の包含関係 \subset は半順序である. x1,x1x1,x2,\emptyset\subset{x_1},{x_1}\subset{x_1,x_2},\cdots と考えていくと, ハッセ図は次のようになる.

図5: 半順序集合 ((x1,x2,x3),)(\wp({x_1,x_2,x_3}), \subset) のハッセ図による図示

このときの最小元および下限は \emptyset であり, 最大元および上限は x1,x2,x3{x_1,x_2,x_3} である.

半順序集合の拡張

有向半順序 (directed partial order) 集合

半順序関係 RR有向集合 AA の組 (A,R)(A, R) に対し AA を有向半順序 dpo (directed partial order) 集合という.

有向完備半順序 (directed-complete partial order) 集合

半順序集合 AA の任意の有向部分集合 XAX\subseteq A について, XX の上限 supXA\sup X\in A が存在するとき, AA を有向完備半順序 dcpo (directed complete partial order) 集合という.

いま XAX\subseteq A を有限有向部分集合としたとき, 有限半順序集合 AA の部分集合 XX は, AA の半順序関係により必ず有向部分集合となる. つまり, 有限半順序集合は dcpo 集合になる. 従って, 図 3, 図 4, 図 5 で示される集合は dcpo 集合である (上記の定義のニュアンスとして, たまに任意の部分集合が有向部分集合でなければならないと捉えられる場合があるが, そうではなく, あくまで有向部分集合として構成可能な部分集合のうちという意味合いである). 教科書によっては, dcpo を単に完備半順序, また cpo ということがある. また, すべての ω\omega 鎖はその定義より有向集合であるから, dcpo は (その部分集合に ω\omega 鎖が存在する場合) ω\omega 鎖が上限を持つとして ω\omega-cpo である. その逆は必ずしも成り立たない.

連続 (continuous)

dcpo 集合 D,DD,D' について, 単調関数 f:DDf:D\rightarrow D' が以下を満たすとき, (Scott-) 連続 (continuous) であるという. AD.f(supA)=sup{f(a)aA}^\forall A\subseteq D.f(\sup A)=\sup\left\{f(a)\mid a\in A\right\} ここで AA有向集合.

コンパクト (compact)

dcpo RR と集合 DD の組 (D,R)(D,R) に対し, 以下の条件を満たすとき, xDx\in D はコンパクトであるという. AD.<x,supA>RyA.<x,y>R(1)^\forall A\subseteq D. \left\lt x,\sup A\right\gt\in R\Rightarrow ^\exists y\in A.\left\lt x,y\right\gt \in R\tag{\htmlId{compact}{1}} ここで AA は有向集合. なお, 条件式 1\href{#compact}{1} を満たす元全体を次のように書くこともある. K(D):={x条件式 1 を満たすxD}\mathrm{K}(D):=\left\{x\mid\text{条件式}\ \href{#compact}{1}\ \text{を満たす} x\in D\right\}

代数的 (algebraic)

dcpo RR と集合 DD の組 (D,R)(D,R) に対し, 以下の条件を満たすとき, DD は代数的であるという. xD,A={aK(D)<a,x>R}.A は有向集合supA=x^\forall x\in D,A=\left\{a\in\mathrm{K}(D)\mid \left\lt a,x\right\gt\in R\right\}.A\text{ は有向集合}\land\sup A=x

基底 (basis)

dcpo RR と集合 DD の組 (D,R)(D,R) 対し, 以下の条件を満たすとき, AK(D)A\subseteq\mathrm{K}(D)DD の基底という. xD,A={aA<a,x>R}.A は有向集合supA=x^\forall x\in D,A=\left\{a\in A\mid \left\lt a,x\right\gt\in R\right\}.A\text{ は有向集合}\land\sup A=x

ここで AADD の基底であるとき, DD は代数的であり K(D)=A\mathrm{K}(D)=A である.

点付き有向完備半順序 (pointed directed-complete partial order) 集合

次の 2 つの条件を満たす半順序集合 AA点付き有向完備半順序集合 cppo (pointed directed-complete partial order) という.
  1. AAdcpo 集合
  2. AA は最小元をもつ

以下にいくつかの例を示す.

  • 任意の集合 AA について, AA の部分集合全体の集合 P(A)={SSA}\mathcal{P}(A)=\left\{S\mid S\subseteq A\right\} は, 集合の包含関係 \subseteq との組 (P(A),)\left(\mathcal{P}(A),\subseteq\right)cppo となる (さらに, すべての PP(A)P\subseteq\mathcal{P}(A) について PP の上限 supPP(A)\sup P\in\mathcal{P}(A) が存在するから, P(A)\mathcal{P}(A)完備束でもある)
  • 図 3 および 図 5 で示される集合は dcpo でありかつ最小元をもつため cppo だが, 図 4 は最小元をもたないため, cppo ではない
  • (N,)(\mathbb{N}, \leq) は, 有向集合として NN\mathbb{N}\subseteq\mathbb{N} が取れるが, その上限は存在しないので, cppo ではない. ここで, =maxN\infty = \max \mathbb{N} となるように拡張した (N{},)(\mathbb{N}\cup\{\infty\},\leq) で考えると, cppo になる

教科書によっては, cppo を単に完備半順序, また cpo ということがある.

正格, 厳密 (strict)

cppo 集合 D,DD,D' について, 射 f:DDf:D\rightarrow D' が最小元を保つ f(minD)=minDDf(\min D)=\min D\in D' とき, ff は正格または厳密であるという.

二項演算子 ,\land,\lor8 のもとで閉じている空でない集合 LL の任意の要素 x,y,zLx,y,z\in L に対して, 次の三つの束の公理
  1. 可換律:xy=yx,xy=yxx\land y=y\land x, x\lor y=y\lor x
  2. 結合律:(xy)z=x(yz),(xy)z=x(yz)(x\land y)\land z=x\land(y\land z), (x\lor y)\lor z=x\lor(y\lor z)
  3. 吸収律:x(xy)=x,x(xy)=xx\land(x\lor y)=x,x\lor(x\land y)=x

を満たすとき, 集合 LL は束であるといい, (L,,)(L,\land,\lor) と表す. ここで ,\lor,\land はそれぞれ, 結び, 交わりと言われる. いま半順序集合 SS の任意の要素 a,ba,b について, 上限を sup{a,b}:={xmM(xm),xM},M={ma,bm,mS}\sup\left\{a,b\right\}:=\left\{x\mid ^\forall m\in M(x\lesssim m),x\in M\right\}, M=\left\{m\mid a,b\lesssim m,m\in S\right\} 下限を inf{a,b}:={xmM(xm),xM},M={ma,bm,mS}\inf\{a,b\}:=\left\{x\mid ^\forall m\in M(x\gtrsim m),x\in M\right\}, M=\left\{m\mid a,b\gtrsim m,m\in S\right\} と書くこととすると, sup{a,b},inf{a,b}\sup\left\{a,b\right\},\inf\left\{a,b\right\} はそれぞれ ab,aba\lor b,a\land b と同値である. すなわち, 束とは, x,yx, y について上限と下限が存在する半順序集合のことである9. また,

  • LL の任意の部分集合が上限と下限をもつとき, 束 LL をとくに完備束
  • 束の部分集合が束であるとき, その束をとくに部分束
  • LL の任意の要素 x,yL^\forall x,y\in L について f(xy)=f(x)f(y),f(xy)=f(x)f(y)f(x\land y)=f(x)\land f(y), f(x\lor y)=f(x)\lor f(y) を満足する単射 f:L1L2f: L_1\to L_2 が存在するとき束 L1,L2L_1,L_2 は同型
  • 束の任意の要素 x,y,zx,y,z について x(yz)=(xy)(xz),x(yz)=(xy)(xz)x\lor(y\land z)=(x\lor y)\land(x\lor z), x\land(y\lor z)=(x\land y)\lor(x\land z) を満たす束をとくに分配束

という.

例えば, 先の例でも挙げた ((x1,x2,x3),)(\wp({x_1,x_2,x_3}), \subset) は束である. 任意の要素として x1,x2{x_1},{x_2} をとってみると, その上限 supx1,x2\sup{{x_1},{x_2}}x1x1,x2,x2x1,x2{x_1}\subset{x_1,x_2},{x_2}\subset{x_1,x_2} なので, supx1,x2=x1,x2\sup{{x_1},{x_2}}={x_1,x_2} である.

図6: 半順序集合 ((x1,x2,x3),)(\wp({x_1,x_2,x_3}), \subset) のハッセ図による図示, sup{{x1},{x2}}\sup\left\{\left\{x_1\right\},\left\{x_2\right\}\right\} を強調

ハッセ図で考えると, 上方向に辺を辿っていったとき, 各ノードそれぞれが順序比較可能でありかつ最小であるものが上限となる. 例えば

sup{{x1,x2},{x2,x3}}={x1,x2,x3}sup{{x1},{x2,x3}}={x1,x2,x3}sup{,{x1,x2}}={x1,x2}sup{,}=(9) \begin{aligned} \sup\left\{\left\{x_1,x_2\right\},\left\{x_2,x_3\right\}\right\}&=&\left\{x_1,x_2,x_3\right\}\\ \sup\left\{\left\{x_1\right\},\left\{x_2,x_3\right\}\right\}&=&\left\{x_1,x_2,x_3\right\}\\ \sup\left\{\emptyset,\left\{x_1,x_2\right\}\right\}&=&\left\{x_1,x_2\right\}\\ \sup\left\{\emptyset,\emptyset\right\}&=&\emptyset\tag{9} \end{aligned}

となる. 最後の (9)(9) はすべての束の任意の要素について言えることである. すなわち任意の束 LL の任意の要素 xLx\in L に対して supx,x=x\sup{x,x}=x である. これは, 束の公理から導ける, 一般にべき等律といわれる定理である.

べき等律

x,yL,z=(xy)x,y\in L,z=(x\lor y) に対して

sup{x,x}xx=x(x(xy))(公理3:吸収律)=x(xz)(公理3:吸収律)=x(公理3:吸収律) \begin{aligned} \sup\left\{x,x\right\}\leftrightarrow x\lor x&=&x\lor(x\land(x\lor y)) & (\because {\rm \href{#lattice3}{公理3}: 吸収律})\\ &=&x\lor (x\land z)&(\because {\rm \href{#lattice3}{公理3}: 吸収律})\\ &=&x&(\because {\rm \href{#lattice3}{公理3}: 吸収律}) \end{aligned}

ここで一度, 上の定理に加えて考察できるいくつかの事項を羅列する.

  • 下限は, 上限の逆順序で定義されるものである. 例えば, infx1,x2=\inf{{x_1},{x_2}}=\emptyset である
  • 完備束 (L,,)(L,\land,\lor) の任意の部分集合 SLS\subseteq L に対して S=S=\emptyset ならば supS=minL\sup S=\min L, S=LS=L ならば supS=maxD\sup S=\max D である

いま, 分配束 LL の最大元, 最小元をそれぞれ 1,01,0 と書くこととする. 束 LL の任意の要素 x,yLx,y\in L について xy=1,xy=0x\lor y=1,x\land y=0 を満足するとき, xxyy の補元といい, xx' または xˉ\bar{x} と書く. 元 1,01,0 はそれぞれ単位元, 零元である. このときの LL の補元は, 唯一に定まる.

LL の補元の唯一性

x,yLx,y\in LaLa\in L の二つの補元だと仮定する.

x=x0=x(ay)=(xa)(xy)=1(xy)=xy \begin{aligned} x&=&x\lor 0\\ &=&x\lor(a\land y)\\ &=&(x\lor a)\land(x\lor y)\\ &=&1\land(x\lor y)\\ &=&x\land y \end{aligned}

同様に y=xyy=x\lor y となるから x=yx=y.

LL のすべての元が補元をもつとき, LL は可補束, または相補束という. 可補分配束は一般にブール代数である10.

参考文献

  1. Extremum - Wolfram MathWorld 2019/3/15 アクセス.
  2. Maximum and minimum of a function - Encyclopedia of Mathematics 2019/3/15 アクセス.
  3. 赤間世紀, 長田康敬, 玉城史朗 (2006)『情報数学入門』共立出版. ISBN-13: 978-4320018143
  4. “Directed complete partial orders”, http://math.chapman.edu/~jipsen/structures/doku.php/directed_complete_partial_orders 2020/7/9 アクセス.
  5. S. Abramsky, A. Jung: Domain theory. In S. Abramsky, D. M. Gabbay, T. S. E. Maibaum, editors (1994)『Handbook of Logic in Computer Science, vol. III』, Oxford University Press.

  1. 例えば xyxy 座標平面を R2\mathbb{R}^2 と書くのは, それが実数二つのペアの集合と考えられるからである.↩︎

  2. 任意の整数 a,b,c,nNa,b,c,n\in \mathbb{N} に対して ab(modn)ab(modn)ba(modn)ab,bc(modn)ac(modn)\begin{aligned}a\equiv b \pmod n\\ a\equiv b\pmod n&\rightarrow& b\equiv a\pmod n\\ a\equiv b, b\equiv c\pmod n &\rightarrow& a\equiv c\pmod n\end{aligned}

    であることを容易に確かめられる. 従って, 合同は同値関係である.↩︎

  3. これをとくに剰余類という. FYI: エルガマル暗号, ガロア体のセクションを参照.↩︎

  4. 関連: ϵδ\epsilon-\delta 論法↩︎

  5. ここで, (A)\wp(A)(A):=YYA\wp(A):={Y\mid Y\subseteq A} であり, AA の冪集合という. すなわち A=a,bA={a,b} とすると (A)=,a,b,a,b\wp(A)={\emptyset,{a},{b},{a,b}} となる. いまその要素の個数を (A)\left|\wp(A)\right| と書くとすると, (A)\left|\wp(A)\right| は集合 AA の全要素の全組み合わせであるので (A)=3C0+3C1+3C2=7\left|\wp(A)\right|={}_3C_0+{}_3C_1+{}_3C_2=7 となる. 従って, ここで取り上げた例題について丁寧に書き出してみると, (X),X=X,x1,x2,x1,x3,x2,x3,x1,x2,x3,,X\wp(X)-{\emptyset,X}={X,{x_1,x_2},{x_1,x_3},{x_2,x_3},{x_1},{x_2},{x_3},\emptyset}-{\emptyset,X} ということ.↩︎

  6. \mid は整数論の界隈で普遍的な記述である. 「割り切れない」も同様にして ∤\not\mid と書いたりする. FYI: エルガマル暗号↩︎

  7. 11 と自分自身以外の数で割り切れるかを考える. 11 は始点なので, 11 のノードへ向けられる辺はないだろう. 22 について考えてみると, 12,31\mid 2,3 なら 131\mid 3 であるが, 441241\mid 2\mid 4 である. これを全要素について適用していくと図のようになる.↩︎

  8. 論理記号とは無関係であることに注意.↩︎

  9. 半順序集合 SS の任意の要素 x,yx, y に対して supx,y,infx,y\sup{x,y},\inf{x,y} が存在すれば, x,yx, y と順序関係のある zSz\in S に対して sup{x,y}=sup{y,x}sup{sup{x,y},z}=sup{x,sup{y,z}}sup{x,inf{x,y}}=x\begin{aligned}\sup\left\{x,y\right\}&=&\sup\left\{y,x\right\}\\ \sup\left\{\sup\left\{x,y\right\},z\right\}&=&\sup\left\{x,\sup\left\{y,z\right\}\right\}\\ \sup\left\{x,\inf\left\{x,y\right\}\right\}&=&x\end{aligned}

    より束の公理を満たす. 双対の原理より双対についても成り立つ.↩︎

  10. 可補束ついて次の性質が成り立つ. x=x0=11=0x0=xx0=0x1=1x1=x(xy)=xy(xy)=xyxyyx\begin{aligned}x''&=&x\\ 0'&=&1\\ 1'&=&0\\ x\lor 0&=&x\\ x\land 0&=&0\\ x\lor 1&=&1\\ x\land 1&=&x\\ (x\land y)'&=&x'\lor y'\\ (x\lor y)'&=&x'\land y'\\ x\leq y&\leftrightarrow& y'\leq x'\end{aligned}

    面倒なので証明略. ブール代数のエントリにて分配律を用いずに証明しているものがあるので, それで代用できるかと.↩︎


活動継続のためのご支援を募集しています