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

  • $\begingroup$ I believe that you should either say $n+3$ is divisible by $3$ or $s(s(s(n)))$ is divisible by $3$ $\endgroup$
    – stity
    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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.