Relations binaires - Prépa ENS (sujet ENS Cachan)

[ENS1D2]

Bonjour,

Dans le cadre d'un DM, j'ai un exercice issu du concours ENS Cachan (voie D2, économie/gestion), concernant les relations binaires qui me pose un peu problème.

Voici le sujet:

Et ce que j'ai fait jusque là:

1. (La question manquait un peu de clarté à mes yeux, j'en ai déduis que on se posait la question de savoir quelle proposition pouvait être vraie si on considère les 3 en même temps).
Si (x;)y) est vraie,
On a (x;)y) => non(y;)x)
Donc (y;)x) est fausse. De plus, (x~y) [non(x;)y) et non(y;)x)], donc si (x;)y) est vraie, (x~y) est fausse.

Si (y;)x) est vraie, on a (y;)x) => non(x;)y).

Or, on ne peut pas avoir (x;)y) ET (y;)x), donc (x;)y) ET (y;)x) sont fausses, on a ainsi [non(x;)y) et non(y;)x)] (x~y)
La seule proposition vraie est donc (x~y)
(ce qui paraît logique ; si x est préféré à y et que y est préféré à x cela implique qu'elles sont équivalentes et qu'en réalité x n'est pas préféré à y et y n'est pas préféré à x)

2. Là je bloque...
Pour rappel de la transitivité j'écris: Quelque soit x,y,z appartiennent à E^3
Si x R y, et y R z, si R est une relation transitive alors x R z.

D'après la propriété T, on a non(x;)y) et non(y;)z) => non(x;)z).
Sauf que la propriété A, (x;)y) => non(y;)x) est à sens unique..(ça se comprend, si y n'est pas préféré à x, cela ne veut pas forcément dire que x est préféré à y -> x peut être équivalent).

Un ami a fait comme ça:
Si on a [(x;)y) et (y;)z)] => [non(y;)x) et non(z;)y)] soit d'après la prop. A => non(z;)x).
Or, (x;)z) => non(z;)x)
Donc, (x;)z) [non(y;)x) et non(z;)y)] ; soit [(x;)y) et (y;)z)] => (x;)z)
Mais ça me semble faux puisqu'on ne peut pas passer de [non(y;)x) et non(z;)y)] à [(x;)y) et (y;)z)]...
En bref -> Je suis perdu sur cette question.

3.Une relation d'équivalence est une relation réflexive, symétrique, transitive.
Montrons que ~ est réflexive:
(x~x) [non(x;)x) et non(x;)x)]
Trivial, x est en relation avec x donc ~ est réflexive.

Montrons que ~ est symétrique:
(x~y) [non(x;)y) et non(y;)x)] [non(y;)x) et non(x;)y)] (y;)x)
~ est donc symétrique

Montrons que ~ est transitive:
(x~y) [non(x;)y) et non(y;)x)]
(y~z) [non(y;)z) et non(z;)y)]

(x~y) et (y~z) non(x;)y) et non(y;)x) et non(y;)z) et non(z;)y)
Or, d'après la propriété T:
-non(x;)y) et non(y;)z) => non(x;)z)
-non(y;)x) et non(z;)y) => non(z;)x)
On a donc [non(x;)z) et non(z;)x)] (x~z)
Donc ~ est transitive.
~ est réflexive, symétrique et transitive, c'est donc une relation d'équivalence.

4. Là je bloque pour les deux...
Dès que je veux utiliser une des propriétés données, je me retrouve coincé avec des non(x;)y) ou des non(x;)z) qui m'empêche de déduire les relations demandées...

5. Montrons que >= est transitive
(x >= y) (x;)y) ou (x~y)
(y >= z) (y;)z) ou (y~z)

(x >= y) et (y >= z) [(x;)y) ou (x~y)] et [(y;)z) ou (y~z)]
=> [(x;)y) et (y;)z)] ou [(x;)y) et (y~z)] ou [(x~y) et (y;)z)] ou [(x~y) et (y~z)]

Or:
*(x;)y) et (y;)z) => x;)z car est transitive d'après la question 2
*(x;)y) et (y~z) => x;)z d'après la question 4a
*(x~y) et (y;)z) => x;)z d'après la question 4b
*(x~y) et (y~z) => x~z car ~ est transitive (car c'est une relation d'équivalence).

On a donc (x;)z) ou (x~z) x >= z
Donc >= est transitive.

Merci d'avance à ceux qui pourront m'aider

[Doraki]

La question 1 demande de montrer que pour tout x et y,
on est dans l'un des 3 cas suivants :
cas 1. x;)y est vrai, y;)x est faux, x~y est faux.
cas 2. x;)y est faux, y;)x est vrai, x~y est faux.
cas 3. x;)y est faux, y;)x est faux, x~y est vrai.

Tu as montré que si x;)y est vrai alors on est dans le cas 1.
Ensuite j'ai pas compris ce que t'as fait c'est pas clair.

Dans la question 2,
Si x;)y et y;)z, alors non z;)x, c'est bon.
Et si x;)z, alors z;)x, c'est bon.
Mais la suite c'est n'importe quoi.
Moi je dirais qu'il faut regarder dans quel cas (1 2 ou 3) se trouvent x et z.

Dans la question 3, évite de dire "x est en relation avec x" quand y'a 3 relations différentes dans le contexte. Et tu n'as expliqué nulle part pourquoi pour tout x, x~x. Mais le reste est bien.

[ENS1D2]

Aaaaah d'accord, en effet j'avais mal compris la question.
Bon donc cas 2:

Si y;)x est vraie, on a y;)x => non(x;)y), donc x;)y est fausse.
Or (x~y) <=> [non(x;)y) et non(y;)x)], donc si y;)x est vraie, (x~y) est fausse
On a bien: x;)y est faux, y;)x est vrai, x~y est faux

Enfin cas 3:
Si (x~y) est vraie, (x~y) <=> [non(x;)y) et non(y;)x)] donc (x;)y) est fausse et (y;)x) est fausse.
On a bien: x;)y est faux, y;)x est faux, x~y est vrai

Pour la 2:
Quand tu parles des cas 1,2 ou 3, tu fais référence à la première question ?
Ben...x et z, on veut que x;)z soit vraie, ce qui serait le cas 1.
Est-ce que démontrer que z;)x et x~z sont fausses reviendrait à démontrer que x;)z est vrai ?

Pour la 3:
x~x <=> [non(x;)x) et non(x;)x)] <=> non(x;)x)
J'ai dû mal à l'expliquer clairement parce que ça me paraît évident, peut être en utilisant le cas 3:
x;)x est faux puisque x ne peut pas être préféré à lui même (mais rien ne me le dit ça, enfin dans la définition de ;) on ne dit pas qu'elle n'est pas réflexive...), x;)x est faux (c'est la même chose en même temps), donc x~x est vrai.

[Doraki]

T'as toujours pas fini pour la question 1.
Pour l'instant tu as donc montré que :
si x;)y alors on est dans le cas 1
si y;)x alors on est dans le cas 2
si x~y alors on est dans le cas 3.

Mais tu n'as pas montré qu'on était toujours dans l'un de ces cas.
Donc il reste à montrer qu'il est impossible d'avoir x;)y,y;)x,x~y tous les trois faux.

Moi j'aurais fait un truc du genre
"ou bien x;)y est vrai et alors blablabla on est dans le cas 1,
ou bien x;)y est faux. Dans ce cas, ou bien y;)x est vrai et alors blablabla on est dans le cas 2,
ou bien y;)x est faux et alors blablabla on est dans le cas 3."

Pour la question 2, tu dois montrer que tu ne peux pas être dans le cas 2 (facile), ni être dans le cas 3. Ce qui te force à être dans le cas 1 d'après la question 1.
donc tu supposes que t'es dans l'un de ces cas et tu cherches une contradiction.

[ENS1D2]

J'ai fait ça:
Si ;) est transitive: x;)y et y;)z => x;)z
On veut x;)z vrai, si x;)z est vrai, d'après le 1, z;)x est faux et x~z est faux, soit x;)z <=> [non(z;)x) et non(x~z)]

Si on a x;)y => non(y;)x)
Et y;)z => non(z;)y)

[non(y;)x) et non(z;)y)] => non(z;)x)

z;)x est faux donc on est pas dans le cas 2.
Maintenant je bloque pour les deux autres...Puisque j'ai du mal à voir ce qui empêche x~z d'être vrai tant que je ne démontre pas que ;) est bien transitive : /
Etant aussi en pleine période de partiels et ayant ce devoir à rendre vendredi je doute que j'arriverais à terminer l'exercice en entier de manière correcte mais bon.
Des pistes sinon pour le 4a et b ? Il faut utiliser le même type de raisonnement, à savoir se servir des 3 cas du 1 et des questions précédentes ? (;) transitive et ~ réflexive ?).
Merci pour l'aide déjà apportée ! :s

[Doraki]

1. écrire toutes tes hypothèses (en termes de ;), pas de ~ ou de <=)
2. déduire le plus de trucs possibles avec les règles S et T
3a. Si on a déduit ce qu'on voulait montrer, on a fini
3b. Si on a montré qu'un truc était à la fois vrai et faux, c'est qu'on s'est mis dans un cas impossible et on a fini
4. Si on est bloqué, on fait une étude de cas (du genre "soit w;)y est vrai, soit w;)y est faux" ou alors "w et y sont soit dans le cas 1 soit dans le cas 2 soit dans le cas 3")
5. goto 2.

C'est mécanique, y'a pas à réfléchir. Il faut juste rien oublier à l'étape 2, ne pas oublier les contradictions à l'étape 3b, et faire proprement les études de cas.

Si tu veux utiliser les résultats des questions d'avant ça revient à prendre des raccourcis (t'es jamais obligé). Mais j'ai pas l'impression que ce soit tellement utile dans la question 4.

[ENS1D2]

2 semaines plus tard...j'ai pu bosser l'exercice et il me semble avoir trouvé la 2 et la 4:
2) Hypothèses de départ: x;)y et y;)z
Or d'après la propriété A: x;)y => non(y;)z)
y;)z => non(z;)y)
Et d'après la propriété T: non(z;)y) et non(y;)x) => non (z;)x)

-> z;)x est donc faux, on est soit dans le cas 1 soit dans le cas 3.
Si on est dans le cas 3, (x~z) est vraie.
Or, (x~z) vraie équivaut à [non(x;)z) et non(z;)x)]
Or si on a non(x;)z), sachant que dans les hypothèses de départ on a non(z;)y), d'après la propriété T on aurait non(x;)y), ce qui est impossible puisque x;)y fait partie des hypothèses de départ.
On ne peut donc pas être dans le cas 3, et d'après le 1), puisqu'on est toujours dans l'un des 3 cas, on est donc dans le cas 1: x;)z est vraie.
On en déduit que si on a x;)y et y;)z, on a x;)z donc la relation ;) est transitive.


4) a)Hypothèses de départ: x;)y et y~z
D'après la propriété A: x;)y => non(y;)x)
(y~z) <=> non(y;)z) et non(z;)y)
Or d'après la propriété T: non(y;)x) et non(z;)y) => non(z;)x)
z;)x est donc faux: on est dans le cas 1 ou dans le cas 3.
Supposons qu'on est dans le cas 3: x~z est donc vraie <=> non(x;)z) et non(z;)x)
Or, non(x;)z) et non(z;)y) => non(x;)y) d'après la propriété T, ce qui est impossible puisque x;)y fait partie des hypothèses de départ.
On est donc forcément dans le cas 1, x;)z est vraie, on peut donc écrire que x;)y et y~z => x;)z

b)Hypothèses de départ: (x~y) et (y;)z)
D'après la propriété A: y;)z => non(z;)y)
Et on a x~z <=> non(x;)y) et non(y;)x)
D'après la propriété T: non(z;)y) et non(y;)x) => non(z;)x)
On est donc soit dans le cas 1 soit dans le cas 3.
Supposons qu'on est dans le cas 3: x~z <=> non(x;)z) et non(z;)x)
Or, d'après la propriété T, non(y;)x) et non(x;)z) => non(y;)z), ce qui est impossible puisque y;)z fait partie des hypothèses de départ.
On est donc forcément dans le cas 1, x;)z est donc vraie, on peut écrire (x~y) et (y;)z) => (x;)z)