順序組のソースを表示

{{Otheruses|数学|計算機科学|タプル}}
[[数学]]における'''順序組'''（じゅんじょぐみ、{{lang-en-short|''ordered tuplet'', ''ordered list''}} etc.）あるいは単に'''組''' ({{Lang|en|''tuple'', ''tuplet'' etc.}}) とは、通常は有限な長さの[[列 (数学)|列]]を言う。特に非負整数 {{mvar|n}} に対して、{{mvar|n}} 個の[[数学的対象|対象]]を順番に並べた（あるいは番号付けた）ものは '''{{math|''n''}}-組''' ({{Lang|en|{{mvar|n}}-tuple}}) と呼ぶ（このとき、並べられた対象のことは、この {{mvar|n}}-組の「要素」や「成分」などと呼ぶ）。
* {{math|0}}-組はただ一つ存在して「何も並べないこと」を意味するが、文脈によりそれは[[空集合]]や、空列や、空リストなどと呼ばれる。
* {{math|1}}-組（あるいは一つ組）は定義により、[[一元集合|ただ一つの元からなる集合]]、ただ一つの項からなる列、ただ一つの点からなる空間などであって、それはそのそれぞれのただ一つの要素であるところの元、項、点などとは厳密には異なるが、にも拘らず多くの場合においてその唯一の要素と同一視して、あるいはそれら要素自身を指す意味で用いられる。
* {{math|2}}-組（あるいは二つ組, {{lang|en|couple}}）は特に'''対''' ({{Lang|en|pair}}) または[[順序対]] ({{Lang|en|ordered pair}}) という特別な呼称を持つ。{{efn|二つ組の意味で {{Lang|en|dual}} や {{Lang|en|twin}} を用いることもあるが、これらはふつう特別な対応をもつ二者に対して用いられる。特に {{Lang|en|dual}} は[[双対性]] (duality) を示す二つ組を言い、またその三つ組版の対応物として{{仮リンク|三対性|en|triality}}を持つものを三重系や三つ鼎などとも呼ぶ}}
* 小さい {{mvar|n}} に対する {{mvar|n}}-組はしばしば、{{math|3}}-組を「三つ組」({{lang|en|triple}})、{{math|4}}-組を「四つ組」({{lang|en|quadruple}}) などのように呼ぶこともある。
任意の長さ {{mvar|n}} に対する {{mvar|n}}-組は、[[順序対]]の構成を[[再帰的定義|帰納的に用いて定義]]できる。順序組はふつう、要素をコンマで区切って書き並べたものを[[丸括弧]] "{{math|()}}" で括る。例えば {{math|(2, 7, 4, 1, 7)}} は五つ組である。要素を括る[[約物]]は、ときどき[[角括弧]] "{{math|[]}}" や[[山括弧]] "{{math|{{angbr|}}}}" や場合によっては [[波括弧]] "{{math|{{mset|}}}}" を使うこともある。特に波括弧は（歴史的な経緯で、数列や点列を扱う文脈などではしばしば用いられるが）標準的な[[集合]]を表す記法と紛らわしいため注意すべきである。

順序組は[[ベクトル]]などほかの数学的対象を記述するのにも用いられる。[[計算機科学]]や[[言語学]]<ref>{{cite web|url=http://www.oxfordreference.com/view/10.1093/acref/9780199202720.001.0001/acref-9780199202720-e-2276|title=N‐tuple - Oxford Reference|work=oxfordreference.com|accessdate=1 May 2015}}</ref>、[[哲学]]<ref>{{cite web|url=http://www.oxfordreference.com/view/10.1093/acref/9780199541430.001.0001/acref-9780199541430-e-2262|title=Ordered n-tuple - Oxford Reference|work=oxfordreference.com|accessdate=1 May 2015}}</ref>などにおいても順序組は用いられる。

== 性質 ==
もっとも重要な一般規則（順序組の定義性質）として、二つの {{mvar|n}}-組が'''相等しい''':
: <math>(a_1, a_2, \ldots, a_n) = (b_1, b_2, \ldots, b_n)</math>
とは、{{math|1=''a''{{sub|1}} = ''b''{{sub|1}}}} かつ {{math|1=''a''{{sub|2}} = ''b''{{sub|2}}}} かつ … かつ {{math|1=''a{{sub|n}}'' = ''b{{sub|n}}''}} を満たすことが[[必要十分]]である。

したがって順序組は、以下の如く[[集合]]とは異なる性質を持つことに注意すべきである:
# 順序組は同じ要素を複数持ち得る: 組として {{math|(1, 2, 2, 3) &ne; (1, 2, 3)}} だが、集合では {{math|1={{mset|1, 2, 2, 3}} = {{mset|1, 2, 3}}}} である。
# 順序組は要素の順番を変えてはならない: 組として {{math|(1, 2, 3) &ne; (3, 2, 1)}} だが、集合では {{math|1={{mset|1, 2, 3}} = {{mset|3, 2, 1}}}} である。
{{seealso|多重集合}}

== 定義 ==
順序組は前節の「性質」を持つものとして定義される。そのような定義の仕方はいくつか存在する。
=== 写像としての定義 ===
集合を扱える文脈において、{{mvar|n}}-組は、以下のような[[写像]] {{math|''F'': ''X'' → ''Y''}} と見なすことができる。すなわち、その定義域 {{mvar|X}} は組の各要素を指し示す陰伏的な添字の集合（[[添字集合]]）で、終域 {{mvar|Y}} は要素の順序組すべての成す集合である。集合論の言葉では
: <math>(a_1, a_2, \dots, a_n) \stackrel{\text{def}}{{}\iff{}} (X,Y,F)</math>
where:
: <math>
    \begin{align}
      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{align}
  </math>
より直観的な書き方をすれば、
: <math> (a_1, a_2, \dots, a_n) \stackrel{\text{def}}{{}={}} (F(1), F(2), \dots, F(n))</math>
と定義されるということである。

=== 順序対の入れ子としての定義 ===
集合論における順序対のモデル化は[[順序対]]を用いても定義できる。ただし、順序対は既に定義されているものとする（そして、順序対は二つ組である）。
# {{math|0}}-組（空組）は[[空集合]] {{math|&empty;}} とする。
# {{math|''n'' > 0}} に対する {{mvar|n}}-組は、初項と {{math|(''n'' − 1)}}-組との順序対 <math display="block">(a_1, a_2, a_3, \ldots, a_n) := (a_1, (a_2, a_3, \ldots, a_n))</math> と定める。
この構成を {{math|(''n'' − 1)}}-組に対しても帰納的に適用して、最終的に
: <math>(a_1, a_2, a_3, \ldots, a_n) \stackrel{\text{def}}{{}={}} (a_1, (a_2, (a_3, (\ldots, (a_n, \emptyset)\ldots)))).</math>

同様の仕方で、要素を後ろに追記していく形に定義することもできる:
# {{math|0}}-組 {{math|&empty;}};
# {{math|''n'' > 0}} に対して <math>(a_1, a_2, a_3, \ldots, a_n) := ((a_1, a_2, a_3, \ldots, a_{n-1}), a_n).</math>
したがって帰納的に
: <math>(a_1, a_2, a_3, \ldots, a_n) \stackrel{\text{def}}{{}={}} ((\ldots(((\emptyset, a_1), a_2), a_3), \ldots), a_n).</math>

さて[[集合論]]において、順序対は集合として定義される（例えば[[順序対#クラトフスキーの定義|クラトフスキーの定義]]）から、順序対による順序組の定義も集合によって定式化できる:
# {{math|0}}-組 {{math|&empty;}};
# {{mvar|n}}-組 {{math|1=''x'' = (''a''{{sub|1}}, ''a''{{sub|2}}, …, ''a{{sub|n}}'')}} と右に追加される要素 {{mvar|b}} に対し、<math>(a_1, a_2, \ldots, a_n, b) := \{\{x\}, \{x, b\}\}</math>

== {{mvar|n}}-組の総数 ==
{{main|重複順列}}
[[離散数学]]、特に初等[[組合せ論]]および有限[[確率論]]において、{{mvar|n}}-組は様々な数え上げ問題において、長さ {{mvar|n}} の（あまり形式ばらない意味での）要素の並びを表すために用いられる{{sfn|D'Angelo|West|2000|p=9}}。{{mvar|m}}-元集合から要素をとって作られる {{mvar|n}}-組は[[重複順列]] (''arrangement with repetition'') と呼び、その総数は {{mvar|m{{sup|n}}}} 個である。これは組合せ論における[[数え上げの積の法則|積の法則]]からわかる{{sfn|D'Angelo|West|2000|p=101}}。この数は[[濃度 (数学)|位数]] {{mvar|m}} の有限集合 {{mvar|S}} の {{mvar|n}}-重[[直積集合|デカルト積]] {{math|''S'' × ''S'' × ⋯ × ''S''}}（この直積集合の元は考えている重複順列 ({{mvar|n}}-組) のことに他ならない）の位数に等しい。

== 型理論 ==
{{main|{{仮リンク|直積型|en|Product type}}}}
[[プログラミング言語]]に広く用いられる[[型理論]]において、順序組は{{仮リンク|直積型|en|product type}}を持つ（これは組の長さも各成分のもつ型も固定しない意味で言う）。形式的には
: <math>(x_1, x_2, \ldots, x_n) : \mathsf{T}_1 \times \mathsf{T}_2 \times \ldots \times \mathsf{T}_n</math>
であり、射影は項構成子:
: <math>\pi_1(x) : \mathsf{T}_1,~\pi_2(x) : \mathsf{T}_2,~\ldots,~\pi_n(x) : \mathsf{T}_n</math>
である。関係モデルで用いられるラベル付き要素の順序組は{{仮リンク|レコード (計算機科学)|en|Record (computer science)|label=レコード型}}を持つ。これらの型は[[単純型付きラムダ計算]]の単純拡大として定義できる<ref name="pierce2002">{{cite book|last=Pierce|first=Benjamin|title=Types and Programming Languages|publisher=MIT Press|year=2002|isbn=0-262-16209-1|pages=126–132}}</ref>。

型理論における順序組の概念と集合論における順序組の概念には以下のような関係がある: 型理論の自然なモデルを考えれ、意味論的解釈にスコット括弧を用いれば、適当な集合 <math>S_1, S_2, \ldots, S_n</math>（ここでイタリックは集合をあらわし、その型特別するために用いることに注意）からなるモデルとして
: <math>[\![\mathsf{T}_1]\!] = S_1,~[\![\mathsf{T}_2]\!] = S_2,~\ldots,~[\![\mathsf{T}_n]\!] = S_n</math>
および基本項の解釈が
: <math>[\![x_1]\!] \in [\![\mathsf{T}_1]\!],~[\![x_2]\!] \in [\![\mathsf{T}_2]\!],~\ldots,~[\![x_n]\!] \in [\![\mathsf{T}_n]\!]</math>
とすれば、この型理論における {{mvar|n}}-組は集合論における {{mvar|n}}-組として自然な解釈<ref>Steve Awodey, [http://www.andrew.cmu.edu/user/awodey/preprints/stcsFinal.pdf ''From sets, to types, to categories, to sets''], 2009, [[preprint]]</ref>
: <math>[\![(x_1, x_2, \ldots, x_n)]\!] = (\,[\![x_1]\!], [\![x_2]\!], \ldots, [\![x_n]\!]\,)</math>
を持つ。{{仮リンク|ユニット型|en|unit type}}は {{math|0}}-組を意味論的解釈に持つ。

== 注 ==
=== 注釈 ===
{{reflist|group="注釈"}}
=== 出典 ===
{{Reflist}}

== 参考文献 ==
{{refbegin}}
* {{citation|first1=John P.|last1=D'Angelo|first2=Douglas B.|last2=West|title=Mathematical Thinking/Problem-Solving and Proofs|year=2000|edition=2nd|publisher=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.&nbsp;7–8
* [[Abraham Adolf Fraenkel]], [[Yehoshua Bar-Hillel]], [[Azriel Lévy]], ''[https://books.google.com/books?q=Foundations+of+set+theory&btnG=Search+Books Foundations of set theory]'', Elsevier Studies in Logic Vol. 67, Edition 2, revised, 1973, ISBN 0-7204-2270-1, p.&nbsp;33
* [[Gaisi Takeuti]], W. M. Zaring, ''Introduction to Axiomatic Set Theory'', Springer [[Graduate texts in mathematics|GTM]] 1, 1971, ISBN 978-0-387-90024-7, p.&nbsp;14
* George J. Tourlakis, ''[https://books.google.com/books?as_isbn=9780521753746 Lecture Notes in Logic and Set Theory. Volume 2: Set theory]'', Cambridge University Press, 2003, ISBN 978-0-521-75374-6, pp.&nbsp;182–193
{{refend}}

== 関連項目 ==
* [[タプル]]
* [[アリティ]]
* [[指数対象]]
* [[形式言語]]
* {{仮リンク|素数k組|en|Prime k-tuple}}: 双子素数、三つ子素数、……
* [[多項関係]]

== 外部リンク ==
* {{nlab|id=tuple}}
* {{MathWorld|urlname=n-Tuple|title=n-Tuple}}
* {{PlanetMath|urlname=orderedtuplet|title=ordered tuplet}}
* {{SpringerEOM|urlname=Tuple|title=Tuple}}


{{Set theory}}
{{Authority control}}
{{DEFAULTSORT:しゆんしよくみ}}
[[Category:数学の表記法]]
[[Category:列 (数学)]]
[[Category:集合の基本概念]]
[[Category:数学に関する記事]]