1

The last question (which is always the hardest) of my Induction Exercises goes like this:

Let S be the subset of $\mathbb{Z}$ defined by:
-12,20 $\in$ S
if x,y $\in$ S, then x+y $\in$ S

We use structural induction to show that S = {4k | k $\in \mathbb{Z}$}. The proof is divided in three parts:

a) Show that 4 and -4 are in S.
b) Prove, by structural induction, that S $\subset$ {4k | k $\in \mathbb{Z}$}
c) Use a) and structural induction to prove that S $\supset$ {4k | k $\in \mathbb{Z}$}

What I Did:
a) -12,20 $\in$ S, so 8 $\in$ S. If -12,8 $\in$ S, then -4 $\in$ S (that's one!). If -4,8 $\in$ S, then 4 $\in$ S (and that's two).
b) We want to prove S $\subset$ {4k | k $\in \mathbb{Z}$}.
We take the smallest subset of S, which is 4. If we take k=1, 4k = 4, so this one is valid.
Then, suppose the statement is true for (Xn, Yn). Then there must be some k so that Xn+Yn = 4k.
Is it also true for the next element? Let's take (Xn+1, Yn+1) as the next element. We could write this as (Xn+1, Yn+1) = (Xn, Yn) + 4. This is equal to 4k + 4, which is a multiple of four. Therefore, (Xn+1, Yn+1) is a multiple of four. Thus, every element in S is a multiple of four, thus S $\subset$ {4k | k $\in \mathbb{Z}$}

The Question: Is this in any way a valid structural induction? And, what about c), isn't that exactly the same as b)?

Thanks in advance!

Tiamo P.
  • 319

1 Answers1

0

I think taht for b) : Prove, by structural induction, that $S ⊂ \{ 4k | k \in \mathbb Z \}$

we can proceed in this way :

i) $-12 = 4 \times -3$, with $-3 \in \mathbb Z$; thus $-12 \in \{ 4k | k \in \mathbb Z \}$.

The same for $20 = 4 \times 5$.

ii) if $x_1,x_2 \in \{ 4k | k \in \mathbb Z \}$, then $x_1=4 \times k_1$ and $x_2=4 \times k_2$.

Thus : $x_1+x_2= 4k_1+4k_2=4(k_1+k_2)$ and we have proved that $x_1+x_2 \in \{ 4k | k \in \mathbb Z \}$.

In this way, we have proved that $S$ in included into $\{ 4k | k \in \mathbb Z \}$, because the definition of inclusion is : $A \subset B$ iff for all $x$, if $x \in A$, then $x \in B$ and our prove above has showed that : for all $n$, if $n \in S$, then $n \in \{ 4k | k \in \mathbb Z \}$.

Part c) ask for the other inclusion : $\{ 4k | k \in \mathbb Z \} \subset S$.

Mauro ALLEGRANZA
  • 94,169