Université de Nice-Sophia Antipolis École Supérieure en Sciences Informatiques

2004–2005

Contrôle de Mathématiques Discrètes du 6 octobre 2004

Nom : Prénom : Groupe:

Durée : 25 minutes

1 2 3 4

1

On dit que le pays a est supérieur au pays b si a = b ou si a a obtenu strictement plus de médailles que b aux Jeux Olympiques d’Athènes en 2004. Justifier que cette relation est un ordre partiel.

Que dire de deux pays non comparables?

2

La relation d’égalité est elle une relation d’ordre bien fondé ?

Une relation d’ordre est telle que toute partie de n éléments contient n éléments maximaux. Donner un exemple d’une telle relation.

Est-ce qu’il y en a d’autres?

4

Soit (E,≤) un ensemble ordonné (l’ordre ≤ est de plus total). Soit R la relation sur P(E) \ {∅} définie par : ARB ⇔ ∀a ∈ A,∃b ∈ B,a ≤ b. La relation R est-elle une relation d’ordre?

Une relation d’ordre est telle que pour tout élément x, il y a un nombre fini d’éléments inférieurs à x. Cette relation est-elle un ordre bien fondé?

6

Sur l’ensemble des disques du plan, on définie une relation ≤ par d ≤ d′ si le disque d est inclus dans le disque d′. Est-ce une relation d’ordre bien fondé?

Soit E = {a,b,c,d}. On considère l’ordre strict sur E, R_{1} défini par xR_{1}y ⇔ (x,y) ∈ R_{1} avec R_{1} = {(a,b),(a,c),(a,d)}.

– E a-t-il un plus petit élément?

– E a-t-il un plus grand élément?

– Donner un sous-ensemble de E n’ayant ni plus petit, ni plus grand élément ?

– Représenter par un dessin l’ordre strict sur R_{1}

Soit E = {a,b,c}, on sait que l’inclusion ⊆ est un ordre partiel sur l’ensemble des parties de E, P (E). Comment complèter l’inclusion dans ce cas particulier, pour obtenir un ordre total?

9

Donner un exemple de relation d’ordre qui ne soit aucun de ceux abordés en cours/TD.

6