Relation d'équivalence

En mathématiques , une relation d'équivalence est une relation binaire entre deux éléments d'un définir les groupes ensemble comme étant «équivalent» en quelque sorte. Soit a, b et c des éléments arbitraires de certains ensemble X. Ensuite, "a ~ b" ou "a ≡ b" indique qu'un équivaut à b.

Une relation d'équivalence "~" est réflexive, symétrique , et transitive. En d'autres termes, les éléments suivants doivent tenir pour "~" être une relation d'équivalence sur X:

Une relation d'équivalence partitionne un ensemble en plusieurs sous-ensembles disjoints, appelés classes d'équivalence. Tous les éléments d'une classe d'équivalence donnée sont équivalents entre eux, et aucun élément est équivalent à ne importe quel élément d'une classe différente.

• Réflexivité: une ~ a
• Symétrie: si un b ~ b ~ puis une
• Transitivité: si un b ~ b ~ c et puis un ~ c.

Le une classe d'équivalence de la rubrique "~", notée [A], est la partie de X dont les éléments b sont tels que X a ~ b. avec "~" est appelé un setoid.

Des exemples de relations d'équivalence

Une relation d'équivalence est l'omniprésente l'égalité ("=") relation entre les éléments de ne importe quel ensemble. D'autres exemples comprennent:

• »A le même anniversaire que" sur l'ensemble de toutes les personnes, étant donné la théorie des ensembles naïve.
• "Est similaire à" ou "congru à" sur l'ensemble des triangles .
• "Est congru à modulo n "sur les entiers .
• "A la même une image en fonction "sur les éléments de la domaine de la fonction.
• Équivalence logique de phrases logiques.
• "Est- isomorphe à "sur modèles d'un ensemble de phrases.
• Dans certains set théories axiomatiques autres que canonique ZFC (par exemple, Nouvelles fondations et des théories connexes):
  • Similarité sur le univers de bien-ordres donne lieu à classes d'équivalence qui sont les nombres ordinaux .
  • Équipotence sur le univers de:
    • Ensembles finis donne lieu à classes d'équivalence qui sont les nombres naturels .
    • Ensembles infinis donne lieu à des classes d'équivalence qui sont la transfinies nombres cardinaux .
• Soit a, b, c, d être des nombres naturels , et laisser (a, b) et (c, d) être paires ordonnées de ces numéros. Puis le classes d'équivalence en vertu de la relation (a, b) ~ (c, d) sont les:
  • Entiers si un + d = b + c;
  • Positifs nombres rationnels Si AD = BC.
• Soit (r _n) et _(n s) soient tout deux Suites de Cauchy de nombres rationnels. Les nombres réels sont les classes d'équivalence de la relation (r _n) ~ (s _n), si la séquence (r _n - s _n) a la limite 0.
• Relations de Green sont cinq relations d'équivalence sur les éléments d'une semi-groupe.
• "Est- parallèlement à "sur l'ensemble des un sous-espaces de espace affine.

Des exemples de relations qui ne sont pas équivalences

• La relation "≥" entre les chiffres réels est réflexive et transitive, mais pas symétrique. Par exemple, sept ≥ 5 ne implique pas que ≥ 5 7. Il est, cependant, un ordre partiel.
• Le rapport "a un facteur commun avec plus de 1" entre des nombres naturels supérieurs à 1, est réflexive et symétrique, mais pas transitive. (Les deux nombres naturels et 6 ont un facteur commun supérieur à 1, et 6 et 3 ont un facteur commun supérieur à 1, 2 et 3 mais ne ont pas de facteur commun supérieur à 1).
• La relation R sur un vide non vide X (ce est à dire aRb ne est jamais vrai) est vacuously symétrique et transitive, mais pas réflexive. (Si X est également vide alors R est réflexive.)
• La relation «est approximativement égal à» entre les nombres réels ou d'autres choses, même si plus précisément définis, ne est pas une relation d'équivalence, parce que même si réflexive et symétrique, il ne est pas transitive, depuis plusieurs petits changements peuvent se accumuler pour devenir un grand changement.
• La relation «est un frère du" sur l'ensemble de tous les êtres humains ne est pas une relation d'équivalence. Bien siblinghood est symétrique (si A est un frère de B, alors B est un frère de A) il ne est ni réflexive (personne ne est un frère de lui-même), ni transitive (car si A est un frère de B, alors B est un frère de A, mais A ne est pas un frère de A). Au lieu d'être transitive, siblinghood est «presque transitive», ce qui signifie que si A ~ B, et B ~ C, et A ≠ C, alors A ~ C.
• La notion de parallélisme géométrie commandé ne est pas symétrique et est, par conséquent, pas une relation d'équivalence.
• Une relation d'équivalence sur un ensemble ne est jamais une relation d'équivalence sur un sur-ensemble approprié de cet ensemble. Par exemple R = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3, 2), (3,3)} est une relation d'équivalence sur {1,2,3} mais pas sur {1,2,3,4} ou sur le nombre naturel. Le problème est que la réflexivité échoue parce que (4,4) ne est pas membre.

Connexion à d'autres relations

Un relation de congruence est une relation d'équivalence dont le domaine X est aussi l'ensemble sous-jacent pour une structure algébrique , et qui respecte la structure supplémentaire. En général, les relations de congruence jouent le rôle de grains de homomorphismes, et le quotient d'une structure par une relation de congruence peuvent être formés. Dans de nombreux cas importants relations de congruence ont une représentation alternatif en tant que sous-structures de la structure sur laquelle ils sont définis. Par exemple, les relations de la congruence sur les groupes correspondent à la sous-groupes normaux.

Ordre et d'équivalence relations sont à la fois transitive, mais seulement équivalence relations sont symétriques ainsi. Si symétrie est affaiblie à antisymétrie, le résultat est un ordre partiel.

Un relation d'équivalence partielle est transitive et symétrique, mais pas réflexive.

• Transitive et symétrique impliquent réflexive ssi pour tout a, b ∈ X, a ~ b est toujours défini.
  

Un relation de dépendance est réflexive et symétrique, mais pas transitive.
Un précommande est réflexive et transitive, mais ni symétrique ni antisymétrique.
Un ordre partiel strict est transitive seul.

relations d'équivalence peuvent donc être considérés comme le point culminant d'une hiérarchie des relations d'ordre.

classe d'équivalence, ensemble quotient, la partition

Soit X un ensemble non vide avec des éléments typiques a et b. Quelques définitions:

• L'ensemble de tous a et b pour laquelle une ~ b détient composer une classe d'équivalence de X par ~. Laissez [a] =: {x ∈ X: x ~ a} désigner la classe d'équivalence à laquelle appartient un. Puis tous les éléments de X équivalent à l'autre sont également des éléments de la même classe d'équivalence: ∀ a, b ∈ X (a ~ b ↔ [a] = [b]).
• L'ensemble des classes d'équivalence possibles de X par ~, notée X / ~ =: {[x]: x ∈ X}, est le quotient ensemble de X par ~. Si X est un espace topologique, il est un moyen naturel de transformer X / ~ dans un espace topologique; voir espace quotient pour les détails.
• Le projection de ~ est la fonction π: X → X / ~, définie par π (x) = [x], éléments de cartographie de X dans leurs classes d'équivalence respectifs par ~.
  

Théorème sur projections (Birkhoff et Mac Lane 1999: 35, 19 Th.): Soit la fonction f: X → B tels qu'un ~ b → f (a) = f (b). Ensuite, il ya une fonction unique g: X / ~ → B, tel que f = g π. Si f est une surjection et un b ↔ ~ f (a) = f (b), alors g est un bijection.

• Le noyau de l'équivalence d'une fonction f est la relation d'équivalence, notée Ef, de telle sorte que xEfy de f (x) = f (y). Le noyau de l'équivalence d'une injection est le relation d'identité.
• Un partition de X est un ensemble P de sous-ensembles de X, de telle sorte que chaque élément de X est un élément d'un seul élément de P. Chaque élément de P est une cellule de la partition. En outre, les éléments de P sont deux à deux disjoints et leur union est X.

Théorème ("théorème fondamental des relations d'équivalence": Wallace 1998:. 31, Th 8; Dummit et Foote 2004:. 3, Prop 2):

• Une relation d'équivalence ~ cloisons X.
• A l'inverse, correspondant à une partition de X, il existe une relation d'équivalence ~ sur X.

Dans les deux cas, les cellules de la partition de X sont les classes d'équivalence de X par ~. Etant donné que chaque élément de X appartient à une cellule unique d'une partition de X, et étant donné que chaque cellule de la partition est identique à une classe d'équivalence de X par ~, chaque élément de X appartient à une classe d'équivalence unique de X par ~. Ainsi, il est un produit naturel bijection de l'ensemble des relations d'équivalence possibles sur X et l'ensemble de toutes les partitions de X.

Compter partitions possibles. Soit X un ensemble fini à n éléments. Étant donné que chaque relation d'équivalence sur X correspond à une partition de X, et vice versa, le nombre de relations d'équivalence éventuels sur X est égal au nombre de partitions distinctes de X, qui est la n-ième Bell a le numéro B _n:

Génération relations d'équivalence

• Compte tenu de tout ensemble X, il ya une relation d'équivalence sur l'ensemble de tous les possibles fonctions X → X. Deux de ces fonctions sont jugées équivalentes lorsque leurs ensembles respectifs de points fixes ont le même cardinal, correspondant à des cycles de longueur dans un une permutation . Des fonctions équivalentes dans cette manière forment une classe d'équivalence sur X ^2, et ceux-ci classes d'équivalence partition X ^2.

• Une relation d'équivalence ~ sur X est le noyau de l'équivalence de son surjective projection π: X → X / ~. (Birkhoff et Mac Lane 1999: 33 18 Th.). Inversement, toute surjection entre les séries détermine une partition sur son domaine, l'ensemble des préimages de singletons dans le codomaine. Ainsi, une relation d'équivalence sur X, une partition de X, et une projection dont le domaine est X, sont trois manières équivalentes de spécifier la même chose.

• L'intersection de deux des relations d'équivalence sur X (considéré comme un sous-ensemble de X × X) est également une relation d'équivalence. Cela donne un moyen pratique de générer une relation d'équivalence: donné aucune relation binaire R sur X, la relation d'équivalence généré par R est la plus petite relation d'équivalence contenant R. Concrètement, R génère la relation d'équivalence a ~ b si et seulement si il existe des éléments x _1, x _2, ..., x _n en X de telle sorte que a = x _1, b = x _n, et (x _i, x _{i + 1)} ∈ R ou (x _{i + 1,} x _i) ∈ R, i = 1, ..., n-1.

A noter que la relation d'équivalence engendrée de cette manière peut être triviale. Par exemple, la relation d'équivalence ~ généré par:

• La relation ≤ binaire a exactement une classe d'équivalence, X lui-même, parce que x ~ y pour tous les x et y;
• Une relation antisymétrique a classes d'équivalence qui sont la singletons de X.

• Soit r toute sorte de relation sur X. Alors R ∪ r ^-1 est un relation symétrique. Le fermeture transitive s des r ∪ r ^-1 assure que l'art est transitive et réflexive. En outre, s est la "plus petite" relation d'équivalence contenant r, et r / s partiellement commandes X / s.

• relations d'équivalence peuvent construire de nouveaux espaces par «collage des choses ensemble." Soit X l'unité Carré cartésien [0,1] × [0,1], et laisser ~ la relation d'équivalence sur X définie par ∀ a, b ∈ [0,1] ((a, 0) ~ (a, 1) ∧ (0 , b) ~ (1, b)). Puis le espace quotient X / ~ peut être naturellement identifié avec un tore : prendre un morceau de papier carré, plier et coller ensemble le bord supérieur et inférieur pour former un cylindre, puis pliez le cylindre résultant de manière à coller ensemble ses deux extrémités ouvertes, résultant dans un tore .

Structure algébrique

Treillis modulaires

Les relations d'équivalence possibles sur un ensemble X, lorsqu'il a ordonné par l'inclusion ensemble , forment un treillis modulaire, appelé Con X par convention. Le canonique carte ker: X ∧ X → Con X, concerne la monoid X ^ X de toutes les fonctions sur X et X Con. ker est surjective mais pas injective. Moins formellement, le ker de relation d'équivalence sur X, prend chaque fonction f: X → X à sa noyau ker f. De même, ker (ker) est une relation d'équivalence sur X ^ X.

La théorie des groupes

Il est très bien connu que théorie treillis capte la structure mathématique de relations d'ordre. Il est moins connu que groupes de transformation (certains auteurs préfèrent groupes de permutation) et leur orbites faire la lumière sur la structure mathématique de relations d'équivalence. Tout comme relations d'ordre sont fondées sur ensembles ordonnés, ensembles fermés en vertu paires supremum et infimum, relations d'équivalence sont fondées sur ensembles partitionnés, ensembles fermés en vertu bijections en préservant la structure de la partition. Depuis toutes ces bijections carte une classe d'équivalence sur lui-même, ces bijections sont également connus comme les permutations .

Let '~' désignent une relation d'équivalence sur un certain ensemble non vide A, appelé univers ou ensemble sous-jacent. Soit G désignent l'ensemble des fonctions bijectives sur A qui préservent la structure de partition de A: ∀ x ∈ A ∀ g ∈ G (g (x) ∈ [x]). Ensuite, les trois suivantes sont connectés théorèmes (Van Fraassen 1989: §10.3):

• ~ Un partitions en classes d'équivalence. (Ce est le théorème fondamental des relations d'équivalence, mentionnés ci-dessus);
• Étant donné un partition de A, G est un groupe de transformation par composition, dont la orbites sont le les cellules de la partition ‡;
• Étant donné un groupe de transformation G sur A, il existe une relation d'équivalence ~ sur A, dont les classes d'équivalence sont les orbites de G. (Wallace 1998: 202, Th 6; Dummit et Foote 2004:. 114, 2 Prop.).

En somme, étant donné une relation d'équivalence ~ sur A, il existe un groupe de transformation G sur A dont orbites sont les classes d'équivalence de A sous ~.

Cette caractérisation du groupe de transformation des relations d'équivalence diffère fondamentalement de la manière treillis caractérisent relations d'ordre. Les arguments des opérations de la théorie des treillis rencontrer et sont des éléments de rejoindre un univers A. Pendant ce temps, les arguments de la opérations du groupe de transformation composition et inverse sont des éléments d'un ensemble de bijections, A → A.

Déplacement à des groupes en général, H un sous-groupe d'un certain groupe G. Soit ~ une relation d'équivalence sur G, de sorte que a ~ b ↔ (ab ^-1 ∈ H). Les classes d'équivalence de ~ -également appelés les orbites de la action de H sur G -Y le droit cosets de H dans G. Interchangeant A et B donne les classes à gauche.

Pour en savoir plus sur la théorie des groupes et des relations d'équivalence, voir Lucas (1973: §31).

‡ Preuve (adapté de Van Fraassen 1989: 246). Que la composition de fonctions interpréter groupe multiplication et fonction inverse interpréter groupe inverse. Alors G est un groupe sous la composition, ce qui signifie que ∀ x ∈ A ∀ g ∈ G ([g (x)] = [x]), parce que G satisfait les quatre conditions suivantes:

• G est fermé dans la composition . La composition de deux éléments quelconques de G existe, car la domaine et codomaine de tout élément de G est un. En outre, la composition est de bijections bijective (Wallace 1998: 22, Th. 6);
• Existence de élément d'identité. Le la fonction d'identité, I (x) = x, est un élément évident de G;
• Existence de fonction inverse . Chaque fonction bijective g a une inverse g ^-1, de sorte que gg ^-1 = I;
• Composition associés . f (gh) = (fg) h. Cela vaut pour toutes les fonctions sur tous les domaines (Wallace 1998:. 24, Th 7).

Soit f et g deux éléments de G. En raison de la définition de G, [g (f (x))] = [f (x)] et [f (x)] = [x], de sorte que [g (f (x))] = [x ]. D'où G est un groupe de transformation (et un groupe d'automorphismes) parce composition de la fonction préserve la partition de A.

La théorie des catégories

La composition de morphismes centraux la théorie des catégories, désigné ici par concaténation, généralise la composition des fonctions centrales à des groupes de transformation. Les axiomes de théorie des catégories affirmer que la composition de morphismes associés, et que la gauche et la droite morphismes d'identité existent. Si tous les morphismes dans un catégorie était d'avoir «inverses», la catégorie ressemblerait à un groupe de transformation, dont l'étroite relation à l'équivalence relations vient d'être expliqué. Un morphisme f peut être dit d'avoir un inverse lorsque f est une automorphismes, à savoir la domaine et codomaine de f sont identiques, et il existe un morphisme g telle que fg = gf = identité morphisme. D'où le concept de la catégorie la théorie la plus proche à une relation d'équivalence est une catégorie dont les morphismes sont tous les automorphismes.

relations d'équivalence et de la logique mathématique

Relations d'équivalence sont une source immédiate d'exemples ou de contre-exemples. Par exemple, une relation d'équivalence avec exactement deux classes d'équivalence infinis est un exemple simple d'une théorie qui est ω- catégorique, mais pas catégorique pour tout grand nombre cardinal .

Une implication des théorie du modèle est que les propriétés définissant une relation peut être prouvé indépendants les uns des autres (et donc nécessaires parties de la définition) si et seulement si, pour chaque propriété, des exemples peuvent être trouvés des relations qui ne satisfont pas la propriété donnée tout en satisfaisant tous les autres propriétés. D'où la définition des propriétés de trois relations d'équivalence peut être prouvée mutuellement indépendants par les trois exemples suivants:

• Réflexive et transitive: La relation ≤ sur N. Ou tout pré-commande;
• Symétrique et transitive: La relation R sur N, définie comme aRb ↔ ab ≠ 0. Ou tout relation d'équivalence partielle;
• Réflexive et symétrique: Le rapport R sur Z, défini comme aRb ↔ "a - b est divisible par au moins un des deux ou 3." Ou tout relation de dépendance.

Propriétés définissables en logique du premier ordre qu'une relation d'équivalence peut ou peut ne pas posséder comprennent:

• Le nombre de classes d'équivalence est fini ou infini;
• Le nombre de classes d'équivalence est égale à la (fini) nombre naturel n;
• Toutes les classes d'équivalence ont infinie cardinal;
• Le nombre d'éléments dans chaque classe d'équivalence est le nombre naturel n.

L'équivalence prévue Euclid

Euclid s ' The Elements inclut la "notion commune une" suivante:

Des choses qui égalent la même chose aussi égale une autre.

Aujourd'hui, la propriété décrite par une notion commune est appelée Euclidienne (en remplaçant "égale" par "sont en relation avec"). Les connecte théorème suivant Relations euclidiennes et relations d'équivalence:

Théorème. Si une relation est euclidienne et réflexive, ce est aussi symétrique et transitive.

Preuve:

• (ARC ∧ BRC) → aRb [a / c] = (aRa ∧ BRA) → aRb [réflexive; effacer T ∧] = bRa → aRb. D'où R est symétrique .
• (ARC ∧ BRC) → aRb [symétrie] = (ARC ∧ CRB) → aRb. D'où R est transitive.

Ainsi une relation d'équivalence est une relation qui est euclidienne et réflexive. Les éléments ne mentionne ni symétrie, ni réflexivité, et d'Euclide aurait probablement jugé la réflexivité de l'égalité trop évident pour justifier mention explicite. Si ce (et en prenant «égalité» comme une relation abstraite tout usage) est accordée, une lecture de bienfaisance de notion commune serait une créditer Euclid d'être le premier à concevoir des relations d'équivalence et de leur importance dans systèmes déductifs.