Math Problems Vault

Problem I.5.1

Prove that if linearly ordered sets are similar, then they are also equivalent.

?

Problem I.5.2

Prove that any set $A$ equivalent to a linearly ordered set $B$ can be linearly ordered so that $A$ becomes similar to $B$ .

?

Problem I.5.3

(a)(b)(c)

Let $A$ , $B$ , $C$ be linearly ordered sets. Prove that:

?

(a)

$A \simeq A$ (reflexivity);

(b)

if $A \simeq B$ , then $B \simeq A$ (symmetry);

(c)

if $A \simeq B$ and $B \simeq C$ , then $A \simeq C$ (transitivity).

Problem I.5.4

Let $A$ and $B$ be linearly ordered sets. Prove that if $A \simeq B$ , then $\left|A\right| = \left|B\right|$ , but the converse is false.

?

Problem I.5.5

Prove that a set of $n$ elements can be linearly ordered in $n!$ ways.

?

Problem I.5.6

Prove that all finite linearly ordered sets of the same cardinality are similar to one another.

?

Problem I.5.7

Prove that for infinite sets the assertion of the previous problem is false.

?

Problem I.5.8

Prove that linearly ordered sets are similar if and only if there exists between them a one-to-one correspondence that is a monotone map.

?

Problem I.5.9

(a)(b)(c)(d)

Prove that for any linearly ordered set $A$ and any $a, b \in A$ :

?

(a)

$a \notin A_{a}$ ;

(b)

if $a$ is the least element of $A$ , then $A_{a} = \emptyset$ ;

(c)

$A_{a}$ is a linearly ordered set;

(d)

if $a < b$ , then $(A_{b})_{a} = A_{a}$ .

Problem I.5.10

Prove that the set of all segments of a linearly ordered set $A$ , ordered by the inclusion relation, is similar to $A$ .

?

Problem I.5.11

(a)(b)(c)

Prove that an infinite linearly ordered set $A$ has order type $\omega$ if and only if it satisfies the following conditions:

?

(a)

$A$ has a least element $a_{0}$ ,

(b)

for every $a \in A$ there exists a greatest lower bound $a'$ of the set $\left\{ x \mid a < x, x \in A\right\}$ ( $a'$ is called the immediate successor of $a$ );

(c)

for any subset $X$ of the set $A$ , from $a_{0} \in X$ and $X$ containing, together with each of its elements, the immediate successor of that element, it follows that $X = A$ .

Problem I.5.12

Prove that an infinite linearly ordered set has order type $\omega$ if and only if all its initial segments are finite.

?

Problem I.5.13

(a)(b)

Prove that any countable linearly ordered set $A$ has order type $\eta$ if and only if $A$ satisfies the following conditions:

?

(a)

$A$ has no least and no greatest element;

(b)

for any $x, y \in A$ such that $x < y$ , there exists $z \in A$ such that $x < z < y$ (such an order is called dense).

Problem I.5.14

Prove that every countable linearly ordered set is similar to some subset of the set $\mathbb {Q}$ of rational numbers.

?

Problem I.5.15

(a)(b)

Let $A$ be a linearly ordered set containing at least two elements, $B = A \cup A^{2} \cup \ldots \cup A^{n} \cup \ldots$ Put, for any $x_{1}, \ldots , x_{n}, y_{1}, \ldots , y_{m} \in A$ $(1 \leq n, m)$ ,

\langle x_{1}, \ldots , x_{n} \rangle \leq \langle y_{1}, \ldots , y_{m} \rangle \Leftrightarrow (n \leq m \text{ and } x_{1} = y_{1}, \ldots , x_{n} = y_{n}) \text{ or }

(x_{1} = y_{1}, \ldots , x_{i-1} = y_{i-1}, x_{i} < y_{i} \text{ for some } i \leq n \text{ and } i \leq m).

Prove that:

?

(a)

$\leq$ is a linear order on $B$ ;

(b)

any countable linearly ordered set is similar to some subset of the set $B$ .

Problem I.5.16

Prove that the order type of any interval (not segment) of real numbers is $\lambda$ .

?

Problem I.5.17

A subset $B$ of a linearly ordered set $A$ with order $\leq$ is called dense in $A$ if for any $a_{1}, a_{2} \in A$ there exists $b \in B$ such that $a_{1} \leq b \leq a_{2}$ or $a_{2} \leq b \leq a_{1}$ . Prove that if $A$ contains a countable subset dense in $A$ , then $A$ is similar to some subset of the set of real numbers $\mathbb {R}$ with the natural order.

?

Problem I.5.18

Show that $(\alpha^{*})^{*} = \alpha$ for any order type $\alpha$ .

?

Problem I.5.19

Show that $\pi^{*} = \pi$ , $\eta^{*} = \eta$ , $\lambda^{*} = \lambda$ , $\omega^{*} \neq \omega$ .

?

Problem I.5.20

(a)(b)

Prove that:

?

(a)

for any order types $\alpha$ and $\beta$ the order types $\alpha + \beta$ and $\alpha \cdot \beta$ exist and are uniquely determined;

(b)

for any linearly ordered set $I$ and any family of order types $\left\{ \alpha_{i}\right\}_{i \in I}$ , the order type $\sum_{i \in I} \alpha_{i}$ exists and is uniquely determined.

Problem I.5.21

Give an example of order types $\alpha$ and $\beta$ such that

\alpha + \beta \neq \beta + \alpha .

?

Problem I.5.22

Prove that:

?

(a)

$\alpha + (\beta + \gamma ) = (\alpha + \beta ) + \gamma$ ;

(b)

$\alpha + 0 = 0 + \alpha = \alpha$ ;

(c)

$2 + 3 = 5$ ;

(d)

$1 + \omega = \omega$ , but $\omega + 1 \neq \omega$ ;

(e)

$\omega^{*} + \omega = \pi$ ;

(f)

$\eta + \eta = \eta$ ;

(g)

$\lambda + 1 + \lambda = \lambda$ ;

(h)

$\lambda + \lambda \neq \lambda$ ;

(i)

$1 + \lambda + 1$ is the order type of the segment $[a, b]$ for $a < b$ .

Problem I.5.23

Give an example of order types $\alpha$ and $\beta$ such that

\alpha \cdot \beta \neq \beta \cdot \alpha .

?

Problem I.5.24

Prove that:

?

(a)

$\alpha \cdot (\beta \cdot \gamma ) = (\alpha \cdot \beta ) \cdot \gamma$ ;

(b)

$\alpha \cdot 0 = 0 \cdot \alpha = 0$ ;

(c)

$\alpha \cdot 1 = 1 \cdot \alpha = \alpha$ ;

(d)

$2 \cdot 2 = 4$ ;

(e)

$\eta^{2} = \eta$ ;

(f)

$\omega \cdot \eta \neq \omega \cdot (\eta + 1)$ .

Problem I.5.25

Construct sets of order types $\omega^{2}, \omega^{3}, \omega^{4}, \ldots$

?

Problem I.5.26

(a)(b)

?

(a)

Prove that for any order types $\alpha$ , $\beta$ , and $\gamma$

\alpha \cdot (\beta + \gamma ) = \alpha \cdot \beta + \alpha \cdot \gamma .

(b)

Give an example of order types $\alpha$ , $\beta$ , and $\gamma$ such that

(\alpha + \beta ) \cdot \gamma \neq \alpha \cdot \gamma + \beta \cdot \gamma .

Problem I.5.27

Let $J$ and $I$ be linearly ordered sets, and $\left\{ B_{i}\right\}_{i \in I}$ a family of pairwise disjoint subsets of the set $J$ such that $\bigcup_{i \in I} B_{i} = J$ . Prove that if $\overline{\overline{J}} = \sum_{i \in I} \overline{\overline{B_{i}}}$ , then for any family of ordinal numbers $\left\{ \alpha_{j}\right\}_{j \in J}$ we have $\sum_{j \in J} \alpha_{j} = \sum_{i \in I} \left(\sum_{j \in B_{i}} \alpha_{j}\right)$ .

?

Problem I.5.28

Prove that $\alpha \cdot \beta = \sum_{b \in B} \alpha_{b}$ , where $\alpha_{b} = \alpha$ for all $b \in B$ and $\overline{\overline{B}} = \beta$ .

?

Problem I.5.29

(a)(b)(c)

Prove that:

?

(a)

$(\alpha + \beta )^{*} = \beta^{*} + \alpha^{*}$ ;

(b)

$(\alpha \cdot \beta )^{*} = \alpha^{*} \cdot \beta^{*}$ ;

(c)

$\left(\sum_{i \in I} \alpha_{i}\right)^{*} = \sum_{i \in I^{*}} \alpha_{i}^{*}$ , where $I$ is a linearly ordered set, and $I^{*}$ is the set $I$ with the dual order.

Problem I.5.30

(a)(b)(c)(d)

Prove that:

?

(a)

every finite linearly ordered set is well-ordered;

(b)

the set $\mathbb {N}$ , where $0 < 1 < 2 < \ldots$ , is well-ordered;

(c)

the set $\mathbb {N}$ , where $0 < 2 < 4 < \ldots < 1 < 3 < 5 < \ldots$ , is well-ordered;

(d)

the set $\mathbb {N}$ , where $\ldots < 3 < 2 < 1 < 0$ , is not well-ordered.

Problem I.5.31

(a)(b)(c)(d)

Are the following sets well-ordered:

?

(a)

the set of integers with their natural order;

(b)

the set $\mathbb {Q}$ of rational numbers with the usual order $\leq$ ;

(c)

the set $\mathbb {R}$ of real numbers with the usual order $\leq$ ;

(d)

the set of numbers of the form $1 - \frac{1}{n}$ , where $n$ is a positive integer, with the usual order $\leq$ ?

Problem I.5.32

(a)(b)

Prove that:

?

(a)

every nonempty well-ordered set has a least element;

(b)

every subset of a well-ordered set is well-ordered.

Problem I.5.33

Prove that if $A \sim B$ and $A$ is well-ordered, then $B$ can be well-ordered so that $A \simeq B$ .

?

Problem I.5.34

Show that if $A$ is a well-ordered set, then every element of the set $A$ , except the greatest one, has an immediate successor (see problem I.5.11).

?

Problem I.5.35

Can an infinite decreasing chain of elements $x_{1} > x_{2} > x_{3} > \ldots$ be extracted from a well-ordered set?

?

Problem I.5.36

Prove that a linearly ordered set is well-ordered if and only if it contains no subset of type $\omega^{*}$ .

?

Problem I.5.37

Let $A$ be a well-ordered set. Prove that there is no monotone one-to-one correspondence $f: A \rightarrow A$ such that $f(a) < a$ for some element $a \in A$ .

?

Problem I.5.38

Prove that a well-ordered set cannot be similar to its own segment or to a part of its own segment.

?

Problem I.5.39

Prove that two distinct segments of a well-ordered set cannot be similar.

?

Problem I.5.40

Prove that there exists at most one isomorphism between two well-ordered sets.

?

Problem I.5.41

Prove that of two well-ordered sets, one is similar to the other or to a segment of it.

?

Problem I.5.42

Prove that a linearly ordered set is finite if and only if it is well-ordered with respect to both the given order and the dual order.

?

Problem I.5.43

Let $A$ be a well-ordered set, $B \subseteq A$ , and suppose that for every element $x \in A$ the set $B$ satisfies the condition: if $A_{x} \subseteq B$ , then $x \in B$ . Prove that $B = A$ (the principle of transfinite induction).

?

Problem I.5.44

(a)(b)

Let $\alpha$ , $\beta$ be arbitrary ordinal numbers. Prove that:

?

(a)

$\alpha < \beta$ or $\beta < \alpha$ or $\alpha = \beta$ ;

(b)

of the conditions listed above, only one holds for $\alpha$ and $\beta$ .

Problem I.5.45

Let $W_{\alpha } = \left\{ \beta \mid \beta < \alpha \right\}$ , where $\alpha$ and $\beta$ are ordinal numbers. Show that $\overline{\overline{W_{\alpha }}} = \alpha$ .

?

Problem I.5.46

Prove that every set of ordinal numbers is well-ordered.

?

Problem I.5.47

(a)(b)

Prove that for any set of ordinal numbers $S$ :

?

(a)

there exists an ordinal number greater than all numbers in $S$ ;

(b)

among the ordinal numbers not belonging to the set $S$ there exists a least one.

Problem I.5.48

Prove that there does not exist a set containing all ordinal numbers.

?

Problem I.5.49

Prove that $\alpha + 1$ is the ordinal number immediately following $\alpha$ (see problem I.5.11).

?

Problem I.5.50

Prove that for any ordinal number $\alpha$ exactly one of the following holds:

$\alpha = 0$ ;
the set $\left\{ \beta \mid \beta \text{ is an ordinal number and } \beta < \alpha \right\}$ has a maximal element;
$\alpha$ is a limit ordinal number.

?

Problem I.5.51

Prove that every ordinal number can be represented in the form $\alpha + n$ , where $\alpha$ is a limit ordinal number or $0$ , and $n$ is a natural number.

?

Problem I.5.52

(a)(b)(c)

Prove that:

?

(a)

the sum of two ordinal numbers is an ordinal number;

(b)

the product of two ordinal numbers is an ordinal number;

(c)

an ordered sum of ordinal numbers, where the index set is well-ordered, is an ordinal number.

Problem I.5.53

Let $I$ and $\left\{ A_{i}\right\}_{i \in I}$ be linearly ordered. Prove that if $A_{i} \neq \emptyset$ and $\sum_{i \in I} \overline{\overline{A_{i}}}$ is an ordinal number, then $I$ and all the $A_{i}$ are well-ordered.

?

Problem I.5.54

Prove that:

?

(a)

if $A$ and $B$ are well-ordered and $A \subseteq B$ , then $\overline{\overline{A}} \leq \overline{\overline{B}}$ ;

(b)

$\alpha \leq \alpha + \gamma$ , $\alpha \leq \gamma + \alpha$ ;

(c)

$\alpha < \beta \Leftrightarrow \gamma + \alpha < \gamma + \beta$ ;

(d)

$\alpha \leq \beta \Rightarrow \alpha + \gamma \leq \beta + \gamma$ ;

(e)

$\gamma + \alpha = \gamma + \beta \Rightarrow \alpha = \beta$ ;

(f)

$\alpha + \gamma < \beta + \gamma \Rightarrow \alpha < \beta$ .

Problem I.5.55

Give an example of ordinal numbers $\alpha$ , $\beta$ , and $\gamma$ such that

\alpha \neq \beta \text{ and } \alpha + \gamma = \beta + \gamma .

?

Problem I.5.56

Prove that:

?

(a)

$\alpha \leq \beta \Rightarrow \alpha \cdot \gamma \leq \beta \cdot \gamma$ ;

(b)

$\alpha < \beta \Rightarrow \gamma \cdot \alpha < \gamma \cdot \beta$ , if $\gamma \neq 0$ ;

(c)

$\gamma \cdot \alpha < \gamma \cdot \beta \Rightarrow \alpha < \beta$ ;

(d)

$\gamma \cdot \alpha = \gamma \cdot \beta \Rightarrow \alpha = \beta$ , if $\gamma \neq 0$ ;

(e)

$\alpha \cdot \gamma < \beta \cdot \gamma \Rightarrow \alpha < \beta$ .

Problem I.5.57

(a)(b)(c)(d)

Let $\beta \leq \alpha$ . An ordinal number $\gamma$ is called the difference of $\alpha$ and $\beta$ and is denoted by $\alpha - \beta$ if $\alpha = \beta + \gamma$ .

Prove that:

?

(a)

$\alpha - \beta$ exists and is unique;

(b)

$\gamma \leq \beta < \alpha \Rightarrow \beta - \gamma < \alpha - \gamma$ ;

(c)

$\gamma \leq \beta \leq \alpha \Rightarrow \alpha - \beta \leq \alpha - \gamma$ ;

(d)

$\beta \leq \alpha \Rightarrow \gamma \cdot (\alpha - \beta ) = \gamma \cdot \alpha - \gamma \cdot \beta$ .

Problem I.5.58

(a)(b)(c)

Prove that:

?

(a)

if $\alpha_{1} + \beta_{1} = \alpha_{2} + \beta_{2}$ and $\beta_{2} < \beta_{1}$ , then $\alpha_{1} < \alpha_{2}$ ;

(b)

if $\gamma < \alpha^{\beta }$ , then there exist unique $\delta$ and $\varepsilon$ such that $\delta < \alpha$ , $\varepsilon < \beta$ , and $\gamma = \alpha \cdot \varepsilon + \delta$ ;

(c)

if $\beta > 0$ , then for any $\alpha$ there exist unique $\gamma$ and $\delta$ such that $\delta < \beta$ and $\alpha = \beta \cdot \gamma + \delta$ (the division algorithm).

Problem I.5.59

Prove that for any ordinal numbers $\alpha_{0}$ and $\alpha_{1}$ , if $\alpha_{0} \neq 0$ and $\alpha_{1} \neq 0$ , then there exist a natural number $n$ and ordinal numbers $\alpha_{2}, \ldots , \alpha_{n}, \beta_{1}, \beta_{2}, \ldots , \beta_{n}$ such that $\alpha_{1} > \alpha_{2} > \ldots > \alpha_{n} > 0$ and $\alpha_{0} = \alpha_{1} \cdot \beta_{1} + \alpha_{2}$ , $\alpha_{1} = \alpha_{2} \cdot \beta_{2} + \alpha_{3}, \ldots , \alpha_{n-2} = \alpha_{n-1} \cdot \beta_{n-1} + \alpha_{n}$ , $\alpha_{n-1} = \alpha_{n} \cdot \beta_{n}$ (the Euclidean algorithm).

?

Problem I.5.60

Let a property $P$ be such that for any ordinal number $\alpha$ , if all ordinal numbers $\beta < \alpha$ have the property $P$ , then $\alpha$ has the property $P$ . Prove that all ordinal numbers have the property $P$ (the principle of transfinite induction for ordinal numbers).

?

Problem I.5.61

Prove that for any ordinal numbers $\alpha$ and $\beta$ , $\alpha^{\beta }$ exists and is unique.

?

Problem I.5.62

Construct a set of order type $\omega^{\omega }$ .

?

Problem I.5.63

(a)(b)(c)

Prove that:

?

(a)

if $\alpha < \beta$ and $\gamma > 1$ , then $\gamma^{\alpha } < \gamma^{\beta }$ ;

(b)

$\alpha^{\beta +\gamma } = \alpha^{\beta } \cdot \alpha^{\gamma }$ ;

(c)

$(\alpha^{\beta })^{\gamma } = \alpha^{\beta \cdot \gamma }$ .

Problem I.5.64

(a)(b)(c)(d)

Prove that:

?

(a)

if $\omega^{\gamma } = \alpha + \beta$ and $\beta \neq 0$ , then $\beta = \omega^{\gamma }$ ;

(b)

if $\alpha > 1$ and $\beta \geq 1$ , then $\alpha^{\beta } \geq \alpha \cdot \beta$ ;

(c)

if $\alpha > 1$ and $\beta \geq 1$ , then there exist unique $\xi , \gamma$ , and $\delta$ such that

\beta = \alpha ^{\xi } \cdot \gamma + \delta \text{ and } \gamma < \alpha , \; \delta < \alpha ^{\xi };

(d)

if $\gamma > 1$ and $1 \leq \alpha < \gamma^{\delta }$ , then there exist a natural number $n$ and sequences of ordinal numbers $\beta_{1}, \beta_{2}, \ldots , \beta_{n}$ and $\delta_{1}, \delta_{2}, \ldots , \delta_{n}$ such that

\alpha = \gamma ^{\delta _{1}} \cdot \beta _{1} + \gamma ^{\delta _{2}} \cdot \beta _{2} + \ldots + \gamma ^{\delta _{n}} \cdot \beta _{n},

\delta > \delta _{1} > \delta _{2} > \ldots > \delta _{n} \text{ and } 0 \leq \beta _{i} < \gamma \text{ for } i = 1, 2, \ldots

Problem I.5.65

A set $S$ is called transitive if the relation

X \leq Y \Leftrightarrow (X = Y \text{ or } X \in Y)

well-orders $S$ , $\emptyset \in S$ , and $X \in Y$ , $Y \in S$ imply $X \in S$ . Prove that for any ordinal number $\alpha \geq 0$ there exists a unique transitive set ordered by type $\alpha$ .

?

Problem I.5.66

The following assertion is called the axiom of choice.

Axiom of choice. Let $X_{a}$ be a nonempty set for every $a \in A$ . Then there exists a choice function $f: A \rightarrow \bigcup_{a \in A} X_{a}$ such that $f(a) \in X_{a}$ for every $a \in A$ . Prove that each of the following assertions is equivalent to the axiom of choice.
Zorn’s lemma. A partially ordered set, each of whose linearly ordered subsets has an upper bound, contains a maximal element.
The Kuratowski–Hausdorff maximality principle. Every chain of a partially ordered set is contained in some maximal chain.
Zermelo’s axiom. For any family $S$ of nonempty pairwise disjoint sets there exists a set $C$ such that $A \cap C$ consists of exactly one point for every $A \in S$ .
Zermelo’s theorem. Every set can be well-ordered.
The Teichmüller–Tukey lemma. Every family of sets having finite character has a maximal element. (A family $S$ of sets has finite character if it satisfies the condition: $X \in S \Leftrightarrow$ every finite subset of the set $X$ belongs to $S$ .)

?

Problem I.5.67

Let $A$ be a partially ordered set in which every chain has an upper bound, and $a \in A$ . Prove that there exists a maximal element $m \in A$ such that $m \geq a$ .

?

Problem I.5.68

Let $A$ be a set of subsets of a set $B$ such that for every chain $C$ (ordered by inclusion) the union of the sets from $C$ belongs to $A$ . Prove that $A$ then has a maximal element.

?

Problem I.5.69

Prove that for every partial order $R$ on a set $A$ there exists a linear order $L$ on the set $A$ such that $R \subseteq L$ .

?