Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Exo7

Ensembles et applications
Vidéo

partie 1
...
Applications

Vidéo

partie 3
...
Ensembles finis

Vidéo

partie 5
...
Il reçut une lettre d’un tout
jeune mathématicien : « J’ai bien lu votre premier livre
...
Un tel ensemble ne peut exister
...
Tout le travail de Frege s’écroulait et il ne s’en remettra jamais
...
Il obtient le
prix Nobel de littérature en 1950
...
C’est très bref, mais difficile à appréhender
...
Considérons
F = E∈E |E∉E
...
Si non, alors par définition on met E dans
l’ensemble F
...
Et pourtant :
– Si F ∈ F alors par définition de F, F est l’un des ensembles E tel que F ∉ F
...

– Si F ∉ F alors F vérifie bien la propriété définissant F donc F ∈ F ! Encore contradictoire
...
On en déduit qu’il ne peut exister un tel ensemble E contenant tous
les ensembles
...
Qui rase le barbier ? » La seule réponse valable est qu’une telle
situation ne peut exister
...

Cependant il n’est pas possible dans ce cours de tout redéfinir
...

– l’ensemble des entiers relatifs Z = {
...

p
– l’ensemble des rationnels Q = q | p ∈ Z, q ∈ N \ {0}
...

– l’ensemble des nombres complexes C
...

Vous vous apercevrez assez rapidement que ce qui est au moins aussi important que les ensembles,
ce sont les relations entre ensembles : ce sera la notion d’application (ou fonction) entre deux
ensembles
...
Ensembles
1
...
Définir des ensembles
– On va définir informellement ce qu’est un ensemble : un ensemble est une collection d’éléments
...
} = N
...

– On note
x∈E
si x est un élément de E, et x ∉ E dans le cas contraire
...

– Exemples :
x ∈ R | | x − 2| < 1 ,

z ∈ C | z5 = 1 ,

x∈R|0

x

1 = [0, 1]
...
2
...
E ⊂ F si tout élément de E est aussi un élément de F (autrement dit : ∀ x ∈
E (x ∈ F))
...

– L’égalité
...

– Ensemble des parties de E
...
Par exemple si
E = {1, 2, 3} :
P ({1, 2, 3}) = ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
...
Si A ⊂ E,
EA =

x∈E|x∉ A

On le note aussi E \ A et juste A s’il n’y a pas d’ambiguïté (et parfois aussi A c ou A)
...
Pour A, B ⊂ E,
A ∪ B = x ∈ E | x ∈ A ou x ∈ B
Le «ou» n’est pas exclusif : x peut appartenir à A et à B en même temps
...

A ∩ B = x ∈ E | x ∈ A et x ∈ B

B

A∩B

A

1
...
Règles de calculs
Soient A, B, C des parties d’un ensemble E
...


Voici les dessins pour les deux dernières assertions
...

– Preuve de (A ∩ B) = A ∪ B : x ∈ (A ∩ B) ⇐⇒ x ∉ (A ∩ B) ⇐⇒ non x ∈ A ∩ B ⇐⇒ non x ∈
A et x ∈ B ⇐⇒ non(x ∈ A) ou non(x ∈ B) ⇐⇒ x ∉ A ou x ∉ B ⇐⇒ x ∈ A ∪ B
...


1
...
Produit cartésien
Soient E et F deux ensembles
...

Exemple 1

1
...

2
...
[0, 1] × [0, 1] × [0, 1] = (x, y, z) | 0

1

x, y, z

1

y
z

1
1
0

1

x

Mini-exercices
1
...

2
...

3
...

4
...

5
...


2
...
1
...

Nous représenterons les applications par deux types d’illustrations : les ensembles «patates»,
l’ensemble de départ (et celui d’arrivée) est schématisé par un ovale ses éléments par des
points
...

f
x

f (x)

E

F

L’autre représentation est celle des fonctions continues de R dans R (ou des sous-ensembles
de R)
...
L’association x → f (x) est représentée par le point (x, f (x))
...
Deux applications f , g : E → F sont égales si et seulement si pour tout x ∈ E, f (x) =
g(x)
...

– Le graphe de f : E → F est

Γf =

x, f (x) ∈ E × F | x ∈ E
y

Γf
x

– Composition
...

g
f
E −−−−→ F −−−−→ G
g◦ f
Exemple 2

1
...

2
...


6
Alors g ◦ f : ]0, +∞[→ R vérifie pour tout x ∈]0, +∞[ :
g ◦ f (x) = g f (x) = g

1
=
x

1
x
1
x

−1
+1

=

1− x
= − g(x)
...
2
...

Définition 1
Soit A ⊂ E et f : E → F, l’image directe de A par f est l’ensemble
f (A) = f (x) | x ∈ A

y

f
F

E

f (A)

A

f (A)
x
A

Définition 2
Soit B ⊂ F et f : E → F, l’image réciproque de B par f est l’ensemble
f −1 (B) = x ∈ E | f (x) ∈ B

f
F

E

B

y

B
x

f −1 (B)

f −1 (B)

Remarque
Ces notions sont plus difficiles à maîtriser qu’il n’y paraît !
– f (A) est un sous-ensemble de F, f −1 (B) est un sous-ensemble de E
...
L’image réciproque existe quelque soit la fonction
...
Par contre l’image réciproque d’un singleton f −1 { y} dépend de f
...


2
...
Antécédents
Fixons y ∈ F
...

En termes d’image réciproque l’ensemble des antécédents de y est f −1 ({ y})
...
Ce sont x1 , x2 , x3
...
Pour deux applications f , g : E → F, quelle est la négation de f = g ?
2
...


3
...
Calculer f ◦ (g ◦ h)
et ( f ◦ g) ◦ h
...
Pour la fonction f : R → R définie par x → x2 représenter et calculer les ensembles
suivants : f ([0, 1[), f (R), f (] − 1, 2[), f −1 ([1, 2[), f −1 ([−1, 1]), f −1 ({3}), f −1 (R \ N)
...
Injection, surjection, bijection
3
...
Injection, surjection
Soit E, F deux ensembles et f : E → F une application
...
Autrement dit :
∀ x, x ∈ E

f (x) = f (x ) =⇒ x = x

Définition 4
f est surjective si pour tout y ∈ F, il existe x ∈ E tel que y = f (x)
...

Les applications f représentées sont injectives :
y

f

)
E

F

F
x
E

Les applications f représentées sont surjectives :

8
f

y

E

F

F

x
E

Remarque
Encore une fois ce sont des notions difficiles à appréhender
...

– f est injective si et seulement si tout élément y de F a au plus 1 antécédent (et éventuellement aucun)
...

Remarque
Voici deux fonctions non injectives :
f
y

E

F
x

x

y

y
x
x

x

Ainsi que deux fonctions non surjectives :
y

f

F
y
E

)

F
x
E

Exemple 3

1
1
...
Montrons que f 1 est injective : soit x, x ∈ N tels
1
1
que f 1 (x) = f 1 (x )
...
Ainsi f 1 est injective
...
Il s’agit de trouver un élément y qui n’a pas d’antécédent par f 1
...
Ainsi f 1 n’est pas surjective
...
Soit f 2 : Z → N définie par f 2 (x) = x2
...
En effet on peut trouver
deux éléments x, x ∈ Z différents tels que f 2 (x) = f 2 (x )
...

f 2 n’est pas non plus surjective, en effet il existe des éléments y ∈ N qui n’ont aucun

9
antécédent
...
Mais alors x n’est pas un entier de Z
...


3
...
Bijection
Définition 5
f est bijective si elle injective et surjective
...
Autrement dit :
∀y ∈ F

∃!x ∈ E

y = f (x)

L’existence du x vient de la surjectivité et l’unicité de l’injectivité
...

y

f

E

F

F

x
E

Proposition 1
Soit E, F des ensembles et f : E → F une application
...
L’application f est bijective si et seulement si il existe une application g : F → E telle
que f ◦ g = idF et g ◦ f = idE
...
Si f est bijective alors l’application g est unique et elle aussi est bijective
...
De plus f −1
= f
...


∀x ∈ E

g f (x) = x
...
Nous avons bien exp ln(y) = y, pour tout
y ∈]0, +∞[ et ln exp(x) = x, pour tout x ∈ R
...
– Sens ⇒
...
Nous allons construire une application g : F → E
...

On a f g( y) = f ( x) = y, ceci pour tout y ∈ F et donc f ◦ g = idF
...
Alors pour tout x ∈ E on a f g ◦ f ( x) = f ( x) or f est injective et donc

10
g ◦ f ( x) = x
...
Bilan : f ◦ g = idF et g ◦ f = idE
...
Supposons que g existe et montrons que f est bijective
...

– f est injective : soient x, x ∈ E tels que f ( x) = f ( x )
...

2
...
Ainsi g−1 = f
...


Proposition 2
Soient f : E → F et g : F → G des applications bijectives
...
Il existe aussi v : G → F
tel que v ◦ g = idF et g ◦ v = idG
...
Et
( u ◦ v) ◦ ( g ◦ f ) = u ◦ (v ◦ g) ◦ f = u ◦ idF ◦ f = u ◦ f = idE
...

Comme u est la bijection réciproque de f et v celle de g alors : u ◦ v = f −1 ◦ g−1
...
Les fonctions suivantes sont-elles injectives, surjectives, bijectives ?
– f 1 : R → [0, +∞[, x → x2
...

– f 3 : N → N, x → x 2
...

– f 5 : R → [0, +∞[, x → | x|
...
Montrer que la fonction f : ]1, +∞[→]0, +∞[ définie par f (x) =
sa bijection réciproque
...
Ensembles finis
4
...
Cardinal

1
x−1

est bijective
...
, n}
...

Quelques exemples :
1
...

2
...

3
...

Enfin quelques propriétés :
1
...


2
...

3
...

4
...
2
...

1
...
Si f est surjective alors Card E

Card F
...


3
...


Démonstration

1
...
Notons F = f (E ) ⊂ F alors la restriction f | : E → F (définie par f | ( x) =
f ( x)) est une bijection
...

Donc E et F ont le même nombre d’éléments
...
Or F ⊂ F , ainsi Card E =
Card F Card F
...
Supposons f surjective
...

3
...


12

Proposition 4
Soit E, F deux ensembles finis et f : E → F une application
...
f est injective,
ii
...
f est bijective
...

– ( i ) =⇒ ( ii )
...
Alors Card f (E ) = Card E = Card F
...

– ( ii ) =⇒ ( iii )
...
Pour montrer que f est bijective, il reste à montrer que f
est injective
...
Alors Card f (E ) < Card E
(car au moins 2 éléments ont la même image)
...

C’est une contradiction, donc f doit être injective et ainsi f est bijective
...
C’est clair : une fonction bijective est en particulier injective
...


Malgré sa formulation amusante, c’est une proposition souvent utile
...
3
...
On note Card E = n et Card F = p
...


13

Exemple 4
En particulier le nombre d’applications de E dans lui-même est n n
...

Démonstration
Fixons F et p = Card F
...
Soit (P n ) l’assertion
suivante : le nombre d’applications d’un ensemble à n éléments vers un ensemble à p éléments est p n
...
Pour n = 1, une application de E dans F est définie par l’image de l’unique élément
de E
...
Ainsi P1 est vraie
...
Fixons n 1 et supposons que P n est vraie
...
On
choisit et fixe a ∈ E ; soit alors E = E \ {a} qui a bien n éléments
...
Pour chaque application f : E → F on peut la
prolonger en une application f : E → F en choisissant l’image de a
...
Ainsi P n+1 est vérifiée
...
Par le principe de récurrence P n est vraie, pour tout n 1
...

Démonstration
Supposons E = {a 1 , a 2 ,
...
Une fois ce choix fait, pour
l’image de a 2 il reste p − 1 choix (car a 2 ne doit pas avoir la même image que a 1 )
...
Ainsi de suite : pour l’image de a k il y p − ( k − 1) choix
...


Notation factorielle : n! = 1 × 2 × 3 × · · · × n
...

Proposition 8
Le nombre de bijections d’un ensemble E de cardinal n dans lui-même est :
n!

Exemple 5
Parmi les 3125 applications de {1, 2, 3, 4, 5} dans lui-même il y en a 5! = 120 qui sont bijectives
...
Soit (P n ) l’assertion suivante : le nombre de bijections
d’un ensemble à n éléments dans un ensemble à n éléments est n!
– P1 est vraie
...

– Fixons n 1 et supposons que P n est vraie
...
On fixe a ∈ E
...
Chaque application se prolonge en une bijection de E → F en posant a → b
...

Ainsi P n+1 est vraie
...


4
...
Nombres de sous-ensembles
Soit E un ensemble fini de cardinal n
...
C’est un bon exercice de les énumérer :
– l’ensemble vide : ∅,
– 5 singletons : {1}, {2},
...
, {2, 3},
...
,
– 5 ensembles à 4 éléments : {1, 2, 3, 4}, {1, 2, 3, 5},
...

Démonstration
Encore une récurrence sur n = Card E
...

– Supposons que la proposition soit vraie pour n 1 fixé
...
On
fixe a ∈ E
...
Par
l’hypothèse de récurrence il y en a 2n
...

Par l’hypothèse de récurrence il y a 2n sous-ensembles A possibles et donc aussi 2n sousensembles A
...

– Par le principe de récurrence, nous avons prouvé que si Card E = n alors Card P (E ) = 2n
...
5
...


Exemple 7
Les parties à deux éléments de {1, 2, 3} sont {1, 2}, {1, 3} et {2, 3} et donc
déjà classé les parties de {1, 2, 3, 4, 5} par nombre d’éléments et donc
– 5 = 1 (la seule partie n’ayant aucun élément est l’ensemble vide),
0
– 5 = 5 (il y a 5 singletons),
1
– 5 = 10 (il y a 10 paires),
2
– 5 = 10,
3

3
2

= 3
...


Sans calculs on peut déjà remarquer les faits suivants :
Proposition 10
–

n
0

= 1,

n
1

= n,

n
n

n
k

–

n
n− k

=

n
k

–

n
0

n
1

+···+

= 1
...
Par exemple :

n
1

= n car il y a n singletons
...
Compter le nombre de parties A ⊂ E ayant k éléments revient aussi à compter le nombre de
n
parties de la forme A (qui ont donc n − k éléments), ainsi n−k = n
...
La formule n + n + · · · + n + · · · + n = 2n exprime que faire la somme du nombre de parties à
0
1
k
n
k éléments, pour k = 0,
...


16

Proposition 11
n
n−1
n−1
=
+
k
k
k−1

0
Démonstration
Soit E un ensemble à n éléments, a ∈ E et E = E \ {a}
...
Il y a en a donc n−1 ,
k
– celles qui contiennent a : elles sont de la forme A = {a} ∪ A avec A une partie à k − 1 éléments
−1
dans E qui a n − 1 éléments
...

k
−1
Bilan : n = n−1 + n−1
...
La ligne du haut corresk
pond à 0 , la ligne suivante à 1 et 1 , la ligne d’après à 2 , 2 et 2
...
,


...

1
1
1

1

1
2

3

1
4

1
1
1
3

6

1
1

4

1
1

2
3

1
1

1
3

6

4
5

1

10

1
4

10

1
5

1

Ce qui fait que cela fonctionne c’est bien sûr la proposition 11 qui se représente ainsi :
n−1
k−1

n−1
k
n
k

Une autre façon de calculer le coefficient du binôme de Newton repose sur la formule suivante :

17

Proposition 12

n
n!
=
k!(n − k)!
k

Démonstration
Cela se fait par récurrence sur n
...
Si c’est vrai au rang n − 1 alors écrivons
n
n−1
n−1
−1
et utilisons l’hypothèse de récurrence pour n−1 et n−1
...
6
...

Exemple 8

1
...

2
...

3
...


Démonstration
Nous allons effectuer une récurrence sur n
...
Pour n = 1, (a + b)1 = 1 a1 b0 + 1 a0 b1
...

0
1

n
k

a n− k · b k
...
Fixons n

2 et supposons que P n−1 est vraie
...

– Conclusion
...


Mini-exercices
1
...
Combien y a-t-il d’applications surjectives d’un ensemble à n + 1 éléments dans un
ensemble à n éléments ?
3
...

4
...

5
...

6
...


5
...
1
...

Nous schématisons une relation ainsi : les éléments de E sont des points, une flèche de x vers y
signifie que x est en relation avec y, c’est-à-dire que l’on associe «Vrai» au couple (x, y)
...
2
...

1
...

– réflexivité : une droite est parallèle à elle-même,
– symétrie : si D est parallèle à D alors D est parallèle à D,
– transitivité : si D parallèle à D et D parallèle à D alors D est parallèle à D
...
La relation «être du même âge» est une relation d’équivalence
...
La relation «être perpendiculaire» n’est pas une relation d’équivalence (ni la réflexivité,
ni la transitivité ne sont vérifiées)
...
La relation (sur E = R par exemple) n’est pas une relation d’équivalence (la symétrie
n’est pas vérifiée)
...
3
...
Soit x ∈ E, la classe d’équivalence de
x est
cl(x) = y ∈ E | yR x

x

cl(x)
x
cl(x )

cl(x) est donc un sous-ensemble de E, on le note aussi x
...

Soit E un ensemble et R une relation d’équivalence
...
cl(x) = cl(y) ⇐⇒ xR y
...
Pour tout x, y ∈ E, cl(x) = cl(y) ou cl(x) ∩ cl(y) = ∅
...
Soit C un ensemble de représentants de toutes les classes alors cl(x) | x ∈ C constitue
une partition de E
...



...


...
Pour la relation «être du même âge», la classe d’équivalence d’une personne est l’ensemble
des personnes ayant le même âge
...
Les trois assertions de la proposition
se lisent ainsi :
– On est dans la même classe d’équivalence si et seulement si on est du même âge
...

– Si on choisit une personne de chaque âge possible, cela forme un ensemble de représentants
C
...


21
2
...
À chaque classe d’équivalence correspond une et une seule direction
...

Tout d’abord R est une relation d’équivalence :
– R est réflexive : pour tout (p, q) on a bien pq = pq et donc (p, q)R (p, q)
...

– R est transitive : pour tout (p, q), (p , q ), (p , q ) tels que (p, q)R (p , q ) et (p , q )R (p , q )
on a donc pq = p q et p q = p q
...
En divisant par q = 0 on obtient pq = q p et donc (p, q)R (p , q )
...
Par exemple,
comme (2, 3)R (4, 6) (car 2 × 6 = 3 × 4) alors les classes de (2, 3) et (4, 6) sont égales : avec notre
2
notation cela s’écrit : 3 = 4
...

4
Les nombres 2 = 6 sont bien égaux (ce sont les mêmes classes) mais les écritures sont diffé3
rentes (les représentants sont distincts)
...
4
...
Définissons la relation suivante sur l’ensemble E = Z :
a ≡ b (mod n)

⇐⇒

a − b est un multiple de n

Exemples pour n = 7 : 10 ≡ 3 (mod 7), 19 ≡ 5 (mod 7), 77 ≡ 0 (mod 7), −1 ≡ 20 (mod 7)
...

– Pour a, b ∈ Z tels que a ≡ b (mod n) alors a − b est un multiple de n, autrement dit il existe
k ∈ Z tel que a − b = kn et donc b − a = (− k)n et ainsi b ≡ a (mod n)
...

Alors a − c = (a − b) + (b − c) = (k + k )n et donc a ≡ c (mod n)
...
Par définition nous avons donc
a = cl(a) = b ∈ Z | b ≡ a (mod n)
...

Comme n ≡ 0 (mod n), n + 1 ≡ 1 (mod n),
...


et donc l’ensemble des classes d’équivalence est l’ensemble

22
Z/nZ = 0, 1, 2,
...

Par exemple : pour n = 7, 0 = {
...
} = 7Z ; 1 = {
...
} = 1 + 7Z ;

...
, −8, −1, 6, 13, 20,
...
Mais ensuite 7 = {
...
} = 0 = 7Z
...
, 6 possède 7 éléments
...
Par
exemple pour l’heure : les minutes et les secondes sont modulo 60 (après 59 minutes on
repart à zéro), les heures modulo 24 (ou modulo 12 sur le cadran à aiguilles)
...


Mini-exercices
1
...
Montrer qu’il y a 3 classes d’équivalence
...
Dans R2 montrer que la relation définie par (x, y)R (x , y ) ⇐⇒ x + y = x + y est une
relation d’équivalence
...

3
...
Calculer la table d’addition dans Z/6Z
(c’est-à-dire toutes les sommes p + q pour p, q ∈ Z/6Z)
...
Mêmes questions avec Z/5Z, puis Z/8Z

---

Title: MATHE ALGEBRA
Description: KEEP IN MIND MATH

Buy These NotesPreview