Exercices de khôlle pour la MPSI

Année scolaire 1997-1998

Première semaine (Logique, ensembles)

David A. Madore ( )

Exercice trivial que pourtant personne n’a encore résolu de manière satisfaisante. A et B étant deux ensembles, préciser

1) Les inclusions entre P(A ∩ B) et P(A) ∩ P(B).

2) Les inclusions entre P(A ∪ B) et P(A) ∪ P(B).

3) Les implications entre P(A) ⊆ P(B) et A ⊆ B.

4) Les implications entre P(A) ∈ P(B) et A ∈ B.

Théorème de Cantor-Bernstein. Soient X et Y deux ensembles, f: X → Y et g: Y → X deux injections. Montrer qu’il existe une bijection h: X → Y.

Exercice d’identification. Étant donnés trois ensembles A, B, B′, trouver

1) Une bijection entre A^{B×B′} et (A^{B})^{B′}.

2) Une bijection entre A^{B∪B′} et A^{B} × A^{B′}, à condition que B et B′ soient disjoints.

Inverses des applications. Montrer qu’une application f: X → Y est surjective ss’il existe g: Y → X telle que fg = id_{X} (on dit que g est une “section” de f). Trouver et prouver une caractérisation similaire des applications injectives (l’existence d’une “rétraction”).

Exercice trop classique. Étant donnés f: X → Y et g: Y → Z, montrer que si gf est surjective (respectivement injective) alors g (respectivement f) l’est aussi. Contre-exemples variés...

Théorème de Cantor et paradoxe de Russell. Soit A un ensemble quelconque. Montrer qu’il n’existe pas de surjection A → P(A). En déduire qu’il n’existe pas d’ensemble U dont tous les ensembles soient éléments (¬∃U∀x(x ∈ U)).

Équivalences. Pour deux ensembles E, F et f: E → F, prouver l’équivalence entre

1) f est surjective.

2) Pour tout y ∈ F, on a f(f^{−1}({y})) = {y}.

3) Pour tout Y ⊆ F, on a f(f^{−1}(Y)) = Y.

4) Le seul Y ⊆ F tel que f^{−1}(Y) = ∅ est ∅.

Trouver un énoncé analogue pour les applications injectives.