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}<b_{2}<b_{3} 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_{2}<a_{3}; (a, b_{1}, c) < (a, b_{2}, c) < (a, b_{3}, c) if b_{1}<b_{2}<b_{3}; (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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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