Démonstrations de l'article "Ensembles et applications"

Enoncé:

Il n'existe qu'un seul ensemble vide.

Démonstration:

Soient E et F deux ensembles vides. Par définition, on a x , xE d'où x , (xExF) (en effet, la proposition PQ est vraie si P est toujours faux), donc EF. Par symétrie de rôles entre E et F, il vient FE, donc E=F.

Enoncé:

Soient E, F, G des ensembles.

On a les propriétés suivantes :

(EG et FG)(EF)G
(GE et GF)G(EF)
EFG\FG\E
EFE\GF\G
E=(EF)E\F

Démonstration:

Soit x(EF). Quitte à échanger les rôles de E et F, on peut supposer xE. Alors, comme EG, on a xG, CQFD.
Soit xG. Par hypothèse, GE et GF, donc xE et xF, c'est à dire xEF, CQFD.
Soit xG\F. Supposons par l'absurde que xG\E; comme xG\FG, on aurait alors xE, d'où xF, ce qui contredit l'hypothèse xG\F. Donc xG\E; CQFD.
Soit xE\G. Alors, d'une part xEF, donc xF; d'autre part xG; donc xF\G, CQFD.
Par définition, E\FE et EFE, donc (EF)E\FE. Réciproquement, soit xE; alors ou bien xF et x(EF), ou bien xF et xE\F, donc x(EF)E\F; d'où E(EF)E\F et E=(EF)E\F, CQFD.

Enoncé:

Soient E et F deux ensembles; alors l'ensemble EF est l'ensemble des éléments qui appartiennent à E ou à F, mais pas aux deux à la fois:
EF=(EF)\(EF)

Démonstration:

On a d'une part E(EF) donc E\F(EF)\F, d'autre part (EF)F donc (EF)\F(EF)\(EF); d'où E\F(EF)\(EF), de même pour F\E; donc EF(EF)\(EF).

Enoncé:

Soient E, F, G, H quatre ensembles, f une application de E vers F, g une application de F vers G, h une application de G vers H. On a (fog)oh=fo(goh).

Démonstration:

Soit x un élément de E.

On a ((fog)oh)(x)=(fog)(h(x))=f(g(h(x)))=f((goh)(x))=(fo(goh))(x).

Ce résultat est valable pour tout choix de x; il vient fo(goh)=(fog)oh

Enoncé:

Soient E et F deux ensembles et f une application de E dans F.

f est surjective si et seulement s'il existe une application g de F dans E telle que fog=Id_F. g est alors injective.
f est injective si et seulement s'il existe une fonction g de F dans E telle que gof=Id_E. g est alors surjective.
f est bijective si et seulement s'il existe une application g de F dans E telle que fog=Id_F et gof=Id_E. g est alors unique; elle est appelée application inverse (ou réciproque) de f et notée f^-1. g est alors également bijective, de réciproque f.

Démonstration:

Supposon d'abord f surjective.
Soit alors y un élément de F; y admet dans E un antécédent x par f; notons-le g(y). Alors on a par construction: yF , y=f(g(y))=(fog)(y) donc fog=Id_F.
Réciproquement, si g existe, alors yF , y=(fog)(y)=f(g(y))
Tout élément de F admet donc un antécédent par f, donc f est surjective.
Supposons maintenant f injective.
Soit alors y un élément de f(E). y admet dans x un unique antécédent par f; notons-le g(y). Alors on a:xE , (gof)(x)=g(f(x))=x donc gof=Id_E.
Réciproquement, supposons l'existence de g. Alors si x et x' sont deux éléments de E tels que f(x)=f(x'), on a x=(gof)(x)=g(f(x))=g(f(x'))=(gof)(x')=x' donc f est injective.
De plus, il découle des deux critères précédents que g est injective si et seulement s'il existe une fonction f de E dans F telle que fog=Id_F et g est injective si et seulement s'il existe une application f de E dans F telle que gof=Id_E, c'est à dire que g est injective si et seulement si f est surjective et g est surjective si et seulement si f est injective.
Il découle des deux énoncés précédents que f est bijective si et seulement s'il existe une application g de F dans E telle que fog=Id_F et gof=Id_E et que g est alors également bijective.
Supposons l'existence de g' vérifiant les mêmes conditions que g. On a alors:
yF , !xE , y=f(x) et g(y)=g(f(x))=(gof)(x)=x=(g'of)(x)=g'(f(x))=g'(y)
c'est-à-dire g=g'; on a donc prouvé l'unicité de g.
La bijectivité de g se prouve alors par symétrie des rôles de f et de g.

Enoncé:

Il existe une injection de E dans F si et seulement s'il existe une surjection de F dans E.

Démonstration:

Supposons l'existence d'une injection f de E dans F; alors on a prouvé qu'il existe une surjection g de F dans E, qui vérifie de plus gof=Id_E.
De même, s'il existe une surjection g de F dans E, alors il existe une injection f de E dans F, telle que fog=Id_F.

Enoncé:

#E#F#F#E

Démonstration:

#E#FIl existe une injection f de E dans FIl existe une surjection g de F dans E#F#E

Enoncé:

Soient E et F deux ensembles.
#E=#F(#E#F et #F#E)

Démonstration:

Enoncé:

Soit E un ensemble non vide; alors #E<#P(E).

Démonstration:

L'application f:EP(E),x{x} est injective, donc #E#P(E).
Supposons maintenant l'existence d'une bijection g de E sur P(E). Considérons alors le sous-ensemble A de P(E) défini par: A={xE;xg(x)}. g est bijective donc A admet un antécédent a. Deux cas se présentent alors: ou bien aA, et alors ag(a)=A, ce qui est impossible, ou bien aA, et alors ag(a)=A, ce qui est également impossible. On arrive donc à une contradiction, donc g n'existe pas, donc #E#F.

Enoncé:

Il n'existe pas d'ensemble contenant tous les ensembles.

Démonstration:

Supposons l'existence d'un tel ensemble et notons-le E.

Alors E contient tous les ensembles; en particulier E contient tous ses sous-ensembles. L'application f:P(E)E,XX est donc définie; elle est évidemment injective donc #P(E)#E, ce qui contredit le théorème de Cantor.

Enoncé:

Tout ensemble infini contient un sous-ensemble dénombrable.

Démonstration:

Nous allons construire par récurrence une injection f de N vers E.
Notons d'abord f(0) un élément quelconque de E. Considérons l'ensemble E₀=E\{f(0)}. L'ensemble E est infini, donc l'ensemble E₀ est non vide. Notons f(1) un élément quelconque de E₀.
Supposons maintenant avoir construit les images des entiers de 1 à n. Notons E_n=E\{f(1),f(2),...,f(n)}. L'ensemble E est infini par hypothèse, alors que {f(1),f(2),...,f(n)}est fini, donc l'ensemble E_n est non vide; notons f(n+1) un de ses éléments.

f est ainsi construite par récurrence; elle est injective par construction, donc l'application g de N dans f(N), définie par nN , g(n)=f(n), est une bijection de N sur f(N), qui est donc une partie dénombrable de E.

Enoncé:

Un ensemble infini E est dénombrable si et seulement si E est l'ensemble-image d'une suite.

Démonstration:

Supposons d'abord E dénombrable. Alors il existe une bijection f de N sur E. Notons nN , x_n=f(n). Alors {x_n;nN} est une suite, d'image E car f est bijective donc surjective.
Réciproquement, supposons que E soit l'image d'une suite {x_n;nN}.
La démonstration du théorème précédent nous donne l'existence d'une injection de N vers l'ensemble infini E.
D'autre part, notons pour tout élément e de E, N_e={n;e=x_n}, et notons g(e) un élément quelconque de N_e. L'application g de E vers N ainsi définie est injective par construction (en effet, si g(e)=g(e')=n, alors e=e'=x_n).
Il existe donc une injection f de N vers E et une injection g de E vers N; le théorème de Cantor-Bernstein nous dit que E et N sont alors en bijection, c'est à dire que E est dénombrable, CQFD.

Enoncé:

Soit (E,+) un magma. S'il existe dans E un élément neutre pour la loi +, alors cet élément est unique.

Démonstration:

Soient e et e' deux éléments neutres.
e est élément neutre donc e+e'=e'.
e' est élément neutre donc e+e'=e.
Donc e=e'.

Enoncé:

Soit (E,+) un magma dont la loi admet un élément neutre 0; soit x un élément de E.
Si x est inversible pour la loi +, et si la loi + est associative, alors l'inverse de x est défini de façon unique.

Démonstration:

Supposons x inversible et notons y et z deux inverses de x. La loi + étant associative et 0 étant élément neutre, on a:
z=0+z=(y+x)+z=y+(x+z)=y+0=y

Enoncé:

Soit (E,+) un magma dont la loi + est associative et admet un élément neutre 0. Alors tout élément inversible à droite (resp. à gauche) de E est régulier à droite (resp. à gauche).

Démonstration:

Soit x un élément de E inversible à droite et y un inverse à droite de x; soient u et v deux éléments quelconques de E. On a:
u+x=v+x(u+x)+y=(v+x)+yu+(x+y)=v+(x+y)u+0=v+0u=v
Soit x un élément de E inversible à gauche et z un inverse à gauche de x; soient u et v deux éléments quelconques de E. On a:
x+u=x+vz+(x+u)=z+(x+v)(z+x)+u=(z+x)+v0+u=0+vu=v

Enoncé:

Soit (E,~) un ensemble muni d'une relation d'équivalence. L'ensemble des classes d'équivalence forme une partition de l'ensemble E.

Démonstration:

xE , x~x donc xcl(x): les classes d'équivalence sont toutes non vides et tout élément de E appartient à une classe d'équivalence.
Supposons que deux classes d'équivalence cl(x) et cl(y) ne soient pas disjointes. Alors zcl(x)cl(y). C'est à dire que par définition des classes x~z et y~z. La relation ~ étant transitive, il vient tcl(x) , t~x donc t~z et t~y, d'où tcl(y) et cl(x)cl(y); par symétrie de rôles entre x et y, on a également cl(y)cl(x), d'où cl(y)=cl(x), CQFD.

Enoncé:

Considérons la relation binaire R sur E définie par (x,y)E² , xRyf(x)=f(y). C'est une relation d'équivalence.

Démonstration:

xE , f(x)=f(x) donc xRx; R est réflexive.
(x,y)E² , (f(x)=f(y)f(y)=f(x)) c'est à dire (xRyyRx); R est symétrique.
Soient x, y, z trois éléments de E avec xRy et yRz. C'est à dire f(x)=f(y) et f(y)=f(z), d'où f(x)=f(z) et xRz; R est transitive.

Enoncé:

L'application s:EE/R,xcl(x) est surjective.

Démonstration:

Soit yE/R. Par définition xE , y=cl(x), c'est à dire y=s(x).

Enoncé:

L'application b:E/Rf(E),y=cl(x)b(y)=f(x) est définie (c'est à dire qu'elle ne dépend pas du choix de x comme représentant de y); elle est de plus bijective.

Démonstration:

Par définition de R, si on se donne x et x' tels que cl(x)=cl(x'), alors f(x)=f(x'), donc l'application b est bien définie.
Soient y=cl(x) et y'=cl(x') deux éléments de E/R tels que b(y)=b(y'). Alors f(x)=f(x') par définition de b, c'est à dire xRx' et donc y=cl(x)=cl(x')=y'; b est injective.
Soit zf(E). Alors xE , z=f(x) et par définition de b, z=b(cl(x)); b est surjective.

Enoncé:

f=iobos

Démonstration:

Soit x un élément quelconque de E.

Par définition de b et de s, on a: f(x)=b(cl(x))=b(s(x))=(bos)(x).
De plus, f(x)f(E) donc f(x)=i(f(x))=i((bos)(x))=(iobos)(x).

Ce résultat est indépendant de x, donc f=iobos.