Trying to understand recursive definitions in discrete math

Question

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

Answer 1

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.

Answer 2

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$.