All textbooks/Problems in Set Theory, Mathematical Logic and the Theory of Algorithms

Part I

Part I. Set Theory

[311/75%]

Show

LaTeX

Show LaTeX

On this page

I.1 · Operations on Sets

I.2 · Relations and Functions

I.3 · Special Binary Relations

I.4 · Cardinal Numbers

I.5 · Ordinal Numbers

I.6 · Operations on Cardinal Numbers

Chapter I.1Operations on Sets[41/63%]

Problem I.1.1

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

Prove:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$A \subseteq A$ (reflexivity);

(b)

if $A \subseteq B$ and $B \subseteq C$ , then $A \subseteq C$ (transitivity);

(c)

$A \cap B \subseteq A \subseteq A \cup B$ ;

(d)

$A \cap B \subseteq B \subseteq A \cup B$ ;

(e)

$A \setminus B \subseteq A$ .

Problem I.1.2

Prove that if $A$ is the set of roots of the equation $x^{2} - 7x + 6 = 0$ and $B = \left\{ 1, 6\right\}$ , then $A = B$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.3

Prove that $\emptyset \neq \left\{ \emptyset \right\}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.4

Prove that $\left\{ \left\{ 1, 2\right\} , \left\{ 2, 3\right\} \right\} \neq \left\{ 1, 2, 3\right\}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.5

(a)(b)(c)

Prove that for any $A$ :

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\emptyset \subseteq A \subseteq U$ ;

(b)

if $A \subseteq \emptyset$ , then $A = \emptyset$ ; if $U \subseteq A$ , then $A = U$ ;

(c)

$A \cup \emptyset = A$ , $A \cap \emptyset = \emptyset$ , $A \cup U = U$ , $A \cap U = A$ .

Problem I.1.6

Prove that there exists only one set with no elements.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.7

Do there exist sets $A$ , $B$ , and $C$ such that

A \cap B \neq \emptyset , \quad A \cap C = \emptyset , \quad (A \cap B) \setminus C = \emptyset \text{?}

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.8

Prove that the set of all roots of the polynomial $\alpha (x) = \beta (x) \cdot \gamma (x)$ is the union of the sets of roots of the polynomials $\beta (x)$ and $\gamma (x)$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.9

Prove that the intersection of the sets of real roots of the polynomials $\alpha (x)$ and $\beta (x)$ with real coefficients coincides with the set of all real roots of the polynomial $\gamma (x) = \alpha^{2}(x) + \beta^{2}(x)$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.10

Prove that

A \subseteq B \Leftrightarrow A \cup B = B \Leftrightarrow A \cap B = A \Leftrightarrow A \setminus B = \emptyset \Leftrightarrow (-A) \cup B = U.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.11

(a)(b)(c)(d)(e)(f)(g)(h)

Prove the following identities:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$A \cup A = A \cap A = A$ ;

(b)

$A \cap B = B \cap A$ ;

(c)

$A \cup B = B \cup A$ ;

(d)

$A \cap (B \cap C) = (A \cap B) \cap C$ ;

(e)

$A \cup (B \cup C) = (A \cup B) \cup C$ ;

(f)

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ ;

(g)

$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ ;

(h)

$(A \cap B) \cup (C \cap D) = (A \cup C) \cap (B \cup C) \cap (A \cup D) \cap (B \cup D)$ .

Problem I.1.12

(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(q)(r)

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

(n)

(o)

(p)

(q)

(r)

Problem I.1.13

(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

Problem I.1.14

(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

Problem I.1.15

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$(A_{1} \cup \ldots \cup A_{n}) \symdiff (B_{1} \cup \ldots \cup B_{n}) \subseteq (A_{1} \symdiff B_{1}) \cup \ldots \cup (A_{n} \symdiff B_{n})$ ;

(b)

$(A_{1} \cap \ldots \cap A_{n}) \symdiff (B_{1} \cap \ldots \cap B_{n}) \subseteq (A_{1} \symdiff B_{1}) \cup \ldots \cup (A_{n} \symdiff B_{n})$ .

Problem I.1.16

(a)(b)(c)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$A \symdiff B = \emptyset \Leftrightarrow A = B$ ;

(b)

$A \cap B = \emptyset \Rightarrow A \cup B = A \symdiff B$ ;

(c)

$A \symdiff B = C \Leftrightarrow B \symdiff C = A \Leftrightarrow C \symdiff A = B$ .

Problem I.1.17

(a)(b)(c)

Define the operations $\cup , \cap , \setminus$ in terms of:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\symdiff , \cap$ ;

(b)

$\symdiff , \cup$ ;

(c)

$\setminus , \symdiff$ .

Problem I.1.18

(a)(b)

Prove that it is impossible to define:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\setminus$ in terms of $\cap$ and $\cup$ ;

(b)

$\cup$ in terms of $\cap$ and $\setminus$ .

Problem I.1.19

Prove that sets form a ring without identity, where $\symdiff$ plays the role of addition and $\cap$ plays the role of multiplication. What plays the role of subtraction in this ring?

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.20

Find all subsets of the sets $\emptyset$ , $\left\{ \emptyset \right\}$ , $\left\{ x\right\}$ , $\left\{ 1, 2\right\}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.21

(a)(b)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Prove that a set of $n$ elements has $2^{n}$ subsets.

(b)

How many subsets of $k$ elements does a set of $n$ elements have $(k \leq n)$ ?

Problem I.1.22

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

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$P(A \cap B) = P(A) \cap P(B)$ ;

(b)

$P\left(\bigcap_{i \in I} A_{i}\right) = \bigcap_{i \in I} P(A_{i})$ ;

(c)

$P(A \cup B) = \left\{ A_{1} \cup B_{1} \mid A_{1} \in P(A) \text{ and } B_{1} \in P(B)\right\}$ ;

(d)

$P\left(\bigcup_{i \in I} A_{i}\right) = \bigcup_{i \in I} \left\{ B_{i} \mid B_{i} \in P(A_{i})\right\}$ .

Problem I.1.23

Prove that for any $a$ , $b$ , $c$ , $d$

\left\{ \left\{ a\right\} , \left\{ a, b\right\} \right\} = \left\{ \left\{ c\right\} , \left\{ c, d\right\} \right\} \Leftrightarrow a = c \text{ and } b = d.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.24

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

Which of the following statements hold for all $A$ , $B$ , and $C$ :

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if $A \in B$ and $B \in C$ , then $A \in C$ ?

(b)

if $A \subseteq B$ and $B \in C$ , then $A \in C$ ?

(c)

if $A \cap B \subseteq -C$ and $A \cup C \subseteq B$ , then $A \cap C = \emptyset$ ?

(d)

if $A \neq B$ and $B \neq C$ , then $A \neq C$ ?

(e)

if $A \subseteq -(B \cup C)$ and $B \subseteq -(A \cup C)$ , then $B = \emptyset$ ?

Problem I.1.25

Prove that for any $A_{1}, A_{2}, \ldots , A_{n}$ ,

\text{if } A_{1} \subseteq A_{2} \subseteq \ldots \subseteq A_{n} \subseteq A_{1}, \text{ then } A_{1} = A_{2} = \ldots = A_{n}.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.26

For every positive integer $n$ , exhibit a set $A_{n}$ of $n$ elements such that if $x, y \in A_{n}$ , then $x \in y$ or $y \in x$ or $x = y$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.27

Solve the system of equations

\begin{cases} A \cap X = B, \\ A \cup X = C, \end{cases}

where $A$ , $B$ , and $C$ are given sets and $B \subseteq A \subseteq C$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.28

Solve the system of equations

\begin{cases} A \setminus X = B, \\ X \setminus A = C, \end{cases}

where $A$ , $B$ , and $C$ are given sets and $B \subseteq A$ , $A \cap C = \emptyset$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.29

(a)(b)

Let systems of sets $\left\{ A_{i}\right\}_{i \in I}$ and $\left\{ B_{i}\right\}_{i \in I}$ be given, where $I$ is some set. Solve the systems of equations:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$A_{i} \cap X = B_{i}$ , $i \in I$ ;

(b)

$A_{i} \cup X = B_{i}$ , $i \in I$ .

For which $A_{i}$ and $B_{i}$ do these systems have solutions?

Problem I.1.30

Solve the system of equations

\begin{cases} A \setminus X = B, \\ A \cup X = C, \end{cases}

where $A$ , $B$ , and $C$ are given sets and $B \subseteq A \subseteq C$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.31

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

Show that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$A = B \Leftrightarrow (A \setminus B) \cup (B \setminus A) = \emptyset$ ;

(b)

any equation in the set $X$ whose right-hand side is $\emptyset$ is equivalent to the equation $(A \cap X) \cup [B \cap (-X)] = \emptyset$ , where $A$ and $B$ are some sets whose expressions do not contain the symbol $X$ ;

(c)

the system of equations

\begin{cases} A \cap X = \emptyset , \\ B \cap (-X) = \emptyset \end{cases}

has a solution if and only if $B \subseteq -A$ ; under this condition, a solution of the system is any set $X$ such that

B \subseteq X \subseteq -A;

(d)

describe a method for solving a system of equations with one unknown.

Problem I.1.32

(a)(b)(c)

Using the method of problem I.1.31, solve the following systems:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\begin{cases} A \cup X = B \cap X, \\ A \cap X = C \cup X; \end{cases}$

(b)

$\begin{cases} A \setminus X = X \setminus B, \\ X \setminus A = C \setminus X; \end{cases}$

(c)

$\begin{cases} A \cap X = B \setminus X, \\ C \cup X = X \setminus A. \end{cases}$

For which $A$ , $B$ , and $C$ do these systems have a solution?

Problem I.1.33

(a)(b)(c)

Prove that every set is:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

the union of all its subsets;

(b)

the union of all its finite subsets;

(c)

the union of all its singleton subsets.

Problem I.1.34

Suppose we have a sequence of sets

X_{0} \supseteq X_{1} \supseteq X_{2} \supseteq \ldots \supseteq X_{n} \supseteq \ldots

Prove that the intersection of any infinite subsequence of these sets coincides with the intersection of the whole sequence.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.35

Suppose we have a sequence of sets

X_{0} \subseteq X_{1} \subseteq X_{2} \subseteq \ldots \subseteq X_{n} \subseteq \ldots

Prove that the union of any infinite subsequence of these sets coincides with the union of the whole sequence.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.36

(a)(b)(c)(d)(e)(f)(g)

Prove the following identities:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\bigcup_{k \in K} \bigcup_{t \in T} A_{kt} = \bigcup_{t \in T} \bigcup_{k \in K} A_{kt}$ ;

(b)

$\bigcap_{k \in K} \bigcap_{t \in T} A_{kt} = \bigcap_{t \in T} \bigcap_{k \in K} A_{kt}$ ;

(c)

$-\left(\bigcup_{k \in K} A_{k}\right) = \bigcap_{k \in K} (-A_{k})$ ;

(d)

$-\left(\bigcap_{k \in K} A_{k}\right) = \bigcup_{k \in K} (-A_{k})$ ;

(e)

$\bigcup_{k \in K} A_{k} \cup \bigcup_{k \in K} B_{k} = \bigcup_{k \in K} (A_{k} \cup B_{k})$ ;

(f)

$\bigcup_{k \in K} (B \cap A_{k}) = B \cap \left(\bigcup_{k \in K} A_{k}\right)$ ;

(g)

$\bigcap_{k \in K} (B \cup A_{k}) = B \cup \left(\bigcap_{k \in K} A_{k}\right)$ .

Problem I.1.37

(a)(b)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Prove that for any $K$ , $T$ , $A_{kt}$

\bigcup _{k \in K} \bigcap _{t \in T} A_{kt} \subseteq \bigcap _{t \in T} \bigcup _{k \in K} A_{kt}.

(b)

Prove that in the assertion (a) the inclusion cannot be replaced by equality.

Problem I.1.38

(a)(b)(c)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if $A_{t} \subseteq B$ for all $t \in T$ , then $\bigcup_{t \in T} A_{t} \subseteq B$ ;

(b)

if $B \subseteq A_{t}$ for all $t \in T$ , then $B \subseteq \bigcap_{t \in T} A_{t}$ ;

(c)

if $A_{t} \subseteq B_{t}$ for all $t \in T$ , then $\bigcup_{t \in T} A_{t} \subseteq \bigcup_{t \in T} B_{t}$ and $\bigcap_{t \in T} A_{t} \subseteq \bigcap_{t \in T} B_{t}$ .

Problem I.1.39

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\bigcup_{t \in T} A_{t}$ is the smallest set containing all the sets $A_{t}$ ;

(b)

$\bigcap_{t \in T} A_{t}$ is the largest set contained in all the sets $A_{t}$ .

Problem I.1.40

Prove that if $\left(\bigcap_{n \in \mathbb {N} \setminus \left\{ 0\right\} } A_{n}\right) \cap \left(\bigcap_{n \in \mathbb {N} \setminus \left\{ 0\right\} } B_{n}\right) = \emptyset$ , then

\bigcap _{n \in \mathbb {N} \setminus \left\{ 0\right\} } A_{n} \subseteq \bigcup _{n \in \mathbb {N} \setminus \left\{ 0\right\} } [A_{n} \cap (B_{n-1} \setminus B_{n})],

where

\left(\bigcup _{n \in \mathbb {N} \setminus \left\{ 0\right\} } A_{n}\right) \cup \left(\bigcup _{n \in \mathbb {N} \setminus \left\{ 0\right\} } B_{n}\right) \subseteq B_{0}.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.1.41

Prove that for any system of sets $A_{0}, \ldots , A_{n}, \ldots$ there exists a system of pairwise disjoint sets $B_{0}, \ldots , B_{n}, \ldots$ such that $\bigcup_{n \in \mathbb {N}} A_{n} = \bigcup_{n \in \mathbb {N}} B_{n}$ and $B_{n} \subseteq A_{n}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Chapter I.2Relations and Functions[51/61%]

Problem I.2.1

(a)(b)

Prove that there exist $A$ , $B$ , and $C$ such that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$A \times B \neq B \times A$ ;

(b)

$A \times (B \times C) \neq (A \times B) \times C$ .

Problem I.2.2

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

Find a geometric interpretation of the following sets:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$[a, b] \times [c, d]$ , where $[a, b]$ and $[c, d]$ are segments of the real line $\mathbb {R}$ ;

(b)

$[a, b]^{2}$ ;

(c)

$[a, b]^{3}$ ;

(d)

$\mathbb {R}^{n}$ .

Problem I.2.3

(a)(b)

Prove that if $A$ , $B$ , $C$ , and $D$ are nonempty, then:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$A \subseteq B$ and $C \subseteq D \Leftrightarrow A \times C \subseteq B \times D$ ;

(b)

$A = B$ and $C = D \Leftrightarrow A \times C = B \times D$ .

Problem I.2.4

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$(A \cap B) \times (C \cap D) = (A \times C) \cap (B \times D)$ ;

(b)

$\bigcap_{i \in I} A_{i} \times \bigcap_{i \in I} B_{i} = \bigcap_{i \in I} (A_{i} \times B_{i})$ .

Problem I.2.5

Prove that $(A \times B) \cup (C \times D) \subseteq (A \cup C) \times (B \cup D)$ . For which $A$ , $B$ , $C$ , and $D$ does equality hold?

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.6

(a)(b)(c)(d)(e)(f)(g)(h)(i)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$(A \cup B) \times C = (A \times C) \cup (B \times C)$ ;

(b)

$A \times (B \cup C) = (A \times B) \cup (A \times C)$ ;

(c)

$(A \cup B) \times (C \cup D) = (A \times C) \cup (B \times C) \cup (A \times D) \cup (B \times D)$ ;

(d)

$(A \setminus B) \times C = (A \times C) \setminus (B \times C)$ ;

(e)

$A \times (B \setminus C) = (A \times B) \setminus (A \times C)$ ;

(f)

$A \times B = (A \times D) \cap (C \times B)$ , where $A \subseteq C$ and $B \subseteq D$ ;

(g)

$U^{2} \setminus (A \times B) = [(U \setminus A) \times U] \cup [U \times (U \setminus B)]$ ;

(h)

$\bigcup_{k \in K} A_{k} \times \bigcup_{t \in T} B_{t} = \bigcup_{\langle k, t \rangle \in K \times T} (A_{k} \times B_{t})$ ;

(i)

$\bigcap_{k \in K} A_{k} \times \bigcap_{t \in T} B_{t} = \bigcap_{\langle k, t \rangle \in K \times T} (A_{k} \times B_{t})$ .

Problem I.2.7

Let $A, B \neq \emptyset$ and $(A \times B) \cup (B \times A) = (C \times D)$ . Prove that $A = B = C = D$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.8

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

Find $\delta R$ , $\rho R$ , $R^{-1}$ , $R \cdot R$ , $R \cdot R^{-1}$ , $R^{-1} \cdot R$ for the following relations:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$R = \left\{ \langle x, y \rangle \mid x, y \in \mathbb {N} \text{ and } x \text{ divides } y\right\}$ ;

(b)

$R = \left\{ \langle x, y \rangle \mid x, y \in \mathbb {N} \text{ and } y \text{ divides } x\right\}$ ;

(c)

$R = \left\{ \langle x, y \rangle \mid x, y \in \mathbb {R} \text{ and } x + y \leq 0\right\}$ ;

(d)

$R = \left\{ \langle x, y \rangle \mid x, y \in \mathbb {R} \text{ and } 2x \geq 3y\right\}$ ;

(e)

$R = \left\{ \langle x, y \rangle \mid x, y \in \left[-\frac{\pi }{2}, \frac{\pi }{2}\right] \text{ and } y \geq \sin x\right\}$ .

Problem I.2.9

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

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\delta R = \emptyset \Leftrightarrow R = \emptyset \Leftrightarrow \rho R = \emptyset$ ;

(b)

$\delta R^{-1} = \rho R$ , $\rho R^{-1} = \delta R$ ;

(c)

$\delta_{R_{1} \cdot R_{2}} = R_{1}^{-1}(\rho R_{1} \cap \delta R_{2})$ ;

(d)

$\rho_{R_{1} \cdot R_{2}} = R_{2}(\rho R_{1} \cap \delta R_{2})$ .

Problem I.2.10

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if $B \neq \emptyset$ , then $\delta_{A \times B} = A$ ;

(b)

if $A \neq \emptyset$ , then $\rho_{A \times B} = B$ .

Problem I.2.11

Let $R$ be a binary relation on $A$ . Prove that $R = i_{A}$ if and only if $R \cdot R_{1} = R_{1} \cdot R = R_{1}$ for every relation $R_{1}$ on $A$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.12

(a)(b)(c)(d)(e)(f)(g)

Prove that for any binary relations:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$R \cup R = R \cap R = R$ ;

(b)

$(R^{-1})^{-1} = R$ ;

(c)

$(R_{1} \cup R_{2})^{-1} = R_{1}^{-1} \cup R_{2}^{-1}$ ;

(d)

$(R_{1} \cap R_{2})^{-1} = R_{1}^{-1} \cap R_{2}^{-1}$ ;

(e)

$-R^{-1} = (-R)^{-1}$ ;

(f)

$\left(\bigcup_{i \in I} R_{i}\right)^{-1} = \bigcup_{i \in I} R_{i}^{-1}$ ;

(g)

$\left(\bigcap_{i \in I} R_{i}\right)^{-1} = \bigcap_{i \in I} R_{i}^{-1}$ .

Problem I.2.13

For which binary relations $R$ does $R^{-1} = -R$ hold?

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.14

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

Let $A$ and $B$ be finite sets consisting of $m$ and $n$ elements, respectively.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

How many binary relations are there between the elements of the sets $A$ and $B$ ?

(b)

How many functions are there from $A$ to $B$ ?

(c)

How many 1--1 functions are there from $A$ to $B$ ?

(d)

For which $m$ and $n$ does there exist a one-to-one correspondence between $A$ and $B$ ?

Problem I.2.15

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

Prove that for any binary relations:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$R_{1} \cdot (R_{2} \cdot R_{3}) = (R_{1} \cdot R_{2}) \cdot R_{3}$ ;

(b)

$(R_{1} \cdot R_{2})^{-1} = R_{2}^{-1} \cdot R_{1}^{-1}$ ;

(c)

$\left(\bigcup_{i \in I} R_{i}\right) \cdot Q = \bigcup_{i \in I} (R_{i} \cdot Q)$ ;

(d)

$Q \cdot \left(\bigcup_{i \in I} R_{i}\right) = \bigcup_{i \in I} (Q \cdot R_{i})$ .

Problem I.2.16

(a)(b)(c)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$Q \cdot \left(\bigcap_{i \in I} R_{i}\right) \subseteq \bigcap_{i \in I} (Q \cdot R_{i})$ ;

(b)

$\left(\bigcap_{i \in I} R_{i}\right) \cdot Q \subseteq \bigcap_{i \in I} (R_{i} \cdot Q)$ ;

(c)

in assertions (a) and (b) the inclusions cannot be replaced by equalities.

Problem I.2.17

Do binary relations form a group with respect to the operations $\cdot$ and ${}^{-1}$ ?

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.18

(a)(b)(c)

Prove that if $R_{1} \subseteq R_{2}$ , then:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$Q \cdot R_{1} \subseteq Q \cdot R_{2}$ ;

(b)

$R_{1} \cdot Q \subseteq R_{2} \cdot Q$ ;

(c)

$R_{1}^{-1} \subseteq R_{2}^{-1}$ .

Problem I.2.19

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if $B \neq \emptyset$ , then $B^{A} \neq \emptyset$ ;

(b)

$B^{A} \subseteq P(A \times B)$ .

Problem I.2.20

Establish a one-to-one correspondence between $A^{n}$ and $A^{l}$ for $l = \left\{ 1, \ldots , n\right\}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.21

Using the definition, describe the set $D(D^{D})$ , where $D$ is the set of real numbers.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.22

Prove that if $f$ is a function from $A$ to $B$ and $g$ is a function from $B$ to $C$ , then $f \cdot g$ is a function from $A$ to $C$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.23

(a)(b)

Let $f$ and $g$ be functions. Under what conditions is:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$f^{-1}$ a function;

(b)

$f \cdot g$ a 1--1 function?

Problem I.2.24

(a)(b)(c)

Let $A, B, A_{1}, B_{1}$ be sets such that $A$ is in one-to-one correspondence with $A_{1}$ , and $B$ with $B_{1}$ . Show that one can establish a one-to-one correspondence:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

between $A \times B$ and $A_{1} \times B_{1}$ ;

(b)

between $A^{B}$ and $A_{1}^{B_{1}}$ ;

(c)

between $A \cup B$ and $A_{1} \cup B_{1}$ , if $A \cap B = \emptyset$ and $A_{1} \cap B_{1} = \emptyset$ .

Problem I.2.25

(a)(b)(c)(d)(e)(f)(g)(h)

Prove that one can establish a one-to-one correspondence between the sets:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$A \times B$ and $B \times A$ ;

(b)

$A \times (B \times C)$ and $(A \times B) \times C$ ;

(c)

$(A \times B)^{C}$ and $A^{C} \times B^{C}$ ;

(d)

$(A^{B})^{C}$ and $A^{B \times C}$ ;

(e)

$A^{B \cup C}$ and $A^{B} \times A^{C}$ , if $B \cap C = \emptyset$ ;

(f)

$\prod_{i \in I} A_{i}$ and $\prod_{i \in I} A_{\varphi (i)}$ , where $\varphi$ is a permutation of the set $I$ ;

(g)

$\prod_{i \in I} A_{i}$ and $\prod_{k \in K} \left(\prod_{j \in T_{k}} A_{j}\right)$ , where $\bigcup_{k \in K} T_{k} = I$ and all the $T_{k}$ are pairwise disjoint;

(h)

$A^{I}$ and $\prod_{k \in K} A^{T_{k}}$ , where $\bigcup_{k \in K} T_{k} = I$ and all the $T_{k}$ are pairwise disjoint.

Problem I.2.26

Let $\varphi : A \rightarrow A$ be a permutation of the set $A$ . Prove that $\varphi^{-1}$ is a permutation of the set $A$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.27

Prove that the set of permutations of a set $A$ forms a group.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.28

(a)(b)(c)

Let $\varphi : A \rightarrow B$ be a one-to-one correspondence. Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\varphi^{-1}$ is a one-to-one correspondence between $B$ and $A$ ;

(b)

$\varphi^{-1} \cdot \varphi = i_{B}$ ;

(c)

$\varphi \cdot \varphi^{-1} = i_{A}$ .

Problem I.2.29

Prove that a relation $R \subseteq A \times B$ is a one-to-one correspondence between $A$ and $B$ if and only if $R \cdot R^{-1} = i_{A}$ and $R^{-1} \cdot R = i_{B}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.30

Prove that the union (intersection) of two functions $f_{1}$ and $f_{2}$ from $A$ to $B$ is a function from $A$ to $B$ if and only if $f_{1} = f_{2}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.31

(a)(b)

Prove that for any function $f$ :

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$f(A \cup B) = f(A) \cup f(B)$ ;

(b)

$f\left(\bigcup_{i \in I} A_{i}\right) = \bigcup_{i \in I} f(A_{i})$ .

Problem I.2.32

(a)(b)

Prove that for any function $f$ :

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$f(A \cap B) \subseteq f(A) \cap f(B)$ ;

(b)

$f\left(\bigcap_{i \in I} A_{i}\right) \subseteq \bigcap_{i \in I} f(A_{i})$ ,

and these inclusions cannot be replaced by equalities.

Problem I.2.33

Prove that $f$ satisfies the condition

f(A \cap B) = f(A) \cap f(B) \text{ for any } A \text{ and } B

if and only if $f$ is a 1--1 function.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.34

Prove that $f(A) \setminus f(B) \subseteq f(A \setminus B)$ for any function $f$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.35

Prove that if, in the previous problem, $f$ is a 1--1 function, then equality holds.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.36

Prove that if $A \subseteq B$ , then $f(A) \subseteq f(B)$ for any function $f$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.37

Prove that for any function $f$

f(A) = \emptyset \Leftrightarrow A \cap \delta f = \emptyset .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.38

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

Prove the following identities for any function $f$ :

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)$ ;

(b)

$f^{-1}\left(\bigcup_{i \in I} A_{i}\right) = \bigcup_{i \in I} f^{-1}(A_{i})$ ;

(c)

$f^{-1}(A \cap B) = f^{-1}(A) \cap f^{-1}(B)$ ;

(d)

$f^{-1}\left(\bigcap_{i \in I} A_{i}\right) = \bigcap_{i \in I} f^{-1}(A_{i})$ ;

(e)

$f^{-1}(A \setminus B) = f^{-1}(A) \setminus f^{-1}(B)$ .

Problem I.2.39

Prove that if $A \subseteq B$ , then $f^{-1}(A) \subseteq f^{-1}(B)$ for any function $f$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.40

Prove that for any function $f$

f^{-1}(A) = \emptyset \Leftrightarrow A \cap \rho f = \emptyset .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.41

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

Prove that if $A \subseteq \delta f$ and $B \subseteq \rho f$ , then:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$A \subseteq f^{-1}(f(A))$ ;

(b)

$f(f^{-1}(B)) = B$ ;

(c)

$f(A) \cap B = f(A \cap f^{-1}(B))$ ;

(d)

$f(A) \cap B = \emptyset \Leftrightarrow A \cap f^{-1}(B) = \emptyset$ ;

(e)

$f(A) \subseteq B \Leftrightarrow A \subseteq f^{-1}(B)$ .

Problem I.2.42

Let $f: A \rightarrow B$ . Define $f_{*}: P(A) \rightarrow P(B)$ , $f^{*}: P(B) \rightarrow P(A)$ by $f_{*}(X) = \left\{ f(x) \mid x \in X\right\}$ and $f^{*}(Y) = \left\{ x \mid f(x) \in Y\right\}$ . Under what conditions is $f^{*} \cdot f_{*} = i_{P(B)}$ ? Under what conditions is $f_{*} \cdot f^{*} = i_{P(A)}$ ?

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.43

(a)(b)

In the notation of the previous problem, prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$f^{*}(X \cap Y) = f^{*}(X) \cap f^{*}(Y)$ ;

(b)

$(f \cdot g)^{*}(X) = f^{*}(g^{*}(X))$ .

Problem I.2.44

Let $U$ be a nonempty set. For any subset $A$ of the set $U$ , denote by $\chi_{A}^{U}$ the following function (the characteristic function of the set $A$ ):

\chi _{A}^{U} = \begin{cases} 0, & \text{if } x \in A, \\ 1, & \text{if } x \in U \setminus A. \end{cases}

Define a function $f: P(U) \rightarrow \left\{ 0, 1\right\}^{U}$ by the condition $f(A) = \chi_{A}^{U}$ for every $A \in P(U)$ . Prove that $f$ is a one-to-one correspondence between $P(U)$ and $\left\{ 0, 1\right\}^{U}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.45

(a)(b)(c)(d)(e)(f)(g)(h)

Prove that the function $\chi_{A}^{U}$ introduced in the previous problem satisfies the following conditions:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\chi_{U}^{U}(x) = 0$ ;

(b)

$\chi_{\emptyset }^{U}(x) = 1$ ;

(c)

$\chi_{U \setminus A}^{U}(x) = 1 - \chi_{A}^{U}(x)$ ;

(d)

$\chi_{A \cup B}^{U}(x) = \chi_{A}^{U}(x) \cdot \chi_{B}^{U}(x)$ ;

(e)

$\chi_{A \cap B}^{U}(x) = \chi_{A}^{U}(x) + \chi_{B}^{U}(x) - \chi_{A}^{U}(x) \cdot \chi_{B}^{U}(x)$ ;

(f)

$\chi_{A \setminus B}^{U}(x) = 1 - \chi_{B}^{U}(x) + \chi_{A \cup B}^{U}(x)$ ;

(g)

if $A = \bigcup_{i \in I} A_{i}$ , then $\chi_{A}^{U}(x) = \min_{i \in I} \chi_{A_{i}}^{U}(x)$ ;

(h)

if $A = \bigcap_{i \in I} A_{i}$ , then $\chi_{A}^{U}(x) = \max_{i \in I} \chi_{A_{i}}^{U}(x)$ .

Problem I.2.46

(a)(b)

Prove the properties of complete distributivity:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\bigcup_{i \in I} \bigcap_{j \in J} A_{ij} = \bigcap_{f \in J^{I}} \bigcup_{i \in I} A_{i f(i)}$ ;

(b)

$\bigcap_{i \in I} \bigcup_{j \in J} A_{ij} = \bigcup_{f \in J^{I}} \bigcap_{i \in I} A_{i f(i)}$ .

Problem I.2.47

Prove that $A^{I} = \prod_{i \in I} A_{i}$ , where $A_{i} = A$ for all $i \in I$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.48

(a)(b)

Let $A_{i} \subseteq X_{i}$ . Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\prod_{i \in I} A_{i} = \bigcap_{i \in I} \prod_{j \in J} A_{ij}$ , where $A_{ii} = A_{i}$ , $A_{ij} = X_{j}$ for $i \neq j$ ;

(b)

$\prod_{i \in I} X_{i} \setminus \prod_{i \in I} A_{i} = \bigcup_{i \in I} \prod_{j \in J} B_{ij}$ , where $B_{ii} = X_{i} \setminus A_{i}$ , $B_{ij} = X_{j}$ for $i \neq j$ .

Problem I.2.49

(a)(b)(c)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\bigcap_{k \in K} \prod_{t \in T} A_{kt} = \prod_{t \in T} \bigcap_{k \in K} A_{kt}$ ;

(b)

if $A_{t_{1}} \cap A_{t_{2}} = \emptyset$ for $t_{1} \neq t_{2}$ , then one can establish a one-to-one correspondence between $B^{\left(\bigcup_{t \in T} A_{t}\right)}$ and $\prod_{t \in T} B^{A_{t}}$ ;

(c)

one can establish a one-to-one correspondence between $\left(\prod_{t \in T} B_{t}\right)^{A}$ and $\prod_{t \in T} B_{t}^{A}$ .

Problem I.2.50

Prove that if $A_{t} \neq \emptyset$ for all $t \in T$ , then $\prod_{t \in T} A_{t} \neq \emptyset$ (one of the formulations of the axiom of choice).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.2.51

Prove that one can establish a one-to-one correspondence between $\prod_{t \in T} A_{t}$ and $\left(\prod_{t_{1} \in T_{1}} A_{t_{1}}\right) \times \left(\prod_{t_{2} \in T_{2}} A_{t_{2}}\right)$ , if $T_{1} \cup T_{2} = T$ and $T_{1} \cap T_{2} = \emptyset$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Chapter I.3Special Binary Relations[72/71%]

Problem I.3.1

Prove that if the relations $R_{1}$ and $R_{2}$ are reflexive, then the relations $R_{1} \cup R_{2}$ , $R_{1} \cap R_{2}$ , $R_{1}^{-1}$ , $R_{1} \cdot R_{2}$ are reflexive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.2

Prove that if the relations $R_{1}$ and $R_{2}$ are irreflexive, then the relations $R_{1} \cup R_{2}$ , $R_{1} \cap R_{2}$ , $R_{1}^{-1}$ are irreflexive. Show that the product $R_{1} \cdot R_{2}$ of irreflexive relations need not be irreflexive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.3

Prove that if the relations $R_{1}$ and $R_{2}$ are symmetric, then the relations $R_{1} \cup R_{2}$ , $R_{1} \cap R_{2}$ , $R_{1}^{-1}$ , $R_{1} \cdot R_{2}^{-1}$ are symmetric.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.4

Prove that the product $R_{1} \cdot R_{2}$ of symmetric relations $R_{1}$ and $R_{2}$ is symmetric if and only if $R_{1} \cdot R_{2} = R_{2} \cdot R_{1}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.5

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if the relations $R_{1}$ and $R_{2}$ are antisymmetric, then $R_{1} \cap R_{2}$ and $R_{1}^{-1}$ are also antisymmetric;

(b)

the union $R_{1} \cup R_{2}$ of antisymmetric relations $R_{1}$ and $R_{2}$ on $A$ is antisymmetric if and only if $R_{1} \cdot R_{2}^{-1} \subseteq i_{A}$ .

Problem I.3.6

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

Construct a binary relation that is:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

reflexive, symmetric, not transitive;

(b)

reflexive, antisymmetric, not transitive;

(c)

reflexive, transitive, not symmetric;

(d)

antisymmetric, transitive, not reflexive.

Problem I.3.7

(a)(b)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Construct a binary relation that is symmetric, transitive, but not reflexive.

(b)

Prove that if $R$ is a transitive and symmetric relation on a set $A$ and $\delta R \cup \rho R = A$ , then $R$ is an equivalence on $A$ .

Problem I.3.8

Prove that any relation $R$ that is both symmetric and antisymmetric is transitive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.9

Prove that a relation $R$ on a set $A$ is simultaneously an equivalence and a partial order if and only if $R = i_{A}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.10

(a)(b)(c)

On the sets $\mathbb {N}$ and $\mathbb {N} \times \mathbb {N}$ define $R_{m}$ , $Q$ , $S$ as follows:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\langle a, b \rangle \in R_{m} \Leftrightarrow (a - b)$ is divisible by $m$ $(m > 0)$ ;

(b)

$\langle \langle a, b \rangle , \langle c, d \rangle \rangle \in Q \Leftrightarrow a + d = b + c$ ;

(c)

$\langle \langle a, b \rangle , \langle c, d \rangle \rangle \in S \Leftrightarrow$

\Leftrightarrow [((a \cdot d = b \cdot c) \text{ and } b \neq 0 \text{ and } d \neq 0) \text{ or } (a = c, b = 0, d = 0)].

Prove that $R_{m}$ , $Q$ , and $S$ are equivalence relations.

Problem I.3.11

(a)(b)

Let $A$ be the set of all lines in the plane. Are the following relations equivalences:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

parallelism of lines;

(b)

perpendicularity of lines?

Problem I.3.12

On the set $\mathbb {R}$ of real numbers define a relation $R$ as follows:

\alpha R \beta \Leftrightarrow (\alpha - \beta ) \text{ is a rational number}.

Prove that $R$ is an equivalence.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.13

(a)(b)

Prove that if $R$ is an equivalence, then:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$x \in [x]_{R}$ ;

(b)

$\langle x, y \rangle \in R \Leftrightarrow [x]_{R} = [y]_{R}$ .

Problem I.3.14

Prove that if $R$ is an equivalence, then $R^{-1}$ is also an equivalence.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.15

Let $R \subseteq A^{2}$ . Prove that

R \text{ is an equivalence} \Leftrightarrow (R \cdot R^{-1}) \cup i_{A} = R.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.16

(a)(b)

Prove that if $R_{1}$ and $R_{2}$ are equivalences on $A$ , then:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$R_{1} \cdot R_{2} = A^{2} \Leftrightarrow R_{1} = A^{2}$ ;

(b)

$R_{1} \cdot R_{2} = A^{2} \Leftrightarrow R_{2} \cdot R_{1} = A^{2}$ .

Problem I.3.17

Prove that there exists a one-to-one correspondence between the class of all partitions of a set $A$ into disjoint nonempty subsets and the family of all equivalence relations on $A$ . (A family $\left\{ A_{i}\right\}_{i \in I}$ is called a partition of $A$ if $\bigcup_{i \in I} A_{i} = A$ and the sets $A_{i}$ are pairwise disjoint.)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.18

Prove that $R$ is an equivalence relation on a set $A$ if and only if there exists a system $P$ of pairwise disjoint sets such that

R = \bigcup _{C \in P} C \times C \quad \text{and} \quad \bigcup _{C \in P} C = A.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.19

Let $f: A \rightarrow B$ be an arbitrary function. Put

Q = \left\{ \langle x, y \rangle \mid f(x) = f(y)\right\} .

Prove that $Q$ is an equivalence on $A$ and that the map $f$ admits a factorization

f = \varepsilon \cdot f_{1},

where $\varepsilon$ is the natural map of $A$ onto $A/Q = \left\{ [x]_{Q} \mid x \in A\right\}$ , i.e., $\varepsilon (x) = [x]_{Q}$ , and $f_{1}$ is a one-to-one correspondence between $A/Q$ and $f(A)$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.20

Prove that the intersection of any system of equivalences on a set $A$ is an equivalence on $A$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.21

Prove that the union $R_{1} \cup R_{2}$ of equivalences $R_{1}$ and $R_{2}$ is an equivalence if and only if $R_{1} \cup R_{2} = R_{1} \cdot R_{2}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.22

Prove that the product $R_{1} \cdot R_{2}$ of two equivalences $R_{1}$ and $R_{2}$ is an equivalence if and only if $R_{1} \cdot R_{2} = R_{2} \cdot R_{1}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.23

Prove that if $R_{1}$ and $R_{2}$ are equivalences and $R_{1} \cdot R_{2} = R_{2} \cdot R_{1}$ , then $R_{1} + R_{2} = R_{1} \cdot R_{2}$ , where $R_{1} + R_{2}$ is the smallest equivalence relation containing $R_{1} \cup R_{2}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.24

Prove that for every family of equivalences $\left\{ R_{i}\right\}_{i \in I}$ there exists an equivalence $Q$ such that $\bigcup_{i \in I} R_{i} \subseteq Q$ and, for every equivalence relation $R$ , if $\bigcup_{i \in I} R_{i} \subseteq R$ , then $Q \subseteq R$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.25

Prove that

p_{n+1} = \sum _{i=0}^{n} C_{n}^{i} p_{i} \quad (p_{0} = 1),

where $p_{n}$ is the number of equivalences on a set of $n$ elements.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.26

Prove that the set of all subsets of a given set is partially ordered by the inclusion relation $\subseteq$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.27

Let $\leq$ and $<$ on the set $\mathbb {N} = \left\{ 0, 1, 2, \ldots \right\}$ be defined in the usual way. Prove that $< \cdot < \; \neq \; <$ ; $\leq \cdot < \; = \; <$ ; $\leq \cdot \geq \; = \; \mathbb {N}^{2}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.28

Prove that $i_{A}$ is a partial order on $A$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.29

Let $a \leq b \Leftrightarrow a, b \in \mathbb {N}$ and $a$ divides $b$ . We take $0$ to divide $0$ . Prove that $\leq$ is a partial order on $\mathbb {N}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.30

(a)(b)(c)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Prove that every partially ordered set contains at most one greatest (least) element.

(b)

Prove that the greatest (least) element of a partially ordered set is the unique maximal (minimal) element.

(c)

Construct an example of a partially ordered set having exactly one minimal element but no least element.

Problem I.3.31

Prove that if $R$ is a partial order, then $R^{-1}$ is a partial order.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.32

Show that if $\left\{ R_{i}\right\}_{i \in I}$ is a system of partial orders on a set $A$ , then $\bigcap_{i \in I} R_{i}$ is a partial order on the set $A$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.33

Prove that a relation $R$ on a set $A$ is a preorder if and only if $R = (R \cdot R) \cup i_{A}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.34

(a)(b)(c)

Let $R$ be a preorder relation on $A$ . Put

a \sim b \Leftrightarrow \langle a, b \rangle \in R \text{ and } \langle b, a \rangle \in R.

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\sim$ is an equivalence relation on $A$ ;

(b)

if $a \sim a_{1}$ , $b \sim b_{1}$ , $\langle a, b \rangle \in R$ , then $\langle a_{1}, b_{1} \rangle \in R$ ;

(c)

$R_{1}$ is a partial order relation on $A/\sim$ , where

\langle [a], [b] \rangle \in R_{1} \Leftrightarrow \langle a, b \rangle \in R.

Problem I.3.35

Prove that if $R$ is a partial (linear, complete) order on $X$ and $A \subseteq X$ , then $R \cap A^{2}$ is a partial (linear, complete) order on $A$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.36

Let $\leq$ be a partial order on $A$ . Prove that $<$ is irreflexive and transitive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.37

Prove that if some relation $<$ on $A$ is irreflexive and transitive, then the relation

x \leq y \Leftrightarrow x < y \text{ or } x = y

is a partial order on $A$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.38

Show that if $A$ and $A_{1}$ are partially ordered sets and $f: A \rightarrow A_{1}$ is a monotone function establishing a one-to-one correspondence between $A$ and $A_{1}$ , then $f^{-1}$ need not be monotone.

Consider the case where $A$ is a linearly ordered set.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.39

Prove that any partially ordered set $A$ is isomorphic to some system of subsets of $A$ , ordered by inclusion $\subseteq$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.40

Let $R_{1}$ and $R_{2}$ be linear orders on a set $A$ . When is $R_{1} \cdot R_{2}$ a linear order?

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.41

(a)(b)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Prove that any nonempty finite partially ordered set $A$ contains minimal and maximal elements.

(b)

Let a partially ordered set $A$ be finite. Prove that for every element $a \in A$ there exist elements $b$ and $c$ of $A$ such that $a \leq b$ and $b$ is a maximal element of $A$ , and $c \leq a$ and $c$ is a minimal element of $A$ .

Problem I.3.42

(a)(b)(c)

Construct a linear order on the set:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\mathbb {N}^{2}$ ;

(b)

$\mathbb {N} \cup \mathbb {N}^{2} \cup \mathbb {N}^{3} \cup \ldots \cup \mathbb {N}^{n} \cup \ldots$ ;

(c)

$\mathbb {C}$ of complex numbers.

Problem I.3.43

Prove that any finite set can be linearly ordered.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.44

Prove that any partial order $R$ on a finite set $A$ can be extended to a linear order $R \subseteq Q$ on the set $A$ (see also problem I.5.69).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.45

Let $A$ be a partially ordered set in which every chain has at most $m$ elements, and every subset of pairwise incomparable elements consists of at most $n$ elements. Show that $A$ has at most $m \cdot n$ elements.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.46

Let $\leq_{A}$ be a partial order on a set $A$ , and $\leq_{B}$ a partial order on a set $B$ . Call the direct product of the partially ordered sets $A$ and $B$ the set $A \times B$ with the relation $\leq$ defined on it:

\langle a_{1}, b_{1} \rangle \leq \langle a_{2}, b_{2} \rangle \Leftrightarrow a_{1} \leq _{A} a_{2} \text{ and } b_{1} \leq _{A} b_{2}.

Prove that $\leq$ is a partial order on $A \times B$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.47

Let $A$ be a partially ordered set, $a, b \in A$ , and $a \leq b$ . Call the set $[a, b] = \left\{ x \mid a \leq x \leq b\right\}$ a segment. Show that the set of all segments of $A$ , partially ordered by inclusion, is isomorphic to some subset of the direct product of $A$ and its dual partially ordered set.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.48

(a)(b)

Call a partially ordered set $A$ self-dual if it is isomorphic to its dual partially ordered set. Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

there are exactly two nonisomorphic partially ordered two-element sets, each of which is self-dual;

(b)

there are five pairwise nonisomorphic partially ordered sets having three elements, and three of them are self-dual.

Problem I.3.49

We say that a partially ordered set $A$ satisfies:

the minimality condition, if every nonempty subset $M$ of the set $A$ has at least one minimal element;
the descending chain condition, if every strictly decreasing chain in $A$ is finite;
the induction condition, if for every property $T$ the following holds:

suppose that for every element $a \in A$ , the validity of the property $T$ for all elements strictly less than $a$ implies the validity of $T$ for $a$ ; then all elements of the set $A$ have the property $T$ . Prove that all these conditions are equivalent.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.50

Prove that a partially ordered set satisfies the minimality condition if and only if all its chains are well-ordered.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.51

Describe all linearly ordered sets $A$ having the property that for any $a \leq b$ there exist only finitely many $c$ such that $a \leq c \leq b$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.52

Find all sets $M$ such that there exists a complete order $R$ such that $R^{-1}$ is also a complete order on $M$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.53

(a)(b)

Let $\varphi : A \times A \rightarrow A$ and, for all $x, y, z \in A$ ,

\varphi (x, y) = \varphi (y, x), \qquad \varphi (x, \varphi (y, z)) = \varphi (\varphi (x, y), z), \qquad \varphi (x, x) = x.

Define $x \leq y \Leftrightarrow \varphi (x, y) = x$ . Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\leq$ is a partial order on $A$ ;

(b)

$\varphi (x, y)$ is the greatest lower bound with respect to the order $\leq$ .

Problem I.3.54

Prove that any subset of the set $P(A)$ , partially ordered by inclusion, has a least upper bound and a greatest lower bound.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.55

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

any linearly ordered set is a lattice;

(b)

the family of all equivalences on a set $A$ is a lattice.

Problem I.3.56

Prove that in a lattice any maximal element is the greatest element, and any minimal element is the least element.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.57

Prove that any finite lattice has a greatest and a least element.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.58

(a)(b)(c)

Give examples of lattices:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

with no greatest element, but with a least element;

(b)

with no least element, but with a greatest element;

(c)

with neither a greatest nor a least element.

Problem I.3.59

Prove that in any lattice the identities

(l_{1}) \; x \cup y = y \cup x, \qquad (l_{2}) \; x \cap y = y \cap x,

(l_{3}) \; x \cup (y \cup z) = (x \cup y) \cup z, \qquad (l_{4}) \; x \cap (y \cap z) = (x \cap y) \cap z,

(l_{5}) \; (x \cap y) \cup y = y, \qquad (l_{6}) \; x \cap (x \cup y) = y

hold.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.60

(a)(b)

Suppose two-place functions $\cup$ and $\cap$ are defined on a set $M$ , satisfying the identities $(l_{1})$ -- $(l_{6})$ of the previous problem.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Prove that for any $x, y \in M$ , $x \cup y = y$ if and only if $x \cap y = x$ .

(b)

Define $x \leq y \Leftrightarrow x \cap y = x$ . Prove that $M$ is a lattice with respect to $\leq$ , and that the greatest lower bound and least upper bound of elements $x$ and $y$ coincide with $x \cap y$ and $x \cup y$ , respectively.

Problem I.3.61

(a)(b)(c)(d)(e)(f)

Prove that in every Boolean algebra $M$ :

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

there exists a least element $0$ and a greatest element $1$ ;

(b)

for every $a \in M$ the complement $(-a)$ is unique;

(c)

$b = -a \Leftrightarrow a \cap b = 0$ and $a \cup b = 1$ ;

(d)

$-(a \cap b) = (-a) \cup (-b)$ ;

(e)

$-(a \cup b) = (-a) \cap (-b)$ ;

(f)

$a \leq b \Leftrightarrow a \cap (-b) = 0$ .

Problem I.3.62

Prove that an algebra of subsets, ordered by inclusion, is a Boolean algebra.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.63

Prove that $1 \in D$ and $0 \notin D$ for any filter $D$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.64

Let $M$ be a Boolean algebra, $A \subseteq M$ . Prove that if $a_{1} \cap \ldots \cap a_{n} \neq 0$ for every $n > 0$ and any elements $a_{1}, \ldots , a_{n} \in A$ , then the set

D = \left\{ x \mid x \in M, \; a_{1} \cap \ldots \cap a_{n} \leq x \text{ for some } a_{1}, \ldots , a_{n} \in A\right\}

is a filter on $M$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.65

Let $D$ be a filter on a Boolean algebra $M$ and $(x \cup y) \in D$ . Prove that there exists a filter $D_{1} \supseteq D$ such that $x \in D_{1}$ or $y \in D_{1}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.66

(a)(b)(c)

Prove that for any filter $D$ the following conditions are equivalent:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$D$ is a maximal filter;

(b)

$D$ is a prime filter;

(c)

$D$ is an ultrafilter.

Problem I.3.67

Prove that any filter on a Boolean algebra $M$ is contained in some maximal filter on $M$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.68

Prove that for any elements $a, b$ of a Boolean algebra $M$ , if it is not the case that $a \leq b$ , then there exists a prime filter $D$ such that $a \in D$ and $b \notin D$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.69

Let $M$ be a Boolean algebra, $P$ the set of all prime filters on $M$ . Put, for $a \in M$ ,

h(a) = \left\{ D \mid a \in D \in P\right\} .

Prove that the set

S = \left\{ h(a) \mid a \in M\right\}

is an algebra of subsets of the set $P$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.70

Prove that any Boolean algebra is isomorphic to some algebra of subsets of a suitable set (Stone’s theorem).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.71

Prove that any filter on a finite Boolean algebra has a least element.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.3.72

Prove that any finite Boolean algebra is isomorphic to the algebra of all subsets of some set.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Chapter I.4Cardinal Numbers[43/93%]

Problem I.4.1

(a)(b)(c)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$A \sim A$ (reflexivity);

(b)

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

(c)

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

Problem I.4.2

(a)(b)(c)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$A \sim B \Leftrightarrow \left|A\right| = \left|B\right|$ ;

(b)

$\left|A_{1}\right| = \left|A_{2}\right|$ , $\left|B_{1}\right| = \left|B_{2}\right|$ , and $\left|A_{1}\right| \leq \left|B_{1}\right| \Rightarrow \left|A_{2}\right| \leq \left|B_{2}\right|$ ;

(c)

if there exists a function from $A$ onto $B$ , then $\left|B\right| \leq \left|A\right|$ .

Problem I.4.3

Let $A_{2} \subseteq A_{1} \subseteq A$ and $A \sim A_{2}$ . Prove that $A \sim A_{1}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.4

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.5

(a)(b)(c)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

every subset of a finite set is finite;

(b)

the union of a finite number of finite sets is finite;

(c)

the direct product of a finite number of finite sets is finite.

Problem I.4.6

(a)(b)(c)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Prove that a finite set is not equivalent to any of its proper subsets or proper supersets.

(b)

Prove that two finite sets are equivalent if and only if they contain the same number of elements.

(c)

Prove that there are infinitely many cardinal numbers.

Problem I.4.7

Prove that a countable subset can be extracted from any infinite set.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.8

Prove that a set is infinite if and only if it is equivalent to some proper subset.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.9

Show that every subset of a countable set is countable or finite.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.10

(a)(b)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Let the domain of a function be countable. Prove that the range of this function is finite or countable.

(b)

Prove that a nonempty set $A$ is countable or finite if and only if it is the range of some function from $\mathbb {N}$ to $A$ .

Problem I.4.11

Prove that if a finite subset is removed from a countable set, the remaining set is countable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.12

(a)(b)(c)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if $A$ and $B$ are countable, then $A \cup B$ is countable;

(b)

if all the $A_{i}$ are finite, nonempty, and pairwise disjoint, then $\bigcup_{i \in \mathbb {N}} A_{i}$ is countable;

(c)

if all the $A_{i}$ are countable, then $\bigcup_{i \in \mathbb {N}} A_{i}$ is countable.

Problem I.4.13

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if $A$ is infinite and $B$ is a finite or countable set, then $A \cup B \sim A$ ;

(b)

if $A$ is infinite and uncountable, $B$ is finite or countable, then $A \setminus B \sim A$ .

Problem I.4.14

Prove that if $A_{1}, \ldots , A_{n}$ $(1 \leq n)$ are countable, then the set $A_{1} \times \ldots \times A_{n}$ is countable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.15

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

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

the set of integers is countable;

(b)

the set of rational numbers is countable;

(c)

the set of rational numbers of the segment $[a, b]$ is countable for $a < b$ ;

(d)

the set of pairs $(x, y)$ , where $x$ and $y$ are rational numbers, is countable.

Problem I.4.16

Prove that the set of all finite sequences formed from the elements of some countable set is a countable set.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.17

Prove that the set of all finite subsets of a countable set is countable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.18

Prove that the set of polynomials in one variable with integer coefficients is countable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.19

Prove the countability of the set of algebraic numbers, i.e., numbers that are roots of polynomials in one variable with integer coefficients.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.20

Prove that any set of pairwise disjoint open intervals on the real line is at most countable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.21

Prove that the cardinality of any set of pairwise disjoint letters T in the plane is at most countable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.22

Prove that if $A \subseteq \mathbb {R}$ and there exists $\delta > 0$ such that $\left|x - y\right| \geq \delta$ holds for all distinct elements $x, y$ of $A$ , then $A$ is finite or countable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.23

Prove that the set of discontinuity points of a monotone function on the real line is at most countable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.24

(a)(b)(c)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$(0, 1) \sim [0, 1] \sim (0, 1] \sim [0, 1)$ ;

(b)

$[a, b] \sim [c, d]$ , where $a < b$ , $c < d$ ;

(c)

$[a, b] \sim \mathbb {R}$ .

Problem I.4.25

Prove that the sets of points of a square and of a segment are equivalent.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.26

Prove that the sets of points of two circles are equivalent.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.27

Prove that $\mathbb {R}^{n} \sim \mathbb {R}^{m}$ $(1 \leq n, m)$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.28

Establish a one-to-one correspondence between the points of a square and of a plane.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.29

Prove that the set of points of the segment $[0, 1]$ is uncountable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.30

What is the cardinality of the set of irrational numbers?

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.31

Prove the existence of transcendental (nonalgebraic) numbers.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.32

Prove that the union of a finite or countable number of sets of cardinality $c$ has cardinality $c$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.33

Prove that the set of all countable sequences of natural numbers has cardinality $c$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.34

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

the set of all countable sequences formed from $0$ and $1$ has cardinality $c$ ;

(b)

$\left|P(\mathbb {N})\right| = c$ .

Problem I.4.35

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if $\left|A_{i}\right| = c$ for all $1 \leq i \leq n$ , then $\left|A_{1} \times \ldots \times A_{n}\right| = c$ ;

(b)

if $\left|A_{i}\right| = c$ for all $i \in I$ and $\left|I\right| = \aleph_{0}$ , then $\left|\prod_{i \in I} A_{i}\right| = c$ .

Problem I.4.36

(a)(b)(c)

What is the cardinality of the set of:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

all countable sequences of real numbers;

(b)

all continuous functions on the real line;

(c)

all monotone functions on the real line?

Problem I.4.37

Let $A$ be a countable set of points on the real line. Can $a$ be chosen so that

\left\{ x + a \mid x \in A\right\} \cap A = \emptyset \text{?}

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.38

Prove that the set of real-valued functions defined on the segment $[0, 1]$ has cardinality greater than $c$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.39

Prove that the cardinality of the set of all functions defined on the segment $[a, b]$ for $a < b$ and discontinuous at at least one point is greater than $c$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.40

Prove that the set $P(A)$ of all subsets of a set $A$ has cardinality greater than $\left|A\right|$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.41

Let $\mathcal{A}$ be a family of sets such that for every set $A$ from $\mathcal{A}$ there exists a set $B$ from $\mathcal{A}$ not equivalent to any subset of the set $A$ . Prove that the union of all sets from $\mathcal{A}$ is not equivalent to any subset of a set from $\mathcal{A}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.42

Prove that there does not exist a set containing all sets.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.4.43

(a)(b)

We say that a sequence of natural numbers $b_{1}, b_{2}, \ldots$ grows faster than a sequence $a_{1}, a_{2}, \ldots$ if $\lim_{n \to \infty } \frac{a_{n}}{b_{n}} = 0$ . Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

for every sequence of natural numbers there exists a sequence growing faster than it;

(b)

if a set of sequences $A$ has the property that for every sequence $a_{1}, a_{2}, \ldots$ there exists a sequence from $A$ growing faster than $a_{1}, a_{2}, \ldots$ , then the set $A$ is uncountable.

Chapter I.5Ordinal Numbers[69/81%]

Problem I.5.1

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.3

(a)(b)(c)

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.5

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.6

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.7

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.9

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

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.18

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.19

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.20

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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 .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.22

(a)(b)(c)(d)(e)(f)(g)(h)(i)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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 .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.24

(a)(b)(c)(d)(e)(f)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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$

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.26

(a)(b)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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)$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.29

(a)(b)(c)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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?

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.36

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.39

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.40

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.41

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.44

(a)(b)

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.46

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.47

(a)(b)

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.49

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.52

(a)(b)(c)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.54

(a)(b)(c)(d)(e)(f)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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 .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.56

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

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.61

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.62

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.5.63

(a)(b)(c)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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$ .)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

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$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Chapter I.6Operations on Cardinal Numbers[35/80%]

Problem I.6.1

Prove that for arbitrary cardinalities $m$ and $n$ exactly one of the conditions $m = n$ , $m < n$ , or $n < m$ holds (trichotomy).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.6.2

Prove that the cardinal numbers are linearly ordered by the relation $\leq$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.6.3

Prove that there is no greatest cardinal number.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.6.4

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

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$3 + 5 = 8$ ;

(b)

$n + \aleph_{0} = \aleph_{0}$ , where $n$ is finite;

(c)

$\aleph_{0} + \aleph_{0} = \aleph_{0}$ ;

(d)

$\aleph_{0} + c = c$ ;

(e)

$c + c = c$ .

Problem I.6.5

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

for any sets $A_{1}, A_{2}$ there exist sets $B_{1}, B_{2}$ such that $A_{1} \sim B_{1}$ , $A_{2} \sim B_{2}$ , and $B_{1} \cap B_{2} = \emptyset$ ;

(b)

the sum of two cardinal numbers always exists.

Problem I.6.6

(a)(b)(c)

Prove for arbitrary cardinal numbers:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$n_{1} + n_{2} = n_{2} + n_{1}$ ;

(b)

$n_{1} + (n_{2} + n_{3}) = (n_{1} + n_{2}) + n_{3}$ ;

(c)

$n + 0 = n$ .

Problem I.6.7

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

Let $A$ , $B$ , $C$ , $A_{1}, \ldots , A_{n}$ be finite sets. Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

(b)

(c)

$\left|\bigcup_{i=1}^{n} A_{i}\right| = \sum_{i=1}^{n} \left|A_{i}\right| + \ldots + (-1)^{k-1} \sum_{\substack {i_{1}, \ldots , i_{k} = 1 \\ i_{1} < \ldots < i_{k}}}^{n} \left|A_{i_{1}} \cap \ldots \cap A_{i_{k}}\right| + \ldots ;$

(d)

$\left|A_{1} \setminus A_{2} \setminus \ldots \setminus A_{n}\right| = \sum_{i=1}^{n} \left|A_{i}\right| + \ldots + (-2)^{k-1} \sum_{\substack {i_{1}, \ldots , i_{k} = 1 \\ i_{1} < \ldots < i_{k}}}^{n} \left|A_{i_{1}} \cap \ldots \cap A_{i_{k}}\right| + \ldots$

Problem I.6.8

(a)(b)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Prove that $n < m \Rightarrow n + 1 \leq m$ .

(b)

Give an example of cardinal numbers $n$ and $m$ such that $n + 1 \leq m$ , but $m \leq n$ .

Problem I.6.9

Prove that $n \leq m$ if and only if there exists $n_{1}$ such that $n + n_{1} = m$ . Show that such an $n_{1}$ is not uniquely determined.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.6.10

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

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$3 \cdot 5 = 15$ ;

(b)

$\aleph_{0} \cdot \aleph_{0} = \aleph_{0}$ ;

(c)

$\aleph_{0} \cdot c = c$ ;

(d)

$c \cdot c = c$ .

Problem I.6.11

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if $A \sim B$ and $C \sim D$ , then $A \times C \sim B \times D$ ;

(b)

the product of two cardinal numbers always exists.

Problem I.6.12

(a)(b)(c)(d)(e)(f)(g)

Prove for arbitrary cardinal numbers:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$n_{1} \cdot n_{2} = n_{2} \cdot n_{1}$ ;

(b)

$n_{1} \cdot (n_{2} \cdot n_{3}) = (n_{1} \cdot n_{2}) \cdot n_{3}$ ;

(c)

$n_{1} \cdot (n_{2} + n_{3}) = (n_{1} \cdot n_{2}) + (n_{1} \cdot n_{3})$ ;

(d)

$n \cdot 1 = n$ ;

(e)

$n \cdot 0 = 0$ ;

(f)

$n \cdot m = n$ , if $m$ is finite and $n$ is an infinite cardinal number;

(g)

$n \cdot \aleph_{0} = n$ , if $n$ is an infinite cardinal number.

Problem I.6.13

Prove that $n^{2} = n$ , if $n$ is an infinite cardinal number.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.6.14

Prove that if $n$ and $m$ are cardinal numbers and one of them is infinite, then $n \cdot m = n + m = \max (n, m)$ , provided $n \neq 0$ and $m \neq 0$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.6.15

(a)(b)(c)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$2^{\aleph_{0}} = c$ ;

(b)

$\aleph_{0}^{\aleph_{0}} = c$ ;

(c)

$c^{\aleph_{0}} = c$ .

Problem I.6.16

Prove that for two cardinal numbers $n$ and $m$ , $n^{m}$ always exists.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.6.17

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

Prove for arbitrary cardinal numbers $m$ , $n$ , and $p$ :

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$m^{n+p} = m^{n} \cdot m^{p}$ ;

(b)

$(m \cdot n)^{p} = m^{p} \cdot n^{p}$ ;

(c)

$(m^{n})^{p} = m^{n \cdot p}$ ;

(d)

$m^{1} = m$ ;

(e)

$1^{m} = 1$ .

Problem I.6.18

Prove that $\left|P(A)\right| = 2^{\left|A\right|}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.6.19

(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

Problem I.6.20

(a)(b)

Prove for arbitrary cardinal numbers:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if $2^{m} \geq \aleph_{0}$ , then $2^{m} \geq 2^{\aleph_{0}}$ ;

(b)

if $m^{n} = \aleph_{0}$ , then $m = \aleph_{0}$ , and $n$ is finite.

Problem I.6.21

(a)(b)

Prove for arbitrary cardinal numbers:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if $n \geq \aleph_{0}$ , then $2^{n} = n^{n}$ ;

(b)

if $1 < m \leq n$ , $\aleph_{0} \leq n$ , then $m^{n} = n^{n}$ .

Problem I.6.22

(a)(b)(c)

Prove for arbitrary cardinal numbers:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if $\left|I\right| = m$ , $n_{i} = n$ for all $i \in I$ , then $m \cdot n = \sum_{i \in I} n_{i}$ ;

(b)

if $m + p = n + p$ and $p$ is finite, then $m = n$ ;

(c)

if $2 \cdot n_{1} = 2 \cdot n_{2}$ , then $n_{1} = n_{2}$ .

Problem I.6.23

Prove that

\left|\bigcup _{i \in I} A_{i}\right| \leq \sum _{i \in I} \left|A_{i}\right|.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.6.24

(a)(b)(c)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Let $\left\{ m_{i}\right\}$ $(i \in I)$ be a family of cardinal numbers, with $m_{i} = 0$ for $i \in J \subseteq I$ . Prove that

\sum _{i \in I} m_{i} = \sum _{i \in I \setminus J} m_{i}.

(b)

Let $\left\{ m_{i}\right\}$ $(i \in I)$ be a family of cardinal numbers, with $m_{i} = 1$ for $i \in J \subseteq I$ . Prove that

\prod _{i \in I} m_{i} = \prod _{i \in I \setminus J} m_{i}.

(c)

Prove that $\prod_{i \in I} m_{i} = 0$ if and only if there exists $i_{0} \in I$ such that $m_{i_{0}} = 0$ .

Problem I.6.25

(a)(b)

Prove that if $\varphi$ is a permutation of the set $I$ , then:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\sum_{i \in I} m_{i} = \sum_{i \in I} m_{\varphi (i)}$ ;

(b)

$\prod_{i \in I} m_{i} = \prod_{i \in I} m_{\varphi (i)}$ .

Problem I.6.26

(a)(b)

Let $\left\{ A_{\lambda }\right\}_{\lambda \in L}$ be a partition of the set $J$ into nonempty pairwise disjoint sets. Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\sum_{i \in I} m_{i} = \sum_{\lambda \in L} \left(\sum_{i \in A_{\lambda }} m_{i}\right)$ ;

(b)

$\prod_{i \in I} m_{i} = \prod_{\lambda \in L} \left(\prod_{i \in A_{\lambda }} m_{i}\right)$ .

Problem I.6.27

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$n \cdot \sum_{i \in I} m_{i} = \sum_{i \in I} (n \cdot m_{i})$ ;

(b)

$\prod_{i \in I} \left(\sum_{j \in J_{i}} m_{ij}\right) = \sum_{f \in K} \prod_{i \in I} m_{i f(i)}$ , where $K = \prod_{i \in I} J_{i}$ .

Problem I.6.28

(a)(b)

Prove that if $m_{i} \leq n_{i}$ for all $i \in I$ , then:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\sum_{i \in I} m_{i} \leq \sum_{i \in I} n_{i}$ ;

(b)

$\prod_{i \in I} m_{i} \leq \prod_{i \in I} n_{i}$ .

Problem I.6.29

(a)(b)

Let $J \subseteq I$ . Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\sum_{i \in J} m_{i} \leq \sum_{i \in I} m_{i}$ ;

(b)

$\prod_{i \in J} m_{i} \leq \prod_{i \in I} m_{i}$ , where $m_{i} \neq 0$ for $i \in I \setminus J$ .

Problem I.6.30

(a)(b)

Let $\left\{ m_{i}\right\}_{i \in I}$ and $\left\{ n_{i}\right\}_{i \in I}$ be two families of cardinal numbers, with $n_{i} \geq 2$ for all $i \in I$ . Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if $m_{i} \leq n_{i}$ for all $i \in I$ , then $\sum_{i \in I} m_{i} \leq \prod_{i \in I} n_{i}$ ;

(b)

if $m_{i} < n_{i}$ for all $i \in I$ , then $\sum_{i \in I} m_{i} < \prod_{i \in I} n_{i}$ .

Problem I.6.31

Let $0 < m_{0} < m_{1} < \ldots$ Prove that $\sum_{n \in \mathbb {N}} m_{n} < \prod_{n \in \mathbb {N}} m_{n}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.6.32

Let $n \geq \aleph_{0}$ , $\left\{ n_{i}\right\}_{i \in I}$ be a family of cardinal numbers not exceeding $n$ , $\left|I\right| \leq n$ . Prove that $\sum_{i \in I} n_{i} \leq n$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.6.33

Let $\alpha$ and $\beta$ be cardinal numbers, $\left|I\right| = \beta$ , and $\alpha_{i} = \alpha$ for every $i \in I$ . Prove that $\alpha^{\beta } = \prod_{i \in I} \alpha_{i}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem I.6.34

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$m^{\left(\sum_{i \in I} n_{i}\right)} = \prod_{i \in I} m^{n_{i}}$ ;

(b)

$\left(\prod_{i \in I} m_{i}\right)^{n} = \prod_{i \in I} m_{i}^{n}$ .

Problem I.6.35

Prove that for any cardinal number $m$ , $m^{\aleph_{0}}$ cannot be represented in the form $\sum_{i \in \mathbb {N}} m_{i}$ , where $m_{i} < m_{i+1}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source