Lycée Louis-Le-Grand, Paris 2015/2016
MPSI 4 – Mathématiques
A. Troesch
Fondements 2 – Ensembles
Exercice 1 – Montrer que X ⊂ Y si et seulement s’il existe Z tel que Z ∩ X ⊂ Z ∩ Y et Z ∪ X ⊂ Z ∪ Y .
Exercice 2 – Montrer que :
a) X \ (Y ∪ Z) = (X \ Y ) ∩ (X \ Z); b) X \ (Y ∩ Z) = (X \ Y ) ∪ (X \ Z);
c) X \ (Y \ Z) = (X \ Y ) ∪ (X ∩ Z); d) (X \ Y ) \ Z = X \ (Y ∪ Z).
Exercice 3 – Soit k un entier au moins égal à 2, et soient A1 , . . . , Ak des parties d’un ensemble. Montrer :
A1 ∪ · · · ∪ Ak = (A1 − A2 ) ∪ (A2 − A3 ) ∪ · · · ∪ (Ak−1 − Ak ) ∪ (Ak − A1 ) ∪ (A1 ∩ · · · ∩ Ak ).
Exercice 4 – Soit E un ensemble éventuellement vide, dont les éléments sont des ensembles. On dit que E est transitif
si : ∀x, x ∈ E =⇒ x ⊂ E.
1. Les ensembles suivants sont-ils transitifs (∅ désigne l’ensemble vide) :
(a) E1 = ∅ (b) E2 = {∅} (c) E3 = {∅, {∅}} (d) {{∅}}.
2. Soit X un ensemble quelconque. On note P0 (X) = X, et P1 (X) = P(X), l’ensemble des parties de X. On définit
alors par récurrence sur n, pour tout n > 1 : Pn+1 (X) = P(Pn (X)).
(a) Soit X = {1, 2}. Déterminer P2 (X).
(b) Déterminer P1 (∅), P2 (∅), P3 (∅).
(c) Montrer que si X est transitif, alors l’ensemble P(X) est transitif.
(d) Montrer que si X est transitif, alors pour tout n ∈ N, Pn (X) est transitif.
3. Montrer que si E est transitif, alors E ∪ {E} l’est également.
S T
4. Soit (Ei )i∈I une famille (finie ou infinie) d’ensembles t ransitifs. Montrer que les ensembles Ei et Ei sont
i∈I i∈I
transitifs.
Exercice 5 – Plus généralement, soient E un ensemble, n un entier naturel non nul, et A1 , . . . , An , et B1 , . . . , Bn des
sous-ensembles de E. Montrer que :
!
[n \ [ [
(Ai ∩ Bi ) = Ai ∪ Bj
i=1 X∈P([[1,n]]) i∈X j∈∁I (X)
Exercice 6 – Soient X et Y deux ensembles. Montrer que X ⊂ Y si et seulement si P(X) ⊂ P(Y )
Exercice 7 – Montrer, sans utiliser l’axiome de fondation, qu’il n’existe aucun ensemble X tel que P(X) ⊂ X.
Exercice 8 – Soient A, B, C, D quatre ensembles. Montrer que si A ⊂ C, B ⊂ D, C ∩ D = ∅ et A ∪ B = C ∪ D, alors
A = C et B = D.
Exercice 9 – (Définitions et démonstrations par induction structurelle)
Soit E un ensemble non vide. Soit m ∈ N∗ et pour tout i ∈ [[1, m]], ki ∈ N∗ , et fi : E ki −→ E. Soit F0 ⊂ E.
On rappelle que le sous-ensemble F de E défini par induction structurelle à partir de F0 et des fonctions f1 , . . . , fm est
le plus petit ensemble au sens de l’inclusion tel que F0 ⊂ F et stable par chacun des fi :
∀i ∈ [[1, m]], ∀(x1 , . . . , xki ) ∈ F ki , fi (x1 , . . . , xki ) ∈ F.
Autrement dit, pour tout autre ensemble H vérifiant ces propriétés, F ⊂ H.
1
1. Existence de F , et description par le haut
Soit M = {G ⊂ E | F0 ⊂ G et G stable par chacun des fi }.
(a) Montrer que M est non vide.
\
(b) Soit F = G. Montrer que F est stable par les fi , et que F0 ⊂ F .
G∈M
(c) Montrer que F est bien l’ensemble défini par induction structurelle à partir de F0 et des fi .
2. Description par le bas de F
Soit pour tout n ∈ N,
m
[
Fn+1 = Fn ∪ fi (Fnki ).
i=1
Ainsi, Fn+1 est obtenu en rajoutant à Fn l’ensemble des éléments pouvant s’obtenir des éléments de Fn en appli-
quant l’une des fonctions fi .
(a) Justifier que pour tout n ∈ N, Fn est bien défini, et Fn ⊂ F .
[
(b) Montrer que F = Fn .
n∈N
Ainsi, F peut se construire « par le bas », en rajoutant petit à petit tous les éléments qu’on peut construire avec
les règles de construction données.
3. Principe d’induction structurelle
Soit P une propriété définie sur un sous-ensemble G de E tel que F ⊂ G. On suppose que :
• ∀x ∈ F0 , P(x)
• ∀i ∈ [[1, m]], ∀(x1 , . . . , xki ) ∈ F ki , P(x1 ) ∧ · · · ∧ P(xki ) =⇒ P(fi (x1 , . . . , xki )).
(a) En considérant V = {x ∈ F | P(x) est vraie}, montrer que P(x) est vraie pour tout x ∈ F .
(b) Retrouver ce résultat en utilisant la description par le bas de F .
4. Exemple : les formules de la logique propositionnelle
Soit V un ensemble fini (les variables propositionnelles P , Q, R...) et E l’ensemble de tous les mots (c’est-à-dire
juxtaposition de lettres) que l’on peut former avec les variables propositionnelles et les symboles (, ), ∧, ∨, ¬, =⇒
et ⇐⇒. On définit les fonctions suivantes, à une ou deux variables dans E :
f1 (F ) = ¬F f2 (F, G) = (F ∨ G) f3 (F, G) = (F ∧ G) f4 (F, G) = (F =⇒ G) f5 (F, G) = (F ⇐⇒ G).
L’ensemble F des formules propositionnelles est l’ensemble défini par induction structurelle à partir de l’ensemble
de base V et des fonctions f1 , f2 , f3 , f4 et f5 .
(a) Montrer qu’une formule de F a toujours autant de parenthèses ouvrantes que de parenthèses fermantes.
(b) On appelle segment initial d’un mot m = m1 m2 . . . mk un mot m1 m2 . . . mi , i ∈ [[1, k]] (il s’agit donc du début
du mot m, contenant au moins une lettre). Un segment initial de m est dit propre s’il est différent de m
lui-même.
i. Montrer que si F est une formule commençant par une parenthèse ouvrante, et F ′ un segment initial propre
de F , alors, si o(F ′ ) et f (F ′ ) désignent le nombre de parenthèses ouvrantes et fermantes respectivement de
F ′ , on a o(F ′ ) > f (F ′ ).
ii. En déduire que si F est une formule, un segment initial propre de F ne peut pas être une formule.
(c) (Théorème de lecture unique d’une formule)
Montrer que pour toute formule F , un et un seul des trois cas suivants se présente :
(i) F ∈ V
(ii) il existe une unique formule G telle que F = ¬G
(iii) il existe un unique connecteur logique γ et un unique couple (G, H) de formules telles que F = (GγH).
2
Exercice 10 – Soit E un ensemble non vide, A et B deux parties de E, et f : P(E) −→ P(E) l’application définie par
f (X) = (A ∩ X) ∪ (B ∩ X), où X désigne le complémentaire de X dans E. Résoudre et discuter l’équation f (X) = ∅.
Exercice 11 – Soit X un ensemble. On appelle recouvrement de X une famille (Ui )i∈I de sous-ensembles de X dont
l’union est égale à X. On dit qu’un recouvrement (Vj )j∈J est plus fin qu’un recouvrement (Ui )i∈I si pour tout j ∈ I, il
existe i ∈ I tel que Vj ⊂ Ui .
Montrer qu’étant donné deux recouvrements de X, il existe toujours un troisième recouvrement plus fin que les deux
premiers, et maximal pour cette propriété (donc moins fin que tout autre recouvrement vérifiant la même propriété).
A-t-on unicité ?
Exercice 12 – Soient X et Y deux ensembles, et (Xi )i∈I un recouvrement de X (i.e. l’union des Xi est X). On se donne
une famille (fi )i∈I d’applications de Xi dans Y . Donner une condition nécessaire et suffisante sur les fi pour qu’il existe
une fonction f : X → Y coïncidant avec fi sur Xi , pour tout i ∈ I. La fonction f est-elle alors unique ?
∗
Exercice 13 – Schémas simpliciaux
On appelle schéma simplicial un couple (K, S), où K est un ensemble et S est un sous-ensemble de parties finies et non
vides de K, et tel que tout sous-ensemble non vide d’un élément de S est encore dans S.
Les éléments de S sont appelés simplexes de K. La dimension d’un simplexe est un de moins que le cardinal de ce
simplexe. Ainsi, les simplexes de dimension 0 sont les singletons de S, aussi appelés sommets. Les simplexes de dimension
1 sont des paires, aussi appelés arêtes. Les simplexes de dimension 2 ont trois éléments, et sont aussi appelés faces, etc.
1. Soit X un ensemble quelconque, et (Ui )i∈I un recouvrement de \X. On convient de dire qu’une partie S de l’ensemble
I est un simplexe si elle est finie, non vide, et si l’intersection Ui est non vide. On note S l’ensemble des simplexes
i∈S
ainsi définis.
Montrer que le couple (I, S) est un schéma simplicial (appelé nerf du recouvrement)
2. Soit (K, S) un schéma simplicial. On désigne par P (K) l’ensemble des fonctions f définies sur l’ensemble K, à
valeurs réelles, et possédant les 3 propriétés suivantes :
(i) l’ensemble des x tels que f (x) 6= 0 est un simplexe de S,
(ii) on a f (x) > 0 pour tout x ∈ K
X
(iii) f (x) = 1.
x∈K
Soit, pour tout x ∈ K, Ux l’ensemble des f ∈ P (K) telles que f (x) 6= 0. Montrer que (Ux )x∈K est un recouvrement
de P (K) dont le nerf est égal à (K, S).
Ainsi, on a montré que tout schéma simplicial est le nerf d’un recouvrement.
∗
Exercice 14 – (ENS Lyon)
Soit n ∈ N∗ et soit (Xi )i∈[[1,n+1]] une famille de parties non vides de [[1, n]]. Montrer qu’il existe deux sous-ensembles
disjoints I et J de [[1, n + 1]] tels que [ [
Xi = Xj .
i∈I j∈J
