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.