# Solutions to System of Sets:

Reference: Introductory Real Analysis, Kolmogorov and Fomin. Dover Publications. Translated and edited by Richard A. Silverman:

Problem 1:

Let X be an uncountable set, and let $\mathscr{R}$ be the ring consisting of all finite subsets of X and their complements. Is $\mathscr{R}$ a $\sigma$-ring?

Solution 1:

Recall the definition: A ring of sets is called $\sigma$-ring if it contains the union $S= \bigcup_{n=1}^{\infty}A_{n}$ whenever it contains the sets $A_{1}, A_{2}, \ldots, A_{n}, \ldots$.

There are countably many finite subsets of X (given uncountable set) and their complements (also especially) so that the union of all these is the whole set X. Hence, X is a $\sigma$-ring as it is closed under countably many set unions. QED.

Problem 2:

Are open intervals Borel sets?

Solution 2:

Recall the following:

(1) Borel sets or B-sets are the subsets of the real line belonging to the minimal B-algebra  generated by the set of all closed intervals $[\alpha, \beta]$.

Problem 3:But a B-algebra is also a ring and is closed under differences/complements. Open intervals are complements of closed intervals. And, they belong hence to B-algebra. Note we still have to answer the question whether open sets are Borel sets and so we have to check if they are contained in a minimal B-algebra. As per the following theorem: Given any non-empty system of sets $\mathscr{S}$, there is a unique irreducible (minimal) B-algebra $\mathscr{B}(\mathscr{P})$ generated by the system $\mathscr{S}$ or the Borel closure of $\mathscr{P}$. So, yes indeed open sets are Borel sets. QED.

Problem 3A:

Let $y=f(x)$ be a function defined on a set M and taking values in a set N. Let $\mathscr{M}$ be a system of subsets of M, and let $f(\mathscr{M})$ denote the system of all images $f(A)$ of sets $A \in \mathscr{M}$. Moreover, let $\mathscr{N}$ be a system of subsets of N, and let $f^{-1}(\mathscr{N})$ denote the system of all preimages $f^{-1}(B)$ of sets $B \in \mathscr{N}$. Prove that:

i) If $\mathscr{N}$ is a ring, so is $f^{-1}(\mathscr{N})$.

ii) If $\mathscr{N}$ is an algebra, so is $f^{-1}(\mathscr{N})$

iii) If $\mathscr{N}$ is a B-algebra, so is $f^{-1}(\mathscr{N})$

iv) $\mathscr{R}(f^{-1}(\mathscr{N})) = f^{-1}(\mathscr{R}(\mathscr{N}))$ where $\mathscr{R}$ stands for a ring.

v) $\mathscr{B}(f^{-1}(\mathscr{N})) = f^{-1}(\mathscr{B}(\mathscr{N}))$ where $\mathscr{B}$ is irreducible or minimum Borel algebra generated by a non-empty system of sets $\mathscr{S}$.

Problem 3B:

Prove the following:

i) If $\mathscr{M}$ is a ring, so is $f(\mathscr{M})$.

ii) If $\mathscr{M}$ is an algebra, so is $f(\mathscr{M})$.

iii) If $\mathscr{M}$ is Borel-algebra, so is $f(\mathscr{M})$.

iv) $\mathscr{R}(f(\mathscr{M}))=f(\mathscr{R}(\mathscr{M}))$

v) $\mathscr{B}(f(M))=f(\mathscr{B}(\mathscr{M}))$ where $\mathscr{B}$ is irreducible minimum Borel algebra generated by a non-empty system of sets $\mathscr{S}$.

Solution 3A:

Part 1: Given mapping $f: M \rightarrow N$, that is, $y=f(x)$, Let $Y_{1}, Y_{2}, Y_{3}, \ldots$ be subsets of N and let $X_{1}, X_{2}, X_{3}, \ldots$ be subsets of M. Then, as it is given that $\mathscr{N}$ is a ring then :

$Y_{1} \bigcap Y_{2} \in \mathscr{N}$

$Y_{1}\bigcup Y_{2} \in \mathscr{N}$

$Y_{1}-Y_{2} \in \mathscr{N}$

$Y_{1} \triangle Y_{2} = (Y_{1}-Y_{2}) \bigcup (Y_{2}-Y_{1}) \in \mathscr{N}$

The above implies:

$f^{-1}(Y_{1}\bigcap Y_{2}) \in f^{-1}(\mathscr{N})$, that is, $f^{-1}(Y_{1}) \bigcap f^{-1}(Y_{2}) \in f^{-1}(\mathscr{N})$, that is, $X_{1} \bigcap X_{2} \in \mathscr{M}$.

Also, $Y_{1} \bigcup Y_{2} \in \mathscr{N}$ so that $f^{-1}(Y_{1} \bigcup Y_{2}) \in f^{-1}(\mathscr{N})$, that is, $f^{-1}(Y_{1}) \bigcup f^{-1}(Y_{2}) \in f^{-1}(\mathscr{N})$, that is, we conclude $X_{1} \bigcup X_{2} \in \mathscr{M}$.

Also, $Y_{1}-Y_{2} \in \mathscr{N}$ as $\mathscr{N}$ is a ring; so that $f^{-1}(Y_{1}-Y_{2}) \in f^{-1}(\mathscr{N})$ so that for some $X_{0}$, which is $f^{-1}(Y_{1}-Y_{0}) \longrightarrow f^{-1}(Y_{1}) - f^{-1}(Y_{0}) \in \mathscr{M}$

So, we have shown that the system of sets $\mathscr{M}$ is closed under set union, set intersection, set difference, and hence, also set symmetric difference. Hence, it is is a ring. QED.

Part ii:

We have already shown that $f^{-1}(\mathscr{N})$ is a ring, now $\mathscr{N}$ is also an algebra meaning a ring of sets with a unit element. Let it contain a unit E $\in \mathscr{N}$ such that if $Y_{0}$ is any set belonging to $\mathscr{N}$, then $Y_{0} \bigcap E = Y_{0}$. so that $f^{-1}(Y_{0} \bigcap E) = f^{-1}(Y_{0})$, hence, $f^{-1}(Y_{0}) \bigcap f^{-1}(E) = f^{-1}(Y_{0})$, which in turn implies that $f^{-1}(E)$ is a unit of $f^{-1}(\mathscr{N})$. Hence, $f^{-1}(\mathscr{N})$ is a ring of sets with a unit element, or in other words, an algebra of sets.

Part iii:

To prove that: if $\mathscr{N}$ is a Borel algebra, so is $f^{-1}(\mathscr{N})$. From parts i and ii above, $f^{-1}(\mathscr{N})$ is a ring with a unit or in other words, $f^{-1}(\mathscr{N})$ is an algebra. Moreover, if it contains $\bigcup_{k=1}^{\infty}Y_{k}$ whenever it contains the sets $Y_{1}, Y_{2}, Y_{3}, \ldots, Y_{n}, \ldots$ all of which are members of $\mathscr{N}$.

But for an arbitrary (finite or infinite) collection of sets:

$f^{-1}(\bigcup_{\alpha}A_{\alpha}) = \bigcup_{\alpha}f^{-1}(A_{\alpha})$

Now, $\bigcup_{k=1}^{\infty}Y_{k} \in \mathscr{N}$

hence $f^{-1}(\bigcup_{k=1}^{\infty}Y_{k}) \in f^{-1}(\mathscr{N})$

Consequently, $\bigcup_{k=1}^{\infty}f^{-1}(Y_{k}) \in f^{-1}(\mathscr{N})$, which in turn implies that $\mathscr{N}$ is a Borel algebra also. QED.

Part iv and part v:

Using parts i and iii above, these can be very easily proved.

Solutions 3b:

i) Prove: If $\mathscr{M}$ is a ring, so is $f(\mathscr{M})$. Note that $f: M \rightarrow N$, $y=f(x)$. Proof (i): As $\mathscr{M}$ is a system of subsets of M. and it is a ring, so if $A_{1} \in \mathscr{M}$, and $A_{2} \in \mathscr{M}$, it implies that $A_{1} \bigcup A_{2} \in \mathscr{M}$; $A_{1} \bigcap A_{2} \in \mathscr{M}$; $(A_{1}-A_{2}) \in \mathscr{M}$. We know that $f(A_{1}\bigcup A_{2}) = f(A_{1}) \bigcup f(A_{2}) \in f(\mathscr{M})$ and $f(A_{1} \bigcap A_{2}) \subset f(A_{1}) \bigcap f(A_{2}) \in f(\mathscr{M})$. And, quite obviously, $f(A_{1}-A_{2}) = f(A_{1}) - f(A_{2}) \in f(\mathscr{M})$ so that it is true that if $\mathscr{M}$ is a ring, then $f(\mathscr{M})$ is also a ring.

ii) Check if it is true or false: if $\mathscr{M}$ is an algebra, so is $f(\mathscr{M})$. Argument: As $\mathscr{M}$ is an algebra, it is already a ring. But additionally, $\mathscr{M}$ contains an element E such that $A_{1} \bigcap E= A_{1}$ (whenever $A_{1} \in \mathscr{M}$ but $f(A_{1} \bigcap E) \subset f(A_{1}) \bigcap f(E) \in f(\mathscr{M})$ but it need not be true that $f(E)$ is a unit element of $f(\mathscr{M})$. So, we can say that in case $\mathscr{M}$ is an algebra, then $f(\mathscr{M})$ may or may not be an algebra. QED.

iii) Check if it is true or false: If $\mathscr{M}$ is a Borel algebra, then so also $f(\mathscr{M})$ is also a Borel algebra. Argument: As in previous case, $f(\mathscr{M})$ may not have a unit element. So, $f(\mathscr{M})$ need not be a Borel algebra. QED.

iv) $\mathscr{R}(f(\mathscr{M})) = f(\mathscr{R}(\mathscr{M}))$. Check if this is true or false. Argument: Let $f(A_{1}) \in f(\mathscr{M})$, $f(A_{2}) \in \mathscr{M}$. By definition of a ring, $f(A_{1}) \bigcup f(A_{2}) \in f(\mathscr{M})$, $f(A_{1}) \bigcap f(A_{2}) \in f(\mathscr{M})$, $f(A_{1}) - f(A_{2}) \in f(\mathscr{M})$, hence we get the following: $f(A_{1} \bigcup A_{2}) \subset f(\mathscr{M})$; $f(A_{1} \bigcap A_{2}) \subset f(A_{1}) \bigcap f(A_{2}) \in f(\mathscr{M})$ and $f(A_{1}-A_{2}) = f(A_{1}) - f(A_{2}) \in f(\mathscr{M})$. This in turn means that $A_{1} \bigcup A_{2} \in \mathscr{M}$, $A_{1} \bigcap A_{2} \in \mathscr{M}$ and $A_{1} - A_{2} \in \mathscr{M}$. Hence, $LHS \subset RHS$. Similarly, we can show that $RHS \subset LHS$. QED.

v) $\mathscr{B}(f(\mathscr(M))) = f(\mathscr{B}(\mathscr{M}))$. Check if this is true or false. (We will discuss this later; meanwhile, if you wish, please try as homework and let me know).

Cheers,

Nalin Pithwa.

# Introductory Real Analysis: Exercise 3 solutions: related to set theory

Problem 1:

Exhibit both a partial ordering and a simple ordering on the set of complex numbers.

Solution I:

Recall the definition of a partial ordering: A binary relation R on a set M is said to be a partial ordering (and the set M itself is said to be partially ordered) if:

(i) R is reflexive (aRa for every $a \in M$) (ii) R is transitive (aRb and bRc together imply aRc) (iii) aRb and bRa together imply $a=b$ (anti symmetric).

Recall the definition of a simple ordering or totally ordered or (just) ordered set: a set M is said to be ordered if it is a partially ordered set and if, given any two distinct elements $a, b \in M$, either $a < b$ or $b < a$.

Let us consider the following relation R on the set of complex numbers, C:

consider any two elements $z_{1}, z_{2} \in C$ such that $z_{1}=x_{1}+i y_{1}$ and $z_{2} = x_{2}=iy_{2}$. We define a relation $z_{1}Rz_{2}$ if and only if $x_{1} \leq x_{2}$ and $y_{1} \leq y_{2}$. Clearly, this is both a partial ordering on C as well as total ordering on C.

Now consider the following relation K on the set of complex numbers:

We define the relation K as: $z_{1}Kz_{2}$ if and only if $\frac{x_{1}}{y_{1}} = \frac{x_{2}}{y_{2}}$ where $x_{1}, y_{1}, x_{2}, y_{2} \in \Re$. Clearly, if any one of $y_{1}$ or $y_{2}$ is zero, then the complex numbers $z_{1}$ and $z_{2}$ are non-comparable. So this could be a partial ordering but not a total ordering on the set of complex numbers.

Problem 2:

What is the minimal element of the set of all subsets of a given set X partially ordered by set inclusion. What is the maximal element?

Solution 2:

Recall the definition: An element “a” of a partially ordered set is said to be maximal if $aRb$ implies $b=a$ and minimal if $bRa$ implies b=a.

Note that in the above definition, element “a” is our given/chosen element to be compared with other elements of the set. So, clearly, if the partial ordering is set inclusion, the minimal element is the null set $\phi$ and the maximal element is the given set X itself.

Problem 3:

A partially ordered set M is said to be a directed set if, given any two elements $a, b \in M$, there is an element $c \in M$ such that $a \leq c$ and $b \leq c$. Are the following partially ordered sets directed sets also ?

PS: in the above we use the notation $aRb$ or equivalently, $a \leq b$ to mean one and the same thing.

Question 3a:  Any set M can be trivially partially ordered by setting $a \leq b$ if and only if $a=b$.

Answer 3a: Clearly, this is a trivial directed set.

Question 3b: Let M be the set of all continuous functions $f, g, \ldots$ defined in a closed interval $[\alpha, \beta]$. Then, we get a partial ordering by setting $f \leq g$ if and only if $f(t) \leq g(t)$ for every $t \in [\alpha, \beta]$. Is this also a directed set ?

Answer 3b: We need to choose two arbitrary elements say $f_{1}$ and $f_{2}$ of the given set of continuous functions on $[\alpha, \beta]$. Our desired “element” could be $f_{3}= |f_{1}(t)|+|f_{2}(t)|$ again defined on $[\alpha, \beta]$. Then, the given set becomes a directed set.

Note that the function $y=f(x) = |x|$ is continuous at zero also (but not differentiable at zero).

Question 3c:

Set inclusion.

Answer 3: Clearly, given any two arbitrary subsets, both are contained always in the given big set M or X. So, this is again a directed set.

Question 3d: The set of all integers greater than 1 is partially ordered if $a \leq b$ means that “b is divisble by a.”

Answer 3: So let us consider two arbitrary positive integers, both greater than 1, call them a and b. We want to know if there exist a positive integer, also greater than 1, call it c such that $a \leq c$ and $b \leq c$? That is, “c is divisible by a” and “c is divisible by b”. Clearly, c can be least common multiple of a and b. So, yes, this is also a directed set.

Problem 4:

By the greatest lower bound of two elements a and b of a partially ordered set M, we mean an element $c \in M$ such that $c \leq a$ and $c \leq b$ and there is no element $d \in M$ such that $c < d \leq a$, $d \leq b$. Similarly, by the least upper bound of a and b, we mean an element $c \in M$ such that $a \leq c$, $b \leq c$, and there is no element $d \in M$ such that $a \leq d < c$ and $b \leq d$. By a lattice is meant a partially ordered set any two elements of which have both a greatest lower bound and a least upper bound. Prove that the set of all subsets of a given set M, partially ordered by set inclusion, is a lattice. What is the set theoretic meaning of the greatest lower bound and least upper bound of two elements of this set ?

Solution 4:

It can be easily checked that the null set is the greatest lower bound and the set M itself if the least upper bound. (PS: these are the minimal and maximal elements of this set M respectively.)

Problem 5:

Prove that an order-preserving mapping of one ordered set onto another is automatically an isomorphism.

Solution 5:

By definition.

Problem 6:

Prove that ordered sums and products of ordered sets are associative, that is, prove that if $M_{1}, M_{2}$ and $M_{3}$ are ordered sets, then

$(M_{1}+M_{2})+M_{3}=M_{1}+(M_{2}+M_{3})$

$(M_{1}.M_{2}).M_{3} = M_{1}.(M_{2}.M_{3})$

PS: comment: this allows us to drop the parentheses in writing ordered sums and products.

where the operations are as defined below:

Let $M_{1}$ and $M_{2}$ be two ordered sets of type $\theta_{1}$ and $\theta_{2}$ respectively. Then, we can introduce an ordering in the union $M_{1} \bigcup M_{2}$ of the two sets by assuming that: (i) a and b have the same ordering as in $M_{1}$ if $a, b \in M_{1}$ (ii) a and b have the same orderiing as in $M_{2}$ if $a, b \in M_{2}$ (iii) $a \leq b$ if $a \in M_{1}$ and $b \in M_{2}$.

In this case/example, the ordered sum or union of three ordered sets $M_{1}, M_{2}, M_{3}$ would mean that any two elements a, b would have the same ordering if $a, b \in M_{1}$, or $a, b \in M_{2}$ or $a,b \in M_{3}$. Also, comparing with ordered sum of two ordered sets, we can say that $a \leq b$ if and only if $a \in M_{1}, b \in M_{2}$ or $a \in M_{1}, b \in M_{3}$, or $a \in M_{2}, b \in M_{3}$. In such a case, the ordered sum is also associative.

The operation of ordered product of two ordered sets is defined as follows: $M_{1}. M_{2}$ is the set of all pairs $(a,b)$ where $a \in M_{1}$ and $b \in M_{2}$ ordered in such a way that (i) $(a_{1}, b_{1}) < (a_{2}, b_{2})$ if $b_{1} < b_{2}$ for arbitrary $a_{1}, a_{2}$, and (ii) $(a_{1},b) < (a_{2}, b)$ if $a_{1} < a_{2}$.

So, if we have three ordered sets $M_{1}, M_{2}, M_{3}$, we can define their ordered product $M_{1}.M_{2}.M_{3}$ as consisting of all ordered triples such that (i) $(a_{1}, b_{1}, c_{1}) < (a_{2}, b_{2}, c_{2}) < (a_{3}, b_{3}, c_{3})$ if and only if $b_{1} and $c_{1} < c_{2} < c_{3}$ for arbitrary $a_{1}, a_{2}, a_{3}$, and (ii) $(a_{1}, b, c) < (a_{2}, b, c) < (a_{3}, b, c)$ if $a_{1}; $(a, b_{1}, c) < (a, b_{2}, c) < (a, b_{3}, c)$ if $b_{1}; $(a,b, c_{1})< (a,b,c_{2}) < (a,b, c_{3})$ of $c_{1} < c_{2} < c_{3}$. In such a case, the product is well-defined and is also associative. (any comments ??)

Problem 7:

Construct well-ordered sets with ordinals

$\omega + n$, $\omega + \omega$, $\omega + \omega + n$, $\omega + \omega + \omega$, $\ldots$

Show that the sets are all countable.

Solution 7:

$\omega + n$: $\{ 1,2,3,\ldots, a_{1}, a_{2}, \ldots, a_{n}\}$. This is countable because there can be bijection from the set $Z^{+}$ to the given set: $1 \rightarrow a_{1}$, $2 \rightarrow a_{2}$, $\ldots$, $n \rightarrow a_{n}$, $n+1 \rightarrow 1$, $n+2 \rightarrow 2$, $\ldots$

$\omega + \omega$: $\{1,2,3, \ldots, 1,2,3, \ldots \}$, this is also countable as it can be put in one-to-one correspondence with $Z^{+}$.

$\omega + \omega + n$; $\{ 1,2, 3, \ldots, 1, 2, 3, \ldots, a_{1}, a_{2}, a_{3}, \ldots, a_{n}\}$. This is also countable in the same manner as the first example.

$\omega + \omega + \omega$: $\{ 1,2, 3, \ldots, 1,2, 3, \ldots, 1,2,3, \ldots\}$: this can be put in one-to-one correspondence with $Z^{+}$

Problem 8:

Construct well-ordered sets with ordinals

$\omega.n$, $\omega^{2}$, $\omega^{2}.n$, $\omega^{3}$, $\ldots$.

Show that the sets are all countable.

Solution 8:

First let us recall the definition: An ordered set M is said to be well-ordered if every non empty subset A of M has a smallest (or, first) element, that is, an element $\mu$ such that $\mu < a$ for every $a \in A$.

Ans 1: $\omega.n$ is set : $M= \{(1,a_{1}), (2,a_{2}), (3, a_{3}), \ldots, (n, a_{n}), (n+1, a_{1}), (n+2, a_{2}), \ldots \}$. This set is ordered clearly by the definition of ordered product of two ordered sets; and this is well-ordered if we define the first element to be $(1, a_{1})$.

Ans 2: $\omega^{2} = \omega. \omega$: this set can be constructed as $M= \{ (1,1), (1,2),(1,3), \ldots, (2,1), (2,2), (2,3), \ldots, \}$ and we can define the first element as $(1,1)$ so that it becomes well-ordered under the usual definition of product of two ordered sets.

Ans 3: $\omega^{2}.n = \omega. \omega. n$: this set can be constructed as follows as an ordered product of three ordered sets: $M = \{ (1,1,a_{1}), (1,1,a_{2}), (1,1,a_{3}), \ldots, (1,1,a_{n}), (1,2,a_{1}), (1,2,a_{2}), (1,2,a_{3}), \ldots, (1, 2, a_{n}), \ldots\}$. We see that this is also well-ordered if we define the first element to be $(1,1,a_{1})$ and “order or list or count” them as shown. (any comments ? )

Ans 4: $\omega^{3}= \omega.\omega.\omega$: this can be well-ordered as above with clearly the first element to be $(1,1,1)$. (any comments?)

PS: the explicit listing shows that all the above sets are clearly countable.

More later,

Cheers,

Nalin Pithwa

# Metric Spaces: Tutorial problems

Reference: Introductory Real Analysis by Kolmogorov and Fomin.

Reference: Analysis by Walter Rudin.

Reference: Introduction to Analysis by Rosenlicht.

Reference: Topology by Hocking and Young.

The problems proposed are as follows:

1. Given a metric space $(X,\rho)$, prove that (1a) $|\rho(x,z)-\rho(y,u)| \leq \rho(x,y) + \rho(z,u)$ where $x,y,z,u \in X$; (1b) $|\rho(x,z) -\rho(y,z)| \leq \rho(x,y)$ where $x,y,z \in X$.
2. Verify that $(\Sigma_{k=1}^{n}a_{k}b_{k})^{2} = \Sigma_{k=1}^{n}a_{k}^{2} \times \Sigma_{k=1}^{n}b_{k}^{2} - \frac{1}{2}\Sigma_{i=1}^{n}\Sigma_{j=1}^{n}(a_{i}b_{j}-a_{j}b_{i})^{2}$. Deduce the Cauchy-Schwarz inequality from the above identity. (refer second last blog from here). For convenience, we reproduce it here again: consider the set of all ordered n-tuples such that $x=(x_{1}, x_{2}, \ldots, x_{n})$ and $y=(y_{1}, y_{2}, \ldots, y_{n})$ and $z=(z_{1}, z_{2}, \ldots, z_{n})$ and let $a_{k}=x_{k}-y_{k}$, $b_{k}=y_{k}-z_{k}$ where $k=1,2, \ldots, n$: then Cauchy Schwarz inequality tells us that : $(\Sigma_{k=1}^{n}a_{k}b_{k})^{2} \leq \Sigma_{k=1}^{n}a_{k}^{2}\Sigma_{k=1}^{n}b_{k}^{2}$
3. Verify that $(\int_{a}^{b}x(t)y(t)dt)^{2} = \int_{a}^{b}x^{2}(t)dt \int_{a}^{b}y^{2}(t)dt -\frac{1}{2}\int_{a}^{b}\int_{a}^{b}(x(s)y(t)-x(t)y(s))^{2}dsdt$.

Deduce Schwarz’s inequality from this identity. (refer second last blog from here). To aid the memory, we present Schwarz’s inequality below: $(\int_{a}^{b}x(t)y(t))^{2} \leq \int_{a}^{b}x^{2}(t)dt \int_{a}^{b}y^{2}(t)dt$

4. Identify the fallacy in example 10, if $p \leq 1$? (refer second last blog from here). Hint: Show that Minkowski’s inequality fails for $p \leq 1$. To help recall, we are reproducing Minkowski’s inequality below: Consider again the set of all ordered n-tuples, and let $x=(x_{1}, x_{2}, \ldots, x_{n})$, and $y=(y_{1}, y_{2}, \ldots, y_{n})$ and $z=(z_{1}, z_{2}, \ldots, z_{n})$ and again further let $a_{k}=x_{k}-y_{k}$ and $b_{k}=y_{k}-z_{k}$, where $k=1,2, \ldots, n$ then Minkowski’s inequality tells us that: $(\Sigma_{k=1}^{n}|a_{k}+b_{k}|^{p})^{\frac{1}{p}} \leq (\Sigma_{k=1}^{n}|a_{k}|^{p})^{\frac{1}{p}} + (\Sigma_{k=1}^{n}|b_{k}|^{p})^{\frac{1}{p}}$

5. Prove that the following metric : Consider two points $x=(x_{1}, x_{2}, \ldots, x_{n})$ and $y=(y_{1}, y_{2}, \ldots, y_{n})$ with the metric function: $\rho_{0}(x,y) = \max_{1 \leq k \leq n}|x_{k}-y_{k}|$

is the limiting case of the following metric: consider the set of all ordered n-tuples $x = (x_{1}, x_{2}, \ldots, x_{n})$ of real numbers with the metric function now defined by: $\rho_{p}(x,y) = (\Sigma_{k=1}^{\infty}|x_{k}-y_{k}|^{p})^{\frac{1}{p}}$

in the sense that

$\rho_{0}(x,y) = \max_{1 \leq k \leq n}|x_{k}-y_{k}| = \lim_{p \rightarrow \infty}(\Sigma_{k=1}^{\infty}|x_{k}-y_{k}|^{p})^{\frac{1}{p}}$

6. Starting from the following inequality: $ab \leq \frac{a^{p}}{p} + \frac{b^{q}}{q}$, deduce Holder’s integral inequality as given by:

$\int_{a}^{b} x(t)y(t)dt \leq (\int_{a}^{b}|x(t)|^{p}dt)^{\frac{1}{p}}(\int_{a}^{b}|y(t)|^{q})^{\frac{1}{q}}$ where $\frac{1}{p} + \frac{1}{q} =1$ valid for any function $x(t)$ and $y(t)$ such that the integrals on the right exist.

7.  Use Holder’s integral inequality to prove Minkowski’s integral inequality:

$(\int_{a}^{b}|x(t)+y(t)|^{p}dt)^{\frac{1}{p}} \leq (\int_{a}^{b}|x(t)|^{p}dt)^{\frac{1}{p}} + (\int_{a}^{b}|y(t)|^{p}dt)^{\frac{1}{p}}$

where $p \geq 1$.

8. Exhibit an isometry between the spaces $C_{[0,1]}$ and $C_{[1,2]}$.

9. Verify that the following is a metric space: all bounded infinite sequences $x=(x_{1}, x_{2}, x_{3}, \ldots)$ of elements of $\Re$, with $\rho(x,y) = lub \{ |x_{1}-y_{1}|,|x_{2}-y_{2}|,|x_{3}-y_{3}|, \ldots\}$

10. Verify that $(\Re \times \Re, \rho)$ is a metric space where $\rho((x,y),(x^{'}, y^{'})) = |y|+|y^{'}|+|x-x^{'}|$ when $x \neq x^{'}$ and is $|y-y^{'}|$ when $x=x^{'}$. Illustrate by diagrams in the plane $E^{2}$ or $R^{2}$ what the open balls of this metric space are.

11. Show that a one-to-one transformation $f: S \rightarrow T$ of a space S onto a space T is a homeomorphism if and only if both f and $f^{'}$ are continuous.

Cheers,

Nalin Pithwa

# Metric Spaces: some additional stuff

Reference: Introductory Real Analysis by Kolmogorov and Fomin, Dover Pub.

Reference: Analysis by Walter Rudin

Section 5.2: Continuous mappings and homeomorphisms. isometric spaces:

Let f be a mapping of one metric space X into another metric space Y, so that f associates an element $y=f(x) \in Y$ with each element $x \in X$. Then, f is said to be continuous at the point $x_{0}$ if, given any $\epsilon >0$, there exists a $\delta >0$ such that

$\rho^{'}(f(x),f(x_{0})) < \epsilon$ whenever $\rho(x,x_{0}) < \delta$.

In the above, the metric $\rho$ is in X and the metric $\rho^{'}$ is in Y. The mapping f is said to be continuous on X if it is continuous at every point in domain X.

Remarks:

This definition reduces to the usual definition of continuity familiar from calculus if X and Y are both numerical sets, that is, if f is a real function defined on some subset of this real line.

Given two metric spaces X and Y, let f be one-to-one mapping of X onto X, and suppose $f$ and $f^{-1}$ are both continuous. Then, f is called a homeomorphic mapping, or simply a homeomorphism between X and Y. Two spaces X and Y are said to be homeomorphic if there exists a homeomorphism between them.

Example :

are said to be isometric to each other. The function $y=f(x) = \frac{2}{\pi}\arctan{x}$

establishes a homeomorphism between the whole real line $(-\infty, \infty)$ and the open interval $(-1,1)$.

DEFINITION 2:

A one-to-one mapping f of one metric space $R=(X,\rho)$ onto another metric space $R^{'} = (X, \rho^{'})$ is said to be an isometric mapping (or simply, an isometry) if

$\rho(x_{1}, x_{2}) = \rho^{'}(f(x_{1}), f(x_{2}))$

for all $x_{1}, x_{2} \in R$. Correspondingly, the spaces R and $R^{'}$ are said to be isometric to each other.

Thus, if $R$ and $R^{'}$ are isometric, the “metric relations” between the elements of R are the same as those between the elements of $R^{'}$, that is, R and $R^{'}$ differ only in the explicit nature of their elements (this distinction is unimportant from the viewpoint of metric space theory). From now on, we will not distinguish between isometric spaces regarding them simply as identical.

Remark:

We will discuss continuity and homeomorphism from a more general viewpoint later.

The next blog poses some exercise problems.

Regards,

Nalin Pithwa.

# II Metric Spaces:

Reference: Introductory Real Analysis Kolmogorov and Fomin, translated by Richard A Silverman, Dover Publications.

Reference: Analysis by Walter Rudin, Third Edition.

Chapter II Metric Spaces:

V: Basic Concepts:

Section 5.1: Definitions and examples:

One of the most important operations in mathematical analysis is the taking of limits. Here what matters is not so much as the algebraic nature of the real numbers (that is, the fact that real numbers form a field), but rather the fact that distance from one point to another on the real line(or, in two or three dimensional space) is well-defined and has certain properties. Roughly speaking, a metric space is a set equipped with a distance (or, ‘metric’) which has these same properties. More exactly, we have:

Definition 1:

By a metric space is meant a pair $(X, \rho)$ consisting of a set X and a distance $\rho$, that is, a single valued, nonnegative, real function $\rho(x,y)$ defined for all $x, y \in X$ which has the following three properties:

1. $\rho(x,y)=0$ if and only if $x=y$
2. Symmetry: $\rho(x,y)=\rho(y,x)$
3. Triangle Inequality: $\rho(x,z) \leq \rho(x,y)+\rho(y,z)$

We will often refer to the set X as a “space” and its elements x, y, …, as “points.” Metric spaces are usually denoted by a single letter, like

$R=(X,\rho)$

or, even by the same letter X as used for the underlying space, in cases where there is no possibility of confusion.

Example 1:

Setting $\rho(x,y)=0$, if $x=y$ and $\rho(x,y)=1$, when $x \neq y$, where x and y are elements of an arbitrary set X, we obviously get a metric space, which might be called a “discrete space” or a “space of isolated points.”

Check: does this satisfy all the three axioms of a metric space: clearly, the first axiom is true. So, also the second axiom is true because $\rho(x,y)=\rho(y,x)$ is zero when $x = y$ and is 1 when $x \neq y$ or $y \neq x$.

Now we have to check: $\rho(x,z) \leq \rho(x,y) + \rho(y,z)$. Case I: if $x=z$, LHS is zero and again RHS could be zero or one depending on y and z. In all cases, the inequality holds. Case II: If $x \neq z$, then LHS is 1. Now, $x \neq y$, then $\rho(x,y)$ is 1 and depending on z, $\rho(y,z)$ is zero or 1. So, we get LHS = RHS = 1 or LHS=1 less than RHS, which is 2.

So, yes indeed this is a well-defined metric function.

Some remarks: To think further:  Suppose we are given the following function : $f(x)=1$ when $x \in \mathscr{Q}$ and $f(x)=0$ when $x \in \mathscr{Q^{'}}$. Can what can we say about this function with respect to the above discrete space ? What are the limit points of such a function ? Is such a function continuous (if so, at which points) in this metric space? Is it dense in this metric space?

Example 2:

The set of all real numbers with distance $\rho(x-y) = |x-y|$ is a metric space, which we denote by $R^{1}$ —- one dimensional real line.

Check: is this a well-defined metric ? Clearly, axiom 1 holds true because $|x-x|=0$ and axiom 2 is true because $\rho(x-y) = |x-y| = |-(x-y)|=|y-x|=\rho(y-x)$. Now, we need to check: $\rho(x,z) \leq \rho(x,y) + \rho(y,z)$. Here, LHS is $|x-z|=|x-y+y-z| = |(x-y) + (y-z)| \leq |x-y| + |y-z| = \rho(x,y) + \rho(y,z)$ where we have used the triangle inequality. So, axiom 3 holds true.

So, this is indeed a well-defined metric.

Example 3:

The set of all ordered n-tuples $x=(x_{1}, x_{2}, \ldots, x_{n})$ of real numbers $x_{1}, x_{2}, \ldots, x_{n}$ with distance

$\rho(x,y)= \sqrt{\Sigma_{k=1}^{n}(x_{k}-y_{k})^{2}}$ ….call this relation I

is a metric space denoted by $R^{n}$ and called n-dimensional Euclidean space (or, simply Euclidean n-space). The distance (I) obviously satisfies axioms 1 and 2 of definition of a metric. Moreover, it can be seen that (I) satisfies the third axiom also:

In fact, let $x=(x_{1}, x_{2}, \ldots, x_{n})$, $y=(y_{1}, y_{2}, y_{3}, \ldots, y_{n})$, $z=(z_{1}, z_{2}, \ldots, z_{n})$ be three points in $R^{n}$.

Futher, let $a_{k}=x_{k}-y_{k}$ and $b_{k}=y_{k}-z_{k}$ when $k=1,2,\ldots, n$.

Then, the triangle inequality takes the form:

$\sqrt{\Sigma_{k=1}^{n}(x_{k}-z_{k})^{2}} \leq \sqrt{\Sigma_{k=1}^{n}(x_{k}-y_{k})^{2}} + \sqrt{\Sigma_{k=1}^{n}(y_{k}-z_{k})^{2}}$….let us call this Relation II.

Or equivalently,

$\sqrt{\Sigma_{k=1}^{n}(a_{k}+b_{k})^{2}} \leq \sqrt{\Sigma_{k=1}^{n}a_{k}^{2}} + \sqrt{\Sigma_{k=1}^{n}b_{k}^{2}}$….call this as relation II’

It follows from the Cauchy-Schwarz inequality that $(\Sigma_{k=1}^{n}a_{k}b_{k})^{2} \leq \Sigma_{k=1}^{n}a_{k}^{2} \times \Sigma_{k=1}^{n}b_{k}^{2}$ …call this as relation III.

so that we have now,

$\Sigma_{k=1}^{n}(a_{k}+b_{k})^{2} = \Sigma_{k=1}^{n}a_{k}^{2} + 2 \Sigma_{k=1}^{n}a_{k}b_{k} + \Sigma_{k=1}^{n}b_{k}^{2} \leq \Sigma_{k=1}^{n}a_{k}^{2}+2\sqrt{\Sigma_{k=1}^{n}a_{k}^{2}\times \Sigma_{k=1}^{n}b_{k}^{2}} + \Sigma_{k=1}^{n}b_{k}^{2} = (\sqrt{\Sigma_{k=1}^{n}a_{k}^{2}} + \sqrt{\Sigma_{k=1}^{n}}b_{k}^{2})^{2}$.

Taking square roots, we get II’ and hence, II.

QED.

Example 4:

Take the same set of ordered tuples as in preceding example $x = (x_{1}, x_{2}, \ldots, x_{n})$, but this time define the distance function by $\rho_{1}(x,y)= \Sigma_{k=1}^{n}|x_{k}-y_{k}|$….call this as relation IV.

It is clear that this is also a well-defined metric function.

Check: Axiom 1 is obvious. So, also axiom 2 because $|a-b|=|b-a|$. Axiom 3 holds true because the following general inequality holds true: $|\pm x_{1} \pm x_{2} \ldots \pm x_{n}| \leq |x_{1}|+|x_{2}|+ \ldots + |x_{n}|$.

Example 5:

Take the same set as in the previous two examples, but now let us define the distance to between two points $x=(x_{1},x_{2}, \ldots, x_{n})$ and $y=(y_{1}, y_{2}, \ldots, y_{n})$ to be $\rho_{0}(x,y)= \max_{1 \leq k \leq n}|x_{k}-y_{k}|$….call this V.

This is also a well-defined metric function.

This space, denoted by $R_{0}^{n}$ is often as usual the Euclidean space $R^{n}$.

Remark: The last three examples show that it is sometimes important to use a different notation for a metric space than for the underlying set of points in the space, since the latter can be “metrized” in a variety of different ways.

Example 6:

The set $C_{[a,b]}$ of all continuous functions defined on the closed interval $[a,b]$ with distance $\rho(f,g)=-\max_{a \leq t \leq b}|f(t)-g(t)|$…call this VI. This is a metric space of great importance in analysis.

Let us verify so:

*****

****

***

This metric space and the underlying set of points in the space will both be denoted by $C_{[a,b]}$. Instead of $C_{[0,1]}$ we just write C. A space like $C[a,b]$ is often called a “function space” to emphasize that its elements are functions.

Example 7:

Let $I_{2}$ be the set of all “infinite” sequences : $x=(x_{1}, x_{2}, \ldots, x_{k}, \ldots)$ of real numbers $x_{1}, x_{2}, \ldots, x_{k}, \ldots$ satisfying the convergence condition:

$\Sigma_{k=1}^{\infty}x_{k}^{2} \leq \infty$

Note: the infinite sequence with the general term $x_{k}$ can be written as $\{ x_{k}\}$ or simply as $x_{1}, x_{2}, \ldots, x_{k}, \ldots$  (this notation is familiar from calculus). It can also be written in “point notation” as $x=(x_{1}, x_{2}, \ldots, , x_{k}, \ldots)$, that is, as an “ordered $\infty-$tuple” generalizing the notion of an ordered n-tuple. (In writing $x_{k}$) we have another use of curly brackets, but the context will always prevent any confusion between the sequence $x_{k}$  and the set whose only element is $x_{k}$).

Where distance between points is defined by

$\rho(x,y)=\sqrt{\Sigma_{k=1}^{\infty}(x_{k}-y_{k}^{2})}$…call this VII.

Clearly, VII makes sense for all $x, y \in l_{2}$ since it follows from the elementary inequality

$(x_{k} \pm y_{k})^{2}\leq 2(x_{k}^{2}+y_{k}^{2})$ that the convergence of the two series $\Sigma_{k=1}^{n}x_{k}^{\infty}$ and $\Sigma_{k=1}^{\infty}y_{k}^{2}$ also implies the convergence of the series $\Sigma_{k=1}^{\infty}(x_{k}-y_{k})^{2}$.

At the same time, we find that if the points $(x_{1}, x_{2}, \ldots, x_{k}, \ldots)$ and $(y_{1}, y_{2}, \ldots, y_{k}, \ldots)$ both belong to $l_{2}$, then so does the point:

$(x_{1}+y_{1}, x_{2}+y_{2}, \ldots, x_{k}+y_{k}, \ldots)$

(since the lim of a sum of two sequences is the sum of the individual limits)

The function VII obviously has the first two defining properties of a distance. To verify the triangle inequality, which takes the form:

$\sqrt{\Sigma_{k=1}^{\infty}(x_{k}-z_{k})^{2}} \leq \sqrt{\Sigma_{k=1}^{\infty}(x_{k}-y_{k})^{2}} + \sqrt{\Sigma_{k=1}^{\infty}(y_{k}-z_{k})^{2}}$ ….call this VIII.

for the metric VII, we first note that all three series converge, for the reason just given. Moreover, the inequality:

$\sqrt{\Sigma_{k=1}^{n}(x_{k}-z_{k})^{2}} \leq \sqrt{\Sigma_{k=1}^{n}(x_{k}-y_{k})^{2}} + \sqrt{\Sigma_{k=1}^{n}(y_{k}-z_{k})^{2}}$…call this IX, holds for all n, (as proved in Example 3 above). Taking the limit as $n \rightarrow \infty$ in IX, we get VIII, thereby satisfying the triangle inequality in $l_{2}$. Therefore, $l_{2}$ is a metric space.

Example 8:

As in Example 6, consider the set of all functions continuous on the interval $[a,b]$, but now let us define the metric by the formula:

$\rho(x,y) = (\int_{a}^{b}[x(t)-y(t)]^{2}dt)^{\frac{1}{2}}$….call this X.

The resulting metric space will be denoted by $C_{[a,b]}^{2}$. The first two axioms of the metric clearly hold, and the fact that X satisfies the triangle inequality is an immediate consequence of the following Schwarz’s inequality:

$(\int_{a}^{b}x(t)y(tdt))^{2} \leq \int_{a}^{b}x^{2}(t)dt \times \int_{a}^{b}y^{2}(t)dt$

(see Problem 3 in the exercises below), by the continuous analogue of the argument given in example 3 above.

Example 9:

Next consider the set of all bounded infinite sequences of real numbers $x=(x_{1},x_{2}, \ldots, x_{k}, \ldots)$ and let

$\rho(x,y) = \sup_{k} {|x_{k}-y_{k}|}$….call this XII.

This gives a metric space which we denote by m. The fact that XII satisfies axioms 1 and 2 of a metric space is obvious by the definition of a supremum.

Axiom 3 can be verified as follows:

***

***

Example 10:

As in example 3, consider the set of all ordered n-tuples, $x=(x_{1}, x_{2}, \ldots, x_{k}, \ldots)$, but now let the metric be given by the more general formula as follows:

$\rho_{p}(x,y)=(\Sigma_{k=1}^{n}|x_{k}-y_{k}|^{p})^{\frac{1}{p}}$….call this XIII.

where p is a fixed real number greater than or equal to 1. (Examples 3 and 4 correspond to the cases $p=2$ and $p=1$, respectively.) This gives a metric space, which we denote by $R_{p}^{n}$.

It is obvious that $\rho_{p}(x,y) = 0$ if and only if $x=y$.

It is obvious that $\rho_{p}(x,y)=\rho_{p}(y,x)$.

But, verification of the third axiom of the definition of a metric (XIII) (that is, the triangle inequality) requires a little work as follows:

Let $x=(x_{1}, x_{2}, \ldots, x_{n})$, $y=(y_{1}, y_{2}, \ldots, y_{n})$, $z=(z_{1}, z_{2}, \ldots, z_{n})$ be three points in $R_{p}^{n}$, and let:

$a_{k}=x_{k}-y_{k}$, $b_{k}=y_{k}-z_{k}$ for $k=1,2,\ldots, n$ just as in example 3. Then, the triangle inequality

$\rho_{p}(x,z) \leq \rho_{p}(x,y)+\rho_{p}(y,z)$

takes the form of Minkowski’s inequality:

$(\Sigma_{k=1}^{\infty}|a_{k}+b_{k}|^{p})^{\frac{1}{p}} \leq (\Sigma_{k=1}^{\infty}|a_{k}|^{p})^{\frac{1}{p}} + (\Sigma_{k=1}^{\infty}|b_{k}|^{p})^{\frac{1}{p}}$

Call the above inequality as XIV in the current blog article.

PS: I think the proof of the Minkowski inequality can be found in any standard text on Inequalities by B. J. Venkatachala, for example;; or, in wikipedia.

The above inequality holds true clearly for $p=1$, and hence, we assume the case $p \geq 1$.

The proof of XIV in turn again is based on Holder’s inequality:

$\Sigma_{k=1}^{n}|a_{k}b_{k}| \leq (\Sigma_{k=1}^{n}|a_{k}|^{p})^{\frac{1}{p}} (\Sigma_{k=1}^{n}|b_{k}|^{q})^{\frac{1}{q}}$

Call the above as inequality XV.

Where the numbers $p>1$, $q >1$ satisfy the condition:

$\frac{1}{p} + \frac{1}{q} =1$….call this as XVI.

We begin by observing that the inequality XV is homogeneous, that is, if it holds for any two points $(a_{1}, a_{2}, \ldots, a_{n})$ and $(b_{1}, b_{2}, \ldots, b_{n})$ then it holds for the two points $(\lambda a_{1}, \lambda a_{2}, \ldots, \lambda a_{n})$ and $(\mu b_{1}, \mu b_{2}, \ldots, \mu b_{n})$ where $\lambda$ and $\mu$ are any two real numbers. Therefore, we need only prove XV for the following case:

$\Sigma_{k=1}^{n}|a_{k}|^{p}=\Sigma_{k=1}^{n}|b_{k}|^{p}$….call this relation XVII.

Thus, assuming that XVII holds, we now have to prove that: $\Sigma_{k=1}^{n}|a_{k}b_{k}| \leq 1$…call this XVIII.

Consider the two areas $S_{1}$ and $S_{2}$, associated with the curve defined in the $\xi\eta$-plane and given by the equation:

$\eta = \xi^{p-1}$, or equivalently by the equation:

$\xi = \eta^{q-1}$

Then, clearly $S_{1}=\int_{0}^{a}\xi^{p-1}d\xi = \frac{a^{p}}{p}$, and $S_{2}=\int_{0}^{b}\eta^{q-1}d\eta = \frac{b^{q}}{q}$

Moreover, it is apparent (if we draw the figure suitably) that $S_{1}+S_{2} \geq ab$ for arbitrary positive a and b. It follows that $ab \leq \frac{a^{p}}{q} + \frac{b^{q}}{q}$…call this relation (19 or XIX).

Setting $a = |a_{k}|$, $b=|b_{k}|$, summing over k from 1 to n, and taking account of (16, or XVI) and (17, or XVII), we get the desired inequality (18, or XVIII). This proves Holder’s inequality (15 or XV). Note that (15 or XV) reduces to Schwarz’s inequality if $p=2$.

It is now an easy matter to prove Minkowski’s inequality (14 or XIV), starting from the identity

$(|a|+|b|)^{p} = (|a|+|b|)^{p-1}|a|+(|a|+|b|)^{p-1}|b|$.

In fact, putting $a=a_{k}$, $b=b_{k}$ and summing over k from 1 to n, we obtain

$\Sigma_{k=1}^{n}(|a_{k}|+|b_{k}|)^{p}=\Sigma_{k=1}^{n}(|a_{k}|+|b_{k}|)^{p-1}|a_{k}|+\Sigma_{k=1}^{n}(|a_{k}|+|b_{k}|)^{p-1}|b_{k}|$

Next, we apply Holder’s inequality (15 or XV) to both sums on the right, bearing in mind that $(p-1)q=p$:

$\Sigma_{k=1}^{n}(|a_{k}|+|b_{k}|)^{p} \leq (\Sigma_{k=1}^{n}(|a_{k}|+|b_{k}|)^{p})^{\frac{1}{q}}([\Sigma_{k=1}^{n}|a_{k}|^{p}]^{\frac{1}{p}}+[\Sigma_{k=1}^{n}|b_{k}|^{p}]^{\frac{1}{p}})$

Dividing both sides of this inequality by

$(\Sigma_{k=1}^{n}(|a_{k}|+|b_{k}|)^{p})^{\frac{1}{a}}$

we get

$(\Sigma_{k=1}^{n}(|a_{k}|+|b_{k}|)^{p})^{\frac{1}{p}} \leq (\Sigma_{k=1}^{n}|a_{k}|^{p})^{\frac{1}{p}} + (\Sigma_{k=1}^{n}|b_{k}|^{p})^{\frac{1}{p}}$

which immediately implies (14 of XIV), thereby proving the triangle inequality in $R_{p}^{n}$.

QED.

Example 11:

Finally, let $l_{p}$ be the set of all infinite sequences $x = (x_{1}, x_{2}, \ldots, x_{k}, \ldots)$ of real numbers satisfying the convergence condition

$\Sigma_{k=1}^{n}x_{k}^{p} < \infty$ for some fixed number $p \geq 1$, where distance between points is defined by

$\rho(x,y) = (\Sigma_{k=1}^{\infty}|x_{k}-y_{k}|^{p})^{\frac{1}{p}}$….call this (20 or XX)

(the case $p=2$ has already been considered in Example 7). It follows from Minkowski’s inequality (14 or XIV) that

$(\Sigma_{k=1}^{n}|x_{k}-y_{k}|^{p})^{\frac{1}{p}} \leq (\Sigma_{k=1}^{n}|x_{k}|^{p})^{\frac{1}{p}} + (\Sigma_{k=1}^{n}|y_{k}|^{p})^{\frac{1}{p}}$….call this (21 or XXI) for any n.

Since the series $\Sigma_{k=1}^{\infty}|x_{k}|^{p}$, and $\Sigma_{k=1}^{\infty}|y_{k}|^{p}$ converge, by hypothesis, we can take the limit as $n \rightarrow \infty$ in (21 or XXI) obtaining

$(\Sigma_{k=1}^{\infty}|x_{k}-y_{k}|^{p})^{\frac{1}{p}} \leq (\Sigma_{k=1}^{\infty}|x_{k}|^{p})^{\frac{1}{p}} + (\Sigma_{k=1}^{\infty}|y_{k}|^{p})^{\frac{1}{p}} < \infty$.

This shows that (20 or XX) actually makes sense for arbitrary $x, y \in l_{p}$. At the same time, we have verified that the triangle inequality holds in $l_{p}$ (the other two properties of a metric space are obviously satisfied). Therefore, $l_{p}$ is a metric space.

QED.

Remarks:

If $R = (X, \rho)$ is a metric space and M is any subset of X, then obviously $R^{*} = (M, \rho)$ is again a metric space, called a subspace of the original metric space R. This device gives us infinitely more examples of metric spaces.

Example 12:

For $x, y \in R^{1}$, define:

12a) $\rho(x,y) = (x-y)^{2}$

12b) $\rho(x,y) = \sqrt{|x-y|}$

12c) $\rho(x,y) = |x^{2}-y^{2}|$

12d) $\rho(x,y) = |x-2y|$

12e) $\rho(x,y) = \frac{|x-y|}{1+|x-y|}$

Determine for each of these, whether it is a metric or not.

Solution 12a:

Axioms 1 and 2 are clearly satisfied. We have to verify if the following holds true:

$(x-z)^{2} \leq (x-y)^{2} + (y-z)^{2}$. Clearly, RHS is $x^{2} + 2y^{2}+ z^{2} -2xy -2yz$ whereas LHS is $x^{2}+y^{2}-2xy$ so it may not always be true that LHS is lesser than or equal to RHS.

Hence, this is not a metric function.

Solution 12b:

this also satisfies the first two axioms of the definition of a metric.

So, we have to verify if the following is true:

$\rho(x,z) \leq \rho(x,y) + \rho(y,z)$, that is, TPT:

$\sqrt{|x-z|} \leq \sqrt{|x-y|} + \sqrt{|y-z|}$.

Consider the following:

$|x-z|=|x-y+y-z| \leq |x-y|+|y-z|$

Also, $(\sqrt{|x-y|} + \sqrt{|y-z|})^{2} = |x-y|+|y-z|+2\sqrt{|x-y|\times|y-z|}$

So the third axiom holds true in this case. So, the given function is a metric.

Solution 12c:

Once again, the first two axioms clearly hold.

We have to verify if the following holds true:

$\rho(x,z) \leq \rho(x,y) = \rho(y,z)$, that is, to prove that:

$|x^{2}-z^{2}| \leq |x^{2}-y^{2}| + |y^{2}-z^{2}|$, which is obviously true by triangle inequality of real numbers. So, the given function is a metric.

Solution 12d:

Clearly, the first two axioms do not hold. It can easily be checked that the third axiom also does not hold. So, the given function is not a metric.

Solution 12e:

The first axiom holds true.

To check the second axiom consider and compare:

$\rho(x,y) = \frac{|x-y|}{1+|x-y|}$ whereas $\rho(y,x) = \frac{|y-x|}{1+|y-x|}=\frac{|x-y|}{1+|x-y|} = \rho(x,y)$ clearly again.

To verify the third axiom, we have to check if the following is true:

$\rho(x,z) \leq \rho(x,y) + \rho(y,z)$, that is, to prove that:

$\frac{|x-z|}{1+|x-z|} \leq \frac{|x-y|}{1+|x-y|} + \frac{|y-z|}{1+|y-z|}$. A little algebraic work shows that this is aot always possible. Hence, the given function is not a metric.

# Exercises based on system of sets

Reference: Introductory Real Analysis, Kolomogorov and Fomin, Dover Publications, Translated and edited by Richard A. Silverman:

Problem 1:

Let X be an uncountable set, and $\mathscr{R}$ be the ring consisting of all finite subsets of X and their complements. Is $\mathscr{R}$ a $\sigma$ -ring also?

Problem 2:

Are open intervals Borel sets ?

Problem 3:

Let $y=f(x)$ be a function defined on a set M and taking values in a set N. Let $\mathscr{M}$ be a system of subsets of M, and let $f(\mathscr{M})$ denote the system of all images $f(A)$ of sets $A \in \mathscr{M}$. Moreover, let $\mathscr{N}$ be a system of subsets of N, and let $f^{-1}(\mathscr{N})$ denote the system of all preimages of $f^{-1}(B)$ of sets $B \in \mathscr{N}$. Prove that

(i) If $\mathscr{N}$ is a ring, so is $f^{-1}(\mathscr{N})$

(ii) If $\mathscr{N}$ is an algebra, so is $f^{-1}()\mathscr{N}$

(iii) If $\mathscr{N}$ is a borel algebra, then so is $f^{-1}(\mathscr{N})$

(iv) $\mathscr{R}(f^{-1}(\mathscr{N}))=f^{-1}(\mathscr{R}(\mathscr{N}))$

(v) $\mathscr{R}(f^{-1}(\mathscr{N}))=f^{-1}(\mathscr{R}(\mathscr{N}))$.

Which of these assertions remain true if $\mathscr{N}$ os replaced by $\mathscr{M}$ and $f^{-1}$ by f?

Regards,

Nalin Pithwa

# Introductory Real Analysis: System of Sets

Reference: Introductory Real Analysis by Kolomogorov and Fomin, Dover Pub.

Section 4:System of Sets:

Section 4.1 Rings of sets:

By a system of sets, we mean any set whose elements are themselves sets. Unless the contrary is explicitly stated, the elements of a given system of sets will be assumed to be certain subsets of some fixed set X. System of sets will be denoted by capital script letters like $\mathscr{R}, \mathscr{S}$, etc. Our chief interest will be systems of sets which have certain closure properties under some set operations.

DEFINITION 1:

A non-empty system of sets $\mathscr{R}$ is called a ring of sets if $A \triangle B \in \mathscr{R}$ and $A \bigcap B \in \mathscr{R}$ whenever $A \in \mathscr{R}$ and $B \in \mathscr{R}$.

Since

$A \bigcup B = (A \triangle B) \triangle (A \bigcap B)$,

$A - B = A \triangle (A \bigcap B)$

we also have $A \bigcup B \in mathscr{R}$ and $A - B \in \mathscr{R}$ whenever $A \in \mathscr{R}$ and $B \in \mathscr{R}$. Thus, a ring of sets is a system of sets closed under the operations of taking unions, intersections, differences, and symmetric differences. Clearly, a ring of sets is also closed under the operations of taking finite unions and intersections: $\bigcup_{k=1}^{n}A_{k}$ and $\bigcap_{k=1}^{n}A_{k}$.

A ring of sets must contain the empty set $\phi$ since $A-A=\phi$.

A set E is called the unit of a system of sets $\mathscr{S}$ if $E \in \mathscr{S}$ and $A \bigcap E =A$ for every $A \in \mathscr{S}$. Clearly, E is unique (why?). Thus, the unit of $\mathscr{S}$ is just the maximal set of $\mathscr{S}$, that is, the set containing all other sets of $\mathscr{S}$. A ring of sets with a unit is called an algebra of sets.

Example 1: Given a set A, the system $\mathscr{M}(A)$ of all subsets of A is an algebra of sets, with unit $E=A$.

Example 2: The system $\{ \phi, A\}$ consisting of the empty set $\phi$ and any nonempty set A is an algebra of sets, with $E=A$.

Example 3: The system of all finite subsets of a given set A is a ring of sets. This ring is an algebra if and only if A itself is finite.

Example 4: The system of all bounded subsets of the real line is a ring of sets, which does not contain a unit.

Theorem 1:

The intersection $\mathscr{R} = \bigcap_{\alpha} \mathscr{R}_{\alpha}$ of any set of rings is itself a ring.

Proof 1: This follows from definition 1. QED.

Theorem 2:

Given any nonempty system of sets $\mathscr{S}$, there is a unique ring $\mathscr{P}$ containing $\mathscr{S}$ and contained in every ring containing $\mathscr{S}$.

Proof 2:

If $\mathscr{P}$ exists, then clearly $\mathscr{P}$ is unique (why?). To prove the existence of $\mathscr{P}$, consider the union $X = \bigcup_{A \in \mathscr{S}}A$ of all sets A belonging to $\mathscr{S}$ and the ring $\mathscr{M}(X)$ of all subsets of X. Let $\Sigma$ be the set of all rings of sets contained in $\mathscr{M}(X)$ and containing $\mathscr{P}$. Then, the intersection $\mathscr{P}=\bigcap_{\mathscr{R} \in \Sigma}\mathscr{R}$ of all these rings clearly has the desired properties. In fact, $\mathscr{P}$ obviously contains $\mathscr{S}$. Moreover, if $\mathscr{R}^{*}$ is any ring containing $\mathscr{S}$, then the intersection $\mathscr{R}=\mathscr{R}^{*} \bigcap \mathscr{M}(X)$ is a ring in $\Sigma$ and hence, $\mathscr{P} \subset \mathscr{R} \subset \mathscr{R}^{*}$, as required. The ring $\mathscr{P}$ is called the minimal ring generated by the system $\mathscr{S}$, and will henceforth be denoted by $\mathscr{R}(\mathscr{S})$. QED.

Remarks:

The set $\mathscr{M}(X)$ containing $\mathscr{R}(\mathscr{S})$ has been introduced to avoid talking about the “set of all rings containing $\mathscr{S}$“. Such concepts as “the set of all sets,” “the set of all rings,” etc. are inherently contradictory and should be avoided. (Recall: Bertrand Russell’s famous set theory paradox).

Section 4.2:

Semirings of sets:

The following notion is more general than that of a ring of sets and plays an important role in a number of problems (especially in measure theory):

Definition 2:

A system of sets $\mathscr{S}$ is called a semiring (of sets) if

i) $\mathscr{S}$ contains the empty set $\phi$;

ii) $A \bigcap B \in \mathscr{S}$ whenever $A \in \mathscr{S}$ and $B \in \mathscr{S}$.

iii) If $\mathscr{S}$ contains the sets A and $A_{1} \in A$, then A can be represented as a finite union $A = \bigcup_{k=1}^{n}A_{k}$ …..(call this (I)) of pairwise disjoint sets of $\mathscr{S}$, with the given set $A_{1}$, as its first term.

Remarks:

The representation (I) is called a finite expansion of A, with respect to the sets $A_{1}, A_{2}, \ldots, A_{n}$.

Example 1:

Every ring of sets $\mathscr{R}$ is a semiring, since if $\mathscr{R}$ contains A and $A_{1} \subset A$, then $A = A_{1}\bigcup A_{2}$ where $A_{2}=A-A_{1} \in \mathscr{R}$.

Example 2:

The set $\mathscr{S}$ of all open intervals $(a,b)$, closed intervals $[a,b]$ and half-open intervals $[a,b)$, including the empty interval $(a,a) = \phi$ and the single element sets $[a,a] = \{ a\}$ is a semiring but not a ring.

Lemma 1:

Suppose the sets $A_{1}, A_{2}, \ldots, A_{n}$ where $A_{1}, \ldots, A_{n}$ are pairwise disjoint subsets of A, all belong to a semiring $S$. Then, there is a finite expansion

$A = \bigcup_{k=1}^{s}A_{k}$, where $s \geq n$

with $A_{1}, \ldots, A_{n}$ as its first terms, where $A_{k} \in \mathscr{S}$, $A_{k} \bigcap A_{l}=\phi$ for all $k, l = 1, \ldots, n$.

Proof of lemma 1:

The lemma holds for $n=1$ by the definition of a semiring. Suppose the lemma holds for $n=m$, and consider $m+1$ sets $A_{1}, \ldots, A_{m}, A_{m+1}$ satisfying the condition of the lemma. By hypothesis,

$A = A_{1} \bigcup \ldots \bigcup A_{m} \bigcup B_{1} \bigcup \ldots \bigcup B_{p}$ where the sets $A_{1}, \ldots, A_{m}, B_{1}, \ldots, B_{p}$ are pairwise disjoint subsets of A, all belonging to $\mathscr{S}$. Let $B_{q1}=A_{m+1} \bigcap B_{q}$

By the definition of a semiring, $B_{q} = B_{q1} \bigcup \ldots \bigcup B_{qr_{q}}$ where the sets $B_{qj} (j=1, \ldots, r_{q})$ are pairwise disjoint subsets of $B_{q}$, all belonging to $\mathscr{S}$. But then it is easy to see that

$A = A_{1}\bigcup \ldots A_{m} \bigcup A_{m+1} \bigcup \bigcup_{q=1}^{p}(\bigcup_{j=2}^{r_{q}}B_{qj})$

that is, the lemma is true for $n = m+1$. The proof now holds true by mathematical induction. QED.

Lemma 2:

Given any finite system of sets $A_{1}, \ldots, A_{n}$ belonging to a semiring $\mathscr{S}$, there is a finite system of pairwise disjoint sets $B_{1}, \ldots, B_{t}$ belonging to $\mathscr{P}$ such that every $A_{k}$ has a finite expansion $A_{k}= \bigcup_{s \in M_{k}}B_{s}$ where $k=1,2,\ldots, n$ with respect to certain of the sets $B_{s}$. (Note: Here $M_{k}$ denotes some subset of the set $\{ 1,2, \ldots, t\}$ depending on the choice of k).

Proof of Lemma 2:

The lemma is trivial for $n=1$ since we only need to set $t=1$ and $B_{1}=A_{1}$.

Let the lemma be true for $n=m$ and consider a system of sets $A_{1}, \ldots, A_{m}, A_{m+1}$ in $\mathscr{P}$. Let $B_{1}, \ldots, B_{t}$ be sets of $\mathscr{S}$ satisfying the conditions of the lemma with respect to $A_{1}, A_{2}, \ldots, A_{m}$, and let $B_{s1}=A_{m+1}\bigcap B_{s}$.

Then, by Lemma 1, there is an expansion

$A_{m+1}=(\bigcup_{s=1}^{t}B_{s1})\bigcup(\bigcup_{p=1}^{q}B_{p}^{'})$

where $B_{p}^{'} \in \mathscr{S}$. while, by definition of a semiring, there is an expansion such that

$B_{s}=B_{s1}\bigcup B_{s2} \bigcup \ldots \bigcup B_{sr}$, where $B_{sj} \in \mathscr{S}$.

It is obvious that $A_{k}= \bigcup_{s \in M_{k}}(\bigcup_{j=1}^{r_{s}}B_{sj})$ where k=1,2, …, m.

for some suitable $M_{k}$. Moreover, the sets $B_{sj}$, $B_{p}^{'}$ are pairwise disjoint. Hence, the sets $B_{sj}, B_{p}^{'}$ satisfy the conditions of the lemma with respect to $A_{1}, \ldots, A_{m}, A_{m+1}$. The proof now follows by mathematical induction. QED.

Section 4.3:

The ring generated by a semiring:

According to Theorem 1, there is a unique minimal ring $\mathscr{R}(\mathscr{S})$ generated by a system of sets $\mathscr{S}$. The actual construction of $\mathscr{R}(\mathscr{S})$ is quite complicated for arbitrary $\mathscr{S}$. However, the construction is completely straightforward if $\mathscr{S}$ is a semiring, as shown by

Theorem 3:

If $\mathscr{S}$ is a semiring, then $\mathscr{R}(\mathscr{S})$ coincides with the system $\mathscr{Z}$ of all sets A which have finite expansions

$A = \bigcup_{k=1}^{n}A_{k}$

with respect to the sets $A_{k} \in \mathscr{S}$.

Proof of Theorem 3:

First we prove that $\mathscr{Z}$ is a ring. Let A and B be any two sets in $\mathscr{Z}$. Then, there are expansions

$A = \bigcup_{i=1}^{m}A_{i}$ where $A_{i} \in \mathscr{S}$

$B = \bigcup_{j=1}^{n}B_{j}$ where $B_{i} \in \mathscr{S}$

Since $\mathscr{S}$ is a semiring, the sets $C_{ij}=A_{i} \bigcap B_{j}$ also belong to $\mathscr{S}$. By Lemma 1, there are expansions as follows:

$A_{i}=(\bigcup_{j=1}^{n}C_{ij})\bigcup(\bigcup_{k=1}^{r_{i}}D_{ik})$, where $D_{ik} \in \mathscr{S}$

$B_{j}=(\bigcup_{r=1}^{m}C_{ij})\bigcup(\bigcup_{l=1}^{s_{j}}E_{jl})$, where $E_{jl} \in \mathscr{S}$

Let us call the above two relations as (II).

It follows from (II) that $A \bigcap B$ and $A \triangle B$ have the expansions

$A \bigcap B = \bigcup_{i,j}C_{ij}$

$A \triangle B = (\bigcup_{i,k}D_{ik})\bigcup (\bigcup_{j,l}E_{jl})$.

and hence, belong to $\mathscr{Z}$. Therefore, $\mathscr{Z}$ is a ring. The fact that $\mathscr{Z}$ is a minimal ring generated by $\mathscr{S}$ is obvious. QED.

Section 4.4

Borel Algebras:

There are many problems (particularly in measure theory) involving unions and intersections not only of a finite number of sets, but also of a countable number of sets. This motivates the following concepts:

Definition 3:

$\sigma -$ ring and $\sigma -$ algebra:

A ring of sets is called a $\sigma$ -ring if it contains the union $S = \bigcup_{n=1}^{\infty}A_{n}$ whenever it contains the sets $A_{1}, A_{2}, \ldots, A_{n}, \ldots$.

A $\sigma$ -ring with a unit E is called a $\sigma$ – algebra.

Definition 4:

$\delta$ -ring and $\delta$– algebra:

A ring of sets is called a $\delta$ -ring if it contains the intersection $D = \bigcap_{n=1}^{\infty}A_{n}$

whenever it contains the sets $A_{1}, A_{2}, \ldots, A_{n}, \ldots$.

A $\delta$ -ring with a unit E is called a $\delta$ – algebra.

Theorem 4:

Every $\sigma$-algebra is a $\delta$-algebra and conversely.

Proof of theorem 4:

These are immediate consequences of the “dual” formulae:

$\bigcup_{n}A_{n}=E - \bigcap_{n}(E-A_{n})$

$\bigcap_{n}A_{n}= E -\bigcup_{\alpha}(E-A_{n})$.

QED.

The term Borel algebra or briefly B-algebra is often used to denote a $\sigma$ -algebra (equivalently, a $\delta$-algebra). The simplest example of a B-algebra is the set of all subsets of a given set A.

Given any system of sets $\mathscr{S}$, there always exists at least one B-algebra containing $\mathscr{S}$. In fact, let

$X = \bigcup_{A \in \mathscr{S}}A$

Then, the system $\mathscr{B}$ of all subsets of X is clearly a B-algebra containing $\mathscr{S}$.

If $\mathscr{B}$ is any Borel-algebra containing $\mathscr{S}$ and if E is its unit, then every $A \in \mathscr{S}$ is contained in E and hence,

$X = \bigcup_{A \in \mathscr{s}}A \subset E$.

A borel-algebra $\mathscr{B}$ is called irreducible (with respect to the system $\mathscr{S}$) if $X=E$, that is, an irreducible Borel-algebra is a Borel-algebra containing no points that do not belong to one of the sets $A \in \mathscr{S}$. In every case, it will be enough to consider only irreducible Borel-algebras.

Theorem 2 has the following analogue for irreducible Borel-algebras:

Theorem 5:

Given any non empty system of sets $\mathscr{S}$, there is a unique irreducible (to be precise, irreducible with respect to $\mathscr{S}$) B-algebra $\mathscr{B}(\mathscr{S})$ containing $\mathscr{S}$ and contained in every B-algebra containing $\mathscr{S}$.

Proof of theorem 5:

The proof is virtually identical with that of Theorem 2. The B-algebra $\mathscr{B}(\mathscr{S})$ is called the minimal B-algebra generated by the system $\mathscr{S}$ or the Borel closure of $\mathscr{S}$.

Remarks:

An important role is played in analysis by Borel sets or B-sets. These are the subsets of the real line belonging to the minimal B-algebra generated by the set of all closed intervals $[a,b]$.

Exercises to follow,

Regards,

Nalin Pithwa

# Introductory real analysis: exercise 3:

Based on previous two blogs. (Reference: Introductory Real Analysis by Kolmogorov and Fomin, Dover Publishers):

Problem 1:Exhibit both a partial ordering and a simple ordering of the set of all complex numbers.

Problem 2:What is the minimal element of the set of all subsets of a given set X, partially ordered by set inclusion. What is the maximal element?

Problem 3: A partially ordered set M is said to be a directed set if, given any two elements $a, b \in M$, there is an element $c \in M$ such that $a < c, b. Are the partially ordered sets in the previous blog(s) Section 3.1 all directed sets?

Problem 4: By the greatest lower bound of two elements a and b of a partially ordered set M, we mean an element $c \in M$ such that $c \leq a, c \leq b$ and there is no element $d \in M$ such that $a < d \leq a, d \leq b$. Similarly, by the least upper bound of a and b, we mean an element $c \in M$ such that $a \leq c, b \leq c$ and there is no element $d \in M$ such that $a \leq d . By a lattice is meant a partially ordered set any two elements of which have both a greatest lower bound and a least upper bound. Prove that the set of all subsets of a given set X, partially ordered by set inclusion, is a lattice. What is the set theoretic meaning of the greatest lower bound and least upper bound of two elements of this set?

Problem 5: Prove that an order preserving mapping of one ordered set onto another is automatically an isomorphism.

Problem 6: Prove that ordered sums and products of ordered sets are associative, that is, prove that if $M_{1}, M_{2}, M_{3}$ are ordered sets, then

$(M_{1}+M_{2})+M_{3}=M_{1}+(M_{2}+M_{3})$,

$(M_{1}.M_{2}).M_{3}=M_{1}.(M_{2}.M_{3})$ where the operations + and . are the same as defined in previous blog(s).

Comment: This allows us to drop the parentheses in writing ordered sums and products.

Problem 7:

Construct well-ordered sets with ordinals

$\omega + n$, $\omega + \omega$, $\omega + \omega + n$, $\omega + \omega + \omega$, $\ldots$.

Show that the sets are all countable.

Problem 8:

Construct well-ordered sets with ordinals

$\omega . n$, $\omega^{2}$, $\omega^{2}.n$, $\omega^{3}$, $\ldots$.

Show that the sets are all countable.

Problem 9:

Show that $\omega + \omega = \omega. 2$, $\omega + \omega + \omega = \omega. 3$, $\ldots$

Problem 10:

Prove that the set $W(\alpha)$ of all ordinals less than a given ordinal $\alpha$ is well-ordered.

Problem 11:

Prove that any non-empty set of ordinals is well-ordered.

Problem 12:

Prove that the set M of all ordinals corresponding to a countable set is itself uncountable.

Problem 13:

Let $\aleph_{1}$ be the power of the set M in the previous problem. Prove that there is no power m such that $\aleph_{0} .

More later,

Nalin Pithwa.

# Introductory Real Analysis: The well-ordering theorem, the axiom of choice,equivalent assertions

Reference: Introductory Real Analysis by Kolmogorov and Fomin, Dover Publications.

Section 3.7 The well-ordering theorem, the axiom of choice, and equivalent assertions:

Theorem 4 of previous blog shows that the powers of two well-ordered sets are always comparable. In 1904, Zermelo succeeded in proving the

Well-ordering theorem: Every set can be well-ordered.

It follows from the well-ordering theorem and Theorem 5 (of previous blog) that the powers of two arbitrary sets are always comparable, a fact already used earlier. Zermelo’s proof, which will not be given here, rests on the following basic:

AXIOM OF CHOICE:

Given any set M, there is a “choice function” f such that $f(A)$ is an element of A for every non-empty subset $A \subset M$.

We will assume the validity of the axiom of choice without further ado. In fact, without the axiom of choice we would be severely hampered in making set-theoretic constructions. However, it should be noted that from the standpoint of the foundations of set theory, there are still deep and controversial problems associated with the use of axiom of choice.

There are a number of assertions equivalent to the axiom of choice, that is, assertions each of which both implies and is implied by the axiom of choice. One of these is the well-ordering theorem, which obviously implies the axiom of choice. In fact, if an arbitrary set M can be well-ordered, then, by merely choosing the “first” element in each subset $A \subset M$, we get the function $f(A)$ figuring in the statement of the axiom of choice. On the other hand, the axiom of choice implies the well-ordering theorem, as already noted without proof.

To state further assertions equivalent to the axiom of choice, we need some more terminology:

DEFINITION 3:

Let M be a partially ordered set, and let A be any subset of M such that a and b are comparable for every $a, b \in A$. Then, A is called a chain (in M). A chain C is said to be maximal if there is no other chain C in M containing C on a proper subset.

DEFINITION 4:

An element a of a partially ordered set M is called an upper bound of a subset $M^{'} \subset M$, if $a^{'} < a$ for every $a^{'} \in M^{'}$.

We now have the vocabulary needed to state two other assertions equivalent to the axiom of choice:

Hausdorff’s Maximal Principle: Every chain in a partially ordered set M is contained in a maximal chain in M.

Zorn’s lemma:  If every chain in a partially ordered set M has an upper bound, then M contains a maximal element.

For the proof of the equivalence of the axiom of choice, the well-ordering theorem, Hausdorff’s maximal principle and Zorn’s lemma, we refer the reader elsewhere. Of these various equivalent assertions, Zorn’s lemma is perhaps the most useful.

Section 3.8 Transfinite Induction:

Mathematical propositions are very often proved by using the following familiar:

THEOREM 4: MATHEMATICAL INDUCTION:

Given a proposition $P(n)$ formulated for every positive integer n, suppose that :

i) P(1) is true.

ii) The validity of P(k) for all $k implies the validity of $P(n+1)$. Then, P(n) is true for all $n=1,2,\ldots$.

PROOF 4:

Suppose P(n) fails to be true for all $n=1,2,\ldots$ and let n, be the smallest integer for which $P(n)$ is false (the existence of such $n_{1}$ follows from the well-ordering of the positive integers). Clearly, $n_{1}>1$, so that $n_{1}-1$ is a positive integer. Therefore, $P(n)$ is valid for all $k \leq n_{1}-1$ but not for $n_{1}$. Contradiction!!

QED.

Replacing the set of all positive integers by an arbitrary well-ordered set, we get

THEOREM 4 (Transfinite induction):

Given a well-ordered set A, let $P(a)$ be a proposition formulated for every element $a \in A$. Suppose that

i) $P(a)$ is true for the smallest element of A

ii) The validity of $P(a)$ for all $a < a^{*}$ implies the validity of $P(a^{*})$. Then, $P(a)$ is true for all $a \in A$.

PROOF 4:

Suppose $P(a)$ fails to be true for all $a \in A$. Then, $P(a)$ is false for all a in some non empty subset $A^{*} \subset A$. By the well-ordering, $A^{*}$ has a smallest element $a^{*}$. Therefore, $P(a)$ is valid for all $a< a^{*}$ but not for $a^{*}$. Contradiction !!

QED.

Remark:

Since any set can be well-ordered, by the well-ordering theorem, transfinite induction can in principle be applied to any set M whatsoever. In practice, however, Zorn’s lemma is a more useful tool, requiring only that M be partially ordered.

Section 3.9: Historical Remarks:

Set theory as a branch of mathematics in its own right stems from the pioneer work of Georg Cantor (1845-1918). Originally met with disbelief, Cantor’s ideas subsequently became widespread. By now, the set theoretic point of view has become standard in the most diverse fields of mathematics. Basic concepts, like groups, rings, fields, linear spaces etc are habitually defined as sets of elements of an arbitrary kind obeying appropriate axioms.

Further development of set theory led to a number of logical difficulties, which naturally gave rise to attempts to replace “naive” set theory by a more rigorous axiomatic set theory. It turns out that certain set theoretic questions, which would at first seem to have “yes” or “no” answers, are in fact of a different kind. Thus, it was shown by Godel in 1940 that a negative answer to the question :”Is there an uncountable set of power less than that of the continuum” is consistent with set theory (axiomatized in a way we will not discuss here), but it was recently shown by Stephen Cohen that an affirmative answer to the question is also consistent in the same sense !!

We will continue to exercises based on last two blogs now,

Regards,

Nalin Pithwa.

# Ordered Sets and Ordinal Numbers: Introductory Real Analysis: Kolmogorov and Fomin

Section 3: Ordered sets and ordinal numbers:

Section 3.1: Partially ordered sets.

A binary relation R on a set M is said to be a partial ordering (and the set M is said to be partially ordered) if

i) R is reflexive (aRa for every $a \in M$).

ii) R is transitive (aRb and bRc together imply aRc)

iii) R is antisymmetric in the sense that aRb and bRa together imply $a=b$.

For example, if M is the set of all real numbers and aRb means that $a, then R is partial ordering. (please verify!) This suggests writing $a \leq b$ (or equivalently $b \geq a$) instead of aRb whenever R is a partial ordering, and we will do so from now on. Similarly, we write $a < b$ if $a \leq b$, but $a \neq b$; and $b > a$ if $b \geq a$ but $b \neq a$.

The following examples give some idea of the generality of the concept of a partial ordering:

Example 1:

Any set M can be trivially partially ordered by setting $a \leq b$ iff $a=b$.

Example 2:

Let M be the set of all continuous functions $f, g, \ldots$ defined in a closed interval $[\alpha, \beta]$. Then, we get a partial ordering by setting $f \leq g$ iff $f(t) \leq g(t)$ for every $t \in [\alpha, \beta]$.

Example 3:

The set of all subsets $M_{1}, M_{2}, \ldots$ is partially ordered if and only if $M_{1} \leq M_{2}$ means that $M_{1} \subset M_{2}$.

Example 4:

The set of all integers greater than 1 is partially ordered if “$a \leq b$” means that “b is divisible by a.”

Remark: An element of a of a partially ordered set is said to be maximal if $a \leq b$ implies $b=a$ and minimal if $b \leq a$ implies $b=a$. Thus, in Example 4 above, every prime number (greater than 1) is a minimal element. (Of course, 1 is neither prime nor composite.)

Section 3.2: Order-preserving mappings. Isomorphisms:

Let M and $M^{'}$ be any two partially ordered sets, and let f be a one-to-one mapping of M onto $M^{'}$. Then, f is said to be order-preserving if $a \leq b$ (where $a, b \in M$) implies $f(a) \leq f(b)$ (in $M^{'}$). An order preserving mapping f such that $f(a) \leq f(b)$ implies $a \leq b$ is called an isomorphism. In other words, an isomorphism between two partially ordered sets M and $M^{'}$ is a one-to-one mapping of M onto $M^{'}$ such that $f(a) \leq f(b)$ if and only if $a \leq b$. Two partially ordered sets M and $M^{'}$ are said to be isomorphic (to each other) if there exists and isomorphism between them.

Example:

Let M be the set of positive integers greater than 1 partially ordered as in example 4 earlier. Let $M^{'}$ be the same set partially ordered in the natural way, that is, in such a way that $a \leq b$ if and only if $b-a >0$. Then, the mapping of M onto $M^{'}$ carrying every integer n into itself is order-preserving, but NOT an isomorphism.

Some remarks:

Isomorphism between partially ordered sets is an equivalence relation as defined in an earlier blog of this series, being obviously reflexive, symmetric, and transitive. Hence, any given family of partially ordered sets can be partitioned into disjoint classes of isomorphic sets. Clearly, two isomorphic partially ordered sets can be regarded as identical in cases where it is the structure of the partial ordering than the specific nature of the elements of the sets that is of interest.

Some other remarks:

For those of you who are aware, compare now the concepts and some examples of homomorphisms and isomorphisms between two algebraic objects called groups with the above concepts.  Two references for the same are: (i) Topics in Algebra by I N Herstein (2) Abstract Algebra by Dummit and Foote.

Some further remarks:

At this stage, it might even be useful to compare the concepts and examples of a cartesian product of two (non-empty) sets A and B; that of a relation R on set A and set B; that of a binary relation on a set A; that, of an equivalence relation on a set A; and also the basic meaning of a function from set A to set B. You will see that there are slight subtle differences.

Sec 3.3 Ordered Sets. Order Types:

Given two elements a and b of a partially ordered set M, it may turn out that neither of the relations $a \leq b$ or $b \leq a$ holds. In this case, a and b are said to be noncomparable. Thus, in general, the relation $\leq$ is defined only for certain pairs of elements, which is why M is said to be partially ordered. However, if M has no non-comparable elements, then M is said to be simply ordered or linearly ordered or ordered. In other words, a set M is ordered if it is partially ordered and if, given any two distinct elements $a, b \in M$, either $a , or $b. Obviously, any subset of an ordered set is itself ordered.

Each of the sets figuring in Examples 1 to 4 of Section 3.1 in this blog, is partially ordered, but not ordered. Simple examples of ordered sets are the set of all positive integers, the set of all rational numbers, the set of all real numbers in the $[0,1]$ and so on (with the usual relations of “greater than” and “less than”.)

Since an ordered set is a special kind of partially ordered set, the concepts of order-preserving mapping and isomorphism apply equally well to ordered sets. Two isomorphic ordered sets are said to have the same order type. Thus “type” is something shared by all isomorphic ordered sets, just as “power” is something shared by all equivalent sets (considered as ‘plain’ sets, without regard for possible orderings).

The simplest example of an ordered set is the set of all positive integers $1,2,3,\ldots$ arranged in increasing order, with the usual meaning of the symbol <. The order type of this set is denoted by the symbol $\omega$. Two isomorphic ordered sets obviously have the same power (because an isomorphism is a one-to-one correspondence). Thus, it makes sense to talk about the power corresponding to a given order type. The converse is not true, since a set of a given power can in general be ordered in many different ways. It is only in the finite case that the number of elements in a set uniquely determines its type, designated by the same symbol n as the number of elements in the set. For example, besides the “natural” order type $\omega$ of the set of positive integers, there is another order type corresponding to the sequence: $1,3,5, \ldots, 2,4,6, \ldots$ where odd and even numbers are separately arranged in increasing order but any odd number precedes any even number. It can be shown that the number of distinct order types of a set of power $\aleph_{0}$ is infinite and in fact, uncountable.

Section 3.4 Ordered sets and products of ordered sets.

Let $M_{1}$ and $M_{2}$ be two ordered sets of types $\theta_{1}$ and $\theta_{2}$ respectively. Then, we can introduce an ordering in the union $M_{1} \bigcup M_{2}$ of the two sets by assuming that :

(i) a and b have the same ordering as in $M_{1}$ if $a,b \in M_{1}$.

(ii) a and b have the same ordering as in $M_{2}$ if $a,b \in M_{2}$

(iii) $a if $a \in M_{1}$ and $b \in M_{2}$.

(Verify that this is actually an ordering of $M_{1} \bigcup M_{2}$). The set $M_{1} \bigcup M_{2}$ ordered in this way is called the ordered sum of $M_{1}$ and $M_{2}$ denoted by $M_{1}+M_{2}$. Note that the order of terms matters here, that is, in general $M_{2}+M_{1}$ is not isomorphic to $M_{1}+M_{2}$. More generally, we can define the ordered sum of any finite number of ordered sets by writing (this will be an exercise problem after this blogged section) :

$M_{1}+M_{2}+M_{3}=(M_{1}+M_{2})+M_{3}$

$M_{1}+M_{2}+M_{3}+M_{4}=(M_{1}+M_{2}+M_{3})+M_{4}$,

and so on.

By the ordered sum of the types $\theta_{1}+\theta_{2}$, denoted by $\theta_{1}+\theta_{2}$ we mean the order type of the set $M_{1}+M_{2}$.

Example:

Consider the order types $\omega$ and $n$. It is easy to see that $n + \omega = \omega$. In fact, if finitely many terms are written to the left of the sequence $1,2,3,\ldots, k, \ldots$, we again get a set of the same type (Quiz: why?). On the other hand, the order type $\omega + n$, that is the order type of the set (***) :

$\{ 1,2,3, \ldots, k, \ldots, a_{1}, a_{2}, \ldots, a_{n}\}$ is obviously not equal to $\omega$.

(Note: ***: In the above listing of elements of the set, we have used the usual curly braces notation, but with the emphasis on the order as shown.)

Again, let $M_{1}$ and $M_{2}$ be two ordered sets of types $\theta_{1}$ and $\theta_{2}$ respectively, Suppose we replace each element of $M_{2}$ by a “replica” of the set $M_{1}$. Then, the resulting set, denoted  by $M_{1}.M_{2}$ is the set of all pairs $(a,b)$ where $a \in M_{1}$ and $a \in M_{2}$ ordered in such a way that:

(i) $(a_{1},b_{1})<(a_{2},b_{2})$ if $b_{1} for arbitrary $a_{1},a_{2}$

(ii) $(a_{1},b)<(a_{2},b)$ if $a_{1}.

Note that the order of factors matters here, that is, in general $M_{2}.M_{1}$ is not isomorphic to $M_{1}.M_{2}$. The ordered product of any finite number of ordered sets can be defined by writing (again a problem in the exercise later):

$M_{1}.M_{2}.M_{3}=(M_{1}.M_{2}).M_{3}$

$M_{1}.M_{2}.M_{3}.M_{4}=(M_{1}.M_{2}.M_{3}).M_{4}$

and so on. By the ordered product of the types $\theta_{1}$ and $\theta_{2}$, denoted by $\theta_{1}.\theta_{2}$, we mean the order type of the set $M_{1}.M_{2}$.

Section 3.5. Well-ordered sets. Ordinal numbers.

A key concept in the theory of ordered sets is given by:

DEFINITION 1: An ordered set M is said to be well-ordered if every non-empty subset A of M has a smallest (or, “first“) element, that is, an element $\mu$ such that $\mu  for every $a \in A$.

Example 1: Every finite ordered set is obviously well-ordered.

Example 2: Every non-empty subset of a well-ordered set is itself well-ordered.

Example 3: The set M of numbers in the interval $[0,1]$ is ordered but not well-ordered. It is true that M has a smallest element, namely, the number 0 but the subset of M consisting of all positive rational numbers has no smallest element.

DEFINITION 2: The order type of a well-ordered set is called an ordinal number or simply, an ordinal. If the set is infinite, the ordinal is said to be transfinite. (NB: This is a good place to point out that the terms “cardinal number” and “power” of a set are synonymous).

Example 4: The set of positive integers $1,2,\ldots, k, \ldots$ arranged in increasing order is well-ordered, and hence, its order type $\omega$ is a transfinite ordinal. The order type $\omega + n$ of the set $\{1,2,\ldots, k, \ldots, a_{1}, a_{2}, \ldots, a_{n} \}$ is also an ordinal.

Example 5: The set $\{ \ldots, -k, \ldots, -3,-2,-1\}$ is ordered but not well-ordered. It is true that any non empty subset A of this set has a largest element (that is, an element $\mathscr{v}$ such that $a ) for every $a \in A$), but in general set A will not have a smallest element. In fact, the given set itself has no smallest element. Hence, the order type of given set is denoted by $\omega^{*}$ is not an ordinal number.

THEOREM 1The ordered sum of a finite number of well-ordered sets $M_{1}, M_{2}, \ldots, M_{n}$ is itself a well-ordered set.

PROOF 1: Let M be an arbitrary subset of the ordered sum $M_{1}+M_{2}+\ldots+M_{n}$ and let $M_{k}$ be the first of the sets $M_{1}, M_{2}, \ldots, M_{n}$, (namely, the set with the smallest index) containing elements of M. Then, $M \bigcap M_{k}$ is a subset of the well-ordered set $M_{k}$ and as such has a smallest element $\mu$. Clearly, $\mu$ is the smallest element of M itself. QED.

COROLLARYThe ordered sum of a finite number of ordinal numbers is itself an ordinal number.

Thus, new ordinal numbers can be constructed from any given set of ordinal numbers. For example, starting from the positive integers, (that is, the finite ordinal numbers) and the ordinal number $\omega$, we can construct the new ordinal numbers :

$\omega + n$, $\omega + \omega$, $\omega + \omega + n$, $\omega + \omega + \omega$, and so on.

THEOREM 2The ordered product of two well-ordered sets $M_{1}, M_{2}$ is itself a well-ordered set.

Proof 2:

Let M be an arbitrary subset of $M_{1}\dot M_{2}$ so that M is a set of ordered pairs $(a,b)$ with $a \in M_{1}, b\in M_{2}$. The set of all second elements b of pairs in M is a subset of $M_{2}$, and as such has a smallest element since $M_{2}$ is well-ordered. Let $b_{1}$ denote this smallest element, and consider all pairs of the form $(a,b_{1})$ contained in M. The set of all first elements a of these pairs is a subset of $M_{1}$, and as such has a smallest element since $M_{1}$ is well-ordered. Let $a_{1}$ denote this smallest element. Then, the pair $(a,b)$ is clearly the smallest element of M. QED.

COROLLARY 1:

The ordered product of a finite number of well-ordered sets is itself a well-ordered set.

COROLLARY 2:

The ordered product of a finite number of ordinal numbers is itself an ordinal number.

Thus it makes sense to talk about ordinal numbers $\omega . n, \omega^{2}, \omega^{2} . n, \omega^{3}, \ldots$ and so on. It is also possible to define such ordinal numbers as $\omega^{\omega}, \omega^{\omega^{\omega}}, \ldots$.

Section 3.6 Comparison of ordinal numbers:

If $n_{1}$ and $n_{2}$ are two ordinal numbers, then they either coincide or else one is larger than the other. As we now show, the same is true for transfinite ordinal numbers. We begin by observing that every element $a$ of a well-ordered set M determines an (initial section) P, the set of all $x \in M$ such that $x, and a remainder Q, the set of all $x \in M$ such that $x \geq a$. Given any two ordinal numbers $\alpha$ and $\beta$, Let M and N be well-ordered sets of order type $\alpha$ and $\beta$. Then, we say that

i) $\alpha=\beta$ if M and N are isomorphic;

ii) $\alpha < \beta$ if M is isomorphic to some section of N

iii) $\alpha > \beta$ if N is isomorphic to some section of M.

(note that this definition makes sense for finite $\alpha$ and $\beta$).

LEMMA:

Let f be an isomorphism of a well-ordered set A onto some subset $B \subset A$. Then, $f(a) \geq a$ for all $a \in A$.

Proof of lemma:

If there are elements $a \in A$ such that $f(a), then there is a least such element since A is well-ordered. Let $a_{0}$ be this element, and let $b_{0}=f(a_{0})$. Then $b_{0}, and hence, $f(b_{0}), since f is an isomorphism. But, then $a_{0}$ is not the smallest element such that $f(a). Contradiction! QED.

It follows from the lemma that a well-ordered set A cannot be isomorphic to any of its sections, since if A were isomorphic to the section determined by a, then clearly $f(a). In other words, the two relations

$\alpha=\beta$, $\alpha<\beta$ are incompatible, and so are $\alpha=\beta$, $\alpha>\beta$. Moreover, the two relations $\alpha<\beta$, $\alpha>\beta$ are incompatible, since otherwise we could use the transitivity to deduce $\alpha < \alpha$, which is impossible the lemma. Therefore, if one of the three relations

$\alpha<\beta$, $\alpha=\beta$, $\alpha>\beta$….II

holds, the other two are automatically excluded. We must still show that one of the relations in II above always holds, thereby proving that any two ordinal numbers are always comparable.

THEOREM 3:

Two given ordinal numbers $\alpha$ and $\beta$ always satisfy one and only of the relations: $\alpha=\beta$, $\alpha < \beta$ and $\beta<\alpha$.

Proof 3:

Let $W(\alpha)$ be the set of all ordinals $<\alpha$. Any two numbers $\gamma$ and $\gamma^{'}$ in $W(\alpha)$ are comparable (Recall the meaning of $\gamma < \alpha, \gamma^{'}<\alpha$ and use the fact that a section of a section of a well-ordered set is itself a section of a well-ordered set) and the corresponding ordering of $W(\alpha)$ makes it a well-ordered set of type $\alpha$. In fact, if a set $A = \{ \ldots, a, \ldots, b, \ldots\}$ is of type $\alpha$, then by definition, the ordinals less than $\alpha$ are the types of well-ordered sets isomorphic to sections of A. Hence, the ordinals themselves are in one-one correspondence with the elements of A. In other words, the elements of a set of type $\alpha$ can be numbered by using the ordinals less than $\alpha$: $A = \{ a_{1}, a_{2}, \ldots, a_{n}, \ldots\}$.

Now, let $\alpha$ and $\beta$ be two ordinals. Then, $W(\alpha)$ and $W(\beta)$ are well-ordered sets of types $\alpha$ and $\beta$, respectively. Moreover, let $C=A \bigcap B$ be the intersection of the sets A and B, that is, the set of all ordinals less than both $\alpha$ and $\beta$. Then, C is well-ordered, of type $\gamma$, say. We now show that $\gamma \leq \alpha$. If $C=A$, then obviously $\gamma=\alpha$. On the other hand, if $C \neq A$, then C is a section of A and hence, $\gamma < \alpha$. In fact, let $\xi \in C$, $\eta \in A - C$. Then, $\xi$ and $\eta$ are comparable, that is, either $\xi < \eta$ or $\xi > \eta$. But, $\eta < \xi < \alpha$ is impossible, since then $\eta \in C$. Therefore, $\xi < \eta$ and hence, C is a section of A, which implies $\gamma < \alpha$. Moreover, $\gamma$ is the first element of the set $A-C$. Thus, $\gamma < alpha$, as asserted, and similarly, $\gamma < \beta$. The case $\gamma < \alpha$, $\gamma < \beta$ is impossible, since then $\gamma \in A-C$ and $\gamma \in B-C$. But then $\gamma \notin C$ on the one hand and $\gamma \in A \bigcap B = C$ on the other hand. It follows that there are only three possibilities:

$\gamma=\alpha$ and $\gamma = \beta$ and $\alpha=\beta$

$\gamma=\alpha$ and $\gamma< \beta$ and $\alpha < \beta$

$\gamma < \alpha$ and $\gamma = \beta$ and $\alpha > \beta$,

that is, $\alpha$ and $\beta$ are comparable.

QED.

THEOREM 4:

Let A and B be well-ordered sets. Then, either A is equivalent to B or one of the sets is of greater power than the other, that is, the powers of A and B are comparable.

PROOF 4:

There is a definite power corresponding to each ordinal. But we have just seen that ordinals are comparable, and so are the corresponding powers.

[[recall the definition of inequality of powers given in Sec 2.5 in the blog series of Kolmogorov and Fomin). (Reproduced here for the sake of helping the memory: Given any two sets M and N, suppose M and N are equivalent. Then, M and N are said to have the same power. Roughly speaking, “power” is something shared by equivalent sets. If M and N are finite, then M and N have the same number of elements, and the concept of the power of a set reduces to the usual notion of the number of elements in a set. The power of the set $\mathcal{Z_{+}}$ is $\aleph_{0}$ and sets which are equivalent to the set $[0,1]$ are said to have the power of the continuum, c. For the powers of finite sets, that is, for the set of positive integers, we have the notions of “greater than” or “less than”, as well as the notion of equality. These concepts can be extended to infinite sets. If A and B are two sets with powers m(A) and m(B) respectively, either $m(A)=m(B)$, or A is equivalent to a subset of B such that no subset of B is equivalent to A, then by analogy with the final case, m(A) is less than m(B).]]

To be continued soon,

Regards,

Nalin Pithwa