Cours sur les ensembles

Description

Chapter 1Rappels sur les ensembles,d´enombrementSommaire1.1 Motivation: l’´equiprobabilit´e sur un ensemble fini . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Notions de bases sur les ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2.1 D´efinition d’un ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2.2 Parties d’un ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3.1 Image et image r´eciproque de parties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3.2 Injectivit´e, surjectivit´e, bijectivit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.4 Rudiments de cardinalit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.5 D´enombrements classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.5.1 Produit cart´esien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.5.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.5.3 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.5.4 Arrangements, injections, p-listes sans r´ep´etitions et tirage ordonn´e sans remise . . . . . . 101.5.5 ...

Informations

• Publié par: Assa
• Nombre de lectures: 30
• Langue: Français

Extrait

Chapter

1

Rappels sur les de´nombrement

ensembles,

Sommaire 1.1Motivation:l’´equiprobabilite´surunensemblefini........................... 1.2 Notions de bases sur les ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1De´finitiond’unensemble..................................... 1.2.2 Parties d’un ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1Imageetimager´eciproquedeparties.............................. 1.3.2Injectivite´,surjectivite´,bijectivit´e............................... 1.4Rudimentsdecardinalit´e........................................ 1.5D´enombrementsclassiques........................................ 1.5.1Produitcarte´sien......................................... 1.5.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.3 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.4 Arrangements, injections,plsietssna......imessnersa´enndoorgeratitesnoitite´pe´rs 1.5.5Coefficientsbinomiaux,partiesd’unensemblesettiragesnonordonne´ssansremise.... 1.6Principesdebasedude´nombrement.................................. 1.7Quelquesconseilspratiquespourlesexercicesd’e´quiprobabilite´...................

Objectifs: classiques.

5 5 5 5 7 7 7 8 8 8 9 10 10 11 13 13

Rappelerlesnotationssurlesensembles,lesrudimentsdecardinalite´etlesde´nombrements

Motscl´es: •tces,noii,noretnniuentaire.compl´em •application, injection, surjection, bijection. •ensemble fini, cardinal. •tre´tiacorudpneis,nuplet,nteiser,ptamuontilome.c,eocffieitnudibˆn

Outils: •´end’i,dceanndpebedsepicnoitcejiprinraitd,pe.itno •.ueldeudtfromrumlgclale,dreiPaanstwnoedeNoˆeomfbuni

Techniquesded´emonstration: parre´currence.

e´galit´ededeuxensemblespardoubleinclusion,contraposition,de´monstration

1.1

Motivation:

l’e´quiprobabilit´esurunensemblefini

Onrappellequel’e´quiprobabilit´ePsur un ensemble fini Ω est l’application de l’ensembleP(Ω) des parties de Ω dans [0,pera]1´dfiein CardA ∀A∈ P(Ω),P(A) =. Card Ω Cepremierexempledeprobabilit´evaˆetrel’occasionderappelerquelques´el´ementsdelath´eoriena¨ıvedesensembles, etlesprincipesdebasedud´enombrement.

1.2

1.2.1

Notions de bases sur les ensembles

D´efinitiond’unensemble

Pourd´ecrireunensembleedstlilal´´eesesepno,rennodtueatrolccenementsectso’uqsedae’c:lanappelled´efiniitno en extensiontpesn’lembseenUnisnia,e´nnodrosa.{1,3,2}et{1,2,3}sneelbmeaD.eecsntˆmmetnelirev´dce exemple, 2 est unlee´emtn´de{1,2,3}, ce qui se note

2∈ {1,2,3};

par contre,{1,3}estune partiede{1,2,3}; on dit que{1,3}estinclusdans{1,2,3}, ce qui se note

{1,3} ⊂ {1,2,3}.

♠Attention!2∈ {1,2,3}et{2} ⊂ {1,2,3}. Onpeutaussid´efinirunensembleoisnnpromhe´encetseda`’c,tcaraciuesire´roprlesp´esqi´etdnnorieealuoantn sese´l´ements: {2,4,6}={x∈ {1, . . . ,7}: 2|x}.

Quelques ensembles usuels:

•l’ensemble des entiers naturelsN={0,1,2, ...}, ∗ l’ensemble des entiers naturels strictement positifsN={1,2, ...},

•l’ensemble des entiers relatifsZ={...,−2,−1,0,1,2, ...},   p ∗ •l’ensemble des nombres rationnels:Q=, p∈Z, q∈N, q •lbmesedebmonrserel´es’enslRrse´lepssotifiosunuls,dnoesrembR + ...

1.2.2

Partiesd’unensemble

On noteP(Ω) l’ensemble des parties de Ω.

♣Exercice:Soit Ω ={1,2,3}l’ensemble. Ecrire Pties`adees?deparxuneibmoC.dlitaΩestiarepctinstdi(Ω) e´lementsdistinctes?

Soit Ω un ensemble, etAetBdeux parties de Ω.

•lar´noueindeAetBn,toe´eA∪Brtpalast,eedee´sopmocΩedeile´seme´dstneAs´de´eelntmeesdteB:

{1,2,5,6} ∪ {2,3,5,7}={1,2,3,5,6,7}

Lare´uniondedeuxensemblescorrespondaulienlogique“ou”:

x∈A∪B⇔x∈Aoux∈B

5

(noter que sixest dansA∪B, alorsxnadssla`eiofautpetrˆeAetdansB) Lar´euniond’unefamilled’ensemblescorrespondauquantificateur∃soit ((“il existe”): A i ) i∈I une famille de parties d’un ensemble Ω. Alors [ x∈A i ⇔ ∃i∈I, x∈A i . i∈I

•l’intersectiondeAetB,eeon´tA∩Bsafoisdantlap,esedeΩartiesedl´´empco´eosnosila`tnemeuqstAet dansB: {1,2,5,6} ∩ {2,3,5,7}={2,5}

L’intersection de deux ensembles correspond au lien logique “et”:

x∈A∩B⇔x∈Aetx∈B.

L’intersection d’une famille d’ensembles correspond au quantificateur∀(“pour tout”): soit (A i ) i∈I une famille de parties d’un ensemble Ω. Alors \ x∈A i ⇔ ∀i∈I, x∈A i . i∈I

c •leeneml´mpcoeriatdeAon,Ωsnadt´eeAop´seeedeiedcΩmostlapart,esaseniptnosdntqueΩels´me´e dansA: c Ω ={1,2, ...,10}, A={1,3,5,7,8,9,10}, A={2,4,6}.

c Lepassageaucompl´ementairecorresponda`lan´egationlogique:x∈A⇔x∈/ A. Remarquonsquelecompl´ementaired´ependdel’ensembleΩconsid´ere´,etque

c c A∪Aet= Ω A∩A=∅.

Propri´et´es1.1SoitA,BetCtrois parties d’un ensembleE.

c c c •(A∪B) =A∩B

c c c •(A∩B) =A∪B

•(A∪B)∩C= (A∩C)∪(A∩B)

•(A∩B)∪C= (A∪C)∩(A∪B)

D´emonstration:rpade`eocrpno,selbmesnexudedeit´eegalrl’´tnerruomopdouble inclusion, c’est a`direquesil’onsouhaiteprouverquedeuxensemblesAetBueobdrdaa’erqromtnnt´eso,onvgaux Aest inclus dansB, puis queBest inclus dansA. Montronsainsilapremie`reproprie´te´.SoitAetBdeux parties d’un ensembleE. c c c •Montrons que (A∪B) est inclus dansA∩Bmontrer qu’un ensemble. Pour Eest inclus dans un ensembleF,onmontrequehccanued´slee´emesdntEapa`ntiertpaFva donc montrer. On c c c iciquetout´ele´mentde(A∪B) est dansA∩B. c Soitxdans (A∪B) , alorsx6∈A∪B, doncx6∈Aetx6∈B, c c doncx∈Aetx∈B, c c doncx∈A∩B. c c c c c c Donctout´el´ementxde (A∪Bdans) est A∩B, donc (A∪B)⊂A∩B.

6