Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] \| Liste Catégories \| Une page au hasard \| Pages liées

Relation binaire

Cet article fait doublon avec Relation (mathématiques). Il a été demandé de les fusionner sur la page prévue à cet effet.

Merci de n'y apporter aucune modification tant que cette fusion n'aura pas été effectuée et que ce message n'aura pas disparu.

Sommaire

1 Définition

2 Propriétés

3 Nombre de relations binaires sur un ensemble fini

4 Exemples

5 Voir aussi

Définition

Une relation binaire est un concept mathématique qui généralise des relations comme « est supérieur ou égal à » en arithmétique, ou « est un élément d'un ensemble » en théorie des ensembles.

De manière informelle, étant donné un ensemble d'objets (disons des nombres), nous pouvons dire qu'une relation notée $\mathcal R$ est une propriété vérifiée ou non par les couples d'objets de cet ensemble :

pour tout couple d'objets, nous pouvons avoir $x \mathcal R y$ ( est en relation avec ) ou pas. Cela peut être étendu au cas où et sont respectivement des éléments d'ensembles et quelconques (par exemple : ensemble d'objets, ensemble de personnes, $\mathcal R$ peut être la relation « appartient à »).

Formellement, une relation binaire sur un ensemble et un ensemble est un sous-ensemble de $X \times Y$ , où $X \times Y$ est le produit cartésien de et , i.e. ensemble de couples de la forme . Nous identifions le sous-ensemble à la relation $\mathcal R$ , et nous écrivons indifféremment :

Une relation binaire peut être considérée comme une fonction de $X \times Y$ à valeur dans l'ensemble qui à un couple associe si est en relation avec et sinon (indiquant si le couple est un élément de l'ensemble correspondant à la relation).

Propriétés

Les propriétés suivantes sont fondamentales pour la définition des applications. Une relation $\mathcal R$ sur et est dite :

surjective à gauche si pour tout dans , il existe dans tel que $x \mathcal R y$ :
$\forall x \in X, \exists y \in Y, x \mathcal R y$
surjective à droite si pour tout dans , il existe dans tel que $x \mathcal R y$ :
$\forall y \in Y, \exists x \in X, x \mathcal R y$
injective si pour tous et dans et dans , si $x \mathcal R y$ et $z \mathcal R y$ alors :
$\forall x, z \in X, \forall y \in Y, (x \mathcal R y) \and (z \mathcal R y) \implies (x=z)$
univoque si pour tous dans , et et dans , si $x \mathcal R y$ et $x \mathcal R z$ alors :
$\forall x \in X, \forall y, z \in Y, (x \mathcal R y) \and (x \mathcal R z) \implies (y=z)$

Une relation binaire univoque est appelée une fonction.

Une relation binaire qui est à la fois fonction et surjective à gauche est appelée une application.

Si alors nous disons simplement que $\mathcal R$ est une relation binaire sur . Une relation binaire $\mathcal R$ sur est dite :

réflexive si pour tout dans , on a $x \mathcal R x$ :
$\forall x \in X, x \mathcal R x$
symétrique si pour tout et dans , si $x \mathcal R z$ alors $z \mathcal R x$ :
$\forall x, z \in X, (x \mathcal R z) \implies (z \mathcal R x)$
asymétrique si pour tout et dans , si $x \mathcal R z$ alors (non $z \mathcal R x$ ) :
$\forall x, z \in X, (x \mathcal R z) \implies \neg(z \mathcal R x)$
antisymétrique si pour tout et dans , si $x \mathcal R z$ et $z \mathcal R x$ alors :
$\forall x,z \in X, (x \mathcal R z) \and (z \mathcal R x) \implies (x = z)$
transitive si pour tout , et dans , si $x \mathcal R y$ et $y \mathcal R z$ alors $x \mathcal R z$ :
$\forall x, y, z \in X, (x \mathcal R y) \and (y \mathcal R z) \implies (x \mathcal R z)$
totale si pour tout et dans , on a $x \mathcal R y$ ou $y \mathcal R x$ :
$\forall x, y \in X, (x \mathcal R y) \or (y \mathcal R x)$

Une relation qui est réflexive, symétrique et transitive est appelée une relation d'équivalence.

Une relation qui est réflexive, antisymétrique et transitive est appelée une relation d'ordre.

Nombre de relations binaires sur un ensemble fini

Considérons un ensemble fini de cardinal . Nous pouvons facilement démontrer qu'il y a autant de relations binaires sur que d'applications de $E \times E$ dans , i.e. $2^{n^2}$ relations.

il y a relations réflexives
il y a relations symétriques

Pour le nombre de relations transitives, il n'y a toujours pas actuellement de formule « fermée » Le nombre de relations d'équivalence est égal au nombre de partitions d'un ensemble, c'est-à-dire le nombre de Bell.

Exemples

La relation d'appartenance sur $E \times \mathcal{P}(E)$
La relation d'inclusion sur $\mathcal{P}(E)$ (relation d'ordre)
La relation inférieur ou supérieur sur $\mathbb{R}$ (relations d'ordres)
la relation divise sur $\mathbb{Z}$ ou $\mathbb{R}[X]$ (relation d'ordre)
La relation d'égalité (congruencielle ou non) sur E (relation d'équivalence)

Voir aussi

Catégories: Théorie des ensembles

This site support the Wikimedia Foundation. This Article originally from Wikipedia. All text is available under the terms of the