Sets and mappings

Let $\Omega =\left\{ +,-,++,+-,-+,--,+++, \ldots \right\} -$ the set of all finite sequences of pluses and minuses, and let $f: \Omega \rightarrow \Omega$ be the transformation taking the element $\omega =\omega_{1} \omega_{2} \ldots \omega_{n} \in \Omega$ to $\omega^{\prime }=\omega_{1} \dot{\omega }_{1} \omega_{2} \dot{\omega }_{2} \ldots \omega_{n} \dot{\omega }_{n}$, where $\dot{\omega }_{k}=-$ if $\omega_{k}=+$, and $\dot{\omega }_{k}=+$ if $\omega_{k}=-$. Show that in $f(f \omega )$ every segment of length $>4$ contains ++ or --.

Does the map $f: \mathbb {N} \rightarrow \mathbb {N}$ given by the rule $n \mapsto n^{2}$ have a right inverse? Exhibit two left inverse maps for $f$.

Let $f: X \rightarrow Y$ be a map and $S, T$ subsets of $X$. Show that

Give an example showing that the latter inclusion cannot, in general, be replaced by equality.

The set of all subsets of a set $S$ is denoted

If, for example, $S=\left\{ s_{1}, s_{2}, \ldots , s_{n}\right\}$ is a finite set of $n$ elements, then $\mathcal{P}(S)$ consists of the empty set $\varnothing$, $n$ singleton sets $\left\{ s_{1}\right\} ,\left\{ s_{2}\right\} , \ldots \left\{ s_{n}\right\}$, $n(n-1) / 2$ two-element sets $\left\{ s_{i}, s_{j}\right\} , 1 \leqslant i<j \leqslant n$, and so on up to $T=S$. What is the cardinality of the set $\mathcal{P}(S)$?

Let $f: X \rightarrow Y$ be a map and $b=f(a)$ for some $a \in X$. The preimage

is also sometimes called the fiber over the element $b \in \operatorname {Im} f$. Show that the whole set $X$ is a union of pairwise disjoint fibers (i.e., a partition of the set $X$).

Warning. The notation $f^{-1}(b)$ should not be associated with the inverse map, which may not even exist.

Show that a finite Cartesian power of a countable set is a countable set.

The symmetric difference of two sets $S$ and $T$ is denoted $S \triangle T$: $S \triangle T=(S \backslash T) \cup (T \backslash S)$ (Fig. 6). Show that $S \backslash T=(S \cup T) \backslash (S \cap T)$.

$S \triangle T$

Fig. 6