同値関係

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
として描かれている5要素セット52の同値関係 論理行列(薄い灰色のフィールドを含む色付きのフィールドは1を表し、白いフィールドは0を表します。)非白色セルの行と列のインデックスは関連する要素ですが、薄い灰色以外のさまざまな色は同等のクラスを示します(各ライトグレーセルは、独自の同等クラスです)。

数学は、同値関係は、反射的対称的推移的な二項関係ですに等しい関係は、同値関係の標準的な例です。

各同値関係は、基礎となるセットを互いに素な同値類に分割します。与えられたセットの2つの要素は、それらが同じ同値類に属している 場合に限り、互いに同等です。

表記

文献では、2つの要素を示すためにさまざまな表記法が使用されていますセットのは同値関係に関して同等です最も一般的なのは「"および" a≡b " これらは次の場合に使用されます暗黙的であり、 "のバリエーション"、" a≡Rb " または"" 指定します明示的に。非等価性は「a≁bまたは「"。

定義

バイナリ関係 セットでそれが反射的、対称的、推移的である場合に限り、同値関係であると言われます。つまり、すべての人にとって

  • 再帰性
  • 場合に限り対称性
  • もしもそれから推移性

関係と一緒にsetoidと呼ばれます。同値表示と定義されている[1] [2]

簡単な例

セットで、関係同値関係です。次のセットは、この関係の同値類です。

のすべての同値類のセットこのセットはセットのパーティションですに関して

同値関係

次の関係はすべて同値関係です。

  • 数字のセットで「等しい」。例えば、に等しい[2]
  • すべての人のセットで「と同じ誕生日を持っています」。
  • すべての三角形のセットで「にています」
  • すべての三角形のセットで「合同」です
  • 自然数が与えられた、 "は、モジュロに合同です "整数について[2]
  • 与えられた関数 、 "の下に同じ画像がありますの要素の「として」ドメイン 例えば、下に同じ画像があります、つまり。
  • 実数のセットの「と同じ絶対値を持っている」
  • すべての角度のセットで「と同じ正弦を持っています」。

同値ではない関係

  • 実数間の「≥」の関係は、反射的かつ推移的ですが、対称的ではありません。たとえば、7≥5ですが、5≥7ではありません。
  • 1より大きい自然数の間の「1より大きい共通因子を持つ」関係は、反射的で対称的ですが、推移的ではありません。たとえば、自然数2と6は1より大きい公約数を持ち、6と3は1より大きい公約数を持ちますが、2と3は1より大きい公約数を持ちません。
  • セットX空の関係 R ( aRbが真にならないように定義されている)は、空虚な対称で推移的です。ただし、それは反射的ではありません(X自体が空でない限り)。
  • 実数間の関係は、より正確に定義されていても、等価関係ではありません。これは、反射的で対称的ですが、複数の小さな変化が蓄積されて大きな変化になる可能性があるため、推移的ではないためです。ただし、近似が漸近的に定義されている場合、たとえば、ある点でf − gの極限が0の場合、その点の近くで2つの関数fgがほぼ等しいと言うと、これは同値関係を定義します。

他の関係への接続

  • 半順序は、反射的、反対称、推移的な関係です。
  • 等式は、同値関係と半順序の両方です。等式はまた、反射的、対称的、反対称的である集合上の唯一の関係です。代数式では、等式変数を相互に置き換えることができます。これは、等式関連の変数には使用できない機能です。同値関係の同値類は互いに置き換えることができますが、クラス内の個人を置き換えることはできません。
  • 厳密な半順序は、非反射的、推移的、および非対称です。
  • 半同値関係は推移的で対称的です。このような関係は、それがシリアルである場合、つまりすべての場合にのみ反射的です。いくつか存在します[証明1]したがって、同値関係は、対称、推移、および連続関係として代替的に定義される場合があります。
  • 三元同値関係は、通常の(二元)同値関係の三元類似物です
  • 反射的で対称的な関係は、依存関係(有限の場合)であり、許容関係は無限の場合です。
  • 事前注文は反射的で推移的です
  • 合同関係は、その定義域を持つ同値関係です。代数的構造の台集合でもあり、追加の構造を尊重します。一般に、合同関係は準同型の核の役割を果たし、合同関係による構造の商を形成することができます。多くの重要なケースでは、合同関係は、それらが定義されている構造の下位構造として代替表現を持っています(たとえば、グループの合同関係は通常のサブグループに対応します)。
  • 排中律と同等であるため、逆のステートメントは(構成主義の数学とは対照的に古典的な数学でのみ成り立ちますが、任意の同値関係は分離関係の否定です
  • 反射的で左(または右)のユークリッド関係である各関係も同値関係です。

同値関係の下での明確性

もしもの同値関係ですの要素のプロパティですいつでも の場合はtruetrueの場合、プロパティ関係の下で明確に定義されているか、クラス不変であると言われています

頻繁に発生する特定のケースは、からの関数です別のセットにもしも示すそれからの射言われています下のクラス不変 または単に下で不変 これは、たとえば有限群の指標理論で発生します。関数を持つ後者の場合可換三角形で表すことができます。invariantも参照してください一部の作者は「「または単に」「不変」の代わりに「"。

より一般的には、関数は同等の引数をマップする場合があります(同等の関係の下で)同等の値に(同等の関係の下で)。そのような関数はからの射として知られています

同値類、商集合、集合

させていくつかの定義:

同値類

XサブセットY _Yのすべてのab当てはまり、 YのaYの外側bには当てはまらないので、 〜によってX同値類と呼ばれます。させてaが属する同値類を示します。互いに同等 のXのすべての要素も、同じ同値類の要素です。

商集合

Xのすべての同値類の集合〜によるX商集合です。X位相空間である場合、変換の自然な方法があります位相空間に; 詳細については、商空間を参照してください。

投影

投影_関数ですによって定義されますの要素をマップしますそれぞれの同値類に

射影に関する定理[3] 関数をそのようなものであるそれからそれからユニークな機能がありますそのようなもしも全射でありそれから全単射です

等価カーネル

関数等価核は同値関係です〜によって定義されますインジェクションの等価カーネルは恒等関係です。

パーティション

X分割は、Xの空でないサブセットの集合Pであり、 Xのすべての要素がPの単一要素の要素であるようになります。Pの各要素は、パーティションセルです。さらに、Pの要素はペアごとに素であり、それらの和集合Xです。

パーティションのカウント

Xをn個の要素を持つ有限集合としますX上のすべての同値関係はXの分割に対応し、その逆も同様であるため、X上の同値関係の数は、 Xの個別の分割の数に等しくなります。これはn番目のベル数B n:です。

ドビンスキーの公式)。

同値関係の基本定理

重要な結果は、同値関係とパーティションをリンクします:[4] [5] [6]

  • 集合XパーティションX上の同値関係〜
  • 逆に、 Xの任意のパーティションに対応して、Xには同値関係〜が存在します。

どちらの場合も、 Xのパーティションのセルは、 〜によるXの同値類ですXの各要素はXの任意のパーティションの一意のセルに属し、パーティションの各セルはXの〜による同値類と同一であるため、Xの各要素はXの〜による一意の同値類に属します。したがって、 X上のすべての同値関係のセットとXのすべてのパーティションのセットの間には自然な全単射があります。

同値関係の比較

もしも同じセットの2つの同値関係です、 と示すすべてのためにそれからより粗い関係と言われています、 とよりも細かい関係です同等に、

  • よりも細かいですすべての同値類の場合の同値類のサブセットです、したがって、のすべての同値類の同値類の和集合です
  • よりも細かいですによって作成されたパーティションの場合によって作成されたパーティションの改良版です

等式同値関係は、任意のセットで最も細かい同値関係ですが、要素のすべてのペアを関連付ける普遍的な関係は、最も粗いです。

関係 "よりも細かいです「固定集合上のすべての同値関係のコレクションは、それ自体が半順序関係であり、コレクションを幾何束にします。[7]

同値関係の生成

  • 任意のセットが与えられたセット全体の同値関係すべての機能の次のように取得できます。2つの関数は、それぞれのフィックスポイントのセットが同じカーディナリティを持ち、順列の長さ1のサイクルに対応する場合に同等見なさます
  • 同値関係オン全射射影等価カーネルです [8]逆に、セット間の全射は、そのドメイン上のパーティション、つまり域内のシングルトンのプレイメージのセットを決定しますしたがって、上の同値関係のパーティションおよびドメインが同じものを指定する3つの同等の方法です。
  • X上の同値関係のコレクションの共通部分(のサブセットとして表示されるバイナリ関係)も同値関係です。これにより、同値関係を生成する便利な方法が得られます。X上の任意の2値関係Rが与えられると、Rによって生成される同値関係は、 Rを含むすべての同値関係( Rを含む最小の同値関係とも呼ばれます)の共通部分になります。具体的には、Rは同値関係を生成します
自然数が存在する場合 と要素そのような、 とまた、 ために
この方法で生成された同値関係は、取るに足らないものになる可能性があります。たとえば、Xの全順序によって生成される同値関係にはX自体という1つの同値類があります。
  • 同値関係は、「物事をつなぎ合わせる」ことによって新しい空間を構築することができます。Xをデカルト二乗単位とします そして〜をで定義されるX上の同値関係とするすべてのためにすべてのために次に商空間 トーラスで自然に識別できます(同相写像:正方形の紙を取り、上下の端を曲げて接着して円柱を形成し、次に結果の円柱を曲げて2つの開いた端を接着します。トーラス。

代数的構造

数学の多くは、同値関係と秩序関係の研究に基づいています。格子理論は、秩序関係の数学的構造を捉えています。同値関係は数学では秩序関係と同じくらい遍在していますが、同値の代数的構造は秩序の代数的構造ほどよく知られていません。前者の構造は、主に群論に基づいており、程度は低いものの、格子、カテゴリ、および亜群の理論に基づいています。

群論

順序関係順序集合に基づいているのと同じように同値関係は分割された集合に基づいています。これは、分割構造を保持する命令の下で閉じられている集合です。そのような全単射はすべて同値類をそれ自体にマッピングするので、そのような全単射は順列としても知られています。したがって、順列群(変換群としても知られています)と関連する軌道の概念は、同値関係の数学的構造に光を当てます。

'〜'は、宇宙または台集合と呼ばれる空でない集合Aの同値関係を示します。Gが、 Aのパーティション構造を保持する、A上の全単射関数のセットを表すとします。これは、すべての次に、次の3つの接続された定理が成り立ちます。[9]

  • 〜Aを同値類に分割します。(これは、前述の同値関係の基本定理です);
  • Aのパーティションが与えられた場合Gは合成中の変換グループであり、その軌道はパーティションのセルです。[13]
  • A上の変換群Gが与えられると、A上同値関係〜が存在し、その同値類はGの軌道です。[14] [15]

要約すると、A上の同値関係が与えられると軌道が〜の下 のAの同値類であるA上の変換群 Gが存在します。

同値関係のこの変換群の特徴付けは、格子が次数関係を特徴付ける方法とは根本的に異なります。格子理論の操作の引数が出会っ結合するのは、いくつかの宇宙Aの要素です一方、変換グループ演算の合成逆の引数は、全単射のセットAAの要素です

一般にグループに移動して、HをいくつかのグループGサブグループとします。〜をGの同値関係とし、次のようにします。 〜の同値類(Gに対するHの作用の軌道とも呼ばれるGにおけるH正しい剰余ですabを交換すると、左の剰余類が生成されます。

関連する考え方はRosen(2008:chpt。10)にあります。

カテゴリと亜群

Gを集合とし、「〜」がG上の同値関係を表すとします。次に、この同値関係を表す亜群を次のように形成できます。オブジェクトはGの要素であり、G任意の2つの要素xyに対して、次の場合に限り、xからyへの一意の射が存在します。

同値関係を亜群の特殊なケースと見なす利点は次のとおりです。

  • 「自由同値関係」の概念は存在しませんが、有向グラフ上の自由亜群の概念は存在します。したがって、「同値関係の表現」、つまり対応する亜群の表現について話すことは意味があります。
  • 群、群作用、集合、および同値関係の束は、亜群の概念の特殊なケースと見なすことができます。これは、多くの類似点を示唆する観点です。
  • 多くの文脈では、「指数化」、したがってしばしば合同と呼ばれる適切な同値関係が重要です。これは、カテゴリ内の内部亜群の概念につながります[16]

格子

任意の集合Xの同値関係は、集合の包含によって順序付けられると、慣例によりConXと呼ばれる完全な格子を形成します。標準写像カーX ^ XConXは、 XConXのすべての関数のモノイドX ^ Xを関連付けますker全射ですが、単射ではありません。あまり正式ではありませんが、Xの同値関係カー 、各関数fXXをそのカーネル カー fに取ります。同様に、ker(ker)X ^ Xの同値関係です。

同値関係と数理論理学

同値関係は、例または反例の準備ができている情報源です。たとえば、正確に2つの無限の同値類との同値関係は、ω-カテゴリであるが、より大きな基数ではカテゴリではない理論の簡単な例です。

モデル理論の意味するところは、関係を定義するプロパティは、各プロパティについて、与えられたプロパティを満たさないが満たす関係の例を見つけることができる場合にのみ、互いに独立していることを証明できることです(したがって、定義の必要な部分)。他のすべてのプロパティ。したがって、同値関係の3つの定義プロパティは、次の3つの例によって相互に独立していることを証明できます。

  • 反射的および推移的: Nの関係≤ または任意の事前注文;
  • 対称で推移的: aRb↔ab ≠ 0として定義されるNの関係R。または任意の半同値関係;
  • 反射的で対称的: aRb↔a −bは2または3の少なくとも1つで割り切れる」として定義されるZの関係R。または任意の依存関係

同値関係が持つ場合と持たない場合がある 一階述語論理で定義可能なプロパティには、次のものがあります。

  • 同値類の数は有限または無限です。
  • 同値類の数は(有限の)自然数nに等しい。
  • すべての同値類は無限のカーディナリティを持っています;
  • 各同値類の要素数は自然数nです。

も参照してください

メモ

  1. ^ 場合:与えられたさせてシリアル性を使用して保持し、次に対称性によって、したがって推移性によって。次の場合のみ:与えられた選ぶそれから再帰性によって。
  1. ^ ワイスタイン、エリックW. 「同値類」mathworld.wolfram.com 2020年8月30日取得
  2. ^ a b c "7.3:同値類"数学LibreTexts2017-09-20 2020年8月30日取得
  3. ^ Garrett Birkhoff and Saunders Mac Lane、1999(1967)。代数、第3版。p。35、Th。19.チェルシー。
  4. ^ ウォレス、DAR、1998年。グループ、リングおよびフィールドp。31、Th。8.Springer-Verlag。
  5. ^ Dummit、DS、およびFoote、RM、2004年。AbstractAlgebra、3版。p。3、提案2。ジョンワイリー&サンズ。
  6. ^ Karel Hrbacek Thomas Jech(1999)セット理論入門、第3版、29〜32ページ、 Marcel Dekker
  7. ^ Birkhoff、Garrett(1995)、Lattice Theory、Colloquium Publications、vol。25(第3版)、American Mathematical Society、ISBN 9780821810255宗派。IV.9、定理12、95ページ
  8. ^ Garrett Birkhoff and Saunders Mac Lane、1999(1967)。代数、第3版。p。33、Th。18.チェルシー。
  9. ^ ローゼン(2008)、pp。243–45。1989年のバスファンフラーセンの§10.3はあまり明確ではありません。法と対称性オックスフォード大学 押す。
  10. ^ バス・ファン・フラーセン、1989年。法則と対称性オックスフォード大学 プレス:246。
  11. ^ ウォレス、DAR、1998年。グループ、リングおよびフィールドSpringer-Verlag:22、Th。6.6。
  12. ^ ウォレス、DAR、1998年。グループ、リングおよびフィールドSpringer-Verlag:24、Th。7。
  13. ^ 証明[10]関数の合成で群の乗算を解釈し、関数の逆で群の逆数を解釈します。その場合、 Gは構成中の群であり、これは次のことを意味します。 Gは次の4つの条件を満たすためです
    • Gは構成の下で閉じられます。Gの任意の要素の定義域終域Aであるため、Gの任意の2つの要素の構成が存在しますさらに、全単射の構成は全単射です。[11]
    • 恒等関数の存在恒等関数Ix)= xは、G明らかな要素です
    • 逆関数の存在すべての全単射関数 gには、 gg −1 = Iのようなg − 1があります。
    • 作曲アソシエイツfgh)=(fghこれは、すべてのドメインのすべての機能に当てはまります。[12]
    fgをGの任意の2つの要素としますGの定義により、[ gfx))] = [ fx)]および[ fx)] = [ x ]となり、[ gfx))] = [ x ]。したがって、 Gは変換グループ(および自己同形群)でもあります。これは、関数の合成が
  14. ^ ウォレス、DAR、1998年。グループ、リングおよびフィールドSpringer-Verlag:202、Th。6.6。
  15. ^ Dummit、DS、およびFoote、RM、2004年。AbstractAlgebra、3版。John Wiley&Sons:114、提案2。
  16. ^ Borceux、F。and Janelidze、G.、2001。Galois theories、Cambridge University Press、 ISBN 0-521-80309-8 

参考文献

  • ブラウン、ロナルド、2006年。トポロジーとGroupoids。BooksurgeLLC。ISBN1-4196-2722-8_ 
  • Castellani、E.、2003、 "Symmetry and equivalent" in Brading、Katherine、and E. Castellani、eds。、Symmetries in Physics:PhilosophicalReflectionsケンブリッジ大学 プレス:422–433。
  • ロバート・ディルワースとクロウリー、ピーター、1973年。格子の代数理論プレンティスホール。Chpt。12では、格子理論で同値関係がどのように発生するかについて説明します。
  • ヒギンズ、PJ、1971年。カテゴリーと亜群。ヴァンノストランド。2005年からTACの再版としてダウンロード可能。
  • ジョン・ランドルフ・ルーカス、1973年。時間と空間に関する扱いロンドン:メシュエン。セクション31。
  • ローゼン、ジョセフ(2008)対称性のルール:科学と自然が対称性に基づいている方法Springer-Verlag。主に章。9,10。
  • Raymond Wilder(1965)数学の基礎の紹介第2版、第2-8章:同等性を定義する公理、pp 48–50、John Wiley&Sons

外部リンク