Raisonnement et vocabulaire ensembliste

Pour une implication $P\Rightarrow Q$ :

• sa contraposée est l'implication $\neg Q\Rightarrow \neg P$. Elle est logiquement équivalente à $P\Rightarrow Q$.
• sa réciproque est l'implication $Q\Rightarrow P$. Elle n'est pas logiquement équivalente à l'implication directe en général.

Pour toutes assertions $P$ et $Q$, on a les équivalences logiques suivantes (appelées tautologies) :

• $\neg (P\wedge Q)\iff (\neg P)\vee (\neg Q)$
• $\neg (P\vee Q)\iff (\neg P)\wedge (\neg Q)$

Soit $P(x)$ un prédicat sur $E$. On a les équivalences de négation :

• $\neg (\forall x\in E,P(x))\iff \exists x\in E,\neg P(x)$
• $\neg (\exists x\in E,P(x))\iff \forall x\in E,\neg P(x)$

Montrer que pour tout $n\in \mathbb{Z}$, le nombre $n(n+1)$ est pair.

• Cas 1 : $n$ est pair. Alors il existe $k\in \mathbb{Z}$ tel que $n=2k$. D'où $n(n+1)=2k(2k+1)=2[k(2k+1)]$, qui est pair.
• Cas 2 : $n$ est impair. Alors il existe $k\in \mathbb{Z}$ tel que $n=2k+1$. D'où $n(n+1)=(2k+1)(2k+2)=2(2k+1)(k+1)$, qui est pair.

Dans tous les cas, le nombre est pair.

Soit $n\in \mathbb{N}$. Montrer que si $n^2$ est impair, alors $n$ est impair. Par contraposition, supposons que $n$ n'est pas impair, donc que $n$ est pair. Il existe $k\in \mathbb{N}$ tel que $n=2k$. Alors $n^2=(2k{)}^2=4k^2=2(2k^2)$, qui est pair. Ainsi, la contraposée est démontrée, donc l'assertion d'origine est vraie.

Montrer que $\sqrt{2}\notin \mathbb{Q}$. Supposons par l'absurde que $\sqrt{2}\in \mathbb{Q}$. Alors il existe $p\in \mathbb{Z}$ et $q\in {\mathbb{N}}^{\ast }$ tels que $\sqrt{2}=\frac{p}{q}$, la fraction étant irréductible. En élevant au carré, $2=\frac{p^2}{q^2}$, soit $p^2=2q^2$. Donc $p^2$ est pair, ce qui implique $p$ pair. On pose $p=2k$. Alors $4k^2=2q^2$, d'où $q^2=2k^2$. Donc $q^2$ est pair, ce qui implique $q$ pair. Ainsi $p$ et $q$ sont tous deux pairs, ce qui contredit le fait que la fraction $\frac{p}{q}$ est irréductible. L'hypothèse de départ est fausse, d'où $\sqrt{2}\notin \mathbb{Q}$.

Soit $n_0\in \mathbb{N}$ et $P(n)$ une propriété dépendant de $n\ge n_0$. Si :

• Initialisation : $P(n_0)$ est vraie,
• Hérédité : pour tout entier $n\ge n_0$, si $P(n)$ est vraie, alors $P(n+1)$ est vraie,

alors la propriété $P(n)$ est vraie pour tout $n\ge n_0$.

Soit $P(n)$ un prédicat sur $n\ge n_0$ :

• Récurrence double : Si $P(n_0)$ et $P(n_0+1)$ sont vraies, et si pour tout $n\ge n_0$, $[P(n)\wedge P(n+1)]\Rightarrow P(n+2)$, alors $P(n)$ est vraie pour tout $n\ge n_0$.
• Récurrence forte : Si $P(n_0)$ est vraie, et si pour tout $n\ge n_0$, $\left[\forall k\in [[n_0,n]],P(k)\right]\Rightarrow P(n+1)$, alors $P(n)$ est vraie pour tout $n\ge n_0$.

Soient $A,B,C$ des parties de $E$.

• Distributivité :

$$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)\text{et}A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$$

• Lois de De Morgan ensemblistes :

$$(A\cup B{)}^c=A^c\cap B^c\text{et}(A\cap B{)}^c=A^c\cup B^c$$

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

$7\mid 91$ (car $91=7\times 13$) ; $1$ et $-1$ divisent tout entier ; tout entier divise $0$ ; mais $0$ ne divise que $0$. Les diviseurs de $12$ sont $\pm 1,\pm 2,\pm 3,\pm 4,\pm 6,\pm 12$.

Pour tous entiers $a,b,c$ :

• Transitivité : si $a\mid b$ et $b\mid c$, alors $a\mid c$.
• Combinaisons linéaires : si $a\mid b$ et $a\mid c$, alors $a\mid (bu+cv)$ pour tous $u,v\in \mathbb{Z}$.
• Si $a\mid b$ et $b\ne 0$, alors $|a|\le |b|$ : un entier non nul n'a qu'un nombre fini de diviseurs.

Soient $a\in \mathbb{Z}$ et $b\in {\mathbb{N}}^{\ast }$. Il existe un unique couple $(q,r)\in \mathbb{Z}\times \mathbb{N}$ tel que :

$$a=bq+r\text{et}0\le r<b.$$

L'entier $q$ est le quotient, $r$ le reste de la division euclidienne de $a$ par $b$. (Pour $b\in {\mathbb{Z}}^{\ast }$, l'énoncé subsiste avec $0\le r<|b|$.)

$47=5\times 9+2$ : quotient $9$, reste $2$. Attention aux négatifs : $-47=5\times (-10)+3$ : le reste est $3$ (toujours positif), pas $-2$. En Python, -47 % 5 renvoie bien 3.

Le reste de la division par $b$ classe les entiers en $b$ familles ($r=0,1,\dots ,b-1$). Par exemple, tout entier est de la forme $2k$ ou $2k+1$ (pair ou impair) : c'est ce qui fonde le raisonnement par disjonction des cas vu plus haut.

Diviseurs positifs de $12$ : $1,2,3,4,6,12$ ; de $18$ : $1,2,3,6,9,18$. Diviseurs communs positifs : $1,2,3,6$, donc $12\wedge 18=6$. Noter aussi $a\wedge 0=|a|$ pour $a\in {\mathbb{Z}}^{\ast }$.

Si $a=bq+r$, alors les diviseurs communs de $a$ et $b$ sont exactement les diviseurs communs de $b$ et $r$. En particulier :

$$a\wedge b=b\wedge r.$$

Soient $a,b\in \mathbb{Z}$ non tous deux nuls. L'ensemble des diviseurs communs à $a$ et $b$ est exactement l'ensemble des diviseurs de $a\wedge b$ :

$$d\mid a\text{ et }d\mid b⟺d\mid a\wedge b.$$

Pour tous $a,b\in \mathbb{Z}$ non nuls :

$$(a\wedge b)(a\vee b)=|ab|.$$

En pratique, on calcule donc $a\wedge b$ par l'algorithme d'Euclide, puis $a\vee b=\frac{|ab|}{a\wedge b}$ : l'algorithme d'Euclide fournit à la fois le PGCD et le PPCM. (Cette relation se justifie à l'aide de la décomposition en facteurs premiers présentée ci-dessous.)

$12\wedge 18=6$ et $12\vee 18=\frac{12\times 18}{6}=36$ : on vérifie bien $6\times 36=216=12\times 18$.

• Tout entier $n\ge 2$ admet au moins un diviseur premier (le plus petit diviseur $\ge 2$ de $n$ est premier).
• Si $n\ge 2$ est composé, il admet un diviseur premier $p\le \sqrt{n}$ (d'où le test de primalité : il suffit d'essayer les nombres premiers jusqu'à $\sqrt{n}$).

Les nombres premiers inférieurs à $50$ sont : $2,3,5,7,11,13,17,19,23,29,31,37,41,43,47$. Pour les dresser, on peut rayer de proche en proche les multiples stricts des entiers successifs (crible d'Ératosthène).

L'ensemble des nombres premiers est infini.

Tout entier naturel non nul $n$ s'écrit de manière unique (à l'ordre des facteurs près) comme produit de nombres premiers :

$$n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_r^{{\alpha }_r},p_1<p_2<\cdots <p_r\text{ premiers},{\alpha }_i\in {\mathbb{N}}^{\ast }.$$

(Pour $n=1$ : produit vide.) La démonstration de ce théorème est hors programme.

$360=2^3\times 3^2\times 5$,   $2026=2\times 1013$ ($1013$ est premier : aucun premier $\le 31<\sqrt{1013}$ ne le divise).

Sur les décompositions en facteurs premiers, le PGCD s'obtient en prenant pour chaque facteur premier le plus petit des deux exposants, le PPCM le plus grand. Ainsi $12=2^2\times 3$ et $18=2\times 3^2$ donnent $12\wedge 18=2\times 3=6$ et $12\vee 18=2^2\times 3^2=36$. Puisque $\min (\alpha ,\beta )+\max (\alpha ,\beta )=\alpha +\beta$ pour chaque paire d'exposants, on retrouve la relation $(a\wedge b)(a\vee b)=|ab|$.

$-3\in \mathbb{Z}\setminus \mathbb{N}$ ; $\frac{7}{4}=\frac{175}{100}=1,75\in \mathbb{D}\setminus \mathbb{Z}$ ; $\frac{1}{3}\in \mathbb{Q}\setminus \mathbb{D}$ ; $\sqrt{2}\in \mathbb{R}\setminus \mathbb{Q}$ (démontré par l'absurde dans la première section de ce chapitre).

Justifions que $\frac{1}{3}\notin \mathbb{D}$ : si l'on avait $\frac{1}{3}=\frac{a}{10^n}$, alors $10^n=3a$, donc $3$ diviserait $10^n$. Or la décomposition en facteurs premiers de $10^n$ est $2^n\times 5^n$, dans laquelle $3$ n'apparaît pas : par unicité de la décomposition, $3\nmid 10^n$ — contradiction.

La construction des ensembles de nombres usuels, en particulier celle de $\mathbb{R}$, est hors programme : leurs propriétés (règles de calcul usuelles, ordre) sont admises. L'étude approfondie de $\mathbb{R}$ (borne supérieure, approximations décimales) sera menée dans le chapitre consacré aux nombres réels et aux suites.

Soient $f:E\to F$ et $g:F\to G$ deux applications.

• Si $f$ et $g$ sont injectives, alors $g\circ f$ est injective.
• Si $f$ et $g$ sont surjectives, alors $g\circ f$ est surjective.
• Si $g\circ f$ est bijective, alors $f$ est injective et $g$ est surjective.

Si $f:E\to F$ et $g:F\to G$ sont deux applications bijectives, alors $g\circ f:E\to G$ est bijective et sa bijection réciproque vérifie :

$$(g\circ f{)}^{-1}=f^{-1}\circ g^{-1}$$