◻️ 👨🏿‍💻 🍪 関係の定量的特性 🐟 💆🏾 👨🏿‍🤝‍👨🏽

数学および多くの主題分野（意思決定、知識とデータベース、数学的言語学、プロセスモデリングなど）における関係理論は非常に注目に値する役割を果たしますが、まだ完全にはほど遠いです。数学的知識の他の分野と同様に、彼女のよく知られた結果は、それらを列挙する問題よりも、特定のオブジェクトの存在に関する質問や問題に大きく関係しています。理論の特定の分野の研究者は、パノラマ全体を観察するために、関心のあるオブジェクトとその依存関係の全体像に関心を持つ必要があるように思われます。しかし、残念ながら、そのようなパノラマを作成または提供している人はいないため、これを行うことは非常に問題があります（写真）。仕事で提案された関係のカタログでさえ問題を閉じません。

簡単な例。何年も前の本[1p。207]で、私はそのような段落に出くわしました。

部分的に順序付けられたセットの理論には、まだ多くの未解決の問題が含まれています。n≥6の場合、与えられた数nの要素から構築できるそのようなセットの数の問題でさえまだ存在しません。直接計算は、S（n）が部分的に順序付けられたセットの数である場合、S（2）= 3、S（3）= 19、S（4）= 219、S（5）= 4231、および数Snであることを確立することに成功しました。（n）非同形セットの場合、n = 4およびn = 5の要素でのみ検出されました：Sn（4）= 16およびSn（5）= 63。

モスクワ州立大学の学部長、リブニコフK.A.私はこれをさらに深く掘り下げたいと思っていましたが、解決策を探し、少なくとも何らかの方法でリストを拡張し、そして最も重要なことに、部分的な順序をリストし、それらのプロパティで実際に分散していることを確認できるようでした。結果を壁に掛けるだけです。研究プログラムの開発、部分的な順序の実行可能なモデルの作成、プログラムの作成とデバッグに多くの労力が費やされたことを告白します。コンピューターはプログラムされたアルゴリズムを数十時間回転させていました。誰かの（偉人からの）発言は、数学の基礎は数ではなく順序であるべきだと私の頭に浮かびました。そうすれば、おそらく多くの定理がより単純でより透明な証明を受け取ったでしょう。

大きなセットキャリアの関係の数を計算し、関係を列挙することを学びましたが、数S（n）に対しても厳密な式を取得できませんでした。今回は、コンピューターの結果とその分析のほぼすべての出力の後に、モデル、アルゴリズムを変更、改善するためのアイデアが生まれ、新しい仮説をテストするために修正が行われたとき、私自身と同僚の集中的な創造的成長の期間として思い出しますが、重要なもの（~~おそらく脳~~）はそうではありませんでした足りる。

私が何とか開いた（取得した）ものを以下のテキストで示します。ちなみに、他の外国人研究者の結果は私たちの結果と一致しましたが、彼らは数S（n）のみを報告し、部分的な注文の列挙については言及していませんでした。

私たちは小さく始めました。任意のn-キャリアセットのバイナリ関係の完全なリストは既知であり、簡単に取得できます。彼らは質問への答えを探していました：与えられたnに対して、固定された1つのプロパティ、プロパティのペア、トリプルなどとの関係がいくつあるか。このデータがあれば、列挙ではなく、そのような関係を列挙するための直接的なアルゴリズムを構築できました。 OccamのRazorRuleに従うことで、余分なエッセンスを生成しません。

ここでは、バイナリリレーション（BR）でこのような結果を取得する方法について説明します。

したがって、BOのnセットキャリアとすべてのBOの完全なリスト、およびBOプロパティのリストがあり

ます。反射防止;部分的な反射性;

-対称性;非対称性;非対称;非対称;

-一時性; 反遷移性;

-弱い秩序; 厳格な順序; 部分的な順序; 完璧（線形）;

-許容範囲;

-同等性;

-周期性;

-完全性。

バイナリ関係のタイプの定量的特性

リレーションシップには、1つの特定のプロパティだけでなく、プロパティのペア、トリプレットなどのセットも含めることができます。実際にそのような関係を使用することは一般的な状況です。したがって、たとえば、許容範囲（無関心）の各姿勢には、対称性と反射性という2つの特性があります。この一連のプロパティによって、許容関係のタイプが決まります。

別のタイプの関係は、許容関係から、対称性、反射性、および遷移性というプロパティの拡張リストの実現可能性が必要な場合に発生します。おそらくすべての許容関係が一時的なものであるとは限らないことは明らかですが、3つの名前付きプロパティのセットを持つものは、同等性と呼ばれる新しいタイプの関係を形成します。

等価関係のセットは、許容関係のセットにネストされていることがわかります。たとえば、カタログでは、これらのタイプの関係は塗りつぶしによって強調表示されています（8つの許容値と、そのうちの5つだけが同等です）。プロパティのセットまたはそれらの1つを持つBOの数について疑問が生じます。

反射性

セットA = {の関係α= <Å、A>

а_{1}, а_{2}, . . ., а_{n}

${_1,_2,...,_n}$ }は、各ペア（）が反射的である（反射性の特性を持っている）場合

а_{i}, а_{i}

$_ i, _ i$ ）はこの関係を満たします。ここで、Mは関係のグラフ（グラフではありません）です

а_{i} α а_{i}, а_{i} є A, i = 1 (1) | A |

$_ i α _ i , _i є A , i = 1(1)|A|$ ..。

言い換えれば、グラフ行列の主対角Åの比率は1で満たされます。再帰関係グラフでは、すべての頂点にループがあります。いいえの場合、態度は反反射的です

а_{i} є A, i = 1 (1) | A |

$_i є A , i = 1(1)|A|$ 行われていません

а_{i} α а_{i}

$_ i α _ i$ ..。この場合、主対角線上の反反射関係αの行列は単一の単位を持ちません。ゼロがあり、対応するグラフにはどの頂点にもループがありません。

最後に、関係αは、一部の場合、無反射です。

а_{i} є A, а_{i} α а_{i}

$_i є A ,_ i α _ i$ 実行されますが、他の人にとっては実行されません。そのような関係は部分的に反射的であると考えます。主対角上の無反射関係の行列には、部分的に1、部分的に0が含まれています。このような無反射関係のグラフには、すべての頂点にループがありません。

反射関係の典型的な例は、マトリックス表現の主対角、単位（E =Δ）比です。平等関係（カタログ番号68）。この比率のグラフは、マトリックスの主対角線上にある点（ペア）と対応するペアによって形成されます。

(i, i) А, i = 1 (1) | A |

$( i , i ) , i =1(1)|A|$ 、グラフには他のポイントは含まれていません。

この比率のマトリックス表現は、アイデンティティマトリックス（E）に対応します。対角関係グラフは、ループが割り当てられているセットAの要素に対応する頂点によって形成されます。対角関係はしばしばによって示されます

Δ_{А}

$Δ_$ ..。

反射関係の場合、対応するグラフも反射的であり、反反射関係の場合、そのグラフは反反射的です。ある関係αについて、それが反射的であることがわかっている場合、補数ᾱは常に反反射的であり、

α \cap ᾱ = \emptyset, α \cap Δ_{А} = Δ_{А}

$α ∩ ᾱ =∅ , α ∩ Δ_ = Δ_$ ..。

反反射関係βについては、それは真実です

β \cap Δ_{А} = \emptyset

$β ∩Δ_= ∅$ ..。

例1。セットNの関係≤（これ以上）は反射的であり、同じセットの関係<（少ない）は反反射的です。

誰も自分の息子ではないので、「息子である」という態度は反反射的です。

実用的な目的のために、カーディナリティ| A |でセットAに与えられた関係の完全なセットで利用可能な反射関係の数を数える必要がある場合があります。 = n。

そのような計算をどのように実行できるかを示しましょう。平面上で二元反射関係αの行列を考えます。常にすべての対角点が含まれます。

ペア（i、j）に対応する残りのポイント（n×n-n = n（n – 1）の数）は、異なる構成と数kに含めることができます（k = 0（1）（n×n-n））可能な関係に、もちろん、それは反映されます。合計することによってk個の組み合わせ（N-1）N上K、反射関係の総数が決定される

場合K = N（N-1）/ 2であることに弧（エッジ）の数のN-ループなし頂点グラフ。

非反射関係の数は、Aの関係の総数と反射関係の数の差として定義されます。

この式から、無反射関係のセットには次のものが含まれます。

(2^{n} - 1)

$(2^n -1)$ 反射的な関係よりも何倍も多くの関係があります。この過剰な比率は、グラフの対角点のみのさまざまな組み合わせによって生成されますが、構成と残りの点の数は単純に繰り返されます。

非反射関係のセットからの反反射関係の数は、反射関係の数と正確に同じです。

2^{n^{2} - n}

$2^{n^2-n}$ ..。これは、反射関係と反反射関係の間に1対1の対応を確立できるという事実に基づいています。各反射関係から、対角線のすべての点を削除することにより、単一の反反射関係を取得できます。その逆も同様です。

対称

対称性の特性により、関係のセット全体は、対称、非対称の4つのクラスに分類されません。後者は、次に、非対称、非対称、および残りの非対称の3つのクラスに分類されます。

セットAの関係α= <Å、A>は、あるペアの場合、対称です（グラフMの主対角線と一致する直線に関して対称の特性があります）。

(i, j) є A \times A

$(i, j) є A×A$ の

а_{i} α а_{j}

$_i α _j$ すべき

а_{j} α а_{i}

$_j α _i$ ..。言い換えれば、どのペアでも

((а_{i}, а_{j}) є Å)

$((_i, _j) є Å)$ 両方向で実行されるか、まったく実行されません。

対称関係のグラフでは、頂点iとjのペアが円弧（i、j）で接続されている場合、必ず円弧（j、i）で接続されています。対称関係グラフは、対称指向の、または単に無指向の通常のグラフです。からの場合、

比率αは非対称です

а_{i} α а_{j}

$_i α _j$ そして

а_{j} α а_{i}

$_j α _i$ したがって、i = jとなります。

非対称比率マトリックスは、必ずしも主対角線上にすべてのものを含むとは限らず、主対角線に対して対称な2つの位置（対角線の上または対角線の下）のいずれかに1つを含みます。この関係のグラフは、それらのすべてまたは一部にループがある頂点によって形成され、グラフ内の頂点のペア（i、j）が接続されている場合、それは常に一方向のみの円弧になります。対称関係と非対称関係の場合、いくつかの対角点を含めることも含めないこともできることに注意してください。

非対称関係に単一の対角点が含まれていない場合、そのような関係は非対称であると言われます。それは常に反射防止です。

例2..。セットNの関係（≤）は非対称であり、同じセットの関係（<）は非対称です。確かに、最初のケースでは

а_{i} \leq а_{j}

$_i ≤_j$ そして

а_{j} \leq а_{i}

$_j ≤_i$ フォローすることしかできません

i = j

$i = j$ ..。Nの等式関係（=）は対称であり、関係α= A×Aも対称です。

任意の対称比αについて、それは常に真です

α = α^{- 1}

$α = α^{-1}$ そして

α^{- 1}

$α^{-1}$ また対称。非対称関係の場合、

α \cap α^{- 1} \subseteq ∆_{A}

$α ∩ α^{-1}⊆∆_A$ ..。グラフに対称点と非対称点の両方が含まれる一般的な関係は、対称ではありません。この関係は非対称ですが、非対称ではなく、非対称でもありません。

対称性の特性は、n-ary関係にも現れます。セットの関係R

Х = x_{1}, x_{2}, \dots, x_{n}

$= { x_1, x_2,…,x_n}$ それが要素と一緒になっている場合、対称的なn-ary関係です

< x_{i 1}, x_{i 2}, \dots, x_{i n} > є R

$<x_{i1}, x_{i2}, …,x_{in}>є R$ シーケンスが含まれています

< x_{j 1}, x_{j 2}, \dots, x_{j n} >

$< x_{j1}, x_{j2},…, x_{jn}>$ セットXのメンバーの順列によって形成され

ます。非対称関係は常に反反射的であることに注意してください。非反射的で推移的なバイナリ関係は常に非対称です。練習や計算の実行には、グラフの対称性に関連する特定のプロパティを持つ関係の数が重要です。カーディナリティ| A |の任意のセットAについてそのような比率を計算してみましょう。 = n。

私たちの議論では、他の多くのように、まだ十分に深く研究されていない反射性の特性に依存します。すべての関係のセットの表面的な分析でさえ、それは常に次のように分割できると結論付けることができます。

2^{n}

$2^n$ 同じサイズのクラス、およびこれらのクラスを形成する関係の構成は、特定のパターンに従います。

すべてのクラスの関係のセットは同じ構造を持ち、対角点の数と構成のみが異なり、その種類全体は数によって決定されます

2^{n}

$2^n$ ..。固定nの関係の対角線の状態を、その上の点の数と構成によって定義し、特定の関係に属します。対角線のセルの塗りつぶされた状態の固定セットの場合、ブール値によって決定されることは明らかです。

2^{∆}

$2^∆$ 、ここで、∆は、カーディナリティのカルテシアン二乗のグラフの対角線の点の完全なセットです| ∆ | = n。

したがって、関係の理論では、2つの極端な状態のみが伝統的に考慮され、研究されてきました。対角線のすべての点が関係に含まれ、反射的であるか、関係に対角線点が含まれず、反射防止です。

すべての中間状態を、1つの対角点、2つの対角線など、k次の部分反射率k = 0（1）nと呼びます。この種の関係は、部分反射率です。したがって、ゼロ次の部分的な反射関係は反反射関係であり、n次の部分的な反射関係は単なる反射関係です。

すべての状態は、セット∆のブール値の要素として順序付けできることに注意してください。提案されたアプローチにより、さまざまなプロパティを分析し、個々のプロパティまたはそれらの集合体との関係の数を数える方法の概要を説明できます。

関係を反射的で対称的であると見なしましょう。比率の対称性は、相対的な対角線に対して対称に比率のマトリックスに配置されているポイントのペアの存在によって決定されます。任意のn個のそのようなペアに対して、

C_{n}^{2}

$C_n^2$ ..。これらのペアのセットを記号Sで示します。

次に、対称関係と反射関係のすべての種類がブール値によって決定されます。

2^{S}

$2^S$ ..。これらの関係の多くは、少し後で詳しく検討されますが、ここでは、それらが無関心または寛容の空間を形成していると言います。許容比の数がブールの力によって決定されることは明らかです

2^{S}

$2^S$ 、つまり

2^{C_{n}^{2}}

$2^{C_n^2}$ ..。

以下の表。図1は、自然数のセグメントからの初期値nの許容比率の数の値を示しています。

表1。耐性のあるBOの数

対角点の有無によって対称性が変わらないため、すべての対称関係のカーディナリティを簡単に計算できるようになりました。対称関係のセットは、記号SMで示されます。次に、固定nに対するこのセットのカーディナリティは、次の式によって決定されます。

| S M | = 2^{n} \cdot 2^{C_{n}^{2}} = 2^{C_{n + 1}^{2}},

$|SM| = 2^n·2^{C_n^2} = 2^{C_{n+1}^2},$

ここで、nは比率の対角点の数です。テーブル 2は値を示しています| SM | いくつかのnのために。

表2。対称BOの数

次に、非対称関係の計算に移りましょう。そのセットはASで示されます。これらの関係は、対角線のすべての点がそれらに存在せず、対角線の外側にある関係の行列のセルのいずれも対称的なものを持たないという事実によって特徴付けられます。言い換えれば、それは反射防止と非対称の関係のセットです。

このセットのカーディナリティは、式から決定できます。

| A S | = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k} = 3^{C_{n}^{2}},

$|AS| = Σ_{k=0}^K C_K^k·2^k = 3^{C_n^2},$

ここで、K =

C_{n}^{2}

$C_n^2$ ..。

セットASのカーディナリティを計算するための縮小式を取得します-キャリアの特定のカーディナリティの非対称関係| A | = n。定義上、セットASのすべての関係は反反射的であるため、関係のマトリックスの主対角線は空であり、単位要素はマトリックスの残りの位置の半分にのみ配置できます。で

C_{n}^{2} = (n^{2} - n) : 2

${C_n^2} =(n^2-n):2$ セル。

したがって、非対称関係にk要素（点、順序付けられたペア）が含まれていると仮定します0≤k≤

C_{n}^{2}

${C_n^2}$ ..。そのような数の要素との関係の数は明らかにからの組み合わせの数に等しくなります

C_{n}^{2}

$C_n^2$ kによって。

この場合、k個の要素のそれぞれに、対称位置のペアを関連付けます。1つはマトリックスの主対角線の上、もう1つは対角線の下です。各ペアでは、要素は2つの位置のいずれかにある可能性があるため、ブール値はk個の要素に対応しているように見えます。

2^{n}

$2^n$ 機会。

この方法では、

C_{n}^{2}

$C_n^2$ からの位置のkペアの選択肢の数です

C_{n}^{2} = K

$C_n^2 = K$ 関係のマトリックス表現で使用可能なペア、および

2^{n}

$2^n$ -各ペアの位置にk個の要素を配置する機会の数。k個の要素を含む関係の数は、これらのk個の要素を配置するためのオプションの数による位置のペアの選択の数の積として定義されます。

2^{k} C_{K}^{k}

$2^kC_K^k$ ..。

セットAS内の関係の総数は、ゼロから最大許容K =までのkのすべての値にわたって取得された積を合計することによって取得されます

C_{n}^{2} = K

$C_n^2 = K$ 、つまり

| A S | = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k} = 3^{C_{n}^{2}},

$|AS| = Σ_{k=0}^K C_K^k·2^k = 3^{C_n^2},$

ここで、K =

C_{n}^{2}

$C_n^2$ ..。

例3.サポートのセットのカーディナリティを| A | = 5.見つかった式を使用して、非対称関係の数を計算します。合計の上限Kの値を決定します。K=

C_{n}^{2}

$C_n^2$ = 10。被加数を計算するためのデータを表に示します。3.

表3。BOの特徴

セットASのカーディナリティを計算する別の方法があります。これは、対称位置のペアのセットから、そのような各ペアが存在できる状態のセットへのマッピングの数をカウントすることに基づいています。非対称の関係では、

K = C_{n}^{2}

$K = C_n^2$ 位置のペア。

セルのペアの各位置は0または1で占めることができますが、位置のペアにはS = 3の状態があり、次のように示します。

-1、要素（1）が対角線の上に配置されている場合。

-2、要素（1）が対角線の下に配置されている場合。

-両方の位置が空の場合は3（ゼロで占められている）。

したがって、（関係マトリックス内の）対称位置のペアは

、3つの状態のいずれかで各関係にある可能性があります。位置のペアのセット（記号Kで示される）から状態のセットSへのすべての可能なマッピングを計算するための式：

φ : K \to S => | A S | = | S |^{| K |}

$φ: K → S =>|AS| =|S|^{|K|}$

例4。前の例の条件の場合、形式は| A | = 5、K = | K | =

K = C_{5}^{2} = 10,

$K = C_5^2 = 10,$ | S | = 3、次に、

| A S | = 3^{1} 0 = 59049

$|AS| = 3^10 = 59049$ ..。

計算結果は2つの異なる方法で一致し、得られた式の正確さをもう一度確信します。このように、私たちは関係を得ました

3^{C_{n}^{2}} = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k},

$3^{C_n^2} = Σ_{k=0}^K C_K^k·2^k,$

ここで、K =

C_{n}^{2} .

$C_n^2.$

テーブルであげましょう。非対称関係の4つの数| AS | nの値が小さい場合。

表4.非対称BOの数

非対称関係の数を決定するための式があると、別のものを得ることができます-対角点の有無は関係の非対称性の特性を変更しないため、非対称関係の数を計算するために。

したがって、非対称関係のセットを記号ANSで表すと、このセットのカーディナリティは次の式で決定されます。

| A N S | = 2^{n}

$|ANS| =2^n$

| A N S | = 2^{n} Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k} = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k + n} = 2^{n} 3^{C_{n}^{2}},

$|ANS| =2^n Σ_{k=0}^K C_K^k·2^k =Σ_{k=0}^K C_K^k·2^{k+n} =2^n3^{C_n^2},$

ここで、K =

C_{n}^{2}

$C_n^2$

以下は表です。5 n = 3（1）5の（ANS）値を含みます。

表5。非対称BOの数

以下では、ここで紹介するのに便利な概念が必要です。

バイナリ関係αの対称部分はと呼ばれます（そして

α^{(S)}

$α^{(S)}$ ）態度

α^{(S)} = α \cap α^{- 1}

$α^{(S)} =α∩α^{-1}$ と比率

α^{(а)} = α {\α}^{(S)}

$α^{()} = α \α^{(S)}$ （表示

α^{(а)}

$α^{()}$ ）はその非対称部分と呼ばれます。比率αが対称である特定のケースでは、

α^{(S)} = α

$α^{(S)} = α$ そして

α^{(S)}

$α^{(S)}$ 常に対称。αが非対称の場合、

α^{(а)} = α

$α^{()}= α$ そして

α^{(а)}

$α^{()}$ 常に非対称。

トランジティビティ（ラテントランジティバス-トランジショナル、トランジットから-トランジション）

-関係のプロパティの1つ。セットAで定義された関係= <M、A>は、

а_{i}, а_{j}, а_{k} є A

$_i, _ j, _k є A$ 条件が満たされている：から

а_{i} α а_{j}

$_iα _ j$ そして

а_{j} α а_{k}

$_jα _k$ すべき

а_{i} α а_{k}

$_iα _ k$ ..。

言い換えれば、その構成における要素の存在からの過渡的な関係のために（

а_{i} α а_{k}

$_iα _ k$ ）と（

а_{k} α а_{j}

$_kα _ j$ ）その結果、要素（

а_{i} α а_{j}

$_iα _ j$ ）。リレーショングラフの場合、このプロパティは、頂点のペア（

а_{i} α а_{j}

$_iα _ j$ ）は、頂点kを通過し、2つの連続する円弧（

а_{i} α а_{k}

$_iα _ k$ ）、（

а_{k} α а_{j}

$_kα _ j$ ）、同じ頂点が単一の円弧で直接接続されている（

а_{i} α а_{j}

$_iα _ j$ ）。マトリックス要素の場合[

а_{i j}

$_{ij}$ ]からの遷移関係αの

а_{i k} \cdot а_{k j} = 1

$_{ik}·_{kj} =1$ すべき

а_{i j} = 1

$_{ij} = 1$ ..。

バイナリリレーションの遷移プロパティの定義は、リレーションに少なくとも3つの要素（順序付けられたペア）が含まれていることを前提としています。そして、このプロパティは、1つの要素、空、または2つの要素のみを含む関係でどのように現れますか？

すべてのシングルトンと空の関係は一時的なものです。2つの要素の関係は、それに含まれるペアに共通の要素jが含まれている場合、遷移的および非遷移的である可能性があります。順序付けられたペアに対応するグラフアークは、一方向に向けられます（方向付けられた非遷移ルートを形成します）。

たとえば、（

а_{i}, а_{j}

$_i, _ j$ ）єαおよび（

а_{j}, а_{k}

$_j, _ k$ ）єα。公式化された定義では、次のことが必要です。関係αが遷移的であるためには、3番目のペア（アーク）が含まれている必要があります。

а_{i}, а_{k}

$_i, _ k$ ）が存在しないため、αの遷移性は満たされていません。

前と同じように、リレーションに共通の要素を持つ2つのペアのみが含まれている場合

а_{j} є A

$_j є A$ 、しかし、そのような共通の要素

а_{j} є A

$_j є A$ 両方のペアで同じ位置にあります（

а_{j}, а_{i}

$_j, _ i$ ）、（

а_{j}, а_{k}

$_j, _ k$ ）または（

а_{i}, а_{j}

$_i, _ j$ ）、

（

а_{k}, а_{j}

$_k, _ j$ ）、およびグラフ上の円弧が異なる方向に向けられている場合、関係に3番目のペアを含める必要がないため、このような関係は一時的なものになります。

2つのペアに共通の要素がない場合にも、遷移関係が発生します。遷移関係の例は次のとおりです。「等式」（=）、i = kであるため、k = jはi = jを意味します。 "私はjより大きい";ジオメトリ内-「直線の平行度」。非遷移関係の例：ジオメトリの「直線の垂直性」。「私はjと等しくありません」。

関係に関する文献では、トランジティビティを特徴付けるさまざまな概念を見つけることができます：弱いトランジティビティ、強いトランジティビティ、ネガティブトランジティビティ、アンチトランジティビティ、弱いアンチトランジティビティ、一般化されたトランジティビティ、トランジショナルクロージャと他のいくつか。ここでは、関係における推移性の特性のさまざまな形の現れを体系化する試みがなされています。

遷移関係αの場合、関係

α^{- 1}

$α^{–1}$ また、常に一時的です。任意の数の遷移関係の交差は、遷移関係です。関係αを含むすべての遷移関係の共通部分である関係ᾰを考慮すると、ᾰは関係αの遷移クロージャと呼ばれます。

トランジティブクロージャーᾰは、からのルールに従って、任意の関係αに対して構築できます。

а_{i} ᾰ а_{j}

$_i ᾰ _j$ 次のとおりです。

(\exists а_{к 1}, а_{к 2}, \dots, а_{к s}) (а_{i} α а_{к 1} Λ а_{к 1} α а_{к 2} Λ \dots Λ а_{к s} α а_{j})

$(∃_{1}, _{2}, …,_{s})( _iα _{1}Λ_{1}α _{2}Λ… Λ _{s}α _j)$ ..。

関係ᾰは、αを含む最小の遷移関係です。αが推移的である場合、それはその推移的閉鎖α=ᾰと一致し、逆もまた同様です。

有向グラフで遷移バイナリ関係を表す場合、ダイグラフ全体ではなく、その遷移スケルトンのみを表すことができます。各ルートの始点と終点を1つより長く結ぶ円弧は描画されません。この場合、グラフの遷移スケルトンは関係αに対して取られていると言います。この操作は、基本的に、各ネットの開始と終了がアークで接続される一時的な閉鎖操作の逆です。

一般的に、結合関係の操作に関して、遷移性は満たされない。2つの推移的な関係を組み合わせる

α_{1}

$α_1$ そして

α_{2}

$α_2$ それらの一方が他方に対して推移的である場合にのみ、推移的です。バイナリ関係のペアの場合

α_{1}

$α_1$ そして

α_{2}

$α_2$ それらの一方の推移性を他方と比較して考えることができます。

そう

α_{1}

$α_1$ あるに関して推移

α_{2}

$α_2$ 以下の条件下で：

1）から

(а_{i}, а_{k}) є α_{1} и (а_{k}, а_{j}) є α_{2}

$( _i, _k) є α_1 ( _k, _j) є α_2$ すべき

(а_{i}, а_{j}) є а_{1}

$(_i, _j) є _1$ ;

2）から

(а_{i}, а_{k}) є α_{2} и (а_{k}, а_{j}) є α_{1}

$( _i, _k) є α_2 ( _k, _j) є α_1$ すべき

(а_{i}, а_{j}) є α_{1}

$( _i, _j) є α_1$ ..。

の場合

α_{1} = α_{2} = α

$α_1= α_2=α$ 相対的な遷移性は通常の遷移性です。

次のステートメントは、関係の遷移性、対称性、および非対称性のプロパティについて知られています。バイナリ関係が推移的である場合、その対称部分

α^{(S)}

$α^{(S)}$ そして

α^{(а)}

$α^{()}$ 非対称部分も過渡的です。

逆の場合にのみ当てはまります

α^{(S)}

$α^{(S)}$ 、

α^{(а)}

$α^{()}$ 一時的および

α^{(а)}

$α^{()}$ 一時的に相対的

α^{(S)}

$α^{(S)}$ ..。一般的に、推移性から

α^{(S)}

$α^{(S)}$ そして

α^{(а)}

$α^{()}$ αの遷移性は従いません。

遷移関係αとそれ自体の合成は、関係α・α⊆αを満たします。関係αは、その補数が遷移的である場合、つまり、負に遷移的（非遷移的）です。ᾱ。そのような関係のマトリックスで[

α_{i j}

$α_{ij}$ ]から

α_{i k} = 0

$α_{ik} = 0$ そして

α_{k j} = 0

$α_{kj} = 0$ すべき

α_{i j} = 0

$α_{ij} = 0$ ..。αの負の遷移性は、α自体も遷移性である可能性があるという事実を排除するものではありません。

この場合、αは強い遷移関係であると言われます。マトリックス要素[

α_{i j}

$α_{ij}$ ]そのような態度は、

а_{i k} \cdot а_{k j} = 1

$_{ik}·_{kj} =1$ すべき

а_{i j} = 1

$_{ij} = 1$ 、から

а_{i k} = а_{k j} = 0

$_{ik} = _{kj} =0$ すべき

а_{i j} = 0

$_{ij} = 0$ ..。

強い遷移関係に加えて、弱い遷移（疑似遷移）関係を考慮します。これには、条件が

а_{i} α^{(S)} а_{К}

$_iα^{(S)}_$ そして

а_{К} α а_{j}

$_α_j$ すべき

а_{i} α а_{j}

$_iα_j$ ..。その遷移性は、非対称性と負の遷移性に由来します。

関係αは、からのδの場合、一時的に完全です。

а_{K 1} α а_{K 2}, а_{K 2} α а_{K 3}, \dots, а_{K (δ - 1)} α а_{K δ}

$_{K1}α_{K2}, _{K2}α_{K3},…, _{K(δ-1)}α_{Kδ}$ 、

比較可能性は次のとおりです

а_{K 1}

$_{K1}$ そして

а_{K δ}

$_{Kδ}$ 、つまりどちらかが実行されます

а_{K 1} α а_{K δ}

$_{K1}α_{Kδ}$ または

а_{K δ} α а_{K 1}

$_{Kδ}α_{K1}$ ..。

周期性

セットAで定義された関係は、それらの中にサイクルが存在するという観点から見ることができます。関係のグラフでこのような考察を行うと便利です。循環関係グラフには、常に少なくとも1つの閉じた輪郭（ルート）が含まれます。矢印を無視すると、パスがループに変わります。非周期的関係のグラフには周期が含まれておらず、非周期的または非制御と呼ばれます。セットAの要素からフォームの少なくとも1つのチェーンを形成できる場合

、関係= <Å、A>は循環的です。

а_{i} α а_{K 1}, а_{K 1} α а_{K 2}, \dots, а_{K (δ - 1)} α а_{K δ}, а_{K δ} α а_{K i}

$_iα_{K1}, _{K1}α_{K2},…, _{K(δ-1)}α_{Kδ},_{Kδ}α_{Ki}$ 任意の長さδ。循環関係の遷移クロージャのグラフMには、少なくとも1つのペアが含まれています（

а_{i}, а_{i}

$_i, _i$ ）、および非周期的関係の場合、αにはそのようなペアは含まれません。

関連= <Å、A>は、非環式、任意δ≥1ため、場合から条件

а_{i} α а_{K 1}, а_{K 1} α а_{K 2}, \dots, а_{K (δ - 1)} α а_{j}

$_iα_{K1}, _{K1}α_{K2},…, _{K(δ-1)}α_j$ すべき

а_{i} \neq а_{j}

$_i ≠ _j$ ..。マトリックス内[

α_{i j}

$α_{ij}$ ]からの非周期的関係

а_{i K 1} а_{K 1 K 2} . . . а_{K (δ - 1) j} = 1

$_{iK1}_{K1K2}..._{K(δ-1)j}=1$ i≠jが続きます。非周期的な関係は常に非対称ですが、その逆は当てはまりません。言い換えれば、いくつかのピークがある場合

а_{i}

$_i$ そして

а_{j}

$_j$ グラフα非周期的関係は方法で接続されています。その場合、グラフに円弧はありません（

а_{j}, а_{i}

$_j, _i$ ）。トランジティブトーナメント

は、このプロパティを持つグラフの典型的な例です。このようなグラフの頂点には番号を付け直すことができます。

а_{i}, а_{j}

$_i, _j$ ）頂点jの数が頂点iよりも大きい。

αが反反射的遷移バイナリ関係である場合、それは非周期的です。関係の非周期性と一時的な完全性は、その一時性を意味します。

完全

完全性プロパティ（完全性、線形性）。関係のセット全体が不完全と完全に分けられ、その中で、非常に完全な関係が際立っています。関係のグラフを考慮して、関係の完全性の特性を説明します。

完全な関係のグラフは完全です。その頂点の任意の2つは、少なくとも1つのアークによって直接接続されています。隣接しています。グラフ内の各アークは、関係のグラフのポイント（要素、ペア）に対応しているため、上記に基づいて定義を作成できます。セットAのすべての要素が互いに同等または等しい場合に限り

、関係= <Å、A>は完全（完全、線形）です。したがって、全体的な態度は反射的です。言い換えれば、任意の2つの要素に対して

а_{i}

$_i$ そして

а_{j}

$_j$ フェア

(а_{i} α а_{j} V а_{j} α а_{i} V а_{i} = а_{j})

$(_i α _j V _j α _i V _i = _j)$ ..。

関係αに少なくとも1つのペアがある場合

а_{i}

$_i$ 、

а_{j}

$_j$ 比類のない不平等な要素の場合、そのような関係は不完全です。任意の合計比率αについて、

∆ U α U α^{- 1} = A \times A

$∆UαUα^{-1}=A×A$ またはから

а_{i} ᾱ а_{j}

$_i ᾱ _j$ すべき

а_{j} α а_{i}

$_j α _i$ ..。バイナリ関係αは、次の場合にのみ完全です。

а^{(a)} = а^{(d)}

$^{(a)} =^{(d)}$ 、つまりその非対称部分が二重（項目9）関係と一致する場合。グラフがA×Aと一致すると、

バイナリ関係αは完全に完成します。この関係のグラフは、頂点の各ペアがエッジで接続され、各頂点にループがある完全なグラフです。このようなグラフは、完全完全グラフと呼ばれます。総比率αは常に関係を満たします

ᾱ \subset α^{- 1}

$ᾱ ⊂ α^{-1}$ そして

α^{- 1} \subset ᾱ \cup (α \cap α^{- 1})

$α^{-1}⊂ᾱ ∪(α∩α^{-1})$ ..。姿勢

α \cup (ᾱ \cap α^{d}) = α \cup (ᾱ)^{(S)}

$α∪(ᾱ∩α^{d}) = α∪(ᾱ)^{(S)}$ 常にいっぱいです。

場合

α_{1}

$α_1$ そして

α_{2}

$α_2$ 完全な関係、そして

α_{1} \cdot α_{2}

$α_1·α_2$ いっぱいです。マトリックス内[

α_{i j}

$α_{ij}$ ]完全な関係

α_{i j} = 1

$α_{ij} = 1$ または

α_{j i} = 1

$α_{ji} = 1$ 任意のi、j、または両方の等式が真です。関係αは、もしあれば、弱く完全です（弱く接続されています）

а_{i}, а_{j} є A

$_i,_j є A$ そのような

а_{i} \neq а_{j}

$_i ≠ _j$ または

а_{i} α а_{j}

$_i α _j$ または

а_{j} α а_{i}

$_j α _i$ ..。

マトリックス内[

α_{i j}

$α_{ij}$ ]任意のi≠jの弱く完全な関係、または

α_{i j} = 1

$α_{ij} = 1$ または

α_{j i} = 1

$α_{ji} = 1$ 、または両方の等式が真です。関係αは、からの任意のnに対して、一時的に完全です。

а_{i} α а_{K 1}, а_{K 1} α а_{K 2}, \dots, а_{K (n - 1)} α а_{i n}

$_iα_{K1}, _{K1}α_{K2},…, _{K(n-1)}α_{in}$ 比較可能性は次のとおりです

а_{i 1} \equiv а_{i n}

$_{i1}≡ _{in}$ それら。

а_{i 1} α а_{i n}

$_{i1}α _{in}$ または

а_{i n} α а_{i 1}

$_{in}α _{i1}$ ..。

完全な関係の数を数えましょう。まず、回線の問題について考えます。比率マトリックスの線は、比率マトリックスの主対角線に垂直な直線セグメントであり、この対角線に対して対称に配置されたマトリックスの2つのセル（セル）の中心を接続します。

対称位置の2つ以上のペアが比率マトリックスの1つの線（直線）にある場合でも、線の数はそのような位置のペアの数と同じままです。任意のnの位置のペアの総数は、次のように定義されます。

C_{n}^{2} = L

$C_n^2 = L$ ..。

したがって、セットA上の任意の関係のマトリックスには、並列セグメント（線）のセットLがあります。セグメント（線）の終了位置をL-左とP-右の記号で指定しましょう。また利用できる| L |ラインの端の位置に配置できるチップ。課題は、アレンジが可能な方法の数を決定することです| L |各ラインに少なくとも1つのチップがあるようにチップ。

問題は、π位置のセット（n = {A、P}）へのラインのセットLのマッピングf：L→πの数Fを決定することに還元できることは明らかです。このようなマッピングの数は、次の式によって決定されることが知られています。

F = | п |^{| L |}

$F = ||^{|L|}$ ..。特定のマッピング（画像）は、|のインデックスのシーケンスの<P、P、L、L、L、…、L、P>の形式を持つことができます。L | 位置。L記号は主対角線の下の位置に対応し、P記号は対角線の上でそれに対称です。

合計比率の定義から、そのグラフには少なくともKポイントが含まれていることがわかります。K=

C_{n}^{2}

$C_n^2$ 配置：すべての回線が少なくとも1つのチップによって占有されるようにします。グラフ上のポイントの数kは、必要な最小数に加えて、値k = 0（1）K =

C_{n}^{2}

$C_n^2$ ..。

固定数kポイントごとに、それらを配置できる位置の選択肢のセットは、値によって決定されます。

C_{К}^{k}

$C_^k$ 、ここで、Kは空いている位置のセットです。k個の追加ポイントがk個の線を完全に埋めるので、比率の完全性を確保するために、K-k個の位置をチップ（必要な最小値のセットからのポイント）で埋める必要があり、そのような塗りつぶしの数は次のようになります。

2^{К - k}

$2^{-k}$ ..。

k個の追加ポイントの位置の選択とK-kラインをチップで埋める方法は独立しています。したがって、すべての線が少なくとも1つの点で占められるように、K + k点を2∙Kの位置に配置する可能性の総数は、次の式によって決定されます。

C_{К}^{k} \cdot 2^{К - k}, k = 0 (1) К .

$C_^k ·2^{-k}, k = 0(1).$

この式を合計すると、完全な関係の数が得られます。これは、対角点の配置の状況に依存しません。言い換えれば、それは部分的に反射的な完全な関係の数です。たとえば、反反射的で完全な反射的で完全な関係などです。

例5。対角点を配置するためのさまざまな状況は、数によって決定されます

2^{n}

$2^n$ ..。次に、固定nのすべての完全な関係のセットのカーディナリティは、次の式によって決定されます。

П = 2^{n} \cdot \sum_{k = 0}^{К} C_{К}^{k} 2^{К - k} = \sum_{k = 0}^{К} C_{К}^{k} 2^{К + n - k}

$= 2^n·∑_{k=0}^C_^k2^{-k} = ∑_{k=0}^C_^k2^{ + n - k}$ ..。

関係については3つので必要とされる特性

に必要な3つのプロパティを持つ同値関係については。注目すべき結果があります。n個の要素のセットに対する各等価関係は、このセットのパーティションと1対1で対応しています。そのような関係の数は、次の式によって決定されます。

B_{n} = \sum_{m = 0}^{n} S (n, m)

$B_n = ∑_{m=0}^nS(n, m)$ 、ここで、S（n、m）は第2種のスターリング番号、Bnは

ベル番号、または繰り返し形式です。

B_{n + 1} = \sum_{k = 0}^{n} C_{n}^{k} B_{k} .

$B_{n+1} = ∑_{k=0}^nC_n^kB_k.$

注文セット（部分注文）の場合、そのような式はオープンではなく、その数は直接計算によって決定されます。モデリング。nの値が小さい場合、データを

表6に示します。二元関係の定量的特性

表6は次のことを示しています。n= | A | -セットキャリアのカーディナリティ。

2^{n^{2}}

$2^{n^2}$ -セットAのすべてのバイナリ関係の数。

|（n）で| -非同形関係のクラスの数。

|（n）| -部分的な順序の関係の数。

| Gn（n）| -クラスの数は、部分的な順序の非同形関係です。

| Gl（n）| = n！-線形順序関係の数。

結論

この作業では、バイナリ比の基本的な特性と構造の詳細な分析が実行され、それに基づいて、1つ以上の特性を持つBOの定量的特性を取得することができました。2つおよび3つの必要なプロパティを持ついくつかのタイプの関係の数の元の比率を見つけて提示しました。これらの結果は、BOとより高いarityの関係をモデル化して研究する可能性を開きます。

中古文献一覧

Aigner M. CombinatorialTheory。-M。：Mir、1982。
BirkhoffG。構造の理論。-M。：IL、1952.-408p。
Noden P.、KitteK。代数的アルゴリズム。--M。：Mir、1999。-720ページ
リブニコフK.A. 組み合わせ分析の概要。-M。：Ed。モスクワ州立大学、1972年。-256秒。
スタンレーR.列挙型コンビナトリクス。Vol。1.-M。：Mir、1990 .-- 440p。
スタンレーR.列挙型コンビナトリクス。T.2.- M。：Mir、2005.-767s。
シハノビッチYu.A. 現代数学入門。初期の概念-M。：Nauka、1965.-376p。

関係の定量的特性

バイナリ関係のタイプの定量的特性

反射性

対称

トランジティビティ（ラテントランジティバス-トランジショナル、トランジットから-トランジション）

周期性

完全

結論

中古文献一覧

More articles: