順序対

数学における順序対（じゅんじょつい、テンプレート:Lang-en-short）は、一口に言えば対象を「対」にしたものである。二つの対象 テンプレート:Mvar の順序対をふつうは テンプレート:Math で表す。ここで、「順序」対において対象の現れる順番は重要であることに注意しなければならない、すなわち テンプレート:Math でない限り テンプレート:Math という対と テンプレート:Math という対とが相異なるテンプレート:Efn2。

順序対 テンプレート:Math において、対象 テンプレート:Mvar を第一成分 (first entry, first component), 対象 テンプレート:Mvar を第二成分 (second entry, second component) などと呼ぶ。場合によっては、第一、第二座標や、左射影・右射影ともいう。

順序対のことを二つ組とか長さ テンプレート:Math の列（計算機科学方面ではリスト）とも呼ぶ。あるいは、スカラー（数量）の順序対は二次元の（数）ベクトルである。順序対の成分となる対象として、別の順序対を取ることもでき、それによって[[順序組|順序 テンプレート:Mvar-組]]の再帰的定義が可能になる。例えば、順序三つ組 テンプレート:Math を、ひとつの対を別の対へ入れ子にした テンプレート:Math として定義できる。

直積集合やその部分集合である二項関係（これは対応と言っても同じであり、また従って当たり前のように目にする写像や函数もこれに含まれる）はZFという数学基礎論的な公理体系を背景とした順序対を用いて定義される。

一般論

テンプレート:Math をふたつの順序対とするとき、順序対の特徴づけ (characteristic property) あるいは定義性質 (defining property）とは

テンプレート:Math となるのは テンプレート:Math かつ テンプレート:Math のとき、かつそのときに限る

というものである。第一成分が集合 テンプレート:Mvar の元で、第二成分が集合 テンプレート:Mvar の元となるような順序対全体の成す集合は、テンプレート:Mvar と テンプレート:Mvar との直積集合と呼ばれ、テンプレート:Math と書かれる。テンプレート:Math 上の二項関係とは、テンプレート:Math の部分集合のことである。

注

数学の広範な分野において記号 テンプレート:Math はさまざまな意味で用いられ、そうしたものの中で顕著な例はたとえば実数直線上の開区間を挙げることができるだろう。記号の意味は文脈に完全に依存しており、意味を取るためには文脈に注意しなければならないテンプレート:Sfnテンプレート:Sfn。そうして時には、区別の明確化のために順序対を テンプレート:Math などの少し異なる記号で表すこともある（が、そういった記号もやはり他で多義的に用いられている）。

順序対 テンプレート:Mvar が与えられたとき、その第一および第二成分への射影はそれぞれ テンプレート:Math および テンプレート:Math のように書くのがふつうである（左射影・右射影の意味で テンプレート:Math のように書いてもよい）。この文脈では、自然に テンプレート:Mvar-組 テンプレート:Mvar が第 テンプレート:Mvar-成分への射影 テンプレート:Math を使って考えられる（必ずしも再帰的でない取り扱いができる）。

直観的な定義

入門書の類いにおいては、順序対の定義としてやや不正確だが直観的に テンプレート:Quote というような形で与えるものがある。こういった場合、順序対の理解のために集合の場合との比較を持ってくるのが通例である: たとえば、集合 テンプレート:Math の元として テンプレート:Mvar と テンプレート:Mvar が区別できるには、テンプレート:Mvar は相異なるものでなければならないが、順序対 テンプレート:Math ではその必要が無い。また、集合では元の書き並べ方を変えてももとと意味が変わることはない (テンプレート:Math) が、順序対では並べる順番が異なればそれらは別の順序対 (テンプレート:Math) である

このような「定義」は、記述的に与えられたにすぎず、また並べる「順番」というのも直観的に与えられたものでしかないから、厳密な意味での定義と呼ぶには不十分である。それでも大抵の場合はこのような感覚的な捉え方で問題となることはなく、順序対はそのようなものとして受け止められていると考えられるテンプレート:Sfn。

もう少し正確な取り扱いをするには、上で述べた「順序対の定義性質」を満たすものという役割が数学における順序対の意味の全てであると捉えることになる。そういう立場では、順序対とは順序対の定義性質を対応する公理とするテンプレート:Ill2として扱うという見方ができる。1954年に出版されたブルバキの『集合論』テンプレート:Lang ではこのやり方が取られている。しかしこれは順序対の存在と定義性質の両方を公理的に仮定しなければならないのが難であるテンプレート:Sfn。

順序対を厳密に取り扱う別な方法としては、集合論の文脈で形式的に定義してしまうというのがある。やり方はいくつかあるが、何れも存在と特徴付けを集合論の公理から証明可能という点で優位性がある。そういった定義のなかでもっともよく用いられるのがカシミール・クラトフスキーによるもの（後述）であり、その定義は1970年に出版されたブルバキ『集合論』の第二版で用いられた。順序対を直観的に導入する教科書でも、クラトフスキーによる厳密な定義に演習問題の中で言及するといったものも少なくない。

集合論による順序対の定義

集合論による数学の基礎付けというパラダイムに則れば、全ての数学的対象はある種の集合として定義される。したがって、順序対を原始概念と考えないならば、順序対もまた集合として定義されなければならないテンプレート:Efn2。順序対の集合論的定義を以下にいくつか挙げる。

ウィーナーの定義

ウィーナーが初めて順序対の集合論的定義:

$(a,b):=\{\{\{a\},\mathrm{\varnothing }\},\{\{b\}\}\}$

を提唱したのは1914年のことであるテンプレート:Efn2。ウィーナーはこの定義によって『プリンキピア・マテマティカ』における型が集合として定義できるようになることを注意している。『プリンキピア・マテマティカ』では型、したがって任意のアリティを持つ関係の全体を原始概念として採用するものであった。

ハウスドルフの定義

テンプレート:Harvtxt とほぼ同時期にハウスドルフは

$(a,b):=\{\{a,1\},\{b,2\}\}$

という順序対の定義を提唱した。「ここで、テンプレート:Math および テンプレート:Math は、テンプレート:Mvar とも テンプレート:Mvar とも異なる、相異なるふたつの対象である」テンプレート:Sfn

クラトフスキーの定義

テンプレート:Harvtxt は今日的に広く受け入れられている順序対 テンプレート:Math の定義テンプレート:Sfnテンプレート:Efn2

$(a,b{)}_{\text{K}}:=\{\{a\},\{a,b\}\}$

を提唱した。注目すべきは、これが第一成分と第二成分が等しいときにも

$p=(x,x)=\{\{x\},\{x,x\}\}=\{\{x\},\{x\}\}=\{\{x\}\}$

として有効な定義になっていることである。

順序対 テンプレート:Mvar が与えられたとき、「テンプレート:Mvar の第一成分が テンプレート:Mvar である」という性質は

$\mathrm{\forall }Y\in p:x\in Y$

として定式化することができる。「テンプレート:Mvar の第二成分が テンプレート:Mvar である」という性質は

$(\mathrm{\exists }Y\in p:x\in Y)\wedge (\mathrm{\forall }{Y}_1,\mathrm{\forall }{Y}_2\in p:Y_1\ne Y_2\to (x\notin Y_1\vee x\notin Y_2))$

と定式化できる。第一成分と第二成分が等しいときは、連言の右側の条件

$(\mathrm{\forall }{Y}_1,\mathrm{\forall }{Y}_2\in p:Y_1\ne Y_2\to (x\notin Y_1\vee x\notin Y_2))$

は テンプレート:Math となることが絶対に無いので、明らかに真である。

順序対の第一座標は

${\pi }_1(p)=\bigcup \bigcap p$

とすることで簡単に取り出せる。第二座標の取り出しは第一座標のそれより難しいが、

${\pi }_2(p)=\{\begin{array}{cc}\bigcup \bigcap p& \text{if }\bigcap p=\bigcup p\\ \bigcup (\bigcup p\setminus \bigcap p)& \text{if }\bigcap p\ne \bigcup p\end{array}$

とすればよい。

上述のクラトフスキーによる順序対の定義は順序対が満足すべき特徴づけ $$(a,b)=(x,y)⟺a=x\wedge b=y$$ を満足するに「相応しい」ものである。ほかにもこれと同じくらい相応しい、同様あるいはより単純な形の定義として

クラトフスキーの定義の変形版

• $(a,b{)}_{\text{reverse}}:=\{\{b\},\{a,b\}\},$
• $(a,b{)}_{\text{short}}:=\{a,\{a,b\}\},$
• $(a,b{)}_{\text{01}}:=\{\{0,a\},\{1,b\}\}$テンプレート:Efn2

などが存在する。reverse（逆順）版はあまり使われないが、クラトフスキーの定義の自明な変形版であり、もとの定義で見たこと以外の特徴としてとくに見るべきものは無い。short（省略）版はその名の通り、もとの定義にブレースの組が三つあったことに比べて、ふたつの組に減っている。short 版が順序対の特徴付けを満足することの証明には、ZFCの正則性公理が必要であるテンプレート:Sfn。さらに、自然数の集合論的構成を認めるならば、自然数の "テンプレート:Math" は集合 テンプレート:Math として定義されるが、これは順序対 テンプレート:Math と区別が付かない。

クワイン–ロッサーの定義

テンプレート:Harvs はウィラード・ヴァン・オーマン・クワインに負うところよる自然数のア・プリオリな定義を必要とする順序対の定義を採用している。テンプレート:Mathbf を自然数全体の成す集合とし、函数

$\phi (x)=(x\setminus \mathbb{N})\cup \{n+1:n\in (x\cap \mathbb{N})\}$

を定義する。この函数を適用するには、ただ テンプレート:Mvar に属するどの自然数も テンプレート:Math 増やせばいい。とくに、テンプレート:Math は最小の自然数である テンプレート:Math を含まないので、任意の集合 テンプレート:Mvar に対し

$\phi (x)\ne \{0\}\cup \phi (y)$

が成立する。これを用いて順序対 テンプレート:Math を

$(A,B)=\{\phi (a):a\in A\}\cup \{\phi (b)\cup \{0\}:b\in B\}$

と定義する。この対から テンプレート:Math を含まない元をすべて取り出して、テンプレート:Mvar の適用を取り消せば テンプレート:Mvar が得られる。同様に、テンプレート:Math を含む元を考えれば テンプレート:Mvar を復元することができる。

型理論および公理的集合論 NF のような副産物において、クワイン-ロッサー対は、対とその成分とが同じ型を持つため、「型レベル」テンプレート:Lang の順序対と呼ばれる。その意味でこの定義は、順序対として定義される写像が、その引数よりも 1 だけ高い階の型を持つことを許すという点で有利である。この定義は、自然数全体の成す集合が無限集合である場合にのみうまくいく。これは NF ではそうなっているが、型理論や NFU においてはそうではない。ロッサーはそのような型レベルの順序対（あるいは「型が 1 だけ上がる」順序対）の存在性が無限公理を含意することを示した。クワイン集合論の文脈での順序対の広範な議論は テンプレート:Harvtxt を参照せよ。

カントール–フレーゲの定義

集合論の初期（カントールの逆理の出現以前）、カントールはフレーゲに従い、関係の概念は原始概念として認めたうえで、二つの集合の順序対をそれらの集合の間に成り立つ関係全体の成すクラス $$(x,y)=\{R:xRy\}$$として定義したテンプレート:Sfn。

この定義は現代的に定式化されたほとんどの集合論では許容されないが、たとえば集合の濃度を与えられた集合と等濃な集合全体の成すクラスとして定義する方法論と似て整然としたものであるテンプレート:Sfn。

モースの定義

モース＝ケリー集合論では真のクラスを自由に扱うことができる テンプレート:Harv。モースは成分が集合のみならず真のクラスであるような順序対を定義した（クラトフスキーの定義ではそのようなことはできない）。モースはまず、クラトフスキーの方法で成分が集合となる順序対を定義し、それから順序対 テンプレート:Math を

$(x\times \{0\})\cup (y\times \{1\})$

として「再定義」した。これに現れる直積は集合上のクラトフスキー対からなる。この第二段階で、成分が真のクラスとなるような順序対というものが可能になる。また、上述のクワイン-ロッサーの定義でも成分を真のクラスとすることができる。

圏論

集合の圏における圏論的な直積 テンプレート:Math は、第一成分が テンプレート:Mvar に属し、第二成分が テンプレート:Mvar に属する順序対全体の成す集合を表現する。この文脈では上で述べた順序対の特徴づけは、直積の普遍性と集合 テンプレート:Mvar の元が（ある一元集合）テンプレート:Mathbf から テンプレート:Mvar への射と同一視されるという事実とからの帰結である。別の対象が同じ普遍性を持つかもしれないが、それらはすべて自然同型である。

参考文献

• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Cite book
• テンプレート:Citation (The publisher has graciously consented to permit diffusion of this monograph via the web. Copyright is reserved.)
• テンプレート:Cite book
• テンプレート:Cite journal
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Citation