順序組

テンプレート:Otheruses 数学における順序組（じゅんじょぐみ、テンプレート:Lang-en-short etc.）あるいは単に組 (テンプレート:Lang) とは、通常は有限な長さの列を言う。特に非負整数 テンプレート:Mvar に対して、テンプレート:Mvar 個の対象を順番に並べた（あるいは番号付けた）ものは テンプレート:Math-組 (テンプレート:Lang) と呼ぶ（このとき、並べられた対象のことは、この テンプレート:Mvar-組の「要素」や「成分」などと呼ぶ）。

• テンプレート:Math-組はただ一つ存在して「何も並べないこと」を意味するが、文脈によりそれは空集合や、空列や、空リストなどと呼ばれる。
• テンプレート:Math-組（あるいは一つ組）は定義により、ただ一つの元からなる集合、ただ一つの項からなる列、ただ一つの点からなる空間などであって、それはそのそれぞれのただ一つの要素であるところの元、項、点などとは厳密には異なるが、にも拘らず多くの場合においてその唯一の要素と同一視して、あるいはそれら要素自身を指す意味で用いられる。
• テンプレート:Math-組（あるいは二つ組, テンプレート:Lang）は特に対 (テンプレート:Lang) または順序対 (テンプレート:Lang) という特別な呼称を持つ。テンプレート:Efn
• 小さい テンプレート:Mvar に対する テンプレート:Mvar-組はしばしば、テンプレート:Math-組を「三つ組」(テンプレート:Lang)、テンプレート:Math-組を「四つ組」(テンプレート:Lang) などのように呼ぶこともある。

任意の長さ テンプレート:Mvar に対する テンプレート:Mvar-組は、順序対の構成を帰納的に用いて定義できる。順序組はふつう、要素をコンマで区切って書き並べたものを丸括弧 "テンプレート:Math" で括る。例えば テンプレート:Math は五つ組である。要素を括る約物は、ときどき角括弧 "テンプレート:Math" や山括弧 "テンプレート:Math" や場合によっては 波括弧 "テンプレート:Math" を使うこともある。特に波括弧は（歴史的な経緯で、数列や点列を扱う文脈などではしばしば用いられるが）標準的な集合を表す記法と紛らわしいため注意すべきである。

順序組はベクトルなどほかの数学的対象を記述するのにも用いられる。計算機科学や言語学、哲学などにおいても順序組は用いられる。

性質

もっとも重要な一般規則（順序組の定義性質）として、二つの テンプレート:Mvar-組が相等しい:

$(a_1,a_2,\dots ,a_n)=(b_1,b_2,\dots ,b_n)$

とは、テンプレート:Math かつ テンプレート:Math かつ … かつ テンプレート:Math を満たすことが必要十分である。

したがって順序組は、以下の如く集合とは異なる性質を持つことに注意すべきである:

1. 順序組は同じ要素を複数持ち得る: 組として テンプレート:Math だが、集合では テンプレート:Math である。
2. 順序組は要素の順番を変えてはならない: 組として テンプレート:Math だが、集合では テンプレート:Math である。

定義

順序組は前節の「性質」を持つものとして定義される。そのような定義の仕方はいくつか存在する。

写像としての定義

集合を扱える文脈において、テンプレート:Mvar-組は、以下のような写像 テンプレート:Math と見なすことができる。すなわち、その定義域 テンプレート:Mvar は組の各要素を指し示す陰伏的な添字の集合（添字集合）で、終域 テンプレート:Mvar は要素の順序組すべての成す集合である。集合論の言葉では

$(a_1,a_2,\dots ,a_n)\stackrel{\text{def}}{⟺}(X,Y,F)$

where:

$\begin{array}{cc}X& =\{1,2,\dots ,n\}\\ Y& =\{a_1,a_2,\dots ,a_n\}\\ F& =\{(1,a_1),(2,a_2),\dots ,(n,a_n)\}.\\ \end{array}$

より直観的な書き方をすれば、

$(a_1,a_2,\dots ,a_n)\stackrel{\text{def}}{=}(F(1),F(2),\dots ,F(n))$

と定義されるということである。

順序対の入れ子としての定義

集合論における順序対のモデル化は順序対を用いても定義できる。ただし、順序対は既に定義されているものとする（そして、順序対は二つ組である）。

1. テンプレート:Math-組（空組）は空集合 テンプレート:Math とする。
2. テンプレート:Math に対する テンプレート:Mvar-組は、初項と テンプレート:Math-組との順序対 $$(a_1,a_2,a_3,\dots ,a_n):=(a_1,(a_2,a_3,\dots ,a_n))$$ と定める。

この構成を テンプレート:Math-組に対しても帰納的に適用して、最終的に

$(a_1,a_2,a_3,\dots ,a_n)\stackrel{\text{def}}{=}(a_1,(a_2,(a_3,(\dots ,(a_n,\mathrm{\varnothing })\dots )))).$

同様の仕方で、要素を後ろに追記していく形に定義することもできる:

1. テンプレート:Math-組 テンプレート:Math;
2. テンプレート:Math に対して $$(a_1,a_2,a_3,\dots ,a_n):=((a_1,a_2,a_3,\dots ,a_{n-1}),a_n).$$

したがって帰納的に

$(a_1,a_2,a_3,\dots ,a_n)\stackrel{\text{def}}{=}((\dots (((\mathrm{\varnothing },a_1),a_2),a_3),\dots ),a_n).$

さて集合論において、順序対は集合として定義される（例えばクラトフスキーの定義）から、順序対による順序組の定義も集合によって定式化できる:

1. テンプレート:Math-組 テンプレート:Math;
2. テンプレート:Mvar-組 テンプレート:Math と右に追加される要素 テンプレート:Mvar に対し、$(a_1,a_2,\dots ,a_n,b):=\{\{x\},\{x,b\}\}$

テンプレート:Mvar-組の総数

テンプレート:Main 離散数学、特に初等組合せ論および有限確率論において、テンプレート:Mvar-組は様々な数え上げ問題において、長さ テンプレート:Mvar の（あまり形式ばらない意味での）要素の並びを表すために用いられるテンプレート:Sfn。テンプレート:Mvar-元集合から要素をとって作られる テンプレート:Mvar-組は重複順列 (arrangement with repetition) と呼び、その総数は テンプレート:Mvar 個である。これは組合せ論における積の法則からわかるテンプレート:Sfn。この数は位数 テンプレート:Mvar の有限集合 テンプレート:Mvar の テンプレート:Mvar-重デカルト積 テンプレート:Math（この直積集合の元は考えている重複順列 (テンプレート:Mvar-組) のことに他ならない）の位数に等しい。

型理論

テンプレート:Main プログラミング言語に広く用いられる型理論において、順序組はテンプレート:仮リンクを持つ（これは組の長さも各成分のもつ型も固定しない意味で言う）。形式的には

$(x_1,x_2,\dots ,x_n):{𝖳}_1\times {𝖳}_2\times \dots \times {𝖳}_n$

であり、射影は項構成子:

${\pi }_1(x):{𝖳}_1,{\pi }_2(x):{𝖳}_2,\dots ,{\pi }_n(x):{𝖳}_n$

である。関係モデルで用いられるラベル付き要素の順序組はレコード型を持つ。これらの型は単純型付きラムダ計算の単純拡大として定義できる。

型理論における順序組の概念と集合論における順序組の概念には以下のような関係がある: 型理論の自然なモデルを考えれ、意味論的解釈にスコット括弧を用いれば、適当な集合 $S_1,S_2,\dots ,S_n$（ここでイタリックは集合をあらわし、その型特別するために用いることに注意）からなるモデルとして

$[[{𝖳}_1]]=S_1,[[{𝖳}_2]]=S_2,\dots ,[[{𝖳}_n]]=S_n$

および基本項の解釈が

$[[x_1]]\in [[{𝖳}_1]],[[x_2]]\in [[{𝖳}_2]],\dots ,[[x_n]]\in [[{𝖳}_n]]$

とすれば、この型理論における テンプレート:Mvar-組は集合論における テンプレート:Mvar-組として自然な解釈

$[[(x_1,x_2,\dots ,x_n)]]=([[x_1]],[[x_2]],\dots ,[[x_n]])$

を持つ。テンプレート:仮リンクは テンプレート:Math-組を意味論的解釈に持つ。

参考文献

• テンプレート:Citation
• Keith Devlin, The Joy of Sets. Springer Verlag, 2nd ed., 1993, ISBN 0-387-94094-4, pp. 7–8
• Abraham Adolf Fraenkel, Yehoshua Bar-Hillel, Azriel Lévy, Foundations of set theory, Elsevier Studies in Logic Vol. 67, Edition 2, revised, 1973, ISBN 0-7204-2270-1, p. 33
• Gaisi Takeuti, W. M. Zaring, Introduction to Axiomatic Set Theory, Springer GTM 1, 1971, ISBN 978-0-387-90024-7, p. 14
• George J. Tourlakis, Lecture Notes in Logic and Set Theory. Volume 2: Set theory, Cambridge University Press, 2003, ISBN 978-0-521-75374-6, pp. 182–193

関連項目

• タプル
• アリティ
• 指数対象
• 形式言語
• テンプレート:仮リンク: 双子素数、三つ子素数、……
• 多項関係

外部リンク

• テンプレート:Nlab
• テンプレート:MathWorld
• テンプレート:PlanetMath
• テンプレート:SpringerEOM

テンプレート:Set theory テンプレート:Authority control