Document créé le 29 octobre 2015 Lien vers la dernière mise à jour de ce document Lien vers les exercices de ce chapitre




Chapitre 1

Logique et ensembles

Sommaire
1.1 Rudiments de logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Propositions, démonstrations, etc. . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Ensembles, éléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Propriétés portant sur les éléments d’un ensemble . . . . . . . . . . . . . . . . 3
1.1.4 Opérations sur les propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.5 Quantificateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.6 Quelques synonymies classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.7 Conditions nécessaires et/ou suffisantes . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Raisonnements classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Conseils appuyés pour bien rédiger . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Quelques figures usuelles du raisonnement . . . . . . . . . . . . . . . . . . . . . 7
1.2.3 L’axiome de récurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.4 Raisonnement par récurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.5 Raisonnement par analyse-synthèse . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.6 Résolutions d’équations ou d’inéquations . . . . . . . . . . . . . . . . . . . . . . 10
1.2.7 Équations ou inéquations à un paramètre . . . . . . . . . . . . . . . . . . . . . 11
1.3 Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.1 Opérations sur les ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.2 Ensemble des parties d’un ensemble . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.3 Opérations sur les parties d’un ensemble . . . . . . . . . . . . . . . . . . . . . . 13
1.3.4 Produit cartésien d’un nombre fini d’ensembles . . . . . . . . . . . . . . . . . . 14
1.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.1 Applications entres ensembles non vides . . . . . . . . . . . . . . . . . . . . . . 14
1.4.2 Famille indexée par un ensemble non vide . . . . . . . . . . . . . . . . . . . . . 15
1.4.3 Fonction indicatrice d’une partie . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.4 Restriction et prolongement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.5 Image directe d’une partie par une application . . . . . . . . . . . . . . . . . . 17
1.4.6 Image réciproque d’une partie par une application . . . . . . . . . . . . . . . . 18
1.4.7 Composition d’applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5 Injections, surjections, bijections . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.1 Applications injectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.2 Applications surjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.3 Applications bijectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.1 Rudiments de logique Chapitre 1 : Logique et ensembles


1.6 Relations binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.6.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.6.2 Propriétés éventuelles des relations binaires . . . . . . . . . . . . . . . . . . . . 22
1.6.3 Relations d’ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.6.4 Relations d’équivalence, classes d’équivalence . . . . . . . . . . . . . . . . . . . 24
1.6.5 Congruence modulo un réel strictement positif . . . . . . . . . . . . . . . . . . 24
1.6.6 Division euclidienne et congruence modulo un entier . . . . . . . . . . . . . . . 25




1.1 Rudiments de logique

1.1.1 Propositions, démonstrations, etc.

Définition 1.1.1
Une proposition est un énoncé dont on doit pouvoir dire qu’il est « vrai » ou « faux ».
On notera V et F (ou encore 1 et 0) les deux valeurs logiques possibles d’une proposition.

Exemples :
– « l’entier 2011 est premier » est une proposition vraie
– « l’entier 2012 est premier » est une proposition fausse
– « l’entier 2014 est une somme de deux carrés » est une proposition fausse (prouvez-le)
– « l’entier 2017 est somme de deux carrés » est une proposition vraie (en effet 2017 = 92 + 442 )

Définition 1.1.2
Certaines propositions sont déclarées vraies à priori : ce sont les axiomes. Sinon la véracité (ou la
fausseté) d’une proposition doit résulter d’une démonstration (d’une preuve).

Remarque : dans le cadre d’un cours de mathématiques, quand on énonce une proposition, c’est pour
affirmer qu’elle est vraie (et qu’on va la démontrer) !

Définition 1.1.3
Un théorème est une proposition vraie particulièrement importante.
Un lemme est une proposition vraie, utile à la démonstration d’une proposition plus importante.
Un corollaire est une proposition vraie, conséquence immédiate d’une autre proposition vraie.
Une conjecture est une proposition qu’on pense généralement vraie, sans en avoir de preuve.

Exemples :
– « l’axiome de récurrence » dans N, « l’axiome de la borne supérieure » dans R.
– « le théorème de Pythagore », le « théorème de Rolle », « le théorème de Bolzano-Weierstrass ».
– le « lemme des bergers », le « lemme de Gauss », le « lemme des noyaux ».
– la « conjecture de Syracuse », la « conjecture de Goldbach »
– la « conjecture de Fermat » est devenue le « grand théorème de Fermat » en 1994.


Mathématiques en MPSI mathprepa.fr Page 2
© Jean-Michel Ferrard
1.1 Rudiments de logique Chapitre 1 : Logique et ensembles


1.1.2 Ensembles, éléments
On ne se risque pas à donner une définition précise de ces notions premières.

Définition 1.1.4
On dit qu’un ensemble E est constitué d’éléments et qu’un élément a appartient à E (on écrit : a ∈ E)
ou n’appartient pas à E (on écrit : a ∈
/ E).
Deux ensembles E, F sont dits égaux (on note E = F ) s’ils sont constitués des mêmes éléments.
Par convention l’ensemble vide, noté ∅, est l’ensemble ne contenant aucun élément.

Quelques remarques
– Un même objet mathématique peut, selon les circonstances, être vu comme un ensemble, ou comme
un élément d’un ensemble. Par exemple, l’intervalle [0, 1] est un ensemble de nombres réels, mais c’est
également un élément de l’ensemble des intervalles de R.
– Un ensemble fini peut être défini en extension, c’est-à-dire par la liste (non ordonnée) de ses éléments.
C’est le cas par exemple de l’ensemble E = {1, 3, 6, 10, 15, 21, 28, 36, 45, 55}.
Dans une écriture comme {a, b, c, . . .} les éléments a, b, c, etc. sont à priori supposés distincts, et
l’ordre dans lequel ils sont donnés n’a aucune importance.
– Un ensemble E peut être défini en compréhension (par une propriété caractérisant ses éléments).
n o
Ainsi E = n(n+1)
2
, n ∈ N, 1 6 n 6 10 est une autre définition de {1, 3, 6, 10, 15, 21, 28, 36, 45, 55}.
– Il y a bien d’autres conventions pour définir ou nommer des ensembles. Par exemple :
· Si a, b sont deux réels, [a, b[ est l’ensemble des réels x qui vérifient a 6 x < b.
· Si E est un ensemble, P(E) est l’ensemble des parties de E.
· Certains ensembles ont des noms consacrés par l’usage : N, Z, Q, R, C, ...

Définition 1.1.5
Par convention l’ensemble vide, noté ∅, est l’ensemble ne contenant aucun élément.
Un ensemble {a}, formé d’un seul élément, est appelé un singleton.
Un ensemble {a, b}, formé de deux éléments distincts, ...