Book E · English

Index of statements

The 381 statements of Theory of Sets, by chapter and §. Pick a kind, filter by a word, or put the most cited first.

Most cited first

I. Description of formal mathematics

§ 1. Terms and relations

Example 1 The assembly ∨ 1 is represented by ⇒. 03P0
Example 2 The following symbols represent assemblies (and very long ones at that) : 03P1
Example The symbol τₓ(∈ xy) represents the assembly 03RY
Example If we replace x by square wherever x occurs in the assembly ∨∈ xy=xx, we obtain the assembly ∨∈square y=squaresquare. 03TO
Remark When an abbreviating symbol Σ is introduced, by means of a definition, to represent a certain assembly, the (usually tacit) convention is made of representing the assembly obtained… 03P2
Example In the theory of sets, in which ∈ is a relational sign of weight 2, the following sequence of assemblies is a formative construction: 077Q
Remark Intuitively, terms are assemblies which represent objects, and relations are assemblies which represent assertions which can be made about these objects. Condition (a) means that t… 077R
Examples The symbols ∅, N, “the real line”, “the Γ function”, f∘ g represent terms. The symbols π=sqrt2+sqrt3, 1∈2, “every finite division ring is a field”, “the zeros of ζ(s) other than -2… 0E3Y

§ 2. Theorems

Remark Under the hypotheses of C5, if the theory T turns out to be contradictory, the same will be true of T'. For if A and "not A" are theorems in T, then (T₁|a₁) … (Tₕ|aₕ)A and not(T₁|a… 03G7

§ 5. Equalitarian theories

Theorem 1 x = x. ↩ 2 03P3
Theorem 2 (x = y) ⇔ (y = x). 03P4
Theorem 3 ((x = y) and (y = z)) ⇒ (x = z). 03P5

App. 0. Characterization of terms and relations

Proposition 1 If A₁, A₂, ..., Aₚ are p significant words and if f is a sign of weight p, then the word f A₁ A₂ … Aₚ is significant. ↩ 1 03P6
Proposition 2 A word is significant if and only if it is balanced. ↩ 1 03P7
Lemma 1 Let A be a balanced word. Then for each integer k such that 0 leqslant k < l(A) there exists exactly one balanced segment S of A which begins at the (k + 1)th place. ↩ 1 03P8
Lemma 2 Every balanced word A can be put in the form 03GT
Corollary 1 Let A be a significant word. For each integer k such that 0≤ k<l(A) there is exactly one significant segment of A which begins at the (k+1)th place. 03GU
Corollary 2 Every significant word may be written in exactly one way in the form fA₁A₂… Aₚ, where the Aᵢ are significant and n(f)=p. ↩ 2 03GV
Remark Except in certain mathematical theories which are particularly weak in axioms (cf. Exercise 7) we have no general procedure of this type to enable us to test whether or not a given… 03GW

II. Theory of sets

§ 1. Collectivizing relations

Definition 1 The relation denoted by (∀ z)((z ∈ x) ⇒ (z ∈ y)), in which only the letters x and y appear, is written in one of the following ways : x ⊂ y, y ⊃ x, "x is contained in y", "y contai… ↩ 1 03H5
Proposition 1 x ⊂ x. 03P9
Proposition 2 (x ⊂ y and y ⊂ z) ⇒ (x ⊂ z). 03PA
Example 1 The relation x ∈ y is clearly collectivizing in x. 03RZ
Example 2 The relation x ≠ x is not collectivizing in x; in other words, (not Collₓ(x ≠ x)) is a theorem. Let us argue by contradiction and suppose that x ≠ x is collectivizing. Let a be an… 03S0
Definition 2 The set E_z (z = x or z = y), whose only elements are x and y, is denoted by x, y. 03H6
Remark Let R be a relation which is collectivizing in x, and let S be a relation such that (∀ x)(S ⇒ R) is a theorem. Then S is collectivizing in x; for R is equivalent to x ∈ Eₓ(R), so t… 03H7
Definition 3 Let A be a subset of a set X. The set of elements of X which do not belong to A, that is to say the set Ex (x ∉ A and x ∈ X), is called the complement of A in X, and is denoted by… 03H8
Theorem 1 The relation (∀ x)(x ∉ X) is functional in X. 03H9
Remark There exists no set of which every object is an element; in other words, "not (∃ X)(∀ x)(x ∈ X)" is a theorem. For if there were such a set, then by C52 every relation would be col… 03PB

§ 2. Ordered pairs

Theorem 1 The relation 03PC
Definition 1 Given two sets X and Y, the set 03PD
Proposition 1 If A', B' are non-empty sets, the relation A' × B' ⊂ A × B is equivalent to "A' ⊂ A and B' ⊂ B". 03PE
Proposition 2 Let A and B be two sets. The relation A × B = ∅ is equivalent to "A = ∅ or B = ∅". ↩ 1 03PF

§ 3. Correspondences

Definition 1 G is said to be a graph if every element of G is an ordered pair, i.e., if the relation 03PG
Proposition 1 Let G be a graph. There exists exactly one set A and exactly one set B with the following properties : 03HI
Remark The relation x = y has no graph, for the first projection of the graph, if it existed, would be the set of all objects (cf. § 1, no. 7, Remark). 03S1
Definition 2 A correspondence between a set A and a set B is a triple 03HJ
Definition 3 Let G be a graph and X a set. The set of all objects which correspond under G to elements of X is called the image of X under G and is denoted by G⟨ X ⟩ or G(X). ↩ 1 03PI
Remark 1 Precisely, G⟨ X ⟩ denotes the set E_y((∃ x)(x ∈ X and (x,y) ∈ G)). From now on we shall not usually translate our definitions into formal language. 03PH
Remark 2 The notations G(X) and Γ(X) can occasionally lead to confusion with the notation introduced later (cf. no. 4, Remark following Definition 9). 03S2
Proposition 2 Let G be a graph and let X, Y be two sets; then the relation X ⊂ Y implies G⟨ X ⟩ ⊂ G⟨ Y ⟩. ↩ 1 03PJ
Corollary If A ⊃ pr₁ G, we have G⟨ A ⟩ = pr₂ G. 03PK
Definition 4 Let G be a graph and x an object. The set G⟨ x ⟩ (which is sometimes denoted by G(x), by abuse of language) is called the section of G at x. 03PL
Definition 5 Let G be a graph. The graph whose elements are the ordered pairs (x, y) such that (y, x) ∈ G is called the inverse of G and is denoted by overset-1G. 03PM
Definition 6 Let G, G′ be two graphs. The graph (with respect to x and z) of the relation (∃ y)((x, y) ∈ G and (y, z) ∈ G') is called the composition of G′ and G, and is denoted by G' ∘ G (or s… ↩ 1 03PN
Proposition 3 Let G, G′ be two graphs. The inverse of G′ ∘ G is then overset-1G ∘ overset-1G'. ↩ 1 03HK
Proposition 4 Let G₁, G₂, G₃ be graphs. Then 03HL
Proposition 5 Let G, G′ be graphs and let A be a set. Then ↩ 1 03HM
Definition 7 Let Γ = (G, A, B) and Γ' = (G', B, C) be two correspondences such that the target of Γ is the source of Γ'. Then the correspondence (G' ∘ G, A, C) is called the composition of Γ' a… 03PO
Definition 8 If A is a set, the set Δ_A of all objects of the form (x, x), where x ∈ A, is called the diagonal of A × A. 03PP
Definition 9 A graph F is said to be a functional graph if for each x there is at most one object which corresponds to x under F (Chapter I, § 5, no. 3). A correspondence f = (F, A, B) is said… ↩ 1 03HN
Remark The reader should beware of the confusion which may arise from the simultaneous use of the notations f(x) and f(X) (synonymous with f⟨ X ⟩) introduced in Definition 3 (cf. Exercise… 03HO
Example 1 The empty set is a functional graph. Every function whose graph is empty has domain and range equal to the empty set. Among such functions, the one whose target is empty (i.e., the… ↩ 1 03V1
Example 2 Let A be a set. The identity correspondence of A (no. 3) is a function, called the identity mapping of A. 03V2
Example 1 If f is a mapping of A into B, the function f is equal to the function x → f(x) (x ∈ A, f(x) ∈ B), which is written simply as x → f(x) or also (fₓ)_x ∈ A (the latter notation is es… 03S3
Example 2 Let G be a set of ordered pairs. The functions 03S4
Proposition 6 If f is a mapping of A into B, and g is a mapping of B into C, then g ∘ f is a mapping of A into C. 03HP
Definition 10 Let f be a mapping of A into B. The mapping f is said to be injective, or an injection, if any two distinct elements of A have distinct images under f. The mapping f is said to be… 03HQ
Example 1 If A ⊂ B, the mapping of A into B whose graph is the diagonal of A is injective and is called the canonical mapping or the canonical injection (or simply the injection) of A into B… 03S5
Example 2 Let A be a set. The mapping x → (x, x) of A into the diagonal Δ_A of A × A is a bijective mapping, called the diagonal mapping of A. 03S6
Example 3 Let G be a set of ordered pairs. The mapping pr₁ (resp. pr₂) of G into pr₁G (resp. pr₂G) is surjective; pr₁ is injective if and only if G is a functional graph. 03S7
Example 4 Let G be a set of ordered pairs. The mapping 03S8
Example 5 Let A be a set and b an object. The mapping x → (x,\ b) of A into A × b is a bijection. 03S9
Proposition 7 Let f be a mapping of A into B. Then overset-1f is a function if and only if f is bijective. 03PQ
Remark Let f be a mapping of A into B. For each subset X of A we have (no. 3) X ⊂ overset-1f⟨ f⟨ X⟩⟩. Furthermore, for each subset Y of B we have f⟨ overset-1f⟨ Y⟩⟩ ⊂ Y, for the relation… 03HR
Proposition 8 Let f be a mapping of A into B. If there exists a mapping r (resp. s) of B into A such that r ∘ f (resp. f ∘ s) is the identity mapping of A (resp. B), then f is injective (resp. s… ↩ 5 03HS
Corollary Let A, B be sets, let f be a mapping of A into B, and let g be a mapping of B into A. If g ∘ f is the identity mapping of A and if f ∘ g is the identity mapping of B, then f and g… ↩ 1 03HT
Definition 11 Let f be an injective (resp. surjective) mapping of A into B. Any mapping r (resp. s) of B into A such that r ∘ f (resp. f ∘ s) is the identity mapping of A (resp. B) is called a r… ↩ 6 03HU
Theorem 1 Let f be a mapping of A into B, let f' be a mapping of B into C, and let f'' = f' ∘ f. Then : ↩ 2 03PR
Proposition 9 (a) Let E, F, G be sets, let g be a mapping of E onto F and f a mapping of E into G. Then there exists a mapping h of F into G such that f = h ∘ g if and only if the relation g(x)… ↩ 1 03PS

§ 4. Union and intersection of a family of sets

Definition 1 Let (X_ι)_ι ∈ I be a family of sets (resp. a family of subsets of a set E). The set Eₓ((∃ ι)(ι ∈ I and x ∈ X_ι)), that is to say, the set of all x which belong to at least one set… 03I1
Definition 2 Let (Xₗ)_l∈ I be a family of sets whose index set I is not empty. The set Eₓ((∀ l)((l∈ I)Longrightarrow(x∈ Xₗ))), that is to say, the set of all x which belong to every set of the… 03PT
Definition 3 Let (Xₗ)_l∈ I be a family of subsets of a set E. The set Eₓ(x∈ E and (∀ l)((l∈ I)Longrightarrow(x∈ Xₗ))), 03PU
Proposition 1 Let (X_ι)_ι ∈ I be a family of sets, and let f be a mapping of a set K onto I. Then ↩ 5 03PV
Corollary Let (X_ι)_ι ∈ I be a family of sets such that X_ι = X_varkappa for each pair of indices (ι, varkappa). Then for each α ∈ I we have 03I2
Definition 4 Let 𝔉 be a set of sets and let Φ be the family of sets defined by the identity mapping of 𝔉. The union of the sets of Φ and (if 𝔉 is not empty) the intersection of the sets of Φ ar… 03I3
Proposition 2 Let (X_ι)_ι ∈ I be a family of sets whose index set I is the union of a family (J_λ)_λ ∈ L of sets. Then ↩ 1 03I4
Proposition 3 Let (X_ι)_ι ∈ I be a family of subsets of a set A, and let Γ be a correspondence between A and B. Then ↩ 4 03I5
Proposition 4 Let f be a mapping of A into B and let (Y_ι)_ι ∈ I be a family of subsets of B. Then overset-1f⟨ ⋂_ι ∈ I Y_ι ⟩ = ⋂_ι ∈ I overset-1f⟨ Y_ι ⟩. ↩ 3 03I6
Corollary If f is an injection of A into B and if (X_ι)_ι ∈ I is a family of subsets of A whose index set I is not empty, then f⟨ ⋂_ι ∈ I X_ι ⟩ = ⋂_ι ∈ I f⟨ X_ι ⟩. 03I7
Proposition 5 For every family (X_ι)_ι ∈ I of subsets of a set E, we have ↩ 1 03I8
Proposition 6 Let f be a mapping of A into B. For every subset Y of B, we have ↩ 1 03PW
Corollary Let f be an injection of A into B. For every subset X of A, we have f⟨ A - X ⟩ = f⟨ A ⟩ - f⟨ X ⟩. 03PX
Definition 5 A family of sets (X_ι)_ι ∈ I is said to be a covering of a set E (or to cover E) if E ⊂ ⋃limits_ι ∈ I X_ι. If (X_ι)_ι ∈ I and (Y_varkappa)_varkappa ∈ K are coverings of E, the seco… ↩ 1 03PY
Proposition 7 (1) Let E be a set and (X_ι)_ι ∈ I a covering of E. If f and g are two functions with domain E such that f and g agree on E ∩ X_ι for each ι ∈ I, then f and g agree on E. ↩ 5 03PZ
Definition 6 Two sets A and B are said to be disjoint (or not to intersect) if A ∩ B = ∅. If A ∩ B ≠ ∅, we say that A meets (or intersects) B. Let (X_ι)_ι ∈ I be a family of sets. The sets of t… 03Q0
Proposition 8 Let (X_ι)_ι ∈ I be a family of mutually disjoint sets, and let (f_ι)_ι ∈ I be a family of functions with the same target F such that the domain of f_ι is X_ι for each ι ∈ I. Then t… ↩ 5 03Q1
Definition 7 A partition of a set E is a family of non-empty mutually disjoint subsets of E which covers E. 03Q2
Example For every non-empty set A, the family (x)_x ∈ A is a partition of A. 03I9
Proposition 9 Let (X_ι)_ι ∈ I be a family of sets. Then there exists a set X with the following property : X is the union of a family (X'_ι)_ι ∈ I of mutually disjoint sets such that for each ι… 03Q3
Definition 8 Let (X_ι)_ι ∈ I be a family of sets. The sum of this family is the union of the family of sets (X_ι × ι)_ι ∈ I. ↩ 3 03Q4
Proposition 10 Let (X_ι)_ι ∈ I be a family of mutually disjoint sets. Let A be its union and S its sum. Then there exists a bijective mapping of A onto S. ↩ 1 03IA

§ 5. Product of a family of sets

Proposition 1 (1) If f is a surjection of a set E onto a set F, the canonical extension hatf of f is a surjection of 𝔓(E) onto 𝔓(F). ↩ 1 03IJ
Proposition 2 (1) If u is a surjection of E' onto E and v an injection of F into F', then the mapping f ↦ v ∘ f ∘ u is injective. ↩ 2 03Q5
Corollary If u is a bijection of E' onto E and v is a bijection of F onto F', then f ↦ v ∘ f ∘ u is bijective. 03Q6
Proposition 3 If for every mapping f of B × C into A we denote by tildef the mapping y → f(bullet, y) of C into 𝔉(B, A), then the function f → tildef is a bijection (called the canonical bijecti… ↩ 1 03Q7
Definition 1 Let (X_ι)_ι ∈ I be a family of sets. The set of functional graphs F with domain I such that F(ι) ∈ X_ι for each ι ∈ I is called the product of the family of sets (X_ι)_ι ∈ I and is… 03Q8
Proposition 4 Let (X_ι)_ι ∈ I be a family of sets, and let u be a bijection of a set K onto the index set I. If U is the graph of u, the mapping F → F ∘ U of ∏_ι ∈ I X_ι into ∏_x ∈ K Xᵤ₍ₓ₎ is bi… ↩ 2 03IK
Proposition 5 Let (X_ι)_ι∈ I be a family of sets and let J be a subset of I. If for each ι∈ I we have X_ι≠∅, the projection pr_J is a mapping of ∏_ι∈ IX_ι onto ∏_ι∈ JX_ι. ↩ 1 03Q9
Proposition 6 Let (X_ι)_ι∈ I be a family of sets such that X_ι≠∅ for all ι∈ I. If g is a mapping of J⊂ I into A=⋃_ι∈ IX_ι, such that g(ι)∈ X_ι for all ι∈ J, then there exists an extension f of g… ↩ 6 03QA
Corollary 1 Let (X_ι)_ι∈ I be a family of sets such that for each ι∈ I we have X_ι≠∅. Then for each α∈ I the projection pr_α is a mapping of ∏_ι∈ IX_ι onto X_α. ↩ 2 03QB
Corollary 2 Let (X_ι)_ι ∈ I be a family of sets. Then ∏limits_ι ∈ I X_ι = ∅ if and only if there exists ι ∈ I such that X_ι = ∅. ↩ 4 03QC
Corollary 3 Let (X_ι)_ι ∈ I and (Y_ι)_ι ∈ I be two families of sets having the same index set I. If X_ι ⊂ Y_ι for each ι ∈ I, then ↩ 1 03QD
Proposition 7 Let (X_ι)_ι ∈ I be a family of sets whose index set I is not the empty set. Let (J_λ)_λ ∈ L be a partition of I. Then the mapping ↩ 2 03IN
Remark 1 Let α, β be two distinct objects and let (J_λ)_λ ∈ α, β be a partition of I into two sets J_α, J_β. We thus obtain a one-to-one mapping (again called canonical) of the product ∏_ι… ↩ 1 03SA
Remark 2 Let α, β, γ be three objects, no two of which are equal (three such objects exist; for example, ∅, ∅, ∅), and let A, B, C be sets. Consider the functional graph (α, A), (β, B), (γ… 03SB
Proposition 8 Let ((X_λ,ι)_ι ∈ J_λ)_λ ∈ L be a family (with index set L) of families of sets. Suppose that L ≠ ∅ and that J_λ ≠ ∅ for each λ ∈ L. Let ↩ 2 03IO
Corollary Let (X_ι)_ι ∈ I and (Y_varkappa)_varkappa ∈ K be two families of sets with non-empty index sets I, K. Then ↩ 1 03IP
Proposition 9 Let ((X_λ, ι)_ι ∈ J_λ)_λ ∈ L be a family (with index set L) of families of sets. Let I = ∏_λ ∈ L J_λ. Then ↩ 2 03IQ
Corollary 1 Suppose that L ≠ ∅ and that J_λ ≠ ∅ for each λ ∈ L. If for e achindex λ ∈ L the family (X_λ, ι)_ι ∈ J_λ is a partition of X_λ = ⋃_ι ∈ J_λ X_λ, ι, then the family ( ∏_λ ∈ L X_λ, f(λ… ↩ 1 03QE
Corollary 2 Let (X_ι)_ι ∈ I and (Y_varkappa)_varkappa ∈ K be two families of sets. Then 03QF
Proposition 10 Let (X_ι, varkappa)_(ι, varkappa) ∈ I × K be a family of sets whose index set is the product of two sets I and K. If K ≠ ∅, we have ↩ 1 03QG
Corollary Let (X_ι)_ι ∈ I and (Y_ι)_ι ∈ I be two families of sets with the same index set I ≠ ∅. Then 03IR
Definition 2 Let (X_ι)_ι ∈ I, (Y_ι)_ι ∈ I be two families of sets, and let (g_ι)_ι ∈ I be a family of functions with the same index set I such that g_ι is a mapping of X_ι into Y_ι for each ι ∈… ↩ 2 03IS
Proposition 11 Let (X_ι)_ι ∈ I, (Y_ι)_ι ∈ I, (Z_ι)_ι ∈ I be three families of sets and let (g_ι)_ι ∈ I, (g'_ι)_ι ∈ I be two families of functions, all having the same index set, such that g_ι is… 03IT
Corollary Let (Xᵢ)_i∈ I, (Yᵢ)_i∈ I be two families of sets and let (gᵢ)_i∈ I be a family of functions. If gᵢ is an injection (resp. surjection) of Xᵢ into Yᵢ, for each i∈ I, then the extensi… ↩ 1 03IU

§ 6. Equivalence relations

Example The relation x = y is symmetric and transitive. The relation X ⊂ Y is transitive but not symmetric. The relation X ∩ Y = ∅ is symmetric but not transitive. 077S
Example 1 The relation x = y is an equivalence relation which has no graph, for if it did, the first projection of this graph would be the set of all objects. 03IX
Example 2 The relation "x = y and x ∈ E" is an equivalence relation on E whose graph is the diagonal of E × E. 03SC
Example 3 The relation "there exists a bijection of X onto Y" is an equivalence relation which has no graph (cf. Chapter III, § 3). 03TQ
Example 4 The relation "x ∈ E and y ∈ E" is an equivalence relation on E, whose graph is E × E. 03TR
Example 5 Suppose A ⊂ E; then the relation 03TS
Example 6 \ The relation "x ∈ Z and y ∈ Z and x - y is divisible by 4" is an equivalence relation on Z.\ 03TP
Proposition 1 A correspondence Γ between X and X is an equivalence on X if and only if it satisfies the following conditions : (a) X is the domain of Γ; (b) Γ = overset-1Γ; (c) Γ ∘ Γ = Γ. Let Γ… ↩ 1 03QH
Example 1 Let R be the equivalence relation "x ∈ E and y ∈ E and x = y" on a set E. The equivalence class of x ∈ E is then the set x, and the canonical mapping x → x of E onto E/R is bijecti… 03SD
Example 2 Let E, F be two sets and let R be the equivalence relation on E × F associated with the mapping pr₁ of E × F onto E. The equivalence classes with respect to R are the sets of the f… 03SE
Example 1 The relation "x ∈ E and y ∈ E and x = y" is finer than every equivalence relation on E. The relation "x ∈ E and y ∈ E" is coarser than every equivalence relation on E. 03SF
Example 2 \ The equivalence relation "x ∈ Z and y ∈ Z and x - y is divisible by 4" is finer than the equivalence relation "x ∈ Z and y ∈ Z and x - y is divisible by 2". \ 03SG
Remark Let Px, x' be a relation in which the letters y, y' do not occur. P is said to be compatible with the equivalence relations Rx, y and R'x', y' (with respect to x and x') if the rel… 03IY

III. Ordered sets, cardinals, integers

§ 1. Order relations. Ordered sets

Example 1 The relations of equality and inclusion are not order relations on a set, for the relations x = x and X ⊂ X are not collectivizing (Chapter II, § 1, no. 7). 03SH
Example 2 Let Rx,\ y be an order relation between x and y, and let E be a set such that x ∈ E implies Rx,\ x (notice that the empty set satisfies this condition). The relation "Rx,\ y and x… 03SI
Example 3 Let E, F be sets. The relation "g extends f" is an order relation (between f and g) on the set of mappings of subsets of E into F. ↩ 3 03SJ
Example 4 In the set 𝔓(𝔓(E)) of sets of subsets of a set E, let P be the set of partitions of E (Chapter II, § 4, no. 7). We recall that a partition varpi is said to be coarser than a partit… ↩ 2 03V3
Proposition 1 A correspondence Γ between E and E is an ordering on E if and only if its graph G satisfies the following conditions : 03JA
Example \ Let A be a ring with an identity element. The relation (∃ z)(z ∈ A and y = zx) between two elements x, y of A is a preorder relation on A; it is read "x is a right divisor of y"… 03JB
Example 1 Let E, F be two sets, and let Φ(E, F) be the set of all mappings of subsets of E into F. For each f ∈ Φ(E, F) let G_f be the graph of f, which is a subset of E × F. If we endow Φ(E… 03WB
Example 2 For each partition varpi of a set E, let tildevarpi be the graph of the equivalence relation defined by varpi on E. The mapping varpi → tildevarpi is an isomorphism of the set 𝔏 of… 03WC
Example 3 Let E be a set and let Ω ⊂ 𝔓(E × E) be the set of graphs of preorderings on E (no. 2) (or, by abuse of language, the set of all preorderings on E). The order relation s ⊂ t between… ↩ 1 03WD
Definition 1 Let E and F be preordered sets (the preorder relation in each being denoted by leqslant). A mapping f of E into F is said to be increasing (or order-preserving) if the relation x l… 03JC
Definition 2 Let E and F be two ordered sets. A mapping f of E into F is said to be strictly increasing (or strictly order-preserving) if the relation x < y implies f(x) < f(y); f is said to be… 03JD
Example 1 Let E be a set. The mapping X → E - X of 𝔓(E) (ordered by inclusion) onto itself is strictly decreasing. 03SK
Example 2 Let E be an ordered set. For each x ∈ E let Uₓ be the set of all y ∈ E such that y geqslant x. The mapping x → Uₓ is a strictly decreasing mapping of E into 𝔓(E) (ordered by inclus… 03SL
Proposition 2 Let E, E' be two ordered sets, and let u : E → E' and v : E' → E be two decreasing mappings such that for all x ∈ E and all x' ∈ E' we have v(u(x)) geqslant x and u(v(x')) geqslant… ↩ 2 03JE
Definition 3 Let E be an ordered set. An element a ∈ E is said to be a minimal (resp. maximal) element of E if the relation x leqslant a (resp. x geqslant a) implies x = a. 03JF
Example 1 Let A be a set. In the subset of 𝔓(A) (ordered by inclusion) consisting of the non-empty subsets of A, the minimal elements are the subsets consisting of a single element. 03SM
Example 2 In the set Φ(E, F) of mappings of subsets of E into F (F being non-empty), ordered by the relation "v extends u" between u and v, the maximal elements are the mappings of the whole… 03SN
Example 3 \ In the set of natural integers > 1, ordered by the relation "m divides n" between m and n, the minimal elements are the prime numbers. \ 03SO
Example 4 \ The set of real numbers has no maximal element and no minimal element. \ 03SP
Definition 4 Let E be an ordered set. An element a ∈ E is said to be the least (resp. greatest) element of E if for all x ∈ E we have a leqslant x (resp. x leqslant a). 03JG
Example 1 Let 𝔖 be a non-empty subset of the set 𝔓(E) of subsets of a set E. If 𝔖 has a least (resp. greatest) element A with respect to the inclusion relation, then A is the intersection (r… 03SQ
Example 2 In particular, ∅ is the least element and E the greatest element of 𝔓(E). In the set Φ(E, F) of mappings of subsets of E into F, ordered by extension of mappings (no. 1, Example 3)… 03SR
Proposition 3 Let E be an ordered set and let E' be the disjoint union of E and a set a consisting of a single element. Then there exists a unique ordering on E' which induces the given ordering… ↩ 1 03JH
Definition 5 Let E be a preordered set and let X be a subset of E. Any element x∈ E such that x≤ y (resp. x≥ y) for all y∈ X is called a lower (resp. upper) bound of X in E. 03JI
Definition 6 Let E be an ordered set and let X be a subset of E. An element of E is said to be the greatest lower bound or infimum (resp. least upper bound or supremum) of X in E if it is the g… 03JJ
Proposition 4 Let E be an ordered set and let A be a subset of E which has both a greatest lower bound and a least upper bound in E. Then inf A leqslant sup A if A ≠ ∅; if A = ∅, sup A is the le… ↩ 1 03JK
Proposition 5 Let E be an ordered set and let A, B be two subsets of E, each of which has a least upper bound (resp. greatest lower bound) in E. If A ⊂ B, then sup A leqslant sup B (resp. inf A… ↩ 1 03JL
Corollary Let (x_ι)_ι ∈ I be a family of elements of an ordered set E which has a least upper bound in E. If J is a subset of I such that the family (x_ι)_ι ∈ J has a least upper bound in E… ↩ 1 03JM
Proposition 6 Let (x_ι)_ι ∈ I, (y_ι)_ι ∈ I be two families of elements of an ordered set E, indexed by the same set I, and such that x_ι leqslant y_ι for all ι ∈ I. If both families have a least… 03JN
Proposition 7 Let (x_ι)_ι ∈ I be a family of elements of an ordered set E, and let (J_λ)_λ ∈ L be a covering of the index set I. Suppose that each of the subfamilies (x_ι)_ι ∈ J_λ has a least up… 03JO
Corollary Let (x_λμ)_(λ,\ μ) ∈ L × M be a "double" family of elements of an ordered set E such that for each μ ∈ M the family (x_λμ)_λ ∈ L has a least upper bound in E. For the family (x_λμ)… 03JP
Proposition 8 Let (E_ι)_ι∈ I be a family of ordered sets. Let A be a subset of the product ordered set E = ∏_ι∈ I E_ι, and let A_ι = pr_ι A for each ι ∈ I. For A to have a least upper bound in E… ↩ 1 03QI
Example 1 \ In the ordered set E = R of real numbers, consider the subset F = Q of rational numbers and the set A ⊂ F of rational numbers < sqrt2; sup_E A exists but sup_F A does not. ↩ 1 03SS
Example 2 In the notation of Example 1, let G be the union of A and the set 2; then G ⊂ F and sup_G A exists, but sup_F A does not. 03ST
Example 3 With the same notation, sup_E A = sqrt2, sup_G A = 2. \ 03SU
Proposition 9 Let E be an ordered set, F a subset of E, A a subset of F. If both sup_E A and sup_F A exist, we have sup_E A leqslant sup_F A. If sup_E A exists and belongs to F, then sup_F A exi… 03QJ
Definition 7 A preordered set E is said to be right directed (resp. left directed) if every subset of two elements of E is bounded above (resp. bounded below). 03QK
Proposition 10 In a right directed ordered set E, a maximal element a is the greatest element of E. ↩ 3 03QL
Definition 8 An ordered set E is said to be a lattice if every subset consisting of two elements of E has a least upper bound and a greatest lower bound in E. 03QM
Example 1 \ The set of integers geqslant 1, ordered by the relation “m divides n” between m and n, is a lattice; the least upper bound of m,n is the l.c.m. of m and n, and the greatest lower… 03SV
Example 2 The set of subgroups of a group G, ordered by inclusion, is a lattice. 03TT
Example 3 The set of topologies on a set A, ordered by the relation “T is coarser than T'” between T and T', is a lattice. (General Topology, Chapter I, § 2). 03TU
Example 4 The set 𝔉(I,R) of all real-valued functions defined on an interval I of R is a lattice with respect to the order relation fleqslant g (no. 4), and as such is isomorphic to the prod… 03TV
Remark A lattice is obviously both left and right directed. But an ordered set which is both left and right directed is not necessarily a lattice. \ An example of the latter is the set of… 03JQ
Definition 9 Two elements x, y of a preordered set E are said to be comparable if the relation “xleqslant y or yleqslant x” is true. A set E is said to be totally ordered if it is ordered and i… 03JR
Example 1 Every subset of a totally ordered set is totally ordered by the induced ordering. 03SW
Example 2 Let E be an arbitrary ordered set. The empty subset of E is totally ordered, and so is every subset of E consisting of a single element. 03TW
Example 3 \ The set R of real numbers is totally ordered. \ 03TX
Example 4 If A is a set which has at least two distinct elements, the set 𝔓(A) (ordered by inclusion) is not totally ordered, for if x≠ y, the subsets x and y are not comparable. 03TY
Proposition 11 Every strictly monotone mapping f of a totally ordered set E into an ordered set F is injective. If f is strictly increasing, f is an isomorphism of E onto f(E). ↩ 5 03JS
Proposition 12 Let E be a totally ordered set and let X be a subset of E. For an element b of E to be the least upper bound of X in E, it is necessary and sufficient that (1) b is an upper bound… 03JT
Proposition 13 In a lattice, the intersection of two intervals is an interval. Consider for example the intersection of two closed intervals [a, b] and [c, d], and let α = sup (a, c), β = inf (b… 03JU

§ 2. Well-ordered sets

Definition 1 A set E is said to be well-ordered if it is ordered and if each non-empty subset of E has a least element. 03JY
Example 1 Let E = α, β be a set whose elements are distinct. It is easily verified that the subset (α, α), (β, β), (α, β) of E × E is the graph of a well-ordering on E. 03SX
Example 2 Every subset (in particular, the empty subset) of a well-ordered set is well-ordered by the induced ordering. 03SY
Example 3 \ The existence of totally ordered sets which are not well-ordered is equivalent to the axiom of infinity (§ 4, no. 4, Corollary 1 to Proposition 3, and Exercise 3). 03SZ
Example 4 If Γ is a well-ordering on E, the ordering opposite to Γ is a well-ordering on E only if E is finite (§ 4, Exercise 3). \ 03T0
Example 5 Let E be a well-ordered set. The set E₁ obtained by adjoining to E a greatest element b (§ 1, no. 7) is well-ordered, for if H is any non-empty subset of E₁ other than b, the least… 03T1
Remark \ As a consequence of the axiom of infinity (§ 6, no. 1), there exist well-ordered sets which have no greatest element, for example the set N of natural integers. \ 03JZ
Definition 2 In an ordered set E, a subset of E such that the relations x ∈ S, y ∈ E, and y leqslant x imply y ∈ S is called a segment of E. ↩ 1 03QN
Proposition 1 In a well-ordered set E, every segment of E other than E itself is an interval ]←, a[, where a ∈ E. ↩ 3 03QO
Proposition 2 The set E\ of segments of a well-ordered set E is well-ordered by inclusion. The mapping x → Sₓ is an isomorphism of the well-ordered set E onto the set of segments of E other than… ↩ 3 03QP
Proposition 3 Let (X_ι)_ι ∈ I be a family of well-ordered sets such that for each pair of indices (ι, varkappa) one of the sets X_ι, X_varkappa is a segment of the other. Then there exists a uni… ↩ 2 03QQ
Lemma 1 Let (X_α)_α ∈ A be a family of ordered sets, directed with respect to the relation ⊂ (in other words, such that for each pair of indices α, β there exists an index γ such that X_α… 03QR
Lemma 2 Let E be a well-ordered set and let 𝔖 be a set of segments of E with the following properties : (1) every union of segments belonging to 𝔖 belongs to 𝔖; (2) if Sₓ∈𝔖, then Sₓ∪x∈𝔖. T… 03K0
Lemma 3 Let E be a set, let 𝔖 be a subset of 𝔓(E), and let p be a mapping of 𝔖 into E such that p(X) ∉ X for all X ∈ 𝔖. Then there exists a subset M of E and a well-ordering Γ on M such th… ↩ 3 03K1
Theorem 1 (Zermelo) Every set E can be well-ordered. ↩ 7 03QS
Definition 3 An ordered set E is said to be inductive if every totally ordered subset of E has an upper bound in E. ↩ 3 03K2
Example 1 Let 𝔉 be a set of subsets of a set A, ordered by inclusion, and such that for every totally ordered subset 𝔊 of 𝔉 the union of the sets of 𝔊 belongs to 𝔉. Then 𝔉 is inductive with… 03T2
Example 2 An important example of a set of subsets which is inductive with respect to the relation ⊂ is the set 𝔉 of graphs of mappings of subsets of a set A into a set B. For 𝔉 is a subset… ↩ 2 03T3
Example 3 \ It follows from the axiom of infinity (§ 6, no. 1) that the well-ordered set of natural integers is not inductive with respect to the relation leqslant. \ 03T4
Theorem 2 ("Zorn's lemma") — Every inductive ordered set has a maximal element. ↩ 11 03QT
Proposition 4 Let E be an ordered set in which every well-ordered subset is bounded above; then E has a maximal element. 03K3
Corollary 1 Let E be an inductive ordered set and let a be an element of E. Then there exists a maximal element m of E such that m≥ a. ↩ 2 03K4
Corollary 2 Let 𝔉 be a set of subsets of a set E such that, for every subset 𝔊 of 𝔉 which is totally ordered by inclusion, the union (resp. intersection) of the sets of 𝔊 belongs to 𝔉; then 𝔉… ↩ 1 03K5
Theorem 3 Let E and F be two well-ordered sets. Then at least one of the following two statements is true : ↩ 9 03K6
Lemma 4 Let E, F be two well-ordered sets and let f, g be two increasing mappings of E into F such that f(E) is a segment of F and g is strictly increasing; then f(x)≤ g(x) for all x∈ E. ↩ 1 03K7
Corollary 1 The only isomorphism of a well-ordered set E onto a segment of E is the identity mapping of E onto itself. ↩ 1 03K8
Corollary 2 Let E, F be two well-ordered sets. If there exists an isomorphism f of E onto a segment T of F and an isomorphism g of F onto a segment S of E, then we must have S=E, T=F, and g,f… 03K9
Corollary 3 Every subset A of a well-ordered set E is isomorphic to a segment of E. ↩ 3 03KA

§ 3. Equipotent sets. Cardinals

Definition 1 A set X is said to be equipotent to a set Y if there exists a bijection of X onto Y. The relation “X is equipotent to Y” is denoted by Eq(X,Y). 03QU
Definition 2 The set τ_Z(Eq(X, Z)) is called the cardinal of X (or the power of X) and is written Card(X). 03QV
Proposition 1 Two sets X and Y are equipotent if and only if their cardinals are equal. 03QW
Example 1 Card(∅) is denoted by 0. Since the only set equipotent to ∅ is ∅ (Chapter II, § 3, nos. 1 and 4), we have 0 = Card(∅) = ∅. 03T5
Example 2 All sets consisting of a single element are equipotent, since (a, b) is the graph of a bijection of a onto b; in particular, they are all equipotent to ∅. The cardinal Card(∅) = τ_… 03T6
Example 3 Card(∅, ∅) is denoted by 2; this is the cardinal of every set consisting of two distinct elements. 03T7
Example 4 A Hilbert space of countable type is equipotent to the set of real numbers. \ 03T8
Theorem 1 The relation Rξ,η: “ξ and η are cardinals and ξ is equipotent to a subset of η” is a well-ordering relation (§ 2, no. 1). ↩ 1 03QX
Corollary 1 Given any two sets, one of them is equipotent to a subset of the other. 03QY
Corollary 2 Two sets each of which is equipotent to a subset of the other are equipotent. 03QZ
Remark Given any set A, there exists a set whose elements are the cardinals Card(X) for all the subsets X of A, namely, the set of objects of the form Card(X) for X∈𝔓(A) (Chapter II, § 1… 03R0
Proposition 2 For every family (𝔞_ι)_ι ∈ I of cardinals, there exists a unique cardinal 𝔟 such that 𝔞_ι leqslant 𝔟 for all ι ∈ I and such that every cardinal 𝔠 for which 𝔞_ι leqslant 𝔠 for all ι… 03KL
Proposition 3 Let X and Y be sets. If there exists a surjection f of X onto Y, then Card (Y) leqslant Card (X). ↩ 3 03KM
Definition 3 Let (𝔞_ι)_ι ∈ I be a family of cardinals. The cardinal of the product (resp. sum) of the sets 𝔞_ι is called the cardinal product (resp. cardinal sum) of the cardinals 𝔞_ι and is de… 03KN
Proposition 4 Let (E_ι)_ι ∈ I be a family of sets, P their product, and S their sum, and let 𝔞_ι be the cardinal of E_ι. Then the cardinal of P (resp. S) is the cardinal product (resp. cardinal… 03KO
Corollary If (E_ι)_ι ∈ I is any family of sets, the cardinal of the union ⋃_ι ∈ I E_ι is at most equal to the sum ∑_ι ∈ I Card (E_ι). ↩ 1 03KP
Proposition 5 (a) Let (𝔞_ι)_ι ∈ I be a family of cardinals, and let f be a bijection of a set K onto the index set I. Then ↩ 3 03R1
Corollary Let 𝔞, 𝔟, 𝔠 be cardinals. Then ↩ 4 03R2
Proposition 6 Let (𝔞_ι)_ι ∈ I be a family of cardinals, and let J (resp. K) be a subset of I such that 𝔞_ι = 0 for all ι ∉ J (resp. 𝔞_ι = 1 for all ι ∉ K). Then ↩ 2 03R3
Corollary 1 For every cardinal 𝔞 we have 𝔞 + 0 = 𝔞 . 1 = 𝔞. ↩ 1 03R4
Corollary 2 Let 𝔞 and 𝔟 be cardinals and let I be a set equipotent to 𝔟. For each ι ∈ I let 𝔞_ι = 𝔞, 𝔠_ι = 1. Then ↩ 2 03R5
Proposition 7 Let (𝔞_ι)_ι ∈ I be a family of cardinals. Then P_ι ∈ I 𝔞_ι ≠ 0 if and only if 𝔞_ι ≠ 0 for all ι ∈ I. ↩ 1 03R6
Proposition 8 If 𝔞 and 𝔟 are cardinals such that 𝔞 + 1 = 𝔟 + 1, then 𝔞 = 𝔟. ↩ 3 03R7
Definition 4 Let 𝔞 and 𝔟 be cardinals. The cardinal of the set of mappings of 𝔟 into 𝔞 is denoted by 𝔞^𝔟, by abuse of notation. 03KQ
Proposition 9 Let X and Y be two sets, 𝔞 and 𝔟 their respective cardinals. Then the set X^Y has cardinal 𝔞^𝔟. 03KR
Proposition 10 Let 𝔞 and 𝔟 be cardinals and let I be a set such that Card\ (I) = 𝔟. If 𝔞_ι = 𝔞 for all ι ∈ I, we have 𝔞^𝔟 = P_ι ∈ I 𝔞_ι. ↩ 4 03KS
Corollary 1 Let 𝔞 be a cardinal and let (𝔟_ι)_ι ∈ I be a family of cardinals. Then ↩ 1 03KT
Corollary 2 Let (𝔞_ι)_ι ∈ I be a family of cardinals and let 𝔟 be a cardinal. Then ( mathopP_ι ∈ I 𝔞_ι )^𝔟 = mathopP_ι ∈ I 𝔞_ι^𝔟. 03KU
Corollary 3 Let 𝔞, 𝔟, 𝔠 be cardinals. Then 𝔞^𝔟𝔠 = (𝔞^𝔟)^𝔠. 03KV
Proposition 11 Let 𝔞 be a cardinal. Then 𝔞⁰ = 1, 𝔞¹ = 𝔞, 1^𝔞 = 1; and 0^𝔞 = 0 if 𝔞 ≠ 0. 03KW
Proposition 12 Let X be a set and let 𝔞 be its cardinal. Then the cardinal of the set 𝔓(X) of all subsets of X is 2^𝔞. ↩ 4 03KX
Proposition 13 Let 𝔞 and 𝔟 be cardinals. Then 𝔞 geqslant 𝔟 if and only if there exists a cardinal 𝔠 such that 𝔞 = 𝔟 + 𝔠. ↩ 4 03KY
Proposition 14 Let (𝔞_ι)_ι ∈ I and (𝔟_ι)_ι ∈ I be two families of cardinals, both indexed by the same set I, and such that 𝔞_ι geqslant 𝔟_ι for all ι ∈ I. Then ↩ 5 03KZ
Corollary 1 Let (𝔞_ι)_ι ∈ I be a family of cardinals. For each subset J of I we have ∑_ι ∈ J 𝔞_ι leqslant ∑_ι ∈ I 𝔞_ι. If also 𝔞_ι ≠ 0 for all ι ∈ I - J, then P_ι ∈ J 𝔞_ι leqslant P_ι ∈ I 𝔞_ι. ↩ 1 03L0
Corollary 2 If 𝔞, 𝔞', 𝔟, 𝔟' are cardinals such that 𝔞 leqslant 𝔞', 𝔟 leqslant 𝔟', and 𝔞' > 0, then 𝔞^𝔟 leqslant mathfraka'^𝔟'. 03L1
Theorem 2 (Cantor) — For each cardinal 𝔞, we have 2^𝔞 > 𝔞. ↩ 4 03R8
Corollary There does not exists a set that has every cardinal as an element. 03L2

§ 4. Natural integers. Finite sets

Definition 1 A cardinal α is said to be finite if α ≠ α + 1. A finite cardinal is also called a natural integer (or simply an integer if there is no risk of confusion [^1]). A set E is said to… ↩ 1 03R9
Proposition 1 A cardinal α is finite if and only if α + 1 is finite. ↩ 1 03RA
Proposition 2 Let n be an integer. Then every cardinal α such that α ≤ n is an integer. If n ≠ 0, there exists a unique integer m such that n = m + 1, and the relation α < n is equivalent to α ≤… ↩ 11 03RB
Corollary 1 Every subset of a finite set is finite. 03RC
Corollary 2 If X is a subset of a finite set E and X ≠ E, then ↩ 2 03RD
Corollary 3 If f is a mapping of a finite set E into a set F, then f(E) is a finite subset of F. ↩ 2 03RE
Corollary 4 Let E and F be two finite sets with the same number of elements, and let f be a mapping of E into F. Then the following statements are equivalent : ↩ 2 03RF
Remark There are various criteria which are frequently used under the name of "principle of induction". They can all be easily deduced from C61, and we indicate here the most important of… 077T
Proposition 3 Let E be a right directed preordered set (resp. a lattice, resp. a totally ordered set). Then every non-empty finite subset of E is bounded above (resp. has a least upper bound and… ↩ 3 03L9
Corollary 1 Every totally ordered finite set is well-ordered and has a greatest element. ↩ 5 03LA
Corollary 2 Every finite ordered set has a maximal element. ↩ 1 03LB
Definition 2 Let E be a set. A set 𝔖 of subsets of E is said to be of finite character if the relation X ∈ 𝔖 is equivalent to the relation "every finite subset of X belongs to 𝔖". 03LC
Example 1 The set of totally ordered subsets of an ordered set E is of finite character. Indeed, a subset X of E is totally ordered if and only if every subset of X consisting of two element… 03T9
Example 2 \ The set of all free subsets of a module is of finite character. The same is true of the set of all algebraically free subsets of an extension of a field. 03TA
Example 3 The set of submodules of a module E is not of finite character, because a finite subset of a submodule of E is not necessarily a submodule of E. \ 03TB
Theorem 1 Every set 𝔖 of subsets of a set E which is of finite character has a maximal element (when ordered by inclusion). 03LD

§ 5. Properties of integers

Proposition 1 Let (aᵢ)_i ∈ I be a finite family of integers. Then the cardinals ∑_i ∈ I aᵢ and ∏_i ∈ I aᵢ are integers. ↩ 1 03LP
Corollary 1 The union E of a finite family (Xᵢ)_i ∈ I of finite sets is a finite set. ↩ 2 03LQ
Corollary 2 The product of a finite family of finite sets is a finite set. 03LR
Corollary 3 If a and b are integers, aᵇ is an integer. 03LS
Corollary 4 The set of subsets of a finite set E is finite. ↩ 1 03LT
Proposition 2 Let a and b be two integers. Then a < b if and only if there exists an integer c > 0 such that b = a + c. ↩ 4 03LU
Proposition 3 Let (aᵢ)_i ∈ I and (b)_i ∈ I be two finite families of integers such that aᵢ leqslant bᵢ for each i ∈ I and aᵢ < bᵢ for at least one index i. Then ↩ 4 03LV
Corollary 1 Let a, a', and b be integers such that a < a' and b > 0. Then aᵇ < a'ᵇ. 03LW
Corollary 2 Let a, b, and b' be integers such that a > 1 and b < b'; then aᵇ < a^b'. 03LX
Corollary 3 Let a, b, b' be integers (resp. integers such that a > 0). Then a + b = a + b' (resp. ab = ab') if and only if b = b'. ↩ 2 03LY
Corollary 4 If a and b are integers such that a leqslant b, then there exists a unique integer c such that b = a + c. ↩ 1 03LZ
Proposition 4 Let a and b be integers. Then the mapping x → a + x is a strictly inrceasing isomorphism of the interval [0, b] onto the interval [a, a + b], and y → y - a is the inverse isomorphi… ↩ 1 03M0
Proposition 5 If a and b are integers such that a leqslant b, then the interval [a, b] is a finite set whose number of elements is b - a + 1. ↩ 3 03M1
Proposition 6 For every finite set E which is totally ordered and has n elements (n geqslant 1), there exists a unique isomorphism of E onto the interval [1, n]. ↩ 3 03M2
Proposition 7 For each pair of subsets A, B of a non-empty set E, we have 03M3
Theorem 1 Let a and b be integers such that b > 0. Then there exist integers q and r such that a = bq + r and r < b, and the integers q and r are uniquely determined by these conditions. ↩ 2 03M4
Definition 1 With the notation of Theorem 1, r is called the remainder of the division of a by b. If r = 0, we say that a is a multiple of b, or that a is divisible by b, or that b is a divisor… 03M5
Proposition 8 Let b be an integer >1. For each integer k>0 let Eₖ be the lexicographic product (§ 2, no. 6) of the family (Jₕ)_0≤ h≤ k-1 of intervals all identical with [0,b-1]. For each r=(r₀,r… ↩ 1 03M6
Proposition 9 Let E and F be two sets, 𝔞 and 𝔟 their cardinals, f a surjection of E onto F such that the sets overset-1f(y), where y ∈ F, all have the same cardinal 𝔠. Then 𝔞 = 𝔟𝔠. ↩ 3 03M7
Definition 2 Let n be an integer. The product ∏_i < n (i + 1) is denoted by n! (read "factorial n"). 03M8
Proposition 10 Let m and n be integers such that m leqslant n. Then n!/(n - m)! is the number of injective mappings of a set A with m elements into a set B with n elements. 03M9
Corollary The number of permutations of a finite set with n elements is equal to n!. ↩ 1 03MA
Proposition 11 Let E be a finite set with n elements, and let (pᵢ)_1 leqslant i leqslant h be a finite sequence of integers such that ∑ᵢ₌₁ʰ pᵢ = n. Then the number of coverings (Xᵢ)_1 leqslant i… ↩ 1 03MB
Corollary 1 Let A be a set with n elements and let p be an integer leqslant n. Then the number of subsets of A which have p elements is dfracn!p!(n-p)!. ↩ 2 03MC
Corollary 2 Let E and F be totally ordered finite sets with p and n elements, respectively. Then the number of strictly increasing mappings of E into F is binomnp. 03RG
Proposition 12 For each integer n, we have 03RH
Proposition 13 If n and p are integers, then ↩ 2 03RI
Proposition 14 Let n be an integer > 0. Then the number aₙ (resp. bₙ) of ordered pairs (i, j) of integers such that 1 leqslant i leqslant j leqslant n (resp. 1 leqslant i < j leqslant n) is 1/2n(… 03RJ
Corollary For each integer n > 0, we have ↩ 1 03RK
Proposition 15 Let n and h be integers and let E be a set with h elements. Then the number of mappings u of E into [0, n] such that ∑_x ∈ E u(x) leqslant n (resp. ∑_x ∈ E u(x) = n, for h > 0) is ↩ 1 03RL

§ 6. Infinite sets

Definition 1 A set is said to be infinite if it is not finite. 03MV
Theorem 1 The relation "x is an integer" is collectivizing. ↩ 1 03MW
Definition 2 A sequence (resp. a sequence of elements of a set E) is a family (resp. a family of elements of E) whose index set is a subset of N. The sequence is said to be infinite if its inde… 03MX
Example 1 Suppose that a is an element of a set E and that Su is the term g(u), where g is a mapping of E into itself [^3]. Then it is immediately seen by induction on n that for all n ∈ N w… 03TC
Example 2 Let X be a set and let E be the set of mappings of X into itself. Let e denote the identity mapping of X into itself, and let f be any element of E. Take Su to be the term f ∘ u [^… 03TD
Example 3 If we take Su to be the term 𝔓(u), and a to be a set E, it follows likewise that there exists a mapping, denoted by n → 𝔓ⁿ(E), of N into a set V(E) such that 𝔓⁰(E) = E, 𝔓¹(E) = 𝔓(E… 03TE
Remark Let E be a set, let A be a subset of E, let g be a mapping of A into E, and let a be an element of A. Take Su to be the term g(u). Criterion C63 is applicable and proves the existe… 03MY
Theorem 2 For every infinite cardinal 𝔞 we have 𝔞² = 𝔞. ↩ 6 03MZ
Lemma 1 Every infinite set E contains a set equipotent to N. ↩ 2 03N0
Lemma 2 The set N × N is equipotent to N. 03N1
Corollary 1 If 𝔞 is an infinite cardinal, then 𝔞ⁿ = 𝔞 for every integer n geqslant 1. ↩ 1 03N2
Corollary 2 The product of a finite family (𝔞ᵢ)_i ∈ I of non-zero cardinals, of which the greatest is an infinite cardinal 𝔞, is equal to 𝔞. 03N3
Corollary 3 Let 𝔞 be an infinite cardinal and let (𝔞_ι)_ι ∈ I be a family of cardinals leqslant 𝔞 whose index set I has a cardinal leqslant 𝔞. Then ∑limits_ι ∈ I 𝔞_ι leqslant 𝔞; and if 𝔞_ι = 𝔞… ↩ 4 03N4
Corollary 4 If 𝔞 and 𝔟 are two non-zero cardinals, one of which is infinite, we have 𝔞𝔟 = 𝔞 + 𝔟 = sup (𝔞, 𝔟). ↩ 3 03N5
Definition 3 A set is said to be countable if it is equipotent to a subset of the set N of integers. 03N6
Proposition 1 Every subset of a countable set is countable. The product of a finite family of countable sets is countable. The union of a sequence of countable sets is countable. 03N7
Proposition 2 Every countable infinite set E is equipotent to N. 03N8
Proposition 3 Every infinite set has a partition (X_ι)_ι ∈ I formed of countable infinite sets X_ι, the index set I being equipotent to E. ↩ 2 03N9
Proposition 4 Let f be a mapping of a set E onto an infinite set F such that, for each y ∈ F, overset-1f(y) is countable. Then F is equipotent to E. 03NA
Proposition 5 The set 𝔉(E) of finite subsets of an infinite set E is equipotent to E. 03NB
Definition 4 A set is said to have the power of the continuum if it is equipotent to the set of all subsets of N. 03NC
Definition 5 A sequence (xₙ)_n ∈ N of elements of a set E is said to be stationary if there exists an integer m such that xₙ = xₘ for all integers n geqslant m. 03ND
Proposition 6 Let E be an ordered set. Then the following statements are equivalent : ↩ 4 03NE
Corollary 1 A totally ordered set E is well-ordered if and only if every decreasing sequence of elements of E is stationary. 03NF
Corollary 2 Every increasing sequence of elements of a finite ordered set is stationary. 03NG
Proposition 7 ("Principle of Noetherian induction") — Let E be a Noetherian set, and let F be a subset of E with the following property : if a ∈ E is such that the relation x > a implies x ∈ F, then a ∈ F. Under these conditions, F… 03RM

§ 7. Inverse limits and direct limits

Example 1 Suppose that the order relation on I is the relation of equality. Then the only pairs (α,β) such that α≤β are the pairs (α,α) where α∈ I; and since f_αα is the identity mapping, th… ↩ 1 03TF
Example 2 Suppose that I is right directed, that E_α is the same set F for all α∈ I, and that f_αβ is the identity mapping of F onto itself whenever α≤β. Then E=undersetlongleftarrowlim E_α… ↩ 1 03TG
Proposition 1 Let I be an ordered set, let (E_α, f_αβ) be an inverse system of sets relative to I, let E = varprojlim E_α be its inverse limit, and for each α ∈ I let ↩ 4 03OC
Corollary 1 Let (E_α, f_αβ) and (F_α, g_αβ) be two inverse systems of sets relative to the same index set I; let E = varprojlim E_α, F = varprojlim F_α, and let f_α (resp. g_α) be the canonica… 03RN
Corollary 2 Let (E_α,f_αβ), (F_α,g_αβ), (G_α,h_αβ) be three inverse systems of sets relative to the same index set I; let E=underset←lim E_α, F=underset←lim F_α, G=underset←lim G_α, and let f_… ↩ 1 03RO
Proposition 2 Let (E_α,f_αβ) and (E'_α,f'_αβ) be two inverse systems of sets relative to I, and let u_α be a mapping of E_α into E'_α for each α∈ I, such that the u_α form an inverse system of m… ↩ 2 03RP
Corollary If u_α is injective (resp. bijective) for each α ∈ I, then u is injective (resp. bijective). 03OD
Proposition 3 Let I be a preordered set, let (E_α, f_αβ) be an inverse system of sets relative to I, and let E = varprojlim E_α. Let J be a cofinal subset of I such that J is right directed, and… 03OE
Remark 1 For each α ∈ I put E'_α = f_α(E). Then the sets E'_α form an inverse system of subsets of the E_α by reason of (2), and it is immediately clear that varprojlim E'_α = E = varprojli… 03TH
Remark 2 Let I be a (right) directed ordered set, let (E_α, f_αβ) be an inverse system of sets relative to I, and for each α ∈ I let u_α : F → E_α be a mapping such that the family (u_α) sa… 03TI
Remark 3 Let I be an ordered set and let (E_α, f_αβ) be an inverse system of sets relative to I. For each finite subset J of I, let F_J be the inverse limit of the (finite) inverse system o… 03TJ
Proposition 4 If (E^λ_α, f^λμ_αβ) is an inverse system of sets relative to a product I × L of preordered sets, then (up to a canonical bijection) we have ↩ 2 03OF
Corollary 1 Let (E'^λ_α, f'^μλ_αβ) be another inverse system of sets relative to I × L, and for each (α, λ) ∈ I × L let u^λ_α be a mapping of E^λ_α into E'^λ_α such that the u^λ_α form an inve… 03OG
Corollary 2 Let (E^λ_α, f^λ_αβ)_λ ∈ L be a family of inverse systems of sets relative to I. If ∏_λ ∈ L f^λ_αβ denotes the extension to products (Chapter II, § 5, no. 7, Definition 2) of the fa… ↩ 1 03OH
Proposition 5 Let (E_α, f_αβ) be an inverse system of sets relative to a directed set I which has a countable cofinal subset, and suppose furthermore that the f_αβ are surjective. Then, if E = v… 03OI
Theorem 1 Suppose that I is directed, that the sets 𝔖_α satisfy conditions (i) and (ii), and that the inverse system (E_α, f_αβ) has the following properties: ↩ 2 03RQ
Remark Suppose that condition (iii) in Theorem 1 is replaced by the following weaker condition : 03OJ
Example 1 If the E_α are finite sets, Theorem 1 can be applied by taking 𝔖_α to be the set of all subsets of E_α. \ This example is generalized in General Topology to the situation in which… 03TK
Example 2 \ Let A be a ring with an identity element, and for each α ∈ I let T_α be an Artinian left A-module. Let E_α be a homogeneous space for T_α on which T_α operates faithfully (so tha… 03TL
Example 1 Let A, B be two sets, and let (V_α)_α ∈ I be a family of subsets of A whose index set I is directed, and such that the relation α leqslant β implies V_β ⊂ V_α. Let E_α denote the s… 03TM
Example 2 Suppose that, for each α ∈ I, E_α is the same set F and that whenever α leqslant β, f_βα is the identity mapping of F onto itself. Then there exists a canonical bijection of varinj… ↩ 1 03TN
Lemma 1 Let (E_α, f_βα) be a direct system of sets, E = varinjlim E_α its direct limit, and for each α ∈ I let f_α colon E_α → E the canonical mapping. ↩ 11 03OK
Proposition 6 Let I be a directed set, let (E_α, f_βα) be a direct system of sets relative to I, let E = varinjlim E_α be the direct limit, and for each α ∈ I let ↩ 8 03RR
Remark Suppose that each of the mappings f_βα is injective. Then each of the f_α is injective, by the definition of the relation R. In this case we generally identify E_α and f_α(E_α) and… ↩ 1 03OL
Corollary 1 Let (E_α, f_βα) and (F_α, g_βα) be two direct systems of sets relative to the same index set I; let E = varinjlim E_α, F = varinjlim F_α, and for each α ∈ I let f_α (resp. g_α) be… 03RS
Corollary 2 Let (E_α, f_βα), (F_α, g_βα), (G_α, h_βα) be three direct systems of sets relative to I. Let E = varinjlim E_α, F = varinjlim F_α, G = varinjlim G_α, and let f_α (resp. g_α, h_α) b… ↩ 1 03RT
Proposition 7 Let (E_α, f_βα) and (E'_α, f'_βα) be two direct systems of sets relative to I, and for each α ∈ I let u_α be a mapping of E_α into E'_α such that the u_α form a direct system of ma… ↩ 1 03RU
Corollary Let (E_α, f_βα) and (E'_α, f'_βα) be two direct systems of sets, let (u_α) be a direct system of mappings u_α : E_α → E'_α, and let u = varinjlim u_α. ↩ 1 03ON
Remark Suppose that, for each α ∈ I, u_α : E_α → E' is a mapping such that the family (u_α) satisfies (23). Consider the direct system (E_α, i_βα) relative to I, where E'_α = E' for all α… 03OO
Proposition 8 Let I be a directed set, let (E_α, f_βα) be a direct system of sets relative to I, and let E = varinjlim E_α be its direct limit. Let J be a cofinal subset of I and let E′ be the d… 03OP
Proposition 9 If (E_α^λ, f_βα^μλ) is a direct system of sets relative to a product I × L of two directed sets, then (up to a canonical bijection) we have 03RV
Corollary Let (E'^λ_α, f'^μλ_βα) be another direct system of sets relative to I × L, and for each (α, λ) ∈ I × L let u_α^λ be a mapping of E_α^λ into E'^λ_α, such that the u_α^λ form a direc… 03OQ
Proposition 10 Let (E_α, f_βα) and (E'_α, f'_βα) be two direct systems of sets, both relative to the same directed set I. Let E = varinjlim E_α, E' = varinjlim E'_α, and let f_α : E_α → E, f'_α… ↩ 1 03RW
Corollary Let (F_α, g_βα) and (F'_α, g'_βα) be two direct systems of sets relative to I, and for each α ∈ I let u_α : E_α → F_α, u'_α : E'_α → F'_α be mappings such that (u_α) and (u'_α) are… 03RX

IV. Structures

§ 1. Structures and isomorphisms

Example Given two sets E, F, the set 𝔓(𝔓(E)) × 𝔓(F) is an echelon on E, F, with scheme 03V4
Example 1 Take T to be the theory of sets, and consider the species of structures which has no auxiliary base set, one principal base set A, the typical characterization s ∈ 𝔓(A × A), and th… ↩ 2 03V5
Example 2 Take T to be the theory of sets, and consider the species of structures which has no auxiliary base set, one principal base set A, the typical characterization F ∈ 𝔓((A × A) × A)… ↩ 3 03V6
Example 3 As before, let T be the theory of sets, and consider the species of structures which has no auxiliary base set, one principal base set A, the typical characterization V ∈ 𝔓(𝔓(A))… ↩ 5 03V7
Example 4 \ Take T to be the theory of the species of division ring structures, which has (among other things) a constant K as unique (principal) base set. The species of structure of a left… ↩ 1 03V8
Example 5 Again let T be the theory of sets; in this theory, the field C of complex numbers is a term which contains no letters. The species of structure of a complex analytic manifold of di… 03V9
Remark 1 In applications it is often the case (as in Example 4 above) that the echelon S(E₁, …, Eₙ, A₁, …, Aₘ) is a product of echelons 03VA
Remark 2 Names are given to the species of structures most frequently used in mathematics, and to sets endowed with structures of these species. Thus an ordered set (Chapter III, § 1) is a… 03VB
Remark 3 By abuse of language, in the theory of sets T, the giving of n distinct letters x₁, …, xₙ (with no typical characterization and no axiom) is considered as a species of structure Σ₀… ↩ 1 03VC
Remark By abuse of language, if fᵢ is any bijection of Eᵢ onto E'ᵢ (1 leqslant i leqslant n), (f₁, …, fₙ) is said to be an isomorphism of E₁, …, Eₙ onto E'₁, …, E'ₙ with respect to the sp… 03VD
Example 1 \ The species of topological group structures has a single principal base set A, no auxiliary base set, and the corresponding generic structure is a pair (s₁,s₂) (s₁ being the grap… 03VE
Example 2 The species of vector space structures over C (resp. R) has a principal base set E, an auxiliary base set equal to C (resp. R), and typical characterization 03VF
Example 3 Suppose that Θ has the same (principal and auxiliary) base sets as Σ, and the same typical characterization. If, moreover, the axiom of Σ implies (in T) the axiom of Θ, it is clear… 03VG
Example 4 \ When each of Σ and Θ is the species of group structures (resp. ring structures), there is defined in algebra a procedure of deduction which associates with each group structure (… 077U
Remark When P is a “q-tuple” (P₁,…,P_q), it is also said that the terms P₁,…,P_q constitute a procedure of deduction of a structure of species Θ from a structure of species Σ. 03VH
Example 1 \ Let Σ be the species of commutative group structures; Σ has a single (principal) base set A, and its generic structure consists of a single letter F; the typical characterization… 03VI
Example 2 Let Σ be the species of topological structures (no. 4, Example 3), let A be the (principal) base set, and let V be the generic structure of Σ. Consider the relation 03VJ

§ 2. Morphisms and derived structures

Example 1 Take Σ to be the species of order structures and let σx,y,s,t denote the set of all mappings f of x into y such that the relation (u,v)∈ s implies (f(u),f(v))∈ t. With the notation… 03VL
Example 2 Take Σ to be a species of algebraic structures which has a single (internal) law of composition, everywhere defined (§1, no. 4, Example 2). Let A, A' be two sets endowed with struc… ↩ 1 03VM
Example 3 Take Σ to be the species of topological strcutures (§1, no. 4, Example 3). Let A, A' be two sets endowed with topologies V, V', respectively. Consider the mappings f of A into A' s… ↩ 2 03VN
Remark For given species of structures Σ we may have occasion to define various terms σ x,\ y,\ s,\ t which satisfy the conditions (MO_I), (MO_II), and (MO_III). For example, if Σ is the… 03VO
Remark When a species of structures Σ has several principal base sets x₁, …, xₙ, and auxiliary base sets A₁, …, Aₘ, a σ-morphism is a system (f₁, …, fₙ), where fᵢ is a mapping of xᵢ into… 03VP
Example 1 An order structure with graph s on a set A is finer than an order structure with graph s' if and only if s ⊂ s'. In other words, the relation x leqslant y with respect to s implies… 03VQ
Example 2 Consider two algebraic structures F, F' of the same species Σ on a set A, where F and F' are the graphs of the (everywhere defined) laws of composition of these two structures. Fro… ↩ 1 03VR
Example 3 Let V, V' be two topologies on the same set A. To say that V is finer than V' means, by virtue of the definition of morphisms in this case (no. 1, Example 3), that V' ⊂ V; in other… 03VS
Remark We have just met an example (Example 2) in which two comparable structures of the same species Σ are necessarily identical. There are many other such examples : linear order struct… 03VT
Remark Let (S_λ)_λ ∈ L be a family of structures of species Σ on the same set A; let A_λ denote the set A endowed with the structure S_λ, and let I_λ denote the identity mapping of A into… 03VU
Remark For most of the usual structures, the condition given in CST16 is not only sufficient but also necessary for f to be a morphism (cf. Exercise 7). In particular, this is so in the f… 03VV
Remark Let A be a set endowed with a structure S of species Σ, and let R be an equivalence relation on A such that there exists on E=A/R a quotient structure S' of S by R. Let φ be the ca… 03VW