有限関係

数学において、集合の列X ₁、...、X _n上の有限関係は、直積X ₁ × ... × X _nのサブセットです。つまり、n組( x ₁、...、x _n )の集合であり、各組は対応するX _iの要素x _iの列です。^{[1] [2] [3]通常、関係は}n組の要素間の可能な接続を表します。たとえば、「xはyとzで割り切れる」という関係は、 x、y、zにそれぞれ代入すると文が真になる 3 組の集合で構成されます。

関係の「場所」の数を与える非負の整数n は、関係のarity、adicity、またはdegreeと呼ばれます。 n 個の「場所」を持つ関係は、 n項関係、n進関係、またはdegree nの関係などと呼ばれます。 場所の数が有限の関係は、 finitary 関係(または、文脈が明らかな場合は単に関係)と呼ばれます。 この概念を、無限シーケンスを持つinfinary 関係に一般化することもできます。^[4]

2 つのオブジェクト、性質、クラス、または属性を心で一緒に見たときに、何らかのつながりがあるように見える場合、そのつながりは関係と呼ばれます。

— オーガスタス・ド・モルガン^[5]

意味

Rは集合X ₁ , ..., X _n上のn項関係であり、直積X ₁ × ... × X _nの部分集合によって与えられる。^[1]

定義は基になる集合X ₁、 ...、X _nに基づいているため、R はより正式には ( n + 1 ) 組( X ₁、 ...、X _n、G )として定義されます。ここで、GはRのグラフと呼ばれ、直積X ₁ × ... × X _nのサブセットです。

数学でよく行われるように、数学的対象と基礎となる集合を指すのに同じ記号が使用されるため、( x ₁ , ..., x _n ) ∈ Rという文は、 ( x ₁ , ..., x _n ) ∈ Gという意味でよく使用され、これは「x ₁ , ..., x _nはRに関連している」と読み、接頭表記法ではRx ₁ ⋯ x _n、接尾表記法ではx ₁ ⋯ x _n Rと表記されます。Rが2 項関係である場合、これらの文は中置表記法ではx ₁ Rx ₂と表記されます。

以下の考慮事項が適用されます。

• 集合X _iはRのi番目の定義域と呼ばれる。^[1] Rが二項関係の場合、 X _1は単にRの定義域または出発点集合とも呼ばれ、X _2はRの共定義域または目的地集合とも呼ばれる。
• X _iの要素が関係であるとき、X _{i は}Rの非単純領域と呼ばれる。^[1]
• 少なくとも1つの( x ₁ , ..., x _n )に対してRx ₁ ⋯ x _{i −1} x _i x _{i +1} ⋯ x _nとなる∀ x _i ∈ X _iの集合は、 Rのi番目の定義域またはアクティブドメインと呼ばれます。^[1] Rが2項関係の場合、その最初の定義域は単にRの定義域またはアクティブドメインとも呼ばれ、2番目の定義域はRの定義余域またはアクティブ余域とも呼ばれます。
• Rのi番目の定義域がX _iに等しいとき、R はそのi番目の定義域で（または、あいまいでない場合はX _i上で）全であるといわれる。 Rが 2 項関係の場合、 R がX ₁上で全であるとき、それは左全または直列であるとも言われ、R がX ₂上で全であるとき、それは右全または全射であるとも言われる。
• ∀ x ∀ y ∈ X _i . ∀ z ∈ X _j . xR _ij z ∧ yR _ij z ⇒ x = y （ i ∈ I 、 j ∈ J 、 R ij ₌ π ij _R、 { I 、 J }が{ 1、...、n }の分割）のとき、Rは{ X _i } _{i ∈ I}上で一意であるとされ、{ X _i } _{i ∈ J}はRの主キー[ ^1]と呼ばれます。 Rが二項関係の場合、 R が{ X ₁ }上で一意であるとき、左一意または単射であるとも言われ、Rが { X _{2 } 上で一意であるとき、}一価または右一意であるとも言われます。
• すべてのX _iが同じ集合Xである場合、 RをX上のn項関係として参照する方が簡単であり、同次関係と呼ばれます。この制限がない場合、R は異次関係と呼ばれます。
• X _iのいずれかが空の場合、定義する直積は空であり、そのようなドメインのシーケンス上の唯一の関係は空の関係R = ∅です。

ブール領域 Bを2 要素の集合、たとえばB = {0, 1}とし、その要素を論理値、典型的には0 = falseおよび1 = trueとして解釈できるようにします。Rの特性関数はχ _Rで表され、ブール値関数χ _R : X ₁ × ... × X _n → Bであり、Rx ₁ ⋯ x _nの場合はχ _R ( ( x ₁ , ..., x _n ) ) = 1、それ以外の場合はχ _R ( ( x ₁ , ..., x _n ) ) = 0と定義されます。

応用数学、コンピュータサイエンス、統計学では、ブール値関数をn項述語と呼ぶのが一般的です。形式論理とモデル理論のより抽象的な観点からは、関係R は論理モデルまたは関係構造を構成し、何らかのn項述語記号 の多くの可能な解釈の 1 つとして機能します。

関係は多くの科学分野や数学や論理学の多くの分野で生じるため、用語にはかなりのバリエーションがあります。関係概念または用語の集合論的 拡張とは別に、「関係」という用語は、関係内のすべての要素が共有する内包または抽象的特性の全体である論理的理解、またはこれらの要素と内包を表す記号のいずれか、対応する論理的実体を指すためにも使用できます。さらに、後者の信奉者の中には、より具体的な意味合いを持つ用語を導入する人もいます (特定の関係概念の集合論的拡張に対して「関係構造」など)。

ヌラリ (0 項) 関係には、決して成立しない空のヌラリ関係と、常に成立する普遍的なヌラリ関係の 2 つのメンバーのみが含まれます。これは、0 タプルが空のタプル () のみであり、すべての 0 タプルの (単一) セットのサブセットが正確に 2 つ存在するためです。これらは、帰納的議論の基本ケースを構築するのに役立つ場合があります。

単項関係は、何らかの特性（ノーベル賞を受賞したことなど）を持つメンバーの集合（ノーベル賞受賞者の集合など）として考えることができます。

すべてのゼロ項関数は単項関係です。

二項関係は有限関係の中で最も一般的に研究されている。同次二項関係（X ₁ = X ₂）には以下が含まれる。

• 等号と不等号は、「 5 < 12」などの文では=や<などの記号で表されます。
• 割り切れるかどうかは、「 13 | 143」などの文では記号 | で表されます。

異種二項関係には以下が含まれる。

• 集合のメンバーシップ。「 1 ∈ N 」などの文では記号 ∈ で表されます。

三項関係には、たとえば、 2 つの入力と出力を関連付ける2 項関数が含まれます。同次三項関係の 3 つのドメインはすべて同じセットです。

人々の集合P = { Alice, Bob, Charles, Denise }上の三項関係R「x はyが好きだと思っている」を考えます。これは次のように定義されます。

R = { (アリス、ボブ、デニス)、(チャールズ、アリス、ボブ)、(チャールズ、チャールズ、アリス)、(デニス、デニス、デニス) }。

R は次の表で同等に表すことができます。

ここで、各行はRの 3 つ組を表します。つまり、「xはy がz を好きだと思っている」という形式のステートメントを作成します。たとえば、最初の行は「アリスはボブがデニスを好きだと思っている」と述べています。すべての行は異なります。行の順序は重要ではありませんが、列の順序は重要です。^[1]

上記の表は、リレーショナルデータベースの簡単な例でもあります。リレーショナルデータベースは、リレーショナル代数に根ざした理論とデータ管理への応用を持つ分野です。^[6]しかし、コンピュータ科学者、論理学者、数学者は、一般的な関係とは何か、それが何から構成されているかについて、異なる概念を持つ傾向があります。たとえば、データベースは、定義上有限である経験的データを処理するように設計されていますが、数学では、無限のアリティを持つ関係（つまり、無限関係）も考慮されます。

論理学者オーガスタス・ド・モルガンは、1860年頃に出版された著作の中で、現在のような意味での関係の概念を初めて明確に表現した人物である。また、関係の理論における最初の正式な結果を述べた（ド・モルガンと関係については、Merrill 1990を参照）。

チャールズ・パース、ゴットロープ・フレーゲ、ゲオルク・カントール、リヒャルト・デデキントらは関係理論を発展させた。彼らのアイデアの多く、特に順序と呼ばれる関係については、 『数学原理』（1903年）にまとめられており、バートランド・ラッセルはこれらの結果を自由に利用した。

1970年にエドガー・コッドはデータベースのリレーショナルモデルを提案し、データベース管理システムの発展を予見した。^[1]