Forum de mathématiques - Bibm@th.net

Victor

Invité

Ensemble de structures binaires

Bonjour,

On a un travail de groupe très difficile et il y a une certaine question à laquelle nous n'arrivons pas à y répondre. Nous pensons que la réponse pourrait nous débloquer sur tout le reste du sujet. Est-ce que quelqu'un pourrait nous aider ?

Merci à vous d'avance.

Le sujet :

On rappelle qu’une structure binaire est un couple où la deuxième composante est une relation binaire ayant
pour base la première composante. C’est-à-dire que la deuxième composante est un sous-ensemble du produit cartésien de la première composante par elle-même. Ainsi pour la structure binaire B on a que B(1) est un ensemble et que B(2) ⊆ B(1) × B(1). Une structure binaire B est dite non vide si B(1) 6= ∅.

On appelle pseudo-chemin, dans une structure binaire non vide B, toute suite finie non vide d’éléments de
B(1) telle que deux éléments consécutifs de cette suite induisent un élément de B(2). C’est-`a-dire que Ch est un pseudo-chemin de B si les deux conditions suivantes sont vérifiées :
1. ∃k ∈ ℕ∗, tel que Ch = (x_i)_i∈[k] et {x_i: i ∈ [k]} ⊆ B(1), et
2. soit k = 1, soit k 6= 1 et alors ∀i ∈ [k − 1], on a (x_i, x_i+1) ∈ B(2).
On appelle chemin élémentaire dans une structure binaire non vide B tout pseudo-chemin uniquement
constitue d’éléments distincts.
Une structure binaire non vide B est sans circuit si tous ses pseudo-chemins sont des chemins élémentaires.
On peut montrer qu’une structure binaire non vide est sans circuit si et seulement s’il existe k ∈ N∗
et une suite (Xi)i∈[k], dite suite “linéarisante”, telle que :
1. {X_i: i ∈ [k]} soit une partition de B(1),
2. ∀e ∈ B(2), ∃i, j ∈ [k] tels que i <_ℕ j, e(1) ∈ X_i et e(2) ∈ X_j .
On rappelle que la longueur d’une suite correspond au nombre d’éléments la composant. Ainsi la suite (αi)i∈[k] est de longueur k.

La question :
Montrez qu’une structure binaire non vide B est sans circuit si et seulement si elle possède une suite
“linéarisante”.

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Ensemble de structures binaires

Bonjour,

  Il y a un sens qui me semble assez facile : si on possède une suite "linéarisante", alors on est sans circuit.
En effet, si on prend un pseudo-chemin $(x_1,\dots,x_k)$, alors pour chaque $p$ dans $1,\dots,k$, il existe un $i_p$ tel que
$x_p\in X_{i_p}$ (la suite linéarisante réalise une partition), et la propriété 2. dit que la suite $(i_p)$ est strictement croissante. Ainsi, il est impossible que $x_p=x_q$ si $p<q$.

Pour la réciproque, cela a l'air nettement plus ardu.....

F.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 913

Re : Ensemble de structures binaires

Bonjour,

Pour la réciproque on peut considérer la relation d'équivalence R entre éléments x et y de B(1), x R y <=> il existe un pseudo-chemin de x vers y, ou de y vers x, ou  x = y. On obtient une partition en fait en chemins si on fait l'hypothèse que la structure binaire est sans circuit , qui donne la suite linéarisante.

Alain