[PDF] —————————— Théorie des ensembles —————————

1 3 Applications 1 3 1 Généralités Définition — Soit E et F deux ensembles On appelle graphe (ou graphe fonc- tionnel) de E × F toute partie X ⊂ E × F

18 fév 2013 · 6) R∗ = l'ensemble des nombres réels non nuls Terminologie de la théorie des ensembles Si x est un élément d'un ensemble A, on ecrit x ∈ A

[PDF] Chapitre I Applications, généralités

Applications, généralités I – Définitions 1 Application Définition : Une application est la donnée : - d'un ensemble de départ , - d'un ensemble d'arrivée ,

[PDF] Ensembles et applications - Normale Sup

Pour les trois exercices suivants, on rappelle que deux ensembles A et B sont dits en bijection s'il existe une application bijective entre A et B Exercice 8 Soient A

[PDF] 1 Généralités sur les ensembles - MATH LA SUP 5

Deux applications f et g sont égales si elles ont même en- semble de départ E, même ensemble d'arrivée F et si ∀x ∈ E, f(x) = g(x) Exemples 7 1 L' application

[PDF] Cours Logique Ensembles Applications 15-18 - Lycée Descartes

I Logique Ensemble Applications : 2014-2018 Prof : Yann Vargoz 7 B) ENSEMBLES I) GÉNÉRALITÉS : DES ENSEMBLES D'ENSEMBLES D' ENSEMBLES

[PDF] Chapitre 5 Applications

Applications 1 Définitions et exemples Définition 5 1 – Soient E et F deux ensembles Une application f de E dans F est un “procédé” qui permet d'associer `a

[PDF] ALGÈBRE Cours et Exercices Première Année LMD - USTO

2 Ensembles et Applications 20 2 1 Ensembles 20 41 3 Relations Binaires 48 3 1 Généralités 48

[PDF] Applications 1 Introduction 2 Généralités

La raison pour laquelle on s'intéresse aux ensemble de départ et d'arrivée est que pour une même règle de calcul x ↦→ f(x), changer les ensembles de départ et

[PDF] —————————— Théorie des ensembles ——————————

1 3 Applications 1 3 1 Généralités Définition — Soit E et F deux ensembles On appelle graphe (ou graphe fonc- tionnel) de E × F toute partie X ⊂ E × F

[PDF] application injective surjective bijective cours

[PDF] ensemble application relation exercice

[PDF] formule trigonométrique 3eme

[PDF] problèmes conduisant ? une modélisation par des fonctions.

[PDF] application des suites numériques dans la vie

[PDF] application des mathématiques ? d autres disciplines capes

[PDF] oral capes maths

[PDF] maths au quotidien college

[PDF] les maths au quotidien pdf

[PDF] application immédiate de la loi nouvelle

[PDF] l'application de la loi dans le temps dissertation

[PDF] histoire du nombre d or pdf

[PDF] le nombre d or histoire des arts

[PDF] principe de précaution définition

[PDF] etu.um5.ac.ma résultats

Th´eorie des ensembles

Cours de licence d"informatique

Saint-Etienne - 2002/2003

Bruno Deschamps

1 El´ements de th´eorie des ensembles 3

1.1 Introduction au calcul propositionnel . . . . . . . . . . . . . . . . . . 3

1.2 Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2.1 G´en´eralit´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2.2 Ensemble des parties . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.3 Produit cart´esien . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.1 G´en´eralit´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.2 Image directe et r´eciproque . . . . . . . . . . . . . . . . . . . 7

1.3.3 Injectivit´e, surjectivit´e, bijectivit´e . . . . . . . . . . . . . . . 7

1.3.4 Caract´erisation de l"injectivit´e et de la surjectivit´e . . . . . . 8

1.4 Relations binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4.1 G´en´eralit´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4.2 Relations d"´equivalence . . . . . . . . . . . . . . . . . . . . . 9

1.4.3 Partitions et relations d"´equivalences . . . . . . . . . . . . . . 10

1.4.4 Repr´esentation matricielle d"une relation binaire . . . . . . . 10

1.5 D´enombrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5.1 Principe de r´ecurrence . . . . . . . . . . . . . . . . . . . . . . 11

1.5.2 Ensembles finis . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5.3 Analyse combinatoire . . . . . . . . . . . . . . . . . . . . . . 12

1.6 Ensembles infinis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.6.1 Cardinalit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.6.2 Ensembles d´enombrables . . . . . . . . . . . . . . . . . . . . . 13

2 Ordres 13

2.1 G´en´eralit´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.1 Ensembles ordonn´es . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.2 El´ements remarquables . . . . . . . . . . . . . . . . . . . . . 14

2.2 Treillis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2.1 Ensembles r´eticul´es . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 Ensembles complets et bien fond´es . . . . . . . . . . . . . . . . . . . 17

2.3.1 G´en´eralit´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3.2 Principe d"induction Noeth´erienne . . . . . . . . . . . . . . . 17

2.3.3 Les th´eor`emes de Kn¨aster et Tarski . . . . . . . . . . . . . . . 17

1 El´ements de th´eorie des ensembles

1.1 Introduction au calcul propositionnel

On noteA,B,C···des propositions ´el´ementaires qui prennent la valeur 0 (faux) ou 1 vrai et l"on forme de nouvelles propositions `a partir des connecteurs suivants : non, et, ou, implique, ´equivaut. On leur affecte alors une v´erit´e d"apr`es les tables de v´erit´e ci-apr`es et la valeur prise par les propositions intervenant dans la proposition

´etudi´ee.

•N´egation. •Conjonction. •Disjonction. •Implication. •Equivalence. D´efinition.-On appelle tautologie toute proposition qui ne prend que la valeur1 quelle que soit la valeur des propositions ´el´ementaires qu"elle contient. Th´eor`eme.-SoitPetQdeux propositions ayants les mˆeme propositions ´el´ementaires. AlorsPetQont mˆeme table de v´erit´e ssiP??Qest une tautologie. Th´eor`eme.-Toute proposition du calcul propositionnel ´equivaut `a une conjonc- tion de disjonctions (et `a une disjonction de conjonctions) de propositions ´el´ementaires.

1.2 Ensembles

1.2.1 G´en´eralit´es

•On appelleensembleune collection d"objets assuj´etie `a certaines contraintes que nous n"´enoncerons pas ici. Les objets de cette collection s"appelle les ´el´ements de l"ensemble. SiEest un ensemble et si···sont ses ´el´ements, on note alors E={···}ou alors on repr´esenteEpar une patate (ce qui est plus visuel, car l"ordre d"´enum´eration des ´el´ements d"un ensemble n"a aucune importance).

•L"ensemble qui ne contient aucun ´el´ement est appell´el"ensemble videet est not´e∅

ou parfois{}. On remarquera bien queE={∅}n"est pas l"ensemble vide puisqu"il contient un ´el´ement. •SiEest un ensemble et sixest un objet, on ´ecrirax?Epour symboliser le fait que x est ´el´ement deE, et on ´ecrirax /?Epour symboliser le fait que x n"est pas

´el´ement deE.

•SiEest un ensemble et siPd´esigne une propri´et´e pourtant sur les ´el´ements de

l"ensembleE, on ´ecrira ?x?E P(x) pour dire "pour toutxla propri´et´eP(x)" de mˆeme, on ´ecrira ?x?E P(x) pour dire "il existextel que la propri´et´eP(x)". D´efinition.-SoitAetBdeux ensembles. Si tout ´el´ement deAest un ´el´ement deB, on dit queAest un sous-ensemble deBet l"on noteA?B. i.e. A?B?? ?x?A, x?B 4 On dit que deux ensemblesAetBsont ´egaux et l"on noteA=BsiA?Bet B?A. SiA?BetA?=Bon parle d"inclusion stricte et l"on note ??? Exemple:SoitE={x,y,{x,y}}etA={x,y}. On a alors `a la foisx?Aet X?A. D´efinition.-SoientAetBdeux ensembles. On appelle r´eunion deAet deB l"ensemble, not´eA?B, constitu´e des ´el´ements appartenant `aAou `aB i.e. x?A?B??x?A ou x?B De mˆeme, On appelle intersection deAet deBl"ensemble, not´eA∩B, constitu´e des ´el´ements appartenant `aAet `aB i.e. x?A∩B??x?A et x?B

Proposition.-SoitA,B,Ctrois ensembles. On a

A∩(B?C) = (A∩B)?(A∩C)

A?(B∩C) = (A?B)∩(A?C)

D´efinition.-SoitEun ensemble etAun sous-ensemble deE. On appelle compl´ementaire deAdansEl"ensemble, not´eCEA, constitu´e des ´el´ements deE qui n"appartiennent pas `aA. Proposition.-SoitEun ensemble etA,Bdes sous-ensembles deE. On a: • C

E(CEA) =A,

•siA?BalorsCEB? CEA, • C

E(A?B) = (CEA)∩(CEA),

• C

E(A∩B) = (CEA)?(CEA).

D´efinition.-SoientEetFdeux ensembles. on appelle diff´erence deEparF l"ensemble, not´eE-F, constitu´e des ´el´ements deEqui ne sont pas ´el´ements deF. Exemple:Soient 5N={0,5,10,···}l"ensemble des entiers multiples de 5 et 3N= {0,3,6,···}l"ensemble des entiers multiples de 3. L"ensemble 5N-3Nest donc constitu´e des entiers multiples de 5 qui ne sont pas multiples de 3. Or, les entiers multiples de 5 et multiples de 3 sont exactement les entiers multiples de 15. On en d´eduit donc que :

Proposition.-SoientE,F,Gtrois ensembles. On a

•E-F=CEE∩F=CE?FF, •E-(F?G) = ((E?G)-F)∩((E?F)-G), •E-(F?G) = (E-F)∩(E-G), •E-(F∩G) = (E-F)?(E-G). 5

1.2.2 Ensemble des parties

D´efinition.-SoientEun ensemble. On appelle ensemble des parties deEl"ensemble, not´eP(E)constitu´e des sous-ensembles deE. On remarquera bien que les ´el´ements deP(E) sont des ensembles.

Exemples:SiE={x,y}alors

P(E) ={∅,{x},{y},E}

On a

P(∅) ={∅}

de mˆeme,

P(P(∅)) ={∅,{∅}}

1.2.3 Produit cart´esien

D´efinition.-SoitAetBdeux ensembles, on appelle couple (ou paire ordonn´ee) d"´el´ement deAet deBtout ensemble de la forme{a,{a,b}}aveca?Aetb?B. Un tel ensemble se note alors(a,b). L"ensemble constitu´e des couples d"´el´ements deAet deBs"appelle le produit cart´esien deAparBet se noteA×B. Il faut bien remarquer que (a,b)?= (b,a) le plus souvent. En fait : Proposition.-SoientAetBdeux ensembles et(a,b)et(c,d)deux ´el´ements de A×B. Les propositions suivantes sont ´equivalentes: i)(a,b) = (c,d), ii)a=cetb=d.

Proposition.-SoitA,B,Ctrois ensembles. On a:

•A×(B?C) =A×B?A×C, •A×(B∩C) =A×B∩A×C. Remarque:SiE1,···,Ensont des ensembles, on d´efinit par r´ecurrence le produit cart´esienE1× ··· ×Endes ensemblesE1,···,En, par la relation E

1× ··· ×En= (E1× ··· ×En-1)×En

Les ´el´ements deE1×···×Ensont alors appell´es desn-uplets et not´es (x1,···,xn)

avecxi?Eipour touti= 1,···,n. On a alors Proposition.-SoientE1,···,Endes ensembles et(x1,···,xn)et

(y1,···,yn)deux ´el´ements deE1×···×En. Les propositions suivantes sont ´equivalentes:

i)(x1,···,xn) = (y1,···,yn), ii)xi=yipour touti= 1,···n.

1.3 Applications

1.3.1 G´en´eralit´es

D´efinition.-SoitEetFdeux ensembles. On appelle graphe (ou graphe fonc- tionnel) deE×Ftoute partieX?E×Fv´erifiant : ?(a,b)?X,?(a?,b?)?X, a=a?=?b=b?

Exemple:PourE=F,

6 •X=∅, •X={(a,a)/ a?E} D´efinition.-On appelle fonction la donn´ee d"un triplet(E,X,F)o`uEetF sont des ensembles etXun graphe deE×F. On notef= (E,X,F)ou plus classiquementf:E→Fune fonction. L"ensembleEs"appelle l"ensemble de d´epart def, l"ensembleFs"appelle l"ensemble d"arriv´e def, etXs"appelle de graphe de f. On dit alors quefest une fonction deEdansFde grapheX.

Si(x,y)?X, on note alorsy=f(x).

Sif= (E,X,F)est une fonction, on appelle ensemble de d´efinition defle sous-ensembleAdeEconstitu´e des ´el´ementsa?Etel qu"il existeb?Fv´erifiant (a,b)?X. On dit qu"une fonctionf= (E,X,F)est totale et on parle alors d"application, si le domaine de d´efinition defestE. Lemme.-SoitEetFdeux ensembles etXun graphe fonctionnel deE×F. Soit

U?E. L"ensemble

U={(a,b)?X/ a?U}

est un graphe fonctionnel deU×F. D´efinition.-Soitf:E-→Fune fonction,Xsont graphe etU?E. La fonction deUdansFde grapheXUs"appelle la restricion def`aUet se notef|U(c"est une fonction). En particulier, siAest le domaine de d´efinition def, alorsf|Aest une application. Notation :SiEetFsont deux ensembles, on noteF(E,F) l"ensemble des appli- cations deEdansF. Exemples:•SiEest un ensemble etX={(a,a)?E×E, a?E}, l"application f= (E,X,E) s"appelle l"application identit´e deEet se noteIdE. •SiE?Fsont deux ensembles etX={(a,a)?E×F, a?E}, l"application f= (E,X,F) s"appelle l"injection canonique deEdansF. Dans le cas o`uE=F il s"agit alors deIdE. D´efinition.-SoitE,F,Gtrois ensembles,X1un graphe fonctionnel deE×F etX2un graphe fonctionnel deF×G. On appelle graphe compos´e deX1etX2 l"ensemble

X={(a,b)?E×G/?c?F,(a,c)?X1et(c,b)?X2}

(C"est un graphe fonctionnel deE×G) Proposition.-Sif:E→Fest une application deEdansFde grapheX1et g:F→Gest une application deFdansGde grapheX2, le graphe compos´e deX1 etX2est le grapheXd"une application deEdansG. D´efinition.-Avec les notation pr´ec´edente, l"application(E,X,G)s"appelle la compos´ee defetget se noteg◦f. Proposition.-Soientf:E→F,g:F→G,h:G→Hsont trois applications. Les deux applications(h◦g)◦feth◦(g◦f)sont identique (i.e. ont mˆeme graphe). Remarque:La loi◦est donc associative. DansF(E,F) elle est rarement associa- tive. Par exemple sif,g:R→Rsont d´efinie par,f(x) =x+ 1 etg(x) =x2; on a alorsf◦g(x) =x2+ 1 etg◦f(x) = (x+ 1)2. 7quotesdbs_dbs26.pdfusesText_32

[PDF] [PDF] —————————— Théorie des ensembles ——————————