les relations binaires

Bonjour,
Suite aux explications de Mtschoon de ce matin j'ai tenté de faire un exercice type partiel.
Je l'ai fait entièrement, je vais essayer de vous détailler mes réponses et si quelqu'un a un peu de temps pour valider ou non mes réponses cela serait génial.

L'énoncé est:
Soit X l'ensemble des mots binaires non vides. On note <= la relation
d'ordre lexicographique sur X (en posant 0 < 1). On considère la relation R sur X, définie
par :
u R v si et seulement si il existe w € X tel que w <=u et w <=v.
La relation R est-elle :
a. réflexive ?
b. symétrique ?
c. transitive ?
d. antisymétrique ?

a) la relation est réflexive car si on prend 1R1
1<=1 et 1<=1

b)
x R y -> y R x
La relation n'est pas symétrique ça 0R1 oui mais 1R0 non, 1 étant plus grand que 0

c) la relation est transitive, prenons:
xRy et yRz -> xRz
0R1 et 1R11 --> 0R11
0<=0 et 0<=1 ; 1<=1 et 1<=11 donc 0<=0 et 0<=11

d) La relation est antisyemetrique:
xRy et yRx --> x=y
001R001 et 001R001
001<=001 et 001<=001, x est bien égal à y

Merci par avance et bonne fin d'ap

Bonsoir Dut,

Je regarde rapidement tes réponses.
Elles ne sont pas au point...et je ne sais pas si tu as compris précisemenr la définition de cette relation R
Je détaillerai au mieux demain.

Mince je n'étais pas mécontent de ma réponse. Est ce que vous pourriez m'expliquer demain uniquement la relation, j'essaierai de résoudre le problème avec votre explication.
Passez une bonne soirée

Bonjour Dut,

Quelques remarques :
1)Assure toi d'avoir compris la relation : c'est essentiel car tout s'en découle.
L'énoncé indique :
u R v si et seulement si il existe W € X tel que W <=u et W <=v.
Il faut donc, tout simplement, que tu indiques une valeur de W telle que $\le u$ et $W≤vW\le v$
Dans ce que tu indiques, on ne voit pas apparaître W

Un exemple pour comprendre
est-ce que 1111 R 1001 est vraie ?
la réponse est Oui
Pour W=1 , $1≤11111\le 1111$ et $1≤10011\le 1001$ donc 1111 R 1001 est vraie.
On aurait pu donner d'autres valeurs pour W ( 0 ou 1000 ...)

2)J'ignore si dans tes partiels la rigueur de la démonstration est importante ou s'il suffit de trouver le bon résultat.
Si la rigueur est importante, comme je te l'ai indiqué dans un topic précédent, les propriétés doivent être prouvées de façon générale et pas seulement avec un exemple.
Par contre, pour indiquer qu'un propriété est fausse, un exemple suffit (ce que l'on appelle un contre exemple)

3)Tu sembles avoir encore des difficultés avec l'antisymétrie.

Je t'avais mis un lien dans ton précédent topic
"Nous dirons qu'une relation binaire sur un ensemble E est 'antisymétrique' si dès qu'un élément est relié à un autre, et que cet autre est relié à lui alors ils sont nécessairement égaux.
Ou bien encore, on ne peut pas trouver deux éléments distincts x et y tels que xRy et yRx
R symétrique ⇔ ∀ x,y ∈E (xRy ∧ yRx) ⇒ y=x"

Je t'indiques, en plus, une propriété qui peut, dans certains cas, te simplifier la tache.
Si une propriété n'est pas symétrique, elle peut être, ou pas, antisymétrique. Il faut étudier l'antisymétrie pour le savoir.
Par contre, sauf pour la cas pour la relation d'égalité, si une propriété est symétrique, elle ne peut pas être antisymétrique.

Comme tu le souhaites, je te laisse revoir les propriétés.
Tiens nous au courant si besoin.

Bonjour Mtschoon,
tout d'abord je vous souhaite une excellente année. Quelle soit pour vous bonheur,santé et satisfaction.

Merci pour votre explication. La relation est quand même réfléxive, symétrique et antisymétrique? et n'est pas symétrique?

Merci pour tes bons voeux , Dut.
A mon tour de te souhaiter une très excellente année 2019.

Il faut que tu réfléchisses encore à la définition de R.
La relation R est réflexive, transitive, symétrique, et non antisymétrique (ce qui est, comme je te l'ai indiqué une conséquence de la symétrie).

Essaie de prouver tout cela .
Si besoin, je te détaillerai les explications.

Pour la symétrie je vois bien que 1111R1001 et 1001R1111 sont symétrique.
Par contre pour l'antisymétrie quelle est la rédaction a donné car malgré la propriété que je ne connaissais pas 1 R 1 est juste car w=1 1<=1 et 1<=1

Je n'ai donc pas besoin de raisonner comme ça, je donne juste la propriété

Comme je te l'ai dit plusieurs fois, si tu dois donner, un jour de contrôle, une explication rigoureuse, il faut donner une justification générale.

Pour la symétrie :

Soit u et v tels que u R v est vraie.
Par définition, c'est qu'il existe W tel que $W≤uW\le u$ ET $W≤vW\le v$
(Remarque W=0 convient dans tous les cas)

La question est : est ce que v R u est vraie ?

La réponse est OUI car si $W≤uW\le u$ ET $W≤vW\le v$ , nécessairement $W≤vW\le v$ ET $W≤uW\le u$ , donc v R u.
C'est une évidence...

Pour l'antisymétrie.

Si un jour de contrôle , tu es sûr de la symétrie et si tu galères pour justifier que l'antisymétrie est fausse (ce qui est pourtant une évidence) , tu peux énoncer la propriété que je t'ai indiquée :
Si la relation n'est pas la relation d'égalité, et si la relation est symétrique, elle ne peut pas être antisymétrique

L'explication directe est très simple.
Pour dire NON, un exemple suffit (c'est ce qu'on appelle une contre exemple)

Il suffit de prendre deux mots u et v tels que u R v et v R u sont vraies et tels que $\ne v$

Soit par exemple :
u=1111R1001 et v=1001R1111

u R v est vraie car en prenant w=1 ,
$w≤1111R100w\le 1111R100$ ET $w≤1001R1111w\le 1001R1111$

v R u est vraie car en prenant w=1 ,
$w≤w\le$ 1001R1111 ET $w≤1111R100w\le 1111R100$

Tout ceci est évident vu que la relation est symétrique

Bien sûr:
$\fbox{1001R1111 \ne 1111R100}$ c'est à dire $\fbox{u \ne v}$

Donc la propriété d'antisymétrie n'est pas vérifiée

Merci beaucoup Mtschoon, c'est maintenant clair dans mon esprit pour cet exercice.

C'est très bien Dut, si c'est clair maintenant.