other exercises: 20241031_DiskMat_Serie6.pdf

6.6 The hunt for Red October

inspiration: https://cage.ugent.be/~ldnaux/problem_5.html

The position of the submarine is

Since $s,v_0\in \mathbb{Z}$ are not known, the submarine has a par of unknown values $(v,s_0)\in \mathbb{Z}\times \mathbb{Z}$. Since $\mathbb{Z}$ is countable, $\mathbb{Z}\times \mathbb{Z}$ is countable as well (Theorem 3.22). The pairs can be written as

where $t=1,2,\dots ,n$. At every $t$, Svetlana can fire a torpedo at

until she targets the position (pair) where the submarine is, e.g. $t=n$, thus sinking the submarine in a finite time.

6.5 Countability

For all $l{\ge }_1,l\in \mathbb{N}$:

~~Since $k,l\in \mathbb{N}$, $\frac{k}{l}+1$ cannot be smaller than 1. Thus, all functions

are also part of $A_l$.~~
Now, we assume that $A_l$ is countable ($A_l⪯\mathbb{N}$). Let

Let $b\in \{0,1{\}}^{\mathrm{\infty }}$ and $x,k,l\in \mathbb{N}$. Since the function only returns $1$ if $\sum _{i=1}^{x-1}{b}_x\le \frac{x-1}{l}+1$, the sum $\sum _{i=0}^k{f}_b(i)$ is always smaller than $\frac{k}{l}+1$. Thus, $f_b$ is in $A_l$.

-> This means that $g(b)=f_b\in S$ for $b\in \{1,0{\}}^{\mathrm{\infty }}$

Let $b,b^{\prime }\in \{0,1{\}}^{\mathrm{\infty }}$ so that $b\ne b^{\prime }$. This means that $b_n\ne b_n^{\prime }$ for $n\in \mathbb{N}$.
Let $j$ be the smallest index where $b_j\ne b_j^{\prime }$.
Then $f_b(j)\ne f_{b^{\prime }}(j)$, since only $b_j$ or $b_k^{\prime }$ satisfy the first case of the function.

-> $f_b$ is an injective function

We have shown that there is an injective function $g:\{0,1{\}}^{\mathrm{\infty }}\to A_l$. According to Definition 3.42, then applies $\{0,1{\}}^{\mathrm{\infty }}⪯A_l$.

Since we assume that $A_l$ is countable and we have shown that $\{0,1{\}}^{\mathrm{\infty }}⪯A_l$ it follows (Lemma 3.15):

This is a contradiction, thus proving that $A_l$ is uncountable. $◻$