Maths discrètes - Relation -ordre lexicographique

[dut]

Bonjour, je m'exerce sur un exercice typique (que nous avons déjà traité ensemble: https://forum.mathforu.com/topic/30046/relation-d-ordre-ordre-total/5) mais qui pose énormément de problème d'un point de vu raisonnement.

Soit X l'ensemble des mots binaires non vides. On note $\le$ 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 SSI il existe w € X tel que w $\le$ u et w $\le$v

La relation R est t-elle:

Reflexive?
Oui en prenant U=001, w=000, V=010
R=ewe (e=element vide)$\le$u et ewe$\le$V

symetrique?
Non car w$\le$u different de u$\le$w et w$\le$v différent v$\le$w

Transitive?
URV et VRW
Je dirais non mais je ne sais pas comment l'écrire

Antisymètrique: U R V et VRU
|u|$\le$|v| et |V|$\le$|U| Non

Pouvez-vous me corriger?

Merci

[mtschoon]

Je viens de modifier ton énoncé avec la précision donnée, mise en gras dans ton énoncé
Cela change ainsi l'explication proposée au départ !

Un conseil ; n'essaie pas de répondre aux questions en imitant un autre exercice, mais comprends ce que signification la relation R
Dans l'exercice que tu donnes en lien, il s'agit de facteurs alors que dans cet exercice, il s'agit de l'ordre lexicographique c'est à dire de l'ordre du "dictionnaire" avec des 0 et 1, sachant que 0 < 1

L'énoncé te précise que $\le$ est une relation d'ordre (donc à utiliser directement)

$W\le U$ signifie que W est "avant" U dans l'ordre lexicographique (W peut être préfixe de U, mais c'est un cas particulier, il faut étudier le cas général avec 0 et 1.

On compare les chiffres ( 0 - 1) de gauche des deux mots
Si un mot commence par 0 et l'autre par 1, alors $0...\le 1...$
Si les deux mots commencent par le même chiffre (deux 0 ou deux 1), on compare les deux chiffres suivants, etc, etc...

Exemples :
$01\le 0110$
$100100\le 1001001$
$010111\le 1100$
$101\le 110$
$101\le 101$ (car $\le$ réflexive)

[mtschoon]

Je te donne quelques indications pour l'étude à faire sur R.
(rédaction abrégée)

Réflexivité : U R U ?
Soit W tel que $W\le U$ et $W\le U$ équivaut à dire W est tel que $W\le U$
C'est vrai

Symétrie U R V => V R U ?
Soit W tel que $W\le U$ et $W\le V$ équivaut à dire W est tel que $W\le V$ et $W\le U$
C'est vrai

Transitivité U R V et V R T => U R T ?
Soit W tel que $W\le U$ et $W\le V$
Soit W' tel que $W^{\prime }\le V$ et $W^{\prime }\le T$

Il faut voir deux cas suivant que $W\le W^{\prime }$ ou $W^{\prime }\le W$

Je te fais le cas $W\le W^{\prime }$

$W\le U$
$W\le W^{\prime }\le T$

Vu que la relation $\le$ est transitive (car relation d'ordre) , on peut déduire que $W\le T$

Bilan, on obtient $W\le U$ et $W\le T$ donc U R T est vrai.

Je te laisse traiter les cas $W^{\prime }\le W$

Dans les deux cas, c'est vrai

Anti-Symétrie
U R V et V R U => U=V ?
C'est faux

Un contre-exemple pour le prouver.
Soit U=101 et V=110
En choisissant W=010, on a bien $W\le U$ et $W\le V$ et pourtant $U\ne V$

Bon courage pour tes révisions.

[dut]

Je n'avais pas tout mais ça à l'air de rentrer doucement.

Merci ces révisions me stressent énormément.

[mtschoon]

Le mieux serait de ne pas stresser mais c'est normal !

Tu travailles avec sérieux donc ton travail portera ses fruits.

Un conseil , que tu appliques déjà peut-être.

Parfois, tu ne sais pas faire un exercice tout simplement car tu as des difficultés à comprendre l'énoncé.
Alors, sans refaire tous les exercices de l'année ( ce serait un travail fastidieux !), tu pourrais relire les énoncés avec grand soin (au mot près, car un mot peut changer le sens d'un énoncé) et t'assurer de bien comprendre ce qu'il signifie. C'est la base pour pouvoir répondre correctement.
Bien sûr, si un énoncé te pose problème, tu peux nous poser la question.

Bon travail !