1. Rule Induction Question

Here is the problem I'm trying to solve:

The set S is defined to be the least subset of Natural Numbers such that:

1. 1∈S
2. if n∈S then 3n∈S
3. if n∈S and n>2 then (n-2)∈S

I must firstly show that S={m∈ℕ| ∃r,s ∈ ℕ0. m=3^r - 2s} and secondly show that this is the set of all odd numbers. By rule induction, I know I can show that the property m=3^r - 2s holds for all members of S but this does not prove the above definition for S since S might only contain a subset of m=3^r - 2s for integers r and s. Could someone please explain this? I hope I've made the problem clear.

2. Indication:

When you have to prove a set equality (A=B), you prove that $\displaystyle A\subset B$ and $\displaystyle B\subset A$.

S=\left \{ m \in \mathbb{N} |\exists r, s\in \mathbb{N}^{*}, m=3^{r}-2s \right \}
First show that every m=3^{r}-2s is in S. (Hint - 3 \in S) Then show that every element from S can be written as [tex]3^{r}-2s, r, s \in \mathbb{N}^{*}.

3. Each inductive definition of some set A has two sides. One shows how to approximate A from below, i.e., how to construct subsets of A by building more and more elements of A. Elements of A are built using the rules given in the inductive definition. The other side shows how to bound A from above, i.e., how to prove that A is a subset of other sets that satisfy the same building rules. This is done using induction, which says that A is the least set that satisfy these building rules.

Let T = {m ∈ ℕ | ∃r,s ∈ ℕ0. m=3^r - 2s}. You've shown that S ⊆ T using structural induction (rule induction). Conversely, you can show T ⊆ S by showing how each element of T can be constructed using the building rules of S. Let m = 3^r - 2s ∈ T for some r, s. It is easy to see how m can be constructed using rules 1—3.

4. Thanks, I've manged to prove the first part now. What about showing that S is the set of odd numbers? Don't I need to show that every number of the form 2^k + 1 can be written in the form 2^m -3m? I'm not sure how to do this.

Originally Posted by emakarov
Each inductive definition of some set A has two sides. One shows how to approximate A from below, i.e., how to construct subsets of A by building more and more elements of A. Elements of A are built using the rules given in the inductive definition. The other side shows how to bound A from above, i.e., how to prove that A is a subset of other sets that satisfy the same building rules. This is done using induction, which says that A is the least set that satisfy these building rules.

Let T = {m ∈ ℕ | ∃r,s ∈ ℕ0. m=3^r - 2s}. You've shown that S ⊆ T using structural induction (rule induction). Conversely, you can show T ⊆ S by showing how each element of T can be constructed using the building rules of S. Let m = 3^r - 2s ∈ T for some r, s. It is easy to see how m can be constructed using rules 1—3.

5. You can prove by induction on n that there exist r, s such that 2n + 1 = 3^r - 2s. For the step, consider two cases: when s from the induction hypothesis equals 0 and when it is > 0. The second case is trivial.