順序対

数学における順序対（じゅんじょつい、英: ordered pair）は、一口に言えば対象を「対」にしたものである。二つの対象 $a, b$ の順序対をふつうは $(a, b)$ で表す。ここで、「順序」対において対象の現れる順番は重要であることに注意しなければならない、すなわち $a = b$ でない限り $(a, b)$ という対と $(b, a)$ という対とが相異なる^{[注 1]}。

順序対 $(a, b)$ において、対象 $a$ を第一成分 (first entry, first component), 対象 $b$ を第二成分 (second entry, second component) などと呼ぶ。場合によっては、第一、第二座標や、左射影・右射影ともいう。

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

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

一般論

$(a 1, b 1), (a 2, b 2)$ をふたつの順序対とするとき、順序対の特徴づけ (characteristic property) あるいは定義性質 (defining property）とは

(a 1, b 1) = (a 2, b 2)

となるのは

a 1 = a 2

かつ

b 1 = b 2

のとき、かつそのときに限る

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

注: 数学の広範な分野において記号 $(a, b)$ はざまざまな意味で用いられ、そうしたものの中で顕著な例はたとえば実数直線上の開区間を挙げることができるだろう。記号の意味は文脈に完全に依存しており、意味を取るためには文脈に注意しなければならない^[1]^[2]。そうして時には、区別の明確化のために順序対を $⟨ a, b ⟩$ などの少し異なる記号で表すこともある（が、そういった記号もやはり他で多義的に用いられている）。

順序対 $p$ が与えられたとき、その第一および第二成分への射影はそれぞれ $π 1 (p)$ および $π 2 (p)$ のように書くのがふつうである（左射影・右射影の意味で $π l (p), π r (p)$ のように書いてもよい）。この文脈では、自然に $n$ -組 $t$ が第 $i$ -成分への射影 $π n i (t)$ を使って考えられる（必ずしも再帰的でない取り扱いができる）。

直観的な定義

入門書の類いにおいては、順序対の定義としてやや不正確だが直観的に

二つの対象 $a$ , $b$ に対し、順序対 $(a, b)$ とは、対象 $a, b$ をこの順番で指定する記法である^[3]

というような形で与えるものがある。こういった場合、順序対の理解のために集合の場合との比較を持ってくるのが通例である: たとえば、集合 ${a, b}$ の元として $a$ と $b$ が区別できるには、 $a, b$ は相異なるものでなければならないが、順序対 $(a, b)$ ではその必要が無い。また、集合では元の書き並べ方を変えてももとと意味が変わることはない ( ${b, a} = {a, b}$ ) が、順序対では並べる順番が異なればそれらは別の順序対 ( $(b, a) \neq (a, b)$ ) である

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

もう少し正確な取り扱いをするには、上で述べた「順序対の定義性質」を満たすものという役割が数学における順序対の意味の全てであると捉えることになる。そういう立場では、順序対とは順序対の定義性質を対応する公理とする原始概念（英語版）として扱うという見方ができる。1954年に出版されたブルバキの『集合論』("Theory of Sets") ではこのやり方が取られている。しかしこれは順序対の存在と定義性質の両方を公理的に仮定しなければならないのが難である^[3]。

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

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

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

ウィーナーの定義

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

(a,b):=\{\{\{a\},\,\emptyset \},\,\{\{b\}\}\}

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

ハウスドルフの定義

Wiener (1914) とほぼ同時期にハウスドルフは

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

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

クラトフスキーの定義

Kuratowski (1921) は今日的に広く受け入れられている順序対 $(a, b)$ の定義^[5]^{[注 4]}

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

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

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

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

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

\forall Y\in p:x\in Y

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

(\exists Y\in p:x\in Y)\land (\forall Y_{1},\,\forall Y_{2}\in p:Y_{1}\neq Y_{2}\rightarrow (x\notin Y_{1}\lor x\notin Y_{2}))

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

(\forall Y_{1},\,\forall Y_{2}\in p:Y_{1}\neq Y_{2}\rightarrow (x\notin Y_{1}\lor x\notin Y_{2}))

は $Y 1 \neq Y 2$ となることが絶対に無いので、明らかに真である。

順序対の第一座標は

\pi _{1}(p)=\bigcup \bigcap p

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

\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\neq \bigcup p\end{cases}}

とすればよい。

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

(a,b)=(x,y)\iff a=x\land b=y

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

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

$(a,b)_{\text{reverse}}:=\{\{b\},\,\{a,b\}\},$
$(a,b)_{\text{short}}:=\{a,\,\{a,b\}\},$
$(a,b)_{\text{01}}:=\{\{0,a\},\,\{1,b\}\}$ ^{[注 5]}

などが存在する。reverse（逆順）版はあまり使われないが、クラトフスキーの定義の自明な変形版であり、もとの定義で見たこと以外の特徴としてとくに見るべきものは無い。short（省略）版はその名の通り、もとの定義にブレースの組が三つあったことに比べて、ふたつの組に減っている。short 版が順序対の特徴付けを満足することの証明には、ZFCの正則性公理が必要である^[6]。さらに、自然数の集合論的構成を認めるならば、自然数の " $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 \neq b$ のふたつの場合がある。; $a = b$ のとき、 $(a, b) K = {{a}, {a, b}} = {{a}, {a, a}} = {{a}}$ に注意すれば $\{\{c\},\{c,d\}\}=(c,d)_{\text{K}}=(a,b)_{\text{K}}=\{\{a\}\}$ から ${c} = {c, d} = {a}$ でなければならないが、これは $a = c$ かつ $a = d$ ということであり、また仮定より $a = b$ であったから $b = d$ を得る。; $a \neq b$ のとき、 $(a, b) K = (c, d) K$ は ${{a}, {a, b}} = {{c}, {c, d}}$ の意である。まず、 ${c, d} = {a}$ であるとすると $c = d = a$ ゆえ $\{\{c\},\{c,d\}\}=\{\{a\},\{a,a\}\}=\{\{a\},\{a\}\}=\{\{a\}\}$ となるがこれと ${{a}, {a, b}}$ とが等しいとすると $b = a$ であることになり、 $a \neq b$ という仮定に反する。また、 ${c} = {a, b}$ であるとすると $a = b = c$ ゆえ同様に $a \neq b$ という仮定に反する。したがって、 ${c} = {a}$ であり、 $c = a$ および ${c, d} = {a, b}$ を得る。このとき $d = a$ であるとすると ${c, d} = {a, a} = {a} \neq {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 版^{[注 6]}

十分性: 明らか。
必要性: ${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}$ であり、それゆえに $\{b\}=\{a,b\}\smallsetminus \{a\}=\{c,d\}\smallsetminus \{c\}=\{d\}$ したがって $b = d$ を得る。

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

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

\varphi (x)=(x\smallsetminus \mathbb {N} )\cup \{n+1:n\in (x\cap \mathbb {N} )\}

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

\varphi (x)\neq \{0\}\cup \varphi (y)

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

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

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

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

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

集合論の初期（カントールの逆理の出現以前）、カントールはフレーゲに従い、関係の概念は原始概念として認めたうえで、二つの集合の順序対をそれらの集合の間に成り立つ関係全体の成すクラス

(x,y)=\{R:xRy\}

として定義した^[7]。

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

モースの定義

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

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

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

圏論

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

注

注釈

^ これに対して非順序対 ${a, b}$ は非順序対 ${b, a}$ と常に等しい。集合および多重集合の項も参照のこと
^ クワインは、順序対の概念の集合論的な実現は哲学的概念を明確化するパラダイムであると主張した（"Word and Object" の &sec;53 を参照）。そのような概念や実現の一般概念が、トーマス・フォースター (Thomas Forster) の "Reasoning about theoretical entities" に論じられている。
^ ウィーナーの論文 "A Simplification of the logic of relations"（「論理と関係の単純化」）が、貴重な解説付きで (van Heijenoort 1967, pp. 224ff) に再録されている。ヴァン・エジュノールはこの方法での単純化について "By giving a definition of the ordered pair of two elements in terms of class operations, the note reduced the theory of relations to that of classes"（クラス演算による二つの元の順序対の定義が与えられれば、そのようなクラスに対する関係の理論のノートが節約できる）と述べている。
^ ヴァン・エジュノールは、結果として得られる順序対を表す集合は（それらが同じ型の元であるとき）「それらの元よりも 2 階高い型を持つ」ことを注意している。これを示すのに関連して、エジュノールは、特定の状況下で型が 1 か 0 に還元できることを述べている。
^ ハウスドルフ版の定義とほぼ同じだが、 $0, 1$ が $a, b$ と異なるとは限らない
^ shortの適格性の厳密な超数学的証明はこちら (opthreg)を参照。また Tourlakis (2003), Proposition III.10.1. も参照。

出典

^ Lay 2005, p. 50.
^ Devlin 2004, p. 79.
^ ^a ^b Wolf 1998, p. 164.
^ Fletcher & Patty 1988, p. 80.
^ ^a ^b van Heijenoort 1967, p. 224, —ウィーナーの論文の導入を参照。
^ Tourlakis 2003, Proposition III.10.1..
^ Frege 1893, §144.
^ 2007, p. 22, footnote 59.

参考文献

Devlin, Keith (2004), Sets, Functions and Logic / An Introduction to Abstract Mathematics (3rd ed.), Chapman & Hall / CRC, ISBN 978-1-58488-449-1
Fletcher, Peter; Patty, C. Wayne (1988), Foundations of Higher Mathematics, PWS-Kent, ISBN 0-87150-164-3
Frege, Gottlob (1893). Grundgesetze der Arithmetik. Jena: Verlag Hermann Pohle
Holmes, Randall (1998), Elementary Set Theory with a Universal Set, Academia-Bruylant (The publisher has graciously consented to permit diffusion of this monograph via the web. Copyright is reserved.)
Kanamori, Akihiro (2007). Set Theory From Cantor to Cohen. Elsevier BV. http://math.bu.edu/people/aki/16.pdf
Kuratowski, Casimir (1921). “Sur la notion de l'ordre dans la Théorie des Ensembles”. Fundamenta Mathematicae 2 (1): 161–171.
Lay, Steven R. (2005), Analysis / With an Introduction to Proof (4th ed.), Pearson / Prentice Hall, ISBN 978-0-13-148101-5
Morse, Anthony P. (1965), A Theory of Sets, Academic Press
Rosser, J. Barkley (1953), Logic for Mathematicians, McGraw-Hill
Tourlakis, George (2003). Lectures in Logic and Set Theory. Vol. 2: Set Theory. Cambridge Univ. Press
van Heijenoort, Jean (1967). From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931. Harvard University Press, Cambridge MA. ISBN 0-674-32449-8
Wolf, Robert S. (1998), Proof, Logic, and Conjecture / The Mathematician's Toolbox, W. H. Freeman and Co., ISBN 978-0-7167-3050-7

[1] これに対して非順序対 ${a, b}$ は非順序対 ${b, a}$ と常に等しい。集合および多重集合の項も参照のこと

[6] クワインは、順序対の概念の集合論的な実現は哲学的概念を明確化するパラダイムであると主張した（"Word and Object" の &sec;53 を参照）。そのような概念や実現の一般概念が、トーマス・フォースター (Thomas Forster) の "Reasoning about theoretical entities" に論じられている。

[7] ウィーナーの論文 "A Simplification of the logic of relations"（「論理と関係の単純化」）が、貴重な解説付きで (van Heijenoort 1967, pp. 224ff) に再録されている。ヴァン・エジュノールはこの方法での単純化について "By giving a definition of the ordered pair of two elements in terms of class operations, the note reduced the theory of relations to that of classes"（クラス演算による二つの元の順序対の定義が与えられれば、そのようなクラスに対する関係の理論のノートが節約できる）と述べている。

[9] ヴァン・エジュノールは、結果として得られる順序対を表す集合は（それらが同じ型の元であるとき）「それらの元よりも 2 階高い型を持つ」ことを注意している。これを示すのに関連して、エジュノールは、特定の状況下で型が 1 か 0 に還元できることを述べている。

[10] ハウスドルフ版の定義とほぼ同じだが、 $0, 1$ が $a, b$ と異なるとは限らない

[12] shortの適格性の厳密な超数学的証明はこちら (opthreg)を参照。また Tourlakis (2003), Proposition III.10.1. も参照。

[FOOTNOTELay200550-2] Lay 2005, p. 50.

[FOOTNOTEDevlin200479-3] Devlin 2004, p. 79.

[FOOTNOTEWolf1998164-4] Wolf 1998, p. 164.

[FOOTNOTEFletcherPatty198880-5] Fletcher & Patty 1988, p. 80.

[FOOTNOTEvan_Heijenoort1967224-8] van Heijenoort 1967, p. 224, —ウィーナーの論文の導入を参照。

[FOOTNOTETourlakis2003Proposition_III.10.1.-11] Tourlakis 2003, Proposition III.10.1..

[FOOTNOTEFrege1893§144-13] Frege 1893, §144.

[FOOTNOTE200722footnote_59-14] 2007, p. 22, footnote 59.

[注 1]

[1]

[2]

[3]

[4]

[注 2]

[注 3]

[5]

[注 4]

[注 5]

[6]

[注 6]

[7]

[8]