Section 3.3: Problem 6 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

Is $3$ a sequence number? What is $\mbox{lh}3$ ? Find $(1\ast3)\ast6$ and $1\ast(3\ast6)$ .

$3=2^{0}\cdot3^{1}$ is not a sequence number, as $p_{1}=3$ divides $3$ but $p_{0}=2$ does not divide $3$ . However, formally, we can still calculate the formulas in the question.

First, formally, $\mbox{lh}b$ is defined as the least $n\in\mathbb{N}$ such that either $b=0$ or $<p_{n},b>\notin\mathcal{D}$ where $\mathcal{D}$ is the divisibility relation. In our case, $<p_{0},3>\notin\mathcal{D}$ , so that $\mbox{lh}3=0$ .

Second, formally, $(b)_{c}$ is defined as the least $n\in\mathbb{N}$ such that either $b=0$ or $<p_{c}^{n+2},b>\notin\mathcal{D}$ . In our case, $(3)_{c}=0$ for all $c\in\mathbb{N}$ (including $c=1$ for which $p_{1}=3$ ).

Finally, $a\ast b=a\cdot\prod_{i<\mbox{lh}b}p_{i+\mbox{lh}a}^{(b)_{i}+1}$ is defined for all natural numbers as well. In particular, since $\mbox{lh}1=0$ , $1\ast b=\prod_{i<\mbox{lh}b}p_{i}^{(b)_{i}+1}$ which is simply the maximum sequence number that divides $b$ . Therefore, $1\ast3=1$ and $(1\ast3)\ast6=6$ ( $6=\langle0,0\rangle$ is a sequence number). Further, $3\ast6=3\cdot\prod_{i<2}p_{i}^{(6)_{i}+1}=3\cdot6=18=2^{1}\cdot3^{2}=<0,1>$ . Hence, $1\ast(3\ast6)=18$ .

Note. The exercise shows that the concatenation operation, as defined, is not associative on the set of all natural numbers, however, as mentioned in the text, it is associative on the set of sequence numbers.

Subpages

Section 3.3: Problem 6 Solution

Section 3.3: Problem 6 Solution