Basic mathematics series: Sets and numbers

This paper aims to sort out some basic concepts and theorems in set theory.

This article lists only extremely simple proofs, omitting the complex ones.

1. Fundamentals of set theory

First of all, we introduce Cartesian product (Cartesian product, direct product) A×BA\times BA×B, which is A pair of ordered numbers formed by taking one element from AAA and one element from BBB. If the set is NNN, their Cartesian product is an NNn-tuples:

If A Relation is any subset of A×AA\times AA×A, it is called A Relation RRR on set AAA. If (x,y)∈R(x,y)\in R(x,y)∈R, it can be written as xRyxRyxRy. The possible properties of RRR are:

• Reflexive: xRxxRxxRx;
• Symmetric: If xRyxRyxRy, there must be yRxyRxyRx.
• Antisymmetric: If xRyxRyxRy and yRxyRxyRx are symmetric, x=yx=yx=y;
• Transitive: if xRyxRyxRy and yRzyRzyRz, xRzxRzxRz must be used.

Equivalence relation is the relation of reflexivity, symmetry and transfer.

Equivalence relation RRR on AAA, and the element XXX in AAA. Is A collection of the Ex = {y ∈ A: xRy} E_x = \ {y \ in A: xRy \} the Ex = {y ∈ a. xRy}. If ExE_xEx and EyE_yEy are the equivalent classes of XXX and YYy, then there must be Ex∩Ey=∅E_x\cap E_y=\emptyEx∩Ey=∅ or Ex=EyE_x=E_yEx=Ey.

The relation of reflexivity, antisymmetry, and transmission is called partial ordering, which can be expressed with the symbol ≥\geq≥ or ≤\leq≤. For any partial ordering, if the (x,x)(x,x)(x,x) (x,x) element is removed, the strict ordering becomes strict, which is indicated by the symbol >\gt> or <\lt<. Such relation is no longer reflexive and antisymmetric, but still transitive. If, for the set AAA, every pair of (x,y)∈A×A(x,y)\in A\times A(x,y)∈A×A satisfies one of x

yx\gt yx>y or x=yx=yx= yx=y, So AAA is called eal ordered. Further, define the minimum element of the set AAA to be A ∈Aa\in Aa∈A, which satisfies ∀x∈A, A ≤x\forall x\in A, A \ LEq x∀ X ∈A, A ≤ X ≤ X (the largest element can be similarly defined), then, Eal ordered AAA is called well-ordered if every subset of eal AAA has a minimum element.
\lt>

A mapping transformation/function is defined as the T: X ↦ YT: X \ mapsto YT: X ↦ Y, this is a kind of each element in the XXX and YYY linked to only one element in the rules. XXX is called domain, YYY is codomain, Collection of GT = {(x, y) : x ∈ x, y = T (x)} ⊆ x x YG_T = \ {(x, y) : \ x in x, y = T (x) \} \ \ subseteq x times YGT = {(x, y) : x ∈ x, y = T (x)} ⊆ x x y is called the graph of TTT. Set T (A) = {T (x) : x ∈ a.} ⊆ YT (A) = \ {T (x) : x \ in A \} \ subseteq YT (A) = {T (x) : x ∈ a.} ⊆ Y called AAA image, under the condition of TTT for B ⊆ YB \ subseteq YB ⊆ Y, Set T – 1 (B) = {x: T ∈ B} (x) ⊆ XT ^ {1} (B) = \ {x: T (x) \ \} in B \ subseteq XT – 1 (B) = {x: T (x) ∈ B} ⊆ x is called the BBB in the TTT inverse image. The set T(X)T(X)T(X) is called the range of TTT. If T(X)=YT(X)=YT(X)=Y, the mapping is called from XXX onto YYY, otherwise into YYY. If each YYY is a unique image x∈Xx\in Xx∈X, then the mapping is one-to-one, or written as 111-111, which is called injective in Chinese.

T−1T^{-1}T−1 is a Correspendence, but not necessarily a mapping, when each element in XXX corresponds to a rule that may not be unique in YYY. If the mapping is 111-111 and is onto, the mapping is called one-to-one correspendence. For a mapping, T(x1)≤T(x2)T(x_1)\leq T(x_2)T(x1)≤T(x2) if and only if x1≤x2x_1\leq x_2x1≤x2, Call this mapping order-preserving. If XXX is partial ordered, represented by ≤\leq≤, a 111-111 mapping can induce ** to induce a partial ordering on codomain. If this mapping is still onto, linear ordering on XXX can induce a linear ordering on YYY.

The number of elements ina set is called the cardinality or cardinal number of the set. If 111-111 correspondence exists between AAA and BBB, then both sets are equipotent.

2 countable set

Write the cardinal number of the positive natural numbers set N+N^+N+ as ℵ\alephℵ. An infinite set is called countable or denumerable if it has 1−11-11−1 correspondence with the elements in N+N^+N+.

The set of integers ZZZ is countable because for any N ∈ n +n\in n ^+n∈ n +, let it correspond to ⌊n/2⌋(−1)n∈Z\lfloor n/2\rfloor (-1)^n\in Z⌊n/2⌋(−1)n∈Z.

Theorem: The rational number set QQQ countable.

Theorem: The union of a countable collection of countable sets is a countable set.

A Collection of duplicate elements is allowed.

3 Real number continuum

Theorem: The set of real numbers RRR is uncountable.

If the cardinal number of RRR is CCC, ℵ

Theorem: Any open interval is uncountable.

Theorem: Any open interval is equipotent with RRR.

For the open interval (a,b)(a,b)(a,b), Arbitrary x ∈ Rx \ in Rx ∈ R mapping to y = a + b2 + x2 (b – a) (1 + ∣ x ∣) y = \ dfrac {} a + b + \ dfrac {2} {x} (b – a) (1 + | | x) {2} y = a + b + 2 (1 + ∣ x ∣) x (b – a) can pass.

Theorem: the real number plane R2=R×RR^2=R\times RR2=R×R is equipotent.

Theorem: Any open interval contains at least one rational number.

For the open interval (a,b)(a,b)(a,b), suppose a≥0a\geq 0A ≥0, take QQQ as the smallest integer greater than 1/(b− A)1/(b-a)1/(b− A), take PPP as the smallest integer greater than QBQBQB, Is there will be (p – 1)/q ∈ (a, b) (1) p/q \ in (a, b) (p – 1)/q ∈ (a, b), (p – 1)/q ∈ q (1) p/q \ in q ∈ (p – 1)/q q.

Inference: Every collection of disjoint open intervals is countable.

Because every open interval contains at least one rational number, the collection of these disconnected open intervals can establish a corresponding relationship with any rational number in each of the open intervals, and the set of rational numbers is countable.

Here are some more definitions of sets. The supremum of set A⊂RA\subset RA⊂R, if there is, is the minimum YYy for any X ∈Ax\in Ax∈A which satisfies x≤yx\leq yx≤y, and can be written sup⁡A\sup AsupA; Instead, the infimum of the set AAA can be defined as inf⁡A\ INF AinfA. For some subset of RRR, if there is an upper bound, there must be supremum, if there is a lower bound, there must be Infimum. If we could define extended real line R∪ =R∪{−∞,+∞}\bar R=R\cup \{-\infty,+\infty\}Rˉ=R∪{−∞,+∞} (treating infinity as an element, too), then all sets would have supremum and Infimum. In addition to remember R ˉ + = R ∪ {+ up} \ bar R ^ + = R \ cup \ {+ \ infty \} R ˉ + = R ∪ {+ up}.

Sequence of sets

The Monotone sequence (Monotone sequence) is non-cosmic (meaning ∀ N,An⊆An+1\forall n, A_n\subseteq A_{n+1}∀ N,An⊆An+1) or non-increasing refers to the sequence of ∀ N,An⊇An+1\forall N, A_{n}\ Supseteq A_{n+1}∀ N,An⊇An+1), there are also strict monotone sequences, Replace the inclusion relationship with a strict inclusion relationship ⊂\subset⊂ and what \supset⊃.

The limit of the sequence AAA is the same as the A=∪n=1∞AnA=\cup_{n=1}^{\infty}A_nA=∪n=1∞An for the non-decreasing sequence. Or for the non-increasing sequence A=∩n=1∞AnA= cap_{n=1}^{infty}A_nA=∩n=1∞An, can be written as An↑AA_n\uparrow AAn↑A and An↓AA_n\downarrow AAn↓A, Or in general, lim⁡n→∞An=A\lim\limits_{n\to\infty}A_n = An→∞limAn=A, or An→AA_n\to AAn→A.

For any collection sequence {An} \ {A_n \} {An}, collection of Bn = ∪ m = n up AmB_n = \ cup_} {m = n ^ {\ infty} A_mBn = ∪ m = n up Am for non – increasing sequence, So B=lim⁡n→∞BnB=\lim\limits_{n\to\infty}B_nB=n→∞limBn exists and is called {An}\{A_n\}{An} superior limit, Write it as limsup ⁡nAn\ limsup_na_nlimsupnan. Conversely, the limit of the non-decreasing sequence Cn=∩m= N ∞AmC_n=\cap_{m= N}^{\infty}A_mCn=∩m= N ∞Am CCC is the inferior limit of {An}\{A_n}{An}. Write lim INF ⁡nAn\liminf_n A_nliminfnAn. Formally defined as

By De Morgan’s laws, lim INF ⁡nAn=(lim sup⁡nAnc)c\liminf_n A_n = \left(\limsup_n A_n^c \right)^climinfnAn=(limsupnAnc)c.

Lim sup⁡nAn\limsup_n A_nlimsupnAn is a set of infinitely many elements that can be filled by AnA_nAn, Lim inf⁡nAn\liminf_n A_nliminfnAn is a set of elements found in all but a finite number of AnA_nAn.

The above concepts provide a convergence criterion for set sequences: Lim inf⁡nAn⊆lim sup⁡nAn\ liminf_a_n \subseteq \limsup_n A_nliminfnAn⊆limsupnAn. If the two sets are not equal, {An}\{A_n\}{An} do not converge.

5 subsets of classes

The set of all subsets of XXX becomes the power set of XXX, denoted 2X2^X2X. For a countable set, consider its power set to have 2ℵ2^\aleph2ℵ elements.

Theorem: 2ℵ=c2^\aleph =c2 ℵ=c

Next, some properties of subsets of a given set are investigated. A Power set is generally too large for the problem under study. The following series of definitions aims to define a subset of 2X2^X2X that is large enough for the problem under study and has properties that we can handle easily. The general approach is to select a set of known properties to form a basic collection, and then create new collections to add to it with some specific operations.

Define Ring: nonempty class R\mathscr{R}R consisting of subsets of set XXX, Ring if:

• ∅ ∈ R \ empty \ \ in mathscr {R} ∅ ∈ R;
• If A∪B∈RA\ in\mathscr{R}A∈R and B∈RB\in\mathscr{R}B∈R, then A∪B∈RA\cup B\in\mathscr{R} A∪B∈R, A∩B∈RA\cap B\in\mathscr{R} A∩B∈R, A – B ∈ RA – B \ \ in mathscr {R} A – B ∈ R.

The operations of Ring for union, intersection, and difference are closed. However, ring does not necessarily contain the complete XXX itself. If XXX is added, it becomes a field (or algebra) definition:

Define Field: class F\mathscr{F}F consisting of subsets of XXX, Field if:

• X ∈ FX \ \ mathscr in {} F ∈ X F;
• If A∈FA\in\mathscr{F}A∈F, then Ac∈FA^c\in\mathscr{F}Ac∈F;
• If A∪B∈FA\ in\mathscr{F}A∈F and B∈FB\in\mathscr{F}B∈F, then A∪B∈FA\cup B\in\mathscr{F} A∪B∈F.

If a collection C\mathscr{C}C is given and it is interpreted as “seed” to generate fields, the smallest field containing C\mathscr{C}C is called field generated by C\mathscr{C}C.

The concepts of Ring and field are somewhat limited in their application to probability theory, so the following definitions are introduced:

Define semi-ring: a nonempty class S\mathscr{S}S consisting of subsets of the set XXX, semi-ring if:

• ∅ ∈ \ S empty \ \ in mathscr {S} ∅ ∈ S;
• If A∈SA\in\mathscr{S}A∈S and B∈SB\in\mathscr{S}B∈S, then A∩B∈SA\cap B\in\mathscr{S} A∩B∈S;
• If A∈SA\in\mathscr{S}A∈S, B∈SB\in\mathscr{S}B∈S and A⊆BA \subseteq BA⊆B, then ∃n<∞\exist n\lt \infty∃n<∞, Make B−A=∪j= 1NCJB-A =\cup_{j=1}^{n} C_jB−A=∪j=1nCj, The Cj ∈ SC_j \ \ in mathscr {S} Cj and for j ∈ S indicates j ‘j \ neq j’ j  = j ‘for Cj studying Cj’ = ∅ C_j \ cap C_ {j ‘} = \ emptyCj studying Cj ‘= ∅.

The third property is simply that the difference of any two sets of S\mathscr{S}S can be decomposed into a union of a finite number of sets of S\mathscr{S}S.

Add XXX itself to the semi-ring, and it becomes semi-algebra.

6 Sigma fields

In the previous section, field closed for Complement and Finite Union. We extend field’s Finite Union to complement and Finite Union.

Sigma sigma sigma-field (sigma-algebra) : class F sigma sigma-field {F}F

• X ∈ FX \ \ mathscr in {} F ∈ X F;
• If A∈FA\in\mathscr{F}A∈F, then Ac∈FA^c\in\mathscr{F}Ac∈F;
• If {the An, n ∈ n +} \ {A_n, n \ n in ^ + \} {the An, n ∈ n +} to F \ mathscr {} F F collection in the sequence, then ∪ n = 1 up An ∈ \ cup_ F {n = 1} ^ {\ infty} A_n \ \ mathscr in {} F ∪ n = 1 up An ∈ F.

σ\sigmaσ-field is closed for Complement and countable union. Given a collection C\mathscr{C}C, the intersection of σ\sigmaσ-field generated by C\mathscr{C}C is called σ\sigmaσ-field generated by C\mathscr{C}C, It is denoted as σ(C)\sigma(\mathscr{C})σ(C).

Theorem: If C\mathscr{C}C is a finite collection, then σ(C)\sigma(\mathscr{C})σ(C) is also finite, otherwise σ(C)\sigma(\mathscr{C})σ(C) is always uncountable.

If take X = RX = RX = R, C = {(- up, R] : R ∈ Q} \ mathscr {C} = \ {(- \ infty, R] : R \ \} in Q C = {(- up, r] : r ∈ Q}, the sigma (C) \ sigma (\ mathscr {C}) sigma (C) is called Borel field of RRR, can generally be counted as B \ mathscr {B} B. B\mathscr{B}B can be generated from many different collections. If given a real interval III, then BI={B∩I:B∈B}\mathscr{B}_I = \{B\cap I: B\in\mathscr{B}\}BI={B∩I:B∈B} is called the restnctlon of B\mathscr{B}B to III, or Borel field on III. In fact, the BI \ mathscr _IBI can be made of C = {B} {(- up, r] studying I: r ∈ Q} \ mathscr = {C} \ {(\ \ infty, r] cap I: \ r \ in Q} C = {(- up, r] studying I: r ∈ Q}.

The union of two σ\sigmaσ -fields is not necessarily aσ \sigmaσ-field, The smallest σ\sigmaσ-field containing all the elements of two σ\sigmaσ-field F\mathscr{F}F and G\mathscr{G}G is denoting F∨ sigma \mathscr{F}\vee\mathscr{G}F∨G. However, the intersection F∩G={A:A∈FandA∈G}\mathscr{F}\cap\mathscr{G}=\{A:A\in \mathscr{F}\ quad\text{and} \quad A \in\mathscr{G}\}F∩G={A:A∈FandA∈G}, it must be σ\sigmaσ-field, for the unity of symbols can be written as F∧G\mathscr{F}\wedge\mathscr{G}F∧G, It is the maximum σ\sigmaσ-field that guarantees that the element belongs to both F\mathscr{F}F and G\mathscr{G}G. Both concepts can be generalized to countably many cases.

A great deal of work in probability theory and measure theory is devoted to proving that a class of sets is σ\sigmaσ-field. The first two of the three properties of the sigma \sigma sigma -field definition are easy to verify, but the last one is difficult to verify. For this purpose we define a monotone class M\mathscr{M}M, which also consists of some sets: If {An}\{A_n\}{An} is monotone sequence, has the limit AAA, and ∀ N,An∈M\forall N, A_n\in\mathscr{M}∀ N,An∈M, then A∈MA\in \mathscr{M}A∈M, Call such M\mathscr{M}M monotone class. Using this and the following theorem, it is convenient to prove that some classes are σ\sigmaσ-field.

Theorem: F\mathscr{F}F is σ\sigmaσ-field if and only if F\mathscr{F}F is field and it is a Monotone class.

Using this theorem, when considering whether a class is σ\sigmaσ-field, we need only consider whether the limits of Monotone sequences belong to it.

Another common trick is Dynkin’s π\ PI π- λ\lambda lambda Theorem. To this need to introduce two concepts to pave the way.

The definition of PI \ PI PI – system: There is class P\mathscr{P}P, if A∈PA\in\mathscr{P}A∈P and B∈PB\in\mathscr{P}B∈P, then A∩B∈PA\cap B\in\mathscr{P} A∩B∈P, Then P\mathscr{P}P is π\ PI π-system.

Define lambdaλ-system: there is a class L\mathscr{L}L, then L\mathscr{L}L is lambda lambdaλ-system if it satisfies the following properties:

• X ∈ LX \ \ in mathscr {L} X ∈ L;
• If A∈LA\in\mathscr{L}A∈L, B∈LB\in\mathscr{L}B∈L and B⊆AB\subseteq AB⊆A, then A−B∈ la-b \in\mathscr{L}A−B∈L;
• If {An∈L}\{A_n\in\mathscr{L}\}{An∈L} is A non-decreasing sequence and An↑AA_n\uparrow AAn↑A, then A∈LA\in\mathscr{L}A∈L.

λ\lambdaλ-system is closed for complement. And since rule 2 means that ∀ N,Bn=An+1−An∈L\forall N, B_n=A_{n+1} -a_n \in\mathscr{L}∀ N,Bn=An+1−An∈L, the third rule also says that, The countable union of disjoint sets in L\mathscr{L}L is still in L\mathscr{L}L. Using this, we have the following theorem.

Theorem: A class L\mathscr{L}L is λ\lambdaλ-system if and only if:

• X ∈ LX \ \ in mathscr {L} X ∈ L;
• If B∈LB\in\mathscr{L}B∈L, then Bc∈LB^c\in\mathscr{L}Bc∈L;
• If {An∈L}\{A_n\in\mathscr{L}\}{An∈L} is a disjoint sequence, then ∪nAn∈L\cup_n A_n\in\mathscr{L}∪nAn∈L.

Sigma sigma -field must be λ\lambda lambda -system, and the class that is both π\ PI π-system and λ\lambda lambda -system must be sigma sigma sigma -field.

The following theorem uses these definitions.

Dynkin’s π\ PI π- λ\lambda lambda: If P\mathscr{P}P is a π\ PI π-system, L\mathscr{L}L is aλ \lambdaλ-system, and P\mathscr{P} subseteq \mathscr{L}P⊆L, The sigma (P) ⊆ L \ sigma (\ mathscr {P}) \ subseteq \ mathscr {L} sigma (P) ⊆ L.

reference

• Davidson, J., 1994. Stochastic limit theory: An introduction for econometricians. OUP Oxford.