HS21

Task 1

e) Uncountability

Exercise: $Y$ finite and non-empty. $f:\mathbb{N}\to Y$ an arbitrary function. We have to show that there exists a strictly increasing function $g:\mathbb{N}\to \mathbb{N}$ such that $f\circ g$ is constant.

For each element $y\in Y$, consider the following set: $S_y=\{n|f(n)=y\}$ From the definition of $f:\mathbb{N}\mapsto Y$, we know that the domain $\mathbb{N}$ is infinite.

Now by contradiction: if for all $y\in Y$ we have that $S_y$ is finite, then the union of all such sets is finite ${\bigcup }_{y\in Y}{S}_y$ (as there are finitely many sets and each set is finite). However, this set is $\mathbb{N}$, which is known to be infinite.

Hence, there must exist at least one $y\in Y$ s. t. $S_y$ is infinite. (Let $y$ be fixed from now on.)

Now, we can define a strictly increasing function $g:\mathbb{N}\mapsto \mathbb{N}$ s. t. for all $n\in \mathbb{N}$ we have $(f\circ g)(n)=f(g(n))=y$. For any integer $k\in \mathbb{N}$, we define $g$: $g(k)=\text{min}(\{n|f(n)=y\wedge (\forall x\in \mathbb{N}x<k\to g(x)<n)\})$ Note that the first condition is directly derived from the set $S_y$ and the second condition ensures that $g$ is strictly increasing. Finally, note that a minimum matching these conditions always exists, since the set is infinite.

Task 2

c)

When assuming there is a minimum positive element in a subset of $\mathbb{N}$, then we have to show that a positive element exists.

Here we have infinite $S\subseteq \mathbb{Z}$ thus $S=\{-1,-2,\dots \}$ is possible. Thus $\exists x\ne 0$. By the assumption $x\in S$ we have $(x)\subseteq S$ (exercise says this), therefore $-x\in S$ and thus there is a positive number.

Task 3

d) Disprove that for groups $G,H$ all subgroups of $G\times H$ must be of the form $G^{\prime }\times H^{\prime }$ where $G^{\prime },H^{\prime }$ are subgroups of $G,H$.

Consider $G=H={\mathbb{Z}}_3$ then a subgroup is $S=\{(0,0),(1,1),(2,2)\}$. But $S$ cannot be of the form $G^{\prime }\times H^{\prime }$ as otherwise there would also be $\{(0,1),(1,0),\dots \}$ in the set.

${\mathbb{Z}}_3\times {\mathbb{Z}}_3$ forms a group with neutral $(0,0)$, addition is closed (show all cases) and each element has an inverse:

• $(1,1)+(2,2)=(0,0)$
• $(2,2)+(1,1)=(0,0)$