Let $M$ be a free module over a PID with finite rank, then any submodule $N \subset M$ is also free with finite rank I want to post the statement from Dummit and Foote (page460), but it is so long that I have to post a shorter one from another book.




Q2: I want to make sure I understand this. We apply induction on $t &gt; 0$, so that means anything $&lt;t$ is assumed to be true. Therefore $N \cap \ker g$ being a submodule of $N$ with rank $t -1 &lt; t$ is assumed to be a free of finite rank $t-1.$ So what they are saying is to adjoin the one element $a_1x_1$ to the finite set of basis $B_{t-1}$ is a finite basis set. So I think this is actually strong induction? In this instance, we don't even need to prove the $t + 1$ case?
Q2: Again by reasoning above assume it is true for $r &gt; 0$ and any all integers less than $r$, then $\ker g$ is a submodule of rank $r -1.$ Now what I don't get is it says
$\exists \{x_2, \dots,x_{r}\}$ basis (there is exactly $r-1$ in this set) for $\ker g$ such that $\{a_2x_2,\dots, a_rx_r\}$ basis for $N \cap \ker g$ such that $a_i | a_{i+1}.$
It feels like we somehow already know that elements of the form $a_ix_i$ with $a_i|a_{i+1}$ are going to be basis elements for $N\cap \ker g$ to make this induction. I feel like there is some circular logic going on. The induction feels like one big verification. I want to know how we know the submodule has to be generated by elements that look that in the first place.
Both of your questions are labelled as Q2. They have more to do with the principle of induction than with modules.
Anyhow, in the first instance you are quite right that this is a strong induction. This means that they assume that the statement is true for all numbers $\leq t-1$ and then have to prove it for $t$.
The strong induction could alternatively be phrased as follows: Assume that the statement is true for all numbers $\leq t$ and then they would need to prove it for $t+1$. Which version you choose is a matter of notation, not of the actual mathematical content.

The second issue is similar. At the stage that you say you don't get, the author is using the inductive hypothesis (remember, you are proving the statement for $r$ so you are allowed to use it for $r-1$). This is not circular, because there is extra work to be done to transfer from
a basis $\{a_2x_2, \dots ,a_rx_r\}$ for $N \cap \ker g$ such that $a_i|a_{i+1}$ (induction hypothesis = statement for $r-1$)
to
a basis $\{a_1x_1,a_2x_2, \dots ,a_rx_r\}$ for $N$ such that $a_i|a_{i+1}$ (your goal = statement for $r$).

Following the comment, I now see that you are interested in &quot;how would one think about that in the first place&quot; rather than in the details of the proof. The prototypical example I would have in mind is a free $\mathbb{Z}$-module $M=\mathbb{Z}^n$. Choose a standard basis $x_i = (0,\dots ,0,1,0, \dots, 0)$ for $i=1, \dots, n$. What do the submodules of $M$ look like? For example, there is a submodule $N_1 = \mathbb{Z}x_1$ spanned by $x_1$. This has a very nice form already. But there is also a submodule $N_2 = \mathbb{Z}(3x_5-2x_{10}) + \mathbb{Z}7x_9$ spanned by $3x_5-2x_{10}$ and $7x_9$, which you may think is ugly. But wait! It's only ugly with respect to this basis of $M$. The theorem says that there is another basis $y_1, \dots, y_n$ of $M$ such that $N_2$ is a nice direct sum of two multiples of basis vectors, ie $N$ has a basis $\{ a_1y_1, a_2y_2 \}$ for some $a_1, a_2$.
There are two inductions one is on $t=$rank($N$), one is on $r=$rank($M$).
Actually the induction on $t$ doesn't prove anything, that paragraph can be deleted.
induction on $r$ part need a result to obtain ker($g$) is free: submodule of a free $R$-module is free.
This induction is actually just repeat the process of how you get $a_1$ to get $a_2$ then $a_3$, ...