Le cours

Résumé en cinq points

Une implication n'est fausse que si l'hypothèse est vraie et la conclusion fausse. Sa négation est « $P$ et non $Q$ », sa contraposée lui est équivalente, sa réciproque ne l'est pas.
On nie une phrase quantifiée en échangeant $\forall$ et $\exists$ dans l'ordre puis en niant la fin. L'ordre des quantificateurs change le sens.
Les modes de raisonnement sont : direct, contraposition, absurde, disjonction des cas, analyse-synthèse, récurrence simple, double ou forte.
Le vocabulaire ensembliste se manipule par double inclusion, et De Morgan pour les ensembles n'est que De Morgan pour la logique.
L'image réciproque $f^{-1}(B)$ n'exige pas la bijectivité. Injectivité, surjectivité et bijectivité dépendent des ensembles de départ et d'arrivée.

Pourquoi ce chapitre

Ce chapitre donne la langue commune de toute l'année. Sans lui, on ne sait ni lire un énoncé, ni écrire une démonstration correcte. Ce n'est pas un cours de logique formelle ni de théorie des ensembles, c'est une boîte à outils de rédaction. Son acquisition est un objectif pour la fin du premier semestre : elle se construit progressivement, en même temps que les autres chapitres.

Aux concours, les points se perdent rarement sur une idée manquante. Ils se perdent sur :

une négation ratée ;
une équivalence écrite à la place d'une implication ;
une récurrence sans initialisation ;
une image réciproque confondue avec une bijection réciproque.

1Rudiments de logique

1.1Proposition, connecteurs

Définition 1.1Proposition

Une proposition est un énoncé qui est soit vrai, soit faux.

Exemple 1.2

« 7 est premier » est vraie. « $x > 0$ » n'est pas une proposition tant que $x$ n'est pas fixé.

La négation de $P$ est vraie exactement quand $P$ est fausse.
« $P$ et $Q$ » est vraie quand les deux le sont.
« $P$ ou $Q$ » est vraie dès que l'une au moins l'est : le ou mathématique est inclusif.

Loi 1.3Lois de De Morgan

La négation de « $P$ et $Q$ » est « non $P$ ou non $Q$ ».
La négation de « $P$ ou $Q$ » est « non $P$ et non $Q$ ».

Exemple 1.4

Dire qu'un réel $x$ n'appartient pas à $\intff{0}{1}$ revient à dire que $x < 0$ ou $x > 1$ .

1.2Implication, contraposition, équivalence

Définition 1.5Implication

L'implication $P \Rightarrow Q$ est fausse dans un seul cas : $P$ vraie et $Q$ fausse. Elle équivaut à « non $P$ ou $Q$ ». En particulier une implication à hypothèse fausse est vraie.

La négation de $P \Rightarrow Q$ est « $P$ et non $Q$ ». Réfuter une implication, c'est exhiber un contre-exemple.
Dans $P \Rightarrow Q$ , $P$ est une condition suffisante pour $Q$ , et $Q$ une condition nécessaire pour $P$ . Ce vocabulaire sert notamment aux raisonnements par analyse-synthèse.
La réciproque de $P \Rightarrow Q$ est $Q \Rightarrow P$ . Elle n'a aucune raison d'être vraie.
La contraposée de $P \Rightarrow Q$ est « non $Q \Rightarrow$ non $P$ ». Une implication et sa contraposée sont simultanément vraies ou fausses.

Exemple 1.6Réciproque fausse

« $n$ multiple de 4 $\Rightarrow$ $n$ pair » est vraie, sa réciproque est fausse avec $n = 2$ .

Définition 1.7Équivalence

$P \Leftrightarrow Q$ signifie que les deux implications sont vraies. On dit condition nécessaire et suffisante. On démontre en général les deux sens séparément.

Attention

Enchaîner des $\Leftrightarrow$ alors qu'une étape n'est qu'une implication est une faute classique. Élever au carré, multiplier par une quantité pouvant s'annuler, appliquer une fonction non injective : ces opérations ne donnent qu'une implication.

1.3Quantificateurs

Définition 1.8Quantificateurs

$\forall x \in E,\ P(x)$ affirme que $P(x)$ est vraie pour chaque $x$ de $E$ . Pour le prouver, on écrit « soit $x$ dans $E$ » et on ne suppose rien de particulier sur $x$ .
$\exists x \in E,\ P(x)$ affirme qu'au moins un élément convient. On l'établit en exhibant un $x$ , ou par un théorème d'existence.
$\exists !$ signifie « il existe un unique ».

Propriété 1.9Négation d'une phrase quantifiée

La négation de « $\forall x \in E,\ P(x)$ » est « $\exists x \in E,\ \text{non } P(x)$ ».
La négation de « $\exists x \in E,\ P(x)$ » est « $\forall x \in E,\ \text{non } P(x)$ ».

On échange les quantificateurs dans l'ordre, puis on nie la fin.

Exemple 1.10Convergence d'une suite

La suite $(u_n)$ converge vers $l$ signifie : $\begin{aligned} &\forall \varepsilon > 0,\ \exists N,\\ &\forall n \geqslant N,\ \abs{u_n - l} \leqslant \varepsilon. \end{aligned}$ Sa négation est : $\begin{aligned} &\exists \varepsilon > 0,\ \forall N,\\ &\exists n \geqslant N,\ \abs{u_n - l} > \varepsilon. \end{aligned}$ Savoir écrire cela sans hésiter est un exigible.

On peut permuter deux quantificateurs de même nature, jamais un $\forall$ et un $\exists$ .

Exemple 1.11Ordre des quantificateurs

« $\forall x \in \R,\ \exists y \in \R,\ y > x$ » est vraie : prendre $y = x + 1$ . « $\exists y \in \R,\ \forall x \in \R,\ y > x$ » est fausse. Dans le premier cas $y$ dépend de $x$ , dans le second il est commun à tous les $x$ .

Attention

Les quantificateurs ne sont pas des abréviations. On écrit soit une phrase française complète, soit une formule entièrement symbolique, jamais un mélange.

2Les modes de raisonnement

2.1Raisonnement direct

On suppose $P$ et on déduit $Q$ par une chaîne d'implications justifiées. C'est le mode par défaut.

2.2Par contraposition

Pour prouver $P \Rightarrow Q$ , on prouve « non $Q \Rightarrow$ non $P$ ».

Exemple 2.1

Si $n^2$ est pair alors $n$ est pair. Contraposée : si $n$ est impair alors $n^2$ est impair. Avec $n = 2k + 1$ : $n^2 = 2(2k^2 + 2k) + 1,$ qui est impair.

2.3Par l'absurde

Pour prouver $P$ , on suppose non $P$ et on obtient une contradiction.

Exemple 2.2 $\sqrt{2}$ est irrationnel

Supposons $\sqrt{2} = p/q$ avec $p$ et $q$ entiers sans facteur commun. Alors $p^2 = 2q^2$ , donc $p$ est pair, $p = 2m$ , puis $q^2 = 2m^2$ donc $q$ est pair. Contradiction.

Attention

Ne pas confondre avec la contraposée. La contraposée retourne une implication. L'absurde suppose le contraire de la conclusion visée. Quand la contraposée suffit, elle est plus lisible.

2.4Par disjonction des cas

On découpe en cas exhaustifs et on conclut dans chacun.

Exemple 2.3

$n(n + 1)$ est pair pour tout entier $n$ . Si $n$ est pair, le produit l'est. Sinon $n + 1$ est pair.

2.5Par analyse-synthèse

MéthodeAnalyse-synthèse

Analyse : on suppose qu'un objet convient et on déduit sa forme obligatoire. On obtient des candidats, donc une condition nécessaire.
Synthèse : on vérifie lesquels conviennent, ce qui donne la condition suffisante.

Exemple 2.4Parité d'une fonction

Toute fonction $f$ de $\R$ dans $\R$ s'écrit de façon unique comme somme d'une fonction paire et d'une fonction impaire.

Analyse : si $f = p + i$ alors $f(-x) = p(x) - i(x)$ , donc $\begin{aligned} p(x) &= \frac{f(x) + f(-x)}{2},\\ i(x) &= \frac{f(x) - f(-x)}{2}. \end{aligned}$ Synthèse : ces deux fonctions conviennent. Existence et unicité sont obtenues d'un coup.

2.6Par récurrence

MéthodeRécurrence simple

Pour $P(n)$ vraie pour tout $n \geqslant n_0$ , trois étapes nommées :

Initialisation : on vérifie $P(n_0)$ .
Hérédité : on fixe $n \geqslant n_0$ , on suppose $P(n)$ et on prouve $P(n + 1)$ .
Conclusion.

Variantes exigibles :

Récurrence double : on initialise $P(n_0)$ et $P(n_0 + 1)$ , puis on déduit $P(n + 2)$ de $P(n)$ et $P(n + 1)$ . Utile pour $u_{n+2} = a u_{n+1} + b u_n$ .
Récurrence forte : on suppose $P(k)$ pour tout $k$ entre $n_0$ et $n$ . Exemple : tout entier $n \geqslant 2$ admet un diviseur premier.

Toute construction et toute axiomatique de $\N$ sont hors programme. On admet donc que toute partie non vide de $\N$ a un plus petit élément, propriété qui légitime le principe de récurrence.

Attention

Erreurs classiques :

oublier l'initialisation : la propriété « $n = n + 1$ » est héréditaire et fausse ;
écrire « supposons $P(n)$ pour tout $n$ », ce qui est la conclusion ;
ne pas dire à partir de quel rang on démarre.

3Ensembles

Un ensemble est une collection d'objets. On écrit $x \in E$ ou $x \notin E$ . L'ensemble vide, noté $\varnothing$ , n'a aucun élément.

Définition 3.1Inclusion

$A \subset E$ signifie que tout élément de $A$ est élément de $E$ . On dit que $A$ est une partie de $E$ .

Pour prouver $A = B$ , on procède par double inclusion : $A \subset B$ et $B \subset A$ .

Définition 3.2Opérations sur les parties de $E$

réunion $A \cup B$ ;
intersection $A \cap B$ ;
différence $A \setminus B$ , formée des éléments de $A$ qui ne sont pas dans $B$ ;
complémentaire de $A$ dans $E$ , noté $E \setminus A$ , $\overline{A}$ ou $A^c$ .

Propriété 3.3Lois de De Morgan ensemblistes

Le complémentaire de $A \cup B$ est l'intersection des complémentaires.
Le complémentaire de $A \cap B$ est la réunion des complémentaires.

Ce sont les lois logiques vues plus haut, traduites. L'intersection est de plus distributive sur la réunion, et réciproquement.

Définition 3.4Produit cartésien

$E_1 \times \cdots \times E_n$ est l'ensemble des $n$ -uplets $(x_1, \dots, x_n)$ avec $x_i \in E_i$ .

Attention

$(a, b)$ et $(b, a)$ diffèrent en général.

Définition 3.5Ensemble des parties

$\mathcal{P}(E)$ est l'ensemble dont les éléments sont les parties de $E$ .

Exemple 3.6

Si $E = \{1, 2\}$ alors $\mathcal{P}(E) = \{\varnothing, \{1\}, \{2\}, E\}$ .

Attention

$\{1\} \subset E$ et $\{1\} \in \mathcal{P}(E)$ , mais $1 \in E$ et $1 \notin \mathcal{P}(E)$ .

Définition 3.7Recouvrement disjoint, partition

Une famille de parties de $E$ recouvre $E$ si leur réunion vaut $E$ . Le recouvrement est disjoint si les parties sont deux à deux d'intersection vide. Une partition de $E$ est un recouvrement disjoint par des parties non vides.

Exemple 3.8

Les classes de parité partitionnent $\Z$ en pairs et impairs.

4Ensembles de nombres usuels

La construction de $\N$ , $\Z$ , $\Q$ , $\R$ est hors programme. On les utilise.

4.1Divisibilité et division euclidienne

Définition 4.1Divisibilité

Dans $\Z$ , $a$ divise $b$ s'il existe un entier $k$ tel que $b = ak$ . On dit que $a$ est un diviseur de $b$ et $b$ un multiple de $a$ .

Théorème 4.2Division euclidienne

Hypothèses

$a \in \Z$ ;
$b \in \N^*$ .

Alors il existe un unique couple $(q, r)$ d'entiers avec $a = bq + r \quad \text{et} \quad 0 \leqslant r < b.$

L'idée d'existence : on prend pour $q$ le plus grand entier tel que $bq \leqslant a$ , ce qui existe grâce à la propriété du plus petit élément. L'unicité vient du fait que deux restes possibles diffèrent d'un multiple de $b$ tout en étant dans un intervalle de longueur $b$ .

4.2PGCD, PPCM, algorithme d'Euclide

Définition 4.3PGCD et PPCM

Le PGCD de $a$ et $b$ , non tous deux nuls, est le plus grand élément de l'ensemble des diviseurs communs à $a$ et $b$ pour l'ordre de $\Z$ . Cet ensemble est non vide et majoré, donc ce plus grand élément existe. Le PPCM est le plus petit multiple commun strictement positif.

MéthodeAlgorithme d'Euclide

Il repose sur le fait que les diviseurs communs de $a$ et $b$ sont exactement ceux de $b$ et $r$ , où $r$ est le reste de $a$ par $b$ .

Diviser $a$ par $b$ pour obtenir le reste $r$ .
Recommencer avec $b$ et $r$ , jusqu'à un reste nul.
Le dernier reste non nul est le PGCD.

Exemple 4.4PGCD de 252 et 198

$\begin{aligned} 252 &= 1 \times 198 + 54,\\ 198 &= 3 \times 54 + 36,\\ 54 &= 1 \times 36 + 18,\\ 36 &= 2 \times 18 + 0. \end{aligned}$ Le PGCD vaut 18.

4.3Nombres premiers

Définition 4.5Nombre premier

Un entier $p \geqslant 2$ est premier si ses seuls diviseurs positifs sont 1 et $p$ .

Théorème 4.6Infinité des nombres premiers

L'ensemble des nombres premiers est infini.

Démonstration

Par l'absurde, démonstration d'Euclide. S'il n'y avait qu'un nombre fini de premiers $p_1, \dots, p_r$ , on pose $N = p_1 \cdots p_r + 1$ . Cet entier est au moins 2, donc il admet un diviseur premier $p$ , qui est l'un des $p_i$ . Ce $p$ divise le produit et divise $N$ , donc il divise 1. Contradiction.

Tout entier $n \geqslant 2$ admet une décomposition en produit de facteurs premiers, existante et unique. Le programme indique explicitement que la démonstration est hors programme. On l'utilise pour calculer PGCD et PPCM, en prenant respectivement le minimum et le maximum des exposants.

4.4Décimaux, rationnels, irrationnels

Un décimal est un rationnel de la forme $a/10^n$ .
Un rationnel est un quotient d'entiers.
Un irrationnel est un réel non rationnel, par exemple $\sqrt{2}$ .

5Applications

5.1Définitions

Définition 5.1Application

Une application $f$ de $E$ dans $F$ associe à tout élément de $E$ un unique élément de $F$ . Le point de vue est intuitif et le programme ne distingue pas fonction et application. On note $\mathcal{F}(E, F)$ ou $F^E$ l'ensemble des applications de $E$ dans $F$ . Le graphe de $f$ est l'ensemble des couples $(x, f(x))$ .

Définition 5.2Famille

Une famille d'éléments de $E$ indexée par $I$ est une application de $I$ dans $E$ , notée $(x_i)_{i \in I}$ .

Définition 5.3Fonction indicatrice

La fonction indicatrice d'une partie $A$ de $E$ , notée $\mathbf{1}_A$ , vaut 1 sur $A$ et 0 ailleurs.

Une relation utile : $\mathbf{1}_{A \cap B} = \mathbf{1}_A \times \mathbf{1}_B$ .

Définition 5.4Restriction, prolongement

La restriction de $f$ à $A$ se note $f|_A$ . Le prolongement est l'opération inverse : on étend le domaine en conservant les valeurs.

5.2Image directe, image réciproque

Définition 5.5Images directe et réciproque

Image directe de $A \subset E$ : $f(A)$ est l'ensemble des $f(x)$ pour $x \in A$ .
Image réciproque de $B \subset F$ : $f^{-1}(B)$ est l'ensemble des $x$ de $E$ tels que $f(x) \in B$ .

La notation $f^{-1}(B)$ a un sens même si $f$ n'est pas bijective : elle ne présuppose aucune réciproque.

Exemple 5.6

Avec $f(x) = x^2$ de $\R$ dans $\R$ : $\begin{aligned} f^{-1}(\intff{1}{4}) &= \intff{-2}{-1} \cup \intff{1}{2},\\ f(\R) &= \R_+. \end{aligned}$

Attention

$y \in f(A)$ signifie qu'il existe $x \in A$ avec $y = f(x)$ , pas que tout antécédent de $y$ soit dans $A$ .

5.3Composition

Définition 5.7Composée

$(g \circ f)(x) = g(f(x))$ , définie quand l'ensemble d'arrivée de $f$ est inclus dans celui de départ de $g$ . La composition est associative, non commutative.

5.4Injection, surjection, bijection

Définition 5.8Injection, surjection, bijection

$f$ est injective si deux éléments distincts ont des images distinctes. En pratique, on montre que $f(x) = f(y)$ entraîne $x = y$ .
$f$ est surjective de $E$ sur $F$ si tout élément de $F$ a au moins un antécédent, c'est-à-dire $f(E) = F$ .
$f$ est bijective si elle est injective et surjective, autrement dit si tout élément de $F$ a exactement un antécédent.

Une bijection $f$ admet une unique application réciproque $f^{-1}$ de $F$ dans $E$ vérifiant $f^{-1} \circ f = \mathrm{id}_E$ et $f \circ f^{-1} = \mathrm{id}_F$ .

Propriété 5.9Composition (exigible)

La composée de deux injections est injective.
La composée de deux surjections est surjective.
La composée de deux bijections $f$ et $g$ est bijective, et $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ , dans l'ordre inversé.

Démonstration

Pour la réciproque de $g \circ f$ , on vérifie que $(f^{-1} \circ g^{-1}) \circ (g \circ f) = \mathrm{id}$ par associativité, et de même dans l'autre sens.

Remarque

Compatibilité des notations : si $f$ est bijective, l'image réciproque de $B$ par $f$ coïncide avec l'image directe de $B$ par l'application $f^{-1}$ . C'est ce qui rend la notation cohérente.

Exemple 5.10Récapitulatif avec $x \mapsto x^2$

De $\R$ dans $\R$ : ni injective ni surjective.
De $\R$ dans $\R_+$ : surjective, non injective.
De $\R_+$ dans $\R$ : injective, non surjective.
De $\R_+$ dans $\R_+$ : bijective, de réciproque la racine carrée.

À retenir

L'injectivité et la surjectivité dépendent des ensembles de départ et d'arrivée, pas de la seule formule.

Méthodes

MéthodeRéflexes du chapitre

Pour prouver une égalité d'ensembles, faire une double inclusion, ou une chaîne d'équivalences si chaque étape est réversible.
Pour prouver $\forall x \in E,\ P(x)$ , commencer par « soit $x$ dans $E$ ».
Pour réfuter un énoncé universel, un contre-exemple suffit. Pour le prouver, aucun exemple ne suffit.
Pour une injectivité, partir de $f(x) = f(y)$ . Pour une surjectivité, se donner $y$ dans $F$ et résoudre $f(x) = y$ en $x$ , ce qui est une analyse-synthèse déguisée.
Pour un problème d'existence et d'unicité, penser analyse-synthèse.
Pour une propriété d'entiers, penser division euclidienne, disjonction selon le reste, ou récurrence forte.

Ce qu'il faut savoir refaire en khôlle

Nier une phrase à trois quantificateurs, par exemple la définition de la limite d'une suite.
Démontrer par contraposition que si $n^2$ est pair alors $n$ est pair, puis par l'absurde que $\sqrt{2}$ est irrationnel.
Mener une analyse-synthèse complète : décomposition d'une fonction en partie paire plus partie impaire.
Rédiger une récurrence simple, une double et une forte en nommant les trois étapes.
Démontrer les lois de De Morgan ensemblistes par double inclusion.
Énoncer la division euclidienne avec ses hypothèses exactes et faire tourner l'algorithme d'Euclide.
Démontrer que l'ensemble des nombres premiers est infini.
Discuter injectivité, surjectivité, bijectivité de $x \mapsto x^2$ selon les ensembles de départ et d'arrivée, et calculer une image réciproque.

Méthodes et exercices

Les résultats à connaître

Lois de De Morgan logiques, non(P et Q) équivaut à (non P ou non Q), et l'analogue pour le ou. Exigible avec démonstration, par table de vérité.
Une implication P ⇒ Q équivaut à sa contraposée non Q ⇒ non P, et sa négation est (P et non Q). Exigible avec démonstration.
Négation d'une phrase quantifiée, on échange ∀ et ∃ dans l'ordre puis on nie la fin. Exigible, à savoir appliquer sans hésiter.
Principe de récurrence simple, double, forte. Admis, toute axiomatique de N est hors programme. La rédaction en trois étapes est exigible.
Théorème de la division euclidienne. Pour a dans Z et b dans N*, existence et unicité de (q, r) dans Z × N avec a = bq + r et 0 ≤ r < b. Exigible avec démonstration.
Existence du PGCD de deux entiers non tous deux nuls. Exigible, l'ensemble des diviseurs communs est non vide et fini.
Lemme d'Euclide. Si a = bq + r, les diviseurs communs de a et b sont ceux de b et r. Exigible avec démonstration, c'est le moteur de l'algorithme.
Tout entier n ≥ 2 admet un diviseur premier. Exigible avec démonstration, par récurrence forte ou par le plus petit diviseur supérieur à 1.
L'ensemble des nombres premiers est infini. Exigible avec démonstration.
Existence et unicité de la décomposition en facteurs premiers. Admise, démonstration hors programme. Application au calcul du PGCD et du PPCM par les exposants.
√2 est irrationnel. Exigible avec démonstration.
Lois de De Morgan ensemblistes et distributivité de ∩ sur ∪ et de ∪ sur ∩. Exigibles avec démonstration par double inclusion.
La composée de deux injections est injective, celle de deux surjections est surjective, celle de deux bijections est bijective et sa réciproque est f⁻¹ ∘ g⁻¹. Exigibles avec démonstration.
Si f est bijective, l'image réciproque de B par f est l'image directe de B par f⁻¹. Exigible.
Hors programme en PCSI, à signaler si un exercice les demande, le théorème de Bézout, le lemme de Gauss, les congruences comme théorie, et toute étude systématique de la logique.

Clés de démonstration

Division euclidienne. Existence, l'ensemble des entiers k tels que bk ≤ a est non vide et majoré, on prend son plus grand élément q et on pose r = a − bq. Par maximalité, b(q + 1) > a donc r < b. Unicité, deux couples donnent b(q − q') = r' − r, et une différence de restes est strictement comprise entre −b et b, donc nulle. Astuce, un multiple de b dans l'intervalle ouvert de −b à b est forcément 0.

Lemme d'Euclide. Si d divise a et b, il divise a − bq = r. Si d divise b et r, il divise bq + r = a. Les deux ensembles de diviseurs communs coïncident donc leurs plus grands éléments aussi. Astuce, on ne compare pas les PGCD, on compare les ensembles.

Diviseur premier. Récurrence forte, si n est premier c'est fini, sinon n = ab avec 2 ≤ a < n, et a a un diviseur premier par hypothèse. Astuce, récurrence forte parce que le diviseur a est quelconque en dessous de n.

Infinité des premiers. Par l'absurde, avec une liste finie on forme le produit plus 1. Ce nombre a un diviseur premier, qui divise aussi le produit, donc divise 1. Astuce, un diviseur commun à N et N − 1 divise leur différence.

√2 irrationnel. Par l'absurde avec une fraction irréductible p/q, p² = 2q² donne p pair, puis q pair. Astuce, la contraposée « n² pair ⇒ n pair » est démontrée à part, avant.

De Morgan ensembliste. On prend x dans le complémentaire de A ∪ B, on traduit par « non (x ∈ A ou x ∈ B) », on applique De Morgan logique. Astuce, chaque énoncé ensembliste est une phrase logique sur un x générique.

Réciproque d'une composée. On vérifie (f⁻¹ ∘ g⁻¹) ∘ (g ∘ f) = id par associativité, puis dans l'autre sens. Astuce, l'unicité de la réciproque fait le reste.

Analyse-synthèse. Pour la décomposition paire plus impaire, on suppose l'écriture, on évalue en −x, on résout le système en p(x) et i(x), puis on vérifie que les candidats conviennent. Astuce, l'analyse donne l'unicité, la synthèse donne l'existence.

Exemples et contre-exemples à connaître

« ∀x ∈ R, ∃y ∈ R, y > x » est vraie et « ∃y ∈ R, ∀x ∈ R, y > x » est fausse. C'est le contre-exemple qui interdit de permuter ∀ et ∃.
« Si 1 = 0 alors 2 = 3 » est une implication vraie. Une hypothèse fausse rend l'implication vraie, ce qui trouble au début.
La propriété « n = n + 1 » est héréditaire et fausse pour tout n. Sans initialisation, une récurrence ne prouve rien.
x ↦ x² est injective de R+ dans R, surjective de R dans R+, bijective de R+ dans R+, ni l'un ni l'autre de R dans R. La formule ne suffit pas, les ensembles comptent.
Avec f(x) = x², f⁻¹({−1}) = ∅ et f⁻¹({4}) = {−2, 2}. L'image réciproque existe sans bijection et peut être vide ou avoir plusieurs éléments.
Toujours avec f(x) = x², A = {−1}, B = {1}, on a f(A ∩ B) = ∅ mais f(A) ∩ f(B) = {1}. L'image directe ne commute pas avec l'intersection, seule l'inclusion f(A ∩ B) ⊂ f(A) ∩ f(B) est vraie.
f l'inclusion de N dans Z et g la valeur absolue de Z dans N. Alors g ∘ f = id_N est bijective, pourtant f n'est pas surjective et g n'est pas injective.
Si E = {1, 2}, alors {1} ⊂ E et {1} ∈ P(E), mais 1 ∉ P(E). Appartenance et inclusion ne vivent pas au même étage.
√2 × √2 = 2. Un produit de deux irrationnels peut être rationnel, alors que la somme d'un rationnel et d'un irrationnel est toujours irrationnelle.
La négation de « (u_n) converge vers l » est « il existe ε > 0 tel que pour tout N il existe n ≥ N avec |u_n − l| > ε ». Trois quantificateurs, c'est le test de khôlle.

Techniques du chapitre

Nier une phrase quantifiée. Mini-exercice, nier « f est majorée sur R », c'est-à-dire « ∃M ∈ R, ∀x ∈ R, f(x) ≤ M ». Négation, « ∀M ∈ R, ∃x ∈ R, f(x) > M ». On lit, aussi grand que soit M, f le dépasse quelque part.

Contraposée pour un énoncé sur les entiers. Mini-exercice, montrer que si 3 divise a² alors 3 divise a. Contraposée, si 3 ne divise pas a, alors a = 3k + 1 ou a = 3k + 2, donc a² = 3(3k² + 2k) + 1 ou a² = 3(3k² + 4k + 1) + 1, jamais multiple de 3.

Analyse-synthèse pour une équation. Mini-exercice, résoudre √(x + 1) = x − 1. Analyse, si x convient alors x ≥ 1 et x + 1 = (x − 1)², soit x² − 3x = 0, donc x = 0 ou x = 3. Synthèse, x = 0 donne 1 = −1, rejeté. x = 3 donne 2 = 2, accepté. Unique solution 3.

Récurrence double. Mini-exercice, u₀ = 1, u₁ = 3, u_n+2 = 3u_n+1 − 2u_n. Montrer u_n = 2ⁿ⁺¹ − 1. Initialisation, 1 et 3 conviennent. Hérédité, 3(2ⁿ⁺² − 1) − 2(2ⁿ⁺¹ − 1) = 3·2ⁿ⁺² − 2ⁿ⁺² − 1 = 2ⁿ⁺³ − 1. Conclusion pour tout n.

Double inclusion ou chaîne d'équivalences. Mini-exercice, f⁻¹(B ∩ C) = f⁻¹(B) ∩ f⁻¹(C). Pour x dans E, x ∈ f⁻¹(B ∩ C) équivaut à f(x) ∈ B et f(x) ∈ C, qui équivaut à x ∈ f⁻¹(B) et x ∈ f⁻¹(C). Chaque étape est une équivalence, une seule chaîne suffit. L'image réciproque commute avec tout, l'image directe non.

Bijectivité par résolution de f(x) = y. Mini-exercice, f définie sur R privé de 1 par f(x) = (x + 1)/(x − 1), à valeurs dans R privé de 1. Pour y ≠ 1, l'équation y(x − 1) = x + 1 donne x(y − 1) = y + 1, donc x = (y + 1)/(y − 1), qui est bien différent de 1. Unique antécédent, f est bijective, et f⁻¹ = f.

Disjonction selon le reste. Mini-exercice, le reste de n² dans la division par 4 vaut 0 ou 1. Si n = 2k, n² = 4k². Si n = 2k + 1, n² = 4(k² + k) + 1. Conséquence, un entier de la forme 4m + 3 n'est jamais somme de deux carrés.

Algorithme d'Euclide. Mini-exercice, PGCD de 1071 et 462. 1071 = 2 × 462 + 147, 462 = 3 × 147 + 21, 147 = 7 × 21 + 0. Le PGCD vaut 21.

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

Exercice 1. Vrai ou faux, avec négation

Classiques de khôlle et concours · Niveau khôlle

Pour chaque phrase, dire si elle est vraie et écrire sa négation. (a) ∀n ∈ N, ∃m ∈ N, m > n. (b) ∃m ∈ N, ∀n ∈ N, m > n. (c) ∀x ∈ R, ∀y ∈ R, (xy = 0 ⇒ x = 0 ou y = 0). (d) ∀x ∈ R, ∃y ∈ R, x + y = 0.

Technique négation mécanique des quantificateurs.

Voir le corrigé

(a) vraie, prendre m = n + 1. Négation, ∃n ∈ N, ∀m ∈ N, m ≤ n. 2. (b) fausse, car pour m fixé, n = m ne vérifie pas m > n. Négation, ∀m ∈ N, ∃n ∈ N, m ≤ n, qui est vraie. 3. (c) vraie, c'est l'intégrité de R. Négation, ∃x ∈ R, ∃y ∈ R, xy = 0 et x ≠ 0 et y ≠ 0. 4. (d) vraie avec y = −x. Négation, ∃x ∈ R, ∀y ∈ R, x + y ≠ 0.

piège : Nier une implication en niant les deux membres, alors que non(P ⇒ Q) est (P et non Q).

Exercice 2. Irrationalité de √2 + √3

Classiques de khôlle et concours · Niveau khôlle

Montrer que √2 est irrationnel, puis que √2 + √3 l'est.

Technique absurde et manipulation algébrique.

Voir le corrigé

Si √2 = p/q irréductible, alors p² = 2q², donc p est pair, p = 2m, puis q² = 2m², donc q est pair, contradiction avec l'irréductibilité. 2. Supposons r = √2 + √3 rationnel. Alors r − √2 = √3, et en élevant au carré, r² − 2r√2 + 2 = 3, donc √2 = (r² − 1)/(2r), rationnel car r ≠ 0. Contradiction avec 1.

piège : Oublier de justifier r ≠ 0 avant de diviser.

Exercice 3. Écriture binaire par récurrence forte

Classiques de khôlle et concours · Niveau khôlle

Montrer que tout entier n ≥ 1 est somme de puissances de 2 deux à deux distinctes.

Technique récurrence forte avec choix d'un plus grand élément.

Voir le corrigé

Initialisation, 1 = 2⁰. 2. Soit n ≥ 2, on suppose le résultat pour tout entier de 1 à n − 1. L'ensemble des k tels que 2^k ≤ n est fini et non vide, on prend son plus grand élément k. 3. Alors 2^k ≤ n < 2^k+1, donc 0 ≤ n − 2^k < 2^k. Si n − 2^k = 0, c'est fini. Sinon, par hypothèse, n − 2^k est somme de puissances distinctes, toutes strictement inférieures à 2^k puisque leur somme l'est. 4. On ajoute 2^k, qui n'apparaissait pas, et on conclut.

piège : Utiliser la récurrence simple alors que n − 2^k n'est pas n − 1.

Exercice 4. Équation fonctionnelle par analyse-synthèse

Classiques de khôlle et concours · Niveau khôlle

Déterminer les applications f de R dans R telles que, pour tout réel x, f(x) + 2f(1 − x) = x².

Technique substituer x par 1 − x pour obtenir un système.

Voir le corrigé

Analyse. Si f convient, en remplaçant x par 1 − x, f(1 − x) + 2f(x) = (1 − x)². 2. On a deux équations en f(x) et f(1 − x). On multiplie la seconde par 2 et on soustrait la première, 3f(x) = 2(1 − x)² − x², donc f(x) = (x² − 4x + 2)/3. 3. Synthèse. Avec cette formule, f(1 − x) = ((1 − x)² − 4(1 − x) + 2)/3 = (x² + 2x − 1)/3, et f(x) + 2f(1 − x) = (x² − 4x + 2 + 2x² + 4x − 2)/3 = x². 4. Unique solution.

piège : S'arrêter après l'analyse. Sans synthèse on a seulement prouvé qu'il y a au plus une solution.

Exercice 5. Égalités d'ensembles

Classiques de khôlle et concours · Niveau khôlle

Soient A, B, C trois parties d'un ensemble E. (a) Montrer que si A ∪ B = A ∩ B alors A = B. (b) Montrer que si A ∩ B = A ∩ C et A ∪ B = A ∪ C alors B = C.

Technique double inclusion avec disjonction selon l'appartenance à A.

Voir le corrigé

(a) Soit x ∈ A. Alors x ∈ A ∪ B = A ∩ B, donc x ∈ B. Par symétrie B ⊂ A. 2. (b) Soit x ∈ B. Si x ∈ A, alors x ∈ A ∩ B = A ∩ C, donc x ∈ C. Si x ∉ A, alors x ∈ A ∪ B = A ∪ C, et comme x ∉ A, x ∈ C. 3. Donc B ⊂ C, et l'hypothèse est symétrique en B et C, d'où C ⊂ B.

piège : Écrire des égalités d'ensembles par calcul formel sans revenir à un élément.

Exercice 6. Images directes et réciproques

Classiques de khôlle et concours · Niveau khôlle

Soit f de E dans F, A ⊂ E et B ⊂ F. Montrer f(f⁻¹(B)) ⊂ B, puis A ⊂ f⁻¹(f(A)). Montrer que la première inclusion est une égalité si f est surjective, la seconde si f est injective. Donner un contre-exemple à chaque égalité.

Technique revenir aux définitions, y ∈ f(A) signifie qu'il existe x ∈ A avec y = f(x).

Voir le corrigé

Si y ∈ f(f⁻¹(B)), il existe x avec f(x) ∈ B et y = f(x), donc y ∈ B. 2. Si x ∈ A, alors f(x) ∈ f(A), donc x ∈ f⁻¹(f(A)). 3. Si f est surjective et y ∈ B, il existe x avec f(x) = y, alors x ∈ f⁻¹(B) et y ∈ f(f⁻¹(B)). 4. Si f est injective et x ∈ f⁻¹(f(A)), il existe a ∈ A avec f(x) = f(a), donc x = a ∈ A. 5. Contre-exemples avec f(x) = x² de R dans R, B = R donne f(f⁻¹(R)) = R+ ≠ R, et A = R+ donne f⁻¹(f(R+)) = R ≠ R+.

piège : Croire que f⁻¹(f(A)) = A en général.

Exercice 7. Composition et bijections

Classiques de khôlle et concours · Niveau khôlle

Soient f de E dans F et g de F dans E avec g ∘ f = id_E. Montrer que f est injective et g surjective. Montrer que si de plus f ∘ g = id_F, alors f est bijective de réciproque g.

Technique composer par la bonne application.

Voir le corrigé

Si f(x) = f(y), on applique g, x = y. 2. Pour x ∈ E, x = g(f(x)) a un antécédent par g. 3. Si f ∘ g = id_F, alors f est aussi surjective, car y = f(g(y)). Donc f est bijective. 4. On compose g ∘ f = id_E à droite par f⁻¹, g = f⁻¹.

piège : Conclure que f est bijective avec la seule hypothèse g ∘ f = id_E. L'exemple 7 de la section 3 montre que non.

Exercice 8. Une fraction toujours irréductible

Classiques de khôlle et concours · Niveau écrit CCINP

Montrer que pour tout entier n ≥ 1, les entiers n² + n + 1 et n² + 2n + 2 sont premiers entre eux.

Technique lemme d'Euclide en cascade.

Voir le corrigé

Un diviseur commun d divise la différence, (n² + 2n + 2) − (n² + n + 1) = n + 1. 2. Donc d divise n² + n + 1 et n + 1, et comme n² + n + 1 = n(n + 1) + 1, d divise 1. 3. Le PGCD vaut 1.

piège : Chercher à factoriser au lieu de soustraire.

Exercice 11. Une bijection de N sur Z

Classiques de khôlle et concours · Niveau khôlle

Soit f définie sur N par f(n) = n/2 si n est pair et f(n) = −(n + 1)/2 si n est impair. Montrer que f est une bijection de N sur Z.

Technique disjonction des cas selon la parité, puis résolution de f(n) = m.

Voir le corrigé

f est à valeurs dans Z, les pairs donnent 0, 1, 2, …, les impairs donnent −1, −2, …. 2. Surjectivité, pour m ≥ 0, n = 2m convient, pour m < 0, n = −2m − 1 est impair et convient. 3. Injectivité, un pair a une image positive ou nulle, un impair une image strictement négative, donc f(n) = f(n') impose la même parité, puis n = n' par calcul dans chaque cas.

piège : Oublier que 0 est atteint une seule fois, par n = 0.

Exercice 9. Nombres premiers de la forme 4k + 3

Approfondissement · Niveau écrit Centrale

Montrer qu'il existe une infinité de nombres premiers de la forme 4k + 3.

Technique la preuve d'Euclide adaptée avec un produit bien choisi.

Voir le corrigé

Un produit de deux entiers de la forme 4a + 1 est encore de cette forme, (4a + 1)(4b + 1) = 4(4ab + a + b) + 1. 2. Par l'absurde, soit p₁, …, p_r la liste finie des premiers de la forme 4k + 3, et N = 4p₁…p_r − 1. N est impair, au moins égal à 2, et de la forme 4m + 3. 3. On décompose N en facteurs premiers, tous impairs, donc de la forme 4k + 1 ou 4k + 3. S'ils étaient tous de la forme 4k + 1, N le serait aussi par 1. 4. Donc un facteur premier q de N est de la forme 4k + 3, donc q est l'un des p_i, donc q divise 4p₁…p_r et N, donc q divise 1. Contradiction.

piège : Prendre N = 4p₁…p_r + 1, qui est de la forme 4m + 1 et ne permet pas de conclure.

Exercice 10. Théorème de Cantor

Approfondissement · Niveau écrit X ou ENS

Soit E un ensemble. Montrer qu'aucune application f de E dans P(E) n'est surjective.

Technique argument diagonal, l'ensemble des x qui n'appartiennent pas à leur image. Cet exercice n'utilise que les définitions du programme.

Voir le corrigé

Soit A l'ensemble des x ∈ E tels que x ∉ f(x). C'est une partie de E. 2. Supposons A = f(a) pour un a ∈ E. 3. Si a ∈ A, alors par définition de A, a ∉ f(a) = A. Si a ∉ A, alors a ∉ f(a), donc a ∈ A. Contradiction dans les deux cas. 4. A n'a pas d'antécédent, f n'est pas surjective.

piège : Penser que A pourrait être vide et que cela sauve l'argument. Même vide, A est une partie de E sans antécédent.

Erreurs fréquentes

Écrire une chaîne de ⇔ alors qu'une étape n'est qu'une ⇒, en particulier après une élévation au carré.
Nier ∀x, P(x) ⇒ Q(x) par ∀x, non P(x), au lieu de ∃x, P(x) et non Q(x).
Oublier l'initialisation ou supposer P(n) « pour tout n » dans l'hérédité.
Confondre f⁻¹(B) image réciproque, définie toujours, et f⁻¹ bijection réciproque, définie seulement si f est bijective.
Utiliser Bézout ou Gauss en PCSI sans savoir que ces résultats ne sont pas au programme, alors qu'une soustraction et le lemme d'Euclide suffisent.

Fiche de cours rédigée à partir du programme officiel de PCSI (2021), section « Raisonnement et vocabulaire ensembliste » du premier semestre. Elle couvre les rudiments de logique, les modes de raisonnement, le vocabulaire des ensembles, les ensembles de nombres usuels avec leurs propriétés arithmétiques de base, et les applications.