順序組

数学における順序組（じゅんじょぐみ、英: ordered tuplet, ordered list etc.）あるいは単に組 (tuple, tuplet etc.) とは、通常は有限な長さの列を言う。特に非負整数 $n$ に対して、 $n$ 個の対象を順番に並べた（あるいは番号付けた）ものは $n$ -組 ( $n$ -tuple) と呼ぶ（このとき、並べられた対象のことは、この $n$ -組の「要素」や「成分」などと呼ぶ）。

$0$ -組はただ一つ存在して「何も並べないこと」を意味するが、文脈によりそれは空集合や、空列や、空リストなどと呼ばれる。
$1$ -組（あるいは一つ組）は定義により、ただ一つの元からなる集合、ただ一つの項からなる列、ただ一つの点からなる空間などであって、それはそのそれぞれのただ一つの要素であるところの元、項、点などとは厳密には異なるが、にも拘らず多くの場合においてその唯一の要素と同一視して、あるいはそれら要素自身を指す意味で用いられる。
$2$ -組（あるいは二つ組, couple）は特に対 (pair) または順序対 (ordered pair) という特別な呼称を持つ。^{[注釈 1]}
小さい $n$ に対する $n$ -組はしばしば、 $3$ -組を「三つ組」(triple)、 $4$ -組を「四つ組」(quadruple) などのように呼ぶこともある。

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

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

性質

もっとも重要な一般規則（順序組の定義性質）として、二つの $n$ -組が相等しい:

(a_{1},a_{2},\ldots ,a_{n})=(b_{1},b_{2},\ldots ,b_{n})

とは、 $a 1 = b 1$ かつ $a 2 = b 2$ かつ … かつ $a n = b n$ を満たすことが必要十分である。

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

順序組は同じ要素を複数持ち得る: 組として $(1, 2, 2, 3) \neq (1, 2, 3)$ だが、集合では ${1, 2, 2, 3} = {1, 2, 3}$ である。
順序組は要素の順番を変えてはならない: 組として $(1, 2, 3) \neq (3, 2, 1)$ だが、集合では ${1, 2, 3} = {3, 2, 1}$ である。

→「多重集合」も参照

定義

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

写像としての定義

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

(a_{1},a_{2},\dots ,a_{n}){\stackrel {\text{def}}{{}\iff {}}}(X,Y,F)

where:

{\begin{aligned}X&=\{1,2,\dots ,n\}\\Y&=\{a_{1},a_{2},\ldots ,a_{n}\}\\F&=\{(1,a_{1}),(2,a_{2}),\ldots ,(n,a_{n})\}.\\\end{aligned}}

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

(a_{1},a_{2},\dots ,a_{n}){\stackrel {\text{def}}{{}={}}}(F(1),F(2),\dots ,F(n))

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

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

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

$0$ -組（空組）は空集合 $\emptyset$ とする。
$n > 0$ に対する $n$ -組は、初項と $(n - 1)$ -組との順序対 $(a_{1},a_{2},a_{3},\ldots ,a_{n}):=(a_{1},(a_{2},a_{3},\ldots ,a_{n}))$ と定める。

この構成を $(n - 1)$ -組に対しても帰納的に適用して、最終的に

(a_{1},a_{2},a_{3},\ldots ,a_{n}){\stackrel {\text{def}}{{}={}}}(a_{1},(a_{2},(a_{3},(\ldots ,(a_{n},\emptyset )\ldots )))).

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

$0$ -組 $\emptyset$ ;
$n > 0$ に対して $(a_{1},a_{2},a_{3},\ldots ,a_{n}):=((a_{1},a_{2},a_{3},\ldots ,a_{n-1}),a_{n}).$

したがって帰納的に

(a_{1},a_{2},a_{3},\ldots ,a_{n}){\stackrel {\text{def}}{{}={}}}((\ldots (((\emptyset ,a_{1}),a_{2}),a_{3}),\ldots ),a_{n}).

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

$0$ -組 $\emptyset$ ;
$n$ -組 $x = (a 1, a 2, \dots, a n)$ と右に追加される要素 $b$ に対し、 $(a_{1},a_{2},\ldots ,a_{n},b):=\{\{x\},\{x,b\}\}$

$n$ -組の総数

→詳細は「重複順列」を参照

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

型理論

→詳細は「直積型（英語版）」を参照

プログラミング言語に広く用いられる型理論において、順序組は直積型（英語版）を持つ（これは組の長さも各成分のもつ型も固定しない意味で言う）。形式的には

(x_{1},x_{2},\ldots ,x_{n}):{\mathsf {T}}_{1}\times {\mathsf {T}}_{2}\times \ldots \times {\mathsf {T}}_{n}

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

\pi _{1}(x):{\mathsf {T}}_{1},~\pi _{2}(x):{\mathsf {T}}_{2},~\ldots ,~\pi _{n}(x):{\mathsf {T}}_{n}

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

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

[\![{\mathsf {T}}_{1}]\!]=S_{1},~[\![{\mathsf {T}}_{2}]\!]=S_{2},~\ldots ,~[\![{\mathsf {T}}_{n}]\!]=S_{n}

および基本項の解釈が

[\![x_{1}]\!]\in [\![{\mathsf {T}}_{1}]\!],~[\![x_{2}]\!]\in [\![{\mathsf {T}}_{2}]\!],~\ldots ,~[\![x_{n}]\!]\in [\![{\mathsf {T}}_{n}]\!]

とすれば、この型理論における $n$ -組は集合論における $n$ -組として自然な解釈^[6]

[\![(x_{1},x_{2},\ldots ,x_{n})]\!]=(\,[\![x_{1}]\!],[\![x_{2}]\!],\ldots ,[\![x_{n}]\!]\,)

を持つ。ユニット型（英語版）は $0$ -組を意味論的解釈に持つ。

注

注釈

^ 二つ組の意味で dual や twin を用いることもあるが、これらはふつう特別な対応をもつ二者に対して用いられる。特に dual は双対性 (duality) を示す二つ組を言い、またその三つ組版の対応物として三対性（英語版）を持つものを三重系や三つ鼎などとも呼ぶ

出典

^ “N‐tuple - Oxford Reference”. oxfordreference.com. 2015年5月1日閲覧。
^ “Ordered n-tuple - Oxford Reference”. oxfordreference.com. 2015年5月1日閲覧。
^ D'Angelo & West 2000, p. 9.
^ D'Angelo & West 2000, p. 101.
^ Pierce, Benjamin (2002). Types and Programming Languages. MIT Press. pp. 126–132. ISBN 0-262-16209-1
^ Steve Awodey, From sets, to types, to categories, to sets, 2009, preprint

参考文献

D'Angelo, John P.; West, Douglas B. (2000), Mathematical Thinking/Problem-Solving and Proofs (2nd ed.), Prentice-Hall, ISBN 978-0-13-014412-6
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