# 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

This site uses Akismet to reduce spam. Learn how your comment data is processed.