Math Problems Vault

Problem 1.1

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

Let $A_{i}(i \in I), B$ be subsets of $X$ . Prove the equalities:

?

(a)

$\left(\bigcup_{i \in I} A_{i}\right) \cap B=\bigcup_{i \in I}\left(A_{i} \cap B\right)$ ;

(b)

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

(c)

$\overline{\bigcup_{i \in I} A_{i}}=\bigcap_{i \in I} \overline{A_{i}}$ ;

(d)

$\bigcap_{i \in I} A_{i}=\bigcup_{i \in I} \overline{A_{i}}$ .

Problem 1.2

Let $X$ be an arbitrary set, and let $2^{X}$ be the set of all its subsets. Prove that the operation $\triangle$ of symmetric difference

A \Delta B=(A \cap \bar{B}) \cup (\bar{A} \cap B)

on the set $2^{X}$ has the following properties:

?

(a)

$A \triangle B=B \triangle A$ ;

(b)

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

(c)

$A \triangle \varnothing =A$ ;

(d)

for any subset $A \subset X$ there exists a subset $B \subset X$ such that $A \triangle B=\varnothing$ ;

(e)

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

(f)

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

(g)

$A \Delta B=(A \backslash B) \cup (B \backslash A)$ .

Problem 1.3

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

\begin{aligned} \left|\bigcup _{i=1}^{n} A_{i}\right|= & \sum _{i=1}^{n}\left|A_{i}\right|-\sum _{1 \leqslant i<j \leqslant n}\left|A_{i} \cap A_{j}\right|+\ldots \\ & \quad \ldots +(-1)^{k-1} \sum _{1 \leqslant i_{1}<\ldots <i_{k} \leqslant n}\left|A_{i_{1}} \cap \ldots \cap A_{i_{k}}\right|+\ldots \\ & \quad \ldots +(-1)^{n-1}\left|A_{1} \cap \ldots \cap A_{n}\right| \end{aligned}

?

Problem 1.4

Prove that for any natural number $n>1$

\varphi (n)=n\left(1-\frac{1}{p_{1}}\right)\left(1-\frac{1}{p_{2}}\right) \ldots \left(1-\frac{1}{p_{r}}\right).

where $p_{1}, p_{2}, \ldots , p_{r}$ are all the distinct prime divisors of $n$ , and $\varphi (n)$ is Euler's function.

?

Problem 1.5

What is the maximum number of subsets that can be formed from $n$ given subsets of a fixed set using the operations of intersection, union, and complementation?

?

Problem 1.6

Let $A, B, C$ be subsets of some set. Prove that $A \cap B \subseteq C$ if and only if $A \subseteq \bar{B} \cup C$ .

?