[PDF] Relations dordre. Dénombrement. Plus grand élément. Borne

View - Download Relations dordre. Dénombrement. Plus grand élément. Borne

Previous PDF

Next PDF

Universite de Provence2009{2010

Mathematiques Generales 1 - Parcours PEI

Relations d'ordre. D

enombrement. Plus grandelement. Borne Superieure.1 Relations d'ordre.

1.1 Relations d'ordre. Ensembles ordonnes.Denition.SoitEun ensemble muni d'une relation binaireR. On dit queRest unerelation d'ordresurEou

que (E;R) est unensemble ordonnesi et seulement siRpossede les proprietes suivantes : -Re exivite:8x2E; xRx. -Anti-symetrie:8(x;y)2E2; xRyetyRx)x=y. -Transitivite:8(x;y;z)2E3; xRyetyRz)xRz.Exemples. - Dans l'ensemble des nombres reels, l'inegalite largexyest une relation d'ordre. - Dans l'ensemble des nombres naturels, la relationadiviseb, noteeajbest une relation d'ordre. - Dans l'ensemble des parties d'un ensemble, la relationABest une relation d'ordre.

Remarques.Bien faire attention au fait que l'anti-symetrie n'est pas la negation de la symetrie. Il existe des

relations qui sont a la fois symetriques et anti-symetriques. D'une maniere generale, les symboles pour designer les relations d'ordre sont,,,:::

1.2 Majorants, minorants. Plus grand element. Plus petit element.Denition.Soit (E;) un ensemble ordonne etAune partie deE.

- On dit queM2EestmajorantdeAsi et seulement si :8x2A,xM.

- On dit quem2EestminorantdeAsi et seulement si :8x2A,mx.Exemples.Par exemple, si (E;) = (R;) et siA= [0;1[,B=Z,C= [1;2], alors tout reelx1 est majorant

deA, tout reelx <0 est minorant deA, il n'y a ni minorant, ni majorant deB, tout reelx >2 est majorant

deC, tout reelx <1 est minorant deC.

Si (E;) = (N;j) et siD=f1;2;3;4;5;6g, les majorants deDsont tous les nombres divisibles par 1, 2, 3, 4,

5, 6, donc divisibles par PPCM(2;3;4;5;6) = 2235 = 60.

Denition.Avec les notations precedentes, on dit queAestmajorees'il existe au moins un majorant deA.

De m^eme, on dit queAestminorees'il existe au moins un minorant deA.Denition.Soit (E;) un ensemble ordonne etAune partie deA. Soita2E. On dit que :

-aest unplus grand element deAsi et seulement siaest majorant deAeta2A.

-aest unplus petit element deAsi et seulement siaest minorant deAeta2A.Exemples.Pour reprendre les exemples precedents,

-An'a pas de plus grand element mais a un plus petit element 0. -Bn'a ni plus grand element, ni plus petit element. -Ca pour plus petit element 1 et pour plus grand element 2.

-Dn'a pas de plus grand element mais a pour plus petit element 1.Theoreme.Soit(E;)un ensemble ordonne etAune partie deA. SiApossede un plus grand element, celui-ci

est unique. Il en est de m^eme pour le plus petit element.Preuve.En eet, soientaeta0deux plus grands elements deA.

Commea2Aet quea0est majorant deA, on aaa0.

Commea02Aet queaest majorant deA, on aa0a.

L'antisymetrie denous donnea=a0.Denition.SiAun sous-ensemble de (E;) possede un plus grand element, celui-ci est unique et on le note

maxA.

De m^eme, si le plus petit element existe, celui-ci est unique et on le note minA.Nous avons vu dans les exemples preceents que les parties deR, qu'elles soient majorees ou non, non pas

forcement de plus grand element.

Par contre, et c'est un des axiomes de construction de l'ensemble des entiers naturelsNou de l'ensemble des

entiers relatifsZ, nous avons :AxiomesToute partie non vide majoree deNpossede un plus grand element.

Toute partie non vide deNpossede un plus petit element. Toute partie non vide majoree deZpossede un plus grand element.

Toute partie non vide minoree deZpossede un plus petit element.Comme application, nous pouvons construire la partie entiere des reels.

Theoreme et denition.Sixest un nombre reel, il existe un et un seul entiern2Ztel quenx < n+ 1. On le note [x] ouE(x). De plus [x] = maxfn2Z=nxg.2 Preuve.Soitx2R. On considereA=fn2Z=nxg. C'est un sous-ensemble deZnon vide (car il existe

des entiers relatifs plus petits quex) et majore (car il existe des entiers relatifs strictement plus grands quex).

DoncApossede un plus grand element,n.

On an2A, doncnx.

Commenest majorant deA,n+1 aussi. On ne peut avoirn+12A. En eet, si c'etait le cas, on aurait deux

elementsnetn+1 qui seraient tous les deux dansAet qui seraient majorants deA. Ceci contredirait l'unicite

du plus grand element deA.

On a doncn+ 162A, ce qui implique quen+ 1> x.

Ceci montre bien l'existence de la partie entiere dex. Reste a voir l'unicite de celle-ci. Supposons quen02Zsoit tel quen0x < n0+ 1. Nous allons montrer que necessairement,n0=n. Sin0< n, alorsn0+ 1nx, ce qui est impossible carx < n0+ 1. De m^eme,n < n0est impossible. On a donc bienn=n0.

1.3 Bornes superieures, borne inferieures.Denition.Soit (E;) un ensemble ordonne etAune partie deE.

On dit quea2Eestborne superieuredeAsi et seulement siaest le plus petit element de l'ensemble des majorants deA. On dit quea2Eestborne inferieuredeAsi et seulement siaest le plus grand element de l'ensemble des minorants deA.

Il decoule de l'unicite du plus grand element et du plus petit element d'un ensemble que les bornes superieures

et inferieures, si elles existent, sont uniques.

On note la borne superieure, supA, et la borne inferieure, infA.Exemples.Pour reprendre les exemples precedents,

- supA= 1, infA= 0. - supBet infBn'existent pas - supC= 2 et infC= 1. - supD= 60 et infD= 1.

En general, si la borne superieure d'un ensembleAexiste, elle n'est pas le plus grand element deAcar elle n'a

aucune raison d'appartenir aA(voir l'exemple de l'ensembleAci-dessus). Mais par contre, si un ensembleAadmet un plus grand elementa= maxA, alorsaest la borne superieure

deA. Ceci prouve que la notion de borne superieure est une notion plus generale que la notion de plus grand

element. Theoreme.Soit(E;)un ensemble ordonne etAE. SiAadmet un plus grand elementa, alorsaest borne superieure deA.

Preuve.Pour montrer queaest egal a la borne superieure deA, il faut montrer queaest le plus petit element

de l'ensemble des majorants deA. Oraest majorant deA. Il reste donc a prouver queaest minorant de 3 l'ensemble des majorants deA, c'est-a-dire que, pour tout majorantMdeA, on aaM. Or ceci est bien le cas cara2A.

1.4 Cas deR.

L'une des proprietes fondamentales deRest la suivante :Axiome.Toute partie non vide majoree deRpossede une borne superieure.

Toute partie non vide minoree deRpossede une borne inferieure.Nous avons aussi le theoreme suivant, tres important, appele "Theoreme de passage a la borne superieure" :

Theoreme.SoitAune partie non vide deR. SoitM2Rtel que :8x2A; xM. AlorssupAexiste et supAM.Il y a bien entendu un enonce tout a fait analogue pour la borne inferieure. Preuve.La borne superieure existe carAest non vide et majoree. CommeMest un majorant deA, on en

deduit que supAqui est le plus petit element de l'ensemble des majorants verie supAM.Attention toutefois au faux theoreme de passage a la borne superieure. L'enonce suivant : \8x2A,x < M

implique supA < M" est un enonce faux. Si par exempleA= [0;1[ etM= 1, on a :8x2A,x <1 et pourtant

supA= 1. Il est donc tres important dans le theoreme de passage a la borne superieure que les inegalites soient

larges.Enn, nous avons le theoreme de caracterisation de la borne superieure d'un sous-ensemble deRsuivant :Theoreme.SoitAune partie non vide majoree deRets2R. Alorss= supAsi et seulement si,

8x2A; xs

et

8" >0;9x2A; xs":Preuve.En eet, sis= supA, alorssverie la premiere propriete.

Pour la seconde, on remarque que, si" >0, commes" < set quesest le plus petit des majorants, alorss" n'est pas majorant deA. Et donc, il existex2Atel quex > s". Ceci prouve le deuxieme point. Reciproquement, sisverie les deux proprietes, montrons ques= supA.

Tout d'abord, il decoule de la premiere propriete quesest majorant deA. Montrons quesest le plus petit

element de l'ensemble des majorants deA, c'est-a-dire quesest minorant de l'ensemble des majorants. SoitMun majorant deA. Montrons quesM. SiM < s, alors, pour"=sM2 >0, on sait qu'il existex2A tel quexs". On a alorsxssM2 =M+s2 > McarM > s. On a donc exhibe un elementxdeAtel 4 quex > M. Ceci contredit le fait queMsoit un majorant deA. On a donc bien prouve quesM, et ques est la borne superieure de l'ensembleA.

2 Produit cartesien d'ensembles nis.

2.1 EnsemblesEFetFp.puplets.

Rappel de choses vues dans le premier chapitre.Denition.EetFsont deux ensembles nis non vides. Leproduit cartesiendeEetF, noteEF, est

l'ensemble des couples (x;y) formes d'un elementxdeEsuivi d'un elementydeF.Exemple.SiE=fa;b;cgetF=f1;2g, on a

EF=f(a;1);(a;2);(b;1);(b;2);(c;1);(c;2)gDenition.Soitpun entier naturel non nul,E1;:::;Eppensembles nis non vides. Leproduit cartesiende

E

1;E2;:::;Ep, noteE1 Ep, est l'ensemble despuplets(x1;x2;;xp) formes d'un elementx1deE1

suivi d'un elementx2deE2,etc...

SiE1;:::Epsont tous egaux aE, on noteE E=Ep.Exemple.On lance simultanement trois des discernables, par exemple rouge, vert et blanc; et on note les numeros

des faces.

Le resultat d'un tel lancer peut se noter a l'aide d'un triplet (x;y;z) ouxest le numero du de rouge,ycelui du

de vert etzcelui du de blanc. SiEdesigne l'ensemblef1;2;3;4;5;6g, a chaque lancer des trois des est associe un element deE3.

2.2 Cardinal d'un produit d'ensembles.Theoreme.SiEetFsont deux ensembles nis, alors

Card(EF) = (CardE)(CardF):

Plus generalement, siE1;:::Epsontpensembles nis

Card(E1 Ep) = (CardE1)(CardE2)(CardEp):

Enn, siEest un ensemble ni etpun entier naturel non nul,

(CardEp) = (CardE)p:Exemple.Dans un jeu de bridge, il y a 52 cartes. Chacune de ces cartes peut ^etre consideree comme un element

du produit cartesienEF, ouEest l'ensemble des quatre couleurs (pique, cur, carreau, tre e) etFcelui

des treize valeurs (as, 2, 3,:::, 9, 10, valet, dame, roi). Notez que l'on a bien card(EF) = 413 = 52.

5

3 Arrangements. Permutations.

3.1 Arrangements.Denition.netpsont des naturels tels que 1pnetEest un ensemble anelements. Unarrangementde

pelements deEest unpuplet d'elements deux a deux distinctsdeE.Exercice.Ecrire tous les arrangements de trois elements defa;b;c;dg.

3.2 Nombre d'arrangements.

Dans le cas general, notonsE=fa1;:::;ang. Pour fabriquer un arrangement depelements deE, on a le choix

entrenelements pour la premiere position. Ce choix etant fait, on peut alors mettren1 elements possibles

en deuxieme position. En continuant comme cela jusqu'a lapieme position, on peut alors y placernp+ 1

elements possibles. Le nombre d'arrangements est doncn(n1) (np+ 1).Theoreme.netpsont des naturels tels que1pnetEest un ensemble anelements. Le nombre

d'arrangements depelements deEest A pn=n(n1) (np+ 1) =n!(np)!:3.3 Permutations. Denition.nest un naturel non nul etEun ensemble anelements. Unepermutationdes elements deEest

un arrangement denelements deE.Theoreme.Le nombre de permutations d'un ensemble anelements estn!4 Parties apelements d'un ensemble anelements (pn).

4.1 Nombre de parties apelements. Combinaisons.

SoitEun ensemble de cardinaln1 et soit 1pn. Nous savons que le nombre d'arrangements dep elements pris parmi lesndeEestApn. Chaque partie apelements deE, par permutation de ses elements,

donne naissance ap! des arrangements precedents. Le nombre de parties apelements est doncApnp!. Sip= 0,

cela est encore vrai.Theoreme.Le nombre de parties apelements d'un ensemble anelements avecpnestApnp!. On note ce

nombreCpn, on a donc : C pn=Apnp!=n!(np)!p!:6 Denition.Une partie apelements d'un ensembleEanelements (pn) s'appelle unecombinaisondepdes nelements deE.4.2 Proprietes desCpn.

Pour tout entier natureln,C0n=Cnn= 1.

Pour tout entier natureln1,C1n=n.

SoitEun ensemble de cardinaln1, soitpnet soitAune partie deEapelements. Choisir lespelements

deAdansE, c'est aussi choisir lesnpelements du complementaire deAdansE. Il y a donc autant de parties

apelements deEque de parties anpelements deE.Theoreme.Pour tous naturelsnetptels quepnon a : C pn=Cnpn:SoitEun ensemble an1 elements et soitptel que 1pn1. Notonsal'un des elements deE. Notons Al'ensemble des parties deEapelements qui contiennentaetBl'ensemble des parties deEapelements qui ne contiennent pasa. Choisir une partie deArevient a choisir une partie ap1 elements dansEn faga laquelle on rajoutefag. Il y a doncCp1 n1telles parties. Choisir une partie deBrevient a choisir une partie ap elements dansEn fag. Il y a doncCp n1telles parties.Theoreme.Pour tous naturelsnetptels que1pn1on a : C pn=Cp1 n1+Cp

n1:Il decoule de ce theoreme, en faisant une recurrence surn:Formule du bin^ome de Newton.Pour tous complexesaetbet pour tout entier natureln1,

(a+b)n=nX k=0C knakbnk:Corollaire.Le nombre de parties d'un ensemble anelements est C

0n+C1n++Cn1n+Cnn= (1 + 1)n= 2n:7

quotesdbs_dbs47.pdfusesText_47

[PDF] montrer verbe

[PDF] Montres que le lycée est un lieu régit par le Droit

[PDF] montrez

[PDF] montrez comment la structure de l'adn explique sa fonction de support de l'information génétique

[PDF] montrez comment le progrès technique stimule la croissance économique

[PDF] Montrez comment un pouvoir est politique et comment une question devient politique

[PDF] Montrez en citant des indices, que Les Confessions appartiennent au genre autobiographique

[PDF] montrez en quoi la croissance est un phénomène cumulatif

[PDF] Montrez l'importance des ressources alimentairess sur la reproduction des anchois

[PDF] montrez les différentes facettes du défi alimentaire auquel l'Inde est confrontée

[PDF] montrez que la 2 nd guerre mondiale fut une guerre d'aneantissement

[PDF] montrez que la détermination du salaire peut dépendre de l'intervention de l'état.

[PDF] montrez que la fiscalité peut contribuer ? la justice sociale.

[PDF] Montrez que la fonction f a pour expression

[PDF] montrez que le facteur capital est source de croissance économique.