順序組

順序組（タプル）とは

数学における順序組（じゅんじょぐみ）、または単に組（タプル）とは、要素を特定の順序で並べたものです。特に、n個の要素を並べたものをn-組と呼びます。要素の順序が重要であり、同じ要素でも順序が異なれば別の組として扱われます。例えば、(1, 2)と(2, 1)は異なる組です。

n-組の例:

0-組：要素がない組。空組とも呼ばれます。
1-組：要素が1つの組。その要素と同一視されることもあります。
2-組：2つの要素からなる組。特に順序対とも呼ばれます。
3-組：3つの要素からなる組。三つ組とも呼ばれます。
4-組：4つの要素からなる組。四つ組とも呼ばれます。

順序組は、要素をコンマで区切り、丸括弧で囲んで表記することが一般的です。例：(2, 7, 4, 1, 7)は五つ組です。ただし、場合によっては角括弧や山括弧、波括弧が使われることもあります。

順序組の性質

順序組の最も重要な性質は、二つのn-組が等しいかどうかは、各要素が順番通りに等しいかどうかで判断されるという点です。つまり、

(a₁, a₂, ..., aₙ) = (b₁, b₂, ..., bₙ) であるためには、a₁ = b₁, a₂ = b₂, ..., aₙ = bₙ がすべて成り立つ必要があります。

この性質から、順序組は集合とは異なることがわかります。

重複: 順序組は同じ要素を複数持つことができますが、集合では重複した要素は一つとして扱われます。例：(1, 2, 2, 3) ≠ (1, 2, 3)　一方、{1, 2, 2, 3} = {1, 2, 3}
順序: 順序組は要素の順序を変えると別の組になりますが、集合では要素の順序は関係ありません。例：(1, 2, 3) ≠ (3, 2, 1)　一方、{1, 2, 3} = {3, 2, 1}

順序組の定義

順序組は、その性質を満たすものとして定義されます。いくつかの定義方法が存在します。

写像としての定義

順序組は、写像F: X → Yと見なすことができます。ここで、Xは組の各要素を指し示す添字の集合、Yは要素全体の集合です。このとき、

(a₁, a₂, ..., aₙ) ⇔ (X, Y, F)

と定義できます。具体的には、

X = {1, 2, ..., n}
Y = {a₁, a₂, ..., aₙ}
F = {(1, a₁), (2, a₂), ..., (n, aₙ)}

より直観的に表現すると、

(a₁, a₂, ..., aₙ) = (F(1), F(2), ..., F(n))

となります。

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

順序組を、順序対を入れ子にすることで定義する方法もあります。この定義では、順序対は既に定義されているものとします。

0-組（空組）は空[[集合]]∅とします。
n > 0 に対するn-組は、初項と(n-1)-組の順序対として定義します。

(a₁, a₂, a₃, ..., aₙ) := (a₁, (a₂, a₃, ..., aₙ))

この構成を繰り返すことで、

(a₁, a₂, a₃, ..., aₙ) = (a₁, (a₂, (a₃, (..., (aₙ, ∅)...))))

と表現できます。

また、要素を後ろに追加していく形で定義することもできます。

0-組は ∅
n > 0 に対して (a₁, a₂, a₃, ..., aₙ) := ((a₁, a₂, a₃, ..., aₙ₋₁), aₙ)

したがって帰納的に、

(a₁, a₂, a₃, ..., aₙ) = ((...(((∅, a₁), a₂), a₃)...), aₙ)

と定義できます。さらに、順序対自体が集合として定義される場合（例えば、クラトフスキーの定義）、順序組も集合を用いて定式化できます。

0-組 ∅
n-組x = (a₁, a₂, ..., aₙ)と、右に追加される要素bに対して
(a₁, a₂, ..., aₙ, b) := {{x}, {x, b}}

n-組の総数

離散数学や組合せ論では、n-組は要素の並びを表すために利用されます。m個の要素からなる集合から要素を選んでn-組を作る場合、その総数は mⁿ 個となります。これは、組合せ論における積の法則から導かれます。この数は、m個の要素を持つ集合のn個の直積[[集合]]の位数と等しくなります。

型理論における順序組

プログラミング言語の型理論では、順序組は直積型を持ちます。形式的には、

(x₁, x₂, ..., xₙ) : T₁ × T₂ × ... × Tₙ

と表されます。射影は項構成子として定義されます。

π₁(x) : T₁, π₂(x) : T₂, ..., πₙ(x) : Tₙ

関係モデルで使用されるラベル付き要素の順序組は、レコード型を持ちます。これらの型は、単純型付きラムダ計算の拡張として定義できます。型理論における順序組と集合論における順序組の間には密接な関係があり、型理論の自然なモデルを考慮すると、集合論における順序組として解釈できます。ユニット型は0-組に対応します。

まとめ

順序組は、数学や計算機科学、論理学など、様々な分野で用いられる重要な概念です。要素の順序が重要であり、集合とは異なる性質を持つことを理解することが重要です。この記事では、順序組の定義、集合との違い、様々な表現方法、型理論における意味について解説しました。

関連項目

タプル
アリティ
指数対象
形式言語
素数k組
多項関係

もう一度検索