Discrete Mathematics - Recursion

Question

Given the following question by my professor:

 Recursively define the set of natural numbers divisible by 3.

My answer:

Basis clause: 0 is in S.

Inductive clause: For any natural number x, x*3 is in S.

Extremal clause: Nothing is in S unless it is obtained from the Basis and Inductive clause.

My inductive clause is apparently wrong, and I cannot figure out any other way to define all the natural numbers divisible by 3.

Any help on why I might be wrong?

Thanks!

Answer 1

Your definition defines the elements of the set in terms of the natural numbers, rather than in terms of the other elements of the set.

Here's a recursive definition along the lines of what he was probably looking for:

• Basis Clause: $0$ is in $S$.
• Inductive Clause: For any $x$ in $S$, $x+3$ is in $S$
• Extremal Clause: Nothing is in $S$ unless it is obtained by the above two clauses

See the difference?

Answer 2

Modifying Omnomnomnom's answer.

Basis Clause: $0$ is in S.

Inductive Clause: For any $x$ in S, $x+1$ is not in S, $x+2$ is not in S, $x+3$ is in S

Exercise for the reader: Show that all integers are decided.