順序付きペア

数学において、順序付きペア( a , b )は、順序が重要なオブジェクトのペアです。順序付きペア ( a , b ) は、 a = bでない限り、順序付きペア ( b , a )とは異なります。対照的に、順序なしペア({ a , b }) は、順序なしペア { b , a } と同じです。

順序付きペアは、2 タプル、または長さ 2 のシーケンス(コンピュータ サイエンスのコンテキストではリストと呼ばれることもあります)とも呼ばれます。順序付きスカラーのペアは、2 次元ベクトルと呼ばれることもあります。(技術的には、順序付きペアはベクトル空間の要素である必要がないため、これは用語の誤用です。) 順序付きペアのエントリは、他の順序付きペアになる可能性があり、順序付きnタプル( n個のオブジェクトの順序付きリスト)の再帰的な定義が可能になります。たとえば、順序付き 3 つ組 ( a、b、c ) は、( a、 ( b、c ))、つまり 1 つのペアが別のペアにネストされたもの として定義できます。

順序付きペア ( a、b ) では、オブジェクトa はペアの最初のエントリと呼ばれ、オブジェクトb はペアの2番目のエントリと呼ばれます。あるいは、オブジェクトは、順序付きペアの 1 番目と 2 番目のコンポーネント、1 番目と 2 番目の座標、または左と右の投影と呼ばれます。

デカルト積と二項関係（および関数）は、順序付きペアで定義されます（図を参照）。

と を順序付きペアとします。順序付きペアの 特性（または定義）プロパティは次のようになります。${\displaystyle (a_{1},b_{1})}$${\displaystyle (a_{2},b_{2})}$$${\displaystyle (a_{1},b_{1})=(a_{2},b_{2}){\text{ }}a_{1}=a_{2}{\text{ かつ }}b_{1}=b_{2} のときのみ。}$$

最初の要素が何らかの集合Aに含まれ、 2 番目の要素が何らかの集合Bに含まれるすべての順序付きペアの集合は、 AとBの直積と呼ばれ、A × Bと表記されます。集合AとB間の2 項関係は、 A × Bのサブセットです。

( a , b )表記は他の目的にも使用されることがありますが、最もよく使われるのは実数直線上の開区間を表す場合です。このような状況では、文脈からどちらの意味が意図されているかは通常明らかです。^{[1] [2]}さらに明確にするために、順序付きペアは異形表記で表すことができますが、この表記には他の用途もあります。 ${\textstyle \langle a,b\rangle }$

左と右対pの射影は通常、それぞれπ ₁ ( p )とπ ₂ ( p )、またはπ _ℓ ( p )とπ _r ( p )で表されます。任意のn組が考慮される文脈では、 π^に
_私は( t ) は、 n組tのi番目の要素を表す一般的な表記法です。

いくつかの入門数学の教科書では、順序付きペアの非公式な（または直感的な）定義が与えられている。例えば、

任意の2つのオブジェクトaとbについて、順序付きペア( a、b )は、2つのオブジェクトaとbをその順序で指定する表記法です。^[3]

この後には通常、2 つの要素のセットとの比較が続きます。セットではaとbは異なる必要がありますが、順序付きペアでは等しい場合があり、セットの要素をリストする順序は重要ではありませんが、順序付きペアでは異なるエントリの順序を変更すると順序付きペアも変更されることを指摘します。

この「定義」は、記述的なものに過ぎず、順序の直感的な理解に基づいているため、不十分です。しかし、時々指摘されるように、この説明に頼っても害はなく、ほとんどすべての人が順序付きペアをこのように考えています。^[4]

より満足のいくアプローチは、上記で示した順序付きペアの特性が、数学における順序付きペアの役割を理解するために必要なすべてである、と観察することです。したがって、順序付きペアは、特性特性が関連する公理である基本概念としてとらえることができます。これは、1954年に出版されたN.ブルバキグループが集合論で採用したアプローチでした。ただし、このアプローチには、順序付きペアの存在とその特性特性の両方が公理的に仮定されなければならないという欠点もあります。^[3]

順序付きペアを厳密に扱う別の方法は、集合論の文脈でそれらを形式的に定義することです。これはいくつかの方法で実行でき、存在と特性が集合論を定義する公理から証明できるという利点があります。この定義の最も引用されているバージョンの 1 つは、クラトフスキーによるもので (下記参照)、彼の定義は 1970 年に出版されたブルバキの集合論の第 2 版で使用されました。順序付きペアの非公式な定義を与える数学の教科書でも、演習でクラトフスキーの正式な定義に言及することがよくあります。

集合論が数学の魅力的な基礎であるということに同意するならば、すべての数学的対象は何らかの集合として定義されなければならない。したがって、順序付きペアがプリミティブとして扱われない場合、それは集合として定義されなければならない。[ ^5]順序付きペアの集合論的定義のいくつかを以下に示す（^[6]も参照）。

ノーバート・ウィーナーは1914年に最初の集合論的順序対の定義を提案した。^{[7]彼はこの定義によって} プリンキピア・マテマティカの型を集合として 定義することが可能になったと指摘した。プリンキピア・マテマティカは型、したがってすべてのアリティの関係をプリミティブとして扱っていた。 $${\displaystyle \left(a,b\right):=\left\{\left\{\left\{a\right\},\,\emptyset \right\},\,\left\{\left\{b\right\}\right\}\right\}.}$$

Wiener は、クラス内のすべての要素が同じ「型」でなければならないという型理論と定義を互換性のあるものにするために、 { b } ではなく{{ b }}を使用しました。bが追加のセット内にネストされている場合、その型は's と等しくなります。 ${\displaystyle \{\{a\},\emptyset \}}$

ウィーナー（1914）とほぼ同時期に、フェリックス・ハウスドルフは 「1と2はaとbとは異なる2つの異なるオブジェクトである」という定義を提案した 。 ^[8]$${\displaystyle (a,b):=\left\{\{a,1\},\{b,2\}\right\}}$$

1921年にカジミエシュ・クラトフスキは、現在受け入れられている 順序付きペア（a、b ）の定義^{[9] [10]}を提示した。 最初の座標と2番目の座標が同一の場合、定義は次のようになる。 $${\displaystyle (a,\ b)_{K}\;:=\ \{\{a\},\ \{a,\ b\}\}.}$$$${\displaystyle (x,\ x)_{K}=\{\{x\},\{x,\ x\}\}=\{\{x\},\ \{x\}\}=\{\{x\}\}}$$

ある順序付きペアpが与えられた場合、「xはpの最初の座標である」という特性は次のように定式化できます。 「x はpの 2 番目の座標である」という特性は次のように定式化できます。 左と右の座標が同一の場合、Y ₁ ≠ Y ₂となることは決してないため、右の連言は自明に真です。 $${\displaystyle \forall Y\in p:x\in Y.}$$$${\displaystyle (\exists Y\in p:x\in Y)\land (\forall Y_{1},Y_{2}\in p:Y_{1}\neq Y_{2}\rightarrow (x\notin Y_{1}\lor x\notin Y_{2})).}$$ ${\displaystyle (\forall Y_{1},Y_{2}\in p:Y_{1}\neq Y_{2}\rightarrow (x\notin Y_{1}\lor x\notin Y_{2}))}$

その場合: ${\displaystyle p=(x,y)=\{\{x\},\{x,y\}\}}$

${\displaystyle \bigcap p=\bigcap {\bigg \{}\{x\},\{x,y\}{\bigg \}}=\{x\}\cap \{x,y\}=\{x\},}$

${\displaystyle \bigcup p=\bigcup {\bigg \{}\{x\},\{x,y\}{\bigg \}}=\{x\}\cup \{x,y\}=\{x,y\}.}$

これは、ペアの最初の座標を抽出する方法です（任意の交差と任意の和集合の反復演算表記を使用）。 $${\displaystyle \pi _{1}(p)=\bigcup \bigcap p=\bigcup \{x\}=x.}$$

2 番目の座標を抽出する方法は次のとおりです。 $${\displaystyle \pi _{2}(p)=\bigcup \left\{\left.a\in \bigcup p\,\right|\,\bigcup p\neq \bigcap p\rightarrow a\notin \bigcap p\right\}=\bigcup \left\{\left.a\in \{x,y\}\,\right|\,\{x,y\}\neq \{x\}\rightarrow a\notin \{x\}\right\}=\bigcup \{y\}=y.}$$

（ の場合、集合 {y} はより簡単に得ることができます: 、ただし前の式は x=y の場合も考慮に入れています） ${\displaystyle x\neq y}$${\displaystyle \{y\}=\{\left.a\in \{x,y\}\,\right|\,a\notin \{x\}\}}$

およびは、その定義域と共定義域が適切なクラスであるという意味で、一般化された関数であることに注意してください。 ${\displaystyle \pi _{1}}$${\displaystyle \pi _{2}}$

上記のクラトフスキーの順序付きペアの定義は、順序付きペアが満たさなければならない特性、つまり を満たすという点で「適切」です。特に、でない限り が偽であるという点で、「順序」を適切に表現しています。同様の複雑さまたは複雑さの少ない、同様に適切な他の定義があります。 ${\displaystyle (a,b)=(x,y)\leftrightarrow (a=x)\land (b=y)}$${\displaystyle (a,b)=(b,a)}$${\displaystyle b=a}$

• ${\displaystyle (a,b)_{\text{reverse}}:=\{\{b\},\{a,b\}\};}$
• ${\displaystyle (a,b)_{\text{short}}:=\{a,\{a,b\}\};}$
• ${\displaystyle (a,b)_{\text{01}}:=\{\{0,a\},\{1,b\}\}.}$^[11]

逆定義は、クラトフスキー定義の単なる些細な変形であり、それ自体は独立した興味の対象ではない。short 定義は、3対ではなく 2 対の括弧を必要とするため、このように呼ばれる。shortが特性特性を満たすことを証明するには、ツェルメロ-フランケル集合論 の正則性公理が必要である。^[12]さらに、フォン・ノイマンの自然数集合論的構成を使用する場合、2 は集合 {0, 1} = {0, {0}} として定義され、これは (0, 0) _shortペアと区別がつかない。short ペアのさらに別の欠点は、aとbが同じ型であっても、short ペアの要素はそうではないという事実である。 (ただし、a  =  bの場合、shortバージョンの基数は 2 のままであり、これは任意の「ペア」(任意の「順序付きペア」を含む) に期待されるものである。)

証明: a = cかつb = dの場合にのみ、 ( a、b ) = ( c、d )となります。

クラトフスキー：
もしa = cかつb = dならば、{{ a }, { a , b }} = {{ c }, { c , d }} です。したがって、( a, b ) _K = ( c , d ) _Kです。

の場合のみ。2 つのケース: a = b、およびa ≠ b。

a = bの場合:

( a, b ) _K = {{ a }, { a , b }} = {{ a }, { a , a }} = {{ a }}。

{{ c }, { c , d }} = ( c , d ) _K = ( a , b ) _K = {{ a }}.

したがって、 { 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となり、{{ c }, { c , d }} = {{ a }, { a , a }} = {{ a }, { a }} = {{ a }} となります。しかし、{{ a }, { a, b }} も {{ a }}となるため、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となります。

逆:
( a, b )_逆= {{ b }, { a, b }} = {{ b }, { b, a }} = ( b, a ) _K .

もし ( a, b )_逆= ( c, d )_逆ならば、 ( b, a ) _K = ( d, c ) _Kです。したがって、b = dかつa = cです。

の場合のみ。a = cかつb = d の場合、{{ b }, { a, b }} = {{ d }, { c, d }} です。したがって、( a, b )_逆= ( c, d )_逆です。

ショート：^[13]

場合: a = cかつb = d の場合、 { a , { a, b }} = { c , { c, d }} です。したがって、 ( a, b ) _short = ( c, d ) _{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 = { c, d } = { a, b }より、 a はaの要素となり、これも規則性に反します。

したがって、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 } \ { a } = { c, d } \ { c } = { d } となり、b = dとなります。

Rosser (1953) ^{[14] は、}自然数の事前定義を必要とする、クワインの順序付きペアの定義を採用しました。 を自然数の集合とし、まず を定義します。 関数 は、引数が自然数の場合はその引数を増分し、そうでない場合はそのままにします。数 0 は の関数値として現れません。に含まれないの元の集合はである のと同じです。を続けてください。 これはの下での集合の集合像であり、によっても表記されることがあります。 関数 を集合xに適用すると、その中のすべての自然数が単純に増分されます。特に、 には数 0 が含まれないため、任意の集合xおよびyについて、 が成り立ちます。 さらに、 を定義します。 これにより、 には常に数 0 が含まれます。 ${\displaystyle \mathbb {N} }$$${\displaystyle \sigma (x):={\begin{cases}x,&{\text{if }}x\notin \mathbb {N} ,\\x+1,&{\text{if }}x\in \mathbb {N} .\end{cases}}}$$${\displaystyle \sigma }$${\displaystyle \sigma }$${\displaystyle x\setminus \mathbb {N} }$${\displaystyle x}$${\displaystyle \mathbb {N} }$$${\displaystyle \varphi (x):=\sigma [x]=\{\sigma (\alpha )\mid \alpha \in x\}=(x\setminus \mathbb {N} )\cup \{n+1:n\in (x\cap \mathbb {N} )\}.}$$${\displaystyle x}$${\displaystyle \sigma }$${\displaystyle \sigma ''x}$${\displaystyle \varphi }$${\displaystyle \varphi (x)}$$${\displaystyle \varphi (x)\neq \{0\}\cup \varphi (y).}$$$${\displaystyle \psi (x):=\sigma [x]\cup \{0\}=\varphi (x)\cup \{0\}.}$$${\displaystyle \psi (x)}$

最後に、順序付きペア ( A、B ) を分離和集合 (代替表記) として定義します。 $${\displaystyle (A,B):=\varphi [A]\cup \psi [B]=\{\varphi (a):a\in A\}\cup \{\varphi (b)\cup \{0\}:b\in B\}.}$$${\displaystyle \varphi ''A\cup \psi ''B}$

0を含まないペアの要素をすべて抽出して元に戻すとAが得られます。同様に、0を含むペアの要素からBを復元できます^。[15]${\displaystyle \varphi }$

たとえば、ペアはprovidedとしてエンコードされます。 ${\displaystyle (\{\{a,0\},\{b,c,1\}\},\{\{d,2\},\{e,f,3\}\})}$${\displaystyle \{\{a,1\},\{b,c,2\},\{d,3,0\},\{e,f,4,0\}\}}$${\displaystyle a,b,c,d,e,f\notin \mathbb {N} }$

型理論や、公理的集合論NFなどのその派生では、クワインとロッサーのペアは射影と同じ型を持つため、「型レベル」の順序付きペアと呼ばれる。したがって、この定義には、順序付きペアの集合として定義される関数が、その引数の型より 1 だけ高い型を持つことができるという利点がある。この定義は、自然数の集合が無限である場合にのみ有効である。これはNFの場合であるが、型理論やNFUの場合はそうではない。J . バークレー・ロッサーは、このような型レベルの順序付きペア（または「型を 1 上げる」順序付きペア）の存在は、無限公理を意味することを示した。クワイン集合論の文脈における順序付きペアの詳細な議論については、Holmes (1998) を参照。^[16]

集合論の発展の初期、パラドックスが発見される前に、カントルはフレーゲに従って、関係の概念が原始的であると仮定して、2つの集合の順序付きペアをこれらの集合の間に成立するすべての関係のクラスとして定義しました。^[17] $${\displaystyle (x,y)=\{R:xRy\}.}$$

この定義は、現代の形式化された集合論のほとんどでは受け入れられず、集合の基数を与えられた集合と同値なすべての集合のクラスとして定義することと方法論的に類似している。^[18]

モース・ケリー集合論は、固有クラスを自由に利用している。^[19] モースは、投影が集合だけでなく固有クラスにもなるように順序付きペアを定義した。（クラトフスキーの定義ではこれは許されていない。）彼はまず、投影が集合である順序付きペアをクラトフスキーの方法で定義した。次に、成分 の 直積が集合のクラトフスキーペアであり、 $${\displaystyle (x,y)=(\{0\}\times s(x))\cup (\{1\}\times s(y))}$$$${\displaystyle s(x)=\{\emptyset \}\cup \{\{t\}\mid t\in x\}}$$

これにより、投影が適切なクラスである可能性のあるペアがレンダリングされます。上記の Quine-Rosser 定義では、投影として適切なクラスも許可されています。同様に、トリプルは次のように 3 組として定義されます。 $${\displaystyle (x,y,z)=(\{0\}\times s(x))\cup (\{1\}\times s(y))\cup (\{2\}\times s(z))}$$

挿入された空集合を持つシングルトン集合を使用すると、タプルは、 aがnタプルで b がmタプルであり、a = bならばn = mである、という一意性特性を持つことができます。順序付きペアとして定義される順序付きトリプルは、順序付きペアに関してこの特性を持ちません。 ${\displaystyle s(x)}$

ツェルメロ・フランケル集合論（ZF）では、ZFに2項の新しい関数記号（通常は省略される）と定義公理を追加するだけで、順序付きペアを公理的に導入することもできる。 ${\displaystyle f}$${\displaystyle f}$$${\displaystyle f(a_{1},b_{1})=f(a_{2},b_{2}){\text{ if and only if }}a_{1}=a_{2}{\text{ and }}b_{1}=b_{2}.}$$

この定義は、ZF のこの拡張が保守的な拡張であるため受け入れられます。^{[引用が必要]}

この定義は、Kuratowski の定義 (a,b) = {{a}, {a,b}} が使用されている場合に、(a,a) = {{a}}、および {a} ∈ (a,b) のような、いわゆる偶然の定理を回避するのに役立ちます。

集合のカテゴリにおけるカテゴリ理論的積 A × B は、最初の要素がAから、2 番目の要素がBから得られる順序付きペアの集合を表します。この文脈では、上記の特性特性は、積の普遍特性と、集合Xの要素が1 (1 つの要素の集合) からXまでの射で識別できるという事実の結果です。異なるオブジェクトが普遍特性を持つことはありますが、それらはすべて自然に同型です。

• デカルト積
• タルスキ・グロタンディーク集合論
• Trybulec, Andrzej、1989、「Tarski–Grothendieck Set Theory」、Journal of Formalized Mathematics (「順序付きペア」の定義 Def5 を { { x,y }, { x } } と定義)