# Trying to understand recursive definitions in discrete math

Consider the recursive definition of the natural numbers:

• Basis: $$0 \in \mathbb{N}$$
• Recursive step: if $$n \in \mathbb{N}$$ , then $$s(n) \in \mathbb{N}$$

Give recursive definitions of:

• $$T_0$$ the set of natural numbers that are divisible by 3
• $$T_1$$ the set of natural numbers with a remainder of 1 when divided by 3

I'm having trouble understanding the adaptation of the basis and recursion step for natural numbers. Should I approach it something like:

Basis: if $$n = 0, {0\over 3}$$ is divisible by 3
Recursive: if $$n \in \mathbb{N}$$, then $$s(n+3)$$ is divisible by 3 ( where $$s$$ is the successor function )

I will of course need some type of closure. I would appreciate any help trying to grasp the concept

• I believe that you should either say $n+3$ is divisible by $3$ or $s(s(s(n)))$ is divisible by $3$ Feb 11 '16 at 19:40

For the basis step, you don't want to state that $0/3$ is divisible by $3$, you just state that $0$ is divisible by $3$.
For the recursive step: you assume that $n \in \mathbb{N}$ is divisible by 3, then say that this implies that some other number is divisible by 3. To get what that other number is, think about the numbers divisible by $3$, then think about the relationship between them in terms of the successor operation.
Recursive definition of the set $T_0$ of natural numbers divisible by $3$:
• Basis: $0\in T_0$
• Recursive step: if $n\in T_0$, $s(s(s(n)))\in T_0$.
Try to figure out how to modify it to get the set $T_1$ of natural numbers with a remainder of $1$ when divided by $3$.