順序対

数学における順序対（じゅんじょつい、テンプレート:Lang-en-short）は、座標 (coordinate) や射影 (projection) とも呼ばれるふたつの成分 (entry) を持つ対象を総称するものである。順序対では常に、第一成分（第一座標、左射影）と第二成分（第二座標、右射影）の対によって対象が一意に決定される。第一座標が a で第二座標が b であるような順序対は通常、(a, b) で表される。「順序」対という呼称は、a = b でない限り (a, b) という対と (b, a) という対とが異なるという意味を示唆してのものである。

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

一般論

(a₁, b₁), (a₂, b₂) をふたつの順序対とするとき、順序対の特徴づけ (characteristic property or defining property）とは

(a₁, b₁) = (a₂, b₂) となるのは a₁ = a₂ かつ b₁ = b₂ のとき、かつそのときに限る

というものである。順序対を他の順序対の成分にすることができて、このような再帰的定義から順序 n-組（項数 n の順序付けられた配列）の概念が得られる。たとえば、三つ組 (a,b,c) は対を入れ子にした (a, (b,c)) として定義される。このやり方は、計算機プログラミング言語に反映されて、コンスセル (cons cell) を入れ子にすることで要素のリストを構成することができる。例えば、リスト (1 2 3 4 5) は (1, (2, (3, (4, (5, {}))))) という具合である。LISP言語はこのようなリストを基本データ構造として採用している。

第一成分が集合 X の元で、第二成分が集合 Y の元となるような順序対全体の成す集合は、X と Y との直積集合と呼ばれ、X × Y と書かれる。X ∪ Y 上の二項関係とは、X × Y の部分集合のことである。

記号 (a, b) を別な意味（たとえば実数直線上の開区間など）に用いたい場合などに、区別のために順序対を 〈a, b〉 などの少し異なる記号で表すこともある。

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

数学における順序対の役割を理解するのに必要なことの全ては、上述した順序対の特徴づけに尽きる。したがって、順序対を上述の特徴づけをその公理とする原始概念として捉えることができる。1954年に出版されたブルバキの『集合論』("Theory of Sets") ではこのやり方が取られている。ずっと後になってクラトフスキがこれを簡単にしたものを発見している（後述）。クラトフスキの定義は1970年に出版された『集合論』の第二版で加えられた。

集合論による素晴らしい数学の基礎付けを認めるならば、全ての数学的対象はある種の集合として定義される。したがって、順序対を原始概念と考えないならば、順序対もまた集合として定義されなければならない 順序対の集合論的定義を以下にいくつか挙げる。

ウィーナーの定義

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

<math>(a, b) := \{\{\{a\},\, \emptyset\},\, \{\{b\}\}\}</math>

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

ハウスドルフの定義

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

<math>(a, b) := \{\{a, 1\},\, \{b, 2\}\}</math>

という順序対の定義を提唱した。「ここで、1 および 2 は、a とも b とも異なる、相異なるふたつの対象である」。

クラトフスキーの定義

1921年にクラトフスキーは今日的に広く受け入れられている順序対 (a, b) の定義

<math>(a, b)_\text{K} := \{\{a\},\, \{a, b\}\}</math>

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

<math>p = (x, x) = \{\{x\},\, \{x, x\}\} = \{\{x\},\{x\}\} = \{\{x\}\}</math>

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

順序対 p が与えられたとき、「p の第一成分が x である」という性質は

<math>\forall Y \in p : x \in Y</math>

として定式化することができる。「p の第二成分が x である」という性質は

<math>(\exist Y \in p : x \in Y )\and(\forall Y_{1},\,\forall Y_{2} \in p : Y_{1}\ne Y_{2}\rarr (x \notin Y_{1} \or x \notin Y_{2}))</math>

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

<math>(\forall Y_{1},\,\forall Y_{2} \in p : Y_{1}\ne Y_{2}\rarr (x \notin Y_{1} \or x \notin Y_{2}))</math>

は Y₁ ≠ Y₂ となることが絶対に無いので、明らかに真である。

順序対の第一座標は

<math>\pi_1(p) = \bigcup\bigcap p</math>

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

<math>\pi_2(p) = \begin{cases}

 \bigcup\bigcap p & \text{if } \bigcap p = \bigcup p\\[7pt]
 \bigcup\left(\bigcup p \smallsetminus \bigcap p\right) & \text{if }\bigcap p \ne \bigcup p \end{cases}</math>

とすればよい。

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

上述のクラトフスキーによる順序対の定義は順序対が満足すべき特徴づけ

<math>(a,b) = (x,y) \leftrightarrow a=x \and b=y</math>

を満足するに「相応しい」ものである。ほかにもこれと同じくらい相応しい、同様あるいはより単純な形の定義として

• <math>(a, b)_\text{reverse} := \{\{b\},\, \{a, b\}\},</math>
• <math>(a, b)_\text{short} := \{a,\, \{a, b\}\},</math>
• <math>(a, b)_\text{01} := \{\{0, a\},\, \{1, b\}\}</math>

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

特徴づけを満足する事

(a, b) = (c, d) となるための必要十分条件が a = c かつ b = d であることを示す。

Kratowski の定義

十分性

a = c かつ b = d ならば {{a}, {a, b}} = {{c}, {c, d}} ゆえ (a, b)_K = (c, d)_K である。

必要性

a = b と a ≠ b のふたつの場合がある。

a = b のとき、(a, b)_K = {{a}, {a, b}} = {{a}, {a, a}} = {{a}} に注意すれば

<math>\{\{c\},\, \{c, d\}\} = (c, d)_\text{K} = (a, b)_\text{K} = \{\{a\}\}</math>

から {c} = {c, d} = {a} でなければならないが、これは a = c かつ a = d ということであり、また仮定より a = b であったから b = d を得る。

a ≠ b のとき、(a, b)_K = (c, d)_K は {{a}, {a, b}} = {{c}, {c, d}} の意である。まず、{c, d} = {a} であるとすると c = d = a ゆえ

<math>\{\{c\},\, \{c, d\}\} = \{\{a\},\, \{a, a\}\} = \{\{a\},\, \{a\}\} = \{\{a\}\}</math>

となるがこれと{{a}, {a, b}} とが等しいとすると b = a であることになり、a ≠ b という仮定に反する。また、{c} = {a, b} であるとすると a = b = c ゆえ同様に a ≠ b という仮定に反する。したがって、 {c} = {a} であり、c = a および {c, d} = {a, b} を得る。このとき d = a であるとすると {c, d} = {a, a} = {a} ≠ {a, b} で矛盾するから、この場合 d = b であり、まとめると a = c かつ b = d であることを得る。

Reverse 版

(a, b)_reverse = {{b}, {a, b}} = {{b}, {b, a}} = (b, a)_K であることに注意すれば簡明である。

十分性

a = c かつ b = d ならば {{b}, {a, b}} = {{d}, {c, d}} ゆえ (a, b)_reverse = (c, d)_reverse を得る。

必要性

(a, b)_reverse = (c, d)_reverse ならば (b, a)_K = (d, c)_K ゆえに b = d かつ a = c である。

Short 版

十分性

明らか。

必要性

{a, {a, b}} = {c, {c, d}} を仮定すれば a は左辺に属すから、したがって右辺にも属する。集合の相当条件は属する元が等しいことであったから、a = c か a = {c, d} のうちのいずれか一方が成り立つ。

a = {c, d} ならば上と同様の理由で {a, b} が右辺に属するから {a, b} = c であるか {a, b} = {c, d} である。{a, b} = c ならば c は {c, d} = a に属し、a は c に属するが、これは {a, c} が「～の元である」という関係の下での最小元を持たないことになり、正則性の公理に矛盾する。{a, b} = {c, d} ならば a は a の元で、a = {c, d} = {a, b} から再び正則性に反する。ゆえに a = c でなければならない。

再びはじめに戻れば、{a, b} = c または {a, b} = {c, d} である。{a, b} = c かつ a = c とすれば c は c の元となり正則性に反する。ゆえに a = c かつ {a, b} = {c, d} であり、それゆえに

<math>\{b\} = \{a, b\} \smallsetminus \{a\} = \{c, d\} \smallsetminus \{c\} = \{d\}</math>

したがって b = d を得る。

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

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

<math>\varphi(x) = (x \smallsetminus \N) \cup \{n+1 : n \in (x \cap \N) \}</math>

を定義する。この函数を適用するということは、ただ x に属するどの自然数も 1 増やせばいい。とくに、φ(x) は最小の自然数である 0 を含まないので、任意の集合 x, y に対し

<math>\varphi(x) \ne \{0\} \cup \varphi(y)</math>

が成立する。これを用いて順序対 (A, B) を

<math>(A, B) = \{\varphi(a) : a \in A\} \cup \{\varphi(b) \cup \{0\} : b \in B \}</math>

と定義する。この対から 0 を含まない元をすべて取り出して、φ の適用を取り消せば A が得られる。同様に、0 を含む元を考えれば B を復元することができる。

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

モースの定義

モース・ケリーの集合論 (Morse 1965)では真のクラスを自由に扱うことができる。モースは成分が集合のみならず真のクラスであるような順序対を定義した（クラトフスキーの定義ではそのようなことはできない）。モースはまず、クラトフスキーの方法で成分が集合となる順序対を定義し、それから順序対 (x, y) を

<math>(x \times \{0\}) \cup (y \times \{1\})</math>

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

圏論

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