Début de la boite de navigation du chapitre
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, «
Introduction aux mathématiques : Relations binaires Introduction aux mathématiques/Relations binaires », n'a pu être restituée correctement ci-dessus.
Ici
E
{\displaystyle E}
Voir aussi : Relation (mathématiques)/Définition .
Définition et notation : relations binaires
On appelle
relation binaire sur
E , toute partie de
E ×
E .
Si
R
{\displaystyle {\mathcal {R}}}
est une telle relation sur
E et si
x
,
y
∈
E
{\displaystyle x,y\in E}
, on note
x
R
y
{\displaystyle x{\mathcal {R}}y}
plutôt que
(
x
,
y
)
∈
R
{\displaystyle (x,y)\in {\mathcal {R}}}
.
Pour
E
=
N
{\displaystyle E=\mathbb {N} }
R
=
{
(
0
,
1
)
,
(
3
,
7
)
,
(
3
,
4
)
,
(
1
,
1
)
}
{\displaystyle {\mathcal {R}}=\{(0,1),(3,7),(3,4),(1,1)\}}
0
R
1
{\displaystyle 0{\mathcal {R}}1}
3
R
7
{\displaystyle 3{\mathcal {R}}7}
3
R
4
{\displaystyle 3{\mathcal {R}}4}
3
R
5
{\displaystyle 3{\mathcal {R}}5}
L'égalité (
=
{\displaystyle =}
E
{\displaystyle E}
Δ
=
{
(
x
,
x
)
,
x
∈
E
}
{\displaystyle \Delta =\{(x,x),x\in E\}}
x
=
y
{\displaystyle x=y}
x
Δ
y
{\displaystyle x\Delta y}
L'inclusion sur
P
(
E
)
{\displaystyle {\mathcal {P}}(E)}
R
=
{
(
X
,
Y
)
∈
P
(
E
)
2
/
X
⊂
Y
}
{\displaystyle {\mathcal {R}}=\{(X,Y)\in {\mathcal {P}}(E)^{2}/X\subset Y\}}
L'ordre sur
R
{\displaystyle \mathbb {R} }
R
=
{
(
x
,
y
)
∈
R
2
/
x
≤
y
}
{\displaystyle {\mathcal {R}}=\{(x,y)\in \mathbb {R} ^{2}/x\leq y\}}
Soit
R
{\displaystyle {\mathcal {R}}}
E .
R
{\displaystyle {\mathcal {R}}}
réflexive ssi
∀
x
∈
E
,
x
R
x
{\displaystyle \forall x\in E,x{\mathcal {R}}x}
transitive ssi
∀
x
,
y
,
z
∈
E
,
(
x
R
z
et
z
R
y
)
⇒
x
R
y
{\displaystyle \forall x,y,z\in E,(x{\mathcal {R}}z\,{\text{et}}\,z{\mathcal {R}}y)\Rightarrow x{\mathcal {R}}y}
symétrique ssi
∀
x
,
y
∈
E
,
x
R
y
⇒
y
R
x
{\displaystyle \forall x,y\in E,x{\mathcal {R}}y\Rightarrow y{\mathcal {R}}x}
E est vide) ;antisymétrique ssi
∀
x
,
y
∈
E
,
x
R
y
et
y
R
x
⇒
x
=
y
{\displaystyle \forall x,y\in E,x{\mathcal {R}}y\,{\text{et}}\,y{\mathcal {R}}x\Rightarrow x=y}
complète ssi
∀
x
,
y
∈
E
,
x
R
y
ou
y
R
x
{\displaystyle \forall x,y\in E,x{\mathcal {R}}y\,{\text{ou}}\,y{\mathcal {R}}x}
Définitions et notations :
relation d'équivalence , classes d'équivalence, ensemble quotient, surjection canonique
On appelle
relation d'équivalence sur
E toute relation binaire
R
{\displaystyle {\mathcal {R}}}
sur
E à la fois
réflexive ,
transitive et
symétrique .
Pour tout
x
∈
E
{\displaystyle x\in E}
classe d'équivalence de x modulo
R
{\displaystyle {\mathcal {R}}}
E notée
x
¯
=
{
y
∈
E
∣
x
R
y
}
{\displaystyle {\overline {x}}=\{y\in E\mid x{\mathcal {R}}y\}}
L'ensemble de ces classes d'équivalence, qui est une partie de
P
(
E
)
{\displaystyle {\mathcal {P}}(E)}
ensemble quotient de
E
{\displaystyle E}
R
{\displaystyle {\mathcal {R}}}
, noté
E
/
R
{\displaystyle E/{\mathcal {R}}}
L’application
π
:
E
→
E
/
R
,
x
↦
x
¯
{\displaystyle \pi :E\rightarrow E/{\mathcal {R}},x\mapsto {\overline {x}}}
. C'est une surjection, appelée
surjection (ou projection)
canonique .
Début d'un lemme
Lemme
∀
x
,
y
∈
E
(
x
R
y
⇒
x
¯
=
y
¯
)
{\displaystyle \forall x,y\in E\quad \left(x{\mathcal {R}}y\Rightarrow {\overline {x}}={\overline {y}}\right)}
.
Fin du lemme
Proposition
Les classes d'équivalence forment une partition de E .
'Démonstration'
D'abord, ce sont des parties de E .
Par réflexivité de
R
{\displaystyle {\mathcal {R}}}
x
∈
x
¯
{\displaystyle x\in {\overline {x}}}
E .
Enfin, deux classes non distinctes sont disjointes, car deux classes non disjointes sont égales. En effet, si
z
∈
x
¯
∩
y
¯
{\displaystyle z\in {\overline {x}}\cap {\overline {y}}}
x
R
z
{\displaystyle x{\mathcal {R}}z}
y
R
z
{\displaystyle y{\mathcal {R}}z}
x
¯
=
z
¯
=
y
¯
{\displaystyle {\overline {x}}={\overline {z}}={\overline {y}}}
Exercice
Étant donnée une partition de
E
{\displaystyle E}
Voir aussi : Relation (mathématiques)/Relation d'ordre .
Définitions et notations : relations d'ordre, ensembles ordonnés, ordres totaux
On appelle
relation d'ordre sur
E toute relation binaire
R
{\displaystyle {\mathcal {R}}}
sur
E à la fois
réflexive ,
transitive et
antisymétrique .
On appelle ensemble ordonné un tel couple
(
E
,
R
)
{\displaystyle (E,{\mathcal {R}})}
On note plus volontiers
≤
{\displaystyle \leq }
L'ordre est dit
total si pour tous éléments
x
,
y
∈
E
(
x
≤
y
ou
y
≤
x
)
{\displaystyle x,y\in E\quad \left(x\leq y\,{\text{ ou }}\,y\leq x\right)}
. C'est le cas de l’ordre usuel sur
R
{\displaystyle \mathbb {R} }
mais pas de l'inclusion sur
P
(
E
)
{\displaystyle {\mathcal {P}}(E)}
dès que
E
{\displaystyle E}
a au moins deux éléments.
(
E
,
≤
)
{\displaystyle (E,\leq )}
Proposition et définition : plus petit et plus grand éléments
Wikipedia-logo-v2.svg Soit
A
⊂
E
{\displaystyle A\subset E}
Alors il existe au plus un élément
m
∈
A
{\displaystyle m\in A}
∀
x
∈
A
x
≤
m
{\displaystyle \forall x\in A\quad x\leq m}
Un tel élément est appelé
plus grand élément de
A
{\displaystyle A}
, noté
max
A
{\displaystyle \max A}
. On définit de même un éventuel
plus petit élément .
Définitions : majorants, minorants, bornes supérieure et inférieure
Wikipedia-logo-v2.svg Wikipedia-logo-v2.svg Une partie
A
⊂
E
{\displaystyle A\subset E}
majorée (resp : minorée ) ssi
∃
m
∈
E
/
∀
x
∈
A
,
x
≤
m
{\displaystyle \exists m\in E/\forall x\in A,x\leq m}
Un tel élément s’appelle un majorant (resp : minorant ).
max
A
{\displaystyle \max A}
Si l’ensemble des majorants (
resp : minorants) de
A admet un plus petit élément (
resp : plus grand élément), celui-ci unique, s’appelle la
borne supérieure (
resp :
inférieure ) de
A .
Exercice
Soit
≤
{\displaystyle \leq }
E
{\displaystyle E}
≥
{\displaystyle \geq }
∀
x
,
y
∈
E
,
x
≥
y
⇔
y
≤
x
{\displaystyle \forall x,y\in E,\,x\geq y\Leftrightarrow y\leq x}
On s'intéresse ici à la compatibilité des applications avec les relations d'équivalence ou d'ordre.
Wikipedia-logo-v2.svg Soit
f
:
E
→
F
{\displaystyle f:E\rightarrow F}
∼
{\displaystyle \sim }
E
{\displaystyle E}
f
{\displaystyle f}
compatible avec
∼
{\displaystyle \sim }
∀
x
,
y
∈
E
(
x
∼
y
⇒
f
(
x
)
=
f
(
y
)
)
{\displaystyle \forall x,y\in E\quad \left(x\sim y\Rightarrow f(x)=f(y)\right)}
f
{\displaystyle f}
passe au quotient , c'est-à-dire qu'on peut définir une nouvelle application
f
~
:
E
/
∼→
F
,
x
¯
↦
f
(
x
)
{\displaystyle {\tilde {f}}:E/\sim \to F,\ {\overline {x}}\mapsto f(x)}
Exercices :
Étant donnée une application
f
:
E
→
F
{\displaystyle f:E\rightarrow F}
f
{\displaystyle f}
On considère la relation binaire sur
E
{\displaystyle E}
∀
x
,
x
′
∈
E
(
x
∼
x
′
⇔
f
(
x
)
=
f
(
x
′
)
)
{\displaystyle \forall x,x'\in E\quad \left(x\sim x'\Leftrightarrow f(x)=f(x')\right)}
Définition : application croissante ou décroissante
Soit
f
:
E
→
F
{\displaystyle f:E\rightarrow F}
une application et
<
,
≤
{\displaystyle <,\leq }
deux ordres sur
E
{\displaystyle E}
et
F
{\displaystyle F}
respectivement. On dit que
f
{\displaystyle f}
est
croissante (
resp. :
décroissante ) si :
∀
x
,
x
′
∈
E
(
x
<
x
′
⇒
f
(
x
)
≤
f
(
x
′
)
)
{\displaystyle \forall x,x'\in E\quad \left(x<x'\Rightarrow f(x)\leq f(x')\right)}
(
resp. :
∀
x
,
x
′
∈
E
(
x
′
<
x
⇒
f
(
x
)
≤
f
(
x
′
)
)
{\displaystyle \forall x,x'\in E\quad \left(x'<x\Rightarrow f(x)\leq f(x')\right)}
).
P
(
E
)
→
P
(
E
)
,
A
↦
A
c
{\displaystyle {\mathcal {P}}(E)\to {\mathcal {P}}(E),\ A\mapsto A^{c}}
Exercices :
Soit
Φ
:
P
(
E
)
→
P
(
E
)
{\displaystyle \Phi :{\mathcal {P}}(E)\rightarrow {\mathcal {P}}(E)}
Φ
{\displaystyle \Phi }
A
⊂
E
{\displaystyle A\subset E}
Φ
(
A
)
=
A
{\displaystyle \Phi (A)=A}
Soit
f
:
E
→
F
{\displaystyle f:E\rightarrow F}
g
:
F
→
E
{\displaystyle g:F\rightarrow E}
E
{\displaystyle E}
F
{\displaystyle F}
Wikipedia-logo-v2.svg Wikipedia-logo-v2.svg Indications :
Considérer
A
:=
{
A
⊂
E
∣
Φ
(
A
)
⊂
A
}
{\displaystyle {\mathcal {A}}:=\{A\subset E\mid \Phi (A)\subset A\}}
A
0
:=
⋂
A
∈
A
A
{\displaystyle A_{0}:=\bigcap _{A\in {\mathcal {A}}}A}
Faire un dessin et appliquer 1/, ou aller voir sur Wikipédia…
