Math Problems Vault

Problem 1

Find all subsets of the following sets: $\varnothing ,\left\{ \varnothing \right\} ,\left\{ 1,2,3\right\}$ , $\left\{ a, \left\{ 1,2\right\} , \varnothing \right\}$ .

?

Problem 2

Let $A=\left\{ 0,1\right\} , B=\left\{ a, b, c\right\}$ . Find the sets $A \times B$ and $B \times A$ .

?

Problem 3

(a)(b)

Prove the following inclusions:

?

(a)

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

(b)

$A \backslash B \subseteq A$ .

Problem 4

Prove the following identities for arbitrary sets $A, B, C$ :

?

(a)

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

(b)

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

(c)

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

(d)

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

(e)

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

(f)

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

(g)

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

(h)

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

(i)

$A \div B=(A \cup B) \backslash (A \cap B)$ ;

(j)

$A \cup \varnothing =\varnothing \cup A=A$ ;

(k)

$A \cap \varnothing =\varnothing \cap A=\varnothing$ ;

(l)

$A \div \varnothing =\varnothing \div A=A$ ;

(m)

$A \div A=\varnothing$ .

Problem 5

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

Prove that

?

(a)

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

(b)

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

(c)

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

(d)

if $A \subseteq B$ and $C \subseteq D$ , then $(A \times C)=(A \times D) \cap (B \times C)$ .

Problem 6

Prove that the inclusion $A \subseteq B$ holds if and only if $\mathrm{P}(A) \subseteq \mathrm{P}(B)$ holds.

?

Problem 7

For each of the following relations find $\operatorname {dom} R, \operatorname {rng} R, R^{-1}$ , $R \circ R, R \circ R^{-1}$ :

?

(a)

$R=\left\{ (x, y): x, y \in \omega \text{ and }x\text{ divides }y\right\}$ ; $x$ divides $y$ if there exists $z$ such that $x z=y$ ;

(b)

$R=\left\{ (x, y): x, y \in \omega \text{ and }x+y \leqslant 10\right\}$ ;

(c)

$R=\left\{ (x, y): x, y \in \omega \text{ and }y=3 x+1\right\}$ ;

(d)

$R=\left\{ \left(x, x^{2}\right): x \in \omega \text{ and } x \leqslant 10\right\}$ ;

(e)

$R=\left\{ (a, b),(b, c),(b, d),(c, d),(d, b)\right\}$ .

Problem 8

(a)(b)

Let the set $S=\left\{ (i, j): 1 \leqslant i, j \leqslant 8\right\}$ denote the squares of a chessboard. Describe the following binary relations on $S$ :

?

(a)

$L=\left\{ (a, b)\text{ : a rook can move from square }a\text{ to square }b\text{ in one move}\right\}$ ;

(b)

$K=\left\{ (a, b)\text{ : a knight can move from square }a\text{ to square }b\text{ in one move}\right\}$ .

Are these relations equivalence relations? Describe the relation $L \circ L$ .

Problem 9

(a)(b)

Let $\Pi$ be the set of all lines in the Euclidean plane. Determine whether the following relations on $\Pi$ are equivalence relations:

?

(a)

parallelism of lines (we regard a line as parallel to itself);

(b)

perpendicularity of lines.

Problem 10

Let $\Pi$ be the set of polygons in the plane. Are the following relations equivalence relations on $\Pi$ :

?

(a)

$x$ and $y$ can be made to coincide;

(b)

$x$ and $y$ are similar;

(c)

$x$ and $y$ have the same angle;

(d)

$x$ and $y$ intersect;

(e)

$x$ and $y$ have the same area;

(f)

$x$ and $y$ have a common vertex;

(g)

$x$ and $y$ are equidecomposable.

Problem 11

Let $W$ be the set of words over the alphabet $\Sigma$ . Are the following relations equivalence relations on $W$ :

?

(a)

$x$ and $y$ consist of the same symbols, disregarding count;

(b)

$x$ and $y$ consist of the same symbols, counting multiplicity;

(c)

$x y$ has even length;

(d)

$x$ and $y$ have the same length;

(e)

$x$ and $y$ have the same length and differ in at most one position;

(f)

$x$ and $y$ have at least one common letter;

(g)

$x$ and $y$ begin with the same letter.

Problem 12

(a)(b)

Let $\Sigma =\left\{ a_{1}, \ldots , a_{m}\right\}$ be an arbitrary finite alphabet, that is, a set of symbols. Denote by $\Sigma^{n}$ the set of words of length $n$ over the alphabet $\Sigma$ (this notation is consistent with the same notation for the Cartesian power of $\Sigma$ , since the power $\Sigma^{n}$ consists of all sequences of elements of $\Sigma$ of length $n$ ).

?

(a)

Define the following relation $R_{1}$ on words from $\Sigma^{n}$ . Let $v=a_{i_{1}} a_{i_{2}} \ldots a_{i_{n}}, w=a_{j_{1}} a_{j_{2}} \ldots a_{j_{n}}$ . Then $(v, w) \in R_{1}$ if and only if $i_{k} \leqslant j_{k}$ for all $k$ from 1 to $n$ and $i_{k}<j_{k}$ for some such $k$ , that is, the number of each letter of the word $v$ is no greater than the number of the same letter in the word $w$ , and for at least one letter it is strictly smaller. Determine whether this relation $R_{1}$ is a relation of partial (linear) order.

(b)

Define the following relation $R_{2}$ on words from $\Sigma^{*}$ . Let $v=a_{i_{1}} a_{i_{2}} \ldots a_{i_{n}}, w=a_{j_{1}} a_{j_{2}} \ldots a_{j_{r}}$ . Then $(v, w) \in R_{2}$ if and only if there exists $k$ in the range from 1 to $n$ such that $i_{l}=j_{l}$ for $l<k$ and $i_{k}<j_{k}$ , or $n<r$ and the first $n$ symbols of $w$ coincide with the word $v$ . Determine whether this relation $R_{2}$ is a relation of partial (linear) order.

Remark.

?

Remark 3 (Ordering of tuples). The relation $R_{1}$ defined in part (a) is called the coordinatewise order relation, and the relation $R_{2}$ from part (b) is called the lexicographic order relation. Words in dictionaries and encyclopedias, for example, are ordered according to lexicographic order.

Problem 13

Prove that, under the conditions of Problem 12 on the facing page, on the set $\Sigma^{k}$ the lexicographic order extends the coordinatewise order, that is $R_{1} \subseteq R_{2}$ .

?

Problem 14

Prove that if $X \subseteq Y$ are finite subsets of $\omega$ , then $\rho (X) \leqslant \rho (Y)$ , where the function $\rho$ is from Example 2 on p. 31. Show that the converse is false.

Example 2: Let $\mathrm{P}_{f}(A)$ denote the set of all finite subsets of $A$ . The function $\rho : \mathrm{P}_{f}(\omega ) \rightarrow \omega$ is defined by $\rho (X)=\sum_{i \in X} 2^{i}$ .

?

Problem 15

Prove that a function $f$ on a set $A$ is a partial order on $A$ if and only if $f(f(x))=f(x)$ for all $x \in A$ .

?

Problem 16

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

Prove that if the sets $A$ and $B$ are finite, then the following equalities hold for their cardinalities:

?

(a)

(b)

$|A \cup B|=|A|+|B|-|A \cap B|$ ;

(c)

$\left|\left\{ 0,1\right\}^{n}\right|=2^{n}$ ;

(d)

$\left|\mathrm{P}(A)\right|=2^{\left|A\right|}$ .

Problem 17

Prove that the set of pairs $\omega^{2}$ is countable.

?

Problem 18

Prove that the set of ordered $n$ -tuples $\omega^{n}$ is countable.

?

Problem 19

Prove that the union of a countable number of countable sets is again countable.

?

Problem 20

Prove that the set of rational numbers $\mathbb {Q}$ is countable.

?

Problem 21

Prove that the set of degree- $n$ polynomials with integer coefficients is countable for a fixed $n$ .

?

Problem 22

Prove that the set of all polynomials with integer coefficients is countable.

?

Problem 23

Prove that the set of algebraic numbers is countable.

?

Problem 24

Using the Cantor–Bernstein theorem, prove that the set $S$ of sequences of real numbers $\left(a_{i}\right)_{i \in \omega }, a_{i} \in \mathbb {R}$ , has the same cardinality as $\mathbb {R}$ .

?

Problem 25

Prove that every language over a finite alphabet is countable.

?

Problem 26

Find $L_{1} \cap L_{2}, L_{2} \backslash L_{1}, \bar{L}_{1}$ for the following languages over the alphabet $\Sigma =\left\{ a, b\right\}$ :

\begin{align} & L_{1}=\left\{ w \in \Sigma ^{*}: \text{ the numbers of letters } a \text{ and } b \text{ in } w \text{ are equal }\right\} \\ & L_{2}=\left\{ a^{i} b^{j}: i, j \in \omega \right\} . \end{align}

?

Problem 27

Find all prefixes and suffixes of the word $a^{2} b^{2} c$ .

?