À la découverte de l’algèbre

2

3

123

Vecteurs de (cid:82)n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

Exemples dapplications lin aires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

Propri t s des applications lin aires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

Espaces vectoriels

1

2

3

4

5

6

7

8

137

Espace vectoriel (d but) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

Espace vectoriel (n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

Sous-espace vectoriel (d but) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

Sous-espace vectoriel (milieu) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

Sous-espace vectoriel (n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

Application lin aire (d but) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

Application lin aire (milieu) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

Application lin aire (n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

11 Dimension nie

167

Famille libre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

Famille g n ratrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

Dimension dun espace vectoriel

Dimension des sous-espaces vectoriels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

12 Matrices et applications lin aires

187

Rang dune famille de vecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

Applications lin aires en dimension nie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

Matrice dune application lin aire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

Changement de bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

1

2

3

4

5

1

2

3

4

13 D terminants

211

D terminant en dimension 2 et 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

D nition du d terminant

Propri t s du d terminant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

Calculs de d terminants

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224

Applications des d terminants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

1

2

3

4

5

Index

Logique et

raisonnements

Chapitre

1

Vid o (cid:132) partie 1. Logique

Vid o (cid:132) partie 2. Raisonnements

Fiche dexercices (cid:135) Logique, ensembles, raisonnements

Quelques motivations

" Il est important davoir un langage rigoureux. La langue fran aise est souvent ambig e. Prenons

lexemple de la conjonction ou ; au restaurant fromage ou dessert signie lun ou lautre mais pas

les deux. Par contre si dans un jeu de carte on cherche les as ou les cSurs alors il ne faut pas exclure

las de cSur. Autre exemple : que r pondre la question As-tu 10 euros en poche ? si lon dispose de

15 euros ?

" Il y a des notions difciles expliquer avec des mots : par exemple la continuit dune fonction est

souvent expliqu e par on trace le graphe sans lever le crayon . Il est clair que cest une d nition peu

satisfaisante. Voici la d nition math matique de la continuit dune fonction f : I (cid:82) en un point

x0

I :

| < = | f (x) f (x0

Cest le but de ce chapitre de rendre cette ligne plus claire ! Cest la logique.

> 0 > 0 x I

(|x x0

)| < ).

" Enn les math matiques tentent de distinguer le vrai du faux. Par exemple Est-ce quune augmentation

de 20%, puis de 30% est plus int ressante quune augmentation de 50% ? . Vous pouvez penser oui

ou non , mais pour en tre s r il faut suivre une d marche logique qui m ne la conclusion. Cette

d marche doit tre convaincante pour vous mais aussi pour les autres. On parle de raisonnement.

Les math matiques sont un langage pour sexprimer rigoureusement, adapt aux ph nom nes complexes,

qui rend les calculs exacts et v riables. Le raisonnement est le moyen de valider ou dinrmer une

hypoth se et de lexpliquer autrui.

LOGIQUE ET RAISONNEMENTS

1. LOGIQUE 2

1. Logique

1.1. Assertions

Une assertion est une phrase soit vraie, soit fausse, pas les deux en m me temps.

Exemples :

" Il pleut.

" Je suis plus grand que toi.

" 2 + 2 = 4

" 2 3 = 7

" Pour tout x (cid:82), on a x 2 (cid:62) 0.

" Pour tout z (cid:67), on a |z| = 1.

Si P est une assertion et Q est une autre assertion, nous allons d nir de nouvelles assertions construites

partir de P et de Q.

Lop rateur logique et

Lassertion P et Q est vraie si P est vraie et Q est vraie. Lassertion P et Q est fausse sinon.

On r sume ceci en une table de v rit :

P \ Q V F

V F

F

F

V

F

F I G U R E 1.1 Table de v rit de P et Q

Par exemple si P est lassertion Cette carte est un as et Q lassertion Cette carte est cSur alors lassertion

P et Q est vraie si la carte est las de cSur et est fausse pour toute autre carte.

Lop rateur logique ou

Lassertion P ou Q est vraie si lune (au moins) des deux assertions P ou Q est vraie. Lassertion P ou

Q est fausse si les deux assertions P et Q sont fausses.

On reprend ceci dans la table de v rit :

P \ Q V

F

V V

F

V

V

F

F I G U R E 1.2 Table de v rit de P ou Q

Si P est lassertion Cette carte est un as et Q lassertion Cette carte est cSur alors lassertion P ou Q

est vraie si la carte est un as ou bien un cSur (en particulier elle est vraie pour las de cSur).

Remarque.

Pour d nir les op rateurs ou , et on fait appel une phrase en fran ais utilisant les mots ou, et ! Les

tables de v rit s permettent d viter ce probl me.

La n gation non

Lassertion non P est vraie si P est fausse, et fausse si P est vraie.

LOGIQUE ET RAISONNEMENTS

1. LOGIQUE 3

P

non P

V

F

F

V

F I G U R E 1.3 Table de v rit de non P

Limplication =

La d nition math matique est la suivante :

Lassertion (non P) ou Q est not e P = Q .

Sa table de v rit est donc la suivante :

P \ Q V

F

V

F

V V

V

F

F I G U R E 1.4 Table de v rit de P = Q

Lassertion P = Q se lit en fran ais P implique Q .

Elle se lit souvent aussi si P est vraie alors Q est vraie ou si P alors Q .

Par exemple :

" 0 (cid:54) x (cid:54) 25 =

" x ] , 4[ = x 2 + 3x 4 > 0 est vraie ( tudier le bin me).

" sin( ) = 0 = = 0 est fausse (regarder pour = 2 par exemple).

" 2 + 2 = 5 =

x (cid:54) 5 est vraie (prendre la racine carr e).

(cid:112)

(cid:112)

2 = 2 est vraie ! Eh oui, si P est fausse alors lassertion P = Q est toujours

vraie.

L quivalence

L quivalence est d nie par :

P Q est lassertion (P = Q) et (Q = P) .

On dira P est quivalent Q ou P quivaut Q ou P si et seulement si Q . Cette assertion est vraie

lorsque P et Q sont vraies ou lorsque P et Q sont fausses. La table de v rit est :

P \ Q V

V

F

V

F

F

F

V

F I G U R E 1.5 Table de v rit de P Q

Exemples :

" Pour x, x (cid:48) (cid:82), l quivalence x x (cid:48) = 0 (x = 0 ou x (cid:48) = 0) est vraie.

" Voici une quivalence toujours fausse (quelque soit lassertion P) : P non(P) .

On sint resse davantage aux assertions vraies quaux fausses, aussi dans la pratique et en dehors de ce

chapitre on crira P Q ou P = Q uniquement lorsque ce sont des assertions vraies. Par

exemple si lon crit P Q cela sous-entend P Q est vraie . Attention rien ne dit que P et Q

soient vraies. Cela signie que P et Q sont vraies en m me temps ou fausses en m me temps.

LOGIQUE ET RAISONNEMENTS

1. LOGIQUE 4

Proposition 1.

Soient P, Q, R trois assertions. Nous avons les quivalences (vraies) suivantes :

1. P non(non(P))

2. (P et Q) (Q et P)

3. (P ou Q) (Q ou P)

4. non(P et Q) (non P) ou (non Q)

5. non(P ou Q) (non P) et (non Q)

6. (cid:0)P et (Q ou R)(cid:1) (P et Q) ou (P et R)

7. (cid:0)P ou (Q et R)(cid:1) (P ou Q) et (P ou R)

8. P = Q non(Q) = non(P)

D monstration. Voici des exemples de d monstrations :

4. Il suft de comparer les deux assertions non(P et Q) et (non P) ou (non Q) pour toutes les valeurs

possibles de P et Q. Par exemple si P est vrai et Q est vrai alors P et Q est vrai donc non(P et Q)

est faux ; dautre part (non P) est faux, (non Q) est faux donc (non P) ou (non Q) est faux. Ainsi dans

ce premier cas les assertions sont toutes les deux fausses. On dresse ainsi les deux tables de v rit s et

comme elles sont gales les deux assertions sont quivalentes.

P \ Q V

F

V

F

V V

V

F

F I G U R E 1.6 Tables de v rit de non(P et Q) et de (non P) ou (non Q)

6. On fait la m me chose mais il y a trois variables : P, Q, R. On compare donc les tables de v rit dabord

dans le cas o P est vrai ( gauche), puis dans le cas o P est faux ( droite). Dans les deux cas les deux

assertions (cid:0)P et (Q ou R)(cid:1) et (P et Q) ou (P et R) ont la m me table de v rit donc les assertions

sont quivalentes.

Q \ R V

F

V V

F

V

V

F

Q \ R V F

F

F

V

F

F

F

8. Par d nition, limplication P = Q est lassertion (non P) ou Q . Donc limplication non(Q) =

non(P) est quivalente non(non(Q)) ou non(P) qui quivaut encore Q ou non(P) et donc est

quivalente P = Q . On aurait aussi pu encore une fois dresser les deux tables de v rit et voir

quelles sont gales.

1.2. Quanticateurs

Le quanticateur : pour tout

Une assertion P peut d pendre dun param tre x, par exemple x 2 (cid:62) 1 , lassertion P(x) est vraie ou

fausse selon la valeur de x.

Lassertion

est une assertion vraie lorsque les assertions P(x) sont vraies pour tous les l ments x de lensemble E.

x E

P(x)

LOGIQUE ET RAISONNEMENTS

1. LOGIQUE 5

On lit Pour tout x appartenant E, P(x) , sous-entendu Pour tout x appartenant E, P(x) est vraie .

Par exemple :

" x [1, +[

" x (cid:82) (x 2 (cid:62) 1) est une assertion fausse.

" n (cid:78) n(n + 1) est divisible par 2 est vraie.

(x 2 (cid:62) 1) est une assertion vraie.

Le quanticateur : il existe

Lassertion

x E

P(x)

est une assertion vraie lorsque lon peut trouver au moins un x de E pour lequel P(x) est vraie. On lit il

existe x appartenant E tel que P(x) (soit vraie) .

Par exemple :

" x (cid:82) (x(x 1) < 0) est vraie (par exemple x = 1

" n (cid:78) n2 n > n est vraie (il y a plein de choix, par exemple n = 3 convient, mais aussi n = 10 ou

2 v rie bien la propri t ).

m me n = 100, un seul suft pour dire que lassertion est vraie).

" x (cid:82) (x 2 = 1) est fausse (aucun r el au carr ne donnera un nombre n gatif).

La n gation des quanticateurs

La n gation de x E

P(x) est x E non P(x) .

Par exemple la n gation de x [1, +[

effet la n gation de x 2 (cid:62) 1 est non(x 2 (cid:62) 1) mais s crit plus simplement x 2 < 1.

(x 2 (cid:62) 1) est lassertion x [1, +[

(x 2 < 1) . En

La n gation de x E

P(x) est x E non P(x) .

Voici des exemples :

" La n gation de z (cid:67) (z2 + z + 1 = 0) est z (cid:67) (z2 + z + 1 (cid:54)= 0) .

" La n gation de x (cid:82) (x + 1 (cid:90)) est x (cid:82) (x + 1 / (cid:90)) .

" Ce nest pas plus difcile d crire la n gation de phrases complexes. Pour lassertion :

sa n gation est

Remarques

x (cid:82) y > 0 (x + y > 10)

x (cid:82) y > 0 (x + y (cid:54) 10).

Lordre des quanticateurs est tr s important. Par exemple les deux phrases logiques

x (cid:82) y (cid:82) (x + y > 0)

et

y (cid:82) x (cid:82) (x + y > 0).

sont diff rentes. La premi re est vraie, la seconde est fausse. En effet une phrase logique se lit de gauche

droite, ainsi la premi re phrase afrme Pour tout r el x, il existe un r el y (qui peut donc d pendre de x)

tel que x + y > 0. (par exemple on peut prendre y = |x| + 1). Cest donc une phrase vraie. Par contre la

deuxi me se lit : Il existe un r el y, tel que pour tout r el x, x + y > 0. Cette phrase est fausse, cela ne

peut pas tre le m me y qui convient pour tous les x !

On retrouve la m me diff rence dans les phrases en fran ais suivantes. Voici une phrase vraie Pour toute

personne, il existe un num ro de t l phone , bien s r le num ro d pend de la personne. Par contre cette

phrase est fausse : Il existe un num ro, pour toutes les personnes . Ce serait le m me num ro pour tout le

monde !

LOGIQUE ET RAISONNEMENTS

2. RAISONNEMENTS 6

Terminons avec dautres remarques.

" Quand on crit x (cid:82) ( f (x) = 0) cela signie juste quil existe un r el pour lequel f sannule. Rien

ne dit que ce x est unique. Dans un premier temps vous pouvez lire la phrase ainsi : il existe au moins

un r el x tel que f (x) = 0 . An de pr ciser que f sannule en une unique valeur, on rajoute un point

dexclamation :

! x (cid:82) ( f (x) = 0).

" Pour la n gation dune phrase logique, il nest pas n cessaire de savoir si la phrase est fausse ou vraie.

Le proc d est algorithmique : on change le pour tout en il existe et inversement, puis on prend la

n gation de lassertion P.

" Pour la n gation dune proposition, il faut tre pr cis : la n gation de lin galit stricte < est lin galit

large (cid:62) , et inversement.

" Les quanticateurs ne sont pas des abr viations. Soit vous crivez une phrase en fran ais : Pour tout

r el x, si f (x) = 1 alors x (cid:62) 0. , soit vous crivez la phrase logique :

x (cid:82) ( f (x) = 1 = x (cid:62) 0).

Mais surtout n crivez pas x r el, si f (x) = 1 = x positif ou nul . Enn, pour passer dune ligne

lautre dun raisonnement, pr f rez plut t donc = .

" Il est d fendu d crire (cid:54), (cid:54)= . Ces symboles nexistent pas !

Mini-exercices.

1. crire la table de v rit du ou exclusif . (Cest le ou dans la phrase fromage ou dessert , lun ou

lautre mais pas les deux.)

2. crire la table de v rit de non (P et Q) . Que remarquez vous ?

3. crire la n gation de P = Q .

4. D montrer les assertions restantes de la proposition 1.

5. crire la n gation de (cid:0)P et (Q ou R)(cid:1) .

6. crire laide des quanticateurs la phrase suivante : Pour tout nombre r el, son carr est positif .

Puis crire la n gation.

7. M mes questions avec les phrases : Pour chaque r el, je peux trouver un entier relatif tel que leur

produit soit strictement plus grand que 1 . Puis Pour tout entier n, il existe un unique r el x tel que

exp(x) gale n .

2. Raisonnements

Voici des m thodes classiques de raisonnements.

2.1. Raisonnement direct

On veut montrer que lassertion P = Q est vraie. On suppose que P est vraie et on montre qualors Q

est vraie. Cest la m thode laquelle vous tes le plus habitu .

Exemple 1.

Montrer que si a, b (cid:81) alors a + b (cid:81).

D monstration. Prenons a (cid:81), b (cid:81). Rappelons que les rationnels (cid:81) sont lensemble des r els s crivant

q avec p (cid:90) et q (cid:78).

p

LOGIQUE ET RAISONNEMENTS

2. RAISONNEMENTS 7

Alors a = p

q pour un certain p (cid:90) et un certain q (cid:78). De m me b = p(cid:48)

q(cid:48) avec p(cid:48) (cid:90) et q(cid:48) (cid:78). Maintenant

+ p(cid:48)

q(cid:48)

Or le num rateur pq(cid:48) + qp(cid:48) est bien un l ment de (cid:90) ; le d nominateur qq(cid:48) est lui un l ment de (cid:78). Donc

a + b s crit bien de la forme a + b = p(cid:48)(cid:48)

q(cid:48)(cid:48) avec p(cid:48)(cid:48) (cid:90), q(cid:48)(cid:48) (cid:78). Ainsi a + b (cid:81).

= pq(cid:48) + qp(cid:48)

qq(cid:48)

a + b = p

q

.

2.2. Cas par cas

Si lon souhaite v rier une assertion P(x) pour tous les x dans un ensemble E, on montre lassertion pour

les x dans une partie A de E, puis pour les x nappartenant pas A. Cest la m thode de disjonction ou du

cas par cas.

Exemple 2.

Montrer que pour tout x (cid:82), |x 1| (cid:54) x 2 x + 1.

D monstration. Soit x (cid:82). Nous distinguons deux cas.

Premier cas : x (cid:62) 1. Alors |x 1| = x 1. Calculons alors x 2 x + 1 |x 1|.

x 2 x + 1 |x 1| = x 2 x + 1 (x 1)

= x 2 2x + 2

= (x 1)2 + 1 (cid:62) 0.

Ainsi x 2 x + 1 |x 1| (cid:62) 0 et donc x 2 x + 1 (cid:62) |x 1|.

Deuxi me cas : x < 1. Alors |x1| = (x1). Nous obtenons x 2x+1|x1| = x 2x+1+(x1) = x 2 (cid:62) 0.

Et donc x 2 x + 1 (cid:62) |x 1|.

Conclusion. Dans tous les cas |x 1| (cid:54) x 2 x + 1.

2.3. Contrapos e

Le raisonnement par contraposition est bas sur l quivalence suivante (voir la proposition 1) :

Lassertion P = Q est quivalente non(Q) = non(P) .

Donc si lon souhaite montrer lassertion P = Q , on montre en fait que si non(Q) est vraie alors non(P)

est vraie.

Exemple 3.

Soit n (cid:78). Montrer que si n2 est pair alors n est pair.

D monstration. Nous supposons que n nest pas pair. Nous voulons montrer qualors n2 nest pas pair. Comme

n nest pas pair, il est impair et donc il existe k (cid:78) tel que n = 2k+1. Alors n2 = (2k+1)2 = 4k2+4k+1 = 2(cid:96)+1

avec (cid:96) = 2k2 + 2k (cid:78). Et donc n2 est impair.

Conclusion : nous avons montr que si n est impair alors n2 est impair. Par contraposition ceci est quivalent

: si n2 est pair alors n est pair.

2.4. Absurde

Le raisonnement par labsurde pour montrer P = Q repose sur le principe suivant : on suppose la

fois que P est vraie et que Q est fausse et on cherche une contradiction. Ainsi si P est vraie alors Q doit tre

vraie et donc P = Q est vraie.

LOGIQUE ET RAISONNEMENTS

2. RAISONNEMENTS 8

Exemple 4.

Soient a, b (cid:62) 0. Montrer que si

a

1+b

= b

1+a alors a = b.

D monstration. Nous raisonnons par labsurde en supposant que a

= b

1+a

1+b

alors a(1 + a) = b(1 + b) donc a + a2 = b + b2 do a2 b2 = b a. Cela conduit (a b)(a + b) = (a b).

Comme a (cid:54)= b alors a b (cid:54)= 0 et donc en divisant par a b on obtient a + b = 1. La somme des deux

nombres positifs a et b ne peut tre n gative. Nous obtenons une contradiction.

Conclusion : si

1+a et a (cid:54)= b. Comme a

1+b

= b

= b

1+a alors a = b.

a

1+b

Dans la pratique, on peut choisir indiff remment entre un raisonnement par contraposition ou par labsurde.

Attention cependant de bien pr ciser quel type de raisonnement vous choisissez et surtout de ne pas changer

en cours de r daction !

2.5. Contre-exemple

P(x) est vraie alors pour chaque x de E il faut

Si lon veut montrer quune assertion du type x E

montrer que P(x) est vraie. Par contre pour montrer que cette assertion est fausse alors il suft de trouver

P(x) est x E non P(x) .)

x E tel que P(x) soit fausse. (Rappelez-vous la n gation de x E

P(x) .

Trouver un tel x cest trouver un contre-exemple lassertion x E

Exemple 5.

Montrer que lassertion suivante est fausse Tout entier positif est somme de trois carr s .

(Les carr s sont les 02, 12, 22, 32,... Par exemple 6 = 22 + 12 + 12.)

D monstration. Un contre-exemple est 7 : les carr s inf rieurs 7 sont 0, 1, 4 mais avec trois de ces nombres

on ne peut faire 7.

2.6. R currence

Le principe de r currence permet de montrer quune assertion P(n), d pendant de n, est vraie pour tout

n (cid:78). La d monstration par r currence se d roule en trois tapes : lors de linitialisation on prouve P(0).

Pour l tape dh r dit , on suppose n (cid:62) 0 donn avec P(n) vraie, et on d montre alors que lassertion

P(n + 1) au rang suivant est vraie. Enn dans la conclusion, on rappelle que par le principe de r currence

P(n) est vraie pour tout n (cid:78).

Exemple 6.

Montrer que pour tout n (cid:78), 2n > n.

D monstration. Pour n (cid:62) 0, notons P(n) lassertion suivante :

2n > n.

Nous allons d montrer par r currence que P(n) est vraie pour tout n (cid:62) 0.

Initialisation. Pour n = 0 nous avons 20 = 1 > 0. Donc P(0) est vraie.

H r dit . Fixons n (cid:62) 0. Supposons que P(n) soit vraie. Nous allons montrer que P(n + 1) est vraie.

2n+1 = 2n + 2n > n + 2n

car par P(n) nous savons 2n > n,

> n + 1

car 2n (cid:62) 1.

Donc P(n + 1) est vraie.

Conclusion. Par le principe de r currence P(n) est vraie pour tout n (cid:62) 0, cest- -dire 2n > n pour tout

n (cid:62) 0.

Remarques :

LOGIQUE ET RAISONNEMENTS

2. RAISONNEMENTS 9

" La r daction dune r currence est assez rigide. Respectez scrupuleusement la r daction propos e : donnez

un nom lassertion que vous souhaitez montrer (ici P(n)), respectez les trois tapes (m me si souvent

l tape dinitialisation est tr s facile). En particulier m ditez et conservez la premi re ligne de lh r dit

Fixons n (cid:62) 0. Supposons que P(n) soit vraie. Nous allons montrer que P(n + 1) est vraie.

" Si on doit d montrer quune propri t est vraie pour tout n (cid:62) n0, alors on commence linitialisation au

rang n0.

" Le principe de r currence est bas sur la construction de lensemble (cid:78). En effet un des axiomes pour

d nir (cid:78) est le suivant : Soit A une partie de (cid:78) qui contient 0 et telle que si n A alors n + 1 A. Alors

A = (cid:78) .

Mini-exercices.

1. (Raisonnement direct) Soient a, b (cid:82)+. Montrer que si a (cid:54) b alors a (cid:54) a+b

2

2. (Cas par cas) Montrer que pour tout n (cid:78), n(n + 1) est divisible par 2 (distinguer les n pairs des n

(cid:54) b et a (cid:54)

ab (cid:54) b.

(cid:112)

3. (Contrapos e ou absurde) Soient a, b (cid:90). Montrer que si b (cid:54)= 0 alors a + b

(cid:112)

2 / (cid:81). (On utilisera que

impairs).

(cid:112)

2 / (cid:81).)

(cid:112)

4. (Absurde) Soit n (cid:78). Montrer que

5. (Contre-exemple) Est-ce que pour tout x (cid:82) on a x < 2 = x 2 < 4 ?

6. (R currence) Montrer que pour tout n (cid:62) 1, 1 + 2 + + n = n(n+1)

7. (R currence) Fixons un r el x (cid:62) 0. Montrer que pour tout entier n (cid:62) 1, (1 + x)n (cid:62) 1 + nx.

n2 + 1 nest pas un entier.

2

.

Auteurs du chapitre Arnaud Bodin, Benjamin Boutin, Pascal Romon

Ensembles et applications

Chapitre

2

Vid o (cid:132) partie 1. Ensembles

Vid o (cid:132) partie 2. Applications

Vid o (cid:132) partie 3. Injection, surjection, bijection

Vid o (cid:132) partie 4. Ensembles finis

Vid o (cid:132) partie 5. Relation d quivalence

Fiche dexercices (cid:135) Logique, ensembles, raisonnements

Fiche dexercices (cid:135) Injection, surjection, bijection

Fiche dexercices (cid:135) D nombrement

Fiche dexercices (cid:135) Relation d quivalence, relation dordre

Motivations

Au d but du X Xe si cle le professeur Frege peaunait la r daction du second tome dun ouvrage qui souhaitait

refonder les math matiques sur des bases logiques. Il re ut une lettre dun tout jeune math maticien :

Jai bien lu votre premier livre. Malheureusement vous supposez quil existe un ensemble qui contient tous les

ensembles. Un tel ensemble ne peut exister. Sensuit une d monstration de deux lignes. Tout le travail de

Frege s croulait et il ne sen remettra jamais. Le jeune Russell deviendra lun des plus grands logiciens et

philosophes de son temps. Il obtient le prix Nobel de litt rature en 1950.

Voici le paradoxe de Russell pour montrer que lensemble de tous les ensembles ne peut exister. Cest

tr s bref, mais difcile appr hender. Par labsurde, supposons quun tel ensemble (cid:69) contenant tous les

ensembles existe. Consid rons

F = (cid:166)

E (cid:69) | E / E

(cid:169)

.

Expliquons l criture E / E : le E de gauche est consid r comme un l ment, en effet lensemble (cid:69) est

lensemble de tous les ensembles et E est un l ment de cet ensemble ; le E de droite est consid r comme un

ensemble, en effet les l ment de (cid:69) sont des ensembles ! On peut donc sinterroger si l l ment E appartient

lensemble E. Si non, alors par d nition on met E dans lensemble F .

La contradiction arrive lorsque lon se pose la question suivante : a-t-on F F ou F / F ? Lune des deux

afrmation doit tre vraie. Et pourtant :

" Si F F alors par d nition de F , F est lun des ensembles E tel que F / F . Ce qui est contradictoire.

" Si F / F alors F v rie bien la propri t d nissant F donc F F ! Encore contradictoire.

Aucun des cas nest possible. On en d duit quil ne peut exister un tel ensemble (cid:69) contenant tous les

ensembles.

Ce paradoxe a t popularis par l nigme suivante : Dans une ville, le barbier rase tous ceux qui ne se rasent

pas eux-m mes. Qui rase le barbier ? La seule r ponse valable est quune telle situation ne peut exister.

Ne vous inqui tez pas, Russell et dautres ont fond la logique et les ensembles sur des bases solides.

Cependant il nest pas possible dans ce cours de tout red nir. Heureusement, vous connaissez d j quelques

ENSEMBLES ET APPLICATIONS

1. ENSEMBLES 12

ensembles :

" lensemble des entiers naturels (cid:78) = {0, 1, 2, 3, . . .}.

" lensemble des entiers relatifs (cid:90) = {. . . , 2, 1, 0, 1, 2, . . .}.

" lensemble des rationnels (cid:81) = (cid:8) p

" lensemble des r els (cid:82), par exemple 1,

" lensemble des nombres complexes (cid:67).

| p (cid:90), q (cid:78) \ {0}(cid:9).

2, , ln(2),. . .

(cid:112)

q

Nous allons essayer de voir les propri t s des ensembles, sans sattacher un exemple particulier. 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 dapplication (ou fonction) entre deux ensembles.

1. Ensembles

1.1. D nir des ensembles

" On va d nir informellement ce quest un ensemble : un ensemble est une collection d l ments.

" Exemples :

{0, 1},

{rouge, noir},

{0, 1, 2, 3, . . .} = (cid:78).

" Un ensemble particulier est lensemble vide, not qui est lensemble ne contenant aucun l ment.

" On note

si x est un l ment de E, et x / E dans le cas contraire.

x E

" Voici une autre fa on de d nir des ensembles : une collection d l ments qui v rient une propri t .

" Exemples :

(cid:8)x (cid:82) | |x 2| < 1(cid:9),

(cid:8)z (cid:67) | z5 = 1(cid:9),

(cid:8)x (cid:82) | 0 (cid:54) x (cid:54) 1(cid:9) = [0, 1].

1.2. Inclusion, union, intersection, compl mentaire

" Linclusion. E F si tout l ment de E est aussi un l ment de F . Autrement dit : x E (x F ). On

dit alors que E est un sous-ensemble de F ou une partie de F .

" L galit . E = F si et seulement si E F et F E.

" Ensemble des parties de E. On note (cid:80) (E) lensemble des parties de E. Par exemple si E = {1, 2, 3} :

(cid:80) ({1, 2, 3}) = (cid:8), {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}(cid:9).

" Compl mentaire. Si A E,

(cid:251)

EA = (cid:8)x E | x / A(cid:9)

On le note aussi E \ A et juste (cid:251)A sil ny a pas dambigu t (et parfois aussi Ac ou A).

E

A

(cid:251)

EA

" Union. Pour A, B E,

A * B = (cid:8)x E | x A ou x B(cid:9)

Le ou nest pas exclusif : x peut appartenir A et B en m me temps.

ENSEMBLES ET APPLICATIONS

1. ENSEMBLES 13

A

A * B

B

" Intersection.

A ) B = (cid:8)x E | x A et x B(cid:9)

A

A ) B

B

1.3. R gles de calculs

(on peut donc crire A ) B ) C sans ambig it )

A B A ) B = A

(on peut donc crire A * B * C sans ambigu t )

A B A * B = B

Soient A, B, C des parties dun ensemble E.

" A ) B = B ) A

" A ) (B ) C) = (A ) B) ) C

" A ) = ,

A ) A = A,

" A * B = B * A

" A * (B * C) = (A * B) * C

" A * = A,

" A ) (B * C) = (A ) B) * (A ) C)

" A * (B ) C) = (A * B) ) (A * C)

" (cid:251) (cid:0)(cid:251)A(cid:1) = A

" (cid:251) (A ) B) = (cid:251)A * (cid:251)B

" (cid:251) (A * B) = (cid:251)A ) (cid:251)B

A * A = A,

et donc

A B (cid:251)B (cid:251)A

Voici les dessins pour les deux derni res assertions.

(cid:251)A

(cid:251)B

A

B

A

B

(cid:251)(A ) B) = (cid:251)A * (cid:251)B

(cid:251)(A * B) = (cid:251)A ) (cid:251)B

A

A ) B

B

A

A * B

B

Les preuves sont pour lessentiel une reformulation des op rateurs logiques, en voici quelques-unes :

" Preuve de A) (B * C) = (A) B) * (A) C) : x A) (B * C) x A et x (B * C) x A et (x

B ou x C) (x A et x B) ou (x A et x C) (x A ) B) ou (x A ) C) x

(A ) B) * (A ) C).

ENSEMBLES ET APPLICATIONS

1. ENSEMBLES 14

" Preuve de (cid:251) (A ) B) = (cid:251)A * (cid:251)B : x (cid:251) (A ) B) x / (A ) B) non(cid:0)x A ) B(cid:1) non(cid:0)x

A et x B(cid:1) non(x A) ou non(x B) x / A ou x / B x (cid:251)A * (cid:251)B.

Remarquez que lon repa...