Proof that $S = \{a + b\sqrt{5}: a,b \in \mathbb{N}\}$ is inductive.

Question

A set is inductive iff $1 \in S$ and $(x + 1) \in S$ whenever $x \in S$.

So it's easy to show when a=1,b=0 then $a+b\sqrt{5} = 1$. So 1 is in S (I assume $0 \in \mathbb{N}$).

However, I am having difficult with the inductive step. This is my thinking thus far.

Assume $a + b\sqrt{5} \in S$.

We need to show $(a+1) + b\sqrt{5} \in S$. Since we know $1+0\sqrt{5} = 1 \in S$. We can substitute in for 1 as follows: $(a + (1 + 0\sqrt{5})) + b\sqrt{5} = (a+1) + b\sqrt{5}$. Thus, $(a+1) + b\sqrt{5} \in S$.

Is this correct? If so, why is the substitution I made allowed? I'm new to induction so my apologies if this seems like a trivial question, but that is where I am struggling to be confident in my proof. I feel like I am using what I need to prove to show what I need to prove.

Thank you!

Since $a\in\Bbb N$, $a+1\in\Bbb N$ too. And $b\in\Bbb N$. So, $(a+1)+b\sqrt5\in S$, by the definition of $S$, right? — José Carlos Santos, Aug 31 '21 at 16:19
What are you trying to prove? What does it mean to "be inductive"? — Mark Saving, Aug 31 '21 at 16:20
by inductive I mean that $1 \in S$ and $(x+1) \in S$ whenever $x \in S$. — James Bradley, Aug 31 '21 at 16:21
That seems a strange definition for “inductive.” Are you sure you have it right? Where is it used? — Thomas Andrews, Aug 31 '21 at 16:25
Positive. Exactly what the text says. A set $S$ is inductive iff $1 \in S$ and $(x + 1) \in S$ whenever $x \in S$. — James Bradley, Aug 31 '21 at 16:27
It is also inductive in the sense of Russell, in that $S$ is ordered under $<$ and for each $x\in S,$ there is a least $y\in S$ such that $x<y.$ This is a bit harder to prove, but still elementary. — Thomas Andrews, Aug 31 '21 at 16:36
For your conclusion, you just need: If $a\in\mathbb N,$ then $a+1\in\mathbb N.$ — Thomas Andrews, Aug 31 '21 at 16:43
Ahhh I see that now. Since we know $a \in \mathbb{N}$ and $\mathbb{N}$ is inductive then we know that $a+1 \in \mathbb{N}$. Thank you @ThomasAndrews. Is what I did above incorrect or just unnecessary? — James Bradley, Aug 31 '21 at 16:48
Proving that something is an inductive set doesn't amount to using induction.. In fact using induction is pretty much irrelevant here. — Trebor, Aug 31 '21 at 17:02
@Trebor Thanks! Yeah, I realized that with this problem and the info y'all have provided. — James Bradley, Aug 31 '21 at 18:19

score 1 · Answer 1 · answered Aug 31 '21 at 16:59

You have shown that $1\in S$
It remains to show that if $x \in S$ then $(x+1) \in S$

Assume $x\in S$ Then $x=a+b\sqrt{5}$ for some $a, b \in N $

Note that $$x+1= (a+b\sqrt{5})+1=(a+1)+b\sqrt{5}$$

Since N is inductive and $a\in N$, $(a+1)\in N $

Thus $x+1\in S$

Proof that $S = \{a + b\sqrt{5}: a,b \in \mathbb{N}\}$ is inductive.

1 Answers1