1
$\begingroup$

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

  • 0
    @Gerry They are all inductive definitions. They all mean the same thing it's just different ways of writing it. Top down is the most important method because later in the class when I have to write programs that check to see if something is in a set, I would have to use Top down because of the way programming works.2011-09-01

3 Answers 3

0

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

  • 0
    How would I invert that for top down form? For top down I would need: n - f(n) where f(n) = -2 when n = 3 and -1 otherwise.2011-09-01
2

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

  • 0
    I think this answer is great. The OP might be objecting because he wants something that simultaneously indexes the set; i.e., has a single seed. @C Dawg: Is that what you are looking for?2011-09-01
2

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