How do I find the inductive definition of the set defined as $\{2n+3m+1|n,m\in\mathbb N\}$?

Question

$\lbrace 2n+3m+1:n,m\in N\rbrace$ is the set of all positive integers except for $0$ and $2$. I need to know how to write its inductive definition.

This is part of the introduction on learning how to develop recursive functions using lambda calculus. I can do some of them but on others, such as this one, I get lost. How do you handle the multiple variables. Please explain how you got your answer as well since an answer doesn't do me much good if I don't know how to get it.

Here are two of the ones I know how to do.

$\lbrace 3n+2: n\in \mathbb N\rbrace$

Top Down: $n = 2; n - 3 \in S$

Bottom up: $2 \in S$; if $n \in S$, then $(n + 3) \in S$

Rule of Inference: $2 \in S$; if $n \in S$, then $(n+3) \in S$

$\lbrace(n,2n+1): n\in \mathbb N\rbrace$

Top Down: $(n,m)=(0,1);(n-1,m-2) \in S$

Bottom up: $(0,1) \in S$; if $(n,m) \in S$, then $(n+1,m+2) \in S$

Answer 1

A solution could be found by starting with $1$. Then, if $n\in S$, you require $n+f(n)\in S$ too, where $f(n)$ is 2 for $n=1$ and $1$ otherwise. One way to do this is to make use of the step function $\frac{x}{|x|}$, which is $-1$ for negative input and $+1$ for positive input. Inserting a horizontal shift so that the discontinuity is at $2$ rather than $0$, scaling down by 2 (since we want a span that's $1$ unit long, not $2$), inverting vertically since we want the larger jump to happen earlier, and shifting up by the proper amount ($\frac{3}{2}$)...

$$f(n) = \frac{3}{2}-\frac{n-2}{2|n-2|}$$

(Edited: I had it completely backwards the first time!)

So that means you can have: $1\in S$; if $n\in S$, then $n+\frac{3}{2}-\frac{n-2}{2|n-2|}\in S$.

EDIT: For moving down...

You just need a different step function: one with its discontinuity between $3$ and $4$. Also, it's negated from the one used for moving up.

$$g(n)= -\frac{3}{2}+\frac{n-3.5}{2|n-3.5|}$$

And then: $1\in S$; if $n\in S$, then $n-\frac{3}{2}+\frac{n-3.5}{2|n-3.5|}\in S$.

Answer 2

How's this: 1 and 4 are in $S$; if $n$ is in $S$, then $n+2$ is in $S$.

Answer 3

The most straightforward bottom up definition description of $S=\lbrace 2n+3m+1:n,m\in N\rbrace$ can be read directly from the expression $2n+3m+1$. The base case is clearly $n=m=0$, giving $1 \in S$. The term $2n$ tells you that if $k \in S$, then $k + 2 \in S$, and similarly, the $3m$ term tells you that if $k \in S$, then $k + 3 \in S$: these rules correspond to incrementing $n$ and $m$, respectively, by $1$. In short:

• $1 \in S$;
• if $k \in S$, then $k+2 \in S$; and
• if $k \in S$, then $k+3 \in S$.

This is not the most efficient recursive description of $S$, but it is the one that most directly matches the definition that you’ve been given. After you prove that $S$ is in fact the set of all positive integers except $2$, you can give a simpler recursive description $-$ Gerry Myerson’s, for instance.

I’m not familiar with your top down style of description, but if I’ve extrapolated correctly from your first example, the top down version of the bottom up description that I just gave is:

• $n=1$;
• $n-2 \in S$; and
• $n-3 \in S$.

(Your top down version for $\lbrace(n,2n+1): n\in N\rbrace$ must be incomplete; I’m guessing that the rest of it should be $(n-1,m-2) \in S$.)