Livre E · Français

Index des énoncés

Les 349 énoncés de Théorie des ensembles, par chapitre et paragraphe. Choisissez un type, filtrez par un mot, ou mettez les plus cités en tête.

Les plus cités d’abord

I. Description de la mathématique formelle

§ 1. Termes et relations

Exemple 1 L’assemblage ∨ ¬ se représente par ⇒. 03P0
Exemple 2 Les symboles suivants représentent des assemblages (d’ailleurs fort longs): 03P1
Exemple Le symbole τₓ(∈ xy) représente l’assemblage τ∈square y. 03RY
Exemple Lorsque dans l’assemblage 03TO
Remarque Quand on introduit, par une définition, un symbole abréviateur Σ pour représenter un certain assemblage, on convient (en général de façon tacite) de représenter l’assemblage obtenu… 03P2
Exemple \ Dans la théorie des ensembles, où ∈ est un signe spécifique de poids 2, la suite des assemblages que voici est une construction formative: 077Q
Remarque Intuitivement, les termes sont des assemblages qui représentent des objets, les relations sont des assemblages qui représentent des assertions que l’on peut faire sur des objets. L… 077R
Exemple Les symboles ∅, N, « la droite numérique », « la fonction Γ », f, g, représentent des termes. Les symboles π=sqrt2+sqrt3, ι∈ 2, « tout corps fini est commutatif », « les zéros de ζ… 0E3Y

§ 2. Théorèmes

Remarque Sous les hypothèses de C5, si la théorie T s’avérait contradictoire, il en serait de même de T'. En effet, si A et « non A » sont des théorèmes de T, 03G7

§ 5. Théories égalitaires

Théorème 1 x = x. ↩ 2 03P3
Théorème 2 (x = y) ⇔ (y = x). 03P4
Théorème 3 ((x = y) et (y = z)) ⇒ (x = z). 03P5

App. 0. Caractérisation des termes et des relations

Proposition 1 Si A₁,A₂,…,Aₚ sont p mots significatifs et f un signe de poids p, le mot fA₁A₂… Aₚ est significatif. ↩ 1 03P6
Proposition 2 Pour qu’un mot soit significatif, il faut et il suffit qu’il soit équilibré. ↩ 1 03P7
Lemme 1 Soit A un mot équilibré. Pour tout entier k tel que 0≤ k<l(A), il existe un segment équilibré S de A et un seul qui commence à la (k+1)-ième place. ↩ 1 03P8
Lemme 2 Tout mot équilibré A peut se mettre sous la forme A=fA₁A₂… Aₚ, où les Aᵢ sont équilibrés et où n(f)=p. 03GT
Corollaire 1 Soit A un mot significatif. Pour tout entier k tel que 0≤ k<l(A), il existe un segment significatif de A et un seul qui commence à la (k+1)-ième place. 03GU
Corollaire 2 Tout mot significatif A peut se mettre, d’une manière et d’une seule, sous la forme fA₁A₂… Aₚ, où les Aᵢ sont significatifs et où n(f)=p. ↩ 2 03GV
Remarque Sauf pour certaines théories mathématiques particulièrement pauvres en axiomes (I, p. 50, exerc. 7), on ne dispose pas, en général, d’un procédé du type précédent, permettant de sa… 03GW

II. Théorie des ensembles

§ 1. Relations collectivisantes

Définition 1 La relation désignée par (∀ z)((z∈ x)⇒(z∈ y)) dans laquelle ne figurent que les lettres x et y, se note de l’une quelconque des manières suivantes : x⊂ y, y⊃ x, « x est contenu dan… ↩ 1 03H5
Proposition 1 x⊂ x. 03P9
Proposition 2 (x⊂ y\ et\ y⊂ z)⇒(x⊂ z). 03PA
Définition 2 L’ensemble z| z=x\ ou\ z=y, dont les seuls éléments sont x et y, se note x,y. 03H6
Remarque Soient R une relation collectivisante en x, et S une relation telle que (∀ x)(S⇒ R) soit un théorème. Alors S est collectivisante en x, car R est équivalente à x∈x| R, donc S⇒ (x∈x… 03H7
Définition 3 Soit A une partie d’un ensemble X. On appelle complémentaire de A par rapport à X, et on désigne par complement_XA ou X-A (ou par complement A lorsqu’il n’y a pas de confusion à cr… 03H8
Théorème 1 La relation (∀ x)(x∉ X) est fonctionnelle en X. 03H9
Remarque Il n’existe pas d’ensemble dont tous les objets soient éléments ; autrement dit, « non (∃ X)(∀ x)(x∈ X) » est un théorème. En effet, s’il existait un tel ensemble, toute relation s… 03PB

§ 2. Couples

Proposition 1 La relation x,x,y=x',x',y' est équivalente à « x=x' et y=y' ». 03PE
Théorème 1 La relation 03PC
Définition 1 Etant donnés deux ensembles X et Y, l’ensemble 03PD
Proposition 2 Si A', B' sont des ensembles non vides, la relation A'× B'⊂ A× B est équivalente à « A'⊂ A et B'⊂ B ». ↩ 1 03PF
Proposition 3 Soient A et B deux ensembles. La relation A× B=∅ est équivalente à « A=∅ ou B=∅ ». 0E3Z

§ 3. Correspondances

Définition 1 On dit que G est un graphe si tout élément de G est un couple, autrement dit si la relation 03PG
Proposition 1 Soit G un graphe. Il existe un ensemble A et un seul, et un ensemble B et un seul, qui possèdent les propriétés suivantes : 1) la relation (∃ y)((x,y) ∈ G) est équivalente à x ∈ A… 03HI
Remarque La relation x = y n’admet pas de graphe; car la première projection de ce graphe, s’il existait, serait l’ensemble de tous les objets (cf. II, p. 6, Remarque). 03S1
Définition 2 On appelle correspondance entre un ensemble A et un ensemble B un triplet (II, p. 9) Γ = (G, A, B) où G est un graphe tel que pr₁ G ⊂ A et pr₂ G ⊂ B. On dit que G est le graphe de… 03HJ
Définition 3 Soient G un graphe et X un ensemble. L’ensemble des objets qui correspondent par G à des éléments de X s’appelle l’image de X par G et se désigne par G⟨ X⟩ ou G(X). ↩ 1 03PI
Remarque 1 D’une manière précise, G⟨ X⟩ désigne l’ensemble y | (∃ x)(x ∈ X et (x,y) ∈ G). Nous ne ferons plus que rarement désormais la traduction des définitions en langage formel. 03PH
Remarque 2 Les notations G(X) et Γ(X) peuvent parfois conduire à des confusions avec des notations introduites ultérieurement (cf. II, p. 14, Remarque). 03S2
Proposition 2 Soient G un graphe, X et Y deux ensembles; la relation X ⊂ Y entraîne G⟨ X⟩ ⊂ G⟨ Y⟩. ↩ 1 03PJ
Corollaire Si A ⊃ pr₁ G, on a G⟨ A⟩ = pr₂ G. 03PK
Définition 4 Soient G un graphe et x un objet. On appelle coupe de G suivant x l'ensemble G⟨x⟩ (qu'on désigne aussi parfois par G(x), par abus de notation). 03PL
Définition 5 Soient G un graphe. Le graphe dont les éléments sont les couples (x,y) tels que (y,x)∈ G s'appelle le graphe réciproque de G et se désigne par overlineG⁻¹ ou G⁻¹. 03PM
Définition 6 Soient G et G' des graphes. On appelle composé de G' et de G, et on désigne par G'∘ G (ou parfois par G'G), le graphe par rapport à x et z de la relation (∃ y)((x,y)∈ G et (y,z)∈ G… ↩ 1 03PN
Proposition 3 Soient G et G' deux graphes. Le graphe réciproque de G' ∘ G est G⁻¹ ∘ G'⁻¹. ↩ 1 03HK
Proposition 4 Soient G₁,G₂,G₃ des graphes. On a alors (G₃ ∘ G₂)∘ G₁=G₃∘(G₂∘ G₁). 03HL
Proposition 5 Soient G et G' des graphes et A un ensemble. On a ↩ 1 03HM
Définition 7 Soient Γ = (G, A, B) et Γ' = (G', B, C) deux correspondances telles que l’ensemble d’arrivée de Γ soit identique à l’ensemble de départ de Γ'. On appelle composée de Γ' et de Γ, et… 03PO
Définition 8 Si A est un ensemble, l’ensemble Δ_A des objets de la forme (x, x), pour x ∈ A, s’appelle la diagonale de A × A. 03PP
Définition 9 On dit qu’un graphe F est un graphe fonctionnel si, pour tout x, il existe au plus un objet correspondant à x par F (I, p. 40). On dit qu’une correspondance f = (F, A, B) est une f… ↩ 1 03HN
Remarque Il faut prendre garde aux confusions que risque d’entraîner l’emploi simultané de la notation f(x) et de la notation f(X) (synonyme de f(⟨ X⟩)) introduite dans la déf. 3 (cf. II, p… 03HO
Proposition 6 Si f est une application de A dans B, et g une application de B dans C, g ∘ f est une application de A dans C. 03HP
Définition 10 Soit f une application de A dans B. On dit que f est une injection, ou que f est une application injective, si deux éléments distincts de A ont des images distinctes par f. On dit… 03HQ
Proposition 7 Soit f une application de A dans B. Pour que overlinef⁻¹ soit une fonction, il faut et il suffit que f soit bijective. 03PQ
Remarque Soit f une application de A dans B; pour toute partie X de A, on a vu (II, p. 12) que l’on a X⊂ f⁻¹⟨ f(X)⟩. En outre, pour toute partie Y de B, on a f⟨ f⁻¹(Y)⟩⊂ Y: en effet, la rel… 03HR
Proposition 8 Soit f une application de A dans B. S’il existe une application r (resp. s) de B dans A telle que r∘ f (resp. f∘ s) soit l’application identique de A (resp. B), f est injective (re… ↩ 5 03HS
Corollaire Soient A et B des ensembles, f une application de A dans B, g une application de B dans A. Si g∘ f est l’application identique de A et f∘ g l’application identique de B, f et g son… ↩ 1 03HT
Définition 11 Soit f une application injective (resp. surjective) de A dans B. Toute application r (resp. s) de B dans A telle que r∘ f (resp. f∘ s) soit l’application identique de A (resp. B) e… ↩ 6 03HU
Théorème 1 Soient f une application de A dans B, f' une application de B dans C, et f'' = f' ∘ f. Alors: ↩ 2 03PR
Proposition 9 a) Soient E,F,G des ensembles, g une application de E sur F, f une application de E dans G. Pour qu’il existe une application h de F dans G telle que f=h∘ g (fig. 1), il faut et il… ↩ 1 03PS

§ 4. Réunion et intersection d’une famille d’ensembles

Définition 1 Soit (Xᵢ)_i∈ I une famille d’ensembles (resp. une famille de parties d’un ensemble E). On appelle réunion de cette famille, et on désigne par ⋃_i∈ I Xᵢ, l’ensemble 03I1
Définition 2 Soit (Xᵢ)_i∈ I une famille d’ensembles dont l’ensemble d’indices I n’est pas vide. On appelle intersection de cette famille, et on désigne par ⋂_i∈ I Xᵢ, l’ensemble 03PT
Définition 3 Soit (Xₜ)_t ∈ I une famille de parties d’un ensemble E. On appelle intersection de cette famille, et on désigne par ⋂_t ∈ I Xₜ, l’ensemble x | x ∈ E et (∀ t)((t ∈ I) ⇒ (x ∈ Xₜ)), a… 03PU
Proposition 1 Soit (Xₜ)_t ∈ I une famille d’ensembles, et soit f une application d’un ensemble K sur I. On a alors ⋃_κ ∈ K X_f(κ) = ⋃_t ∈ I Xₜ, et, si I ≠ ∅, ⋂_κ ∈ K X_f(κ) = ⋂_t ∈ I Xₜ. ↩ 5 03PV
Corollaire Soit (Xₜ)_t ∈ I une famille d’ensembles telle que Xₜ = X_κ pour tout couple d’indices (t, κ). Alors, pour tout α ∈ I, on a ⋃_t ∈ I Xₜ = X_α, et (si I ≠ ∅) ⋂_t ∈ I Xₜ = X_α. 03I2
Définition 4 Soit 𝔉 un ensemble d’ensembles, et soit Φ la famille d’ensembles 03I3
Proposition 2 Soit (Xₜ)_t∈ I une famille d’ensembles dont l’ensemble d’indices I est réunion d’une famille (J_λ)_λ∈ L d’ensembles. On a alors ⋃_t∈ IXₜ=⋃_λ∈ L(⋃_t∈ J_λXₜ) et (si L≠∅ et J_λ≠∅ pour… ↩ 1 03I4
Proposition 3 Soient (Xi){i \in I} une famille de parties d’un ensemble A, et Γ une correspondance entre A et B. On a alors Γ ⟨ ⋃_i ∈ I Xᵢ ⟩ = ⋃_i ∈ I Γ ⟨ Xᵢ ⟩, et Γ ⟨ ⋂_i ∈ I Xᵢ ⟩ ⊂ ⋂_i ∈ I Γ ⟨… ↩ 4 03I5
Proposition 4 Soient f une application de A dans B, et (Yᵢ)_i ∈ I une famille de parties de B. On a alors f⁻¹ ⟨ ⋂_i ∈ I Yᵢ ⟩ = ⋂_i ∈ I f⁻¹ ⟨ Yᵢ ⟩. ↩ 3 03I6
Corollaire Si f est une injection de A dans B et si (Xᵢ)_i ∈ I est une famille de parties de A dont l’ensemble d’indices n’est pas vide, on a f ⟨ ⋂_i ∈ I Xᵢ ⟩ = ⋂_i ∈ I f ⟨ Xᵢ ⟩. 03I7
Proposition 5 Pour toute famille (Xᵢ)_i ∈ I de parties d'un ensemble E, on a ↩ 1 03I8
Proposition 6 Soit f une application de A dans B; pour toute partie Y de B, on a ↩ 1 03PW
Corollaire Soit f une injection de A dans B; pour toute partie X de A, on a 03PX
Définition 5 On dit qu’une famille d’ensembles (Xᵢ)_i ∈ I est un recouvrement d’un ensemble E si E ⊂ ⋃_i ∈ I Xᵢ. Si (Xᵢ)_i ∈ I et (Y_κ)_κ ∈ K sont des recouvrements de E, on dit que le second d… ↩ 1 03PY
Proposition 7 1° Soient E un ensemble et (Xᵢ)_i ∈ I un recouvrement de E. Si deux fonctions f, g, ayant E pour ensemble de définition, sont telles que, pour tout i ∈ I, f et g coïncident dans E… ↩ 5 03PZ
Définition 6 On dit que deux ensembles A, B sont disjoints (ou sans élément commun) si A ∩ B = ∅; s’il n’en est pas ainsi, on dit que A et B se rencontrent. Soit (Xᵢ)_i ∈ I une famille d’ensemb… 03Q0
Proposition 8 Soient (Xᵢ)_i ∈ I une famille d’ensembles mutuellement disjoints, (fᵢ)_i ∈ I une famille de fonctions ayant même ensemble d’arrivée F, et telles que, pour tout i ∈ I, l’ensemble de… ↩ 5 03Q1
Définition 7 On appelle partition d’un ensemble E une famille de parties mutuellement disjointes de E, qui est un recouvrement de E. 03Q2
Exemple Pour tout ensemble non vide A, la famille (x)_x ∈ A des parties de A réduites à un seul élément est une partition de A. 03I9
Proposition 9 Soit (Xᵢ)_i ∈ I une famille d’ensembles. Il existe un ensemble X possédant la propriété suivante : X est réunion d’une famille (X'ᵢ)_i ∈ I d’ensembles mutuellement disjoints, telle… 03Q3
Définition 8 Soit (Xᵢ)_i ∈ I une famille d’ensembles. On appelle somme de cette famille d’ensembles la réunion de la famille des ensembles Xᵢ × i (i ∈ I). ↩ 3 03Q4
Proposition 10 Soit (Xᵢ)_i ∈ I une famille d’ensembles mutuellement disjoints. Soient A sa réunion et S sa somme. Il existe une application bijective de A sur S. ↩ 1 03IA

§ 5. Produit d'une famille d'ensembles

Proposition 1 1° Si f est une surjection d’un ensemble E sur un ensemble F, l’extension canonique hatf est une surjection de 𝔓(E) sur 𝔓(F). ↩ 1 03IJ
Proposition 2 1° Si u est une surjection de E’ sur E, et v une injection de F dans F’, l’application f ↦ v ∘ f ∘ u est injective. ↩ 2 03Q5
Corollaire Si u est une bijection de E’ sur E et v une bijection de F sur F’, f ↦ v ∘ f ∘ u est bijective. 03Q6
Proposition 3 Si, pour toute application f de B × C dans A, on désigne par tildef l’application y ↦ f_y de C dans F(B; A), la fonction f ↦ tildef est une bijection (dite canonique) de F(B × C; A… ↩ 1 03Q7
Définition 1 Soit (Xᵢ)_i ∈ I une famille d'ensembles. L'ensemble des graphes fonctionnels F, ayant I pour ensemble de définition, et tels que F(i) ∈ Xᵢ pour tout i ∈ I, s'appelle le produit de… 03Q8
Proposition 4 Soient (X_ι)_ι ∈ I une famille d’ensembles, u une bijection d’un ensemble K sur l’ensemble I, U son graphe. L’application F ↦ F ∘ U de ∏_ι ∈ I X_ι dans ∏_κ ∈ K X_u(κ) est bijective… ↩ 2 03IK
Proposition 5 Soient (X_ι)_ι ∈ I une famille d’ensembles, et J une partie de I. Si, pour tout ι ∈ I, on a X_ι ≠ ∅, la projection pr_J est une application de ∏_ι ∈ I X_ι sur ∏_ι ∈ J X_ι. ↩ 1 03Q9
Proposition 6 Soit (Xᵢ)_i ∈ I une famille d’ensembles telle que Xᵢ ≠ ∅ pour tout i ∈ I. Etant donnée une application g de J ⊂ I dans A = ⋃_i ∈ I Xᵢ, telle que g(i) ∈ Xᵢ pour tout i ∈ J, il exist… ↩ 6 03QA
Corollaire 1 Soit (Xᵢ)_i ∈ I une famille d’ensembles telle que, pour tout i ∈ I, on ait Xᵢ ≠ ∅. Alors, pour tout α ∈ I, la projection pr_α est une application de ∏_i ∈ I Xᵢ sur X_α. ↩ 2 03QB
Corollaire 2 Soit (Xᵢ)_i ∈ I une famille d’ensembles. Pour que ∏_i ∈ I Xᵢ = ∅, il faut et il suffit qu’il existe un i ∈ I tel que Xᵢ = ∅. ↩ 4 03QC
Corollaire 3 Soient (Xᵢ)_i ∈ I et (Yᵢ)_i ∈ I deux familles d’ensembles ayant le même ensemble d’indices I. Si, pour tout i ∈ I, on a Xᵢ ⊂ Yᵢ, on a aussi ∏_i ∈ I Xᵢ ⊂ ∏_i ∈ I Yᵢ. ↩ 1 03QD
Proposition 7 Soit (Xᵢ)_i ∈ I une famille d’ensembles. Soit (J_λ)_λ ∈ L une partition de I; l’application f ↦ (pr_J_λ f)_λ ∈ L de ∏_i ∈ I Xᵢ dans l’ensemble produit ∏_λ ∈ L (∏_i ∈ J_λ Xᵢ) est bi… ↩ 2 03IN
Remarque 1 Soient α, β deux objets distincts, et (J_λ)_λ ∈ α, β une partition de I en deux ensembles J_α, J_β. On obtient une application bijective (dite encore canonique) du produit ∏_i ∈ I… ↩ 1 03SA
Remarque 2 Soient α, β, γ des objets deux à deux distincts (il en existe, par exemple ∅, ∅ et ∅), et soient A, B, C des ensembles. Considérons le graphe fonctionnel (α, A), (β, B), (γ, C), c’… 03SB
Proposition 8 Soit ((X_λ, i)_i ∈ J_λ)_λ ∈ L une famille (admettant L pour ensemble d’indices) de familles d’ensembles. On suppose L ≠ ∅ et J_λ ≠ ∅ pour tout λ ∈ L. Soit I = ∏_λ ∈ L J_λ ≠ ∅. On a… ↩ 2 03IO
Corollaire Soient (Xᵢ)_i ∈ I et (Yₖ)_k ∈ K deux familles d’ensembles dont les ensembles d’indices sont non vides. On a ↩ 1 03IP
Proposition 9 Soit ((X_λ, i)_i ∈ J_λ)_λ ∈ L une famille (admettant L comme ensemble d’indices) de familles d’ensembles. Soit I = ∏_λ ∈ L J_λ. On a ↩ 2 03IQ
Corollaire 1 Si, pour chaque indice λ ∈ L, la famille (X_λ, i)_i ∈ J_λ est une partition de X_λ = ⋃_i ∈ J_λ X_λ, i, la famille (∏_λ ∈ L X_λ, f(λ))_f ∈ I est une partition de ∏_λ ∈ L X_λ. ↩ 1 03QE
Corollaire 2 Soient (Xᵢ)_i ∈ I et (Yₖ)_k ∈ K deux familles d’ensembles. On a (⋃_i ∈ I Xᵢ) × (⋃_k ∈ K Yₖ) = ⋃_(i, k) ∈ I × K (Xᵢ × Yₖ) et (si I et K sont non vides) (⋂_i ∈ I Xᵢ) × (⋂_k ∈ K Yₖ) =… 03QF
Proposition 10 Soit (X_i, k)_(i, k) ∈ I × K une famille d’ensembles dont l’ensemble d’indices est le produit de deux ensembles I et K. Si K ≠ ∅, on a ⋂_k ∈ K ( ∏_i ∈ I X_i, k ) = ∏_i ∈ I ( ⋂_k ∈… ↩ 1 03QG
Corollaire Soient (Xι){ι ∈ I} et (Yι){ι ∈ I} deux familles d'ensembles ayant même ensemble d'indices I ≠ ∅. On a 03IR
Définition 2 Soient (Xι^i){ι ∈ I}, (Yι){ι ∈ I} deux familles d'ensembles, et (gι){ι ∈ I} une famille de fonctions, admettant le même ensemble d'indices, et telles que, pour tout ι ∈ I, gι soit… ↩ 2 03IS
Proposition 11 Soient (Xι){ι ∈ I}, (Yι){ι ∈ I}, (Zι){ι ∈ I} trois familles d'ensembles, (gι){ι ∈ I}, (g'ι){ι ∈ I} deux familles de fonctions, admettant le même ensemble d'indices, et telles que… 03IT
Corollaire Soient (Xι){ι ∈ I}, (Yι){ι ∈ I} deux familles d'ensembles, (gι){ι ∈ I} une famille de fonctions. Si, pour tout i ∈ I, gᵢ est une injection (resp. surjection) de Xᵢ dans Yᵢ, alors l… ↩ 1 03IU

§ 6. Relations d’équivalence

Exemple La relation x = y est symétrique et transitive. La relation X ⊂ Y est transitive, mais non symétrique. La relation X ∩ Y = ∅ est symétrique, mais non transitive. 03IX
Proposition 1 Pour qu'une correspondance Γ entre X et X soit une équivalence dans X, il faut et il suffit que les conditions suivantes soient vérifiées : a) X est l'ensemble de définition de Γ… ↩ 1 03QH
Exemple 1 La relation « x ∈ E et y ∈ E et x = y » est plus fine que toute relation d’équivalence dans E; la relation « x ∈ E et y ∈ E » est moins fine que toute relation d’équivalence dans E… 03SF
Exemple 2 \ La relation d'équivalence « x ∈ Z et y ∈ Z et x - y est divisible par 4 » est plus fine que la relation d'équivalence « x ∈ Z et y ∈ Z et x - y est divisible par 2 ». 03SG
Remarque Soit Px, x' une relation où ne figurent pas les lettres y et y'; on dit que P est compatible avec les relations d'équivalence Rx, y et R'x', y' (par rapport à x et x') si la relati… 03IY

III. Ensembles ordonnés, cardinaux, nombres entiers

§ 1. Relations d’ordre. Ensembles ordonnés

Exemple 1 La relation d’égalité et la relation d’inclusion ne sont pas des relations d’ordre dans un ensemble, car les relations x = x et X ⊂ X ne sont pas collectivisantes (II, p. 6). 03SH
Exemple 2 Soient Rx, y une relation d’ordre entre x et y, et E un ensemble tel que x ∈ E entraîne Rx, x (on notera que l’ensemble vide satisfait à cette condition). La relation « Rx, y et x… 03SI
Exemple 3 Soient E et F des ensembles. La relation « g prolonge f » est une relation d’ordre (entre f et g) dans l’ensemble des applications de parties de E dans F. ↩ 3 03SJ
Exemple 4 Dans l’ensemble 𝔓(𝔓(E)) des ensembles de parties d’un ensemble E, soit P l’ensemble des partitions de E (II, p. 29). Rappelons qu’une partition varpi est dite moins fine qu’une par… ↩ 2 03V3
Proposition 1 Pour qu’une correspondance Γ entre E et E soit un ordre sur E, il faut et il suffit que son graphe G satisfasse aux conditions suivantes: 03JA
Exemple Soit A un anneau ayant un élément unité. La relation (∃ z)(z ∈ A et y = zx) entre deux éléments x et y de A est une relation de préordre dans A; elle se lit « x est diviseur à droi… 03JB
Exemple Les relations induites par la relation d’inclusion X ⊂ Y sur divers ensembles de parties ont une importance considérable. En voici des exemples: 03WB
Définition 1 Soient E et F des ensembles préordonnés (par des relations toutes deux notées ≤). On dit qu’une application f de E dans F est croissante si la relation x ≤ y entraîne f(x) ≤ f(y)… 03JC
Définition 2 Soient E et F deux ensembles ordonnés; on dit qu’une application f de E dans F est strictement croissante si la relation x < y entraîne f(x) < f(y); on dit que f est strictement dé… 03JD
Exemple 1 Soit E un ensemble; l’application X ↦ E - X de 𝔓(E) (ordonné par inclusion) sur lui-même est strictement décroissante. 03SK
Exemple 2 Soit E un ensemble ordonné. Pour tout x ∈ E, soit Uₓ l’ensemble des y ∈ E tels que y ≥ x. L’application x ↦ Uₓ est une application strictement décroissante de E dans 𝔓(E) (ordonné… 03SL
Proposition 2 Soient E, E’ deux ensembles ordonnés, u : E → E' et v : E' → E deux applications décroissantes, telles que pour tout x ∈ E et tout x' ∈ E', on ait v(u(x)) ≥ x et u(v(x')) ≥ x'. Alo… ↩ 2 03JE
Définition 3 Soit E un ensemble préordonné. Un élément a ∈ E est appelé élément minimal (resp. maximal) de E si la relation x ≤ a (resp. x ≥ a) entraîne x = a. 03JF
Exemple 1 Soit A un ensemble; dans la partie de 𝔓(A) (ordonnée par inclusion) formée des parties non vides de A, les éléments minimaux sont les parties réduites à un élément. 03SM
Exemple 2 Dans l'ensemble Φ(E, F) des applications de parties de E dans F (F n'étant pas vide), ordonné par la relation « v prolonge u » entre u et v, les éléments maximaux sont les applicat… 03SN
Exemple 3 \ Dans l'ensemble des entiers naturels > 1, ordonné par la relation « m divise n » entre m et n, les éléments minimaux sont les nombres premiers. 03SO
Exemple 4 \ L'ensemble des nombres réels n'a pas d'élément maximal ni d'élément minimal. 03SP
Définition 4 Soit E un ensemble ordonné. On dit qu'un élément a ∈ E est le plus petit (resp. le plus grand) élément de E si, pour tout x ∈ E, on a a ≤ x (resp. x ≤ a). 03JG
Exemple 1 Soit 𝔊 une partie non vide de l'ensemble 𝔓(E) des parties d'un ensemble E. Si 𝔊 admet un plus petit (resp. plus grand) élément A pour la relation d'inclusion, A n'est autre que l'i… 03SQ
Exemple 2 En particulier, ∅ est le plus petit élément et E le plus grand élément de 𝔓(E). Dans l'ensemble Φ(E, F) des applications de parties de E dans F, ordonné par prolongement (III, p. 2… 03SR
Proposition 3 Soient E un ensemble ordonné, E’ l’ensemble somme de E et d’un ensemble {a} réduit à un seul élément ; il existe sur E’ un ordre et un seul induisant sur E l’ordre donné et pour le… ↩ 1 03JH
Définition 5 Soient E un ensemble préordonné et X une partie de E. On appelle minorant (resp. majorant) de X dans E tout élément x ∈ E tel que, pour tout y ∈ X, on ait x ≤ y (resp. x ≥ y) ; on… 03JI
Définition 6 Soient E un ensemble ordonné, X une partie de E. On dit qu’un élément de E est la borne inférieure (resp. supérieure) de X dans E si c’est le plus grand (resp. le plus petit) éléme… 03JJ
Exemple 1 L’ensemble des majorants de la partie vide ∅ d’un ensemble ordonné E est évidemment E lui-même; pour que ∅ admette dans E une borne supérieure, il faut et il suffit donc que E adme… ↩ 1 03SS
Exemple 2 Dans l’ensemble 𝔓(E) des parties d’un ensemble E, ordonné par inclusion, toute partie 𝔊 de 𝔓(E) admet une borne supérieure, qui est la réunion des ensembles de 𝔊, et une borne infé… 03ST
Exemple 3 Soient E et F deux ensembles, et Θ une partie de l’ensemble Φ(E, F) des applications de parties de E dans F, ordonné par prolongement (III, p. 2, Exemple 3). Pour tout u ∈ Φ(E, F)… 03SU
Proposition 4 Soient E un ensemble ordonné, et A une partie de E admettant à la fois une borne inférieure et une borne supérieure dans E; on a inf A ≤ sup A si A n’est pas vide; si A = ∅, sup A… ↩ 1 03JK
Proposition 5 Soient E un ensemble ordonné, A et B deux parties de E admettant toutes deux une borne supérieure (resp. inférieure) dans E ; si A ⊂ B, on a sup A ≤ sup B (resp. inf A ≥ inf B). ↩ 1 03JL
Corollaire Soit (xᵢ)_i ∈ I une famille d’éléments d’un ensemble ordonné E, admettant une borne supérieure dans E ; si J est une partie de I telle que la famille (xᵢ)_i ∈ J admette une borne s… ↩ 1 03JM
Proposition 6 Soient (xᵢ)_i ∈ I, (yᵢ)_i ∈ I deux familles d’éléments d’un ensemble ordonné E, ayant même ensemble d’indices I, et telles que xᵢ ≤ yᵢ pour tout i ∈ I ; si elles admettent toutes d… 03JN
Proposition 7 Soient (xᵢ)_i ∈ I une famille d’éléments d’un ensemble ordonné E, (J_λ)_λ ∈ L un recouvrement de l’ensemble d’indices I ; on suppose que chacune des sous-familles (xᵢ)_i ∈ J_λ adme… 03JO
Corollaire Soit (x_λ μ)_(λ, μ) ∈ L × M une famille « double » d’éléments d’un ensemble ordonné E, telle que, pour tout μ ∈ M, la famille (x_λ μ)_λ ∈ L admette une borne supérieure dans E. Pou… 03JP
Proposition 8 Soit (Eᵢ)_i ∈ I une famille d’ensembles ordonnés. Soit A une partie de l’ensemble ordonné produit E = ∏_i ∈ I Eᵢ, et, pour tout i ∈ I, soit Aᵢ = prᵢ A. Pour que A admette une borne… ↩ 1 03QI
Exemple 4 Dans l’ensemble ordonné E = R des nombres réels, considérons l’ensemble F = Q des nombres rationnels, et l’ensemble A ⊂ F des nombres rationnels < sqrt2; alors sup_E A existe, mais… 0E42
Proposition 9 Soient E un ensemble ordonné, F une partie de E et A une partie de F. Si sup_E A et sup_F A existent toutes deux, on a sup_E A ≤ sup_F A. Si sup_E A existe et appartient à F, sup_F… 03QJ
Définition 7 On dit qu’un ensemble préordonné E est filtrant à droite (resp. à gauche) si toute partie à deux éléments de E est majorée (resp. minorée). 03QK
Exemple 1 Un ensemble ordonné qui admet un plus grand élément est filtrant à droite. 0E43
Exemple 2 \ Dans un espace topologique, un système fondamental de voisinages d’un point est filtrant pour la relation ⊃ (TG, I, § 1, no. 3). 0E44
Exemple 3 L’ensemble des sous-modules de type fini d’un module quelconque (A, II, § 1, n° 7) est filtrant pour la relation ⊂. 0E45
Proposition 10 Dans un ensemble ordonné filtrant à droite E, un élément maximal a est le plus grand élément de E. En effet, pour tout x ∈ E, il existe par hypothèse y ∈ E tel que x ≤ y et a ≤ y… ↩ 3 03QL
Définition 8 On dit qu’un ensemble ordonné E est réticulé (ou que E est un réseau ordonné, ou un lattis) si toute partie à deux éléments de E admet une borne supérieure et une borne inférieure… 03QM
Exemple 1 L’ensemble des entiers ≥ 1, ordonné par la relation « m divise n » entre m et n, est réticulé, la borne supérieure (resp. inférieure) de {m, n} n’étant autre que le ppcm (resp. pgc… 03SV
Exemple 2 L’ensemble des sous-groupes d’un groupe G, ordonné par inclusion, est réticulé (A, I, § 4, n° 3). 03TT
Exemple 3 L’ensemble des topologies sur un ensemble A, ordonné par la relation « T est moins fine que T’ » entre T et T’, est réticulé (TG, I, § 1, n°s 3 et 4). 03TU
Exemple 4 L’ensemble F(I; R) des fonctions numériques définies dans un intervalle I de R est réticulé pour la relation d’ordre f ≤ g (III, p. 6), pour laquelle il est isomorphe au produit Rᴵ… 03TV
Remarque Un ensemble ordonné réticulé est évidemment filtrant à droite et à gauche. Mais un ensemble filtrant à droite et à gauche n’est pas nécessairement réticulé, \ comme le montre l’exe… 03JQ
Définition 9 On dit que deux éléments x, y d’un ensemble préordonné E sont comparables si la relation « x ≤ y ou y ≤ x » est vraie. On dit qu’un ensemble E est totalement ordonné s'il est ordon… 03JR
Exemple 1 Toute partie d'un ensemble totalement ordonné est totalement ordonnée par l'ordre induit. 03SW
Exemple 2 Soit E un ensemble ordonné quelconque. La partie vide de E est totalement ordonnée, ainsi que toute partie réduite à un élément. 03TW
Exemple 3 \ L'ensemble R des nombres réels est totalement ordonné. 03TX
Exemple 4 Si A est un ensemble ayant au moins deux éléments distincts, l'ensemble 𝔓(A), ordonné par inclusion, n'est pas totalement ordonné, car si x ≠ y, les parties x et y ne sont pas comp… 03TY
Proposition 11 Toute application strictement monotone f d'un ensemble totalement ordonné E dans un ensemble ordonné F est injective; si f est strictement croissante, f est un isomorphisme de E su… ↩ 5 03JS
Proposition 12 Soient E un ensemble totalement ordonné, X une partie de E. Pour qu'un élément b ∈ E soit borne supérieure de X dans E, il faut et il suffit que : 1° b soit un majorant de X ; 2° p… 03JT
Proposition 13 Dans un ensemble réticulé, l’intersection de deux intervalles est un intervalle. 03JU

§ 2. Ensembles bien ordonnés

Définition 1 On dit qu’un ensemble E est bien ordonné s’il est ordonné et si toute partie non vide de E admet un plus petit élément. 03JY
Exemple 1 Soit E = α, β un ensemble dont les éléments sont distincts. On vérifie aussitôt que la partie (α, α), (β, β), (α, β) de E × E est le graphe d’un bon ordre sur E. 03SX
Exemple 2 Toute partie d’un ensemble bien ordonné (en particulier la partie vide) est bien ordonnée par l’ordre induit. 03SY
Exemple 3 L’existence d’ensembles totalement ordonnés et non bien ordonnés est équivalente à l’axiome de l’infini (III, p. 34, cor. 1 et p. 80, exerc. 3). 03SZ
Exemple 4 Si Γ est un bon ordre sur E, l’ordre opposé à Γ n’est un bon ordre sur E que si E est fini (III, p. 80, exerc. 3). 03T0
Exemple 5 Soit E un ensemble bien ordonné; l’ensemble E₁ obtenu en adjoignant à E un plus grand élément b (III, p. 9) est bien ordonné, car pour toute partie H de E₁ non vide et non réduite… 03T1
Remarque \ L’axiome de l’infini (III, p. 45) permet de montrer qu’il existe des ensembles bien ordonnés qui n’ont pas de plus grand élément, par exemple l’ensemble N des entiers naturels. 03JZ
Définition 2 Dans un ensemble ordonné E, on appelle segment de E toute partie S de E telle que les relations x ∈ S, y ∈ E et y ≤ x entraînent y ∈ S. ↩ 1 03QN
Proposition 1 Dans un ensemble bien ordonné E, tout segment de E distinct de E est un intervalle ]←, a[, où a ∈ E. ↩ 3 03QO
Proposition 2 L’ensemble E^* des segments d’un ensemble bien ordonné E est bien ordonné par inclusion; l’application x ↦ Sₓ est un isomorphisme de l’ensemble bien ordonné E sur l’ensemble des se… ↩ 3 03QP
Proposition 3 Soit (Xᵢ)_i ∈ I une famille d’ensembles bien ordonnés telle que, pour tout couple d’indices (i, k) l’un des ensembles Xᵢ, Xₖ soit un segment de l’autre. Alors, sur l’ensemble E = ⋃… ↩ 2 03QQ
Lemme 1 Soit (X_α)_α ∈ A une famille d’ensembles ordonnés, filtrante pour la relation ⊂ (autrement dit, telle que pour tout couple d’indices α, β il existe un indice γ tel que X_α ⊂ X_γ et… 03QR
Lemme 2 Soient E un ensemble bien ordonné, 𝔖 un ensemble de segments de E possédant les propriétés suivantes: 1° toute réunion de segments appartenant à 𝔖 appartient à 𝔖; 2° si Sₓ ∈ 𝔖, on… 03K0
Lemme 3 Soient E un ensemble, 𝔖 une partie de 𝔓(E) et p une application de 𝔖 dans E telle que p(X) ∉ X pour tout X ∈ 𝔖. Il existe alors une partie M de E et un bon ordre Γ sur M tels que (… ↩ 3 03K1
Théorème 1 (Zermelo) — Sur tout ensemble E il existe un bon ordre. ↩ 7 03QS
Définition 3 On dit qu’un ensemble ordonné E est inductif si toute partie totalement ordonnée de E possède un majorant dans E. ↩ 3 03K2
Exemple 1 Soit 𝔉 un ensemble de parties d’un ensemble A, ordonné par inclusion et tel que, pour tout sous-ensemble totalement ordonné 𝔊 de 𝔉, la réunion des ensembles de 𝔊 appartienne à 𝔉; a… 03T2
Exemple 2 Un exemple important d’ensemble de parties inductif pour la relation ⊂ est l’ensemble 𝔉 des graphes d’applications de parties d’un ensemble A dans un ensemble B; en effet, 𝔉 est un… ↩ 2 03T3
Exemple 3 \ Il résulte de l’axiome de l’infini (III, p. 45) que l’ensemble bien ordonné des entiers naturels n’est pas inductif pour la relation leqslant.. 03T4
Théorème 2 Tout ensemble ordonné inductif possède un élément maximal. ↩ 11 03QT
Proposition 4 Soit E un ensemble ordonné dont toute partie bien ordonné soit majorée; alors E admet un élément maximal. 03K3
Corollaire 1 Soient E un ensemble ordonné inductif, et a un élément de E; il existe un élément maximal m de E tel que m ≥ a. ↩ 2 03K4
Corollaire 2 Soit 𝔉 un ensemble de parties d’un ensemble E tel que, pour tout sous-ensemble 𝔊 de 𝔉, totalement ordonné par inclusion, la réunion (resp. l’intersection) des ensembles de 𝔊 appart… ↩ 1 03K5
Théorème 3 Soient E et F deux ensembles bien ordonnés; l’une au moins des deux propositions suivantes est vraie: 1) il existe un isomorphisme et un seul de E sur un segment de F; 2) il existe… ↩ 9 03K6
Lemme 4 Soient E, F deux ensembles bien ordonnés, f, g deux applications croissantes de E dans F telles que f(E) soit un segment de F et que g soit strictement croissante; on a alors f(x)… ↩ 1 03K7
Corollaire 1 Le seul isomorphisme d’un ensemble bien ordonné E sur un segment de E est l’application identique de E sur lui-même. ↩ 1 03K8
Corollaire 2 Soient E et F deux ensembles bien ordonnés; s’il existe un isomorphisme f de E sur un segment T de F et un isomorphisme g de F sur un segment S de E, on a nécessairement S = E, T =… 03K9
Corollaire 3 Tout sous-ensemble A d’un ensemble bien ordonné E est isomorphe à un segment de E. ↩ 3 03KA

§ 3. Ensembles équipotents. Cardinaux

Définition 1 On dit qu’un ensemble X est équipotent à un ensemble Y s’il existe une bijection de X sur Y. On note Eq(X, Y) la relation « X est équipotent à Y ». 03QU
Définition 2 L’ensemble τ_Z(Eq(X, Z)) est appelé le cardinal de X (ou la puissance de X) et se note Card (X). 03QV
Proposition 1 Pour que deux ensembles X, Y soient équipotents, il faut et il suffit que leurs cardinaux soient égaux. 03QW
Théorème 1 La relation R{\xi, \eta}: ↩ 1 03QX
Corollaire 1 Étant donnés deux ensembles, l’un est équivalent à une partie de l’autre. 03QY
Corollaire 2 Deux ensembles tels que chacun soit équivalent à une partie de l’autre sont équipotents. 03QZ
Remarque Pour tout ensemble A, il existe un ensemble dont les éléments sont les cardinaux Card (X) pour toutes les parties X de A : en effet, c’est l’ensemble des objets de la forme Card (X… 03R0
Proposition 2 Pour toute famille (αᵢ)_i ∈ I de cardinaux, il existe un cardinal et un seul b tel que αᵢ ≤ b pour tout i ∈ I et que tout cardinal c tel que αᵢ ≤ c pour tout i ∈ I soit ≥ b. 03KL
Proposition 3 Soient X et Y des ensembles. S’il existe une surjection f de X sur Y, on a Card(Y) ≤ Card(X). ↩ 3 03KM
Définition 3 Soit (αᵢ)_i ∈ I une famille de cardinaux. Le cardinal de l’ensemble produit (resp. somme) des ensembles αᵢ s’appelle le produit cardinal (resp. la somme cardinale) des αᵢ et se not… 03KN
Proposition 4 Soient (Eᵢ)_i ∈ I une famille d'ensembles, P son produit, S sa somme, aᵢ le cardinal de Eᵢ; le cardinal de P (resp. S) est le produit cardinal (resp. la somme cardinale) de la fami… 03KO
Corollaire Pour toute famille (Eᵢ)_i ∈ I d'ensembles, le cardinal de la réunion ⋃_i ∈ I Eᵢ est au plus égal à la somme ∑_i ∈ I Card(Eᵢ). ↩ 1 03KP
Proposition 5 a) Soit (aᵢ)_i ∈ I une famille de cardinaux, et soit f une bijection d'un ensemble K sur l'ensemble I; on a ↩ 3 03R1
Corollaire Soient a, b, c des cardinaux; on a ↩ 4 03R2
Proposition 6 Soient (aᵢ)_i ∈ I une famille de cardinaux, et J (resp. K) une partie de I telle que l’on ait aᵢ = 0 pour tout i ∉ J (resp. aᵢ = 1 pour tout i ∉ K); on a alors ↩ 2 03R3
Corollaire 1 Pour tout cardinal a, on a a + 0 = a.1 = a. ↩ 1 03R4
Corollaire 2 Soient a et b des cardinaux, et soit I un ensemble équipotent à b; pour tout i ∈ I, soit aᵢ = a, cᵢ = 1; on a ↩ 2 03R5
Proposition 7 Soit (αᵢ)_i ∈ I une famille de cardinaux; pour que l’on ait P_i ∈ I αᵢ ≠ 0, il faut et il suffit que l’on ait αᵢ ≠ 0 pour tout i ∈ I. ↩ 1 03R6
Proposition 8 Si a et b sont des cardinaux tels que a + 1 = b + 1, on a a = b. ↩ 3 03R7
Définition 4 Soient a et b des cardinaux; le cardinal de l’ensemble des applications de b dans a se note aᵇ, par abus de notation. 03KQ
Proposition 9 Soient X et Y deux ensembles, a et b leurs cardinaux; l’ensemble X^Y a pour cardinal aᵇ. 03KR
Proposition 10 Soient a et b des cardinaux, et I un ensemble tel que Card(I) = b; si αᵢ = a pour tout i ∈ I, on a aᵇ = P_i ∈ I αᵢ. ↩ 4 03KS
Corollaire 1 Soient a un cardinal et (bᵢ)_i ∈ I une famille de cardinaux. On a a^∑_i ∈ I bᵢ = P_i ∈ I a^bᵢ. En effet, soit S l’ensemble somme des bᵢ, et posons αₛ = a pour tout s ∈ S. Les deux… ↩ 1 03KT
Corollaire 2 Soient (aᵢ)_i ∈ I une famille de cardinaux, et b un cardinal ; on a (P_i ∈ I aᵢ)ᵇ = P_i ∈ I aᵢᵇ. En effet, posons a_i,β = aᵢ pour tout couple (i, β) ∈ I × b. On a alors, en vertu d… 03KU
Corollaire 3 Soient a, b, c des cardinaux ; on a aᵇᶜ = (aᵇ)ᶜ. En effet, posons b_γ = b pour tout γ ∈ c. On a aᵇᶜ = a^∑_γ ∈ c b_γ = P_γ ∈ c a^b_γ = (aᵇ)ᶜ, en vertu du cor. 1. 03KV
Proposition 11 Soit a un cardinal. On a a⁰ = 1, a¹ = a, 1ᵃ = 1 ; si a ≠ 0, on a 0ᵃ = 0. En effet, il existe une application et une seule de ∅ dans un ensemble quelconque (l’application de graphe… 03KW
Proposition 12 Soient X un ensemble et a son cardinal ; le cardinal de l’ensemble 𝔓(X) des parties de X est 2ᵃ. Soient α et β les éléments du cardinal 2 ; pour toute partie Y de X, soit f_Y l’app… ↩ 4 03KX
Proposition 13 Soient a et b des cardinaux ; pour que l’on ait a ≥ b, il faut et il suffit qu’il existe un cardinal c tel que a = b + c. En effet, la relation a ≥ b signifie qu’il existe une part… ↩ 4 03KY
Proposition 14 Soient (αᵢ)_i ∈ I et (bᵢ)_i ∈ I deux familles de cardinaux ayant même ensemble d'indices I, et telles que αᵢ ≥ bᵢ pour tout i ∈ I; on a alors ↩ 5 03KZ
Corollaire 1 Soit (αᵢ)_i ∈ I une famille de cardinaux. Pour toute partie J de I, on a ∑_i ∈ J αᵢ ≤ ∑_i ∈ I αᵢ. Si en outre on a αᵢ ≠ 0 pour tout i ∈ I - J, on a ∏_i ∈ J αᵢ ≤ ∏_i ∈ I αᵢ. ↩ 1 03L0
Corollaire 2 Si a, a', b, b' sont des cardinaux tels que a ≤ a', b ≤ b' et a' > 0, on a a^b' ≤ a'^b'. 03L1
Théorème 2 (Cantor) Pour tout cardinal a, on a 2ᵃ > a. ↩ 4 03R8
Corollaire Il n'existe pas d'ensemble dont tout cardinal soit élément. 03L2

§ 4. Entiers naturels. Ensembles finis

Définition 1 On dit qu'un cardinal a est fini si a ≠ a + 1; un cardinal fini s'appelle aussi un entier naturel (ou simplement un entier si aucune confusion n'est à craindre.)¹ On dit qu’un ense… ↩ 1 03R9
Proposition 1 Pour qu’un cardinal a soit fini, il faut et il suffit que a + 1 soit fini. ↩ 1 03RA
Proposition 2 Soit n un entier. Tout cardinal a tel que a ≤ n est un entier. Si n ≠ 0, il existe un entier m et un seul tel que n = m + 1, et la relation a < n est équivalente à a ≤ m. ↩ 11 03RB
Corollaire 1 Toute partie d’un ensemble fini est finie. 03RC
Corollaire 2 Si X est une partie d’un ensemble fini E, distincte de E, on a Card (X) < Card (E). ↩ 2 03RD
Corollaire 3 Si f est une application d’un ensemble fini E dans un ensemble F, (E) est une partie finie de F. ↩ 2 03RE
Corollaire 4 Soient E et F deux ensembles finis ayant le même nombre d’éléments, et f une application de E dans F. Les propriétés suivantes sont équivalentes : a) f est une injection ; b) f est… ↩ 2 03RF
Remarque On utilise souvent, sous le nom de « principe de récurrence » divers critères qui se déduisent aisément de C61, et dont nous allons indiquer les plus importants: 077T
Proposition 3 Soit E un ensemble préordonné filtrant à droite (resp. un ensemble ordonné réticulé, resp. un ensemble totalement ordonné). Toute partie finie non vide de E est majorée (resp. adme… ↩ 3 03L9
Corollaire 1 Tout ensemble fini totalement ordonné est bien ordonné et admet un plus grand élément. ↩ 5 03LA
Corollaire 2 Tout ensemble ordonné fini admet un élément maximal. ↩ 1 03LB
Définition 2 Soit E un ensemble. On dit qu’un ensemble 𝔖 de parties de E est de caractère fini si la relation X ∈ 𝔖 est équivalente à la relation « toute partie finie de X appartient à 𝔖 ». 03LC
Exemple 1 L’ensemble des parties totalement ordonnées d’un ensemble ordonné E est de caractère fini : en effet, pour qu’une partie X de E soit totalement ordonnée, il faut et il suffit que t… 03T9
Exemple 2 \ L’ensemble des parties libres d’un module est de caractère fini (A, II, § 1, n° 11). Il en est de même de l’ensemble des parties algébriquement libres d’une extension d’un corps… 03TA
Exemple 3 L’ensemble des sous-modules d’un module E n’est pas de caractère fini, car une partie finie d’un sous-module de E n’est pas nécessairement un sous-module de E. 03TB
Théorème 1 Tout ensemble 𝔖 de parties d’un ensemble E, de caractère fini, admet un élément maximal (quand on l’ordonne par inclusion). 03LD

§ 5. Calcul sur les entiers

Proposition 1 Soit (aᵢ)_i ∈ I une famille finie d’entiers. Les cardinaux ∑_i ∈ I aᵢ et ∏_i ∈ I aᵢ sont alors des entiers. ↩ 1 03LP
Corollaire 1 La réunion E d'une famille finie (Xᵢ)_i ∈ I d'ensembles finis est un ensemble fini. ↩ 2 03LQ
Corollaire 2 Le produit d'une famille finie d'ensembles finis est un ensemble fini. 03LR
Corollaire 3 Si a et b sont des entiers, aᵇ est un entier. 03LS
Corollaire 4 L'ensemble des parties d'un ensemble fini E est fini. ↩ 1 03LT
Proposition 2 Soient a et b deux entiers ; pour que a < b, il faut et il suffit qu'il existe un entier c 0 tel que b = a + c. ↩ 4 03LU
Proposition 3 Soient (aᵢ)_i ∈ I et (bᵢ)_i ∈ I deux familles finies d'entiers telles que aᵢ ≤ bᵢ pour tout i ∈ I et aᵢ < bᵢ pour un indice i au moins. On a alors ∑_i ∈ I aᵢ < ∑_i ∈ I bᵢ. Si on su… ↩ 4 03LV
Corollaire 1 Soient a, a' et b des entiers tels que a < a' et b > 0; alors aᵇ < a'ᵇ. 03LW
Corollaire 2 Soient a, b et b' des entiers tels que a > 1 et b < b'; on a alors aᵇ < a^b'. 03LX
Corollaire 3 Soient a, b, b' des entiers (resp. des entiers tels que a > 0). Pour que l’on ait a + b = a + b' (resp. ab = ab'), il faut et il suffit que l’on ait b = b'. ↩ 2 03LY
Corollaire 4 Si a et b sont des entiers tels que a leqslant b, il existe un entier c et un seul tel que b = a + c. ↩ 1 03LZ
Proposition 4 Soient a et b des entiers; l’application x ↦ a + x est un isomorphisme strictement croissant de l’intervalle [0, b] sur l’intervalle [a, a + b], et y ↦ y - a est l’isomorphisme réc… ↩ 1 03M0
Proposition 5 Si a et b sont des entiers tels que a ≤ b, l’intervalle [a, b] est un ensemble fini dont le nombre d’éléments est (b - a) + 1. ↩ 3 03M1
Proposition 6 Pour tout ensemble fini E, totalement ordonné, ayant n éléments (n ≥ 1), il existe un isomorphisme et un seul de E sur l’intervalle [1, n]. ↩ 3 03M2
Proposition 7 Pour tout couple de parties A, B d’un ensemble E, on a 03M3
Théorème 1 Soient a et b des entiers tels que b > 0; il existe des entiers q et r tels que a = bq + r et r < b, et les entiers q et r sont déterminés de façon unique par ces conditions. ↩ 2 03M4
Définition 1 Les notations étant celles du th. 1, on dit que r est le reste de la division de a par b. Si r = 0, on dit que a est multiple de b, ou que a est divisible par b, ou que b est un di… 03M5
Proposition 8 Soit b un entier > 1. Pour tout entier k > 0, soit Eₖ le produit lexicographique (III, p. 22) de la famille (Jₙ)_0 ≤ n ≤ k-1 d’intervalles tous identiques à (0, b-1). Pour tout r =… ↩ 1 03M6
Proposition 9 (principe des bergers) Soient E et F deux ensembles, a et b leurs cardinaux, f une surjection de E sur F telle que les ensembles f⁻¹(y), pour y ∈ F, aient tous même cardinal c; on a alors a = bc. ↩ 3 03M7
Définition 2 Soit n un entier ; on note n! (qui se lit « factorielle n ») le produit ∏_i < n (i + 1). 03M8
Proposition 10 Soient m et n des entiers tels que m ≤ n. Alors n!/(n - m)! est le nombre des applications injectives d’un ensemble A à m éléments dans un ensemble B à n éléments. 03M9
Corollaire Le nombre de permutations d'un ensemble fini à n éléments est égal à n!. ↩ 1 03MA
Proposition 11 Soient E un ensemble fini à n éléments, et (pᵢ)_1 ≤ i ≤ h une suite finie d'entiers telle que ∑ᵢ₌₁ʰ pᵢ = n. Alors le nombre des recouvrements (Xᵢ)_1 ≤ i ≤ h de E par des ensembles… ↩ 1 03MB
Corollaire 1 Soient A un ensemble à n éléments, et p un entier ≤ n. Le nombre des parties à p éléments de A est n!/(p!(n-p)!). ↩ 2 03MC
Corollaire 2 Soient E et F des ensembles finis totalement ordonnés ayant respectivement p et n éléments. Le nombre des applications strictement croissantes de E dans F est alors binomnp. 03RG
Proposition 12 Pout tout entier n, on a ∑ₚ binomnp = 2ⁿ. 03RH
Proposition 13 Soient n et p des entiers ; on a ↩ 2 03RI
Proposition 14 Soit n un entier 0 ; le nombre aₙ (resp. bₙ) des couples (i, j) d’entiers tels que 1 ≤ i ≤ j ≤ n (resp. 1 ≤ i < j ≤ n) est (n(n+1))/2 (resp. (n(n-1))/2). 03RJ
Corollaire Pour tout entier n > 0, on a ∑ᵢ₌₁ⁿ i = (n(n+1))/2. ↩ 1 03RK
Proposition 15 Soient n et h des entiers, et E un ensemble à h éléments. Le nombre des applications u de E dans 0, n telles que ∑_x ∈ E u(x) ≤ n (resp. ∑_x ∈ E u(x) = n pour h > 0) est binomn+hn… ↩ 1 03RL

§ 6. Ensembles infinis

Définition 1 On dit qu’un ensemble est infini s’il n’est pas fini. 03MV
Théorème 1 La relation « x est un entier » est collectivisante. ↩ 1 03MW
Définition 2 On appelle suite (resp. suite d’éléments d’un ensemble E) une famille (resp. une famille d’éléments de E) dont l’ensemble d’indices est une partie de N; la suite est dite infinie s… 03MX
Remarque Soient E un ensemble, A une partie de E, g une application de A dans E, a un élément de A. Prenons pour S[u] le terme g(u). On peut appliquer le critère C63, qui prouve l'existence… 03MY
Théorème 2 Pour tout cardinal infini a, on a a² = a. Nous utiliserons deux lemmes. ↩ 6 03MZ
Lemme 1 Tout ensemble infini E contient un ensemble équipotent à N. Il existe sur E une relation de bon ordre (III, p. 20, th. 1) que nous noterons x ≤ y. L'hypothèse entraîne que l'ensemb… ↩ 2 03N0
Lemme 2 L'ensemble N × N est équipotent à N. 03N1
Corollaire 1 Si a est un cardinal infini, on a aⁿ = a pour tout entier n geqslant 1. C’est évident par récurrence sur n. 0E46
Corollaire 2 Le produit d’une famille finie (αᵢ)_i ∈ I de cardinaux non nuls, dont le plus grand est un cardinal infini α, est égal à α. Soit b ce produit, et soit n le nombre d’éléments de I… 0E47
Corollaire 3 Soient a un cardinal infini, et (αᵢ)_i ∈ I une famille de cardinaux leqslant a dont l’ensemble d’indices I ait un cardinal leqslant a. On a alors ∑_i ∈ I αᵢ leqslant a; en outre, s… 0E48
Corollaire 4 Si a et b sont deux cardinaux non nuls dont l’un est infini, on a ab = a + b = sup(a, b). Cela résulte aussitôt des cor. 2 et 3. 0E49
Définition 3 On dit qu’un ensemble est dénombrable s’il est équipotent à une partie de l’ensemble N des entiers. 03N6
Proposition 1 Toute partie d’un ensemble dénombrable est dénombrable. Le produit d’une famille finie d’ensembles dénombrables est dénombrable. La réunion d’une suite d’ensembles dénombrables est… 03N7
Proposition 2 Tout ensemble infini dénombrable E est équipotent à N. En effet, on a Card(E) leqslant Card(N) par définition, et comme E est infini, Card(N) leqslant Card(E). 03N8
Proposition 3 Tout ensemble infini E admet une partition (Xᵢ)_i ∈ I formée d'ensembles infinis dénombrables Xᵢ, l'ensemble d'indices I étant équipotent à E. On a en effet Card(E) = Card(E)Card(\… ↩ 2 03N9
Proposition 4 Soit f une application d'un ensemble E sur un ensemble infini F, telle que, pour tout y ∈ F, f⁻¹(y) soit dénombrable. Alors F est équipotent à E. En effet, les f⁻¹(y) (y ∈ F) forme… 03NA
Proposition 5 L'ensemble 𝔉(E) des parties finies d'un ensemble infini E est équipotent à E. Pour tout entier n, notons 𝔉ₙ l'ensemble des parties à n éléments de E. Pour tout X ∈ 𝔉ₙ, il existe un… 03NB
Corollaire L'ensemble S des suites finies d'éléments d'un ensemble infini E est équipotent à E. En effet, S est la réunion des Eᴵ, où I parcourt l'ensemble 𝔉(N) des parties finies de N. Or, p… 0E4A
Définition 4 On dit qu'un ensemble a la puissance du continu s'il est équipotent à l'ensemble des parties de N. 03NC
Définition 5 On dit qu'une suite (xₙ)_n ∈ N d'éléments d'un ensemble E est stationnaire s'il existe un entier m tel que xₙ = xₘ pour tout entier n ≥ m. 03ND
Proposition 6 Soit E un ensemble ordonné. Les propositions suivantes sont équivalentes: a) Toute partie non vide de E a un élément maximal. b) Toute suite croissante (xₙ) d’éléments de E est sta… ↩ 4 03NE
Corollaire 1 Pour qu’un ensemble totalement ordonné E soit bien ordonné, il faut et il suffit que toute suite décroissante d’éléments de E soit stationnaire. 03NF
Corollaire 2 Toute suite croissante d’éléments d’un ensemble ordonné fini est stationnaire. 03NG
Proposition 7 (« principe de récurrence nœthérienne ») Soient E un ensemble nœthérien, F une partie de E ayant la propriété suivante: si a ∈ E est tel que la relation x > a entraîne x ∈ F, alors a ∈ F. Dans ces conditions, on a F = E. 03RM

§ 7. Limites projectives et limites inductives

Exemple 1 Supposons que la relation de préordre dans I soit la relation d’égalité. Alors les seuls couples (α, β) tels que α ≤ β sont les couples (α, α) pour α ∈ I, et comme f_α α est l’appl… ↩ 1 03TF
Exemple 2 Supposons que I soit filtrant à droite, que pour tout α ∈ I, E_α soit égal à un même ensemble F et que pour α ≤ β, f_α β soit l’application identique de F sur lui-même. Alors E = l… ↩ 1 03TG
Proposition 1 Soient I un ensemble préordonné, (E_α, f_α β) un système projectif d’ensembles relativ à I, E = lim_← E_α sa limite projective, et pour tout α ∈ I, soit f_α : E → E_α l’application… ↩ 4 03OC
Corollaire 1 Soient (E_α, f_α β) et (F_α, g_α β) deux systèmes projectifs d’ensembles relatifs à un même ensemble d’indices I; soient E = lim_← E_α, F = lim_← F_α, et pour tout α ∈ I, soit f_α… 03RN
Corollaire 2 Soient (E_α, f_αβ), (F_α, g_αβ), (G_α, h_αβ) trois systèmes projectifs d'ensembles relatifs à I; soient E = lim ← E_α, F = lim ← F_α, G = lim ← G_α, et soit f_α (resp. g_α, h_α) l'… ↩ 1 03RO
Proposition 2 Soient (E_α, f_αβ), (E'_α, f'_αβ) deux systèmes projectifs d'ensembles relatifs à I, et pour chaque α ∈ I, soit u_α une application de E_α dans E'_α, les u_α formant un système pro… ↩ 2 03RP
Corollaire Si u_α est injective (resp. bijective) pour tout α ∈ I, u est injective (resp. bijective). 03OD
Proposition 3 Soient I un ensemble préordonné, (E_α, f_αβ) un système projectif d’ensembles relatif à I, E = lim_← E_α sa limite projective. Soient J une partie cofinale de I, filtrante à droite… 03OE
Proposition 4 Si (E_α^λ, f_α β^λ μ) est un système projectif d’ensembles relatif à un produit I × L d’ensembles préordonnés, on a, à une bijection canonique près (16) lim_← α, λ E_α^λ = lim_← λ… ↩ 2 03OF
Corollaire 1 Soit (E_α^'λ, f_α β^'λ μ) un second système projectif d’ensembles relatif à I × L, et, pour tout (α, λ) ∈ I × L, soit u_α^λ une application de E_α^λ dans E_α^'λ, les u_α^λ formant… 03OG
Corollaire 2 Soit (E_α^λ, f_α β^λ)_λ ∈ L une famille de systèmes projectifs relatifs à I. Alors, si on note ∏_λ ∈ L f_α β^λ l’extension aux produits de la famille d’applications (f_α β^λ)_λ ∈ L… ↩ 1 03OH
Proposition 5 Soit (E_α, f_αβ) un système projectif d'ensembles relatif à un ensemble préordonné filtrant I, qui admet une partie cofinale dénombrable; supposons en outre que les f_αβ soient sur… 03OI
Théorème 1 On suppose que I est filtrant, que les 𝔖_α satisfont aux conditions (i) et (ii), et en outre que le système projectif (E_α, f_αβ) possède les propriétés suivantes: ↩ 2 03RQ
Remarque 1 Supposons que dans l'énoncé du th. 1, on remplace la condition (iii) par la condition plus faible suivante: 03OJ
Exemple 1 Soient A, B deux ensembles, (V_α)_α ∈ I une famille de parties de A, dont l’ensemble d’indices I est filtrant à droite, telle que la relation α ≤ β entraîne V_β ⊂ V_α. Désignons pa… 03TM
Exemple 2 Supposons que pour tout α ∈ I, E_α soit égal à un ensemble F et que pour α ≤ β, g_βα soit l’application identique de F sur lui-même. Alors il existe une bijection canonique de lim… ↩ 1 03TN
Lemme 1 Soient (E_α, f_β α) un système inductif d’ensembles, E = lim E_α sa limite inductive, et pour tout α ∈ I, soit f_α : E_α → E l’application canonique. ↩ 11 03OK
Proposition 6 Soient I un ensemble préordonné filtrant à droite, (E_α, f_β α) un système inductif d’ensembles, E = lim E_α sa limite inductive, et pour tout α ∈ I, soit f_α : E_α → E l’applicati… ↩ 8 03RR
Corollaire 1 Soient (E_α, f_β α) et (F_α, g_β α) deux systèmes inductifs d’ensembles relatifs à un même ensemble d’indices I; soient E = lim → E_α, F = lim → F_α, et pour tout α ∈ I, soit f_α (… 03RS
Corollaire 2 Soient (E_α, f_βα), (F_α, g_βα), (G_α, h_βα) trois systèmes inductifs d’ensembles relatifs à I; soient E = lim E_α, F = lim F_α, G = lim G_α, et soit f_α (resp. g_α, h_α) l’applica… ↩ 1 03RT
Proposition 7 Soient (E_α, f_βα), (E'_α, f'_βα) deux systèmes inductifs d’ensembles relatifs à I, et pour chaque α ∈ I, soit u_α une application de E_α dans E'_α, les u_α formant un système indu… ↩ 1 03RU
Corollaire Soient (E_α, f_βα), (E'_α, f'_βα) deux systèmes inductifs d’ensembles, (u_α) un système inductif d’applications u_α : E_α → E'_α, et soit u = lim u_α. ↩ 1 03ON
Proposition 8 Soient I un ensemble préordonné filtrant à droite, (E_α, f_β α) un système inductif d’ensembles relatif à I, E = lim_longrightarrow E_α sa limite inductive. Soient J une partie cof… 03OP
Proposition 9 Si (E_α^λ, f_βα^μλ) est un système inductif d'ensembles relatif à un produit I × L de deux ensembles préordonnés filtrants à droite, on a, à une bijection canonique près, (32) lim_… 03RV
Corollaire Soit (E'_α, f'_βα^μλ) un second système inductif d'ensembles relatif à I × L, et, pour chaque (α, λ) soit u_α^λ une application de E_α^λ dans E'_α, les u_α^λ formant un système ind… 03OQ
Proposition 10 Soient (E_α, f_βα), (E'_α, f'_βα) deux systèmes inductifs d'ensembles relatifs à un même ensemble d'indices préordonné filtrant à droite I; soient E = lim_longrightarrow E_α, E' =… ↩ 1 03RW
Corollaire Soient (F_α, g_βα), (F'_α, g'_βα) deux systèmes inductifs d’ensembles relatifs à I, et pour tout α ∈ I, soient u_α : E_α → F_α, u'_α : E'_α → F'_α des applications formant deux sys… 03RX

IV. Structures

§ 1. Structures et isomorphismes

Exemple Étant donnés deux ensembles E, F, l'ensemble 𝔓(𝔓(E)) × 𝔓(F) est un échelon sur E, F, de schéma (0, 1), (0, 2), (1, 0), (3, 0), (2, 0), (4, 5). C'est aussi l'échelon sur E, F, de sc… 03V4
Exemple 1 Prenons pour T la théorie des ensembles et considérons l’espèce de structure sans ensemble de base auxiliaire, comportant un ensemble de base principal A, la caractérisation typiqu… ↩ 2 03V5
Exemple 2 Prenons pour T la théorie des ensembles, et considérons l’espèce de structure sans ensemble de base auxiliaire, comportant un ensemble de base principal A, la caractérisation typiq… ↩ 3 03V6
Exemple 3 T étant toujours la théorie des ensembles, considérons l’espèce de structure sans ensemble de base auxiliaire, comportant un ensemble de base principal A, la caractérisation typiqu… ↩ 5 03V7
Exemple 4 \ Prenons pour T la théorie de l’espèce de structure de corps, qui comporte entre autres une constante K comme unique ensemble de base (principal). L’espèce de structure d’espace v… ↩ 1 03V8
Exemple 5 Prenons de nouveau pour T la théorie des ensembles; dans cette théorie, le corps C des nombres complexes est un terme, qui ne contient aucune lettre. L’espèce de structure de varié… 03V9
Remarque — 1) Il arrive souvent dans les applications (comme dans l’Exemple 4 ci-dessus) que l’échelon S(E₁, …, Eₙ, A₁, …, Aₘ) est un produit d’échelons 03VA
Remarque Par abus de langage, lorsque fᵢ est une bijection quelconque de Eᵢ sur E'ᵢ (1 ≤ i ≤ n), on dit que (f₁, …, fₙ) est un isomorphisme de (E₁, …, Eₙ) sur (E'₁, …, E'ₙ) pour l’espèce de… 03VD
Exemple 1 L’espèce de structure de groupe topologique comporte un seul ensemble de base principal A, ne comporte aucun ensemble de base auxiliaire, et la structure générique correspondante e… 03VE
Exemple 2 L’espèce de structure d’espace vectoriel sur C (resp. sur R) comporte un ensemble de base principal E, un ensemble de base auxiliaire égal à C (resp. R) et a pour caractérisation t… 03VF
Exemple 3 Supposons que Θ ait mêmes ensembles de base (principaux et auxiliaires) que Σ, et même caractérisation typique. Si en outre l'axiome de Σ implique (dans T) celui de Θ, il est clair… 03VG
Exemple 4 \ Si Σ et Θ sont toutes deux l'espèce de structure de groupe (resp. d'anneau), on définit en Algèbre (A, I, § 1, no 5) un procédé de déduction associant à toute structure de groupe… 077U
Remarque Lorsque P est un « multiplet » (P₁, …, P_q), on dit aussi que les termes P₁, …, P_q constituent un procédé de déduction d'une structure d'espèce Θ à partir d'une structure d'espèce… 03VH
Exemples 1) Soit Σ l’espèce de structure de groupe commutatif (A, I, § 4, n° 2); elle comporte un seul ensemble de base (principal) A, et sa structure générique une seule lettre F; la carac… 03VI

§ 2. Morphismes et structures dérivées

Exemple 1 Prenons pour Σ l'espèce de structure d'ordre et pour σx, y, s, t l'ensemble des applications f de x dans y telles que la relation (u, v) ∈ s entraîne (f(u), f(v)) \in t. Avec les n… 03VL
Exemple 2 Prenons pour Σ une espèce de structure algébrique comportant une seule loi de composition (interne) (IV, p. 5, Exemple 2). Soient A, A' deux ensembles munis de structures d'espèce… ↩ 1 03VM
Exemple 3 Prenons pour Σ l'espèce de structure topologique (IV, p. 5, Exemple 3). Soient A, A' deux ensembles munis de topologies V, V' respectivement; considérons les applications f de A da… ↩ 2 03VN
Remarque Pour une espèce de structure donnée Σ, on a souvent l'occasion de définir divers termes σ x, y, s, t qui satisfont aux conditions (MOI), (MO{II}) et (MO{III}). Par exemple, pour l'… 03VO
Remarque Lorsqu'une espèce de structure Σ comporte plusieurs ensembles de base principaux x₁, …, xₙ, et des ensembles de base auxiliaires A₁, …, Aₘ, un σ-morphisme est un système (f₁, …, fₙ… 03VP
Exemple 1 Pour qu’une structure d’ordre de graphe s sur un ensemble A soit plus fine qu’une structure d’ordre de graphe s′, il faut et il suffit que s ⊂ s'. Autrement dit, la relation x ≤ y… 03VQ
Exemple 2 Considérons deux structures algébriques F, F′ de même espèce Σ sur un ensemble A, F et F′ étant les graphes des lois de composition de ces deux structures. D’après la définition de… ↩ 1 03VR
Exemple 3 Soient V, V′ deux topologies sur un même ensemble A. Dire que V est plus fine que V′ signifie, en vertu de la définition des morphismes (IV, p. 12, Exemple 3) que V' ⊂ V; en d’autr… 03VS
Remarque Nous venons de voir un exemple (Exemple 2) où deux structures comparables de même espèce Σ sont nécessairement identiques. On rencontre de nombreux exemples de telles structures: s… 03VT
Remarque Soit (S_λ)_λ ∈ L une famille de structures d'espèce Σ sur un même ensemble A; désignons par A_λ l'ensemble A muni de la structure S_λ, et par Id_λ l'application identique de A dans… 03VU
Remarque Pour la plupart des structures usuelles, la condition énoncée dans CST16 est non seulement suffisante, mais aussi nécessaire pour que f soit un morphisme (cf. IV, p. 30, exerc. 7)… 03VV
Remarque Soient A un ensemble muni d'une structure S d'espèce Σ, R une relation d'équivalence dans A telle qu'il existe sur E = A/R une structure quotient S' de S par R. Soit φ l'applicatio… 03VW