Category: Mathematics


My last week in Israel before I come back to Beijing 🙂

https://sites.google.com/site/igtconf2017/

Program

Talks and coffee breaks are in Dan David 001
Dinner and lunches are in Gan Hadkalim (in front of exact sciences building). 
 
Monday, July 10, 2017
 
10:10 — 10:20    Coffee
10:30 — 11:00     Adam Kalai                        Unambiguous communication without a common prior
11:00 — 11:30    Éva Tardos
11:30 — 11:50     Coffee break
11:50 — 12:20     Moshe Tennenholtz        A Game Theoretic Approach to Information Retrieval
12:20 — 12:50    Ariel Rubinstein              Multi-dimensional Reasoning in Games: Framework, Equilibrium and Applications
13:00 — 14:30    Lunch break
14:30 — 15:00    Yuval Salant                   Statistical Inference in Games
15:00 — 15:30    Georgy Egorov               Strategic Communication with Minimal Verification 
15:30 — 16:00    Peter Klibanoff                Incomplete Information Games with Ambiguity Averse Players
16:00 — 16:20    Coffee break
16:20 — 16:50    Peyton Young                 Games, Norms, and Institutions
16:50 — 17:20    David Schmeidler           Desirability
17:20 — 17:50    Robert Aumann              My Ehud
18:30                 Dinner
 
 
Tuesday, July 11, 2017
 
10:10 — 10:20    Coffee
10:30 — 11:00    Tim Roughgarden          On a Theorem of Kalai and Samet
11:00 — 11:30    Michal Feldman              Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs
11:30 — 11:50    Coffee break
11:50 — 12:20    Abraham Neyman          Cooperative Strategic Games
12:20 — 12:50    Rann Smorodinsky         Bayesian Learning in Markets with Common Value
13:00 — 14:30    Lunch break
14:30 — 15:00    Leeat Yariv
15:00 — 15:30    Johannes Hörner
15:30 — 16:00    Jonathan Weinstein        Complementarity Revisited
16:00                 Coffee
 
Wednesday, July 12, 2017
 
10:10 — 10:20    Coffee
10:30 — 11:00    Paul Milgrom                    Economics and Computer Science of a Radio Spectrum Reallocation
11:00 — 11:30    TBA, Microsoft Research
11:30 — 11:50    Coffee break
11:50 — 12:20    Rakesh Vohra
12:20 — 12:50    Noam Nisan
13:00 — 14:30    Lunch break
14:30 — 15:00    Yair Tauman                    Coordination games with unknown outside options
15:00 — 15:30    Dov Samet
15:30 — 16:00    Chaim Fershtman           The Competitive Effects of Information Sharing
16:00 — 16:20    Coffee break
16:20 — 16:50    Ehud Lehrer
16:50 — 17:20    Ehud Kalai
17:30                 Reception
Advertisements

Bounded: |f(x)|\le M for all x\in \mathbb E.

Uniformly bounded: |f_n(x)|<M for all x\in\mathbb E, n=1, 2, 3,...

Pointwise bounded: |f_n(x)<\phi(x)| where \phi is a finite valued function, and x\in\mathbb E, n=1, 2, 3,...

K is compact, f_n is pointwise bounded and equitcontinuous \Rightarrow f_n is uniformly bounded, and f_n contains a uniformly convergent subsequence.

 

Continuous: f: \mathbb E\subset X\to Y, p\in\mathbb E, \forall \varepsilon>0, \exists \delta>0 s.t. \forall x\in\mathbb E, d_X(x, p)<\delta\Rightarrow d_Y(f(x), f(p))<\varepsilon.

Uniformly continuous: \forall \varepsilon>0, \exists \delta>0 s.t. d_X(p, q)<\delta\Rightarrow d_Y(f(p), f(q))<\varepsilon.

Equicontinuous: \forall \varepsilon>0, \exists \delta>0 s.t. d(x, y)<\delta\Rightarrow |f(x)-f(y)|<\varepsilon.

Equicontinuous \Rightarrow uniformly continuous.

Compact set, uniformly convergence \Rightarrow equicontinuous.

 

Convergent: A sequence \{p_n\} in a metric space X, \exists p\in X s.t. \forall \varepsilon>0, \exists N s.t. n\ge N\Rightarrow d(p_n, p)<\varepsilon.

Uniformly convergent (definition 1): a sequence of functions \{f_n\}, n=1, 2, 3, ... converges uniformly on \mathbb E to a function f if \forall \varepsilon>0, \exists N s.t. n\ge N\Rightarrow |f_n(x)-f(x)|\le \varepsilon for all x\in\mathbb E.

Uniformly convergent (definition 2): \varepsilon>0, \exists N s.t. m\ge N, n\ge N, x\in\mathbb E\Rightarrow |f_n(x)-f_m(x)|\le \varepsilon.

Pointwise convergent: f(x)=\lim_{n\to\infty} f(x) (x\in\mathbb E).

If \{f_n\} is uniformly convergent, then \lim_{t\to x}\lim_{n\to\infty}f_n(t)=\lim_{n\to\infty}\lim_{t\to x}f_n(x).

K is compact, \{f_n\} is continuous and pointwise convergent, f_n\ge f_{n+1} \Rightarrow f_n\to f uniformly.

f_n\to f uniformly, where f_n\in\mathcal R Rightarrow \int_a^b f d_\alpha=\lim_{n\to\infty}\int_a^b f_n d\alpha.

\{f_n\} is differentiable, \{f_n'\} converge uniformly on [a, b]\Rightarrow f_n converges uniformly, and $f'(x)=\lim_{n\to\infty}f_n'(x) (a\le x\le b)$.

\{f_n\} is differentiable, f' is uniformly bounded \Rightarrow f_n is equicontinuous.

 

 

Definition. An outer measure on a nonempty set X is a function \mu^*: \mathcal P(X)\to[0, \infty] that satisfies

1) \mu^*(\emptyset)=0,

2) \mu^*(A)\le\mu^*(B) if $A\subset B$,

3) \mu^*(\cup_1^\infty A_j)\le \sum_1^\infty\mu^*(A_j).

 

The most common way to obtain outer measure is to start with a family \mathcal E of “elementary sets” on which a notion of measure is defined (such as rectangles in the plane) and then to approximate arbitrary sets “from the outside” by countable unions of members of \mathcal E. The precise construction is as follows.

 

Proposition. Let \mathcal E\subset\mathcal P(X) and \rho: \mathcal E\to[0, \infty] be such that \emptyset\in\mathcal E, X\in\mathcal E and \rho(\emptyset)=0. For any A\subset X, define

\mu^*(A)=\inf\{\sum_1^\infty\rho(E_j): E_j\in\mathcal E and A\subset \cup_1^\infty E_j\}.

Then \mu^* is an outer measure.

Proof. For any  A\subset X, \exists \{E_j\}_1^\infty\subset\mathcal E such that A\subset\cup_1^\infty E_j (take E_j=X for all j) so the definition of \mu^* makes sense. Obviously \mu^*(\emptyset)=0 (take E_j=\emptyset for all j), and \mu^*(A)\le\mu^*(B) for A\subset B because the set over which the infimum is taken in the definition of \mu^*(A) includes the corresponding set in the definition of \mu^*(B). To prove countable subadditivity, suppose \{A_j\}_1^\infty\subset\mathcal P(X) and \epsilon>0. For each j there exists \{E_j^k\}_{k=1}^\infty\subset\mathcal E such that A_j\subset\cup_{k=1}^\infty E_j^k and \sum_{k=1}^\infty\rho(E_j^k)\le\mu^*(A_j)+\epsilon 2^{-j}. But then if A=\cup_1^\infty A_j, we have A\subset\cup_{j, k=1}^\infty E_j^k and \sum_{j, k}\rho(E_j^k)\le\sum_j\mu^*(A_j)+\epsilon, whence \mu^*(A)+\epsilon. Since \epsilon is arbitrary, we are done. \Box

 

Definition. If \mu^* is an outer measure on X, a set A\subset X is called \mu^*-measurable if

\mu^*(E)=\mu^*(E\cap A)+\mu^*(E\cap A^c) for all E\subset X.

The inequality \mu^*(E)\le\mu^*(E\cap A)+\mu^*(E\cap A^c) holds for any A and E, so to prove that A is \mu^*-measurable, it suffices to prove that the reverse inequality. The latter is trivial if \mu^*(E)=\infty, so we see that A is \mu^*-measurable iff

\mu^*(E)\ge\mu^*(E\cap A)+\mu^*(E\cap A^c) for all E\subset X such that \mu^*(E)<\infty.

If E is a “well-behaved” set such that E\supset A, the equation \mu^*(E)=\mu^*(E\cap A)+\mu^*(E\cap A^c) says that the outer measure of A, \mu^*(A) is equal to the “inner measure” of A, \mu^*(E)-\mu^*(E\cap A^c).

Caratheodory’s Theorem. If \mu^* is an outer measure on X, the collection \mathcal M of \mu^*-measurable sets is a \sigma-algebra, and the restriction of \mu^* to \mathcal M is a complete measure.

Proof. First, we observe that \mathcal M is closed under complements since the definition of \mu^*-measurability of A is symmetric in A and A^c. Next, if A, B\in\mathcal M and E\subset X,

\mu^*(E)=\mu^*(E\cap A)+\mu^*(E\cap A^c)=\mu^*(E\cap A\cap B)+\mu^*(E\cap A\cap B^c)+\mu^*(E\cap A^c\cap B)+\mu^*(E\cap A^c\cap B^c).

But (A\cup B)=(A\cap B)\cup(A\cap B^c)\cup(A^c\cap B), so by subadditivity,

\mu^*(E\cap A\cap B)+\mu^*(E\cap A\cap B^c)+\mu^*(E\cap A^c\cap B)\ge\mu^*(E\cap(A\cup B)),

and hence

\mu^*(E)\ge\mu^*(E\cap(A\cup B))+\mu^*(E\cap(A\cup B)^c).

It follows that A\cup B=\mathcal M, so \mathcal M is an algebra. Moreover, if A, B\in\mathcal M and A\cap B=\emptyset,

\mu^*(A\cup B)=\mu^*((A\cup B)\cap A)+\mu^*((A\cup B)\cap A^c)=\mu^*(A)+\mu^*(B),

so \mu^* is finitely additive on \mathcal M.

To show that \mathcal M is a \sigma-algebra, it will suffice to show that \mathcal M is closed under countable disjoint unions. If \{A_j\}_1^\infty is a sequence of disjoint sets in \mathcal M, let B_n=\cup_1^n A_j and B=\cup_1^\infty A_j. Then for any E\subset X,

\mu^*(E\cap B_n)=\mu^*(E\cap B_n\cap A_n)+\mu^*(E\cap B_n\cap A_n^c)=\mu^*(E\cap A_n)+\mu^*(E\cap B_{n-1}),

so a simple induction shows that \mu^*(E\cap B_n)=\sum_1^n\mu^*(E\cap A_j). Therefore,

\mu^*(E)=\mu^*(E\cap B_n)+\mu^*(E\cap B_n^c)\ge\sum_1^n\mu^*(E\cap A_j)+\mu(E\cap B^c),

and letting n\to\infty we obtain

\mu^*(E)\ge\sum_1^\infty (E\cap A_j)+\mu^*(E\cap B^c)\ge\mu^*(\cup_1^\infty(E\cap A_j))+\mu^*(E\cap B^c)=\mu^*(E\cap B)+\mu^*(E\cap B^c)\ge \mu^*(E).

All the inequalities in the last calculation are thus equalities. It follows that B\in\mathcal M and taking E=B that \mu^*(B)=\sum_1^\infty\mu^*(A_j), so \mu^* is countably additive on \mathcal M. Finally, if \mu^*(A)=0, for any E\subset X we have

\mu^*(E)\le\mu^*(E\cap A)+\mu^*(E\cap A^c)=\mu^*(E\cap A^c)\le\mu(E),

so that A\in\mathcal M. Therefore \mu^*|\mathcal M is a complete measure. \Box

Let go of all thoughts of limitations about how you should or should not behave based on how old or young you are. Age is nothing but a number, “an issue of mind over matter. If you don’t mind, it doesn’t matter.” ~ Mark Twain

References:

[1] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications, 2ed, page 28-30.

[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf.

Definition. Let X be a set equipped with a \sigma-algebra \mathcal M. A measure on \mathcal M (or on (X, \mathcal M), or simply on X if \mathcal M\to[0, \infty] such that

1). \mu(\emptyset)=0.

2). (Countable additivity) if \{E_j\}_1^\infty is a sequence of disjoint sets in \mathcal M, then \mu(\cup_1^\infty E_j)=\sum_1^\infty\mu(E_j).

2)’. if E_1, ..., E_n are disjoint sets in \mathcal M, then \mu(cup_1^n E_j)=\sum_1^n\mu(E_j),

because one can take E_j=\emptyset for j>n. A function \mu that satisfies 1) and 2)’ but not necessarily 2) is called a finitely additive measure.

 

If X is a set and \mathcal M\subset\mathcal P(X) is a \sigma-algebra, (X, \mathcal M) is called a measurable space and the sets in \mathcal M are called measurable sets. If \mu is a measure on (X, \mathcal M), then (X, \mathcal M, \mu) is called a measure space.

 

Let (X, \mathcal M, \mu) be a measure space. If \mu(X)<\infty (which implies that \mu(E)<\infty for all E\in\mathcal M since \mu(X)=\mu(E)+\mu(E^c)), \mu is called finite. If X=\cup_1^\infty E_j where E_j\in\mathcal M and \mu(E_j)<\infty for all j, the set E is said to be \sigma-finite for \mu. More generally, if E=\cup_1^\infty E_j where E_j\in\mathcal M and \mu(E_j)<\infty for all j, the set E is said to be \sigma-finite for \mu. If for each E\in\mathcal M with \mu(E)=\infty there exists F\in\mathcal M with F\subset E and 0<\mu(F)<\infty, \mu is called semifinite.

 

Remark. Every \sigma-finite measure is semifinite, but not conversely.

 

Examples. 1) Let X be any nonempty set, \mathcal M=\mathcal P(X), and f any function from X to [0, \infty]. Then f determines a measure \mu on \mathcal M by the formula \mu(E)=\sum_{x\in E}f(x). \mu is semifinite iff f(x)<\infty for every x\in X, and \mu is \sigma-finite iff \mu is semifinite and \{x: f(x)>0\} is countable.

a. If f(x)=1 for all x, \mu is called counting measure;

b. If for some x_0\in X, f is defined by f(x_0)=1 and f(x)=0 for x\not=x_0, \mu is called the point mass or Dirac measure at x_0.

 

2) Let X be an uncountable set, and let \mathcal M be the \sigma-algebra of countable or co-countable sets. The function \mu on \mathcal M defined by \mu(E)=0 if E is countable and \mu(E)=1 if E is co-countable is easily seen to be a measure.

 

3) Let X be an infinite set and M=\mathcal P(X). Define \mu(E)=0 if E is finite, \mu(E)=\infty if E is infinite. Then \mu is a finitely additive measure but not a measure.

 

Theorem. Let (X, \mathcal M, \mu) be a measure space.

a). (Monotonicity) If E, F\in\mathcal M and E\subset F, then $\mu(E)\le\mu(F)$.

b). (Subadditivity) If \{E_j\}_1^\infty\subset \mathcal M, then \mu(\cup_1^\infty E_j)\le\sum_1^\infty \mu(E_j).

c). (Continuity from below) If \{E_j\}_1^\infty\subset \mathcal M and E_1\subset E_2\subset..., then \mu(\cup_1^\infty E_j)=\lim_{j\to\infty}\mu(E_j).

d). (Continuity from above) If \{E_j\}_1^\infty\subset \mathcal M, E_1\supset E_2\supset..., and \mu(E_1)<\infty, then \mu(\cap_1^\infty E_j)=\lim_{j\to\infty}\mu(E_j).

Proof. a) If E\subset F, then \mu(F)=\mu(E)+\mu(F\setminus E)\ge\mu(E).

b) Let F_1=E_1 and F_k=E_k\setminus(\cup_1^{k-1} E_j) for k>1. Then the F_k's are disjoint and \cup_1^n F_j=\cup_1^n E_j for all n. Therefore, by a)

\mu(cup_1^\infty E_j)=\mu(\cup_1^\infty F_j)=\sum_1^\infty\mu(F_j)\le\sum_1^\infty\mu(E_j).

c) Setting E_0=\emptyset, we have

\mu(\cup_1^\infty E_j)=\sum_1^\infty\mu(E_j\setminus E_{j-1})=\lim_{n\to\infty}\sum_1^n\mu(E_j\setminus E_{j-1})=\lim_{n\to\infty}\mu(E_n).

d) Let F_j=E_1\setminus E_j; then F_1\subset F_2\subset ..., \mu(E_1)=\mu(F_j)+\mu(E_j), and \cup_1^\infty F_j=E_1\setminus(\cap_1^\infty E_j). By c) then

\mu(\cap_1^\infty E_j)+\lim_{j\to\infty}\mu(F_j)=\mu(\cap_1^\infty E_j)+\lim_{j\to\infty}[\mu(E_1)-\mu(E_j)].

Since \mu(E_1)<\infty, we may subtract it from both sides to yield the desired result. \Box

Remark.  The condition \mu(E_1)<\infty in d) could be replaced by \mu(E_n)<\infty for some n>1, as the first n-1 E_j‘s can be discarded from the sequence without affecting the intersection. However, some finiteness assumption is necessary, as it can happen that \mu(E_j)=\infty for all j but \mu(cap_1^\infty E_j)<\infty.

Definition. If (X, \mathcal M, \mu) is a measure space, a set E\in\mathcal M such that \mu(E)=0 is called a null set. By subadditivity, any countable union of null sets is a null set, a fact which we shall use frequently. If a statement about points x\in X is true except for x in some every x. (If more precision is needed, we shall speak of a \mu-null set, or \mu-almost everywhere).

If \mu(E)=0 and F\subset E, then \mu(F)=0 by monotonicity provided that F\in\mathcal M, but in general it need not be true that F\in\mathcal M. A measure whose domain includes all subsets of null sets is called complete. Completeness can sometimes obviate annoying technical points, and it can always be achieved by enlarging the domain of \mu, as follows.

Theorem. Suppose that (X, \mathcal M, \mu) is a measure space. Let \mathcal N=\{N\in\mathcal: \mu(N)=0\} and \bar{\mathcal M}=\{E\cup F: E\in\mathcal M\} and F\subset N for some N\in\mathcal N\}. Then \bar{\mathcal M} is a \sigma-algebra, and there is a unique extension \bar{\mu} of \mu to a complete measure on \bar{\mathcal M}.

Proof. Since \mathcal M and \mathcal N are closed under countable unions, so is \bar{\mathcal M}. If E\cup F\in\bar{\mathcal M} where E\in\mathcal M and F\subset N\in\mathcal N, we can assume that E\cap F=\emptyset (otherwise, replace F and N by F\setminus E and N\setminus E). Then E\cup F=(E\cup N)\cap(N^c\cup F), so (E\cup F)^c=(E\cup N)^c\cup(N\setminus F). But (E\cup N)^c\in\mathcal M and N\setminus F\subset N, so that (E\cup F)^c\in\bar{\mathcal M}. Thus \bar{M} is a \sigma-algebra.

If E\cup F\in\bar{\mathcal M} as above, we set \bar\mu(E\cup F)=\mu(E). This is well defined, since if E_1\cup F_1=E_2\cup F_2 where $F_j\subset N_j\in\mathcal N$, then $E_1\subset E_2\cup N_2$ and so \mu(E_1)\le\mu(E_2)+\mu(N_2)=\mu(E_2), and likewise \mu(E_2)\le\mu(E_1). It is easily verified that \bar\mu is a complete measure on \mu\mathcal M, and that \bar\mu is the only measure on \mathcal M that extends \mu.

Remark. The measure \bar\mu is called the completion of \mu, and \bar{\mathcal M} is called the completion of {\mathcal M} with respect to \mu.

“Whenever you meet a ghost, don’t run away, because the ghost will capture the substance of your fear and materialize itself out of your own substance… it will take over all your own vitality… So then, whenever confronted with a ghost, walk straight into it and it will disappear.” ~ Allan Watts

References:

[1] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications, 2ed, page 24-27.

[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf.

Let \{X_\alpha\}_{\alpha\in A} be an indexed collection of nonempty sets, X=\prod_{\alpha\in A} X_\alpha and \pi_\alpha: X\to X_\alpha the coordinate maps. If \mathcal M_\alpha is a \sigma-algebra on X_\alpha for each \alpha, the product \sigma-algebra on X is the \sigma-algebra generated by

\{\pi_\alpha^{-1}(E_\alpha): E_\alpha\in\mathcal M_\alpha, \alpha\in A\}.

Denote this \sigma-algebra by \bigotimes_{\alpha\in A}\mathcal M_\alpha. (If A=\{1, 2, ..., n\} we also write \bigotimes_1^n\mathcal M_j or \bigotimes_1\bigotimes...\bigotimes\mathcal M_n.)

Proposition 1. If A is countable then \bigotimes_{\alpha\in A}\mathcal M_\alpha is the \sigma-algebra generated by \{\prod_{\alpha\in A}E_\alpha: E_\alpha\in\mathcal M_\alpha\}.

Proof. If E_\alpha\in\mathcal M_\alpha, then \pi_\alpha^{-1}(E_\alpha)=\prod_{\beta\in A}E_\beta where E_\beta=X_\beta for \beta\not=\alpha; on the other hand, \prod_{\alpha\in A}E_\alpha=\cap_{\alpha\in A}\pi_\alpha^{-1}(E_\alpha). \Box

Proposition 2. Suppose that $latex\mathcal M_\alpha$ is generated by \mathcal E_\alpha, \alpha\in A. Then \bigotimes_{\alpha\in A}\mathcal M_\alpha is generated by \mathcal F_1=\{\pi_\alpha^{-1}(E_\alpha): E_\alpha\in E_\alpha, \alpha\in A\}. If A is countable and X_\alpha\in\mathcal E_\alpha for all \alpha, \bigotimes_{\alpha\in A}\mathcal M_\alpha is generated by \mathcal F_2=\{\prod_{\alpha\in A}E_\alpha: E_\alpha\in\mathcal E_\alpha\}.

Proof. It’s easily seen that \mathcal M(\mathcal F_1)\subset\bigotimes_{\alpha\in A}\mathcal M_\alpha. On the other hand, for each \alpha, the collection \{E\subset X_\alpha: \pi_\alpha^{-1}(E)\in\mathcal M(\mathcal F_1)\} is easily seen to be a \sigma-algebra on X_\alpha that contains E_\alpha and hence $latex\mathcal M_\alpha$. \Box

Proposition 3. Let X_1, ..., X_n be metric spaces and let X=\prod_1^nX_j, equipped with the product metric. Then \bigotimes_1^n \mathcal B_{X_j}\subset \mathcal B_X. If the X_j‘s are separable, then $latex\bigotimes_1^n\mathcal B_{X_j}=\mathcal B_X$.

Proof. By the Proposition 2, \bigotimes_1^n\mathcal B_{X_j} is generated by the sets \pi_j^{-1}(U_j), 1\le j\le n, where U_j is open in X_j. Since these sets are open in X, Lemma implies that \bigotimes_1^n\mathcal B_{X_j}\subset \mathcal B_X. Suppose now that C_j is a countable dense set in X_j, and let \mathcal E_j be the collection of balls in X_j with rational radius and center in C_j. Then every open set in X_j is a union of members of \mathcal E_j (a countable union, since E_j itself is countable). Moreover, the set of points in X whose jth coordinate is in C_j for all j is a countable dense subset of X, and the balls of radius r in X are merely products of balls of radius r in the X_j‘s. It follows that \mathcal B_{X_j} is generated by \mathcal E_j and \mathcal B_X is generated by \{\prod_1^n E_j: E_j\in\mathcal E_j\}. Therefore \mathcal B_X=\bigotimes_1^n\mathcal B_{X_j}. \Box

Corollary. \mathcal B_{\mathbb R^n}=\bigotimes_1^n\mathcal B_{\mathbb R}.

Definition. An elementary family is a collection \mathcal E of subsets of X such that:

1) \emptyset\in\mathcal E,

2) if E, F\in\mathcal E then E\cap F\in\mathcal E,

3) if E\in\mathcal E then E^c is a finite disjoint union of members of \mathcal E.

Proposition. If E is an elementary family, the collection \mathcal A of finite disjoint unions of members of \mathcal E is an algebra.

Proof. If A, B\in\mathcal E and B^c=\cup_1^J C_j (C_j\in\mathcal E, disjoint), then A\setminus B=\cup_1^J(A\cap C_j) and A\cup B=(A\setminus B)\cup B, where these unions are disjoint, so A\setminus B\in\mathcal A and A\cup B\in\mathcal A. It now follows by induction that if A_1, ..., A_n\in\mathcal E, then \cup_1^nA_j\in\mathcal A; By inductive hypothesis we may assume that A_1, A_2, ..., A_{n-1} are disjoint, and then \cup_1^n A_j=A_n\cup(\cup_1^{n-1}(A_j\setminus A_n)), which is a disjoint union. Suppose A_1, ..., A_n\in\mathcal E and A_m^c=\cup_{j=1}^{J_m}B_m^j with B_m^1, ..., B_m^{J_m} disjoint members of $latex\mathcal E$, then \mathcal A is closed under complements. \Box

“The power of imagination is incredible. Often we see athletes achieving unbelievable results and wonder how they did it. One of the tools they use is visualization or mental imagery… they made the choice to create their destinies and visualized their achievements before they ultimately succeeded.” ~ George Kohlrieser

References:

[1] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications, 2ed, page 22-24.

[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf.

Definition. Let X be a nonempty set. An algebra of sets on X is a nonempty collection \mathcal A of subsets of X that is closed under finite unions and complements; in other words, if E_1, E_2, ..., E_n\in\mathcal A, then \cup_1^n E_j\in\mathcal A; and if E\in\mathcal A, then E^c\in\mathcal A. A \sigma-algebra is an algebra that is closed under countable unions.

 

Remark. \cap_j E_j=(\cap_j E_j^c)^c, algebras (resp. \sigma-algebras) are also closed under finite (resp. countable) intersections. Moreover, if \mathcal A is an algebra, then \emptyset\in\mathcal A and X\in\mathcal A, for if E\in\mathcal A we have \emptyset=E\cap E^c and X=E\cup E^c.

An algebra \mathcal A is a \sigma-algebra provided that it is closed under countable disjoint unions. Indeed, suppose \{E_j\}_1^\infty\subset \mathcal A. Set

F_k=E_k\setminus [\cup_1^{k-1}E_j]=E_k\cap[\cup_1^{k-1}E_j]^c.

Then F_k‘s belong to \mathcal A and are disjoint, and \cup_1^\infty E_j=\cup_1^\infty F_k.

Example. If X is any set, \mathcal P(X) and \{\emptyset, X\} are \sigma-algebras. If X is uncountable, then

\mathcal A=\{E\subset X: E is countable or E^c is countable \}

is a \sigma-algebra, called the \sigma-algebra of countable or co-countable sets.

Remark. Since the intersection of any family of \sigma-algebras on X is a \sigma-algebra. If follows that if \mathcal E is any subset of \mathcal P(X), there is a unique smallest \sigma-algebra \mathcal M(\mathcal E) containing \mathcal E, namely, the intersection of all \sigma-algebra containing \mathcal E. \mathcal M(\mathcal E) is called the \sigma-algebra generated by \mathcal E.

Lemma. If E\subset \mathcal M(\mathcal F), then \mathcal M(\mathcal E)\subset \mathcal M(\mathcal F).

Proof. \mathcal M(\mathcal F) is a \sigma-algebra containing \mathcal E; it therefore contains \mathcal M(\mathcal E). \Box

Definition. If X is any metric space, or more generally any topological space, the \sigma-algebra generated by the family of open sets in X (or equivalently, by the family of closed sets in X) is called the Borel \sigma-algebra on X and is denoted by \mathcal B_X. Its members are called Borel sets. \mathcal B_x thus includes open sets, closed sets, countable intersections of open sets, countable unions of closed sets, and so forth.

Definition. A countable intersection of open sets is called a G_\delta set; a countable union of closed sets is called an F_\sigma set; a countable union of G_\delta sets is called a G_{\delta\sigma} set; a countable intersection of F_\sigma sets is called an F_{\sigma\delta} set.

Proposition. \mathcal B_{\mathbb R} is generated by each of the following:

a. the open intervals: \mathcal E_1=\{(a, b): a<b\},

b. the closed intervals: \mathcal E_2=\{[a, b]: a<b\},

c. the half-open intervals: \mathcal E_3=\{(a, b]: a<b\} or \mathcal E_4=\{[a, b): a<b\},

d. the open rays: \mathcal E_5=\{(a, \infty): a\in\mathbb R\} or \mathcal E_6=\{(-\infty, a): a\in\mathbb R\},

e. the closed rays: \mathcal E_7=\{[a, \infty): a\in\mathbb R\} or \mathcal E_8=\{(-\infty, a]: a\in\mathbb R\}.

Proof. By the Lemma above, since all of the sets are Borel sets, then \mathcal M(\mathcal E_j)\subset \mathcal B_\mathbb R for all j. Also, since every open set in \mathbb R is a countable union of open intervals, so by lemma again, \mathcal B_{\mathbb R}\subset\mathcal M(\mathcal E_1). Since all open intervals lie in \mathcal M(\mathcal E_j), then by lemma, \mathcal B_{\mathbb R}\subset\mathcal M(\mathcal E_j) for j\ge 2. For example, (a, b)=\cup_1^\infty[a+n^{-1}, b-n^{-1}]\in\mathcal M(\mathcal E_2). \Box

“What is tolerance? It is the consequence of humanity. We are all formed of frailty and error; let us pardon reciprocally each other’s folly – that is the first law of nature.” ~ Voltaire

References:

[1] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications, 2ed, page 21-22.

[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf.

For n\in\mathbb N we would like to have a function \mu that assigns to each E\subset\mathbb R^n a number \mu(E)\in[0, \infty], the n-dimensional measure of E, such that \mu(E) is given by the usual integral formulas when the latter apply. The function \mu has the following properties:

1) If E_1, E_2, ... is a finite or infinite sequence of disjoint sets, then

\mu(E_1\cup E_2\cup ...)=\mu(E_1)+\mu(E_2)+....

2) If E is congruent to F (that is, if E can be transformed into F by translations, rotations, and reflections), then \mu(E)=\mu(F).

3) \mu(Q)=1, where Q is the unit cube

Q=\{x\in\mathbb R^n: 0\le x_j\le 1 for j=1, ..., n\}.

However, 1)-3) are mutually inconsistent. To see why, we can define an equivalence relation on [0, 1) by declaring that x~y iff x-y\in Q is rational. Let N be a subset of [0, 1) that contains precisely one member of each equivalence class. Let R=\mathbb Q\cap[0, 1), and for each r\in R let

N_r=\{x+r: x\in N\cap[0, 1-r)\}\cup\{x+r-1: x\in N\cap[1-r, 1)\}

To obtain N_r, shift N to the right by r units and then shift the part that sticks out beyond [0, 1) one unit to the left. Then N_r\subset[0, 1), every x\in[0, 1) belongs to precisely one N_r. Indeed, if y is the element of N that belongs to the equivalence class of x, then x\in N_r where r=x-y if x\ge y or r=x-y+1 if x<y; on the other hand, if x\in N_r\cap N_s, then x-r (or x-r+1) and x-s (or x-s+1) would be distinct elements of N belonging to the same equivalence class, which is impossible.

Suppose that now \mu: \mathcal P(\mathbb R)\to [0, \infty] satisfies (i), (ii), and (iii). By (i) and (ii),

\mu(N)=\mu(N\cap[0, 1-r))+\mu(N\cap[1-r, 1))=\mu(N_r)

for any r\in R. Also, since R is countable and $[0, 1)$ is the disjoint union of the N_r‘s,

\mu([0, 1))=\sum_{r\in R}\mu(N_r)

by (1) again. But \mu([0,1))=1 by 3), since $\mu(N_r)=\mu(N)$, the sum on the right is either 0 (if \mu(N)=0) or \infty (if \mu(N)>0). Hence no such \mu can exist.

But in 1924, Banach and Tarski proved the following amazing result:

Let U and V be arbitrary bounded open sets in \mathbb R^n, n\ge 3. There exist k\in\mathbb N and subsets E_1, ..., E_k, F_1, ..., F_k of \mathbb R^n such that:

1) the E_j‘s are disjoint and their union is U;

2) the F_j‘s are disjoint and their union is V;

3) E_j is congruent to F_j for j=1,..., k.

The construction of sets E_j and F_j depends on the axiom of choice. But their existence precludes the construction of any \mu: \mathcal P(\mathbb R^n)\to[0,\infty] that assigns positive, finite values to bounded open sets and satisfies (1) for finite sequences as well as (2).

 

“Don’t take anything Personally Nothing others do is because of you. What others say and do is a projection of their own reality, their own dream. When you are immune to the opinions and actions of others, you won’t be the victim of needless suffering” ~ Miguel Ruiz

 

To be continued tomorrow 🙂

 

References:

[1] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications, 2ed, page 19-21.

[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf.

A sequence \{x_n\} in a metric space (X, \rho) is called Cauchy if \rho(x_n, x_m)\to 0 as n, m\to\infty. A subset E of X is called complete if every Cauchy sequence in E converges and its limit is in E. For example, \mathbb R^n is complete, while \mathbb Q^n is not.

 

Proposition. A closed subset of a complete metric space is complete, and a complete subset of an arbitrary metric space is closed.

Proof. If X is complete, E\subset X is closed, and \{x_n\} is a Cauchy sequence in E, \{x_n\} has a limit in X. So x\in\bar{E}=E. If E\subset X is complete and x\in\bar{E}, then there is a sequence \{x_n\} in E converging to x. \{x_n\} is Cauchy, so its limit lies in E; thus E=\bar E. \Box

 

In a metric space (X, \rho) we can define the distance from a point to a set and the distance between two sets. Namely, if x\in X and E, F\subset X,

\rho(x, E)=\inf\{\rho(x, y): y\in E\},

\rho(E, F)=\inf\{\rho(x, y): x\in E, y\in F\}=\inf\{\rho(x, F): x\in E\}.

Note that \rho(x, E)=0 iff $x\in\bar E$. We also define the diameter of E\subset X to be

diam E=\sup\{\rho(x, y): x, y\in E\}.

E is called bounded if diam E<\infty.

If E\subset X and \{V_\alpha\}_{\alpha\in A} is a family of sets such that E \subset \cup_{\alpha\in A}V_\alpha, \{V_\alpha\}_\alpha\in A is called a cover of E, and E is said to be covered by the V_\alpha‘s. E is called totally bounded if for every \epsilon>0, E can be covered by finitely many balls of radius \epsilon. Every totally bounded set is bounded, for if x, y\in\cup_1^n B(\epsilon, z_j), say x\in B(\epsilon, z_1) and y\in B(\epsilon, z_2), then

\rho(x, y)\le\rho(x, z_1)+\rho(z_1, z_2)+\rho(z_2, y)\le 2\epsilon+\max\{\rho(z_j, z_k): 1\le j, k\le n \}.

If E is totally bounded, so is \bar E, for it is easily seen that if E\subset \cup_1^n B(\epsilon, z_j), then \bar E\subset \cup_1^n B(2\epsilon, z_j).

Theorem. If E is a subset of the metric space (X, \rho), the following are equivalent:

1) E is complete and totally bounded.

2) (The Bolzano-Weierstrass Property) Every sequence in E has a subsequence that converges to a point in E.

3) (The Heine-Borel Property) If \{V_\alpha\}_{\alpha\in A} is a cover of E by open sets, there is a finite set F\subset A such that \{V_\alpha\}_{\alpha\in A} covers E.

Proof. 1) \Rightarrow 2): Suppose that 1) holds and \{x_n\} is a sequence in E. E can be covered by finitely many balls of radius 2^{-1}, and at least one of them must contain x_n for finitely many many n: say, x_n\in B_1 for n\in N_1. E\cap B_1 can be covered by finitely many balls of radius 2^{-2}, and at least one of them must contain x_n for infinitely many n\in N_1: say x_n\in B_2 for n\in N_2. Continuing inductively, we obtain a sequence x_n\in B_j for n\in N_j. Pick n_1\in N_1, n_2\in N_2, … such that n_1<n_2<.... Then \{x_{n_j}\} is a Cauchy sequence, for \rho(x_{n_j}, x_{n_k})<2^{1-j} if $k>j$, and since E is complete, it has a limit in E.

2) \Rightarrow 1): If E is not complete, there is a Cauchy sequence \{x_n\} in E with no limit in E. No subsequence of \{x_n\} can converge in E, for otherwise the whole sequence would converge to the same limit. On the other hand, if E is not totally bounded, let \epsilon>0 be such that E cannot be covered by finitely many balls of radius \epsilon. Choose x_n\in E inductively as follows. Begin with any x_1\in E and having chosen x_1, ..., x_n, pick x_{n+1}\in E\setminus \cup_1^n B(\epsilon, x_j). Then \rho(x_n, x_m)>\epsilon for all n, m, so \{x_n\} has no convergent subsequence.

1) + 2) \Rightarrow 3): If suffices to show that if 2) holds and \{V_\alpha\}_{\alpha\in A} is a cover of E by open sets, \exists\epsilon>0 such that every ball of radius \epsilon that intersects E is contained in some V_\alpha, for E can be covered by finitely many such balls by 1). Suppose to the contrary that for each n\in\mathbb N, $\exists$ a ball B_n of radius 2^{-n} such that B_n\cap E\not=\emptyset and B_n is contained in no V_\alpha. Pick x_n\in B_n\cap E; by passing to a subsequence we may assume that \{x_n\} converges to some x\in E. We have x\in V_\alpha for some \alpha, and since V_\alpha is open, \exists\epsilon>0 such that B(\epsilon, x)\subset V_\alpha. But if n is large enough so that \rho(x_n, x)<\epsilon/3 and 2^{-n}<\epsilon/3, then B_n\subset B(\epsilon, x)\subset V_\alpha, contradicting the assumption on B_n.

3) \Rightarrow 2): If \{x_n\} is a sequence in E with no convergent subsequence, for each x\in E there is a ball B_x centered at x that contains x_n for only finitely many n. Then \{B_x\}_{x\in E} is a cover of E by open sets with no finite sub-cover. \Box

A set E can possesses the properties 1)-3) is called compact. Every compact set is closed and bounded, and the converse is false.

Proposition. Every closed and bounded subset of \mathbb R^n is compact.

Proof. Since closed subsets of \mathbb R^n are complete, it suffices to show that bounded subsets of \mathbb R^n are totally bounded. Since every bounded set is contained in some cube

Q=[-R, R]^n=\{x\in\mathbb R^n: \max(|x_1|,..., |x_n|)<R\},

it is enough to show that Q is totally bounded. Given \epsilon>0, pick an integer k>R\sqrt{n}/\epsilon, and express Q as the union of k^n congruent subcubes by dividing the interval [-R, R] into k equal pieces. The side length of these subcubes is 2R/k and hence their diameter is \sqrt{n}(2R/k)<2\epsilon, so they are contained in the balls of radius \epsilon about their centers. \Box

Two metrics \rho_1 and \rho_2 on a set X are called equivalent if

C\rho_1\le\rho_2\le C'\rho_1 for some C, C'>0.

Equivalent metrics define the same open, closed and compact sets, the same convergent and Cauchy sequence, and the same continuous and uniformly continuous mappings. Consequently, most results concerning metric spaces depend not on the particular metric chosen but only on its equivalent class.

“As you simplify your life, the laws of the universe will be simpler; solitude will not be solitude, poverty will not be poverty, nor weakness, weakness.” ~ Henry David Thoreau

References:

[1] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications, 2ed, page 15-16.

[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf.

Definition. A metric on a set X is a function: \rho: X\times X\to[0, \infty) such that

1) \rho(x, y)=0 iff x=y;

2) \rho(x, y)=\rho(y, x) for all x, y\in X;

3) \rho(x, x)\le\rho(x, y)+\rho(y, z) for all x, y, z\in X.

A set equipped with a metric is called a metric space.

 

Examples. 1)  The Euclidean distance \rho(x, y)=|x-y| is a metric on \mathbb R^n.

2) \rho_1(x, y)=\int_0^1|f(x)-g(x)|dx and \rho_\infty(f, g)=\sup_{0\le x\le 1}|f(x)-g(x)| are metrics on the space of continuous functions on [0, 1].

3) If \rho is a metric on X and A\subset X, then \rho|(A\times A) is a metric on A.

4) If (X_1, \rho_1) and (X_2, \rho_2) are metric spaces, the product metric \rho on X_1\times X_2 is given by

\rho((x_1, x_2),(y_1, y_2))=\max(\rho_1(x_1, y_1), \rho_2(x_2, y_2)).

5) Some other metrics used on X_1\times X_2:

\rho_1(x_1, y_1)+\rho_2(x_2, y_2), [\rho_1(x_1, y_1)^2+\rho_2(x_2, y_2)^2]^{1/2}.

Definition. Let (X, \rho) be a metric space. If x\in X and r>0, the (open) ball of radius r about x is B(r, x)=\{y\in X: \rho(x, y)<r\}.

A set E\subset X is open if for every x\in E, \exists r>0 such that B(r, x)\subset E, and closed if the complement is open.

Remark. X and \emptyset are both open and closed. The union of any family of open sets is open, and the intersection of any family of closed sets is closed. The intersection (resp. union) of any finite family of open (resp. closed) sets is open (resp. closed). Indeed, if U_1, U_2, ..., U_n are open and x\in\cap_1^n U_j, for each j, $\exists r_j>0$ such that B(r_j, x)\subset U_j, and then B(r, x)\subset\cap_1^n U_j where r=\min(r_1, ..., r_n), so \cap_1^n U_j is open.

Definition. If E\subset X, then the interior of E, denoted by E the union of all open sets U\subset E is the largest open set contained in E, which is called the interior of E and is denoted by E^0. The intersection of all closed sets F\supset E is the smallest closed set containing E; it is called the closure of E and is denoted by \bar{E}. E is said to be dense in X if \bar{E}=X, and nowhere dense if \bar{E} has empty interior. X is called separable if it has a countable dense subset. (For example, \mathbb Q^n is a countable dense subset of \mathbb R^n.) A sequence \{x_n\} in X converges to x\in X (symbolically: x_n\to x or \lim x_n=x) if \lim_{n\to\infty}\rho(x_n, x)=0.

Proposition. If X is a metric space, E\subset X, and x\in X, the following are equivalent:

1) x\in\bar{E}.

2) B(r, x)\cap E\not=\emptyset for all r>0.

3) There is a sequence \{x_n\} in E that converges to x.

Proof. If B(r, x)\cap E=\emptyset, then B(r, x)^c is a closed set containing E but not x, so x\not\in\bar{E}. Conversely, if $x\not\in\bar{E}$, since (\bar{E})^c is open $\exists r>0$ such that B(r, x)\subset(\bar E)^c\subset E^c. Thus 1) is equivalent to 2). If 2) holds, for each n\in\mathbb N, $\exists x_n\in B(n^{-1}, x)\cap E$, so that x_n\to x. On the other hand, if B(r, x)\cap E=\emptyset, then \rho(y, x)\ge r for all y\in E, so no sequence of E can converge to x. Thus 2) is equivalent to 3). \Box

Remark. If (X_1, \rho_1) and (X_2, \rho_2) are metric spaces, a map f: X_1\to X_2 is called continuous at x\in X_1 if for every \epsilon>0, \exists \delta>0 such that \rho_2(f(y), f(x))<\epsilon whenever \rho_1(x, y)<\delta. In other words, f^{-1}(B(\epsilon, f(x)))\supset B(\delta, x). The map f is called continuous if it is continuous at each x\in X_1 and uniformly continuous if the \delta in the definition of continuity can be chosen independent of x.

Proposition. f: X_1\to X_2 is continuous iff f^{-1}(U) is open in X_1 for every open U\subset X_2.

Proof. If the latter condition holds, then for every x\in X_1 and \epsilon>0, the set f^{-1}(B(\epsilon, f(x))) is open and contains x, so it contains some ball about x; this means that f is continuous at x. Conversely, suppose that f is continuous and U is open in X_2. For each y\in U, \exists \epsilon_y>0 such that B(\epsilon_y, y)\subset U, and for each x\in f^{-1}(\{y\}), \exists\delta_x such that B(\delta_x, x)\subset f^{-1}(B(\epsilon_y, y))\subset f^{-1}(U). Thus f^{-1}(U)=\cup_{x\in f^{-1}}B(\delta_x, x) is open. $\Box$

“I understand now that the vulnerability I’ve always felt is the greatest strength a person can have. You can’t experience life without feeling life. What I’ve learned is that being vulnerable to somebody you love is not a weakness, it is strength.” ~ Elisabeth Shue

References:

[1] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications, 2ed, page 13-14.

[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf.

Extended Real Number System: \bar{\mathbb R}=\mathbb R\cup\{-\infty, \infty\}, and to extend the usual ordering on \mathbb R by declaring that -\infty<x<\infty for all x\in\mathbb R. The completeness of \mathbb R can be stated as: Every subset of A of \bar{\mathbb R} has a least upper bound, or supremum, and a greatest lower bound, or infimum, which are denoted by sup A and inf A. If A=\{a_1, a_2, ..., a_n\}, we also write:

\max (a_1, ..., a_n)=\sup A, \min(a_1, ..., a_2)=\inf A.

From completeness it follows that every sequence \{x_n\} in \bar{\mathbb R} has a limit superior and a limit inferior:

\lim\sup x_n=\inf_{k\ge 1}(\sup_{n\ge k}x_n), \lim\inf x_n=\sup_{k\ge 1}(\inf_{n\ge k} x_n)

The sequence \{x_n\} converges (in \mathbb R) iff these two numbers are equal (and finite), in which case its limit is their common value. One can also define \lim\sup and \lim\inf for functions f: \mathbb R\to\bar{\mathbb R}, e.g. \lim\sup_{x\to a} f(x)=\inf_{\delta>0}(\sup_{0<|x-a|<\delta}f(x)).

The arithmetical operations on \mathbb R can be partially extended to \bar{\mathbb R}:

x\pm\infty=\pm\infty (x\in\mathbb R), \infty+\infty=\infty, -\infty-\infty=-\infty,

x\dot(\pm\infty)=\pm\infty(x>0), x\dot(\pm\infty)=\mp\infty(x<0), 0\dot(\pm\infty)=0.

We employ the following notation for intervals in \bar{\mathbb R}: If -\infty\le a<b\le \infty,

(a, b)=\{x: a<x<b\}, [a, b]=\{x: a\le x\le b\}, (a, b]=\{x: a<x\le b\}, [a, b)=\{x: a\le x<b\}.

If X is an arbitrary set and f: X\to[0, \infty], we define \sum_{x\in X}f(x) to be the supremum of its finite partial sums:

\sum_{x\in X}f(x)=\sup\{\sum_{x\in F}f(x): F\subset X, F   is finite $latex \}$.

Proposition. Given f: X\to[0, \infty], let A=\{x: f(x)>0\}. If A is uncountable, then \sum_{x\in X}f(x)=\infty. If A is countably infinite, then \sum_{x\in X}f(x)=\sum_1^\infty f(g(n)) where g:\mathbb N\to A is any bijection and the sum on the right is an ordinary infinite series.

Proof. We have A=\cup_1^\infty A_n where A_n=\{x: f(x)>\frac 1 n\}. If A is uncountable, then some A_n must be uncountable, and \sum_{x\in F}f(x)>card(F)/n for F a finite subset of A_n. If follows that \sum_{x\in X}f(x)=\infty. If A is countably infinite, g: \mathbb N\to A is a bijection, and B_N=g(\{1, ..., N\}), then every finite subset F of A is contained in some B_N. Therefore,

\sum_{x\in F}f(x)\le \sum_1^Nf(g(n))\le\sum_{x\in X}f(x).

Taking the supremum over N, then

\sum_{x\in F}f(x)\le\sum_1^\infty f(g(n))\le\sum_{x\in X}f(x),

and then taking the supremum over F, we obtain the desired result. \Box

Some terminology concerning (extended) real-valued functions: A relation between numbers that is applied to functions is understood to hold pointwise. Thus f\le g means that f(x)\le g(x) for every x, and \max(f, g) is the function whose value at x is \max(f(x), g(x)). If X\subset\bar{\mathbb R} and f: X\to\bar{\mathbb R}, f is called increasing if f(x)\le f(y) whenever $x\le y$ and strictly increasing if f(x)<f(y) whenever x<y; similarly for decreasing. A function is either increasing or decreasing is called monotone.

If f:\mathbb R\to\mathbb R is an increasing function, then f has right- and left-hand limits at each point:

f(a+)=\lim_{x\searrow a}f(x)=\inf_{x>a}f(x), f(a-)=\lim_{x\nearrow a}f(x)=\inf_{x<a}f(x).

f is called right continuous if f(a)=f(a+) for all a\in\mathbb R and left continuous if f(a)=f(a-) for all a\in\mathbb R.

For points x\in\mathbb R or $\mathbb C$, |x| denotes the ordinary absolute value or modulus of x, |a+ib|=\sqrt{a^2+b^2}. For points x\in\mathbb R^n or \mathbb C^n, |x| denotes the Euclidean norm:

|x|=[\sum_1^n|x_j|^2]^{\frac 1 2}.

We recall that a set U\subset\mathbb R is open if for every x\in U, U includes an interval centered at x.

Proposition. Every open set in \mathbb R is countable disjoint union of open intervals.

Proof. If U is open, for each x\in U consider the collection \mathcal J_x of all open intervals I such that x\in I\subset U. It is easy to check that the union of any family of open intervals containing a point in common is again an open interval, and hence \mathcal J_x=\cup_{I\in\mathcal J_x} is an open interval. It is the largest element of \mathcal J_x. If $x, y\in U$ then either J_x=J_y or J_x\cap J_y=\emptyset, for otherwise J_x\cup J_y would be a larger open interval that J_x in \mathcal J_x. Thus if K=\{J_x: x\in U\}, the (distinct) members of K are disjoint, and U=\cup_{J\in K}\mathcal J. For each J\in K, pick a rational number f(J)\in J. The map f: K\to\mathbb Q thus defined is injective, for if J\not=J' then J\cap J'=\emptyset; therefore K is countable. \Box

“Nobody needs a smile so much as the one that has none to give. So get used to smiling heart-warming smiles, and you will spread sunshine in a sometimes dreary world.” ~ Lawrence G. Lovasik

References:

[1] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications, 2ed, page 10-12.

[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf.